1. Gauss Elimination Method

\((1\times 1)\) \(ax_1=b\) \(\rightarrow\) \(x_1=\frac{b}{a}\)
\((2 \times 2)\) \(\begin{cases}a_{11}x_1+a_{12}x_2=b_1 \\ a_{21}x_1+a_{22}x_2=b_2\end{cases}\)

Ex1:
\[ \begin{cases}x_1+2x_2=5 \\ 3x_1+4x_2=6\end{cases} \rightarrow x_1=-4,x_2=4.5\]

\((n \times n)\)
\[ \begin{cases}a_{11}x_1+a_{12}x_2+\cdots+a_{1n}x_n=b_1 \\ a_{21}x_1+a_{22}x_2+\cdots+a_{2n}x_n=b_2\\ \vdots\\ a_{n1}x_1+a_{n2}x_2+\cdots+a_{nn}x_n=b_n\\ \end{cases}\]

Matix
\[A=\begin{bmatrix} a_{11} & a_{12} & \cdots & a_{1n}\\ a_{21} & a_{22} & \cdots & a_{2n}\\ \vdots\\ a_{11} & a_{12} & \cdots & a_{nn} \end{bmatrix}, x=\begin{bmatrix}x_1 \cdots x_n\end{bmatrix}, b=\begin{bmatrix}b_1 \cdots b_n\end{bmatrix}, Ax=b\]

Matrix form extracts the must essential information .

Matrix form of Ex1:
\[\begin{bmatrix}1 & 2 \\3 & 4\end{bmatrix} \begin{bmatrix}x_1 \\ x_2 \end{bmatrix}=\begin{bmatrix}5\\6\end{bmatrix}\]

Augment matrix
\[\begin{bmatrix}1 & 2 & 5 \\3 & 4 & 6\end{bmatrix} \rightarrow \begin{bmatrix}1 & 2 & 5 \\0 & -2 & -9\end{bmatrix} \rightarrow \begin{bmatrix}1 & 2 & 5 \\0 & 1 & 4.5\end{bmatrix} \rightarrow \begin{bmatrix}1 & 0 & -4 \\0 & 1 & 4.5\end{bmatrix} \]

Systematic method of Solving for Ex1:
\[ \begin{cases}x_1+2x_2=5 \\ 3x_1+4x_2=6\end{cases} \rightarrow \begin{cases}x_1+2x_2=5 \\ 0-2x_2=-9\end{cases} \rightarrow \begin{cases}x_1+2x_2=5 \\ x_2=4.5\end{cases}\]

Know as Gauss elimination Method：

• write as in matrix form
• Use row operations: multiply all elements in a row by the s number, subtract (add) row from another row (These operations do not change the solution)
• Apply row-by-row to bring the matrix to a form which is easy to solve

Matlab: To solve \(Ax=b\), using \(x=A\backslash b\)

>> A = [1 2;3 4]

A =

     1     2
     3     4

>> b = [5 6]'

b =

     5
     6

>> x = A\b

x =

   -4.0000
    4.5000

>> format long
>> x = A\b

x =

  -3.999999999999999
   4.499999999999999

2. Direct Methods and Iterative Methods

Bring to an easily solved form:

• Diagonal: \(\begin{bmatrix}1 & & 0\\ & \ddots & \\0 & & 1 \end{bmatrix}\)
• Upper triangular: \(\begin{bmatrix} a_{11} & a_{12} & \cdots & a_{1n}\\ & & a_{22} & \cdots & a_{2n}\\ \vdots\\ & & & \cdots & a_{nn}\\ \end{bmatrix}\)
• Lower triangular :

For upper triangular (back substitution):

\[a_{nn}x_n=b_n \rightarrow x_n = \frac{b_n}{a_{nn}}\] \[a_{n-1,n-1}x_{n-1}+ a_{n-1,n}x_n=b_{n-1}\] repeat... \[x_i=\frac{b_i-\sum^n_{j=i+1}a_{ij}x_j}{a_{ii}}\]

For lower triangular (forward substitution):

