計算方法浙大C3 線性方程組的解法2

2:44:01下午12:44:01下午1線性方程組2017第三章

第三章解線性方程組的迭代法基礎—向量與矩陣的范數3.5.1向量的范數/*vectornorms*/

為了研究線性方程組近似解的誤差估計和迭代法的收斂性，需要對n維向量空間Rn中的向量的“大小”給出某種度量。衡量數的誤差用到絕對值；現代數學中常用“范數”來度量向量的“大小”。

定義3.1設為定義在Rn上的實函數，如果對任意它滿足條件：（1）當且僅當x=0

(正定性）（2）（對任意常數）（齊次性）（3）（三角不等式）33.5.1向量的范數（對任意）則稱為Rn上的向量范數（4）定義3.1向量范數常用向量范數：==niixx11||||||向量的1-范數：==niixx122||||||向量的2-范數：pnipipxx/11||||||==向量的p-范數：||max||||1inixx=向量的

-范數：可以證明向量函數||x||p是Rn上的向量的范數（滿足定義3.1），且前三種范數是“p”范數的特殊情況||x||2向量范數的幾何意義7例設x

=(-1,2,3)T計算||x||1,||x||∞,||x||2||x||1=1+2+3=6

解

||x||2=(12+22+32)1/2=

||x||∞=max{1,2,3}=3定義向量序列收斂于向量是指對每一個1in都有。可以理解為定義3.2向量收斂的定義§1NormsofVectorsandMatrices–MatrixNorms定義3.3矩陣范數/*matrixnorms*/定義

Rmn空間的矩陣范數

||·||對任意滿足：（正定性

/*positivedefinite*/)對任意(齊次性

/*homogeneous*/)（三角不等式

/*triangleinequality*/)(4)*||AB

||||A||·||B||（相容

/*consistent*/

當

m=n

時)(5)||Ax

||||A

||·||x||特別有：（行或無窮范數）（列或1范數）10

例設計算||A||1、||A||∞解

||A||1=max{5,8}=8||A||∞=max{4,9}=93.5.2矩陣的范數（續(xù)）11在用直接法解線性方程組時要對系數矩陣不斷變換如果方程組的階數很高,則運算量將會很大因此對線性方程組要求找尋更經濟、適用的數值解法3.6線性方程組的迭代解法12迭代法是對任意給定的初始近似解向量，按照某種方法逐步生成近似解序列，使解序列的極限為方程組的解。因此迭代法是用某種極限過程去逐步逼近線性方程組精確解的方法?？梢杂糜邢薏竭\算算出具有指定精確度的近似解。

主要方法：雅可比(Jacobi)迭代法高斯-塞德爾（Gauss-Seidel)迭代法逐次超松弛法

3.6線性方程組的迭代解法133.6線性方程組的迭代解法（續(xù)）143.6線性方程組的迭代解法（續(xù)）153.6線性方程組的迭代解法（續(xù)）

解線性方程組的迭代法的基本思想與求非線性方程的迭代法的基本思想是類似的。163.6線性方程組的迭代解法（續(xù)）3.6.1迭代格式的一般形式變形成等價的同解線性方程組然后任取一個初始向量x(0)∈Rn作為近似解，由公式構造向量序列{x(k)}，如果向量序列{x(k)}滿足173.6.1迭代格式的一般形式（續(xù)）------迭代法收斂方程組的解否則，稱此迭代法發(fā)散。迭代格式迭代矩陣第k次迭代近似解-------第k次迭代誤差用迭代法解方程組(Ax=b)的關鍵是：183.6.1迭代格式的一般形式（續(xù)）如何構造迭代格式雅可比(Jacobi)迭代法高斯-塞德爾（Gauss-Seidel)迭代法逐次超松弛法(2)由迭代格式產生的向量序列{x(k)}的收斂條件是什么？193.6.2雅可比迭代法設線性方程組

Ax=b的一般形式為雅可比（Jacobi)迭代法的步驟為：203.6.2雅可比迭代法（續(xù)）21（2）寫成迭代格式3.6.2雅可比迭代法（續(xù)）22（3）取定初始向量令根據迭代公式（3.23)可得向量序列{x(k)}。3.6.2雅可比迭代法（續(xù)）233.6.2雅可比迭代法（續(xù)）類似于非線性方程的迭代法，對于事先給定的精度要求ε，當就可以得到方程組的近似解24雅可比迭代法的矩陣形式，3.6.2雅可比迭代法（續(xù)）253.6.2雅可比迭代法（續(xù)）則線性方程組(3.18)Ax=b可表示為相應的迭代格式為263.6.2雅可比迭代法（續(xù)）所以Jacobi迭代格式的矩陣形式-----Jacobi迭代矩陣27例.用Jacobi迭代法求解方程組解:按迭代公式，得雅可比迭代格式取令3.6.2雅可比迭代法（續(xù)）283.6.2雅可比迭代法（續(xù)）29在計算機上，使用Jacobi迭代法求解方程組時，可用x，y分別表示x(k)和x(k+1)當時，停止迭代，3.6.2雅可比迭代法（續(xù)）30（4）對i=1~n令xi←yi（5）對D≥ε則轉到(2)（6）輸出xi（i=1~n）并停止計算（1）對i=1~n令xi←0（2）D←0（3）對i=1~n做令

