數(shù)值分析-第6章-線性代數(shù)方程組的迭代法PPT課件

1、6.1 迭代法的基本概念6.2 雅可比迭代法與高斯-塞德爾迭代法6.3 超松弛迭代法6.4 共軛梯度法第6章 解線性方程組的迭代法/* Iterative Techniques for Solving Linear Systems */7/17/20221第6章 解線性方程組的迭代法6.1 迭代法的基本概念 考慮線性方程組 （1.1）其中 為非奇異矩陣。 迭代法通常都可利用 中有大量零元素的特點(diǎn). 6.1.1 引言 當(dāng) 為低階稠密矩陣時，選主元消去法是有效方法. 迭代法適用于求解大型稀疏的線性方程組?；舅枷耄和ㄟ^構(gòu)造迭代格式產(chǎn)生迭代序列，由迭代序列來逼近原方程組的解。要解決的基本問題：1.

2、如何構(gòu)造迭代格式 2.迭代序列是否收斂7/17/20222第6章 解線性方程組的迭代法 6.1.2 向量序列與矩陣序列的極限 則稱向量序列 收斂于 ，記為 定義2 設(shè)有向量序列 如果存在 ，使其中 為任一種向量范數(shù). 定義3 設(shè)有矩陣序列 及 ,如果 個數(shù)列極限存在且有 則稱 收斂于 ，記為 7/17/20223第6章 解線性方程組的迭代法 解由于，當(dāng) 時，有 所以 例1 設(shè)有矩陣序列 且設(shè) ，考查其極限. 證明范數(shù)的等價性 定理1 其中為矩陣的任意一種算子范數(shù). 7/17/20224第6章 解線性方程組的迭代法 證明 定理2 的充分必要條件是（1.7）若 ，則 ，取 為第 個坐標(biāo)向量 ，則必

3、要性。故對一切 ，有 .表示 的第 列元素極限均為零，當(dāng) 時，就得到矩陣的算子范數(shù)滿足 充分性。7/17/20225第6章 解線性方程組的迭代法 定理3 設(shè) ，下面3個命題等價：（1） ；證明與迭代矩陣相關(guān)的結(jié)論（2） ；（3）至少存在一種從屬的矩陣范數(shù) ，使反證法。假定 有一個特征值 ，滿足 , 則存在 ，使 ，由此,由定理2知（1）不成立，從而知 ，即（2）成立.對任意 ，存在一種從屬范數(shù) ，使 ，適當(dāng)選擇 ，可使 ，即（3）成立.由矩陣范數(shù) ，可得 ，從而有又7/17/20226第6章 解線性方程組的迭代法 將 分裂為 （1.9）其中， 為可選擇的非奇異矩陣，且使 容易求解，稱 為分裂矩

4、陣. 即求解一階定常迭代法 （1.11）即（1.10）迭代的構(gòu)造其中 迭代矩陣7/17/20229第6章 解線性方程組的迭代法6.1.4 迭代法的收斂性 研究 的收斂性. 引進(jìn)誤差向量 得 ，遞推得 研究 在什么條件下有是初始誤差向量，是一個確定的值。對任意的初始向量 ，序列 收斂7/17/202210第6章 解線性方程組的迭代法 定理5 給定線性方程組 及一階定常迭代法 對任意選取初始向量 ，迭代法收斂的充要條件是矩陣 的譜半徑（1）迭代法是否收斂取決于迭代矩陣的譜半徑，與初始向量和常數(shù)項(xiàng)無關(guān)。（2）而對于同一個方程組，不同的迭代法對應(yīng)的迭代矩陣的譜半徑一般不會相同，因而收斂性也不同。注：注

5、：至少存在一種從屬的矩陣范數(shù) ，使迭代法收斂的判別準(zhǔn)則7/17/202211第6章 解線性方程組的迭代法 例2 求解方程組 （1.2）記為 , 方程組的精確解是 . 其中 現(xiàn)將(1.2)改寫為 （1.3）或?qū)憺?, 其中 7/17/202212第6章 解線性方程組的迭代法 任取初始值，例如取 . 得到新的值 （1.4）簡寫為 其中 表示迭代次數(shù) 迭代到第10次有 7/17/202213第6章 解線性方程組的迭代法 對于任何由 變形得到的等價方程組 ，迭代法產(chǎn)生的向量序列 是否都能逐步逼近方程組的解 ？ 如方程組構(gòu)造迭代法對任何的初始向量，得到的序列都不收斂.7/17/202214第6章 解線性