\[a_{11}x_1=b_1 \rightarrow x_1 = \frac{b_1}{a_{11}}\] \[a_{2,1}x_{1}+ a_{2,2}x_2=b_{2}\] repeat... \[x_i=\frac{b_i-\sum^{i-1}_{j=1}a_{ij}x_j}{a_{ii}}\]

General Methods:

• Gauss Elimination
• Pivoting
• Gauss-Jordan
• LU-factorization

Starting from 1st, a suitable multiple of the current row (pivot row) is subtracted form all subsequent rows, the result is an upper triangular

Ex2: \[\begin{cases}2x_1+x_2-x_3=1\\x_1+2x_2+x_3=8\\-x_1+x_2-x_3=-5\end{cases}\]

matrix:
\[\begin{bmatrix}2 & 1 & -1 & 1\\ 1 &2 & 1 & 8\\ -1 & 1 & -1 & -5 \end{bmatrix} \rightarrow \begin{bmatrix}2 & 1 & -1 & 1\\ 0 &1.5 & 1.5 & 7.5\\ 0 & 1.5 & -1.5 & -4.5 \end{bmatrix}\]

\[\rightarrow \begin{bmatrix}2 & 1 & -1 & 1\\ 0 &1.5 & 1.5 & 7.5\\ 0 & 0 & -3 & -12\end{bmatrix} \rightarrow \begin{cases}-3x_2 = -12\\x_3=4\end{cases} \rightarrow \begin{cases}x_1 =2 \\x_2=1\\x_3=4\end{cases}\]

It is a problem if this element is zero. If a pivot is small number, this may lead to loss of accuracy.

Exchange rows when necessary:
\[\begin{bmatrix} 1 & 2 & 5\\ 3 & 4& 5 \end{bmatrix}, \] \[\begin{bmatrix} 0 & 2 & 5\\ 3 & 4& 5 \end{bmatrix}, \]

Pivoting is the procedure of rearranying rows to make sure Pivot is not zero and as large as possible in magnitude.

Ex3: \[ \begin{cases}0.0003x_1 + 12.34x_2=12.343 \\0.4321 x_1+x_2=5.321\end{cases}\] Using Gauss:

• \(\frac{0.4321}{0.0003}=1440\) (round-off error, since \(0.0003*1440 = 0.4320\))
• \[ \begin{cases}0.0003x_1 + 12.34x_2=12.343 \\ 0.0001 x_1+17770x_2=-17760\end{cases} \rightarrow x_2 = -\frac{17760}{17770}=0.9994\] \[ \rightarrow x_1 = \frac{12.343-12.34*0.9994}{0.0003}=33.33\]

3. Gauss-Jordan Method (Applicable for calculating inverses)

\[\begin{bmatrix}a_{11} & a_{12} & \cdots & a_{1n}& b_1\\ \vdots & & & \vdots\\ a_{n1} & a_{n2} & \cdots & a_{nn} & b_n\end{bmatrix}\]
normalized and pivot row by dividing by the
normalize by the pivot; subtract the pivot row to elimate all non-zero in the column.

Ex1. \[\begin{bmatrix}4 & 1 & 2 & 21\\ 2 & -2 & 2 & 8\\ 1 & -2 & 4 & 16\end{bmatrix} \rightarrow \begin{bmatrix}1 & -2 & 4 & 16\\ 2 & -2 & 2 & 8 \\4 & 1 & 2 & 21 \end{bmatrix} \rightarrow \begin{bmatrix}1 & -2 & 4 & 16\\ 0 & 2 & -6 & -24 \\0 & 9 & -14 & -43 \end{bmatrix}\] \[ \rightarrow \begin{bmatrix}1 & -2 & 4 & 16\\ 0 & 1 & -3 & -12 \\0 & 9 & -14 & -43 \end{bmatrix} \rightarrow \begin{bmatrix}1 & 0 & -2 & -8\\ 0 & 1 & -3 & -12 \\0 & 0 & 13 & 65 \end{bmatrix} \rightarrow \begin{bmatrix}1 & 0 & -2 & -8\\ 0 & 1 & -3 & -12 \\0 & 0 & 1 & 5 \end{bmatrix}\] \[ \rightarrow \begin{bmatrix}1 & 0 & 0 & 2\\ 0 & 1 & 0 & 3 \\0 & 0 & 1 & 5 \end{bmatrix}\]

