Mathematics 371 – Numerical Analysis Selected Solutions – Problem Set 3 October 19, 2001

Section 3.1/3a and 7a. Given:

\begin{matrix}x_{i} & f(x_{i}) \\ 8.1 & 16.94410 \\ 8.3 & 17.56492 \\ 8.6 & 18.50515 \\ 8.7 & 18.82091 \end{matrix}

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:

\begin{aligned}p_{2} & = 17.56492\frac{(x − 8.6)(x − 8.7)}{(8.3 − 8.6)(8.3 − 8.7)} + 18.50515\frac{(x − 8.3)(x − 8.7)}{(8.6 − 8.3)(8.6 − 8.7)} \\ & + 18.82091\frac{(x − 8.3)(x − 8.6)}{(8.7 − 8.3)(8.7 − 8.6)} \end{aligned}

Then p_{2}(8.4) = 17.877155.

Finally for the polynomial of degree 3, we use all 4 points

\begin{aligned}p_{3} & = 16.94410\frac{(x − 8.3)(x − 8.6)(x − 8.7)}{(8.1 − 8.3)(8.1 − 8.6)(8.1 − 8.7)} + 17.56492\frac{(x − 8.1)(x − 8.6)(x − 8.7)}{(8.3 − 8.1)(8.3 − 8.6)(8.3 − 8.7)} \\ & + 18.50515\frac{(x − 8.1)(x − 8.3)(x − 8.7)}{(8.6 − 8.1)(8.6 − 8.3)(8.6 − 8.7)} + 18.82091\frac{(x − 8.1)(x − 8.3)(x − 8.6)}{(8.7 − 8.1)(8.7 − 8.3)(8.7 − 8.6)} \end{aligned}

And p_{3}(8.4) = 17.877155.

Since in problem 7a it is given that f(x) = x ln(x), we have actual errors:

\begin{aligned}|f(8.4) − p_{1}(8.4)| & = |18.87714633 − 17.87833| = .00118367 \\ |f(8.4) − p_{2}(8.4)| & = |18.87714633 − 17.877155| = .00000867 \end{aligned}

The error bounds for interpolation come from the error formula:

f(x) = p_{n}(x) + \frac{f^{(n+1)}(ξ)}{(n + 1)!}(x − x_{0})(x − x_{1}) ⋯ (x − x_{n})

For n = 1 here, f′′(ξ) = 1/ξ, so |f′′(ξ)| ≤ 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)| ≤ \frac{1}{2 · 8.3}|8.4 − 8.3||8.4 − 8.6| ≐ .001205

which is just larger than the actual error. Similarly f′′′(x) = −1/x^{2}, so

|f(8.4) − p_{3}(8.4)| ≤ \frac{1}{6 · (8.3)^{2}} |8.4 − 8.3||8.4 − 8.6||8.4 − 8.7| ≐ .0000145

and the actual error is within the error bound again.

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 ≤ x ≤ 10, and f(x) = log(x) (common logarithm). We have: f(x) = ln(x)/ ln(10), so f′′(x) = \frac{−1}{x^{2} ln(10)}. For 1 ≤ x ≤ 10 this is largest at x = 1. Then

| log(x) − p_{1}(x)| ≤ \frac{1}{2 ln(10)}|x − x_{i}| · |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}| · |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)| ≤ \frac{1}{2 ln(10)} (\frac{h}{2})^{2} = \frac{h^{2}}{8 ln(10)}

Then

\frac{h^{2}}{8 ln(10)} < 10^{−6} ⇔ h < \sqrt{8 ln(10) · 10^{−6}} ≐ .00429

Taking h = .004 (exactly 250 entries for between one integer x and the next will make x = 10 one of the entries.

3.1/29c. For this part, you need to use generalizations of the results from part a on the “Bernstein polynomials” for 1 and x:

\begin{aligned}∑_{k=0}^{m} \binom{m}{k} (\frac{k}{m}) x^{k}(1 − x)^{m−k} & = x (∗) \\ ∑_{k=0}^{m} \binom{m}{k}x^{k}(1 − x)^{m−k} & = 1 (∗∗) \end{aligned}

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

B_{n}(x) = ∑_{k=0}^{n} \binom{n}{k} (\frac{k}{n})^{2} x^{k}(1 − x)^{n−k}

= ∑_{k=0}^{n} \binom{n − 1}{k − 1} (\frac{k}{n}) x^{k}(1 − x)^{n−k}

= ∑_{k=1}^{n} \binom{n − 1}{k − 1} (\frac{k}{n}) x^{k}(1 − x)^{n−k}

Change the summation index to ℓ = k − 1, split into two sums, and pull out common factors:

= ∑_{ℓ=0}^{n−1} \binom{n − 1}{ℓ} (\frac{ℓ + 1}{n}) x^{ℓ+1}(1 − x)^{n−1−ℓ}

= ∑_{ℓ=0}^{n−1} \binom{n − 1}{ℓ} (\frac{ℓ}{n}) x^{ℓ+1}(1 − x)^{n−1−ℓ} + ∑_{ℓ=0}^{n−1} \binom{n − 1}{ℓ} (\frac{1}{n}) x^{ℓ+1}(1 − x)^{n−1−ℓ}

= \frac{(n − 1)x}{n} ∑_{ℓ=0}^{n−1} \binom{n − 1}{ℓ} (\frac{ℓ}{n − 1}) x^{ℓ}(1 − x)^{n−1−ℓ} + \frac{x}{n} ∑_{ℓ=0}^{n−1} \binom{n − 1}{ℓ}x^{ℓ}(1 − x)^{n−1−ℓ}

= \frac{(n − 1)x}{n} · x + \frac{x}{n}

(using (*) and (**) above for the last step). This is what we wanted to show.