6、方程組的迭代法例3 考察線性方程組（1.2）給出的迭代法（1.4）的收斂性 （1.2）（1.4） 先求迭代矩陣 的特征值. 由特征方程可得解得所以迭代法（1.4）是收斂的.解7/17/202215第6章 解線性方程組的迭代法例4 考察用迭代法解方程組 的收斂性，解其中特征方程為特征根 即 . 這說明用此迭代法解此方程組不收斂. 7/17/202216第6章 解線性方程組的迭代法 定理6及一階定常迭代法 如果有 的某種算子范數(shù) ，則 (迭代法收斂的充分條件)設(shè)有方程組 (1) 迭代法收斂，即對任取 有 利用矩陣的范數(shù)判定迭代收斂只是一個充分條件，通常采用矩陣的1-范數(shù)、 -范數(shù)來判定。事后估計估

7、計迭代次數(shù)7/17/202217第6章 解線性方程組的迭代法 證明(2)反復(fù)遞推即得(2). (1) 是顯然的. 有 (3) 即 (3)反復(fù)利用(a)由關(guān)系式由 7/17/202218第6章 解線性方程組的迭代法 定理6只給出迭代法（1.11）收斂的充分條件，即使條件 對任何常用范數(shù)均不成立，迭代序列仍可能收斂. 例5 迭代法 ,其中 的各種范數(shù)均大于1，但 ，故此迭代法產(chǎn)生的迭代序列 是收斂的.7/17/202219第6章 解線性方程組的迭代法 下面考察迭代法的收斂速度.6.1.4 迭代法的收斂速度/* Rate of Average Convergence */ 假定迭代法是收斂的，即 ，

8、于是根據(jù)從屬范數(shù)定義，有 迭代 次后誤差向量 的范數(shù)與初始誤差向量 的范數(shù)之比的最大值.由 ，得7/17/202220第6章 解線性方程組的迭代法平均每次迭代誤差向量范數(shù)的壓縮率其中 ，可取 . 因?yàn)?，故 ，即（1.12）它表明迭代次數(shù) 與 成反比.若要求迭代 次后有由 兩邊取對數(shù)得越大越小收斂越快7/17/202221第6章 解線性方程組的迭代法 定義4 迭代法（1.11）的平均收斂速度定義為（1.13） 定義5 迭代法(1.11)的漸近收斂速度定義為 由 ，（1.14）（1.15）估計迭代次數(shù)所以 與迭代次數(shù)及 取何種范數(shù)無關(guān)，它反映了迭代次數(shù)趨于無窮時迭代法的漸近性質(zhì)。當(dāng) 越小時 越大

9、，迭代法收斂越快。7/17/202222第6章 解線性方程組的迭代法迭代矩陣 的譜半徑 即取 即可達(dá)到要求.若要求 ，則由于是幾種實(shí)用的基本迭代法應(yīng)用實(shí)例7/17/202223第6章 解線性方程組的迭代法（2.1）6.2.1 雅可比迭代法 6.2 雅可比迭代法與高斯-塞爾迭代法（1.1）設(shè) ，選取 (對角陣)，（2.2）解 的雅可比(Jacobi)迭代法其中 雅可比迭代法的迭代陣7/17/202224第6章 解線性方程組的迭代法記 雅可比迭代或 （2.2）其中 （2.3）解 的雅可比迭代法的分量計算公式 Jacobi方法是由方程組第i個方程解出xi得到的等價方程組。7/17/202225第6章

