LU分解求解线性方程组
L U LU LU分解
前言
L U LU LU分解 由以下定理得以保证：
设 A \boldsymbol{A} A为 n n n阶方阵，若其各界阶顺序主子式都不为 0 0 0，那么它可以
被唯一的上下三角矩阵积分解。
步骤
确定各矩阵形式 A = L U \mathbf{A}=\mathbf{LU} A=LU
( a 11 a 12 ⋯ a 1 n a 21 a 22 ⋯ a 2 n ⋮ ⋮ ⋱ ⋮ a n 1 a n 2 ⋯ a n n ) = ( 1 0 ⋯ 0 l 21 1 ⋯ 0 ⋮ ⋮ ⋱ ⋮ l n 1 l n 2 ⋯ 1 ) ( u 11 u 12 ⋯ u 1 n 0 u 22 ⋯ u 2 n ⋮ ⋮ ⋱ ⋮ 0 0 ⋯ u n n ) \begin{pmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{n1} & a_{n2} & \cdots & a_{nn} \end{pmatrix}=\begin{pmatrix} 1 & 0 & \cdots & 0 \\ l_{21} & 1 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ l_{n1} & l_{n2} & \cdots & 1 \end{pmatrix} \begin{pmatrix} u_{11} & u_{12} & \cdots & u_{1n} \\ 0 & u_{22} & \cdots & u_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & u_{nn} \end{pmatrix} a11a21⋮an1a12a22⋮an2⋯⋯⋱⋯a1na2n⋮ann = 1l21⋮ln101⋮ln2⋯⋯⋱⋯00⋮1 u110⋮0u12u22⋮0⋯⋯⋱⋯u1nu2n⋮unn
根据矩阵乘法得到，各个元素的计算公式：
Step 1：计算 U U U的第一行元素： a 1 i = u 1 i a_{1i}=u_{1i} a1i=u1i
Step 2:计算 L L L的第一列元素：
a i 1 = l i 1 u 11 a_{i1}=l_{i1}u_{11} ai1=li1u11
Step 3:
根据给出的 U \mathbf{U} U的第 1 1 1行到第 r − 1 r-1 r−1行与 L \mathbf{L} L的第 1 1 1列到第 r − 1 r-1 r−1列求第 r r r行列元素：
a r i = ∑ k = 1 n l r k u k i = ∑ k = 1 r − 1 l r k u k i + u r i a_{ri}=\sum_{k=1}^{n}l_{rk}u_{ki}=\sum_{k=1}^{r-1}l_{rk}u_{ki}+u_{ri} ari=k=1∑nlrkuki=k=1∑r−1lrkuki+uri
a i r = ∑ k = 1 n l i k u k r = ∑ k = 1 r − 1 l i k u k r + l i r u r r a_{ir}=\sum_{k=1}^{n}l_{ik}u_{kr}=\sum_{k=1}^{r-1}l_{ik}u_{kr}+l_{ir}u_{rr} air=k=1∑nlikukr=k=1∑r−1likukr+lirurr
然后使用换元法，逐步解决线性方程组的求解：
A x = b ⇒ { L y = b U x = y \mathbf{Ax}=\mathbf{b}\Rightarrow \begin{cases} \mathbf{Ly}=\mathbf{b}\\ \mathbf{Ux}=\mathbf{y} \end{cases} Ax=b⇒{Ly=bUx=y
例
请使用 L U LU LU分解方法求解线性方程组：
( 2 3 0 1 6 7 1 5 2 − 1 3 3 2 − 1 1 8 ) ( x 1 x 2 x 3 x 4 ) = ( − 5 − 11 7 − 2 ) \begin{pmatrix} 2 & 3 & 0 & 1 \\ 6 & 7 & 1 & 5 \\ 2 & -1 & 3 & 3 \\ 2 & -1 & 1 & 8 \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \\ x_3 \\ x_4\\ \end{pmatrix}= \begin{pmatrix} -5 \\ -11 \\ 7 \\ -2 \end{pmatrix} 262237−1−101311538 x1x2x3x4 = −5−117−2
解
( 2 3 0 1 6 7 1 5 2 − 1 3 3 2 − 1 1 8 ) = ( 1 l 21 1 l 31 l 32 l 33 l 41 l 42 l 43 1 ) ( u 11 u 12 u 13 u 14 u 22 u 23 u 24 u 33 u 34 u 44 ) \begin{pmatrix} 2 & 3 & 0 & 1 \\ 6 & 7 & 1 & 5 \\ 2 & -1 & 3 & 3 \\ 2 & -1 & 1 & 8 \end{pmatrix}= \begin{pmatrix} 1 & & & \\ l_{21} & 1 & & \\ l_{31} & l_{32} & l_{33} & \\ l_{41} & l_{42} & l_{43} & 1 \end{pmatrix} \begin{pmatrix} u_{11} & u_{12} &u_{13} &u_{14} \\ & u_{22} &u_{23} & u_{24} \\ & & u_{33} &u_{34} \\ & & & u_{44} \end{pmatrix} 262237−1−101311538 = 1l21l31l411l32l42l33l431 u11u12u22u13u23u33u14u24u34u44
注意到
对于系数矩阵第一行：
( 2 3 0 1 6 7 1 5 2 − 1 3 3 2 − 1 1 8 ) = ( 1 l 21 1 l 31 l 32 l 33 l 41 l 42 l 43 1 ) ( 2 3 0 1 u 22 u 23 u 24 u 33 u 34 u 44 ) \begin{pmatrix} 2 & 3 & 0 & 1 \\ 6 & 7 & 1 & 5 \\ 2 & -1 & 3 & 3 \\ 2 & -1 & 1 & 8 \end{pmatrix}= \begin{pmatrix} 1 & & & \\ l_{21} & 1 & & \\ l_{31} & l_{32} & l_{33} & \\ l_{41} & l_{42} & l_{43} & 1 \end{pmatrix} \begin{pmatrix} 2 & 3&0 &1 \\ & u_{22} &u_{23} & u_{24} \\ & & u_{33} &u_{34} \\ & & & u_{44} \end{pmatrix} 262237−1−101311538 = 1l21l31l411l32l42l33l431 23u220u23u331u24u34u44
对于系数矩阵第一列：
( 2 3 0 1 6 7 1 5 2 − 1 3 3 2 − 1 1 8 ) = ( 1 3 1 1 l 32 l 33 1 l 42 l 43 1 ) ( 2 3 0 1 u 22 u 23 u 24 u 33 u 34 u 44 ) \begin{pmatrix} 2 & 3 & 0 & 1 \\ 6 & 7 & 1 & 5 \\ 2 & -1 & 3 & 3 \\ 2 & -1 & 1 & 8 \end{pmatrix}= \begin{pmatrix} 1 & & & \\ 3 & 1 & & \\ 1& l_{32} & l_{33} & \\ 1 & l_{42} & l_{43} & 1 \end{pmatrix} \begin{pmatrix} 2 & 3&0 &1 \\ & u_{22} &u_{23} & u_{24} \\ & & u_{33} &u_{34} \\ & & & u_{44} \end{pmatrix} 262237−1−101311538 = 13111l32l42l33l431 23u220u23u331u24u34u44
递推得到：
( 2 3 0 1 6 7 1 5 2 − 1 3 3 2 − 1 1 8 ) = ( 1 3 1 1 2 1 1 2 − 1 1 ) ( 2 3 0 1 − 2 1 2 1 − 2 1 ) \begin{pmatrix} 2 & 3 & 0 & 1 \\ 6 & 7 & 1 & 5 \\ 2 & -1 & 3 & 3 \\ 2 & -1 & 1 & 8 \end{pmatrix}= \begin{pmatrix} 1 & & & \\ 3 & 1 & & \\ 1& 2 & 1 & \\ 1 & 2 & -1 & 1 \end{pmatrix} \begin{pmatrix} 2 & 3&0 &1 \\ & -2 &1 & 2 \\ & & 1 &-2 \\ & & & 1 \end{pmatrix} 262237−1−101311538 = 13111221−11 23−201112−21
做换元：
A x = b ⇒ { L y = b U x = y \mathbf{Ax}=\mathbf{b}\Rightarrow \begin{cases} \mathbf{Ly}=\mathbf{b}\\ \mathbf{Ux}=\mathbf{y} \end{cases} Ax=b⇒{Ly=bUx=y
得到：
y = ( y 1 y 2 y 3 y 4 ) = ( − 5 4 4 − 1 ) \mathbf{y}=\begin{pmatrix} y_1 \\ y_2 \\ y_3 \\ y_4 \end{pmatrix}=\begin{pmatrix} -5 \\ 4 \\ 4 \\ -1 \end{pmatrix} y= y1y2y3y4 = −544−1
x = ( x 1 x 2 x 3 x 4 ) = ( 1 − 2 2 − 1 ) \mathbf{x}= \begin{pmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \end{pmatrix}=\begin{pmatrix} 1 \\ -2 \\ 2 \\ -1 \end{pmatrix} x= x1x2x3x4 = 1−22−1