線性方程組的迭代法

線性方程組的迭代法2023/4/231第1頁，共87頁，2023年，2月20日，星期六其中A為非奇異矩陣.其解法大致分為直接法(第六章)和迭代法(第五章)兩大類.對線性方程組Ax=b，(1.1)5.1迭代公式的建立在用直接法解線性方程組時要對系數(shù)矩陣不斷變換.如果方程組的階數(shù)很高,則運算量將會很大并且大量占用計算機資源，因此對線性方程組要求找尋更經(jīng)濟、適用的數(shù)值解法.2023/4/232第2頁，共87頁，2023年，2月20日，星期六當A為大型稀疏矩陣方程組(A的階數(shù)n很大，但零元素較多),利用迭代法求解是合適的.本節(jié)將介紹迭代法的一些基本理論及雅可比迭代法，高斯-賽德爾迭代法，超松弛迭代法，而超松弛迭代法應用很廣泛。2023/4/233第3頁，共87頁，2023年，2月20日，星期六迭代法：從一個初始向量出發(fā)，按照一定的迭代格式，構造出一個趨向于真解的無窮序列迭代解法是目前求解大規(guī)模線性方程組的主要方法.只需存儲系數(shù)矩陣中的非零元素運算量不超過O(kn2),其中k為迭代步數(shù)

(1)迭代格式的建立(3)誤差估計和收斂速度研究內(nèi)容：(2)收斂性判斷下面舉一簡例，以便了解迭代法的思想.2023/4/234第4頁，共87頁，2023年，2月20日，星期六

例1求解方程組記為Ax=b，其中此方程組的精確解是x*=(3,2,1)T.現(xiàn)將改寫為2023/4/235第5頁，共87頁，2023年，2月20日，星期六或?qū)憺閤=B0x+f，其中2023/4/236第6頁，共87頁，2023年，2月20日，星期六任取初始值，例如取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)，反復利用這個計算程序，得到一向量序列和一般的計算公式(迭代公式)2023/4/237第7頁，共87頁，2023年，2月20日，星期六簡寫為x(k+1)=B0x(k)

+f，其中k表示迭代次數(shù)(k=0,1,2,).迭代到第10次有2023/4/238第8頁，共87頁，2023年，2月20日，星期六迭代法的一個突出優(yōu)點就是算法簡單，因而編制程序比較容易。但是迭代法也有缺點,它要求方程組的系數(shù)矩陣具有某種特殊性質(zhì)，以保證迭代過程的收斂性.發(fā)散的迭代過程是沒有實用價值的.這種方式就稱為迭代法.以上過程稱為迭代過程.迭代法產(chǎn)生一個序列如果其極限存在,即則稱迭代法收斂,否則稱為發(fā)散.從此例看出，由迭代法產(chǎn)生的向量序列x(k)逐步逼近方程組的精確解x*=(3,2,1)T.即有2023/4/239第9頁，共87頁，2023年，2月20日，星期六對于任何一個方程組x=Bx+f(由Ax=b變形得到的等價方程組)，由迭代法產(chǎn)生的向量序列x(k)是否一定逐步逼近方程組的解x*呢？回答是不一定.例如：考慮用迭代法解下述方程組

