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

Homework Assignment for Week 14

Assigned Dec 16, 2011.

1. Section 7.4: Construct the Hilbert matrix H^{(n)} in problem 11 and compute the condition number κ(H^{(n)}) for n = 5, 10, 20, 30, ⋯, respectively. You can use the matlab/octave built-in function ’cond’. This is a well-known example of ill-conditioned matrix that corresponds to the continuous least square approximation.

2. Do the same for discrete least square approximation. First derive the equation by trying to find p(x) ∈ P_{n} that minimizes ∑_{j=0}^{m}(p(x_{j}) − f(x_{j}))^{2} with m > n, x_{j} = \frac{j}{m} and f(x_{j}) given.

If time permits, try to find the condition numbers of the corresponding A^{T} A with m = n + 1 and/or m = 2n (in the continuous case, A^{T} A corresponds to H^{(n+1)} with m = ∞ in some sense).

3. Section 2.2: Problems 2(b), 7, 12, 24.

4. The iteration x_{n+1} = g(x_{n}) almost for sure does not converge when |g′| > 1 near the solution x_{∗}. An easy remedy is to give a rough estimate on g′(x_{∗}), then perform the iteration

x_{n+1} = αx_{n} + (1 − α)g(x_{n}).

Show that this iteration, if convergent, gives a root to x = g(x). The advantage of the new iteration is that, you can choose an α according to the approximate value of g′(x_{∗}), so that the new iteration converges. Apply this trick to the equation x = g(x) = 1 − 2x + 0.2 sin x.