[科普中國(guó)]-主元

[pivoting elimination method]

高斯消去法在消元過(guò)程中可能出現(xiàn)零主元，即，這時(shí)消元過(guò)程將無(wú)法進(jìn)行；也可能主元，但其絕對(duì)值非常小，用它做除法將會(huì)導(dǎo)致舍入誤差的擴(kuò)散，使數(shù)值解不可靠。解決該問(wèn)題的辦法是避免使用絕對(duì)值過(guò)小的元素作主元。選主元早在1947年就已由馮·諾依曼（von Neumann）和戈?duì)柕率┨┮颍℅oldstine）所使用。

在第 k 步消元時(shí)，通常采用如下方式選取主元：在中選擇絕對(duì)值最大者作為主元；或在中選擇絕對(duì)值最大者作為主元。前者被稱為部分主元（partial pivoting）或列主元，后者則被稱為全主元（complete pivoting）。術(shù)語(yǔ)“部分主元”和“全主元”由威爾金森（Wilkin-son）所提出。

部分主元高斯消去法消元過(guò)程的第 k 步如下：

（1）選主元，選取 作為主元。若 有多個(gè)值，則取 中最小者；

（2）交換 的第 k ， 行，并將交換之后的增廣矩陣仍記為 ；

（3）將 第 k 行的 倍加到第i=（i=k=1,...,n）行。

經(jīng)過(guò) 步消元，得到 ，其中 是上三角矩陣，則Ax=b化為一個(gè)同解上三角方程組，應(yīng)用回代法即可求得方程組的解。部分主元高斯消去法的工作量約為 個(gè)浮點(diǎn)運(yùn)算和 次邏輯運(yùn)算。

也可以用矩陣運(yùn)算表示部分主元高斯消去法的消元過(guò)程。交換單位矩陣 I 的第 i ，j（i < j）兩行（列）所得的矩陣被稱為初等置換矩陣，記為 ，簡(jiǎn)記為 ，則 是對(duì)稱正交矩陣。設(shè)第 k 步中交換 第 k， 行的初等置換矩陣為 ，高斯變換矩陣為 。記 ， 則可以證明：P 是排列矩陣，并且PA=LU。因此，矩陣 A 的部分主元消元過(guò)程實(shí)現(xiàn)了 A 的一個(gè)部分主元三角分解。

全主元高斯消去法消元過(guò)程的第 k 步如下：

（1）選主元，選取 作為主元。若 有多少個(gè)值，則分別取 中最小者；

（2）交換 的第 k ，行和第列，并將交換之后的增廣矩陣仍記為；

（3）將第 k 行的倍加到第行。

經(jīng)過(guò)步消元，得到數(shù)組和，其中是該上三角矩陣。應(yīng)用回代法即可求得上三角方程組的解，利用數(shù)組可得到原方程的解。

全主元高斯消去法的工作量約為個(gè)浮點(diǎn)運(yùn)算和次邏輯運(yùn)算。與部分主元高斯消去法相比，全主元高斯消去法在其每步的兩維數(shù)組搜索時(shí)需要增加很大的選主元工作量。

全主元高斯消去法的消元過(guò)程也可用矩陣運(yùn)算表示。設(shè)第 k 步中交換的第行的初等置換矩陣為，交換的第列第初等置換矩陣為，高斯變換矩陣為。記,，，則可以證明：P，Q是排列矩陣，并且PAQ=LU。因此，矩陣 A 的全主元消元過(guò)程實(shí)現(xiàn)了 A 的一個(gè)全主元三角分解。

在20世紀(jì)40年代中期，馮·諾依曼等預(yù)言高斯消去法一定是數(shù)值不穩(wěn)定的。在20世紀(jì)50年代早期，計(jì)算經(jīng)驗(yàn)已經(jīng)證實(shí)主元高斯消去法實(shí)際上是穩(wěn)定的。對(duì)這種現(xiàn)象的解釋在理論上是一個(gè)很大的挑戰(zhàn)。威爾金森因?qū)@個(gè)課題的貢獻(xiàn)而成名?？梢宰C明：如果 n 階矩陣 A 非奇異，則用主元高斯消去法求解Ax=b 所得到的計(jì)算解滿足，其中是單位舍入，為主元高斯消去法的增長(zhǎng)因子。

主元高斯消去法的數(shù)值穩(wěn)定性取決于其增長(zhǎng)因子的大小。對(duì)于部分主元高斯消去法，其增長(zhǎng)因子以為上界。威爾金森和賴特（Wright）構(gòu)造了一些例子，說(shuō)明部分主元高斯消去法的增長(zhǎng)因子的這個(gè)上界是可以達(dá)到的。但是，在大多數(shù)實(shí)際計(jì)算中，由部分主元高斯消去法所產(chǎn)生的矩陣元素迅速增長(zhǎng)的情況非常罕見(jiàn)。

對(duì)全主元高斯消去法，威爾金森證明了。威爾金森指出，對(duì)于充分大的 n ，這個(gè)界遠(yuǎn)遠(yuǎn)小于。據(jù)此可以推斷：全主元高斯消去法是數(shù)值穩(wěn)定的。威爾金森曾猜測(cè)：全主元高斯消去法的增長(zhǎng)因子以矩陣的階為界，即。但是，古爾德（Gould）構(gòu)造了一個(gè)反例，說(shuō)明威爾金森的猜測(cè)是不正確的。1