線性方程組的迭代法.ppt

數(shù)值分析 第6章方程與方程組的迭代解法 基本迭代法 迭代法的收斂性 6 2解線性方程組的迭代法 超松弛迭代法 6 2線性方程組的迭代法 在用直接法解線性方程組時要對系數(shù)矩陣不斷變換 如果方程組的階數(shù)很高 則運(yùn)算量將會很大 并且大量占用計算機(jī)資源 因此對線性方程組 要求找尋更經(jīng)濟(jì) 適用的數(shù)值解法 1 如果能將線性方程組 1 變換為 2 顯然 1 式和 2 式同解 我們稱 1 2 等價 對線性方程組 2 采用以下步驟 依此類推 3 這種方式就稱為迭代法 以上過程稱為迭代過程 迭代法產(chǎn)生一個序列 如果其極限存在 即 則稱迭代法收斂 否則稱為發(fā)散 一 簡單迭代法 基本迭代法 設(shè)線性方程組 1 的一般形式為 依此類推 線性方程組 1 可化為 4 5 對 4 作迭代過程 則 5 式轉(zhuǎn)化為矩陣形式 6 令 故迭代過程 6 化為 等價線性方程組為 7 稱 5 式和 7 式為解線性方程組 1 的Jacobi迭代法 J法 例1 用Jacobi迭代法求解方程組 誤差不超過1e 4 解 依此類推 得方程組滿足精度的解為x12 迭代次數(shù)為12次 x4 3 02411 94780 9205d 0 1573x5 3 00031 98401 0010d 0 0914x6 2 99382 00001 0038d 0 0175x7 2 99902 00261 0031d 0 0059x8 3 00022 00060 9998d 0 0040 x9 3 00031 99990 9997d 7 3612e 004x10 3 00001 99990 9999d 2 8918e 004x11 3 00002 00001 0000d 1 7669e 004x12 3 00002 00001 0000d 3 0647e 005 分析Jacobi迭代法 5 的迭代過程 將 5 式細(xì)化 考慮迭代式 7 即 將上式改為 8 9 上式稱為Gauss Seidel迭代法 簡稱G S法 利用 8 式展開Gauss Seidel迭代法也可表示成 例2 用Gauss Seidel迭代法求解例1 解 x1 2 50002 09091 2273d 3 4825x2 2 97732 02891 0041d 0 5305x3 3 00981 99680 9959d 0 0465x4 2 99981 99971 0002d 0 0112x5 2 99982 00011 0001d 3 9735e 004x6 3 00002 00001 0000d 1 9555e 004x7 3 00002 00001 0000d 1 1576e 005 通過迭代 至第7步得到滿足精度的解x7 從例1和例2可以看出 Gauss Seidel迭代法的收斂速度比Jacobi迭代法要高 二 迭代法的收斂性 設(shè)解線性方程組的迭代格式 10 11 將 10 與 11 相減 得 則 因此迭代法收斂的充要條件 可轉(zhuǎn)變?yōu)?定理1 迭代格式 10 收斂的充要條件為 12 根據(jù)矩陣與其Jordan標(biāo)準(zhǔn)形及特征值的關(guān)系 可知 即 因此 定理2 迭代格式 10 收斂的充要條件為 13 又因為矩陣的譜半徑不超過其任一種算子范數(shù) 即 于是又可得到 定理3 14 且 證明 只證 14 式 所以 14 即 14 可以用來估計迭代法的精度 理論上只要 在計算時 迭代終止的條件可以用上式判別 例3 判別下列方程組用J法和G S法求解是否收斂 解 1 求Jacobi法的迭代矩陣 因此不能用定理3 只能用定理2判斷 所以 即Jaobi迭代法收斂 2 求Gauss Seidel法的迭代矩陣 同樣用定理2判斷 所以Gauss Seidel迭代法發(fā)散 在例1和例2中 G S法收斂速度比J法要高 但例3卻說明G S法發(fā)散時而J法卻收斂 因此 不能說G S法比J法更好 另外 給出系數(shù)矩陣對角占優(yōu)線性方程組的一個結(jié)論 定理4 證 1 對于Jacobi迭代法 其迭代矩陣為 根據(jù)定理3 Jacobi迭代法收斂 2 對于G S迭代法 其迭代矩陣為 不能使用定理3 而用定理2 即 從而 因此 由于 可得 矛盾 由定理2 G S迭代法收斂 3解線性方程組的超松弛迭代法 超松弛迭代法 簡稱SOR方法 是高斯 塞德爾方法的一種加速方法 是解大型稀疏矩陣方程組的有效方法之一 設(shè)有方程組其中為非奇異矩陣 且設(shè) 0 1 2 n 設(shè)已知第次迭代向量 及第k 1次迭代向量的分量 要求計算分量 首先用迭代法定義輔助量 再把取為與某個平均值 即加權(quán)平均 即 超松弛迭代公式 其中稱為松弛因子 或?qū)憺?顯然 當(dāng) 1時 SOR方法就是高斯 塞德爾迭代法 當(dāng)時 稱為低松弛法 當(dāng)時 稱為高松弛法 例11 用SOR方法解方程組 它的精確解為 解 取 迭代公式為 取 第11次迭代結(jié)果為 0 46 10 5 下面我們寫出SOR迭代公式的矩陣形式 迭代公式亦可寫為 用分解式A D L U 則 即 顯然對任何一個值 非奇異 由設(shè)于是 這就是說 設(shè)SOR方法迭代公式為 其中 矩陣為SOR方法的迭代矩陣 這說明SOR方法相當(dāng)于對方程組 應(yīng)用一般迭代法 于是關(guān)于一般迭代法的理論可得到下述定理 定理設(shè)有線性方程組Ax b 且 0 i 1 2 n 則解方程組的SOR方法收斂的充要條件是 定理設(shè)解Ax b O i 1 2 n 的SOR方法收斂 則 下面研究對于一般方程組 O i 1 2 n 松弛因子在什么范圍內(nèi)取值 SOR方法才可能收斂 現(xiàn)給出SOR方法收斂的必要條件 證明由設(shè)SOR方法收斂 設(shè)的特征值為 則 而 所以 即 定理如果A為對稱正定矩陣 且 則解Ax b的SOR方法收斂 證明在上述假定下 若能證明 那么定理得證 其中為的任一特征值 事實上 設(shè)y為對應(yīng)的的特征向量 即 亦即 為了找出的表達(dá)式 考慮數(shù)量積 則 顯然 記 由于A AT 所以U LT 所以 當(dāng)O 2時 有 從而 即的任一特征值滿足 故SOR方法收斂 注意當(dāng)O 2時 可以證明