x(k)并不是所有的都收斂到解x*！2023/4/2310第10頁，共87頁，2023年，2月20日，星期六對于給定方程組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ā)散.2023/4/2311第11頁，共87頁，2023年，2月20日，星期六由上述討論，需要研究{x(k)}的收斂性.引進誤差向量由(1.6)減去(1.5)式，得ε(k+1)=Bε(k)(k=0,1,2,)，遞推得要考察{x(k)}的收斂性，就要研究B在什么條件下有l(wèi)imε(k)=0(k→∞)，亦即要研究B滿足什么條件時有Bk→0(零向量)(k→∞).2023/4/2312第12頁，共87頁，2023年，2月20日，星期六其中，A=(aij)∈Rn×n為非奇異矩陣，下面研究任何建立Ax=b的各種迭代法.設線性方程組Ax=b，(1.7)其中，M為可選擇的非奇異矩陣，且使Mx=d容易求解，一般選擇A的某種近似，稱M為分裂矩陣.將A分裂為A=M-N.(1.8)1迭代公式的矩陣表示2023/4/2313第13頁，共87頁，2023年，2月20日，星期六于是，求解Ax=b轉(zhuǎn)化為求解Mx=Nx+b，即求解可構造一階定常迭代法其中B=M-1N=M-1(M-A)=I-M-1A，f=M-1b.稱B=I-M-1A為迭代法的迭代矩陣，選取M矩陣，就得到解Ax=b的各種迭代法.設aii0(i=1,2,,n)，并將A寫成三部分2023/4/2314第14頁，共87頁，2023年，2月20日，星期六2023/4/2315第15頁，共87頁，2023年，2月20日，星期六即A=D-L-U2023/4/2316第16頁，共87頁，2023年，2月20日，星期六2雅可比(Jacobi)迭代公式設aii0(i=1,2,,n)，選取M為A的對角元素部分,即選取M=D(對角陣)，A=D-N，由(1.9)式得到解方程組Ax=b的雅可比(Jacobi)迭代法.又稱簡單迭代法.其中B=I-D-1A=D-1(L+U)=J,f=D-1b.稱J為解Ax=b的雅可比迭代法的迭代矩陣.2023/4/2317第17頁，共87頁，2023年，2月20日，星期六于是雅可比迭代法可寫為矩陣形式其Jacobi迭代矩陣為2023/4/2318第18頁，共87頁，2023年，2月20日，星期六下面給出雅可比迭代法(1.10)的分量計算公式,記由雅可比迭代法(1.10)有每一個分量寫出來為即當aii0時，有2023/4/2319第19頁，共87頁，2023年，2月20日，星期六等價方程組其中

aii(i)0(i=1,2,,n)即由方程組Ax=b得到的2023/4/2320第20頁，共87頁，2023年，2月20日，星期六建立的雅可比迭代格式為2023/4/2321第21頁，共87頁，2023年，2月20日，星期六于是，解Ax=b的雅可比迭代法的計算公式為由(1.11)式可知，雅可比迭代法計算公式簡單，每迭代一次只需計算一次矩陣和向量的乘法且計算過程中原始矩陣A始終不變.2023/4/2322第22頁，共87頁，2023年，2月20日，星期六3高斯－賽德爾迭代法在Jacobi

迭代中，計算xi(k+1)(2in)時，使用xj(k+1)代替xj(k)(1ji-1)，即有建立迭代格式2023/4/2323第23頁，共87頁，2023年，2月20日，星期六或縮寫為稱為高斯—塞德爾(Gauss—Seidel)迭代法.其Gauss—Seidel迭代矩陣為BG=(D-L)-1U于是高斯—塞德爾迭代法可寫為矩陣形式2023/4/2324第24頁，共87頁，2023年，2月20日，星期六這就是說，選取分裂矩陣M為A的下三角部分,即選取M=D-L(下三角陣)，A=M-N，由(1.9)式得到解Ax=b的高斯—塞德爾(Gauss—Seidel)迭代法.其中B=I-(D-L)-1A=(D-L)-1U=G,f=(D-L)-1b.稱矩陣G=(D-L)-1U為解Ax=b的高斯—塞德爾迭代法的迭代矩陣.2023/4/2325第25頁，共87頁，2023年，2月20日，星期六由高斯—塞德爾迭代法(1.12)有每一個分量寫出來為即當aii0時，有(與前面一樣的式子)或2023/4/2326第26頁，共87頁，2023年，2月20日，星期六于是，解Ax=b的高斯—塞德爾迭代法的計算公式為或2023/4/2327第27頁，共87頁，2023年，2月20日，星期六

雅可比迭代法不使用變量的最新信息計算xi(k+1)，而由高斯—塞德爾迭代公式(1.13)可知，計算x(k+1)的第i個分量xi(k+1)時，利用了已經(jīng)計算出的最新分量xj(k+1)(j=1,2,,i-1).

