第二章線性方程組的直接解法

2.1 引言

很多數(shù)學模型的計算最終都歸結為求解線性方程組。

$線性方程組的解法\begin{cases}直接解法（經過有限次計算，求得精確解。過程中無舍入誤差） \\ 迭代解法（變形為等價方程組，構造迭代公式，對給定初值迭代得到近似解） \end{cases}$

2.2 Gauss 消去法

Gauss 消去法的基本思想

利用初等行變換，將線性方程組的增廣矩陣轉化為上三角矩陣，再通過回代求得方程組的解。

例子解線性方程組：
$\begin{cases} x_1 +2x_2 +3x_3 &=1\\ 2x_1 +7x_2 +5x_3 &=6\\ x_1 +4x_2 +9x_3 &=-3 \end{cases}$

解
第一步，初等行變換：
$\begin{cases} x_1 +2x_2 +3x_3 &=1\\ 3x_2 -x_3 &=4\\ 2x_2 +6x_3 &=-4 \end{cases}$

第二步，化為上三角矩陣：
$\begin{cases} x_1 +2x_2 +3x_3 &=1\\ 3x_2 -x_3 &=4\\ \frac{20}{3}x_3 &= -\frac{20}{3} \end{cases}$

第三步，回代求得： $x^*=(2,1,-1)^T$

Gauss 消去法的計算公式

看前述例子。

Gauss 消去法的條件

能用 Gauss 消去法求解線性方程組 $Ax=b$ 的充要條件是系數(shù)陣 $A$ 的各階順序主子式不為零。

Gauss 消去法的計算量約為 $\frac{n^3}{3}$ 。

2.3 Gauss 主元素法

Gauss 消去法中，若存在 $\mid a^{(i)}_{ii} \mid \ll 1$ ，則會導致舍入誤差擴散。

例子采用三位有效數(shù)字計算，求解線性方程組：
$\begin{cases} 0.50x_1 +1.1x_2 +3.1x_3 &=6.0\\ 2.0x_1 +4.5x_2 +0.36x_3 &=0.020\\ 5.0x_1 +0.96x_2 +6.5x_3 &=0.96 \end{cases}$

解方程組的精確解為: $x^*=(-2.6,1,2)^T$ 。

解法一 順序消去法
$\left(\begin{array}{lcr|r} 0.50 & 1.1 & 3.1 & 6.0\\ 2.0 & 4.5 & 0.36 & 0.020\\ 5.0 & 0.96 & 6.5 & 0.96 \end{array}\right) \xrightarrow[l_{31}=10]{l_{21}=4} \left(\begin{array}{lcr|r} 0.50 & 1.1 & 3.1 & 6.0\\ 0 & 0.100 & -12.0 & -24.0\\ 0 & -10.0 & -24.5 & -59.0 \end{array}\right) \xrightarrow{l_{32}=-100} \left(\begin{array}{lcr|r} 0.50 & 1.1 & 3.10 & 6.0\\ 0 & 0.100 & -12.0 & -24.0\\ 0 & 0 & -1220 & -2460 \end{array} \right)$
回代求得: $x=(-5.80,2.40,2.02)^T$ 。

解法二 列主元消去法
$\left( \begin{array}{lcr|r} 0.50 &1.1 &3.1 &6.0\\ 2.0 &4.5 &0.36 &0.020\\ 5.0^* &0.96 &6.5 &0.96 \end{array} \right) \xrightarrow{} \left( \begin{array}{lcr|r} 5.0 &0.96 &6.5 &0.96\\ 2.0 &4.5 &0.36 &0.020\\ 0.50 &1.1 &3.1 &6.0 \end{array} \right) \xrightarrow{} \left( \begin{array}{lcr|r} 5.00 &0.960 &6.50 &0.960\\ 0 &4.12 &-2.24 &-0.364\\ 0 &0 &2.99 &5.99 \end{array} \right)$
回代求得： $x=(-2.60,1,2)^T$ 。

由上可知，通過“選主元”可以避免“零主元”或“小主元”的出現(xiàn)。具體可分為：

列主元消去法
全主元消去法

2.4 Gauss-Jordan 消去法

