第6章 解線性方程組的迭代法

本文格式為Word版，下載可任意編輯——第6章解線性方程組的迭代法

第6章

解線性方程組的迭代方法

6.1迭代法的基本概念6.2雅可比迭代法與高斯-賽德爾迭代法

6.3超松弛迭代法6.4*共軛迭代法

上頁

下頁

6.1迭代法的基本概念6.1.1引言對線性方程組Ax=b,(1.1)其中A為非奇異矩陣,當A為低階稠密矩陣時,第5章探討的選主元消去法是有效的.但對于大型稀疏矩陣方程組(A的階數(shù)n很大104,但零元素較多),利用迭代法求解是適合的.本章將介紹迭代法的一些基本理論及雅可比迭代法，高斯-賽德爾迭代法，超松弛迭代法，而超松弛迭代法應用很廣泛。下面舉簡例，以便了解迭代法的思想.上頁下頁

例1求解方程組

8x13x22x320,4x111x2x333,6x3x12x36.231記為Ax=b,其中

(1.2)

x183230A4111,xx2,b33.x6312363此方程組的確切解是x*=(3,2,1)T.現(xiàn)將(1.2)改寫為

上頁

下頁

13x22x320),x18(1x333),x2(4x111136).x312(6x13x2或寫為x=B0x+f,其中328020884331B011011,f11.63036121212

(1.3)

上頁

下頁

我們任取初始值，例如取x(0)=(0,0,0)T.將這些值代入(1.3)式右邊(若(1.3)式為等式即求得方程組的解，但一般不滿足),得到新的值x(1)=(x1(1),x2(1),x3(1))T=(3.5,3,3)T,再將x(1)分量代入(1.3)式右邊得到x(2),反復利用這個計算程序，得到一向量序列和一般的計

算公式(迭代公式)(((x10)x11)x1k)(0)(1)(1)(k)x2,xx2,,x(k)x2,(0)(1)(k)x3x3x3

x(0)

上頁

下頁

(((x1k1)(3x2k)2x3k)20)/8,(k1)((x2(4x1k)x3k)33)/11,(k1)(k)(k)(6x13x236)/12.x3

(1.4)

簡寫為

x(k+1)=B0x(k)+f,

其中k表示迭代次數(shù)(k=0,1,2,).迭代到第10次有(10)

x

(3.000032,1.999838,0.999813);T

(10)

0.000187

((10)x(10)x).上頁下頁

此后例看出，由迭代法產生的向量序列x(k)逐步迫近方程組的確切解是x*=(3,2,1)T.即有

limx(k)xk

對于任何一個方程組x=Bx+f(由Ax=b變形得到的等價方程組),由迭代法產生的向量序列x(k)是否一定逐步迫近方程組的解x*呢？回復是不一定.請同學們考慮用迭代法解下述方程組

x12x25,x23x15.

但x

(k)并不是所有的都收斂到解x*!

上頁

下頁

對于給定方程組x=Bx+f,設有唯一解x*,則x*=Bx*+f.(1.5)又設x(0)為任取的初始向量,按下述公式構造向量序列x(k+1)=Bx(k)+f,k=0,1,2,.(1.6)其中k表示迭代次數(shù).定義1(1)對于給定的方程組x=Bx+f,用公式(1.6)逐步代入求近似解的方法稱為迭代法(或稱為一階定常迭代法，這里B與k無關).B稱為迭代矩陣.

(2)假使limx(k)(k→)存在(記為x*),稱此迭代法收斂,顯然x*就是方程組的解,否則稱此迭代法發(fā)散.上頁下頁

由上述探討，需要研究{x(k)}的收斂性.引進誤差向量

(k1)x(k1)x,由(1.6)減去(1.5)式，得(k+1)=B(k)(k=0,1,2,),遞推得

(k)B(k1)Bk(0).要考察{x(k)}的收斂性，就要研究B在什么條件下有l(wèi)imε(k)=0(k→∞),亦即要研究B滿足什么條件時有Bk→0(零矩陣)(k→∞).上頁下頁

6.1.2向量序列與矩陣序列的極限定義2設向量序列{x(k)}Rn,x(k)=(x1(k),…,xn(k))T,假使存在x=(x1,x2,…,xn)TRn,使

limxk

(k)i

xi,

i1,2,,n.limx(k)x.,記作k

則稱向量序列{x(k)}收斂于x顯然，limxk(k)

xlimxk

(k)

x0.

其中為任一向量范數(shù).

上頁

下頁

定義3設矩陣序列Ak={aij(k)}Rnn及A={aij}Rnn,假使n2個數(shù)列極限存在，且有

i,j1,2,,n.k則稱矩陣序列{Ak}收斂于A,記作limAkA.lima(k)ij

aij,

k1222A,A,,Ak2000且設||1,考察其極限.解顯然，當||1時，則有

例2設有矩陣序列

k

kk1,.k

00limAklimA00.kkk

上頁

下頁

矩陣序列極限概念可以用矩陣算子范數(shù)來描述.

定理1

limAkAlimAkA0,kk

其中為矩陣的任意一種算子范數(shù).證明顯然有

limAkAlimAkA0.kk

再利用矩陣范數(shù)的等價性,可證定理對其它范數(shù)成立.

上頁

下頁

定理2limAk=0的充分必要條件是

limAkx0,xRn.k

(1.7)

證明對任一種矩陣范數(shù)的附屬范數(shù)有

AkxAkx.若limAk=0,則lim||Ak||=0,故對一切xRn有l(wèi)im||Akx||=0.故(1.7)式成立.反之，若(1.7)式成立，取x為第j個坐標向量ej,則若limAkej=0,表示Ak的第j列元素極限均為零，當j=1,2,…,n時就證明白limAk=0.證畢.下面探討一種與迭代法(1.6)有關的矩陣序列的收斂性,這種序列由矩陣的冪構成,即{Bk},其中BRnn.上頁下頁

定理3設BRnn,則證明3個命題等價：(1)limBk=0;(2)(B)1;

(3)至少存在一種附屬的矩陣范數(shù)||,使||B||1.||證明(1)=(2)用反證法，假定B有一個特征值,滿足||1,則存在x0,使Bx=x,由此可得||Bkx||=||k||x||,當k→時{Bkx}不收斂于零向量.由定理2可知(1)不成立，從而知||1,即(2)成立.(2)=(3)根據(jù)第5章定理18,對任意0,存在一種附屬范數(shù)||,使||B||(B)+,由(2)有(B)1,適||選中取0,可使||B||1,即(3)成立.(3)=(1)由(3)給出的矩陣范數(shù)||B||1,由于||Bk||||B||k,可得lim||Bk||=0,從而有l(wèi)imBk=0.上頁下頁

定理4設BRnn,||||為任一種矩陣范數(shù)，則

limBk

1kk

(B).

(1.8)

(B)(Bk)kBkk.1另一方面對任意0,記B(B)B.Bk

證明由第5章定理18,對一切k有11

顯然有(B)1.由定理3有l(wèi)imBk=0,所以存在正整數(shù)N=N(),使當kN時，

即kN時有

(B)B

(B)1kk

Bk

k

1.

(B).上頁下頁

由的任意性即得定理結論.

6.1.3迭代法及其收斂性設有線性方程組Ax=b,其中，A=(aij)∈Rnn為非奇異矩陣，下面研究如何建立解Ax=b的迭代法.將A分裂為

A=M-N.

(1.9)

其中，M為可選擇的非奇異矩陣，且使Mx=d簡單求解，一般選擇A的某種近似，稱M為分裂矩陣.

上頁

下頁

于是，求解Ax=b轉化為求解Mx=Nx+b,即求解

Axb求解xMNxMb.也就是求解線性方程組x=Bx+f.從而可構造一階定常迭代法：(1.10)

1

1

x(0)(初始向量),(k1)xBx(k)f(k0,1,,),

(1.11)

其中B=M-1N=M-1(M-A)=I-M-1A,f=M-1b.稱B=I-M-1A為迭代法的迭代矩陣，選取M矩陣，就得到解Ax=b的各種迭代法.下面給出迭代法(1.11)式收斂的充分必要條件.上頁下頁

定理5(一階定常迭代法的基本定理)給定線性方程組(1.10)及一階定常迭代法(1.11)式，對任意選取初始向量x(0),迭代法(1.11)式收斂的充分必要條件是矩陣B的譜半徑(B)1.證明(=)設(B)1,易知Ax=f(其中A=I-B)有唯一解，記為x*,則x*=Bx*+f.誤差向量(k)=x(k)-x*=Bk(0),(0)=x(0)-x*.由設(B)1,應用定理3,有l(wèi)imBk=0.于是對任意x(0)有l(wèi)im(k)=0,limx(k)=x*.(=)設對任意x(0)有l(wèi)imx(k)=x*,其中x(k+1)=Bx(k)+f.顯然,極限x*是線性方程組(1.10)的解,且對任意x(0)有(k)=x(k)-x*=Bk(0)→0(k→).由定理2知limBk=0,再由定理3,即得(B)1.上頁下頁

例3考察線性方程組(1.2)給出的迭代法(1.4)式的收斂性.解先求迭代矩陣B0的特征值.由特征方程

38

det(IB0)可得3

41112

14

14111

0.

det(IB0)0.0340909090.0397727270.

解得

10.3082,20.1541i0.3245,20.1541i0.3245.

10.30821,220.35921.即(B0)1,所以用迭代法(1.4)式解(1.2)是收斂的.上頁下頁

例4考察用迭代法解線性方程組x(k+1)=Bx(k)+f.

025的收斂性，其中B30,f5.解特征方程為det(I-B)=2-6=0,特征值

1,26,即(B)1,這說明用迭代法解此方程組不收斂.迭代法的基本定理在理論上是重要的，由于(B)||B||,下面利用矩陣B的范數(shù)建立判別迭代法收斂的充分條件.上頁下頁

定理6(迭