數值分析6 (高斯消元法)

• • 引言
    • 1 解的存在性
    • 2 解的唯一性
    • 3 Crammer法則
  • 高斯消元法
  • 高斯消元法的實質

1 引言

• 非線性能夠精确且細緻的刻畫現實問題, 但是線性主導了現實。求解非線性方程組、常微分方程組、偏微分方程組和積分方程組最終都是歸結為方程組的求解。大規模代數系統的求解是科學與工程計算的基礎和關鍵,其計算量也占有非常大的比重, 有的甚至占整個計算的80%以上！
• 大規模線性方程組的求解能力綜合地展現了一個國家的基礎科研水準, 比如國際上超級計算機排名的标準就是在相同精度下測試求解大規模線性方程組的速度。
• 大規模線性方程組求解關系到國民經濟和國防安全的若幹關鍵領域, 在很多高新工程技術領域其已成為高精度快速計算的瓶頸。

很多的問題都可以轉化為求解以下的線性方程組，方程也可以寫成 Ax=b 的形式。

⎧⎩⎨⎪⎪⎪⎪⎪⎪a11x1+a12x2+⋯+a1nxn=b1a21x1+a22x2+⋯+a2nxn=b2⋯⋯⋯⋯an1x1+an2x2+⋯+annxn=bn

1.1 解的存在性

• 秩是定量刻畫矩陣性質的名額, 相對于矩陣行列式更加精細。

  增廣矩陣:

[A,b]=⎡⎣⎢⎢⎢⎢⎢a11a21⋮an1a12a22⋮an2⋯⋯⋱⋯a1na2n⋮annb1b2⋮bn⎤⎦⎥⎥⎥⎥⎥

• 如果 rank([A,b])=rank(A) , 則線性方程組的有解。

1.2 解的唯一性

• 如果系數矩陣非奇異即 |A|≠0 （即不可逆）, 則線性方程組的解唯一。 如果系數矩陣奇異即 |A|=0 ,則線性方程組的有無窮多解或無解。例如, 2x+y=3 和 4x+2y=6 有無窮多解; 而 2x+y=3 和 4x+2y=0 則無解。

1.3 (Crammer法則)

設 n 階矩陣A可逆，則線性方程組 Ax=b 有唯一解 x=(x1,x2,⋯,xn)T ，其中

xj=detAjdetA(j=1,2,⋯,n)

計算一個 n 階行列式需要的乘法次數為(n−1)n!,計算的次數相當的大，在工程實踐中，幾乎沒有采用這種方法的。

• 然而求解下三角線性方程組 Lx=c 或者上三角線性方程組 Ux=c ，就會大大的降低求解的難度和算法複雜程度。

2 高斯消元法

Erdős 相信上帝手中有一本包含世間所有精妙證明的天書。上帝相信這本書在 Gauss 手上。

高斯消元法是求解線性方程組的經典方法之一。高斯消元法由兩個部分構成: 消元階段和回代階段 。消元階段的目的是将一般線性方程組轉化成容易求解的上三角線性方程組。例如，下面的方程組：

⎧⎩⎨⎪⎪8x1−6x2+2x3=28(a)−4x1+11x2−7x3=−40(b)4x1−7x2+6x3=33(c)

如何将線性方程組化為更容易求解的線性方程組且不改變線性方程組的解？可以經過一系列的初等變換（初等變換不改變方程的解）。

• 消元階段

  經過第一輪消元:

  ⎧⎩⎨⎪⎪8x1−6x2+2x3=28(a)8x2−6x3=−26(b)−4x2+5x3=19(c)

  注釋: 8是主元 (pivot) , -0.5和0.5是乘子 (multiplier) 。

  經過第二輪消元:

  ⎧⎩⎨⎪⎪8x1−6x2+2x3=28(a)8x2−6x3=−26(b)2x3=6(c)

  注釋: 8是主元 (pivot) , -0.5是乘子 (multiplier) 。

  或者這樣表示簡化的過程：

  ⎡⎣⎢8−44−611−72−76∣∣∣∣28−4033⎤⎦⎥→⎡⎣⎢800−68−42−65∣∣∣∣−282619⎤⎦⎥→⎡⎣⎢800−6802−62∣∣∣∣−28266⎤⎦⎥

  經過這樣的化簡之後有：

  A=LU=⎡⎣⎢1−0.50.501−0.5001⎤⎦⎥⎡⎣⎢800−6802−62⎤⎦⎥

  其中，下三角矩陣是由化簡過程中的乘子構成的，而上三角就是化簡後的矩陣。

• 回代階段

  從最後一個方程開始, 從後往前每次求解一個方程, 則三角方程組的解可以表示如下：

  ⎧⎩⎨⎪⎪x3=6/2=3x2=(−26+6x3)/8=−1x1=(28+6x2−2x3)/8=2

• 對算法複雜度的讨論

  高斯消元法由不相等的兩部分組成:工作量相對多的消元階段和工作量相對少的回代階段。對于大的n, 幂次較低的n相比而言可以忽略不計,最高次幂決定了當n趨近于無窮時的極限形态。換而言之, 對大的n, 低階項對算法的執行時間的估計沒有太大的影響, 當僅需近似估計執行時間時可以忽略不計。我們經常使用記号 O 表示算法是“是多少階的”。是以高斯消元法為O(n3/3)的算法。時間複雜度(算法階數)是衡量算法性能優劣的主要名額。用于估計程式運作的時間。

3 高斯消元法的實質

• 高斯消元法的實質就是矩陣的分解（LU分解），先挖個坑，有時間回來填。