Numerical Linear Algebra(Numerical Method)

PLU Decomposition

$$A=\begin{bmatrix}2 & 10 & 8 \\ 14 & 2 & 24\\ -19 & 7 & 24\\\end{bmatrix}$$

Find the PLU factorisation of the matrix above.

Solution:

1) Check for the dominant value in the first column
$\begin{bmatrix}1 & 0 & 0 \\ 0 & 1 & 0\\ 0 & 0 & 1\\\end{bmatrix}A = \begin{bmatrix}\color{yellow}{2} & 10 & 8\\ \color{yellow}{14} & 2 & 24\\ \color{yellow}{-19} & 7 & 24\\\end{bmatrix}$

*Compare the absolute value of the first column numbers and find the dominant (largest) value $\Rightarrow|2| = 2, |14| = 14, |-19| = 19$, therefore, $-19$ have the dominant value

2) Change the row that have the dominant value to the  first row (Remember to change the row of the identity matrix) *if necessary

$\begin{bmatrix}0 & 0 & 1 \\ 0 & 1 & 0\\ 1 & 0 & 0\\\end{bmatrix}A = \begin{bmatrix}-19 & 7 & 24\\ 14 & 2 & 24\\ 2 & 10 & 8\\\end{bmatrix}$

3) Make first column below the first row all become $0$

$$R_1(\color{fuchsia}{\frac{14}{19}})+R_2 \to R_2$$

$$R_1(\color{fuchsia}{\frac{2}{19}})+R_3 \to R_3$$

$\begin{bmatrix}0 & 0 & 1 \\ 0 & 1 & 0\\ 1 & 0 & 0\\\end{bmatrix}A =\begin{bmatrix}1 & 0 & 0\\ \color{fuchsia}{-\frac{14}{19}} & 1 & 0\\ \color{fuchsia}{-\frac{2}{19}} & 0 & 1\end{bmatrix} \begin{bmatrix}-19 & 7 & 24\\ 0 & \frac{136}{19} & \frac{792}{19}\\ 0 & \frac{204}{19} & \frac{200}{19}\\\end{bmatrix}$

4) Check for the dominant value in the second column below the first row
$\begin{bmatrix}0 & 0 & 1 \\ 0 & 1 & 0\\ 1 & 0 & 0\\\end{bmatrix}A =\begin{bmatrix}1 & 0 & 0\\ -\frac{14}{19} & 1 & 0\\ -\frac{2}{19} & 0 & 1\end{bmatrix} \begin{bmatrix}-19 & 7 & 24\\ 0 & \color{yellow}{\frac{136}{19}} & \frac{792}{19}\\ 0 & \color{yellow}{\frac{204}{19}} & \frac{200}{19}\\\end{bmatrix}$

*Compare the absolute value of the first column numbers and find the dominant (largest) value $\Rightarrow|\frac{136}{19}| = 7.15789473684, |\frac{204}{19}| = 10.7368421053$, therefore, $\frac{204}{19}$ have the dominant value

5) Change the row that have the dominant value to the  second row (Remember to change the row of the identity matrix) *if necessary
$\begin{bmatrix}0 & 0 & 1 \\ 1 & 0 & 0\\ 0 & 1 & 0\\\end{bmatrix}A =\begin{bmatrix}1 & 0 & 0\\ -\frac{14}{19} & 1 & 0\\ -\frac{2}{19} & 0 & 1\\\end{bmatrix} \begin{bmatrix}-19 & 7 & 24\\ 0 & \frac{204}{19} & \frac{200}{19}\\ 0 & \frac{136}{19} & \frac{792}{19}\\\end{bmatrix}$

6) Make the second column below the second row all become $0$
$$R_2 (\color{fuchsia}{-\frac{2}{3}}) + R_3 \to R_3$$