Gauss-Jordan 消去法的基本思想
將對角線元素上方和下方的元素通過消元運算轉化為 0，并且將對角線元素轉化為 1。即將增廣矩陣的系數(shù)矩陣轉化為單位矩陣。其省去了回代過程，也稱為無回代的 Gauss 消去法。計算量約 $\frac{n^3}{2}$ ，大于 Gauss 消去法。
方陣的求逆
Gauss-Jordan 消去法是初等行變換求逆矩陣的一種規(guī)范化算法。
例子求：
$\left(\begin{array}{lcr} 1 &-1 &0 \\ 2 &2 &3 \\ -1 &2 &1 \end{array} \right)$

解 Gauss-Jordan 消去法：
$\left(\begin{array}{lcr|lcr} 1 &-1 &0 &1 &0 &0\\ 2 &2 &3 &0 &1 &0\\ -1 &2 &1 &0 &0 &1 \end{array}\right) \xrightarrow{r_1{\leftrightarrow} r_2} \left(\begin{array}{lcr|lcr} 2 &2 &3 &0 &1 &0\\1 &-1 &0 &1 &0 &0\\-1 &2 &1 &0 &0 &1 \end{array}\right) \xrightarrow{第一次消元} \left(\begin{array}{lcr|lcr} 1 &1 &3/2 &0 &1/2 &0\\0 &-2 &-3/2 &1 &-1/2 &0\\ 0 &3 &5/2 &0 &1/2 &1 \end{array}\right) \xrightarrow{r_2 \leftrightarrow r_3} \left(\begin{array}{lcr|lcr} 1 &1 &3/2 &0 &1/2 &0\\ 0 &3 &5/2 &0 &1/2 &1\\ 0 &-2 &-3/2 &1 &-1/2 &0 \end{array}\right) \xrightarrow{第二次消元} \left(\begin{array}{lcr|lcr} 1 &0 &2/3 &0 &1/3 &-1/3\\ 0 &1 &5/6 &0 &1/6 &1/3\\ 0 &0 &1/6 &1 &-1/6 &2/3 \end{array}\right) \xrightarrow{第三次消元} \left(\begin{array}{lcr|lcr} 1 &0 &0 &-4 &1 &-3\\ 0 &1 &0 &-5 &1 &-3\\ 0 &0 &1 &6 &-1 &4 \end{array}\right)$
即：
$\left(\begin{array}{lcr} 1 &-1 &0\\ 2 &2 &3\\ -1 &2 &1 \end{array}\right)^{-1} = \left(\begin{array}{lcr} -4 &1 &-3\\ -5 &1 &-3\\ 6 &-1 &4 \end{array}\right)$

2.5 矩陣的 LU 分解

矩陣 LU 分解的定義
對 n 階方陣 $A$ ，若存在 n 階下三角矩陣 $L$ 和 n 階上三角矩陣 $U$ ，使得 $A=LU$ ，則稱 $LU$ 為矩陣 $A$ 的三角分解，簡稱 $LU$ 分解。
為使三角分解唯一，需對分解式規(guī)范化，常見的三角分解有：
Doolittle 分解：限定 $L$ 為單位下三角矩陣。
Crout 分解：限定 $U$ 為單位上三角矩陣。
Doolittle 分解

$\left(\begin{array}{lccr} a_{11} &a_{12} &\cdots &a_{1n}\\ \ _{21} &a_{22} &\cdots &a_{2n}\\ \vdots &\vdots &\ddots &\vdots\\ a_{n1} &a_{n2} &\cdots &a_{nn} \end{array}\right)= \left(\begin{array}{lccr} 1 \\ l_{21} &1\\ \vdots &\vdots &\ddots \\l_{n1} &l_{n2} &\cdots &1 \end{array}\right)\left(\begin{array}{lccr} u_{11} &u_{12} &\cdots &u_{1n}\\ \ &u_{22} &\cdots &u_{2n}\\ \ &\ &\ddots &\vdots\\ \ &\ &\ &u_{nn} \end{array}\right)$

