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

Quiz 03

Nov 11, 2011.

1. Derive a linear system of equation corresponding to the following boundary value problem

\begin{matrix}u′′(x) − u(x) = f(x), x ∈ (0, 1) \\ u(0) = 0, u(1) = 0 \end{matrix}

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. That is, given f_{i}, i = 1, 2, ⋯, N − 1, try to derive a linear system of equations to solve for u_{i}, i = 1, 2, ⋯, N − 1.

Estimate total number of multiplications/divisions needed for Gaussian elimination without pivoting (counting elimination AND backward substitution together). Give the leading order of the number of multiplications/divisions as CN^{p}. Find C and p.

2. Consider an M^{3} × M^{3} matrix B with b_{ij} = 0 except for i − j = 0, ±1, ±M (only five separated diagonals have nonzero entries). Estimate total number of multiplications needed for Gaussian elimination without pivoting (counting elimination only, NO backward substitution). Give the leading order of the number of multiplications/divisions as KM^{q}. Find K and q.

3. Let A = ( \begin{matrix}−1 & 2 & 2 & 0 \\ 2 & 2 & 0 & 0 \\ 2 & −1 & 1 & 4 \\ −2 & 4 & 1 & 5 \end{matrix} ) . Perform Gaussian elimination, Gaussian elimination

with partial pivoting and Gaussian elimination with scaled partial pivoting on A, respectively (need not do the backward substitution part). Write down your intermediate steps clearly for next problem.

4. In each of the case above, identify the corresponding factorizations as A = LU or P A = LU, respectively. Note that L is a unit-diagonal lower triangular, U is an upper triangular and P a permutation matrix. You must identify each matrix as products of the matrices corresponding to intermediate steps you used in previous problem. Product of several matrices must be be performed one at a time. Write slowly and clearly for yourself. Don’t skip the details. You can check your answer with octave. So if you only give your answers without intermediate processes, you will get no points.

All entries are integers or simple rationals. Some octave built-in functions may be helpful for some factorizations. If not, you can still check by keying your L, U, P, etc. and check if the product is correct.