可看作雅可比迭代法的一種改進.由(1.13)可知，高斯—塞德爾迭代公式每迭代一次只需計算一次矩陣與向量的乘法.

算法(高斯—塞德爾迭代法)見書p160.2023/4/2328第28頁，共87頁，2023年，2月20日，星期六

例2用高斯—塞德爾迭代法解例1的方程組(1.2).

解用高斯—塞德爾迭代公式：取x(0)=(0,0,0)T.迭代到第7次有2023/4/2329第29頁，共87頁，2023年，2月20日，星期六由此例可知，用高斯—塞德爾迭代法，雅可比迭代法解線性方程組(1.2)(且取x(0)=0)均收斂，而高斯—塞德爾迭代法比雅可比迭代法收斂較快(即取相同的x(0)，達到同樣精度所需迭代次數(shù)較少)，但這結論只當A滿足一定條件時才是對的.2023/4/2330第30頁，共87頁，2023年，2月20日，星期六

例3用雅可比迭代法解方程組

解：Jacobi

迭代格式為2023/4/2331第31頁，共87頁，2023年，2月20日，星期六kx1(k)x2(k)x3(k)10.720.830.8420.9711.071.15…………111.0999931.1999931.299991121.0999981.1999981.299997取x(0)=(0,0,0)T

計算結果如下：2023/4/2332第32頁，共87頁，2023年，2月20日，星期六

解：Gauss-Seidel

迭代格式為

例4用Gauss—Seidel迭代法解上題.2023/4/2333第33頁，共87頁，2023年，2月20日，星期六取x(0)=(0,0,0)T

計算結果如下：kx1(k)

x2(k)x3(k)10.720.9021.1644…………81.0999981.1999991.32023/4/2334第34頁，共87頁，2023年，2月20日，星期六4解大型稀疏線性方程組的逐次超松弛法(SOR方法)我們?nèi)?gt;0為松弛因子，建立迭代格式如下即2023/4/2335第35頁，共87頁，2023年，2月20日，星期六或改寫為稱為逐次超松弛迭代法(SuccessiveOverRelaxationMethod),

，簡稱SOR方法.(1.14)2023/4/2336第36頁，共87頁，2023年，2月20日，星期六(1)顯然，當=1時即為Gauss—Seidel迭代法.(2)SOR方法每迭代一次主要運算量是計算一次矩陣與向量的乘法.(3)當>1時，稱為超松弛法；當<1時，稱為低松弛法.(4)在計算機實現(xiàn)時可用控制迭代終止，或用控制迭代終止.2023/4/2337第37頁，共87頁，2023年，2月20日，星期六

SOR迭代法是Gauss—Seidel迭代法的一種修正，可由下述思想得到.設已知x(k)及已計算x(k+1)的分量xj(k+1)(j=1,2,,i-1).(1)首先用Gauss—Seidel迭代法定義輔助量,(2)再由與加權平均定義，即將(1.15)代入(1.16)得到解Ax=b的SOR迭代(1.13)式.2023/4/2338第38頁，共87頁，2023年，2月20日，星期六記筆記5.2向量和矩陣的范數(shù)為了研究線性方程組近似解的誤差估計和迭代法的收斂性,有必要對向量及矩陣的“大小”引進某種度量----范數(shù)的概念.向量范數(shù)是用來度量向量長度的,它可以看成是二、三維解析幾何中向量長度概念的推廣.用Rn表示n維實向量空間.5.2向量和矩陣的范數(shù)2023/4/2339第39頁，共87頁，2023年，2月20日，星期六基本概念:

“范數(shù)”是對向量和矩陣的一種度量,實際上是二維和三維向量長度概念的一種推廣.數(shù)域:數(shù)的集合,對加法和乘法封閉

線性空間:可簡化為向量的集合,對向量的加法和數(shù)量乘法封閉,也稱為向量空間

二維向量和三維向量都可以度量其大小和長度。高維向量的"長度"能否定義呢?2023/4/2340第40頁，共87頁，2023年，2月20日，星期六定義1

