\magnification=\magstep1
\centerline{Mathematics 371 -- Numerical Analysis}
\centerline{Selected Solutions -- Midterm Problem Set 2}
\centerline{\it November 14, 2001}
\bigskip
\noindent
I.  
\item{A)}  The desired polynomial can be constructed using one-variable
Lagrange polynomials:
$$\eqalign{
Q_{i,j}(x,y) &= L_{n,i}(x)L_{m,j}(y)\cr
&={\prod_{p\ne i}(x - x_p)\over \prod_{p\ne i}(x_i - x_p)}\cdot
  {\prod_{q\ne j}(y - y_q)\over \prod_{q\ne j}(y_j - y_q)}\cr}$$
Note that $Q(x_k,y_\ell)$  is zero unless $k = i$ and $\ell = j$ (since
at least one factor in the numerator of the product is zero), 
and $Q(x_i,y_j) = 1$.
\bigskip
\item{B)}  {\it Existence:} Given $z_{i,j}$, consider the polynomial
$$\eqalign{
p(x,y) &= \sum_{i=0}^n \sum_{j=0}^m z_{i,j} Q_{i,j}(x,y)\cr
       &= \sum_{i=0}^n \sum_{j=0}^m z_{i,j} L_{n,i}(x)L_{m,j}(y)\cr}$$
Then by part A, we know that for all $(k,\ell)$
$$p(x_k,y_\ell) = \sum_{i=0}^n \sum_{j=0}^m z_{i,j} Q_{i,j}(x_k,y_\ell) 
= 0 + \cdots + 0 + z_{k,\ell}\cdot 1 + 0 + \cdots + 0.$$
Since each $Q_{i,j}(x,y)$ is of degree $\le n$ in $x$ and degree $\le m$
in $y$, the same is true for $p(x,y)$.  This proves existence for a
polynomial satisfying the conditions given.  

\medskip
\item{} {\it 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 \le i \le n$ and $0\le j \le m$.  Then the polynomial 
$p(x,y) = p_1(x,y) -p_2(x,y)$ has degree $\le n$ in $x$ and degree $\le 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:
$$p(x,y) = c_m(x)y^m + c_{m-1}(x)y^{m-1} + \cdots +c_1(x)y + c_0(x).\leqno(1)$$
Each coefficient polynomial $c_p(x)$ has degree $\le n$ in $x$, since
$p(x,y)$ has degree $\le n$ in $x$.  

\medskip
\item{} If we substitute $x = x_i$, any $0 \le i \le n$ into (1), we obtain
$$p(x_i,y) = c_m(x_i)y^m + c_{m-1}(x_i)y^{m-1} + \cdots +c_1(x_i)y + c_0(x_i)$$
This is a polynomial of degree $\le m$ in $y$ that has $m + 1$ roots
$y_0, y_1, \ldots, y_m$.  Hence it must be identically zero, or 
$c_m(x_i) = 0, \ldots, c_0(x_i) = 0$.  But this is true for all $x_i$
so each of the $c_p(x)$ are polynomials of degree $\le 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)$.

\bigskip
\noindent
III.
\item{A)}  The Taylor series for $f$ looks like:
$$f(x) = f(x_0) + f'(x_0)(x-x_0) + {f''(x_0)\over 2!}(x-x_0)^2 + 
{f'''(x_0)\over 3!}(x-x_0)^3 + {f^{(4)}(\xi(x))\over 4!}(x-x_0)^4$$
So at $x = x_0+h$ and $x = x_0 -h$, we get
$$\eqalign{
f(x_0+h) &= f(x_0) + f'(x_0)h + {f''(x_0)\over 2! } h^2 + 
{f'''(x_0)\over 3!}h^3 + {f^{(4)}(\xi(x_0+h))\over 4! }h^4\cr
f(x_0-h) &= f(x_0) - f'(x_0)h + {f''(x_0)\over 2! }h^2 - 
{f'''(x_0)\over 3! }h^3 + {f^{(4)}(\xi(x_0-h))\over 4! }h^4\cr}$$
Add these last two equations to get:
$$f(x_0+h) + f(x_0-h) = 2f(x_0) + f''(x_0)h^2 + {1\over 24} (f^{(4)}(\xi_1) + 
f^{(4)}(\xi_2))h^4$$
where $\xi_1 = \xi(x_0+h)$ and $\xi_2=\xi(x_0-h)$.  Rearranging yields
$$f''(x_0) = {f(x_0+h) - 2f(x_0)+ f(x_0-h) \over h^2} - {1\over 24} (f^{(4)}(\xi_1) + 
f^{(4)}(\xi_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 
$${1\over 24} (f^{(4)}(\xi_1) + f^{(4)}(\xi_2))h^2 = {1\over 12} f^{(4)}(\xi)h^2$$
for some $\xi \in [x_0-h,x_0+h]$.
\bigskip
\item{B)}  Consider 
$${d_1\over d_1 + d_2} F(c_1) + {d_2\over 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
$${d_1\over d_1 + d_2} F(c_1) + {d_2\over d_1 + d_2} F(c_2) \le 
{d_1\over d_1 + d_2} M + {d_2\over d_1 + d_2} M = M$$
Similarly,
$${d_1\over d_1 + d_2} F(c_1) + {d_2\over d_1 + d_2} F(c_2) \ge 
{d_1\over d_1 + d_2} m + {d_2\over d_1 + d_2} m = m$$
Hence for all $c_1,c_2$, 
$$m \le {d_1\over d_1 + d_2} F(c_1) + {d_2\over d_1 + d_2} F(c_2) \le M$$
Then by the Intermediate Value Theorem, there exists a $c\in [a,b]$
such that 
$$F(c) = {d_1\over d_1 + d_2} F(c_1) + {d_2\over d_1 + d_2} F(c_2)$$
which is equivalent to what we wanted to show.
\bye
