其他連結
WikiWand
LU
ptt 對角線討論
\( L \): lower matrix
\( U \): upper matrix
\(
A=LU
\)
\(
\leadsto
\) LU-decomposition
\(
A\in F^{m\times n}
\)
\(
L\in F^{m\times m},
U\in F^{m\times n}
\)
\(
x\in F^{n\times 1},
b\in F^{m\times 1}
\)
\(
Ax=b
\)
\(
\Rightarrow
LUx=b
\)
LDU
D: Diagonal matrix
\(
A\in F^{m\times n}
\)
\(
L\in F^{m\times m},
D\in F^{m\times m},
U\in F^{m\times n}
\)
\(
A=LU_1=
\begin{bmatrix}
1 & 2 & 3 \\
4 & -6 & -6 \\
-7 & -7 & 9
\end{bmatrix}
=
\begin{bmatrix}
1 & 0 & 0 \\
4 & 1 & 0 \\
7 & 1/2 & 1
\end{bmatrix}
\begin{bmatrix}
1 & 2 & 3 \\
0 & -14 & -18 \\
0 & 0 & 21
\end{bmatrix}
\)
\(
=LDU
=
\begin{bmatrix}
1 & 0 & 0 \\
4 & 1 & 0 \\
7 & 1/2 & 1
\end{bmatrix}
\begin{bmatrix}
1 & 0 & 0 \\
0 & -14 & 0 \\
0 & 0 & 21
\end{bmatrix}
\begin{bmatrix}
1/1 & 2/1 & 3/1 \\
0 & (-14)/(-14) & (-18)/(-14) \\
0 & 0 & 21/21
\end{bmatrix}
\)
\(
=
\begin{bmatrix}
1 & 0 & 0 \\
4 & 1 & 0 \\
7 & 1/2 & 1
\end{bmatrix}
\begin{bmatrix}
1 & 0 & 0 \\
0 & -14 & 0 \\
0 & 0 & 21
\end{bmatrix}
\begin{bmatrix}
1 & 2 & 3 \\
0 & 1 & 9/7 \\
0 & 0 & 1
\end{bmatrix}
\)
Notice
\(
E\in F^{m\times m}
, A\in F^{m\times n}
\)
\(
E=R_kR_{k-1}\dots R_1
\)
\(
\because R \text{ is inverse.}
\)
\(
\therefore E \text{ is inverse.}
\)
\(
A\xrightarrow[\quad\text{without permutation of row}\quad]{E}
U
\)
\(
EA=U
\)
\(
L=E^{-1}
\)
\(
\Rightarrow
(R_kR_{k-1}\dots R_1)A=U
\)
\(
A=
(R_kR_{k-1}\dots R_1)^{-1}U
=
R_{1}^{-1}R_{2}^{-1}\dots R_{k}^{-1}U
\)
Example
Find an LU-decomposition of
\(
A=
\begin{bmatrix}
1 & 2 & 3 \\
4 & -6 & -6 \\
-7 & -7 & 9
\end{bmatrix}.
\)
solution
\(
A\xrightarrow{r_{12}^{(-4)}, r_{13}^{(7)}, r_{23}^{(\frac{1}{2})}}
\begin{bmatrix}
1 & 2 & 3 \\
0 & -14 & -18 \\
0 & 0 & 21
\end{bmatrix}
=U
\)
\(
E=
R_{23}^{(\frac{1}{2})}R_{13}^{(7)}R_{12}^{(-4)}
\)
\(
L=E^{-1}
\)
\(
=(R_{23}^{(\frac{1}{2})}R_{13}^{(7)}R_{12}^{(-4)})^{-1}
\)
\(
=
(R_{12}^{(-4)})^{-1}
(R_{13}^{(7)})^{-1}
(R_{23}^{(\frac{1}{2})})^{-1}
\)
\(
=
R_{12}^{(4)}
R_{13}^{(-7)}
R_{23}^{(-\frac{1}{2})}
\)
\(
=
\begin{bmatrix}
1 & 0 & 0 \\
4 & 1 & 0 \\
0 & 0 & 1
\end{bmatrix}
\begin{bmatrix}
1 & 0 & 0 \\
0 & 1 & 0 \\
-7 & 0 & 1
\end{bmatrix}
\begin{bmatrix}
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & -1/2 & 1
\end{bmatrix}
=
\begin{bmatrix}
1 & 0 & 0 \\
4 & 1 & 0 \\
-7 & -1/2 & 1
\end{bmatrix}
\)
\(
\ast \ast \ast
\begin{bmatrix}
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & -1/2 & 1
\end{bmatrix}
\begin{bmatrix}
1 & 0 & 0 \\
0 & 1 & 0 \\
-7 & 0 & 1
\end{bmatrix}
\begin{bmatrix}
1 & 0 & 0 \\
4 & 1 & 0 \\
0 & 0 & 1
\end{bmatrix}
=
\begin{bmatrix}
1 & 0 & 0 \\
4 & 1 & 0 \\
-9 & 1/2 & 1
\end{bmatrix}
\neq
\begin{bmatrix}
1 & 0 & 0 \\
4 & 1 & 0 \\
-7 & -1/2 & 1
\end{bmatrix}
\)
Application
Using LU-decomposition to solute linear-system equation.
\(
Ax=b
\)
\(
\rightarrow
LUx=b
\)
let
\(
Ux=y
\)
thus,
\(
Ly=b
\)
Step 1: forward substitution solute y
Step 2: back substitution solute x
題目
台大 99 資工
Reference
黃子嘉-線性代數