$\begin{bmatrix}0 & 0 & 1 \\ 1 & 0 & 0\\ 0 & 1 & 0\\\end{bmatrix}A =\begin{bmatrix}1 & 0 & 0\\ -\frac{14}{19} & 1 & 0\\ -\frac{2}{19} & \color{fuchsia}{\frac{2}{3}} & 1\\\end{bmatrix} \begin{bmatrix}-19 & 7 & 24\\ 0 & \frac{204}{19} & \frac{200}{19}\\ 0 & 0 & \frac{104}{3}\\\end{bmatrix}$

7) If both of the matrix in right hand side become upper triangular and lower triangular matrix, then find the inverse of the left hand side matrix and multiply with the right hand side matrix

$PLU =\begin{bmatrix}0 & 0 & 1\\ 1 & 0 & 0\\ 0 & 1  & 0\\\end{bmatrix}^{-1}\begin{bmatrix}1 & 0 & 0\\ -\frac{14}{19} & 1 & 0\\ -\frac{2}{19} & \frac{2}{3} & 1\\\end{bmatrix} \begin{bmatrix}-19 & 7 & 24\\ 0 & \frac{204}{19} & \frac{200}{19}\\ 0 & 0 & \frac{104}{3}\\\end{bmatrix}$

8) The final answer
$$PLU =\begin{bmatrix}0 & 1 & 0\\ 0 & 0 & 1\\ 1 & 0  & 0\\\end{bmatrix}\begin{bmatrix}1 & 0 & 0\\ -\frac{14}{19} & 1 & 0\\ -\frac{2}{19} & \frac{2}{3} & 1\\\end{bmatrix} \begin{bmatrix}-19 & 7 & 24\\ 0 & \frac{204}{19} & \frac{200}{19}\\ 0 & 0 & \frac{104}{3}\\\end{bmatrix}$$

---

QR Decomposition

$$A=\begin{bmatrix}1 & -1 & 4 \\ 1 & 4 & -2\\ 1 & 4 & 2\\ 1 & -1 & 0\\\end{bmatrix}$$

Compute the QR decomposition of A

Solution:

let $a_1 = \begin{bmatrix}1\\1\\1\\1\\\end{bmatrix},a_2=\begin{bmatrix}-1\\4\\4\\-1\\\end{bmatrix},a_3=\begin{bmatrix}4\\-2\\2\\0\\\end{bmatrix}$
$$f_1 = a_1 = \begin{bmatrix}1\\1\\1\\1\\\end{bmatrix}$$

$f_2 = a_2 - (\frac{f_1 \cdot a_2}{f_1 \cdot f_1})f_1$

$$f_2 = \begin{bmatrix}-1 \\ 4 \\ 4 \\ -1\\\end{bmatrix}-\frac{6}{2}\begin{bmatrix}1\\1\\1\\1\\\end{bmatrix} = \begin{bmatrix}-\frac{5}{2}\\ \frac{5}{2}\\ \frac{5}{2}\\ -\frac{5}{2}\end{bmatrix}$$

$f_3 = a_3 - (\frac{f_1 \cdot a_3}{f_1 \cdot f_1})f_1-(\frac{f_2 \cdot a_3}{f_2 \cdot f_2})f_2$
$$f_3 = \begin{bmatrix}4 \\ -2 \\ 2 \\ 0\\\end{bmatrix}-\frac{4}{4}\begin{bmatrix}1\\1\\1\\1\\\end{bmatrix}-(\frac{-10}{25})\begin{bmatrix}-\frac{5}{2}\\ \frac{5}{2}\\ \frac{5}{2}\\ -\frac{5}{2}\end{bmatrix} = \begin{bmatrix}2\\-2\\2\\-2\\\end{bmatrix}$$

Hence, $Q=\begin{bmatrix}\frac{f_1}{\lVert f_1\rVert},\frac{f_2}{\lVert f_2\rVert},\frac{f_3}{\lVert f_3\rVert}\end{bmatrix}$
$$Q=\begin{bmatrix}\frac{1}{2} & -\frac{1}{2} & \frac{1}{2} \\ \frac{1}{2} & \frac{1}{2} & -\frac{1}{2}\\ \frac{1}{2} & \frac{1}{2} & \frac{1}{2}\\ \frac{1}{2} & -\frac{1}{2} & -\frac{1}{2}\\\end{bmatrix}$$