對任一向量XRn,按照一定規(guī)則確定一個實數(shù)與它對應,該實數(shù)記為||X||,若||X||滿足下面三個性質(zhì):(1)||X||0；||X||=0當且僅當X=0；(2)對任意實數(shù)，||X||=||||X||；對任意向量YRn，||X+Y||||X||+||Y||

則稱該實數(shù)||X||為向量X的范數(shù).2023/4/2341第41頁，共87頁，2023年，2月20日，星期六在Rn中，常用的幾種范數(shù)有：其中x1,x2,…,xn分別是X的n個分量。以上定義的范數(shù)分別稱為1-范數(shù)，2-范數(shù)和-范數(shù)可以驗證它們都是滿足范數(shù)性質(zhì)的，其中是由內(nèi)積導出的向量范數(shù)。2023/4/2342第42頁，共87頁，2023年，2月20日，星期六當不需要指明使用哪一種向量范數(shù)時，就用記號||.||泛指任何一種向量范數(shù)。有了向量的范數(shù)就可以用它來衡量向量的大小和表示向量的誤差。設x*為Ax=b的精確解，x為其近似解，則其絕對誤差可表示成||x-x*||，其相對誤差可表示成或2023/4/2343第43頁，共87頁，2023年，2月20日，星期六2023/4/2344第44頁，共87頁，2023年，2月20日，星期六例1證明對任意同維向量x,y

有

證：

即2023/4/2345第45頁，共87頁，2023年，2月20日，星期六例2設x=(1,0,-1,2)T,計算

解:=1+0+|-1|+2=42023/4/2346第46頁，共87頁，2023年，2月20日，星期六定理1對于任意向量x,有證:∵

∴即

當p→∞，

∴2023/4/2347第47頁，共87頁，2023年，2月20日，星期六定義2(向量序列的極限)設為中的一向量序列，,記.如果(i=1,2,…,n)，則稱收斂于向量，記為

定理2（向量范數(shù)的等價性）設為上任意兩種向量范數(shù),則存在常數(shù)C1,C2>0,使得對任意恒有（證:略）

2023/4/2348第48頁，共87頁，2023年，2月20日，星期六定理3

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

2023/4/2349第49頁，共87頁，2023年，2月20日，星期六例3求下列向量的各種常用范數(shù)解:1*4≤9≤9/4*4=92023/4/2350第50頁，共87頁，2023年，2月20日，星期六定義3

（矩陣的范數(shù)）如果矩陣的某個

非負的實值函數(shù)，滿足則稱是上的一個矩陣范數(shù)(或模).

2023/4/2351第51頁，共87頁，2023年，2月20日，星期六定義4（矩陣的算子范數(shù)）設n維向量X和n階方陣A，當給定一種向量范數(shù)||X||時，則定義

為矩陣的范數(shù)，并稱為矩陣的算子范數(shù)。矩陣范數(shù)定義的另一種方法:從定義可以看出，矩陣范數(shù)和向量范數(shù)密切相關。2023/4/2352第52頁，共87頁，2023年，2月20日，星期六常用的矩陣范數(shù)--------(5)--------(6)--------(7)矩陣算子范數(shù)：（誘導范數(shù)）由向量范數(shù)||·||p

導出關于矩陣A

Rnn

的p范數(shù):2023/4/2353第53頁，共87頁，2023年，2月20日，星期六矩陣范數(shù)的性質(zhì)可由向量范數(shù)定義直接驗證.(1)設A≠0,x≠0,使Ax≠0,根據(jù)向量范數(shù)的性質(zhì)Ax>0,所以>0x≠0,使Ax=0,則=0當A=0時,2023/4/2354第54頁，共87頁，2023年，2月20日，星期六∴(2)根據(jù)向量范數(shù)的性質(zhì)2023/4/2355第55頁，共87頁，2023年，2月20日，星期六(3)2023/4/2356第56頁，共87頁，2023年，2月20日，星期六例4計算方陣

的三種范數(shù)

解先計算

所以,從而

