\magnification=\magstep1
\overfullrule=0pt
\centerline{Mathematics 371 -- Numerical Analysis}
\centerline{Selected Solutions -- Problem Set 3}
\centerline{\it October 19, 2001}
\bigskip
\noindent
Section 3.1/3a and 7a.  Given:
$$\matrix{x_i & f(x_i)\cr
      8.1 & 16.94410\cr
      8.3 & 17.56492\cr
      8.6 & 18.50515\cr
      8.7 & 18.82091\cr}$$
To approximate $f(8.4)$ with an interpolating polynomial of degree
1, we would almost always choose the two closest points ``bracketing''
8.4 -- here 8.3 and 8.6.  The Lagrange polynomial is
$$p_1(x) = 17.56492 (x - 8.6)/(8.3 - 8.6) + 18.50515 (x-8.3)(8.6-8.3) = 
3.1341x - 8.44811$$
and $p_1(8.4) = (3.1341)(8.4)-8.44811 = 17.87833$.

With a polynomial of degree 2, we can choose any 3 $x_i$ ``bracketing''
8.4.  The book's choice was 8.3,8.6,8.7:
$$\eqalign{p_2 &= 17.56492{(x - 8.6)(x - 8.7)\over (8.3 - 8.6)(8.3-8.7)}
        + 18.50515 {(x - 8.3)(x - 8.7)\over (8.6 - 8.3)(8.6-8.7)}\cr
       &\qquad  + 18.82091 {(x - 8.3)(x - 8.6)\over (8.7 - 8.3)(8.7-8.6)}\cr}$$
Then $p_2(8.4) = 17.877155$.

Finally for the polynomial of degree 3, we use all 4 points
$$\eqalign{p_3 &= 16.94410{(x-8.3)(x - 8.6)(x - 8.7)\over (8.1 - 8.3)(8.1-8.6)(8.1-8.7)} + 
17.56492{(x-8.1)(x - 8.6)(x - 8.7)\over (8.3 - 8.1)(8.3-8.6)(8.3-8.7)}\cr
      &\quad  + 18.50515{(x-8.1)(x - 8.3)(x - 8.7)\over (8.6 - 8.1)(8.6-8.3)(8.6-8.7)}
   + 18.82091 {(x-8.1)(x - 8.3)(x - 8.6)\over (8.7 - 8.1)(8.7-8.3)(8.7-8.6)}\cr}$$
And $p_3(8.4) = 17.877155$.

\bigskip
Since in problem 7a it is given that $f(x) = x\ln(x)$, we have actual errors:
$$\eqalign{
|f(8.4) - p_1(8.4)| &= |18.87714633 -  17.87833| = .00118367\cr
|f(8.4) - p_2(8.4)| &= |18.87714633 -  17.877155| = .00000867\cr}$$
The error bounds for interpolation come from the error formula:
$$f(x) = p_n(x) + {f^{(n+1)}(\xi) \over (n+1)!} (x-x_0)(x-x_1)\cdots (x-x_n)$$
For $n = 1$ here, $f''(\xi) = 1/\xi$, so $|f''(\xi)| \le 1/8.3$ on 
the interval $[8.3,8.6]$ that we used to get $p_1$.  We get:
$$|f(8.4) - p_1(8.4)| \le {1\over 2\cdot 8.3}|8.4 - 8.3||8.4-8.6| \doteq .001205$$
which is just larger than the actual error.
Similarly $f'''(x) = -1/x^2$, so 
$$|f(8.4) - p_3(8.4)| \le {1\over 6\cdot (8.3)^2}|8.4 - 8.3||8.4-8.6||8.4-8.7| \doteq .0000145$$
and the actual error is within the error bound again.

\bigskip
\noindent
3.1/17.  To construct the table as described, we want to make sure that
the error bound for linear interpolation ($n = 1$) is less than
$10^{-6}$ for all $x$ with $1 \le x \le 10$, and $f(x) = \log(x)$ (common
logarithm).  We have:
$f(x) = \ln(x)/\ln(10)$, so $f''(x) = {-1\over x^2\ln(10)}$.  For $1\le x\le 10$
this is largest at $x = 1$.  Then
$$|\log(x) - p_1(x)| \le {1\over 2\ln(10)} |x - x_i|\cdot |x - (x_i + h)|$$
if we use the table entries for $x_i$ and $x_{i+1} = x_i + h$.
For $x$ between $x_i$ and $x_i+h$, the maximum of 
$|x - x_i|\cdot |x - (x_i + h)| = |(x-x_i)(x - (x_i + h)|$
occurs at $x = x_i+h/2$ and equals $(h/2)^2$.  Hence our error bound gives:
$$|\log(x) - p_1(x)| \le {1\over 2\ln(10)} \left({h\over 2}\right)^2 = 
{h^2 \over 8\ln(10)}$$
Then
$${h^2 \over 8\ln(10)} < 10^{-6} \Leftrightarrow
h < \sqrt{8\ln(10)\cdot 10^{-6}} \doteq .00429$$
Taking $h = .004$ (exactly 250 entries for between one integer 
$x$ and the next will make $x = 10$ one of the entries.
\bigskip
\noindent
3.1/29c.   For this part, you need to use {\it generalizations} of
the results from part a on the ``Bernstein polynomials'' for $1$ and
$x$:
$$\eqalign{
\sum_{k=0}^m {m\choose k} \left({k\over m}\right) x^k (1-x)^{m-k} &= x\ (*)\cr
\sum_{k=0}^m {m\choose k} x^k (1-x)^{m-k} &= 1\ (**)\cr}$$
Then for $f(x) = x^2$, using part b and the fact that the
term in the sum for $B_n(x)$ with $k = 0$ is equal to zero, we have 
\vfill\eject
$$\eqalign{
B_n(x) &= \sum_{k=0}^n {n\choose k} \left({k\over n}\right)^2 x^k (1-x)^{n-k}\cr
&= \sum_{k=0}^n {n-1\choose k-1} \left({k\over n}\right) x^k (1-x)^{n-k}\cr
&=  \sum_{k=1}^n {n-1\choose k-1} \left({k\over n}\right) x^k (1-x)^{n-k}\cr}$$
Change the summation index to $\ell = k-1$, split into two sums, and 
pull out common factors:
$$\eqalign{
&=\sum_{\ell=0}^{n-1} {n-1\choose \ell} \left({\ell+1\over n}\right) x^{\ell+1} (1-x)^{n-1-\ell}\cr
&=\sum_{\ell=0}^{n-1} {n-1\choose \ell} \left({\ell\over n}\right) x^{\ell+1} (1-x)^{n-1-\ell}
+\sum_{\ell=0}^{n-1} {n-1\choose \ell} \left({1\over n}\right) x^{\ell+1} (1-x)^{n-1-\ell}\cr
&={(n-1)x\over n} \sum_{\ell=0}^{n-1} {n-1\choose \ell} \left({\ell\over n-1}\right) x^{\ell} (1-x)^{n-1-\ell}
+ {x\over n}\sum_{\ell=0}^{n-1} {n-1\choose \ell} x^{\ell} (1-x)^{n-1-\ell}\cr
&={(n-1)x\over n}\cdot x + {x\over n}\cr
}$$
(using (*) and (**) above for the last step).  This is what we wanted to show.
\bye 