10、 解線性方程組的迭代法 每迭代一次只需計算一次矩陣和向量的乘法且計算過程中原始矩陣 始終不變. 6.2.2 高斯-塞德爾迭代法 分裂矩陣 取為 的下三角部分，即 (下三角陣)，解 的高斯-塞德爾(Gauss-Seidel)迭代法（2.4）其中 高斯-塞德爾迭代法的迭代陣研究高斯-塞德爾迭代法的分量計算公式. 7/17/202226第6章 解線性方程組的迭代法記 高斯-塞德爾迭代或 即 解 的高斯-塞德爾迭代法的分量計算公式 （2.5）雅可比迭代法的一種改進(jìn)7/17/202227第6章 解線性方程組的迭代法或 （2.6）7/17/202228第6章 解線性方程組的迭代法 迭代一次，這個算法需要的

11、運(yùn)算次數(shù)至多與矩陣 的非零元素的個數(shù)一樣多. 算法1 (高斯-塞德爾迭代法) 設(shè) ，其中 為非奇異矩陣且 本算法用高斯-塞德爾迭代法解 ，數(shù)組 開始存放 ,后存放 為最大迭代次數(shù). 7/17/202229第6章 解線性方程組的迭代法 例6 用高斯-塞德爾迭代法解線性方程組(1.2). 按高斯-塞德爾迭代公式迭代7次，得 ，（1.2）取 ， 且 解7/17/202230第6章 解線性方程組的迭代法方程組的精確解為x*=(1,1,1)T.J迭代法計算公式為取初始向量x(0)=(0,0,0)T,迭代可得計算結(jié)果列表如下:解例7 用J法和G-S法求解線性方程組7/17/202231第6章 解線性方程組

12、的迭代法可見,迭代序列逐次收斂于方程組的解, 而且迭代7次得到精確到小數(shù)點(diǎn)后兩位的近似解.kx1(k)x2(k)x3(k)x(k)-x*0123456701.41.110.9290.99061.011591.0002510.998236400.51.201.0550.96450.99531.0057951.000125501.41.110.9290.99061.011591.0002510.998236410.50.20.0710.03550.011590.0057950.0017636x (6) -x(5) =0.011339,x(7) x(6)=0.00566957/17/202232第6

13、章 解線性方程組的迭代法 同樣取初始向量x(0)=(0,0,0)T, 計算結(jié)果為 由計算結(jié)果可見,G-S迭代法收斂較快.取精確到小數(shù)點(diǎn)后兩位的近似解,G-S迭代法只需迭代3次,而J迭代法需要迭代7次.kx1(k)x2(k)x3(k)x(k)-x*012301.41.06340.995104400.781.020480.9952756801.0260.9875161.0019068610.40.06340.0048956 G-S迭代法的計算公式為:不具有一般性7/17/202233第6章 解線性方程組的迭代法 用J迭代法求上例中方程組的解,取x(0)=(0,0,0)T,若使誤差x(k)-x*10

14、-5,問需要迭代多少次?由上例知,x(1)=(1.4,0.5,1.4)T,于是有 x(1)-x(0)=1.4 ,B=0.5 .例8k應(yīng)滿足故取k=19, 即需要迭代19次.解若使x(k) x* ,只需，即事前估計迭代次數(shù)7/17/202234第6章 解線性方程組的迭代法 定理7 設(shè) ，其中 為非奇異矩陣且 非奇異，則 (1) 解方程組的雅可比迭代法收斂的充要條件是 ，其中 (2) 解方程組的高斯-塞德爾迭代法收斂的充要條件是其中 6.2.3 雅可比迭代與高斯-塞德爾迭代法的收斂性雅可比迭代法收斂的充分條件是高斯-賽德爾迭代法收斂的充分條件是7/17/202235第6章 解線性方程組的迭代法例9

15、：說明用J法和G-S法求解下列方程組的收斂性：解：計算特征值：J法不收斂G-S法的迭代矩陣為G-S法收斂7/17/202236第6章 解線性方程組的迭代法例9：說明用J法和G-S法求解下列方程組的收斂性：解：計算特征值：J法收斂計算特征值：G-S法不收斂7/17/202237第6章 解線性方程組的迭代法其他收斂性結(jié)論1）對角占優(yōu)矩陣的性質(zhì) (1) 如果 的元素滿足 稱 為嚴(yán)格對角占優(yōu)陣. (2) 如果 的元素滿足 且上式至少有一個不等式嚴(yán)格成立，稱 為弱對角占優(yōu)陣. 定義6 (對角占優(yōu)陣) 設(shè) 定義7(可約與不可約矩陣) 設(shè) ,如果存在置換陣 使（2.7）否則稱 為不可約矩陣. 其中 為 階方

