Numerical Analysis I, Fall 2020 (http://www.math.nthu.edu.tw/˜ wangwc/)

Brief Solution to Midterm 02

Dec 09, 2020.

1. (10 pts) State (need not prove) the error formula of Lagrangian interpolation for smooth functions defined on [a, b] with data given on uniformly spaced nodes x_{0}, ⋯, x_{n} on [a, b] where x_{j} = a + jh, h = (b − a)/n.

Ans:

Let P_{n}(x) be the nth Lagrange interpolating polynomail. The error formula is given by

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

where ξ(x) ∈ (a, b).

2. (12 pts) Let P_{n} be the degree n interpolating polynomial of f(x) = \frac{1}{1 + x^{2}} on the

uniformly spaced nodes x_{0}, ⋯, x_{n} on [−5, 5] with x_{j} = −5 + jh, h = 10/n. Is it true that

max_{−5≤x≤5} |f(x) − P_{n}(x)| → 0 as n → ∞?

Use either analytic proof or numerical evidence to support your claim.

Ans: No. f^{(n)} grows fast in n. The error formula does not guarantee convergence (4 pts).

The interpolating polynomial oscillates wildly on [−5, 5] for x ≠ x_{i} as n increases. Some demonstration of the graph or interpolating polynomial value at a fixed x ≠ x_{i} with n ∼ 10 − 20 will do (8 pts).

3. (12 pts) Suppose that we are to construct a piecewise polynomial interpolation S(x) such that S(x_{i}) = f(x_{i}), S′(x_{i}) = f′(x_{i}), i = 0, ⋯, n with additional continuity conditions for S′′ and S′′′ on the interior nodes x_{1}, ⋯, x_{n−1}. If we use polynomials of the same degree on each of the interval [x_{0}, x_{1}], ⋯, [x_{n−1}, x_{n}], what is the minimal degree needed in each interval? How many additional end conditions are needed? Count carefully and explain (give details).

Ans: Values of S at x_{0}, x_{n}: one condition each.

Values of S at x_{1}, ⋯ x_{n−1}: two conditions each.

Values of S′ at x_{0}, x_{n}: one condition each.

Values of S’ at x_{1}, ⋯ x_{n−1}: two conditions each.

Continuity of S′′ at x_{1}, ⋯ x_{n−1}: one condition each.

Continuity of S′′′ at x_{1}, ⋯ x_{n−1}: one condition each.

(6 pts)

Total 6n − 2 conditions. Therefore we require minimal 6n unknowns or degree 5 polynomials on each interval and additional 2 boundary conditions (6 pts).

4. (12 pts) Let x_{i} = 0.01∗i. Use all or part of the data (x_{0}, sin(x_{0})), (x_{1}, sin(x_{1})), ⋯, (x_{100}, sin(x_{100})) and inverse cubic spline interpolation method to find an approximate value of sin^{−1}(0.3). Partial credit if you use a different interpolation method.

Ans:

x = 0 : .01 : 1; y = sin(x).

Answer = spline(y, x, 0.3) = 0.3046926539299876 .

5. (12 pts) Suppose f is smooth and the data f(x), f(x±h), f(x±2h), ⋯ are prescribed.

(a) Find a second order approximation of f′(x + \frac{h}{2}) with minimal number of data points and derive an error identity of the form f′(x+\frac{h}{2})−f′_{h}(x+\frac{h}{2}) = C_{1}f^{(n_{1})}(ξ_{1})h^{2}.

(b) Find a fourth order approximation of f′(x+\frac{h}{2}) with minimal number of data points and derive an error bound of the form |f′(x + \frac{h}{2}) − f′_{h}(x + \frac{h}{2})| ≤ C_{2}|f^{(n_{2})}(ξ_{2})|h^{4}.

Ans:

(a) Apply Taylor expansion to f(x + h) and f(x) around f(x + \frac{h}{2}) leads to

\frac{f(x + h) − f(x)}{h} = f′(x + \frac{h}{2}) + \frac{h^{2}}{24}f′′′(ξ))(4pts).

(b) Also

\frac{f(x + h) − f(x)}{h} = f′(x + \frac{h}{2}) + \frac{h^{2}}{24}f′′′(x + \frac{h}{2}) + \frac{h^{4}}{1920}f^{(5)}(ξ_{1})

It follows that \frac{f(x+2h)−f(x−h)}{3h} admits a similar estimate with h = (x + h) − x replaced by 3h = (x + 2h) − (x − h):

