[Numerical Analysis] 8. Triangular Systems

 Numerical Methods

- Traiangular Systems

 

Triangular Systems

Lower triangular matrix $L$

 - Square matrix for which $L_{ij} = $ when $ i < j$

Linear System $Lx = r$

- Forward substitution

    - $x_i = \frac{1}{L_{ii}} (r_i - \sum_{k=1}^{i-1}L_{ik}x_k)$

 

Upper triangle

 - Square matrix for which $U_{ij} = 0$ when $ i > j$

Linear system $Ux = r$

 - Backward substitution

    - $x_i = \frac{1}{U_{ii}} ( r_i - \sum_{k=i+1}^n U_{ik}x_k)$

 

LU Decomposition

$LU = M$

$M_{ij} = \sum_{k=1}^i L_{ik} U_{kj} \text{if} i \leq j$

$M_{ij} = \sum_{k=1}^j L_{ik} U_{kj} \text{if} i \geq j$

 

- $Mx = r \to LUx = r$

    - Let $Ux = y$

    - Solve $Ly = r$

    - Solve $Ux = y$

 

Doolittle's Method

- $L_{ii} \equiv 1$, $i=1,2,\cdots,n$

- We can express $L$ and $U$ in one matrix

$$D = \begin{bmatrix}
U_{11} & U_{12} & \cdots & U_{1n} \\
L_{21} & U_{22} & \cdots & U_{2n} \\
\vdots & \vdots & \ddots & \vdots \\
L_{n1} & L_{n2} & \cdots & U_{nn} \\
\end{bmatrix}$$

 

- Solve $U$ and $L$ for each column $j$ from top to bottom

    - $U_{1j} = M_{1j}$

    - $U_{ij} = M_{ij} - \sim_{k=1}^{i-1}L_{ik}U_{kj}, \text{if} i > 1$.

    - $L_{i1} = \frac{M_{i1}}{U_{11}}$

    - $L_{ij} = \frac{1}{U_{jj}}( M_{ij} - \sum_{k=1}^{j-1} L_{ik} U_{kj}), \text{if} j >1$

 

Error Reduction

Suppose we solve a linear system $Mxr$

- if we obtained a solution $x=x_0$, $x_0$ usually slightly different from the true solution due to round-off error(computer)

- Thus $Mx_0 = r_0$

    - $M(x+\Delta x) = r+ \Delta r$, where $ \Delat x = x_0 -x$, $\Delta r = r_0 - r$

    - $M\Delta x = \Delta r$

    - Mx_0 = r_0 = r+ \Delta r = r + M \Delta x$

    - M \Delta x = M x_0 - r$

- solve for the error $\Delta x$ and improve the solution : $x = x_0 - \Delta x$

 

Matrix Inversion

Matrix inverse can be computed in a column-by-column method

- $MM^{-1} = I$

- $Mc_1 = I_1$, $Mc_2 = I_2$, $Mc_3 = I_3$ -> 3 linear system -> using LU decompotition to find solution