例子用 Doolittle 方法求解方程組 $Ax=B_1,Ax=B_2$ ，其中：
$A=\left(\begin{array}{lccr} 1 &2 &3 &4\\ 1 &4 &9 &16\\ 1 &8 &27 &64\\ 1 &16 &81 &256 \end{array}\right), B_1=\left(\begin{array}{c} 4 \\ 10\\ 28\\ 82\end{array}\right), B_2=\left(\begin{array}{c} 2 \\ 12\\ 56\\240\end{array}\right)$
解：
$\left(\begin{array}{lccr|lr} 1 &2 &3 &4 &4 &2\\ 1 &4 &9 &16 &10 &12\\ 1 &8 &27 &64 &28 &56\\ 1 &16 &81 &256 &82 &240 \end{array}\right) \xrightarrow{計算U的第一行 L的第一列元素} \left(\begin{array}{lccr|lr} 1 &2 &3 &4 &4 &2\\ 1 &4 &9 &16 &10 &12\\ 1 &8 &27 &64 &28 &56\\ 1 &16 &81 &256 &82 &240 \end{array}\right)\xrightarrow{計算U的第二行 L的第二列元素} \left(\begin{array}{lccr|lr} 1 &2 &3 &4 &4 &2\\ 1 &2 &6 &12 &6 &10\\ 1 &3 &27 &64 &28 &56\\ 1 &7 &81 &256 &82 &240 \end{array}\right) \xrightarrow{計算U的第三行 L的第三列元素} \left(\begin{array}{lccr|lr} 1 &2 &3 &4 &4 &2\\ 1 &2 &6 &12 &6 &10\\ 1 &3 &6 &24 &6 &24\\ 1 &7 &6 &24 &0 &24 \end{array}\right)$
即：
$L=\left(\begin{array}{lccr}1 &0 &0 &0\\ 1 &1 &0 &0\\ 1 &3 &1 &0\\1 &7 &6 &1 \end{array}\right), U=\left(\begin{array}{lccr} 1 &2 &3 &4\\ 0 &2 &6 &12\\ 0 &0 &6 &24\\0 &0 &0 &24 \end{array}\right)$
由： $Ax=LUx=b，\begin{cases}Ux=y\\Ly=b\end{cases}$ ，
回代求得： $x_1=(1,0,1,0)^T,x_2=(0,-1,0,1)^T$ 。

Crout 分解
$\left(\begin{array}{lccr} 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{array}\right)= \left(\begin{array}{lccr} l_{11} \\ l_{21} &l_{22}\\ \vdots &\vdots &\ddots \\l_{n1} &l_{n2} &\cdots &l_{nn} \end{array}\right) \left(\begin{array}{lccr} 1 &u_{12} &\cdots &u_{1n}\\ \ &1 &\cdots &u_{2n}\\ \ &\ &\ddots &\vdots\\ \ &\ &\ &1 \end{array}\right)$
例子用 Crout 方法求解方程組：
$\left(\begin{array}{lccr} 2 &4 &2 &6\\ 4 &9 &6 &15\\ 2 &6 &9 &18\\ 6 &15 &18 &40 \end{array}\right) \left(\begin{array}{c} x_1\\ x_2\\ x_3\\ x_4 \end{array}\right)= \left(\begin{array}{c} 9\\23\\22\\47 \end{array}\right)$
解： $L=\left(\begin{array}{lccr}2\\ 4 &1\\ 2 &2 &3\\ 6 &3 &6 &1 \end{array}\right), U=\left(\begin{array}{lccr}1 &2 &1 &3\\ \ &1 &2 &3\\ \ &\ &1 &2\\ \ &\ &\ &1 \end{array}\right)$
回代求得： $x=(0.5,2,3,-1)^T$ 。

2.6 平方根法

若方程組 $Ax=b$ 的系數(shù)矩陣 $A$ 是對稱正定矩陣，則三角分解還可以簡化。

