Systems of Equations

The LU Factorization

解方程$Ax = b$,将$A$分解为$LU$,$LU$分别为lower triangular , upper triangular

$$\begin{align} Ax &= b \\ LUx &= b \\ \end{align}$$

然后解方程

$$\begin{align} Lc &= b \\ Ux &= c \end{align}$$

先计算出$c$然后计算$x$

LU 分解步骤

$$\begin{align} & A = \begin{bmatrix} 2 & 1 & 5 \\ 4 & 4 & -4 \\ 1 & 3 & 1 \end{bmatrix} ,P = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} ,L = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} \\\\ & \begin{bmatrix} 2 & 1 & 5 \\ 4 & 4 & -4 \\ 1 & 3 & 1 \end{bmatrix} \overset{\text{exchange rows 1 and 2}}{\longrightarrow} \begin{bmatrix} 4 & 4 & -4 \\ 2 & 1 & 5 \\ 1 & 3 & 1 \end{bmatrix} , \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} \overset{\text{exchange rows 1 and 2}}{\longrightarrow} \begin{bmatrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{bmatrix} ,\text{L have no change} \\\\ & \begin{bmatrix} 2 & 1 & 5 \\ 4 & 4 & -4 \\ 1 & 3 & 1 \end{bmatrix} \overset{subtract \frac{1}{2}\times \text{row 1 from row 2}}{\longrightarrow} \begin{bmatrix} 4 & 4 & -4 \\ 2 & 1 & 5 \\ 1 & 3 & 1 \end{bmatrix} , \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} \overset{\text{exchange rows 1 and 2}}{\longrightarrow} \begin{bmatrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{bmatrix} ,\text{L have no change} \end {align}$$

Iterative methods

Jacobi Method

D denote the main diagonal of A, L denote the lower triangle of A (entries below the main diagonal), and U denote the upper triangle (entries above the main diagonal)

$$\begin{align} Ax &= b \\ (D+L+U)x &= b\\ Dx &= b-(L+U)x \\ x &= D^{-1}(b-(L+U)x) \end{align}$$

Example:

$$\begin{align} & \begin{bmatrix} 1 & 1 \\ 3 & -4 \end{bmatrix} = LU = \begin{bmatrix} 1 & 0 \\ 3 & 1 \end{bmatrix} \begin{bmatrix} 1 & 1 \\ 0 & -7 \end{bmatrix} \\\\ & \begin{bmatrix} 1 & 0 \\ 3 & 1 \end{bmatrix} \begin{bmatrix} c_1 \\ c_2 \end{bmatrix} = \begin{bmatrix} 3 \\ 2 \end{bmatrix} \\\\ & c_1 = 3 , c_2 = -7 \\\\ & \begin{bmatrix} 1 & 1 \\ 0 & -7 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} = \begin{bmatrix} 3 \\ -7 \end{bmatrix} \\\\ & x_1 = 2 , x_2 = 1 \end{align}$$

Methods for symmetric positive-definite matrices

$n\times n$ matrix $A$ is symmetric if $A^T = A$.The matrix A is positive-definite if $x^TAx>0$ for all vectors $x\ne 0$