數(shù)值計算方法與算法

關于數(shù)值計算方法與算法

求解線性方程組Ax=y，可用直接法。當A為稀疏矩陣時，直接法將破壞矩陣A的稀疏性。

我們可以對線性方程組進行等價變換，構造出等價方程組x=Mx+g,由此構造迭代關系式例如，分解A=N-P，則第2頁,共47頁，2024年2月25日，星期天迭代法：構造一個向量序列{x(k)}

，使其收斂到某個極限向

量x*，即則x*就是線性方程組的解。常用迭代方法：

雅可比迭代，高斯-賽德爾迭代，松弛迭代等。

第3頁,共47頁，2024年2月25日，星期天6.1

雅可比迭代6.1.1雅可比迭代格式迭代格式線性方程組Ax=y，即

第4頁,共47頁，2024年2月25日，星期天若aii≠0,i=1,2,…,n,（6.1）可變?yōu)橛泟t第5頁,共47頁，2024年2月25日，星期天寫成矩陣形式或簡記為對任意初始向量構造迭代格式：(6.2)是稱為簡單迭代或雅可比迭代。第6頁,共47頁，2024年2月25日，星期天

雅可比迭代矩陣

記所以稱為雅可比迭代矩陣，是常數(shù)項向量。第7頁,共47頁，2024年2月25日，星期天如果通過(6.2)構造的迭代序列{x(k)}收斂，即則x*為Ax=y的解，即Ax*=y。事實上，對(6.2)取極限得第8頁,共47頁，2024年2月25日，星期天迭代格式的收斂性引理6.1(線性代數(shù)定理)

設矩陣序列則（證明見關治和陳景良編《數(shù)值計算方法》P410~412）定理6.1設迭代格式為由初始向量x(0)產(chǎn)生的向量序列{x(k)}收斂的充分必要條件是證明必要性（

）設則由（6.3）得第9頁,共47頁，2024年2月25日，星期天(6.3)-(6.4)得設第k次迭代的誤差記為充分性（

）設ρ(M)<1,證{x(k)}收斂。如果ρ(M)<1，則I-M為非奇異矩陣。事實上，因為ρ(M)<1，λi<1，因此λ=1不是M的特征值，即第10頁,共47頁，2024年2月25日，星期天所以方程組(I-M)x=f有惟一解x*,滿足(I-M)x*=f，即x*=Mx*+f。于是由引理6.1知，第11頁,共47頁，2024年2月25日，星期天例6.1

設系數(shù)矩陣為

判定雅可比迭代格式的收斂性。解雅可比迭代矩陣為特征方程為

第12頁,共47頁，2024年2月25日，星期天

實際計算中，M的特征值難于計算，因此也難于判斷。由于可用作為判斷收斂的條件。定理6.2若

則由迭代格式

確定的迭代序列{x(k)}收斂，且有誤差估計式第13頁,共47頁，2024年2月25日，星期天證明又因為第14頁,共47頁，2024年2月25日，星期天分別把（c）和（d）代入（e）即得證（a）（b）。注：是收斂的充分條件，但不是必要條件。因為收斂，不能推出。例如第15頁,共47頁，2024年2月25日，星期天定義6.1

如果A的元素滿足并且至少有一個不等式嚴格成立，則稱A為行對角占優(yōu)矩陣；如果A的元素滿足則稱A為嚴格行對角占優(yōu)矩陣。同樣可以定義列對角占優(yōu)矩陣和嚴格列對角占優(yōu)矩陣。引理6.2

（對角優(yōu)勢定理）(3)

若A為嚴格對角占優(yōu)矩陣，則A非奇異，且aii≠0,i=1,2,…,n.第16頁,共47頁，2024年2月25日，星期天證明

由線性代數(shù)知識知，det(A)≠0Ax=0只有零解。

反證法假定det(A)=0

，則Ax=0有非零解，記為第17頁,共47頁，2024年2月25日，星期天

當方程組的系數(shù)矩陣為嚴格對角占優(yōu)時，關于雅可比迭代我們有下面的定理。定理6.3當系數(shù)矩陣為嚴格對角占優(yōu)時，雅可比迭代收斂。證明方法一：根據(jù)嚴格對角占優(yōu)矩陣的定義。雅可比迭代矩陣：第18頁,共47頁，2024年2月25日，星期天方法二：反證法。

