數(shù)值計(jì)算方法-第6章解線性方程組的迭代法.ppt

第6章解線性方程組的迭代法 直接法得到的解是理論上準(zhǔn)確的 但是我們可以看得出 它們的計(jì)算量都是n3數(shù)量級 存儲(chǔ)量為n2量級 這在n比較小的時(shí)候還比較合適 n 400 但是對于現(xiàn)在的很多實(shí)際問題 往往要我們求解很大的n的矩陣 而且這些矩陣往往是系數(shù)矩陣就是這些矩陣含有大量的0元素 對于這類的矩陣 在用直接法時(shí)就會(huì)耗費(fèi)大量的時(shí)間和存儲(chǔ)單元 因此我們有必要引入一類新的方法 迭代法 迭代法具有的特點(diǎn)是速度快 與非線性方程的迭代方法一樣 需要我們構(gòu)造一個(gè)等價(jià)的方程 從而構(gòu)造一個(gè)收斂序列 序列的極限值就是方程組的根 對方程組 做等價(jià)變換 如 令 則 則 我們可以構(gòu)造序列 若 同時(shí) 所以 序列收斂 與初值的選取無關(guān) 定義6 1 收斂矩陣 6 1Jacobi迭代 格式很簡單 Jacobi迭代算法 1 輸入系數(shù)矩陣A和向量b 和誤差控制eps2 x1 0 0 0 x2 1 1 1 賦初值3 while A x2 b eps x1 x2 for i 0 i n i x2 i 0 for j 0 j i j x2 i A i j x1 j for j i 1 j n j x2 i A i j x1 j x2 i x2 i b i A i i 4 輸出解x2 迭代矩陣 記 易知 Jacobi迭代有 收斂條件 迭代格式收斂的充要條件是G的譜半徑 1 對于Jacobi迭代 我們有一些保證收斂的充分條件 定理 若A滿足下列條件之一 則Jacobi迭代收斂 A為行對角占優(yōu)陣 A為列對角占優(yōu)陣 A滿足 證明 A為列對角占優(yōu)陣 則AT為行對角占優(yōu)陣 有 證畢 6 2Gauss Seidel迭代 在Jacobi迭代中 使用最新計(jì)算出的分量值 Gauss Siedel迭代算法 1 輸入系數(shù)矩陣A和向量b 和誤差控制eps2 x2 1 1 1 賦初值3 while A x2 b eps for i 0 i n i for j 0 j i j x2 i A i j x2 j for j i 1 j n j x2 i A i j x2 j x2 i x2 i b i A i i 4 輸出解x2 迭代矩陣 是否是原來的方程的解 A D L U 收斂條件 迭代格式收斂的充要條件是G的譜半徑 1 我們看一些充分條件 定理 若A滿足下列條件之一 則Jacobi迭代收斂 A為行或列對角占優(yōu)陣 A對稱正定陣 證明 設(shè)G的特征多項(xiàng)式為 則 為對角占優(yōu)陣 則 時(shí) 為對角占優(yōu)陣 即 即 證畢 注 二種方法都存在收斂性問題 有例子表明 Gauss Seidel法收斂時(shí) Jacobi法可能不收斂 而Jacobi法收斂時(shí) Gauss Seidel法也可能不收斂 1 預(yù)處理 2 格式 3 結(jié)果 1 Jacobi迭代 特征值為 2 Gauss Siedel迭代 6 3松弛迭代 記 則 可以看作在前一步上加一個(gè)修正量 若在修正量前乘以一個(gè)因子 有 對Gauss Seidel迭代格式 寫成分量形式 有 松弛迭代算法 1 輸入系數(shù)矩陣A 向量b和松弛因子omega 和誤差控制eps2 x2 1 1 1 賦初值3 while A x2 b eps for i 0 i n i temp 0for j 0 j i j temp A i j x2 j for j i 1 j n j temp A i j x2 j temp x2 i b i A i i x2 i 1 omega x2 i omega temp 4 輸出解x2 迭代矩陣 定理 松弛迭代收斂 定理 A對稱正定 則松弛迭代收斂 是否是原來的方程的解 SOR方法收斂的快慢與松弛因子 的選擇有密切關(guān)系 但是如何選取最佳松弛因子 即選取 使 達(dá)到最小 是一個(gè)尚未很好解決的問題 實(shí)際上可采用試算的方法來確定較好的松弛因子 經(jīng)驗(yàn)上可取1 4 1 6 定理若SOR方法收斂 則0 2 證設(shè)SOR方法收斂 則 1 所以 det 1 2 n 1 而det det D L 1 1 D U det E D 1L 1 det 1 E D 1U 1 n 于是 1 1 或0 2 定理設(shè)A是對稱正定矩陣 則解方程組Ax b的SOR方法 當(dāng)0 2時(shí)收斂 證設(shè) 是 的任一特征值 y是對應(yīng)的特征向量 則 1 D U y D L y 于是 1 Dy y Uy y Dy y Ly y 由于A D L U是對稱正定的 所以D是正定矩陣 且L UT 若記 Ly y i 則有 Dy y 0 Uy y y Ly Ly y i 0 Ay y Dy y Ly y Uy y 2 所以 當(dāng)0 2時(shí) 有 2 2 2 2 2 2 0 所以 2 1 因此 1 即S0R方法收斂 可得 2 設(shè) 是B的任一特征值 y是對應(yīng)的特征向量 則 L U y Dy 于是 Ly y Uy y Dy y 當(dāng)A對稱正定時(shí) 即2 0 而 2D A y y Dy y Ly y Uy y 2 即 當(dāng)A對稱正定時(shí) Jacobi迭代法收斂 2D A正定