Then, $R=Q^T A$

$$R=\begin{bmatrix}\frac{1}{2} & \frac{1}{2} & \frac{1}{2} &\frac{1}{2} \\ -\frac{1}{2} & \frac{1}{2} & \frac{1}{2} &-\frac{1}{2}\\ \frac{1}{2} & -\frac{1}{2} & \frac{1}{2} &-\frac{1}{2}\\\end{bmatrix}\begin{bmatrix}1 & -1 & 4\\ 1 & 4 & -2\\ 1 & 4 & 2\\ 1 & -1 & 0\\\end{bmatrix} = \begin{bmatrix}2 & 3 & 2\\ 0 & 5 & -2\\ 0 & 0 & 4\end{bmatrix}$$

The final answer will be

$$QR=\begin{bmatrix}\frac{1}{2} & -\frac{1}{2} & \frac{1}{2} \\ \frac{1}{2} & \frac{1}{2} & -\frac{1}{2}\\ \frac{1}{2} & \frac{1}{2} & \frac{1}{2}\\ \frac{1}{2} & -\frac{1}{2} & -\frac{1}{2}\\\end{bmatrix}\begin{bmatrix}2 & 3 & 2\\ 0 & 5 & -2\\ 0 & 0 & 4\\\end{bmatrix}$$

---

Strictly Diagonally Dominant

$$\begin{matrix}x_1-10x_2+x_3=13\\20x_1+x_2-x_3=17\\-x_1+x_2+10x_3=18\end{matrix}$$

can be written as:

  $$A=\begin{bmatrix}20 & 1 & -1\\1 & -10 & 1\\ -1 & 1 & 10\\\end{bmatrix}$$

$\Rightarrow$ A n $\times$ n matrix is called strictly diagonally dominant if $|a_{ii}|>\sum_{j=1,j\neq i}^n |a_{ij}|$

Means:

$$\begin{matrix}|a_{11}| > |a_{12}| + |a_{13}|\\|a_{22}|>|a_{21}| + |a_{23}|\\ |a_{33}| > |a_{31}| +|a_{32}| \end{matrix}$$


So, A is strictly diagonally dominant matrix, because:

$$\begin{matrix}|20| > |1| + |-1|\\|-10|>|1| + |1|\\ |10| > |-1| +|1| \end{matrix}$$

---

Jacobi Method

$$\begin{cases}10x_1+5x_2 &=6\\5x_1+10x_2-4x_3 &=25\\-4x_2+8x_3-x_4 &=-11\\-x_3+5x_4 &=-11\\\end{cases}$$

By using $x^{(0)}=0$, find the first two iterations of the Jacobi method for the linear system above.

Solution:

$$\begin{bmatrix}10  & 5 & 0 & 0\\5  & 10 & -4 & 0\\0 & -4 & 8 & -1 \\0 & 0 & -1 & 5\\\end{bmatrix}\begin{bmatrix}x_1\\ x_2\\x_3\\x_4\\\end{bmatrix} = \begin{bmatrix}6\\25\\-11\\-11\end{bmatrix}$$

*Check whether the matrix is strictly diagonally dominant

$$\begin{matrix}|10| > |5|+|0|+|0| \\|10|>|5| + |-4|+|0|\\ |8| >|0|+ |-4| +|-1|\\|5|>|0|+|0|+|-1|\\ \end{matrix}$$
$\Rightarrow$ The matrix is strictly diagonally dominant

Deriving the Jacobi iteration:

$$\begin{bmatrix}x_1^{(k+1)}\\x_2^{(k+1)}\\x_3^{(k+1)}\\x_4^{(k+1)}\\\end{bmatrix}=\begin{bmatrix}\frac{1}{10}(6-5x_2^{(k)})\\\frac{1}{10}(25-5x_1^{(k)}+4x_3^{(k)})\\\frac{1}{8}(-11+4x_2^{(k)}+x_4^{(k)})\\\frac{1}{5}(-11+x_3^{(k)})\end{bmatrix},k=0,1,2,3,...$$