\frac{f(x + 2h) − f(x − h)}{3h} = f′(x + \frac{h}{2}) + \frac{(3h)^{2}}{24} f′′′(x + \frac{h}{2}) + \frac{(3h)^{4}}{1920} f^{(5)}(ξ_{2})

Therefore

f′_{h}(x + \frac{h}{2}) = \frac{9}{8} \frac{f(x + h) − f(x)}{h} − \frac{1}{8} \frac{f(x + 2h) − f(x − h)}{3h}(4pts).

with

f′_{h}(x + \frac{h}{2}) = f′(x + \frac{h}{2}) + E_{h}

and

|E_{h}| ≤ \frac{3}{512}h^{4}|f^{(5)}(ξ)|(4pts).

6. (12 pts) Give formula for composite trapezoidal rule, midpoint rule and Simpson rule using (x_{i}, f(x_{i})), i = 0 ⋯, n, where x_{j} = a + jh, h = (b − a)/n (you can use (x_{i−1/2}, f(x_{i−1/2})), i = 1, ⋯, n for midpoint rule if you prefer). Give corresponding error formula of the form: I_{h}(a, b) − I(a, b) = C ∑_{i} h^{p}f^{(q)}(ξ_{i}) (find C and p, q for composite trapezoidal and midpoint rule, need not derive) and |I_{h}(a, b) − I(a, b)| ≤ ∑_{i} Ch^{p}|f^{(q)}(ξ_{i})|. (find only p, q for composite Simpson’s rule). Need not derive if you are sure about the answer.

Ans:

Composite Trapezoidal Rule:

∫_{a}^{b} f(x)dx = \frac{h}{2}[f(a) + 2 ∑_{j=1}^{n−1} f(x_{j}) + f(b)] − \frac{b − a}{12}f′′(μ)h^{2}

where n is an integer, h = \frac{b−a}{n}, x_{j} = a + jh, for j = 0, 1, ..., n, and some μ ∈ (a, b) (4 pts)

Composite Midpoint Rule:

∫_{a}^{b} f(x)dx = 2h ∑_{j=1}^{n/2} f(x_{2j−1}) + \frac{b − a}{6}f′′(μ)h^{2}

where n is an integer, h = \frac{b−a}{n}, x_{j} = a + jh, for j = 0, 1, ..., n, and some μ ∈ (a, b) (4 pts)

Composite Simpson’s Rule:

∫_{a}^{b} f(x)dx = \frac{h}{3}[f(a) + 4 ∑_{j=1}^{n/2} f(x_{2j−1}) + 2 ∑_{j=1}^{n/2−1} f(x_{2j}) + f(b)] − \frac{b − a}{180}f^{(4)}(μ)h^{4}

where n is an integer, h = \frac{b−a}{n}, x_{j} = a + jh, for j = 0, 1, ..., n, and some μ ∈ (a, b) (4 pts)

7. (15 pts) Use composite trapezoidal rule N_{1}(h)to evaluate ∫_{0}^{1} x^{0.5}dx and find the rate of convergence (p in Ch^{p}) numerically. Then use Richardson extrapolation to derive N_{2}(h) and find the corresponding p for N_{2}(h) numerically.

Ans:

I = N_{1}(h) + Ch^{p} + ⋯

I = N_{1}(2h) + C(2h)^{p} + ⋯

p ≈ log_{2} \frac{I − N_{1}(2h)}{I − N_{1}(h)}

Numerical result shows that p = 1.5. (3 pts) Therefore

I = N_{1}(2h) + C(2h)^{\frac{3}{2}} + ⋯

or

I = N_{1}(\frac{h}{2}) + C(\frac{h}{2})^{\frac{3}{2}} + ⋯

Use either N_{1}(h) and N_{1}(2h) or N_{1}(h) and N_{1}(\frac{h}{2}) to get

N_{2}(h) = \frac{2\sqrt{2}}{2\sqrt{2} − 1}N_{1}(h) − \frac{1}{2\sqrt{2} − 1}N_{1}(2h)

or

N_{2}(h) = \frac{2\sqrt{2}}{2\sqrt{2} − 1}N_{1}(\frac{h}{2}) − \frac{1}{2\sqrt{2} − 1}N_{1}(h)

Either one will do. (8 pts) Answer(4 pts):

