數值方法/線性方程組的解

定義和基礎

線性方程組是指一組需要同時求解的線性方程。線性方程的形式為

$a_{1}*x_{1}+a_{2}*x_{2}+\ldots +a_{n}*x_{n}=b\quad ,\,$

其中$n+1\,$個係數$a_{0}\ldots a_{n}\,$和$b\,$是常數，而$x_{1}\ldots x_{n}\,$是n個未知數。根據上面的符號，線性方程組可以表示為

${\begin{matrix}a_{11}*x_{1}+a_{12}*x_{2}+\ldots +a_{1n}*x_{n}&=&b_{1}&\\a_{21}*x_{1}+a_{22}*x_{2}+\ldots +a_{2n}*x_{n}&=&b_{2}&\\&\vdots &&\\a_{m1}*x_{1}+a_{m2}*x_{2}+\ldots +a_{mn}*x_{n}&=&b_{m}&\quad .\end{matrix}}\,$

該系統包含$m\,$個線性方程，每個方程有$n+1\,$個係數，並有$n\,$個未知數，這些未知數必須同時滿足這組方程。為了簡化符號，可以使用矩陣符號重寫上述方程

$\mathbf {A} \cdot \mathbf {x} =\mathbf {b} \quad .\,$

矩陣 $\mathbf {A} \,$ 的元素是方程的係數，$a_{ij}\,$，向量 $\mathbf {x} \,$ 和 $\mathbf {b} \,$ 的元素分別為 $x_{i}\,$ 和 $b_{i}\,$。在這個記號中，每行都構成一個線性方程。

超定和欠定系統

為了使解 $\mathbf {x} \,$ 是唯一的，必須至少有與未知數一樣多的方程。用矩陣表示法來說，這意味著 $m\geq n\,$。但是，如果一個系統包含的方程比未知數多 ($m>n$)，則很有可能（不說是規律）根本不存在解。這樣的系統被稱為 **超定系統**，因為它們包含的方程比未知數多。它們需要特殊的數學方法來近似求解。最常用的方法是 **最小二乘法**，它旨在將試圖求解系統時每個未知數產生的誤差平方和最小化。這種問題通常出現在測量或資料擬合過程中。

示例
假設一個任意三角形：假設一個人用 $\pm 0.2^{\circ }\,$ 的精度測量了所有三個內角 $\alpha ,\beta ,\gamma$。此外，假設邊 a、b 和 c 的長度是精確已知的。從三角學可知，使用餘弦定理，如果已知所有其他邊和角，則可以計算角或邊的長度。但眾所周知，平面三角形的內角之和始終為 $180^{\circ }\,$。因此，我們有三個餘弦定理和角之和規則。這總共構成了四個方程和三個未知數，形成了一個超定問題。

另一方面，如果 $m<n\,$，則會出現問題，即解不是唯一的，因為可以自由選擇一個未知數。同樣，也存在數學方法來處理這類問題。但是，這些方法在本課文中將不予介紹。

本章主要集中討論 $m=n\,$ 的情況，除非另有說明，否則預設此條件成立。

線性系統的精確解

用線性代數求解方程組 $\mathbf {Ax} =\mathbf {b} \,$ 很容易：只需從左側乘以 $\mathbf {A} ^{-1}$，得到 $\mathbf {x} =\mathbf {A} ^{-1}\mathbf {b}$。但是，求解 $\mathbf {A} ^{-1}$（除了平凡的情況）非常困難。以下部分將介紹幾種求解該問題精確解（直到舍入誤差）的方法。

對角和三角形系統

對角矩陣只有主對角線上有元素

$a_{ij}\equiv 0\;\forall \;i\neq j$

在這種情況下，$\mathbf {A}$ 的逆矩陣就是一個對角矩陣，其元素為逆元素，即

$\mathbf {A} ^{-1}={\mbox{diag}}(1/a_{ii})\quad .$

因此，對角系統的解為 $x_{i}=b_{i}/a_{ii}$，這很容易計算。

上三角系統定義為

$a_{ij}=0\quad \forall j<i\quad ,$

而下三角系統定義為

$a_{ij}=0\quad \forall j>i\quad .$

回代法是求解上三角系統的過程

$x_{i}={\begin{cases}b_{i}/a_{ii}\quad &{\mbox{if}}\;i=N\\{\frac {1}{a_{ii}}}\left(b_{i}-\sum _{j=i+1}^{N}{a_{ij}x_{j}}\right)\quad &{\mbox{else}}\quad .\end{cases}}$

另一方面，前代法是對下三角系統執行相同過程。

$x_{i}={\begin{cases}b_{i}/a_{ii}\quad &{\mbox{if}}\;i=1\\{\frac {1}{a_{ii}}}\left(b_{i}-\sum _{j=1}^{i-1}{a_{ij}x_{j}}\right)\quad &{\mbox{else}}\quad .\end{cases}}$

高斯-約旦消元法

該方法不求解 $\mathbf {A} ^{-1}$，而是依賴於行操作。根據線性代數的定律，方程組的行可以乘以一個常數而不改變解。此外，行之間可以相加和相減。這引出了改變方程組結構的想法，使得 $\mathbf {A}$ 具有便於求解 $\mathbf {x}$ 的結構。其中一個結構是如上所述的對角矩陣。

高斯-約旦消元法將矩陣 $\mathbf {A}$ 轉換為對角形式。為了簡化過程，人們通常使用一種改進的方案。首先，將矩陣 $\mathbf {A}$ 和右端向量 $\mathbf {b}$ 組合成增廣矩陣