yi=bi對j=1~n但j≠i令yi←yi-aijxj

令yi←yi/aii

若|xi-yi|>D則令D←|xi-yi|計算步驟3.6.2雅可比迭代法（續(xù)）31分析Jacobi迭代法的迭代過程在算x(k+2)時才用x(k+1)代換x(k)。雅可比迭代又稱同時代換法或整體代換法或簡單迭代法。高斯-賽德爾迭代法32迭代公式高斯-賽德爾(Gauss-Seidel)迭代法或稱逐個代換法33高斯-賽德爾(Gauss-Seidel)迭代法的矩陣形式記-----Gauss-Seidel迭代矩陣34例.用高斯-賽德爾迭代法重新求解方程組解:按迭代公式，得高斯-賽德爾迭代格式取令3536故x≈x(8)。在計算機上，用高斯-賽德爾迭代法求解方程組時，當時，停止迭代，37（4）對D≥ε則轉到(2)（5）輸出xi（i=1~n）并停止計算（2）D←0（3）對i=1~n做令

y

=bi令y

←y

/aii

若|xi-y|>D則令D←|xi-y|令xi=y計算步驟（1）對i=1~n令xi←0對j=1~n但j≠i令y

←y-aijxj

38（4）對D≥ε則轉到(2)（5）輸出xi（i=1~n）并停止計算（2）D←0（3）對i=1~n做令

y

=bi令y

←y

/aii

若|xi-y|>D則令D←|xi-y|令xi=y（1）對i=1~n令xi←0對j=1~n但j≠i令y

←y-aijxj

（4）對i=1~n令xi←yi（5）對D≥ε則轉到(2)（6）輸出xi（i=1~n）并停止計算（1）對i=1~n令xi←0（2）D←0（3）對i=1~n做令

yi=bi對j=1~n但j≠i令yi←yi-aijxj

令yi←yi/aii

若|xi-yi|>D則令D←|xi-yi|高斯-賽德爾(Gauss-Seidel)雅可比(Jacobi)393.6.4逐次超松弛迭代法或SOR法SOR法的構造方法：從近似解x(k)出發(fā)，先用Gauss-Seidel迭代格式計算一步，將計算結果記為令新的近似解記松弛因子40逐次超松弛迭代法或SOR法的迭代公式當ω＝1時就是高斯-賽德爾迭代法41

在SOR法中，松弛因子的取值對迭代公式的收斂速度影響極大。實際計算時，可以根據方程組的系數矩陣的性質，或結合實踐計算的經驗來選取松弛因子。3.6.4逐次超松弛迭代法（續(xù)）逐次超松弛迭代法的矩陣形式423.6.4逐次超松弛迭代法（續(xù)）其中433.6.4逐次超松弛迭代法（續(xù)）例3.12用SOR方法解方程組（它的精確解為x*=(-1,-1,-1,-1)T）解取x(0)=0，迭代公式為xi(k+1)=xi(k)+ω(bi-ai1x1(k+1)-…-ai,i-1xi-1(k+1)

-aiixi(k)

-ai,i+1xi+1(k)-…-ainxn(k))/aii443.6.4逐次超松弛迭代法（續(xù)）取ω=1.3，第11次迭代結果為x(11)=(-0.99999646,-1.00000310,-0.99999953,-0.99999912)T對ω取其他值，迭代次數不同。松弛因子ω迭代次數松弛因子ω迭代次數1.0221.5171.1171.6231.2121.7331.3111.8531.4141.910945雅可比迭代格式46迭代公式高斯-賽德爾(Gauss-Seidel)迭代法或稱逐個代換法47Jacobi迭代格式矩陣形式-----Jacobi迭代矩陣48高斯-賽德爾(Gauss-Seidel)迭代法的矩陣形式記-----Gauss-Seidel迭代矩陣49設線性方程組--------(3.30)3.6.5迭代法的收斂性--------(3.29)等價方程組相應的迭代格式是--------(3.31)問題：迭代矩陣B滿足什么條件時，由迭代格式產生的向量序列{x(k)}收斂到x*?50定義3.4設A∈Rn×n的特征值為λi(i=1,2,…,n)，則稱為A的譜半徑定義3.4譜半徑譜半徑/*spectralradius*/定義矩陣A的譜半徑記為(A)=，其中i

為

A

的特征根。ReIm(A)51定理3.11.(迭代法基本定理）迭代格式(3.31)對于任意初值x(0)均收斂的充要條件是3.6.5迭代法的收斂性(續(xù)）證充分性：設，則1不是B的特征值，因而有唯一解x*，即誤差向量523.6.5迭代法的收斂性(續(xù)）必要性：設，其中兩邊取極限得從而有誤差向量533.6.5迭代法的收斂性(續(xù)）由于x(0)是任意的，因而ε(0)也是任意的，所以由定理3.10得證畢。定理3.10設推論1若||B||<1，則迭代格式(3.31)收斂證：定理3.11（定理3.8)迭代格式收斂定理3.8設A∈Rn×n，則