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

Homework Assignment for Week 10

Assigned Nov 18, 2011.

1. Section 6.6: Problems 3(a), 7(a). (These are paper and pencil assignments).

For problems 2 and 3, it may be helpful to review the LU decomposition summarized in page 43-45 of Chap 6’s slides (2011 version).

2. Find the numbers of multiplications/divisions (to leading order) needed for LDL^{T} and Choleski decompositions (both without pivoting), respectively.

3. Derive the recursive version of LDL^{T} decomposition (without pivoting).

4. Discretize the following system

\begin{matrix}u′′(x) − αu(x) = sin(πx), α > 0, x ∈ (0, 1) \\ u(0) = 0, u(1) = 0 \end{matrix}  (1)

with uniformly spaced grids 0 = x_{0} < x_{1} < ⋯ < x_{N} = 1, x_{i} − x_{i−1} = h = 1/N, using second order finite difference method. Let A be the corresponding matrix.

(a) Show that Gauss elimination for A is identical to Gauss elimination with (scaled) partial pivoting for A (i.e. the diagonal elements are exactly the pivot elements). (Hint: First apply Theorem 6.19.)

(b) Form the matrix A in matlab/octave. The built-in functions ’diag’, ’ones’ should be useful.

(c) Implement Algorithm 6.7 (LU decomposition for tridiagonal system, together with forward and backward substitutions) to solve for u_{j}. For future purposes, you should separate the LU-decomposition part and forward/backward substitution part as two separate subroutines. In many applications, you only need to LUdecompose once and solve for u(x_{j}) for many times. The exact solution to (1) is u_{e}(x) = − sin(πx)/(π^{2} + α). If you got all things done correctly, you should be able to see numerically that sup_{j} |u_{h}(x_{j}) − u_{e}(x_{j})| = O(h^{2}). You can also check your answer by the built-in command ’u = A\f’. However, keep in mind that it is much slower for this problem. Keep your code for next week’s homework assignment, which will need to be handed in.