-
主元
鎖定
主元(pivot element),一種變元。指在消去過程中起主導作用的元素。
- 中文名
- 主元
- 外文名
- pivot element
- 適用範圍
- 數理科學
主元主元消去法
[pivoting elimination method]
高斯消去法在消元過程中可能出現零主元,即
,這時消元過程將無法進行;也可能主元
,但其絕對值非常小,用它做除法將會導致舍入誤差的擴散,使數值解不可靠。解決該問題的辦法是避免使用絕對值過小的元素作主元。選主元早在1947年就已由馮·諾依曼(von Neumann)和戈爾德施泰因(Goldstine)所使用。
在第 k 步消元時,通常採用如下方式選取主元:在
中選擇絕對值最大者作為主元;或在
中選擇絕對值最大者作為主元。前者被稱為部分主元(partial pivoting)或列主元,後者則被稱為全主元(complete pivoting)。術語“部分主元”和“全主元”由威爾金森(Wilkin-son)所提出。
主元部分主元高斯消去法
部分主元高斯消去法消元過程的第 k 步如下:
(1)選主元,選取
作為主元。若
有多個值,則取
中最小者;
(2)交換
的第 k ,
行,並將交換之後的增廣矩陣仍記為
;
(3)將
第 k 行的
倍加到第i=(i=k=1,...,n)行。
也可以用矩陣運算表示部分主元高斯消去法的消元過程。交換單位矩陣 I 的第 i ,j(i < j)兩行(列)所得的矩陣被稱為初等置換矩陣,記為
,簡記為
,則
是對稱正交矩陣。設第 k 步中交換
第 k,
行的初等置換矩陣為
,高斯變換矩陣為
。記
,
則可以證明:P 是排列矩陣,並且PA=LU。因此,矩陣 A 的部分主元消元過程實現了 A 的一個部分主元三角分解。
主元全主元高斯消去法
全主元高斯消去法消元過程的第 k 步如下:
(1)選主元,選取
作為主元。若
有多少個值,則分別取
中最小者;
(2)交換
的第 k ,
行和第
列,並將交換之後的增廣矩陣仍記為
;
(3)將
第 k 行的
倍加到第
行。
經過
步消元,得到數組
和
,其中
是該上三角矩陣。應用回代法即可求得上三角方程組的解,利用數組
可得到原方程的解。
全主元高斯消去法的消元過程也可用矩陣運算表示。設第 k 步中交換
的第
行的初等置換矩陣為
,交換
的第
列第初等置換矩陣為
,高斯變換矩陣為
。記
,
,
,則可以證明:P,Q是排列矩陣,並且PAQ=LU。因此,矩陣 A 的全主元消元過程實現了 A 的一個全主元三角分解。
主元應用
在20世紀40年代中期,馮·諾依曼等預言高斯消去法一定是數值不穩定的。在20世紀50年代早期,計算經驗已經證實主元高斯消去法實際上是穩定的。對這種現象的解釋在理論上是一個很大的挑戰。威爾金森因對這個課題的貢獻而成名。可以證明:如果 n 階矩陣 A 非奇異,則用主元高斯消去法求解Ax=b 所得到的計算解
滿足
,其中
是單位舍入,
為主元高斯消去法的增長因子。
主元高斯消去法的數值穩定性取決於其增長因子的大小。對於部分主元高斯消去法,其增長因子
以
為上界。威爾金森和賴特(Wright)構造了一些例子,説明部分主元高斯消去法的增長因子的這個上界是可以達到的。但是,在大多數實際計算中,由部分主元高斯消去法所產生的矩陣元素迅速增長的情況非常罕見。