電力系統(tǒng)迭代法高斯迭代法迭代法的收斂性

1、計 算 方 法第八章 線性方程組的解法計算方法課程組8.0 引 言重要性：解線性代數(shù)方程組的有效方法在計算數(shù)學和科學計算中具有特殊的地位和作用。如彈性力學、電路分析、熱傳導和振動、以及社會科學及定量分析商業(yè)經(jīng)濟中的各種問題。 求解線性方程組 的求解方法，其中 ， 。 假設(shè) 非奇異，則方程組有唯一解.8.0 引 言 分類： 線性方程組的解法可分為直接法和迭代法兩種方法。直接法： 對于給定的方程組，在沒有舍入誤差的假設(shè)下，能在預定的運算次數(shù)內(nèi)求得精確解。最基本的直接法是Gauss消去法，重要的直接法全都受到Gauss消去法的啟發(fā)。 計算代價高.迭代法：基于一定的遞推格式，產(chǎn)生逼近方程組精確解的近似

2、序列.收斂性是其為迭代法的前提，此外，存在收斂速度與誤差估計問題。簡單實用, 誘人。8.1 雅可比Jacobi迭代法 (AX=b) 一、迭代法的基本思想 二、例題分析 三、 Jacobi迭代公式 與解f (x)=0 的不動點迭代相類似，將AX=b改寫為X=BX+f 的形式，建立雅可比方法的迭代格式： 其中，B稱為迭代矩陣。其計算精度可控，特別適用于求解系數(shù)為大型稀疏矩陣(sparse matrices)的方程組。8.1 雅可比Jacobi迭代法 (AX=b)迭代法的基本思想 問題:(a) 如何建立迭代格式？(b) 向量序列 x(k) 是否收斂以及收斂條件?2 例題分析: 其準確解為X*= 1.

3、1, 1.2, 1.3 ?？紤]解方程組 (1)3.1Jacobi迭代法2 例題分析: 建立與式(1)相等價的形式： (2)其準確解為X*=1.1, 1.2, 1.3?？紤]解方程組 (1)3.1Jacobi迭代法2 例題分析: 其準確解為X*=1.1, 1.2, 1.3。建立與式(1)相等價的形式：考慮解方程組取迭代初值據(jù)此建立迭代公式： 迭代結(jié)果如下表：迭代次數(shù) x1 x2 x30 0 0 01 0.72 0.83 0.842 0.971 1.07 1.153 1.057 1.1571 1.24824 1.08535 1.18534 1.282825 1.095098 1.195099 1.2

4、941386 1.098338 1.198337 1.2980397 1.099442 1.199442 1.2993358 1.099811 1.199811 1.2997779 1.099936 1.199936 1.29992410 1.099979 1.199979 1.29997511 1.099993 1.199993 1.29999112 1.099998 1.199998 1.29999713 1.099999 1.199999 1.29999914 1.1 1.2 1.315 1.1 1.2 1.3 設(shè)方程組 AX=b , 通過分離變量的過程建立Jacobi迭代公式，即 由此

5、我們可以得到 Jacobi 迭代公式：8.1 Jacobi迭代公式 雅可比迭代法的矩陣表示 寫成矩陣形式：A =LUDBJacobi 迭代陣8.2 高斯-塞德爾迭代法 (AX=b)注意到利用Jacobi迭代公式計算時，已經(jīng)計算好了的值，而Jacobi迭代公式并不利用這些最新的近似值計算，仍用 這啟發(fā)我們可以對其加以改進,即在每個分量的計算中盡量利用最新的迭代值，得到上式稱為 Gauss-Seidel 迭代法. 寫成矩陣形式：BGauss-Seidel 迭代陣8.2 高斯-塞德爾迭代法其準確解為X*=1.1, 1.2, 1.3?？紤]解方程組高斯-塞德爾迭代法算例高斯-塞德爾迭代格式迭代次數(shù) x1

6、 x2 x3 0 0 0 0 1 0.72 0.902 1.1644 2 1.04308 1.167188 1.282054 3 1.09313 1.195724 1.297771 4 1.099126 1.199467 1.299719 5 1.09989 1.199933 1.299965 6 1.099986 1.199992 1.299996 7 1.099998 1.199999 1.299999 8 1.1 1.2 1.3開始TFTFT 逐次超松弛迭代法(Successive Over Relaxation Method，簡寫為SOR)可以看作帶參數(shù)的高斯-塞德爾迭代法，是 G-S