when k=0,

$$\begin{bmatrix}x_1^{(1)}\\x_2^{(1)}\\x_3^{(1)}\\x_4^{(1)}\\\end{bmatrix}=\begin{bmatrix}\frac{1}{10}(6-5x_2^{(0)})\\\frac{1}{10}(25-5x_1^{(0)}+4x_3^{(0)})\\\frac{1}{8}(-11+4x_2^{(0)}+x_4^{(0)})\\\frac{1}{5}(-11+x_3^{(0)})\end{bmatrix},\text{Given that } \vec{x}^{(0)}=0$$

$$\begin{bmatrix}x_1^{(1)}\\x_2^{(1)}\\x_3^{(1)}\\x_4^{(1)}\\\end{bmatrix}=\begin{bmatrix}\frac{6}{10}\\\frac{25}{10}\\-\frac{11}{8}\\-\frac{11}{5}\\\end{bmatrix}$$

when k=1,

$$\begin{bmatrix}x_1^{(2)}\\x_2^{(2)}\\x_3^{(2)}\\x_4^{(2)}\\\end{bmatrix}=\begin{bmatrix}\frac{1}{10}(6-5x_2^{(1)})\\\frac{1}{10}(25-5x_1^{(1)}+4x_3^{(1)})\\\frac{1}{8}(-11+4x_2^{(1)}+x_4^{(1)})\\\frac{1}{5}(-11+x_3^{(1)})\end{bmatrix}$$

$$\begin{bmatrix}x_1^{(2)}\\x_2^{(2)}\\x_3^{(2)}\\x_4^{(2)}\\\end{bmatrix}=\begin{bmatrix}-\frac{13}{20}\\\frac{33}{20}\\-\frac{2}{5}\\-\frac{99}{40}\\\end{bmatrix}$$

---

Gauss-Seidel Method

$$\begin{cases}10x_1+5x_2 &=6\\5x_1+10x_2-4x_3 &=25\\-4x_2+8x_3-x_4 &=-11\\-x_3+5x_4 &=-11\\\end{cases}$$  

By using $x^{(0)}=0$, find the first two iterations of the Gauss-Seidel method for the linear system above.

Deriving the Gauss-Seidel iteration:

$$\begin{bmatrix}x_1^{(k+1)}\\x_2^{(k+1)}\\x_3^{(k+1)}\\x_4^{(k+1)}\\\end{bmatrix}=\begin{bmatrix}\frac{1}{10}(6-5x_2^{(k)})\\\frac{1}{10}(25-5x_1^{(k+1)}+4x_3^{(k)})\\\frac{1}{8}(-11+4x_2^{(k+1)}+x_4^{(k)})\\\frac{1}{5}(-11+x_3^{(k+1)})\end{bmatrix},k=0,1,2,3,...$$

when k=0,

$$\begin{bmatrix}x_1^{(1)}\\x_2^{(1)}\\x_3^{(1)}\\x_4^{(1)}\\\end{bmatrix}=\begin{bmatrix}\frac{1}{10}(6-5x_2^{(0)})\\\frac{1}{10}(25-5x_1^{(1)}+4x_3^{(0)})\\\frac{1}{8}(-11+4x_2^{(1)}+x_4^{(0)})\\\frac{1}{5}(-11+x_3^{(1)})\end{bmatrix},\text{Given that } \vec{x}^{(0)}=0$$

$$\begin{matrix}x_1^{(1)}&=\frac{1}{10}(6-5(0))&=\color{fuchsia}{0.6}\\x_2^{(1)}&=\frac{1}{10}(25-5(\color{fuchsia}{0.6})+4(0))&=\color{yellow}{2.2}\\x_3^{(1)}&=\frac{1}{8}(-11+4(\color{yellow}{2.2})+0)&=\color{orange}{-0.275}\\x_4^{(1)}&=\frac{1}{5}(-11+(\color{orange}{-0.275}))&=-2.255\end{matrix}$$

