計(jì)算方法浙大C3 線性方程組的解法2

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

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

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

定義3.1設(shè)為定義在Rn上的實(shí)函數(shù)，如果對(duì)任意它滿足條件：（1）當(dāng)且僅當(dāng)x=0

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

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

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

解

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

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

Rmn空間的矩陣范數(shù)

||·||對(duì)任意滿足：（正定性

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

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

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

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

/*consistent*/

當(dāng)

m=n

時(shí))(5)||Ax

||||A

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

例設(shè)計(jì)算||A||1、||A||∞解

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

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

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

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

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

yi=bi對(duì)j=1~n但j≠i令yi←yi-aijxj

令yi←yi/aii

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

y

=bi令y

←y

/aii

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

←y-aijxj

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

y

=bi令y

←y

/aii

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

←y-aijxj

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

yi=bi對(duì)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法的構(gòu)造方法：從近似解x(k)出發(fā)，先用Gauss-Seidel迭代格式計(jì)算一步，將計(jì)算結(jié)果記為令新的近似解記松弛因子40逐次超松弛迭代法或SOR法的迭代公式當(dāng)ω＝1時(shí)就是高斯-賽德爾迭代法41

在SOR法中，松弛因子的取值對(duì)迭代公式的收斂速度影響極大。實(shí)際計(jì)算時(shí)，可以根據(jù)方程組的系數(shù)矩陣的性質(zhì)，或結(jié)合實(shí)踐計(jì)算的經(jīng)驗(yàn)來選取松弛因子。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次迭代結(jié)果為x(11)=(-0.99999646,-1.00000310,-0.99999953,-0.99999912)T對(duì)ω取其他值，迭代次數(shù)不同。松弛因子ω迭代次數(shù)松弛因子ω迭代次數(shù)1.0221.5171.1171.6231.2121.7331.3111.8531.4141.910945雅可比迭代格式46迭代公式高斯-賽德爾(Gauss-Seidel)迭代法或稱逐個(gè)代換法47Jacobi迭代格式矩陣形式-----Jacobi迭代矩陣48高斯-賽德爾(Gauss-Seidel)迭代法的矩陣形式記-----Gauss-Seidel迭代矩陣49設(shè)線性方程組--------(3.30)3.6.5迭代法的收斂性--------(3.29)等價(jià)方程組相應(yīng)的迭代格式是--------(3.31)問題：迭代矩陣B滿足什么條件時(shí)，由迭代格式產(chǎn)生的向量序列{x(k)}收斂到x*?50定義3.4設(shè)A∈Rn×n的特征值為λi(i=1,2,…,n)，則稱為A的譜半徑定義3.4譜半徑譜半徑/*spectralradius*/定義矩陣A的譜半徑記為(A)=，其中i

為

A

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