解線性方程組迭代法的若干幾何研究

盧興江， 金通洸

(浙江大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，杭州310027)

1 引 言

迭代法是解線性方程組常用的方法，如著名的Jacobi迭代法，Gauss-Seidel迭代法和SOR迭代法[1]等.但對(duì)這些迭代過(guò)程的認(rèn)識(shí)、收斂性分析等一般是從分析和代數(shù)上去研究，例如一個(gè)迭代法的收斂與否決定于相應(yīng)迭代矩陣的譜半徑是否小于1，而求譜半徑并非易事，而且僅從譜半徑去認(rèn)識(shí)迭代法的收斂性是不夠的，一個(gè)簡(jiǎn)單的事實(shí)是：對(duì)某些線性方程組，若變換各個(gè)方程的次序，會(huì)改變一些迭代法的收斂性，而解的存在與否是和這些方程的次序無(wú)關(guān)的.要對(duì)這樣的問(wèn)題作出解釋?zhuān)沂境龅ǖ膸缀伪举|(zhì)是重要的.下面將從幾何上提出兩種迭代過(guò)程，從而得到解線性方程組迭代法的幾何實(shí)質(zhì).

2 記 號(hào)

記n階線性方程組為

Ax=b,

(1)

其中A=(aij)n×n∈n×n為n階系數(shù)矩陣，b=為n維常數(shù)向量，x=(x1,x2,…,xn)T為n維未知向量.

記Ai=(ai1,ai2,…,ain),fi(x)=bi-Aix,i=1,2,…,n，則(1)即為

fi(x)=0,i=1,2,…,n.

這n個(gè)方程分別代表n個(gè)超平面，記為πi,i=1,2,…,n.即

πi∶fi(x)=bi-Aix=0，

其中(Ai)T為πi的法向量，i=1,2,…,n.

3 迭代法的兩個(gè)基本幾何過(guò)程

對(duì)線性方程組(1)，首先我們從幾何上來(lái)看兩個(gè)基本迭代過(guò)程.

(Ⅰ) 反射過(guò)程(反射迭代)

對(duì)方程組(1) 的n個(gè)超平面πi,i=1,2,…,n, 選定一組方向(向量)Ei∈n,i=1,2,…,n, 且E1,E2,…,En線性無(wú)關(guān).則反射迭代為這樣一個(gè)過(guò)程(如圖1，其中x*為方程組的解)

圖1 反射迭代

① 選取初值(初始點(diǎn))x0∈n；

③ 這樣得到迭代向量序列{xn}∶x1,x2,…,xn,…

以上過(guò)程稱(chēng)為反射過(guò)程，或反射迭代.

定理1對(duì)方程組(1)及一組線性無(wú)關(guān)的方向E1,E2,…,En，若A非奇異，且Ai·Ei≠0 (i=1,2,…,n)，則

(i)反射迭代可以一直進(jìn)行下去；

(2)

其中(Rij)n×n稱(chēng)之為關(guān)聯(lián)矩陣，Rij稱(chēng)為關(guān)聯(lián)系數(shù).

在反射迭代中，取不同的一組方向Ei(i=1,2,…,n)，就可得到不同的迭代法.

定理2對(duì)方程組(1)，若取一組線性無(wú)關(guān)的方向

Ei=εi=(0,0,…,0,1,0,…,0)T(εi第i個(gè)分量為1，其余分量為0)i=1,2,…,n,

則反射迭代即為Gauss-Seidel迭代法.

證若在反射迭代中取

Ei=εi=(0,0,…,0,1,0,…,0)T,i=1,2,…,n,

即

這恰為Gauss-Seidel迭代法計(jì)算表達(dá)式[1].

因此，Gauss-Seidel迭代法是一種反射迭代過(guò)程. 從這個(gè)幾何本質(zhì)可以看到，Gauss-Seidel迭代法的收斂性是與方程組的各方程(超平面)的次序是有關(guān)系的，因?yàn)樗c“坐標(biāo)”εi(i=1,2,…,n)有關(guān)，如圖2和圖3相同的兩個(gè)方程(兩張“超平面”)，次序不同，收斂性不同 .

圖2 G-S迭代收斂 圖3 G-S迭代發(fā)散

如果在上述反射過(guò)程中引進(jìn)一個(gè)伸縮因子，則有以下迭代過(guò)程，我們稱(chēng)之為伸縮反射過(guò)程(伸縮反射迭代)：

① 選取初值(初始點(diǎn))x0∈n；

圖4 伸縮反射迭代

③ 這樣得到迭代向量序列{xn}∶x1,x2,…,xn,….

顯然，伸縮反射迭代中若取所有的伸縮因子為1，則伸縮反射過(guò)程即為前面的反射過(guò)程 .

定理3對(duì)方程組(1)和一組線性無(wú)關(guān)方向Ei，若AiEi≠0(i=1,2,…,n)，則

(i) 伸縮反射迭代可以一直進(jìn)行下去；

(ii) 對(duì)任意給定的初值x0∈n，存在唯一確定的伸縮因子使得迭代n步即得方程組的精確解,即有x1=x*.

對(duì)于(i)的證明類(lèi)似于定理1的(i)的證明 .

對(duì)于(ii)，因?yàn)?/p>