2023/4/2357第57頁，共87頁，2023年，2月20日，星期六例5求矩陣A的各種常用范數(shù)解:由于2023/4/2358第58頁，共87頁，2023年，2月20日，星期六特征方程為2023/4/2359第59頁，共87頁，2023年，2月20日，星期六容易計算計算較復雜對矩陣元素的變化比較敏感使用最廣泛性質(zhì)較好使用最廣泛2023/4/2360第60頁，共87頁，2023年，2月20日，星期六5.3迭代過程的收斂性1迭代收斂的充分條件其中，A=(aij)∈Rn×n為非奇異矩陣，記x*為(3.1)精確解，且設有等價的方程組設線性方程組Ax=b，(3.1)于是設有解Ax=b的一階定常迭代法2023/4/2361第61頁，共87頁，2023年，2月20日，星期六有意義的問題是：迭代矩陣B滿足什么條件時，由迭代法產(chǎn)生的向量序列{x(k)}收斂到x*.引進誤差向量由(3.3)式減(3.2)得到誤差向量的遞推公式由5.1節(jié)可知，研究迭代法(3.3)收斂性問題就是要研究迭代矩陣B滿足什么條件時，有.2023/4/2362第62頁，共87頁，2023年，2月20日，星期六

定義1設有矩陣序列Ak=(aij(k))∈Rn×n

及A=(aij)∈Rn×n，如果n2個數(shù)列極限存在且有則{Ak}稱收斂于A，記為limAk=A(k→∞).

例1設有矩陣序列{Ak},其中Ak=Bk,而且設|λ|<1，考查矩陣序列極限.

解顯然,當|λ|<1時,則有2023/4/2363第63頁，共87頁，2023年，2月20日，星期六矩陣序列極限概念可以用矩陣算子范數(shù)來描述.

定理1其中||·||為矩陣的任意一種算子范數(shù).

證明顯然有再由矩陣范數(shù)的等價性,則定理對其它算子范數(shù)亦對.

定理2

證明作為練習.2023/4/2364第64頁，共87頁，2023年，2月20日，星期六

定理3(迭代法收斂的充分條件)設有方程組x=Bx+f，B=(bij)∈Rn×n，及一階定常迭代法x(k+1)=Bx(k)+f.如果有B的某種算子范數(shù)||B||=q<1，則(1)迭代法收斂，即對任取x(0)有2023/4/2365第65頁，共87頁，2023年，2月20日，星期六2對角占優(yōu)方程組在科學及工程計算中，要求解方程組Ax=b，其矩陣A常常具有某些特性.例如，A具有對角占優(yōu)性質(zhì)或A為不可約陣，或A是對稱正定陣，下面討論用基本迭代法解這些方程組的收斂性.2023/4/2366第66頁，共87頁，2023年，2月20日，星期六

定義2(對角占優(yōu)陣)設A=(aij)n×n

.(1)如果A的元素滿足稱A為嚴格(按行)對角占優(yōu)陣.(2)如果A的元素滿足且上式至少有一個不等式成立，稱A為弱(按行)對角占優(yōu)陣.2023/4/2367第67頁，共87頁，2023年，2月20日，星期六

定義3(可約與不可約矩陣)設A=(aij)n×n

(n≥2)，如果存在置換陣P使其中A11為r階方陣，A22為n-r階方陣(1≤r≤n)，則稱A為可約矩陣.否則，如果不存在這樣置換陣P使(3.6)式成立，則稱A為不可約矩陣.

A為可約矩陣意即A可經(jīng)過若干行列重排化為(3.6)或Ax=b可化為兩個低階方程組求解(如果A經(jīng)過兩行交換的同時進行相應兩列的交換，稱對A進行一次行列重排).2023/4/2368第68頁，共87頁，2023年，2月20日，星期六

事實上，由Ax=b可化為PTAP(PTx)=PTb.于是，求解Ax=b化為求解且記,其中yi,di為r維向量.由上式第2個方程組求出y2,再代入第1個方程組求出y1.

顯然，如果A所有元素都非零，則A為不可約陣.2023/4/2369第69頁，共87頁，2023年，2月20日，星期六