7、 方法的一種修正或加速，是求解大型稀疏矩陣方程組的有效方法之一。8.3 超松馳迭代法SOR方法1. SOR基本思想 設(shè)方程組AX=b, 其中，A=(aij) 為非奇異陣， x=(x1, x2, , xn)T, b=(b1, b2, , bn)T.假設(shè)已算出 x(k) ，8.3 超松馳迭代法SOR方法2. SOR算法的構(gòu)造 稱為松弛因子 利用高斯-塞德爾迭代法得:8.3 超松馳迭代法SOR方法2. SOR算法的構(gòu)造 (基于G-S迭代) 解方程組AX=b的逐次超松弛迭代公式： 顯然，當取=1時，上式就是高斯-塞德爾迭代公式.8.3 超松馳迭代法SOR方法2. SOR算法的構(gòu)造(基于Jacobi迭代

8、) 得到解方程組 AX=b 的逐次超松弛迭代公式： 顯然，上式就是 基于Jacobi 迭代的 SOR 方法.下面令 ，希望通過選取合適的 來加速收斂，這就是松弛法 。3. SOR算法的進一步解釋 SOR方法其中ri(k+1) =相當于在 的基礎(chǔ)上加個余項生成 。0 1(漸次)超松弛法利用SOR方法解方程組SOR例題分析:其準確解為x*=1, 1, 2.建立與式(1)相等價的形式：據(jù)此建立G-S迭代公式：取迭代初值:,=1.5,迭代結(jié)果如下表. SOR迭代公式為：GS迭代法須迭代85次得到準確值 x*=1, 1, 2;而SOR方法只須55次即得準確值. 由此可見，適當?shù)剡x擇松弛因子，SOR法具有

9、明顯的加速收斂效果. 逐次超松弛迭代法次數(shù) x1 x2 x3 1 0.625000 0.062500 1.750000 2 0.390625 0.882813 1.468750 3 1.017578 0.516602 1.808594 4 0.556885 0.880981 1.710449 5 1.023712 0.743423 1.868103 15 0.991521 0.985318 1.987416 25 0.998596 0.998234 1.998355 55 1.00000 1.0000 2.0000 關(guān)于SOR方法的說明：顯然，當 時，SOR方法就是Gauss- Seidel方

10、法。SOR 方法每一次迭代的主要運算量是計算一次矩陣與向量的乘法。 時稱為超松弛方法， 時稱為低松弛方法。計算機實現(xiàn)時可用 控制迭代終止，或用 SOR方法可以看成是Gauss-Seidel方法的一種修正。 （迭代法基本定理） 設(shè)有方程組 ，對于任意的初始向量 ，迭代公式 收斂的充要條件是迭代矩陣 的譜半徑 . 8.4 迭代法的收斂性-充要條件 迭代法的基本定理在理論分析中有重要意義。定理2：設(shè)X*是方程組AX = b的同解方程X = BX + F 的準確解，若迭代公式中迭代矩陣B的某種范數(shù)，(1)(2)則有 在具體使用上，由于 ，因此，我們利用范數(shù)可以建立判別迭代法收斂的充分條件。 關(guān)于解某些特殊方程組迭代法的收斂性定義：(對角占優(yōu)陣) 設(shè)(1) 如果 元素滿足 稱 為嚴格對角占優(yōu)陣(2) 如果 元素滿足 且上式至少有一個不等式嚴格成立， 稱 為弱對角占優(yōu)陣。 設(shè) ，如果： 為嚴格對角占優(yōu)，則解 的Jacobi迭代法， Gauss-Seidel迭代法均收斂。Seidel迭代格式為 從式中解出故可得Seidel迭代矩陣為從例中可以看出Jacobi迭代矩陣Bj的主對角線為零，而Seidel迭代矩陣Bs的第1列都是零，這對一般情況也是成立的。 舉例檢驗Jacoai迭代的收斂性首先將原方程組寫為迭代形式的方程組，即：求任一行之和的最大值1,即： |M|=max5/8,5/11