此恰為SOR迭代法計(jì)算表達(dá)式[1].

所以，SOR方法為伸縮反射過(guò)程的一個(gè)特例.

定義1在n維空間中，n-1張超平面的交線稱(chēng)為棱，與此n-1張超平面法向皆垂直的方向稱(chēng)為棱方向.

記

其中Δij為A=(aij)n×n中aij的代數(shù)余子式.

其中Δ=det(A).

因此，對(duì)方程組(1)中的n個(gè)超平面，Ci(i=1,2,…,n) 即為n個(gè)棱方向.

定理5若取Ei=Ci(i=1,2,…,n)，則對(duì)任何初值x0，反射過(guò)程進(jìn)行n次即得方程組(1)的精確解，即x1為方程組(1)的解.

即x1為方程組(1)的解.

由定理5知，選取Ci(i=1,2,…,n)為反射方向，有限步(n步)迭代可得到方程組的精確解.

推論1若取Ei=Ci(i=1,2,…,n)，且取初值x0=0時(shí)，則反射迭代所得x1即為方程組(1)的克蘭姆[2](Cramer)法則解.

于是

(Ⅱ) 張傘過(guò)程(張傘迭代)

選定一組方向(基)Ei(i=1,2,…,n)，對(duì)方程組(1)，張傘過(guò)程為(圖5)：

圖5 張傘迭代

① 任取x0∈n；

③ 這樣得到迭代向量序列{xn}∶x1,x2,…,xn,….

事實(shí)上，這把傘為一個(gè)仿射標(biāo)架：{xk,E1,E2,…,En}，求方程組(1)的解x*就是在此仿射標(biāo)架中求出x*的“坐標(biāo)”.

定理6對(duì)方程組(1)，若取一組線性無(wú)關(guān)的方向Ei=εi,i=1,2,…,n, 則張傘過(guò)程即為Jacobi迭代法.

即

此即為Jacobi迭代法計(jì)算表達(dá)式[1].

從上述可知，Gauss-Seidel迭代法與Jacobi迭代法有著不同的幾何本質(zhì)，前者是反射過(guò)程，后者為張傘過(guò)程. 在一般情況下反射過(guò)程比張傘過(guò)程收斂快，所以通常說(shuō)Gauss-Seidel迭代法比Jacobi迭代法收斂快，但這兩個(gè)迭代過(guò)程本質(zhì)不同，因此存在對(duì)有的方程組Gauss-Seidel迭代法發(fā)散而Jacobi迭代法收斂的情況也就不足為奇了.

4 降維迭代法

由上面所述，選取棱方向進(jìn)行反射迭代可有限步得到精確解，但是計(jì)算棱方向的計(jì)算量太大，所以在實(shí)際計(jì)算時(shí)不宜采用. 下面將找出一組容易計(jì)算的方向Ei(i=1,2,…,n)，并能迭代有限步得到方程組(1)的精確解，將它稱(chēng)之為降維迭代法.

引理1若對(duì)方程組(1)，反射迭代的方向E1,E2,…,En滿足

AiEj=0，i=1,2,…,n-1;j=i+1,i+2,…,n.

定理7若Ei(i=1,2,…,n) 滿足引理1條件，則反射迭代n步即得方程組(1)的精確解，即x1為精確解.

設(shè)A1,A2,…,An線性無(wú)關(guān)，記hij=Ai·Aj(i,j=1,2,…,n).令

(3)

①E1=A1；

②E2=W2；

確定，即由

(4)

稱(chēng)這樣構(gòu)造的一組方向Ei(i=1,2,…,n)為降維方向.

由以上易知，如果Ei(i=1,2,…,n) 為降維方向，則有

Ej·Ai=0，i=1,2,…,n-1;j=i+1,i+2,…,n.

定理8設(shè)Ei(i=1,2,…,n)為降維方向，則對(duì)方程組(1)，反射迭代n步即得精確解.

證由引理1、定理7和降維方向的構(gòu)造即得.

以降維方向進(jìn)行反射迭代解線性方程組(1)的方法稱(chēng)其為降維迭代法.用降維法求解時(shí)，稱(chēng)反射迭代n步為迭代1次，因有計(jì)算誤差，如果迭代1次誤差不滿足要求，可以將得到的x1作為x0繼續(xù)迭代，這時(shí)因Ei(i=1,2,…,n)已經(jīng)構(gòu)造好，所以繼續(xù)迭代時(shí)計(jì)算非常方便，計(jì)算量很小，但效果很好.

數(shù)值例子[3]：

精確解為x*=(-1,-1,…,-1)T.

以‖x-x*‖∞<ε來(lái)控制精度. 計(jì)算結(jié)果表明，用降維法迭代4次即得精度為10-6的解.

通過(guò)計(jì)算量分析，降維法與共軛梯度法為同一數(shù)量級(jí)，但降維法不要求A為對(duì)稱(chēng)正定，只要A非奇即可. 且數(shù)值例子表明，降維法比共軛梯度法更有效. 例如：

對(duì)Ax=b用降維迭代法迭代2次即得精確解.

5 總 結(jié)

致謝本文是基于博士階段的工作，感謝導(dǎo)師金通洸先生的悉心指導(dǎo).也以此文表示對(duì)金老師的無(wú)限懷念.