when k=1,

$$\begin{bmatrix}x_1^{(2)}\\x_2^{(2)}\\x_3^{(2)}\\x_4^{(2)}\\\end{bmatrix}=\begin{bmatrix}\frac{1}{10}(6-5x_2^{(1)})\\\frac{1}{10}(25-5x_1^{(2)}+4x_3^{(1)})\\\frac{1}{8}(-11+4x_2^{(2)}+x_4^{(1)})\\\frac{1}{5}(-11+x_3^{(2)})\end{bmatrix}$$

$$\begin{matrix}x_1^{(2)}&=\frac{1}{10}(6-5(2.2))&=\color{fuchsia}{-0.5}\\x_2^{(2)}&=\frac{1}{10}(25-5(\color{fuchsia}{-0.5})+4(-0.275))&=\color{yellow}{2.64}\\x_3^{(2)}&=\frac{1}{8}(-11+4(\color{yellow}{2.64})+(-2.255))&=\color{orange}{-0.336875}\\x_4^{(2)}&=\frac{1}{5}(-11+(\color{orange}{-0.336875}))&=-2.267375\end{matrix}$$

---

Power Method

$$A=\begin{bmatrix}4 & -2\\3 & -1\\\end{bmatrix}$$

Use power method to approximate the dominant eigenvalue and corresponding eigenvector with 3 iteration.

Note: If didn't stating $x_0$, we will always take $x_0=\begin{bmatrix}1\\0\\\end{bmatrix}$

Solution:

Given that $\vec{x}_0=\begin{bmatrix}1\\0\\\end{bmatrix}$,

Iteration 1:

When k = 1,

a) Find $\vec{y}_1 = A\vec{x}_0$

$$\vec{y}_1 = \begin{bmatrix}4 & -2\\3 & -1\\\end{bmatrix}\begin{bmatrix}1\\0\\\end{bmatrix}=\begin{bmatrix}4 \\3\\\end{bmatrix}$$

b) let $m_1=$ dominant value in $\vec{y}_1=|4|=4$

c) Find the corresponding eigenvector using $\vec{x}_1=\frac{1}{m_1}\vec{y}_1$

$$\vec{x}_1=\frac{1}{4}\begin{bmatrix}4\\3\\\end{bmatrix}=\begin{bmatrix}1\\0.75\\\end{bmatrix}$$

Iteration 2:

When k = 2,

a) Find $\vec{y}_2 = A\vec{x}_1$

$$\vec{y}_2 = \begin{bmatrix}4 & -2\\3 & -1\\\end{bmatrix}\begin{bmatrix}1\\0.75\\\end{bmatrix}=\begin{bmatrix}2.5 \\2.25\\\end{bmatrix}$$

b) let $m_2=$ dominant value in $\vec{y}_1=|2.5|=2.5$

c) Find the corresponding eigenvector using $\vec{x}_2=\frac{1}{m_2}\vec{y}_2$

$$\vec{x}_2=\frac{1}{2.5}\begin{bmatrix}2.5\\2.25\\\end{bmatrix}=\begin{bmatrix}1\\0.9\\\end{bmatrix}$$

Iteration 2:

When k = 2,

a) Find $\vec{y}_3 = A\vec{x}_2$

$$\vec{y}_3 = \begin{bmatrix}4 & -2\\3 & -1\\\end{bmatrix}\begin{bmatrix}1\\0.9\\\end{bmatrix}=\begin{bmatrix}2.2 \\2.1\\\end{bmatrix}$$

b) let $m_3=$ dominant value in $\vec{y}_2=|2.2|=2.2$

c) Find the corresponding eigenvector using $\vec{x}_3=\frac{1}{m_3}\vec{y}_3$

$$\vec{x}_3=\frac{1}{2.2}\begin{bmatrix}2.2\\2.1\\\end{bmatrix}=\begin{bmatrix}1\\0.954545\\\end{bmatrix}$$