I = N_{2}(h) + Ch^{p} + ⋯, p = 2

8. (15 pts) Find a quadrature of the form

∫_{−1}^{1} f(x)dx = α(f(γ) + f(−γ)) + βf(0)

with largest degree of precision p, where α, β ∈ R and 0 < γ < 1. Change the interval to ∫_{−h}^{h} f(x)dx and find corresponding α_{h}, β_{h}, γ_{h} in terms of h. Under the assumption (need not prove this assumption) that the error of this quadrature is of the form

α_{h}(f(γ_{h}) + f(−γ_{h})) + β_{h}f(0) = ∫_{−h}^{h} f(x)dx + Kf^{(n)}(ξ)h^{p},

find K, n and p and predict the order of convergence for the composite quadrature (i.e. what is q in |I_{h}(a, b) − I(a, b)| ≤ Ch^{q}?) Ans: Apply I(1) = I_{h}(1), I(x^{2}) = I_{h}(x^{2}) and I(x^{4}) = I_{h}(x^{4}) to get α = \frac{5}{9}, β = \frac{8}{9} and γ = \sqrt{\frac{3}{5}}.(4 pts)

Similar procedure for ∫_{−h}^{h} leads to α_{h} = \frac{5}{9}h, β_{h} = \frac{8}{9}h and γ_{h} = \sqrt{\frac{3}{5}}h. The formula is also exact for all x^{2k+1} due to symmetry. So degree of precision = 5. (3 pts) Therefore n = 6, p = 7 and apply I_{h}(x^{6}) to get K = −\frac{1}{15750}. (6 pts). And for the order of convergence for the composite quadrature is q = 6. (2 pts)

9. (5 pts) Use any method to find a solution of \sqrt{1 + 0.9x} − \sqrt{1 − 0.8x} = 1.0 × 10^{−10} to 15 correct digits. You need to prevent loss of accuracy. Standard methods only gives you about 5 correct digits (and no credit).

Ans:

Apply the following identity

a^{2} − b^{2} = (a + b)(a − b)

that avoids the subtraction of two nearly identical numbers and gives

f(x) = \frac{1.7x}{\sqrt{1 + 0.9x} + \sqrt{1 − 0.8x}} − 10^{−10}. (3 pts)

Then solve f(x) = 0 by any numerical method to find the solution

x_{∗} ≈ 1.17647058823875 × 10^{−10}. (2 pts)

10. (10 pts) It is known that the unique solution to f(x) = x+3 sin(x)−0.01 = 0 is located near x = 0. Find a fixed point iteration that will converge for any x_{0} ∈ [−\frac{1}{2}, \frac{1}{2}]. Show that your method satisfies the assumptions of a relevant Theorem, but need not prove the Theorem again. You can use the numerical values of sin(\frac{1}{2}), cos(\frac{1}{2}), exp(\frac{1}{2}), etc. in your proof.

Ans:

Direct fixed point iteration with x^{(k+1)} = g_{0}^{(k)}(x) = 0.01−3 sin(x^{(k)}) does not converge. Instead, a proper choice of α and g(x) = αx+(1−α)g_{0}(x) will result in local convergence (2 pts). One could choose

α = \frac{g′_{0}(ξ)}{g′_{0}(ξ) − 1}

for some ξ near 0. Since ξ ≈ 0, g′_{0}(ξ) ≈ −3, we take α = \frac{−3}{−3−1} = \frac{3}{4}. (2 pts)

Since g(x) = \frac{3}{4}(x − sin x) + 0.0025, g′(x) = \frac{3}{4}(1 − cos(x))

Therefore

0 < \frac{3}{4} (1 − cos(\frac{1}{2})) ≤ g′(x) ≤ \frac{3}{4} on [−\frac{1}{2}, \frac{1}{2}].

It follows that g is an increasing function on [−\frac{1}{2}, \frac{1}{2}],

−\frac{1}{2} < −0.012931... = g(−\frac{1}{2}) ≤ g(x) ≤ g(\frac{1}{2}) = 0.017931... < \frac{1}{2}

(thus g([−\frac{1}{2}, \frac{1}{2}]) ⊂ [−\frac{1}{2}, \frac{1}{2}] (3 pts) ) and

|g′(x)| = |\frac{3}{4}(1 − cos(x))| ≤ \frac{3}{4} = k < 1 ∀ x ∈ (−\frac{1}{2}, \frac{1}{2}) (3 pts)