Suitable for matrix inverse

\(AB=I\), \(A\begin{bmatrix}b_1 & b_2 & b_3 \end{bmatrix} \rightarrow \begin{bmatrix}a_{11} & a_{12} & a_{13} & 1 & 0 & 0\\ a_{21} & a_{22} & a_{23} & 0 & 1 & 0\\ a_{31} & a_{32} & a_{33} & 0 & 0 & 1\end{bmatrix} \rightarrow \begin{bmatrix}1 & 0 & 0 &c_{11} & c_{12} & c_{13} & \\ 0 & 1 & 0 & c_{21} & c_{22} & c_{23} &\\ 0 & 0 & 1& c_{31} & c_{32} & c_{33} \end{bmatrix}\)

4. LU-decomposition Method

\(A=LU\), where \(L\) means lower triangular, \(U\) means upper triangular.

If this is achieved, then, solve \(Ax=b\) is equivalent to solve \(LUx=b\)
Work in 2 steps: \(Ux=y,Ly=b\), solve \(Ly=b\) then \(Ux=y\).

Two approaches:

• Gauss Elimination;
• Crout's Method

1) Gauss Elimination:

\[\begin{bmatrix} a_{11} & a_{12} & \cdots & a_{1n}\\ a_{21} & a_{22} & \cdots & a_{2n}\\ \vdots\\ a_{11} & a_{12} & \cdots & a_{nn} \end{bmatrix}=\begin{bmatrix}1 & & & & \\ m_{21} & 1 & & & \\ m_{31} & m_{32} & 1 & &\end{bmatrix} \begin{bmatrix}a'_{11} & a'_{12} & \cdots & a'_{1n} \\ & a'_{22} & \cdots & a'_{2n}\end{bmatrix}\]

general formulation: \(m_{ij}=\frac{a'_{ij}}{a'_{jj}}\)

Ex4: \(\begin{bmatrix}1 & 2\\3 & 4\end{bmatrix}=\begin{bmatrix}1 & 0\\3 & 1\end{bmatrix}\begin{bmatrix}1 & 2\\0 & -2\end{bmatrix}\)

2) Crout's Method

\[\begin{bmatrix} a_{11} & a_{12} & \cdots & a_{1n}\\ a_{21} & a_{22} & \cdots & a_{2n}\\ \vdots\\ a_{n1} & a_{n2} & \cdots & a_{nn} \end{bmatrix}=\begin{bmatrix}L_{11} & & & & \\ L_{21} & L_{22} & & & \\ \vdots & \vdots & \ddots & \end{bmatrix} \begin{bmatrix}1 & U_{12} & U_{13} & \cdots & U_{1n} \\ & 1 & U_{23} & \cdots &U_{2n}\\ & & \ddots & & \vdots \\ & & & & 1\end{bmatrix} \]

Ex5:

\[\begin{bmatrix} a_{11} & a_{12} & a_{13}\\ a_{21} & a_{22} & a_{23}\\ a_{31} & a_{32} & a_{33} \end{bmatrix}=\begin{bmatrix} L_{11} & 0 & 0\\ L_{21} & L_{22} & 0\\ L_{31} & L_{32} & L_{33} \end{bmatrix}\begin{bmatrix} 1 & U_{12} & U_{13}\\ 0 &1 & U_{23}\\ 0 & 0 & 1 \end{bmatrix}=\begin{bmatrix} L_{11} & L_{11}U_{12} & L_{11}U_{13}\\ L_{21} & L_{21}U_{12}+L_{22} & L_{21}U_{13}+ L_{22}U_{23}\\ L_{31} & L_{31}U_{12}+L_{32} & L_{33}+ L_{31}U_{13}+ L_{32}U_{23} \end{bmatrix}\]