例7設有矩陣則A,B都是不可約矩陣.2023/4/2370第70頁，共87頁，2023年，2月20日，星期六

定理4(對角占優(yōu)定理)如果A=(aij)n×n為嚴格對角占優(yōu)矩陣或A為不可約弱對角占優(yōu)矩陣，則A為非奇異矩陣.

證明只就A為嚴格對角占優(yōu)矩陣證明此定理.采用反證法，如果det(A)=0，則Ax=b有非零解，記為x=(x1,x2,,xn)T，則.

由齊次方程組第k個方程則有即這與假設矛盾，故det(A)≠0.2023/4/2371第71頁，共87頁，2023年，2月20日，星期六

定理5設方程組Ax=b，如果(1)A為嚴格對角占優(yōu)陣，則解Ax=b的Jacobi迭代法,Gauss-Seidel

迭代法均收斂.(2)A為弱對角占優(yōu)陣，且A為不可約矩陣,則解Ax=b的Jacobi迭代法,Gauss-Seidel

迭代法均收斂.

證明只證(1)，(2)作為練習.

因為A是嚴格對角占優(yōu)陣，所以aii≠0(i=1,,n).則||J||<1，所以Jacobi迭代法收斂.Jacobi迭代陣2023/4/2372第72頁，共87頁，2023年，2月20日，星期六下面證明Gauss—Seidel迭代法收斂.由G=(D-L)-1U，得下面證明||<1.若不然,即||1,則由于所以2023/4/2373第73頁，共87頁，2023年，2月20日，星期六即矩陣是嚴格對角占優(yōu)矩陣，故可逆，這與(*)

式矛盾，所以||<1,從而(G)<1，即Gauss—Seidel迭代法收斂.2023/4/2374第74頁，共87頁，2023年，2月20日，星期六定理6若A為正定矩陣，則方程組Ax=b的Gauss-Seidel迭代法收斂.證因為A=D-L-LT，G=(D-L)-1LT，設為G

的特征值，y為對應的特征(復)向量，即

(D-L)-1LTy=y，LTy=(D-L)y，則內(nèi)積(LTy,y)=((D-L)y,y).從而

因為A正定，所以D正定，故(Dy,y)=>0.2023/4/2375第75頁，共87頁，2023年，2月20日，星期六所以||<1,從而(G)<1,故Gauss-Seidel迭代法收斂.令-(Ly,y)=a+ib，則由復向量內(nèi)積的性質(zhì)有下面研究對于解方程組Ax=b的SOR方法中松弛因子ω在什么范圍內(nèi)取值，SOR方法才可能收斂.2023/4/2376第76頁，共87頁，2023年，2月20日，星期六定理7(SOR方法收斂的必要條件)設解方程組Ax=b的SOR迭代法收斂，則0<<2.

證

A=D-L-U，L=(D-L)-1[(1-)D+U],由于SOR迭代法收斂，則(L)<1.設迭代矩陣L的特征值為i

(i=1,,n)，則有det(L)<|12n|<[(B

)]n<1.于是所以|1-|<1，即0<<2.2023/4/2377第77頁，共87頁，2023年，2月20日，星期六

定理7說明解Ax=b的SOR迭代法，只有在(0,2)范圍內(nèi)取松弛因子，才可能收斂.定理8(SOR方法收斂的充分條件)設有方程組Ax=b，如果：(1)A為對稱正定矩陣，A=D-L-LT;(2)0<<2.則解方程組Ax=b的SOR迭代法收斂.

證在上述假定下，設迭代矩陣L的任一特征值為，只要證明||<1即可.2023/4/2378第78頁，共87頁，2023年，2月20日，星期六事實上，設y為對應的Lω的特征向量，即亦即有內(nèi)積則

因為A正定，所以D正定，記(Dy,y)=>0.令-(Ly,y)=a+ib，則由復向量內(nèi)積的性質(zhì)有2023/4/2379第79頁，共87頁，2023年，2月20日，星期六當0<<2時，有(分子減分母)即L的任一特征值滿足||<1,故SOR迭代法收斂.2023/4/2380第80頁，共87頁