因為A為嚴格對角占優(yōu)矩陣，由引理6.2知，aii≠0.

第19頁,共47頁，2024年2月25日，星期天第20頁,共47頁，2024年2月25日，星期天

雅可比迭代算法算法描述：1.輸入系數(shù)矩陣A和常數(shù)項向量y；2.形成雅可比迭代矩陣B和向量g第21頁,共47頁，2024年2月25日，星期天3.賦初始值

第22頁,共47頁，2024年2月25日，星期天4.實現(xiàn)迭代5.輸出方程組的解x2[i]，i=1,2,…,n.第23頁,共47頁，2024年2月25日，星期天6.2

高斯-塞德爾(Gauss-Seidel)迭代高斯-塞德爾迭代的計算在雅可比迭代(6.4)的迭代過程中，可用新求出的x(k+1)的分量來代替x(k)的分量參與計算，直到用x(k+1)的前n-1分量代替x(k)

的前n-1個分量求出為止，即可由（6.5）得到高斯-塞德爾迭代：算法第24頁,共47頁，2024年2月25日，星期天令B=L+U，其中則高斯-賽德爾迭代可寫成矩陣形式或寫成其中，為高斯-塞德爾迭代矩陣，第25頁,共47頁，2024年2月25日，星期天

高斯-塞德爾迭代的收斂性

由定理6.1知，高斯-塞德爾迭代收斂的充分必要條件為也可以利用條件來判斷高斯-塞德爾迭代收斂。定理6.4當系數(shù)矩陣為嚴格對角占優(yōu)時，高斯-塞德爾迭代收斂。

證明類似于定理6.3的證明。反證法。第26頁,共47頁，2024年2月25日，星期天第27頁,共47頁，2024年2月25日，星期天第28頁,共47頁，2024年2月25日，星期天定理6.5當系數(shù)矩陣A為正定矩陣，高斯-塞德爾迭代收斂。證明第29頁,共47頁，2024年2月25日，星期天第30頁,共47頁，2024年2月25日，星期天例6.2

設系數(shù)矩陣為

判定高斯-塞德爾迭代格式的收斂性。解高斯-塞德爾迭代矩陣為其中，

第31頁,共47頁，2024年2月25日，星期天第32頁,共47頁，2024年2月25日，星期天

高斯-塞德爾迭代算法

根據(jù)(6.6)，可以寫出高斯-塞德爾迭代的核心部分：記第33頁,共47頁，2024年2月25日，星期天第34頁,共47頁，2024年2月25日，星期天6.3

松弛迭代

高斯-塞德爾迭代為松弛迭代法是高斯-塞德爾迭代法的一種變化形式。令第35頁,共47頁，2024年2月25日，星期天其中，參數(shù)ω>0稱為松弛因子。將(6.9)變形為(6.9)或(6.10)稱為松弛迭代法。迭代矩陣為當0<ω<1時，稱為低松弛迭代；當1<ω<2時，稱為超松弛迭代；當ω=1時，即為高斯-塞德爾迭代。第36頁,共47頁，2024年2月25日，星期天

實際用計算機計算時，采用(6.9)的分量形式，即雅可比迭代、高斯-塞德爾迭代和松弛迭代均為單步線性迭代。第37頁,共47頁，2024年2月25日，星期天

松弛迭代的收斂性定理6.6松弛迭代收斂的必要條件是0<ω<2。即若松弛迭代收斂，則必有0<ω<2。證明松弛迭代矩陣其中，第38頁,共47頁，2024年2月25日，星期天

如果松弛迭代收斂，由定理6.1知，即Sω的所有特征值的絕對值均小于1。由特征方程的性質(zhì)得由（1）和（2）兩式得第39頁,共47頁，2024年2月25日，星期天定理6.7如果系數(shù)矩陣A為嚴格對角占優(yōu)，當松弛因子

時，則松弛迭代收斂。

證明類似于定理6.4。定理6.8

若A為對稱正定矩陣時，則當時，松弛迭代收斂。第40頁,共47頁，2024年2月25日，星期天

松弛迭代算法

基本上與高斯-塞德爾迭代算法相同。第41頁,共47頁，2024年2月25日，星期天6.4

逆矩陣的計算1.用初等變換2.

用伴隨矩陣3.用逆矩陣的定義：第42頁,共47頁，202