16、陣， 為 階方陣 ，為可約矩陣.則稱進(jìn)行一次行列重排7/17/202238第6章 解線性方程組的迭代法且記 其中 為 維向量. 由上式第2個方程組求出 , 無零元素的矩陣是不可約矩陣。 再代入第1個方程組求出 例：矩陣可約矩陣 都是不可約矩陣. 7/17/202239第6章 解線性方程組的迭代法 定理8 (對角占優(yōu)定理)如果 為嚴(yán)格對角占優(yōu)矩陣或 為不可約弱對角占優(yōu)矩陣，則 為非奇異矩陣. 就 為嚴(yán)格對角占優(yōu)陣證明此定理. 如果 ，則 有非零解，記為 , 齊次方程組第 個方程 則有 則 證明即 與條件矛盾，故 反證法。7/17/202240第6章 解線性方程組的迭代法 定理9 設(shè) ,如果： (

17、1) 為嚴(yán)格對角占優(yōu)陣，則解 的雅可比迭代法，高斯-塞德爾迭代法均收斂. (2) 為弱對角占優(yōu)陣，且 為不可約矩陣，則解 雅可比迭代法，高斯-塞德爾迭代法均收斂. 2）系數(shù)矩陣對角占優(yōu)的J和G-S迭代的收斂性證明只證(1)中高斯-塞德爾迭代法收斂. 由設(shè)可知， ，高斯-塞德爾迭代法的迭代矩陣為 又 , 于是7/17/202241第6章 解線性方程組的迭代法記當(dāng) 時，由 為嚴(yán)格對角占優(yōu)陣，有 因此，當(dāng) 時，矩陣 為嚴(yán)格對角占優(yōu)陣，因此 即 的特征值均滿足 ，高斯-塞德爾迭代法收斂. 7/17/202242第6章 解線性方程組的迭代法證明只證(1)中Jacobi迭代法收斂. 由設(shè)可知， ，Jaco

18、bi迭代法的迭代矩陣為 又 , 于是記當(dāng) 時，由 為嚴(yán)格對角占優(yōu)陣，有 因此 7/17/202243第6章 解線性方程組的迭代法定理10 設(shè)矩陣 對稱，且對角元 (1) 解線性方程組 的雅可比法收斂的充要條件是 與 均為正定矩陣，其中 (2) 解線性方程組 的高斯-塞德爾法收斂的充分條件是 正定.3）系數(shù)矩陣對稱正定的J和G-S迭代的收斂性例：說明用J法和G-S法求解下列方程組的收斂性：解：計算特征值：7/17/202244第6章 解線性方程組的迭代法例10 在線性方程組 中證明當(dāng) 時高斯-塞德爾法收斂，而雅可比迭代法只在 時才收斂.證明由 的順序主子式當(dāng) 時， 正定，故高斯-塞德爾法收斂.雅

19、可比迭代當(dāng) 時雅可比法收斂.7/17/202245第6章 解線性方程組的迭代法6.3 超松弛迭代法 6.3.1 逐次超松弛迭代法 加速高斯-塞德爾迭代設(shè)已知 及已計算 的分量 (1) 首先用高斯-塞德爾迭代法定義輔助量 (2) 再由 與 加權(quán)平均定義 ，7/17/202246第6章 解線性方程組的迭代法選取分裂矩陣 為其中 為可選擇的松弛因子. 解 的逐次超松弛迭代法(Successive Over Relaxation） （3.1）其中 解 的SOR方法的分量計算公式 （3.2）7/17/202247第6章 解線性方程組的迭代法或 （3.3）注(1) 當(dāng) 時，SOR方法即為高斯-塞德爾迭代法. (2) 每迭代一次主要運(yùn)算量是計算一次矩陣與向量的乘法. (3) ，稱為超松弛法； 時，稱為低松弛法. (4) 在計算機(jī)實(shí)現(xiàn)時用 控制迭代終止，或用 控制迭代終止. 7/17/202248第6章 解線性方程組的迭代法例10 用SOR方法解方程組 精確解為 取 ，解取 ，