矩陣的 LDU 分解
矩陣 $A$ 的各階順序主子式不等于零，則矩陣 $A$ 可以唯一分解為： $A=LDU$ 。
其中， $L$ 是單位下三角矩陣， $U$ 是單位上三角陣， $D$ 是非奇異對角陣。
Cholesky 分解
若 $A$ 為對稱正定矩陣，則存在三角分解 $A=LL^T$ ，其中 $L$ 是非奇異下三角矩陣。當限定 $L$ 的對角元素為正時，分解唯一。
平方根法
利用 Cholesky 分解來求解對稱正定矩陣方程組 $Ax=b$ 的方法稱為平方根法。計算量約為 $\frac{n^3}{6}$ 。
$\left(\begin{array}{lccr} 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{array}\right)=\left(\begin{array}{lccr} l_{11}\\l_{21} &l_{22}\\ \vdots &\vdots &\ddots\\ l_{n1} &l_{n2} &\cdots &l_{nn} \end{array}\right) \left(\begin{array}{lccr} l_{11} &l_{21} &\cdots &l_{n1}\\ \ &l_{22} &\cdots &l_{n2}\\ \ &\ &\ddots &\vdots\\ \ &\ &\ &l_{nn} \end{array}\right)$
例子用平方根法解方程組：
$\left(\begin{array}{lcr}6 &1 &0\\1&4&1\\0&1&14 \end{array}\right) \left(\begin{array}{c} x_1 \\x_2 \\x_3 \end{array}\right)=\left(\begin{array}{c} 6\\24\\322 \end{array}\right)$
解：
$A=\left(\begin{array}{lcr} 2.4495 &0 &0\\ 0.40825 &1.9579 &0\\ 0 &0.51075 &3.7066 \end{array}\right)\left(\begin{array}{lcr} 2.4495 &0.40825 &0\\ 0 &1.9579 &0.51075\\ 0 &0 &3.7066 \end{array}\right)$
回代求得： $x=(1,0,23)^T$ 。
改進的平方根法
將矩陣轉換為 $LDL^T$ 分解。

2.7 追趕法

2.8 向量和矩陣的范數(shù)

通過范數(shù)這一概念可以有效地解決對向量和矩陣進行度量的問題。

向量范數(shù)
對 n 維空間內的任一向量 $x$ 對應存在一個實數(shù) $\mid\mid x \mid\mid$ ，且滿足1)非負性、2)齊次性、3)三角不等式，則稱實數(shù) $\mid\mid x \mid\mid$ 為向量 $x$ 的范數(shù)。
矩陣范數(shù)
對任一 n 階方陣 $A$ 對應存在一個實數(shù) $\mid\mid A \mid\mid$ ，且滿足1)非負性、2)齊次性、3)三角不等式、4)乘法不等式，則稱實數(shù) $\mid\mid A \mid\mid$ 為矩陣 $A$ 的范數(shù)。
常見的矩陣范數(shù)為：
$\begin{cases}\parallel A \parallel _1 &= \underset{1\ll j \ll n}{max} \sum_{i=1}^{n} \mid a_{ij} \mid &（最大列和范數(shù)）\\ \parallel A \parallel _2 &= \sqrt{\lambda_1} &（\lambda _1 是 A^TA的最大特征值）\\ \parallel A \parallel _\infty &= \underset{1\ll i \ll n}{max} \sum_{j=1}{n} \mid a_{ij} \mid &（最大行和范數(shù)） \end{cases}$
譜半徑
設 n 階矩陣 $A$ 的特征值為 $\lambda _i(i=1,2,\cdots,n)$ ，則稱 $\rho(A)=\underset{1\ll i \ll n}{max} \mid \lambda _i \mid$ 為矩陣 $A$ 的譜半徑。
條件數(shù)及病態(tài)方程組
若 $A$ 和 $b$ 的微小變化只導致 $x$ 發(fā)生微小變化，則稱此問題是良態(tài)的；反之則稱其為病態(tài)的。
若 n 階方陣 $A$ 非奇異，則稱 $\mid\mid A \mid\mid · \mid\mid A^{-1} \mid\mid$ 為矩陣 $A$ 的條件數(shù)，記為 $cond(A)$ 。矩陣的范數(shù)選擇不同，可得不同的條件數(shù)：
$cond(A)_1=\mid\mid A \mid\mid _1 \mid\mid A^{-1} \mid\mid _1$
$cond(A)_2=\mid\mid A \mid\mid _2 \mid\mid A^{-1} \mid\mid _2$
$cond(A)_\infty=\mid\mid A \mid\mid _\infty \mid\mid A^{-1} \mid\mid _\infty$
當 $cond(A)$ 接近于 1 時，稱方程組是良態(tài)的；當 $cond(A)\gg 1$ 時，稱方程組是病態(tài)的。