计算方法浙大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矩阵的范数（续）11在用直接法解线性方程组时要对系数矩阵不断变换如果方程组的阶数很高,则运算量将会很大因此对线性方程组要求找寻更经济、适用的数值解法3.6线性方程组的迭代解法12迭代法是对任意给定的初始近似解向量，按照某种方法逐步生成近似解序列，使解序列的极限为方程组的解。因此迭代法是用某种极限过程去逐步逼近线性方程组精确解的方法。可以用有限步运算算出具有指定精确度的近似解。

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

3.6线性方程组的迭代解法133.6线性方程组的迭代解法（续）143.6线性方程组的迭代解法（续）153.6线性方程组的迭代解法（续）

解线性方程组的迭代法的基本思想与求非线性方程的迭代法的基本思想是类似的。163.6线性方程组的迭代解法（续）3.6.1迭代格式的一般形式变形成等价的同解线性方程组然后任取一个初始向量x(0)∈Rn作为近似解，由公式构造向量序列{x(k)}，如果向量序列{x(k)}满足173.6.1迭代格式的一般形式（续）------迭代法收敛方程组的解否则，称此迭代法发散。迭代格式迭代矩阵第k次迭代近似解-------第k次迭代误差用迭代法解方程组(Ax=b)的关键是：183.6.1迭代格式的一般形式（续）如何构造迭代格式雅可比(Jacobi)迭代法高斯-塞德尔（Gauss-Seidel)迭代法逐次超松弛法(2)由迭代格式产生的向量序列{x(k)}的收敛条件是什么？193.6.2雅可比迭代法设线性方程组

Ax=b的一般形式为雅可比（Jacobi)迭代法的步骤为：203.6.2雅可比迭代法（续）21（2）写成迭代格式3.6.2雅可比迭代法（续）22（3）取定初始向量令根据迭代公式（3.23)可得向量序列{x(k)}。3.6.2雅可比迭代法（续）233.6.2雅可比迭代法（续）类似于非线性方程的迭代法，对于事先给定的精度要求ε，当就可以得到方程组的近似解24雅可比迭代法的矩阵形式，3.6.2雅可比迭代法（续）253.6.2雅可比迭代法（续）则线性方程组(3.18)Ax=b可表示为相应的迭代格式为263.6.2雅可比迭代法（续）所以Jacobi迭代格式的矩阵形式-----Jacobi迭代矩阵27例.用Jacobi迭代法求解方程组解:按迭代公式，得雅可比迭代格式取令3.6.2雅可比迭代法（续）283.6.2雅可比迭代法（续）29在计算机上，使用Jacobi迭代法求解方程组时，可用x，y分别表示x(k)和x(k+1)当时，停止迭代，3.6.2雅可比迭代法（续）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雅可比迭代法（续）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)出发，先用Gauss-Seidel迭代格式计算一步，将计算结果记为令新的近似解记松弛因子40逐次超松弛迭代法或SOR法的迭代公式当ω＝1时就是高斯-赛德尔迭代法41

在SOR法中，松弛因子的取值对迭代公式的收敛速度影响极大。实际计算时，可以根据方程组的系数矩阵的性质，或结合实践计算的经验来选取松弛因子。3.6.4逐次超松弛迭代法（续）逐次超松弛迭代法的矩阵形式423.6.4逐次超松弛迭代法（续）其中433.6.4逐次超松弛迭代法（续）例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逐次超松弛迭代法（续）取ω=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迭代法的收敛性(续）证充分性：设，则1不是B的特征值，因而有唯一解x*，即误差向量523.6.5迭代法的收敛性(续）必要性：设，其中两边取极限得从而有误差向量533.6.5迭代法的收敛性(续）由于x(0)是任意的，因而ε(0)也是任意的，所以由定理3.10得证毕。定理3.10设推论1若||B||<1，则迭代格式(3.31)收敛证：定理3.11（定理3.8)迭代格式收敛定理3.8设A∈Rn×n，则