Mathematics 371 – Numerical Analysis Selected Solutions – Midterm Problem Set 2 November 14, 2001

I. A) The desired polynomial can be constructed using one-variable Lagrange polynomials:

\begin{aligned}Q_{i,j}(x, y) & = L_{n,i}(x)L_{m,j}(y) \\ & = \frac{∏_{p≠i}(x − x_{p})}{∏_{p≠i}(x_{i} − x_{p})} · \frac{∏_{q≠j}(y − y_{q})}{∏_{q≠j}(y_{j} − y_{q})} \end{aligned}

Note that Q(x_{k}, y_{ℓ}) is zero unless k = i and ℓ = j (since at least one factor in the numerator of the product is zero), and Q(x_{i}, y_{j}) = 1.

B) Existence: Given z_{i,j}, consider the polynomial

\begin{aligned}p(x, y) & = ∑_{i=0}^{n} ∑_{j=0}^{m} z_{i,j}Q_{i,j}(x, y) \\ & = ∑_{i=0}^{n} ∑_{j=0}^{m} z_{i,j}L_{n,i}(x)L_{m,j}(y) \end{aligned}

Then by part A, we know that for all (k, ℓ)

p(x_{k}, y_{ℓ}) = ∑_{i=0}^{n} ∑_{j=0}^{m} z_{i,j}Q_{i,j}(x_{k}, y_{ℓ}) = 0 + ⋯ + 0 + z_{k,ℓ} · 1 + 0 + ⋯ + 0.

Since each Q_{i,j}(x, y) is of degree ≤ n in x and degree ≤ m in y, the same is true for p(x, y). This proves existence for a polynomial satisfying the conditions given.

Uniqueness: To prove that p(x, y) is unique, suppose we have two polynomials p_{1}(x, y) and p_{2}(x, y) satisfying p_{1}(x_{i}, y_{j}) = p_{2}(x_{i}, y_{j}) = z_{i,j} for all 0 ≤ i ≤ n and 0 ≤ j ≤ m. Then the polynomial p(x, y) = p_{1}(x, y) − p_{2}(x, y) has degree ≤ n in x and degree ≤ m in y and is zero at the (n + 1)(m + 1) points (x_{i}, y_{j}). We can collect powers of y to write:

(1)  p(x, y) = c_{m}(x)y^{m} + c_{m−1}(x)y^{m−1} + ⋯ + c_{1}(x)y + c_{0}(x).

Each coefficient polynomial c_{p}(x) has degree ≤ n in x, since p(x, y) has degree ≤ n in x.

If we substitute x = x_{i}, any 0 ≤ i ≤ n into (1), we obtain

p(x_{i}, y) = c_{m}(x_{i})y^{m} + c_{m−1}(x_{i})y^{m−1} + ⋯ + c_{1}(x_{i})y + c_{0}(x_{i})

This is a polynomial of degree ≤ m in y that has m + 1 roots y_{0}, y_{1}, …, y_{m}. Hence it must be identically zero, or c_{m}(x_{i}) = 0, …, c_{0}(x_{i}) = 0. But this is true for all x_{i} so each of the c_{p}(x) are polynomials of degree ≤ n in x with n + 1 distinct roots x_{i}. Therefore all of the c_{p}(x) are identically zero. Hence p(x, y) is also identically zero, so p_{1}(x, y) = p_{2}(x, y).

III. A) The Taylor series for f looks like:

f(x) = f(x_{0})+f′(x_{0})(x−x_{0})+ \frac{f′′(x_{0})}{2!}(x−x_{0})^{2}+ \frac{f′′′(x_{0})}{3!}(x−x_{0})^{3}+ \frac{f^{(4)}(ξ(x))}{4!}(x−x_{0})^{4}

So at x = x_{0} + h and x = x_{0} − h, we get

\begin{aligned}f(x_{0} + h) & = f(x_{0}) + f′(x_{0})h + \frac{f′′(x_{0})}{2!}h^{2} + \frac{f′′′(x_{0})}{3!}h^{3} + \frac{f^{(4)}(ξ(x_{0} + h))}{4!}h^{4} \\ f(x_{0} − h) & = f(x_{0}) − f′(x_{0})h + \frac{f′′(x_{0})}{2!}h^{2} − \frac{f′′′(x_{0})}{3!}h^{3} + \frac{f^{(4)}(ξ(x_{0} − h))}{4!}h^{4} \end{aligned}

Add these last two equations to get:

f(x_{0} + h) + f(x_{0} − h) = 2f(x_{0}) + f′′(x_{0})h^{2} + \frac{1}{24}(f^{(4)}(ξ_{1}) + f^{(4)}(ξ_{2}))h^{4}

where ξ_{1} = ξ(x_{0} + h) and ξ_{2} = ξ(x_{0} − h). Rearranging yields

f′′(x_{0}) = \frac{f(x_{0} + h) − 2f(x_{0}) + f(x_{0} − h)}{h^{2}} − \frac{1}{24}(f^{(4)}(ξ_{1}) + f^{(4)}(ξ_{2}))h^{2}.

To finish, we need to assume that f^{(4)} is continuous on an interval containing [x_{0} − h, x_{0} + h]. Then the “Useful Lemma” (part B) implies that

\frac{1}{24}(f^{(4)}(ξ_{1}) + f^{(4)}(ξ_{2}))h^{2} = \frac{1}{12}f^{(4)}(ξ)h^{2}

for some ξ ∈ [x_{0} − h, x_{0} + h].

B) Consider

\frac{d_{1}}{d_{1} + d_{2}} F (c_{1}) + \frac{d_{2}}{d_{1} + d_{2}} F (c_{2})

By the standard properties of continuous functions, F has a maximum M and a minimum m on the interval [a, b]. Hence

\frac{d_{1}}{d_{1} + d_{2}} F (c_{1}) + \frac{d_{2}}{d_{1} + d_{2}} F (c_{2}) ≤ \frac{d_{1}}{d_{1} + d_{2}} M + \frac{d_{2}}{d_{1} + d_{2}} M = M

Similarly,

\frac{d_{1}}{d_{1} + d_{2}} F (c_{1}) + \frac{d_{2}}{d_{1} + d_{2}} F (c_{2}) ≥ \frac{d_{1}}{d_{1} + d_{2}} m + \frac{d_{2}}{d_{1} + d_{2}} m = m

Hence for all c_{1}, c_{2},

m ≤ \frac{d_{1}}{d_{1} + d_{2}} F (c_{1}) + \frac{d_{2}}{d_{1} + d_{2}} F (c_{2}) ≤ M

Then by the Intermediate Value Theorem, there exists a c ∈ [a, b] such that

F (c) = \frac{d_{1}}{d_{1} + d_{2}} F (c_{1}) + \frac{d_{2}}{d_{1} + d_{2}} F (c_{2})

which is equivalent to what we wanted to show.