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

Brief Answers to Quiz 06

1:20-2:10PM, Jan 08, 2021.

1. Perform the elimination part of the Gaussian elimination with scaled partial pivoting for the following linear system:

\begin{aligned}x_{1} & − & 5x_{2} & + & x_{3} & = & 7 \\ 10x_{1} & & & + & 20x_{3} & = & 6 \\ 5x_{1} & & & − & x_{3} & = & 4 \end{aligned} ,  (1)

Give all details and the final linear system corresponding to an upper triangular matrix. Need not solve it. Answer:

s_{1} = 5, s_{2} = 20, s_{3} = 5.

Scaled linear system

\begin{aligned}0.2x_{1} & − & x_{2} & + & 0.2x_{3} & = & 1.4 \\ 0.5x_{1} & & & + & x_{3} & = & 0.3 \\ x_{1} & & & − & 0.2x_{3} & = & 0.8 \end{aligned} ,  (2)

Start with row 1 and row 3 exchange:

[ \begin{matrix}1 & −5 & 1 & | & 7 \\ 10 & 0 & 20 & | & 6 \\ 5 & 0 & −1 & | & 4 \end{matrix} ] ⟶^{E_{1}↔E_{3}} [ \begin{matrix}5 & 0 & −1 & | & 4 \\ 10 & 0 & 20 & | & 6 \\ 1 & −5 & 1 & | & 7 \end{matrix} ] (10 pts)

⟶^{E_{2}←E_{2}−2E_{1}} [ \begin{matrix}5 & 0 & −1 & | & 4 \\ 0 & 0 & 22 & | & −2 \\ 1 & −5 & 1 & | & 7 \end{matrix} ] (6 pts) ⟶^{E_{3}←E_{3}− \frac{1}{5} E_{1}} [ \begin{matrix}5 & 0 & −1 & | & 4 \\ 0 & 0 & 22 & | & −2 \\ 0 & −5 & 1.2 & | & 6.2 \end{matrix} ] (6 pts)

⟶^{E_{2}↔E_{3}} [ \begin{matrix}5 & 0 & −1 & | & 4 \\ 0 & −5 & 1.2 & | & 6.2 \\ 0 & 0 & 22 & | & −2 \end{matrix} ] (3 pts)

2. Find P, L, U in the factorization P A = LU for the matrix

A = ( \begin{matrix}0 & 0 & −1 & 1 \\ 1 & 1 & −1 & 2 \\ −1 & −1 & 2 & 0 \\ 1 & 2 & 0 & 2 \end{matrix} )  (3)

where P is the permutation matrix corresponding to partial pivoting.

Answer:

P_{1} = ( \begin{matrix}0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{matrix} ) , P_{1}A = ( \begin{matrix}1 & 1 & −1 & 2 \\ 0 & 0 & −1 & 1 \\ −1 & −1 & 2 & 0 \\ 1 & 2 & 0 & 2 \end{matrix} ) (5 pts)

L_{1} = ( \begin{matrix}1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 \\ −1 & 0 & 0 & 1 \end{matrix} ) , L_{1}P_{1}A = ( \begin{matrix}1 & 1 & −1 & 2 \\ 0 & 0 & −1 & 1 \\ 0 & 0 & 1 & 2 \\ 0 & 1 & 1 & 0 \end{matrix} ) (5 pts)

P_{2} = ( \begin{matrix}1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \end{matrix} ) , P_{2}L_{1}P_{1}A = ( \begin{matrix}1 & 1 & −1 & 2 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 2 \\ 0 & 0 & −1 & 1 \end{matrix} ) (2 pts)

L_{2} = ( \begin{matrix}1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 1 \end{matrix} ) , L_{2}P_{2}L_{1}P_{1}A = ( \begin{matrix}1 & 1 & −1 & 2 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 2 \\ 0 & 0 & 0 & 3 \end{matrix} ) (3 pts)

U = ( \begin{matrix}−1 & −1 & 2 & 0 \\ 0 & 1 & 2 & 2 \\ 0 & 0 & 1 & 2 \\ 0 & 0 & 0 & 3 \end{matrix} ) , P = P_{2}P_{1} = ( \begin{matrix}0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 \end{matrix} ) (3 pts)

L = P_{2}(L_{1})^{−1}(P_{2})^{−1}(L_{2})^{−1} = ( \begin{matrix}1 & 0 & 0 & 0 \\ −1 & 1 & 0 & 0 \\ −1 & 0 & 1 & 0 \\ 0 & 0 & −1 & 1 \end{matrix} ) (7 pts)

3. Derive a 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.

Answer:

Equation at x_{1}: \frac{0 − (2 + h^{2})u_{1} + u_{2}}{h^{2}} = f_{1},

Equation at x_{2}: \frac{u_{1} − (2 + h^{2})u_{2} + u_{3}}{h^{2}} = f_{2},

Equation at x_{i}: \frac{u_{i−1} − (2 + h^{2})u_{i} + u_{i+1}}{h^{2}} = f_{i},

⋯,

Equation at x_{N−1}: \frac{u_{N−2} − (2 + h^{2})u_{N−1} + 0}{h^{2}} = f_{N−1}. (25 pts)

4. Find the Choleski decomposition for the matrix

A = ( \begin{matrix}4 & −1 & 0 \\ −1 & 4 & −1 \\ 0 & −1 & 4 \end{matrix} )  (4)

Give full details of your derivation. Answer: Suppose A = GG^{T}. Since A is banded, so is G. Let

G = ( \begin{matrix}g_{11} & 0 & 0 \\ g_{21} & g_{22} & 0 \\ 0 & g_{32} & g_{33} \end{matrix} ) , G^{T} = ( \begin{matrix}g_{11} & g_{21} & 0 \\ 0 & g_{22} & g_{32} \\ 0 & 0 & g_{33} \end{matrix} )  (5)

Equate the 11 entry: g_{11} = 2. Equate the 21 entry: g_{21} = \frac{−1}{2}. Equate the 22 entry: g_{22} = \frac{\sqrt{15}}{2}. Equate the 32 entry: g_{32} = \frac{−2}{\sqrt{15}}. Equate the 33 entry: g_{33} = \begin{matrix}√ & \overline{56} \\ √ & \overline{15} \end{matrix}. (5 pts for each, total 25pts)