$\left[\mathbf {A} ,\mathbf {b} \right]={\begin{bmatrix}a_{11}&a_{12}&\cdots a_{1N}&b_{1}\\\vdots &\ddots &\vdots &\vdots \\a_{N1}&a_{N2}&\cdots a_{NN}&b_{N}\end{bmatrix}}$

為了說明，考慮一個易於理解但有效的演算法，它可以由四個基本部分構成

• gelim：主函式遍歷一個簡化方程組的堆疊，透過一系列部分解，一次構建一個變數的完整解。

• stack：重複呼叫reduce，生成一個 堆疊，包含簡化方程組，從小到大排序（例如，包含 2 個元素，如 <ax = b>）。

• solve：在給定簡化方程組和部分解的情況下，求解一個變數。例如，給定簡化方程組 <aw bx cy = d> 和部分解 <x y>，則 w = (d - bx - cy)/a。現在，部分解 <w x y> 可用於下一輪，例如 <au bv cw dx , e>。

• reduce：從頂部獲取第一個方程並將其壓入堆疊；然後生成一個殘差 - 簡化矩陣，透過從剩餘較下方程的對應元素中減去第一個原始方程的元素，例如 b[j][k]/b[j][0] - a[k]/a[0]。正如您所見，這透過將一個元素從一個元素中減去來消除每個較下方程的第一個元素，並且只需要保留剩餘的元素 - 最終，殘差是一個輸出矩陣，其行和列比輸入矩陣少一行和一列。然後將其用作下一次迭代的輸入。

需要注意的是，乘法也可以用作除法的替代；但是，對於較大的矩陣（例如 n=10），這會產生級聯效應，導致產生 NAN（無窮大）。從統計學上看，除法具有將簡化矩陣歸一化的效果 - 生成均值更接近零且標準差更小的數字；對於隨機生成的資料，這會生成具有接近 +-1 的條目的簡化矩陣。

繼續的內容仍待撰寫

正如它所示，將方程組轉換為完全對角形式並非必要。將其轉換為三角形形式（上三角或下三角）就足夠了，因為然後可以透過反向或正向替換分別求解它。

LU分解

本節內容待撰寫

線性方程組的近似解

本節內容待撰寫

雅可比迭代法

這是一個迭代方案。

高斯-賽德爾迭代法

本節內容待撰寫

10v+w+x-2y+z=-1
v-20w-2x+y+z=20
v+w+10x-y-z=-1
-v-2w+x+50y+z=2
v+w+x+y+100z=-1 
;find result:

超鬆弛迭代法 (SOR)

SOR 是連續超鬆弛法的縮寫。它是一種迭代方案，使用鬆弛引數 $\omega$，並且是 $\omega =1$ 特殊情況下的高斯-賽德爾方法的推廣。

給定一個具有未知數 x 的 n 個線性方程的方陣系統

$A\mathbf {x} =\mathbf {b}$

其中

$A={\begin{bmatrix}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{bmatrix}},\qquad \mathbf {x} ={\begin{bmatrix}x_{1}\\x_{2}\\\vdots \\x_{n}\end{bmatrix}},\qquad \mathbf {b} ={\begin{bmatrix}b_{1}\\b_{2}\\\vdots \\b_{n}\end{bmatrix}}.$

那麼 A 可以分解為一個 對角 分量 D，以及 嚴格的下三角和上三角 分量 L 和 U

$A=D+L+U,$

其中

$D={\begin{bmatrix}a_{11}&0&\cdots &0\\0&a_{22}&\cdots &0\\\vdots &\vdots &\ddots &\vdots \\0&0&\cdots &a_{nn}\end{bmatrix}},\quad L={\begin{bmatrix}0&0&\cdots &0\\a_{21}&0&\cdots &0\\\vdots &\vdots &\ddots &\vdots \\a_{n1}&a_{n2}&\cdots &0\end{bmatrix}},\quad U={\begin{bmatrix}0&a_{12}&\cdots &a_{1n}\\0&0&\cdots &a_{2n}\\\vdots &\vdots &\ddots &\vdots \\0&0&\cdots &0\end{bmatrix}}.$

線性方程組可以改寫為

$(D+\omega L)\mathbf {x} =\omega \mathbf {b} -[\omega U+(\omega -1)D]\mathbf {x}$

其中ω > 1為常數。

逐次超鬆弛法是一種迭代技術，它使用表示式右側的x先前值求解左側的x。用分析方法表示，可以寫成

$\mathbf {x} ^{(k+1)}=(D+\omega L)^{-1}{\big (}\omega \mathbf {b} -[\omega U+(\omega -1)D]\mathbf {x} ^{(k)}{\big )}.$

但是，利用(D+ωL)的三角形式，可以使用前向替換按順序計算x^(k+1)的元素

$x_{i}^{(k+1)}=(1-\omega )x_{i}^{(k)}+{\frac {\omega }{a_{ii}}}\left(b_{i}-\sum _{j>i}a_{ij}x_{j}^{(k)}-\sum _{j<i}a_{ij}x_{j}^{(k+1)}\right),\quad i=1,2,\ldots ,n.$

鬆弛因子的選擇並不容易，它取決於係數矩陣的性質。對於對稱、正定 矩陣，可以證明0 < ω < 2將導致收斂，但我們通常更關注更快地收斂而不是僅僅收斂。

共軛梯度法

本節內容待撰寫

多重網格法

本節內容待撰寫

---

主頁 - 數學書架 - 數值方法