逐次逼近法lz课件

第六章逐次逼近法6.1解线性方程组的迭代法

6.2矩阵和向量的范数

6.3非线性方程的迭代法

6.4多根区间上的逼近求根第六章逐次逼近法6.1解线性方程组的迭代法16.1解线性方程组的迭代法一、迭代法的思想二、Jacobi迭代法三、Guass-Seidel迭代法6.1解线性方程组的迭代法一、迭代法的思想2第一节解线性方程组的迭代法

一、迭代法的思想1.问题2.思想直接法求解线性方程组Ax=b的过程中，系数矩阵A在不断变动，A的阶数较大时，占用内存很大，程序复杂，对编程技巧要求高。按照某种规则，通过已知元素或已经求得的元素求出后继元素，从而形成一个序列，由该序列的极限过程去逐步逼近数值问题的精确解。解决方法：求解过程中系数矩阵不变程序设计较简单的迭代法。第一节解线性方程组的迭代法

一、迭代法的思想1.问题2.第一节解线性方程组的迭代法

二、Jacobi迭代法例1

用简单迭代法解下列方程组解：我们分别从方程组的三个方程中分离出x1，x2，x3，得：据此可以建立迭代公式如下：当k－>∞时，X1（k）->1.1，X2（k）->1.2

，X3（k）->1.3第一节解线性方程组的迭代法

二、Jacobi迭代法例1第一节解线性方程组的迭代法

二、Jacobi迭代法1.解线性方程组的迭代法：将联立方程组的求解归结为重复计算一组彼此独立的线性表达式，从而简化问题。(i=1~n)考察一般形式的线性方程组：第一节解线性方程组的迭代法

二、Jacobi迭代法1.解第一节解线性方程组的迭代法

二、Jacobi迭代法(i=1~n)(k=0~+∞)写成迭代格式：含义：第k＋1次迭代出来的是由第k次迭代出来的加上一个修正项△xi得到的。随着△xi第一节解线性方程组的迭代法

二、Jacobi迭代法(i=第一节解线性方程组的迭代法

二、Jacobi迭代法2.矩阵表达原来方程：Ax＝b00LUD第一节解线性方程组的迭代法

二、Jacobi迭代法2.矩第一节解线性方程组的迭代法

二、Jacobi迭代法2.矩阵表达:A=D-L-U0000A=-L-UDBJfJ(k=0~+∞)Jacobi迭代矩阵公式第一节解线性方程组的迭代法

二、Jacobi迭代法2.矩第一节解线性方程组的迭代法

二、Jacobi迭代法Jacobi迭代矩阵公式(k=0~+∞)第一节解线性方程组的迭代法

二、Jacobi迭代法Jac第一节解线性方程组的迭代法

二、Jacobi迭代法例1用Jacobi迭代法解下列方程组据此可以建立迭代公式如下：D-1L+U第一节解线性方程组的迭代法

二、Jacobi迭代法例1用第一节解线性方程组的迭代法

二、Jacobi迭代法例2(P214例1)

用简单迭代法解下列方程组其矩阵形式如下：2.矩阵表达若取初值则迭代10次后可得

BJfJ第一节解线性方程组的迭代法

二、Jacobi迭代法例2(第一节解线性方程组的迭代法

二、Jacobi迭代法3.算法设计(1)由于Xi(k+1)=Xi(k)+△Xi,△Xi代表了误差，故可以用Xi(k+1)-Xi(k)控制精度，用Y[i]存储迭代结果Xi(k+1)，用X[i]存储迭代初值Xi(k)，用刻画精度。(2)控制运算量：为了防止收敛速度过慢或迭代不收敛（发散），设置最大迭代次数N以控制计算量。若迭代N次尚不能达到精度要求，则宣告迭代失败。第一节解线性方程组的迭代法

二、Jacobi迭代法3.算第一节解线性方程组的迭代法

二、Jacobi迭代法3.算法设计第一节解线性方程组的迭代法

二、Jacobi迭代法3.算第一节解线性方程组的迭代法

作业题P260习题14(1)（用G－S迭代法解方程组）P260习题14(2)（用Jacobi迭代法解方程组）第一节解线性方程组的迭代法

作业题P260习题1第一节解线性方程组的迭代法

三、Guass－Seidel迭代法例1

用G-S迭代法解下列方程组解：我们分别从方程组的三个方程中分离出x1，x2，x3，得：据此可以建立迭代公式如下：当k－>∞时，X1（k）->1.1，X2（k）->1.2

，X3（k）->1.3(k+1)(k+1)(k+1)第一节解线性方程组的迭代法

三、Guass－Seidel第一节解线性方程组的迭代法

三、Guass－Seidel迭代法1.解线性方程组的迭代法注：（1）Jacobi迭代中没有充分利用已经计算出来的信息，例如在计算xi时，x1～xi-1都已经计算出来了，一般而言，xi(k+1)要比xi(k)更准确些。（2）在本题中G-S的迭代效果比Jacobi好，一般而言G-S的收敛效果比Jacobi好，收敛更快，但也不一定。有时可能G-S比Jacobi收敛更慢，甚至G-S发散，Jacobi反而收敛。第一节解线性方程组的迭代法

三、Guass－Seidel第一节解线性方程组的迭代法

三、Guass－Seidel迭代法(i=1~n)(k=0~+∞)写成迭代格式：△xi1.迭代公式第一节解线性方程组的迭代法

三、Guass－Seidel第一节解线性方程组的迭代法

三、Guass－Seidel迭代法2.矩阵表达原来方程：Ax＝b00第一节解线性方程组的迭代法

三、Guass－Seidel第一节解线性方程组的迭代法

三、Guass－Seidel迭代法2.矩阵表达:A=D-L-U0000A=-L-UDBGfG(k=0~+∞)G-S迭代矩阵公式第一节解线性方程组的迭代法

三、Guass－Seidel第一节解线性方程组的迭代法

二、Jacobi迭代法例1用G-S迭代法解下列方程组解第一节解线性方程组的迭代法

二、Jacobi迭代法例1用第一节解线性方程组的迭代法

二、Jacobi迭代法例1用G-S迭代法解下列方程组据此可以建立迭代公式如下：(D-L)-1U(D-L)-1b第一节解线性方程组的迭代法

二、Jacobi迭代法例1用第一节解线性方程组的迭代法

三、Guass－Seidel迭代法3.Jacobi迭代与G-S迭代比较Jacobi迭代矩阵公式G-S迭代矩阵公式Jacobi迭代公式G-S迭代公式第一节解线性方程组的迭代法

三、Guass－SeidelSOR迭代称为SOR迭代矩阵为了得到更好的收敛效果，可在修正项前乘以一个参数w，于是就得到所谓的逐次超松弛迭代法，简称SOR迭代，其中w

称为松弛因子。此时在GS迭代中解得SOR迭代称为SOR迭代矩阵为了得到更好的收敛效果，可23Jacobi、GS和SOR算法

Jacobi算法

GS算法

SOR算法Jacobi、GS和SOR算法Jacobi算法G24举例解：

例：解线性方程组取初始向量

x(0)=(0,0,0)，迭代过程中小数点后保留4位。Jacobi迭代格式令则迭代得：x(1)=(0.5000,2.6667,-2.5000)Tx(21)=(2.0000,3.0000,-1.0000)T举例解：例：解线性方程组取初始向量x(0)=(0,25举例（续）GS迭代格式得x(1)=(0.5000,2.8333,-1.0833)Tx(9)=(2.0000,3.0000,-1.0000)T举例（续）GS迭代格式得x(1)=(0.5000,26举例（续）SOR迭代格式取w=1.1，得x(1)=(0.5500,3.1350,-1.0257)Tx(7)=(2.0000,3.0000,-1.0000)T如何确定SOR迭代中的最优松弛因子是一件很困难的事。

举例（续）SOR迭代格式取w=1.1，得x(1)=27几种迭代法的统一

Jacobi迭代

GS迭代

SOR迭代A=M-

NM=

D,N=M–A=L+UM=

D–L,N=U几种迭代法的统一Jacobi迭代GS迭代SOR迭28第一节解线性方程组的迭代法

作业题P260习题14(1)（用G－S迭代法解方程组）P260习题14(2)（用Jacobi迭代法解方程组）第一节解线性方程组的迭代法

作业题P260习题16.2矩阵和向量的范数一、向量范数二、矩阵范数三、迭代法的收敛性6.2矩阵和向量的范数一、向量范数30第二节矩阵和向量的范数

一、向量范数1.问题非负性齐次性三角不等式向量范数

||||是一个满足三个条件的实数：2.定义范数是一个数||||∈Rn为了研究迭代过程的收敛性，要对向量的“大小”引入某种度量例如：向量的长度：即：第二节矩阵和向量的范数

一、向量范数1.问题非负性齐次性三第二节矩阵和向量的范数

一、向量范数在Rn中,常用的几种向量范数有:3.四种向量范数1-范数(2)2-范数(3)∞-范数(4)推广p-范数P=1P=2P=∞第二节矩阵和向量的范数

一、向量范数在Rn中,常用的几种向第二节矩阵和向量的范数

一、向量范数P202例1：设x=(1,2,-3,-4)T,则4.性质第二节矩阵和向量的范数

一、向量范数P202例1：设x第二节矩阵和向量的范数

二、矩阵范数1.矩阵算子范数定义(1)

非负性

(2)齐次性(3)三角不等式

(4)*相容性(5)*相容性2.性质是向量范数第二节矩阵和向量的范数

二、矩阵范数1.矩阵算子范数定义(（A所有行绝对和的最大值）（A所有列绝对和的最大值）（ATA最大特征值开方）（A所有元素平方和开方）第二节矩阵和向量的范数

二、矩阵范数3.四种矩阵范数行和范数：列和范数：谱范数：F-范数：P204例2（A所有行绝对和的最大值）（A所有列绝对和的最大值）（ATA第二节矩阵和向量的范数

二、矩阵范数（1）求ATA（2）求ATA的全部特征值（3）求||A||2第二节矩阵和向量的范数

二、矩阵范数（1）求ATA（2）求第二节矩阵和向量的范数

二、矩阵范数4.矩阵的谱半径（P204定义1.4）(A)=，其中i

为A∈Rn×n的特征根。谱半径与矩阵范数的关系：||A||≥(A)ReIm(A)将任意一个特征根所对应的特征向量代入证明：由算子范数的相容性，得到由的任意性：第二节矩阵和向量的范数

二、矩阵范数4.矩阵的谱半径（P2第二节矩阵和向量的范数

二、矩阵范数例3：求矩阵B的谱半径(B)，其中

解：第二节矩阵和向量的范数

二、矩阵范数例3：求矩阵B的谱半径误差分析（外招不要求）线性方程组：

A为非奇异矩阵，x为方程组的精确解.

估计x-y,其中y是的解。由于测量或者计算误差，我们处理的实际矩阵是(或).

数据A(或b)的微小误差对解的影响如何？

？误差分析（外招不要求）线性方程组：A为非奇异矩阵，x为方39误差分析（外招不要求）记为,它的精确解为给常数项进行微小变化，即考察如下的方程组可表示为

,

其中该方程组的解为：

例：设方程组如下：

误差分析（外招不要求）记为,它的精确解为给常数40误差分析（外招不要求）

可以看到方城组的常数项的第2个分量只有的微小变化，方程组的解却变化很大.这样的方程组称为病态方程组.

如果矩阵A或常数项b的微小变化，引起方程组AX＝b解的巨大变化，则矩阵A称为“病态”矩阵(相对于方程组而言)，否则称方程组为“良态”方程组，称为“良态”矩阵.定义误差分析（外招不要求）可以看到方城组的常数项的第241误差分析（外招不要求）设有方程组

其中A为非奇异阵，x为准确解.

设是精确的，有误差，解为,

则利用有由

有

误差分析（外招不要求）设有方程组其中A为非奇异阵，x为42误差分析（外招不要求）

设A为非奇异阵Ax＝b≠0，且定理则

关于b有微小扰动的误差估计

设A为非奇异阵Ax＝b≠0，且定理如果，则关于A有微小扰动的误差估计误差分析（外招不要求）设A为非奇异阵Ax＝b≠0，且定43误差分析（外招不要求）可见量愈小，由(或)的相对误差引起的解的相对误差就愈小；

量愈大，解的相对误差就可能愈大.

所以量实际上刻画了解对原始数据变化的灵敏程度，即刻画了方程组的“病态”程度，定义：设A为非奇异阵，称数为矩阵A的条件数.

注意：矩阵的条件数与范数有关.

误差分析（外招不要求）可见量愈小，由44误差分析（外招不要求）

由上面讨论知，当的条件数相对的大，即

方程组病态性质是方程组本身的特性.的条件数愈大，方程组的病态程度愈严重，也就愈难用一般的计算方法求得比较准确的解.时，是“病态”的(即是“病态”矩阵，或者说是坏条件的，相对于解方程组).

当的条件数相对的小，则是“良态”的(或者说是好条件的).误差分析（外招不要求）由上面讨论知，当的条件数相45误差分析（外招不要求）常用的条件数有

(1)

当A为对称矩阵时，

其中为A的绝对值最大和绝对值最小的特征值.

(2)A的谱条件数

误差分析（外招不要求）常用的条件数有(1)当A46误差分析（外招不要求）

例：已知希尔伯特（Hilbert）矩阵解：计算的条件数.

,408,6/11133==¥-¥HH所以的条件数

误差分析（外招不要求）例：已知希尔伯特（Hilbert）矩47误差分析（外招不要求）

可见，要判别一个矩阵是否病态需要计算条件数而计算比较费劲，最好在计算中能发现病态情况.计算中有如下判断：

(1)如果在的三角约化时(尤其是用主元素消去法解时)出现小主元，对大多数矩阵来说，是病态矩阵.

(2)

系数矩阵的行列式值相对说很小，或系数矩阵某些行近似线性相关，这时可能病态.

(3)

系数矩阵元素间数量级相差很大，并且无一定规则，可能病态.误差分析（外招不要求）可见，要判别一个矩阵是否病态需48误差分析（外招不要求）

病态方程组的求解处理：（1）对于病态方程组可采用高精度的算术运算（采用双倍字长进行运算）。（2）采用预处理方法，即将AX＝b转化为一组等价方程组选择非奇异矩阵使

一般选择为对角阵或者三角矩阵.误差分析（外招不要求）病态方程组的求解处理：（1）对49定理2.2

对及f∈Rn

都收敛(B)<1第二节矩阵和向量的范数

三、迭代法的收敛性定理2.1

对某种迭代式若方程的精确解为，则:0kB定理2.4

若Ax=b中的A式严格对角占优矩阵，则Jacobi和G-S迭代均收敛。对角占优矩阵：严格对角占优矩阵：Buthey,youdon’tseriouslyexpectmetocomputeBk

wheneverIwanttochecktheconvergence,doyou?定理2.3

对迭代式若迭代矩阵满足||B||<1，则：对∈Rn该迭代收敛。||A||≥(A)定理2.3

对迭代式若迭代矩阵满足||B||<1，则：对∈Rn该迭代收敛。定理2.3

对迭代式若迭代矩阵满足||B||<1，则：对∈Rn该迭代收敛。定理2.3

对迭代式若迭代矩阵满足||B||<1，则：对∈Rn该迭代收敛。定理2.2第二节矩阵和向量的范数

三、迭代法的收敛性P219例4：对方程组讨论其Jacobi和G-S迭代是否收敛解：求迭代矩阵判别其谱半径是否小于1第二节矩阵和向量的范数

三、迭代法的收敛性P219例4：对第六章逐次逼近法lz课件第六章逐次逼近法lz课件迭代法收敛性定理

SOR

迭代收敛的必要条件是

0<<2。证：设1,

...,n

是BS=(D-L)-1[(1-)D+U]的n

个特征值，则SOR

迭代收敛(BS)<1

迭代法收敛性定理SOR迭代收敛的必要条件是0<定理

Bk0(B)<1证明：“”若是B

的eigenvalue,则k

是Bk

的eigenvalue。

则[(B)]k=[max||]k=|mk|(Bk)

||Bk||0(B)<1“”首先需要一个引理/*Lemma*/对任意

>0,存在算子范数||·||

使得||A||(A)+

。

由

(B)<1可知存在算子范数||·||使得||B||<1。||Bk||||B||k0ask

Bk

0迭代从任意向量出发收敛Bk0(B)<1

证明：对A

做Jordan分解，有，其中，，i

为A的eigenvalue。令，则有易证：是由导出的算子范数。所以只要取<

，就有||A||<(A)+

。定理Bk0(B)<1证明：“第二节矩阵和向量的范数

作业题P260习题14(1)（判断及论证其Jacobi和G-S迭代是否收敛）P260习题14(2)（判断及论证其Jacobi和G-S迭代是否收敛）第二节矩阵和向量的范数

作业题P260习题146.3非线性方程的迭代法一、简单迭代法二、Newton迭代法三、弦截法6.3非线性方程的迭代法一、简单迭代法57第三节非线性方程的迭代法

一、简单迭代法1.思想2.简单迭代法几何意义f(x)=0x=(x)等价变换f(x)的根(x)的不动点取一个初值x0

代入迭代式xk+1=(xk)(k=0~∞)，得到序列{xk}若k→∞时，xk→α则α是f(x)=0的根，即有：f(α)=0构造一：(x)=x-f(x)x=(x)=x-f(x)<=>f(x)=0构造二：(x)=x-k(x)·f(x)x=(x)=x-k(x)·f(x)<=>f(x)=0问题：怎样的(x)可使迭代xk+1=(xk)收敛？0第三节非线性方程的迭代法

一、简单迭代法1.思想2.简单迭2.简单迭代法几何意义Ox*x2x1x0xy2.简单迭代法几何意义Ox*x259xyy=xxyy=xxyy=xxyy=xx*x*x*x*y=g(x)y=g(x)y=g(x)y=g(x)x0p0x1p1x0p0x1p1x0p0x1p1x0p0x1p1xyy=xxyy=xxyy=xxyy=xx*60第三节非线性方程的迭代法

一、简单迭代法P224例1用迭代法求方程f(x)=2x3-x-1=0的根解(1)方程等价化为(2)方程等价化为收敛！发散！第三节非线性方程的迭代法

一、简单迭代法P224例1用迭第三节非线性方程的迭代法

一、简单迭代法例2收敛！发散！第三节非线性方程的迭代法

一、简单迭代法例2收敛！发散！第三节非线性方程的迭代法

一、简单迭代法3.简单迭代法收敛条件定理3.1：考虑方程x=(x),(x)C[a,b],若(I)当x[a,b]时，(x)[a,b]；(II)0L<1对x[a,b]均有

|’(x)|L<1成立。则x=(x)在[a,b]内有唯一根α且对

x0[a,b]，且xk+1=(xk)k→∞时，xk→α且应用：(1)可用于控制误差：要得到的解，只要(2)可用于估算k值：要得到的解，只要k满足第三节非线性方程的迭代法

一、简单迭代法3.简单迭代法收敛§3Fixed-PointIteration证明：①x=(x)在[a,b]上有解令f(x)至少有一个零点②x=(x)在[a,b]上解唯一？反证：若不然，设还有，则在和之间。而③当k

时，

xkα

？§3Fixed-PointIteration证明：①④⑤可用来控制收敛精度L越收敛越快小④⑤可用来控制收敛精第三节非线性方程的迭代法

一、简单迭代法例2第三节非线性方程的迭代法

一、简单迭代法例2第三节非线性方程的迭代法

一、简单迭代法4.迭代过程的局部收敛性(p224)设(x)在x=(x)的根α附近有连续一阶导数，且|’(α)|<1则迭代过程xk+1=(xk)在α附近具有局部收敛性，即xk→α证：∵’(x)在α附近连续，且|’(α)|<1∴存在充分小的领域△：|x-α|≤δ

，使②|’(α)|≤L<1由微分中值定理：(x)-(α)=’(ξ)(x-α)∵(α)=α∴当x∈△，ξ∈△时，有下式成立①x∈△=[α-δ,α+δ]时，(x)∈△=[α-δ,α+δ]由条件①②知(x)在△区间上满足定理3.1的条件∴(x)在△中任取初值x0迭代均收敛。第三节非线性方程的迭代法

一、简单迭代法4.迭代过程的局部第三节非线性方程的迭代法

一、简单迭代法P225例2：求方程x=e-x在x=0.5附近的一个根，要求精度δ=10-3取k=11，此时计算结果见P226表3-1解：|’(α)|=|(e-x)’|=|-e-x|=e-x连续，且x∈[0.5,0.7]时，|’(α)|≤0.61

故迭代格式对x0=0.5收敛误差控制：第三节非线性方程的迭代法

一、简单迭代法P225例2：求方第三节非线性方程的迭代法

一、简单迭代法5.迭代过程的收敛速度p阶收敛：若p≥1,c>0p,c∈R满足：则称迭代法p阶收敛。线性收敛：p=1

平方收敛：p=2显然：p越大，收敛速度越快。E问题：p难以确定。问题：从可见

L值越小，收敛越快，

L值越大，收敛越慢L<1但L→1时，收敛速度很慢。问题：如何定量衡量收敛速度？第三节非线性方程的迭代法

一、简单迭代法5.迭代过程的收敛第三节非线性方程的迭代法

一、简单迭代法定理3.2(P226)：若x=(x)中，(x)在根x=α附近有：=Xk+1=α为一固定常数第三节非线性方程的迭代法

一、简单迭代法定理3.2(P22P226例3f(α)≡0，且f’(α)≠0，证明由建立的迭代法至少是平方收敛。证明：由定理3.2，只需证明’(α)＝0P226例3f(α)≡0，且f’(α)≠0，证明由证明：由第三节非线性方程的迭代法

二、Newton迭代法2.公式3.几何意义——切线法4.收敛性Newton迭代法至少是平方收敛的。xyαx0x1x21.构造对f(x)=0，可构造x=(x)=x-k(x)·f(x)(k(x)≠0)作为迭代函数由定理3.1’(x)在f(x)=0的根α附近越小，局部收敛速度越快令’(α)＝0，即：’(α)

=1-k’(α)·f(α)-k(α)·f’(α)=1-k(α)·f’(α)=0若f’(α)≠0，即：α不是f(x)的重根（f(α)=0)则：k(α)=1/f’(α)取k(x)=1/f’(x)，有：第三节非线性方程的迭代法

二、Newton迭代法2.公式3第三节非线性方程的迭代法

二、Newton迭代法P229例4：用Newton迭代法计算x3-x-1=0在x=1.5附近的根α解：取x0=1.5代入计算：取x0=0代入计算：收敛！发散！近似解第三节非线性方程的迭代法

二、Newton迭代法P229第三节非线性方程的迭代法

二、Newton迭代法x*x0x0x0注：Newton’sMethod收敛性依赖于x0

的选取。第三节非线性方程的迭代法

二、Newton迭代法x*x0第三节非线性方程的迭代法

二、Newton迭代法5.算法设计（P232）(一)算法名称NEWT(X0,EPS,N)(二)存储方式1.设计FF(X)计算f(x)及FD(X)计算f’(x)2.K代表迭代次数（K>N超过最大迭代次数仍得不到解，停止)3.DT<=|xk+1-xk|代表误差（DT<EPS达到误差要求停止迭代）4.X记录xk+1的值，X0记录xk的值(三)算法描述1.输入初值X0，控制精度EPS，最大迭代次数N2.K<=13.K>N转8，否则C1=FF(X0),C2=FD(X0)4.C2<EPS停机（另选X0），否则X=X0-C1/C25.DT＝|X-X0|6.DT<EPS转7，否则X0<=X,K<=K+1，转37.输出X0，K8.停机第三节非线性方程的迭代法

二、Newton迭代法5.算法设第三节非线性方程的迭代法

二、Newton迭代法6.改进：Newton下山法防止Newton法发散，增加一个条件：即：要求|f(x)|单调下降，最后趋于0解决方法：引入系数得到xk后取λ依次为：1,1/2,1/4,1/8,…直到成立——下山因子注:1.若取不到λ使得，则“下山失败”，另取初值x02.K值取到|xk+1-xk|<ε或|f(xk)|<ε迭代终止。Newton下山法公式P230例5第三节非线性方程的迭代法

二、Newton迭代法6.改进Newton法一步要计算f

和f’，相当于2个函数值，比较费时。现用f

的值近似f’，可少算一个函数值。x0x1切线

/*tangentline*/割线

/*secantline*/切线斜率

割线斜率需要2个初值x0

和x1。收敛阶为p≈1.618，比Newton法慢，且对初值要求同样高。第三节非线性方程的迭代法

三、弦截法终止条件|xk+1-xk|<ε同Newton法1.问题2.几何意义3.公式αNewton法一步要计算f和f’，相当于2个函数值，第三节非线性方程的迭代法

三、弦截法P229例4：用弦截法计算x3-x-1=0在x=1.5附近的根α解：取x0=1.5,x1=1.4,代入计算得：第三节非线性方程的迭代法

三、弦截法P229例4：用弦截第三节非线性方程的迭代法

作业题P261习题18(2)（用Newton法求方程的根）P262习题21(3)（用弦截法求方程的根）第三节非线性方程的迭代法

作业题P261习题186.4多根区间上的逼近求根一、单根——二分法二、重根6.4多根区间上的逼近求根一、单根——二分法80

第四节多根区间上的逼近求根

一、单根法——二分法（见第一章）

二、重根设f(x)=(x-α)mg(x)且g(x)≠0,即：α是f(x)的m重根(m≥2)建立迭代公式为注意区分Newton下山法公式m≥20<λ≤1第四节多根区间上的逼近求根

一、单根法——二分法（

第四节多根区间上的逼近求根

二、重根P234例7：求f(x)=x4-4x2+4=0的二重根的计算值.解：(1)Newton法(2)重根计算法m＝2

取初值x0＝1.5，计算结果见P235表3-3结论：(2)比(1)收敛快！第四节多根区间上的逼近求根

二、重根P234例7第六章逐次逼近法6.1解线性方程组的迭代法

6.2矩阵和向量的范数

6.3非线性方程的迭代法

6.4多根区间上的逼近求根第六章逐次逼近法6.1解线性方程组的迭代法836.1解线性方程组的迭代法一、迭代法的思想二、Jacobi迭代法三、Guass-Seidel迭代法6.1解线性方程组的迭代法一、迭代法的思想84第一节解线性方程组的迭代法

一、迭代法的思想1.问题2.思想直接法求解线性方程组Ax=b的过程中，系数矩阵A在不断变动，A的阶数较大时，占用内存很大，程序复杂，对编程技巧要求高。按照某种规则，通过已知元素或已经求得的元素求出后继元素，从而形成一个序列，由该序列的极限过程去逐步逼近数值问题的精确解。解决方法：求解过程中系数矩阵不变程序设计较简单的迭代法。第一节解线性方程组的迭代法

一、迭代法的思想1.问题2.第一节解线性方程组的迭代法

二、Jacobi迭代法例1

用简单迭代法解下列方程组解：我们分别从方程组的三个方程中分离出x1，x2，x3，得：据此可以建立迭代公式如下：当k－>∞时，X1（k）->1.1，X2（k）->1.2

，X3（k）->1.3第一节解线性方程组的迭代法

二、Jacobi迭代法例1第一节解线性方程组的迭代法

二、Jacobi迭代法1.解线性方程组的迭代法：将联立方程组的求解归结为重复计算一组彼此独立的线性表达式，从而简化问题。(i=1~n)考察一般形式的线性方程组：第一节解线性方程组的迭代法

二、Jacobi迭代法1.解第一节解线性方程组的迭代法

二、Jacobi迭代法(i=1~n)(k=0~+∞)写成迭代格式：含义：第k＋1次迭代出来的是由第k次迭代出来的加上一个修正项△xi得到的。随着△xi第一节解线性方程组的迭代法

二、Jacobi迭代法(i=第一节解线性方程组的迭代法

二、Jacobi迭代法2.矩阵表达原来方程：Ax＝b00LUD第一节解线性方程组的迭代法

二、Jacobi迭代法2.矩第一节解线性方程组的迭代法

二、Jacobi迭代法2.矩阵表达:A=D-L-U0000A=-L-UDBJfJ(k=0~+∞)Jacobi迭代矩阵公式第一节解线性方程组的迭代法

二、Jacobi迭代法2.矩第一节解线性方程组的迭代法

二、Jacobi迭代法Jacobi迭代矩阵公式(k=0~+∞)第一节解线性方程组的迭代法

二、Jacobi迭代法Jac第一节解线性方程组的迭代法

二、Jacobi迭代法例1用Jacobi迭代法解下列方程组据此可以建立迭代公式如下：D-1L+U第一节解线性方程组的迭代法

二、Jacobi迭代法例1用第一节解线性方程组的迭代法

二、Jacobi迭代法例2(P214例1)

用简单迭代法解下列方程组其矩阵形式如下：2.矩阵表达若取初值则迭代10次后可得

BJfJ第一节解线性方程组的迭代法

二、Jacobi迭代法例2(第一节解线性方程组的迭代法

二、Jacobi迭代法3.算法设计(1)由于Xi(k+1)=Xi(k)+△Xi,△Xi代表了误差，故可以用Xi(k+1)-Xi(k)控制精度，用Y[i]存储迭代结果Xi(k+1)，用X[i]存储迭代初值Xi(k)，用刻画精度。(2)控制运算量：为了防止收敛速度过慢或迭代不收敛（发散），设置最大迭代次数N以控制计算量。若迭代N次尚不能达到精度要求，则宣告迭代失败。第一节解线性方程组的迭代法

二、Jacobi迭代法3.算第一节解线性方程组的迭代法

二、Jacobi迭代法3.算法设计第一节解线性方程组的迭代法

二、Jacobi迭代法3.算第一节解线性方程组的迭代法

作业题P260习题14(1)（用G－S迭代法解方程组）P260习题14(2)（用Jacobi迭代法解方程组）第一节解线性方程组的迭代法

作业题P260习题1第一节解线性方程组的迭代法

三、Guass－Seidel迭代法例1

用G-S迭代法解下列方程组解：我们分别从方程组的三个方程中分离出x1，x2，x3，得：据此可以建立迭代公式如下：当k－>∞时，X1（k）->1.1，X2（k）->1.2

，X3（k）->1.3(k+1)(k+1)(k+1)第一节解线性方程组的迭代法

三、Guass－Seidel第一节解线性方程组的迭代法

三、Guass－Seidel迭代法1.解线性方程组的迭代法注：（1）Jacobi迭代中没有充分利用已经计算出来的信息，例如在计算xi时，x1～xi-1都已经计算出来了，一般而言，xi(k+1)要比xi(k)更准确些。（2）在本题中G-S的迭代效果比Jacobi好，一般而言G-S的收敛效果比Jacobi好，收敛更快，但也不一定。有时可能G-S比Jacobi收敛更慢，甚至G-S发散，Jacobi反而收敛。第一节解线性方程组的迭代法

三、Guass－Seidel第一节解线性方程组的迭代法

三、Guass－Seidel迭代法(i=1~n)(k=0~+∞)写成迭代格式：△xi1.迭代公式第一节解线性方程组的迭代法

三、Guass－Seidel第一节解线性方程组的迭代法

三、Guass－Seidel迭代法2.矩阵表达原来方程：Ax＝b00第一节解线性方程组的迭代法

三、Guass－Seidel第一节解线性方程组的迭代法

三、Guass－Seidel迭代法2.矩阵表达:A=D-L-U0000A=-L-UDBGfG(k=0~+∞)G-S迭代矩阵公式第一节解线性方程组的迭代法

三、Guass－Seidel第一节解线性方程组的迭代法

二、Jacobi迭代法例1用G-S迭代法解下列方程组解第一节解线性方程组的迭代法

二、Jacobi迭代法例1用第一节解线性方程组的迭代法

二、Jacobi迭代法例1用G-S迭代法解下列方程组据此可以建立迭代公式如下：(D-L)-1U(D-L)-1b第一节解线性方程组的迭代法

二、Jacobi迭代法例1用第一节解线性方程组的迭代法

三、Guass－Seidel迭代法3.Jacobi迭代与G-S迭代比较Jacobi迭代矩阵公式G-S迭代矩阵公式Jacobi迭代公式G-S迭代公式第一节解线性方程组的迭代法

三、Guass－SeidelSOR迭代称为SOR迭代矩阵为了得到更好的收敛效果，可在修正项前乘以一个参数w，于是就得到所谓的逐次超松弛迭代法，简称SOR迭代，其中w

称为松弛因子。此时在GS迭代中解得SOR迭代称为SOR迭代矩阵为了得到更好的收敛效果，可105Jacobi、GS和SOR算法

Jacobi算法

GS算法

SOR算法Jacobi、GS和SOR算法Jacobi算法G106举例解：

例：解线性方程组取初始向量

x(0)=(0,0,0)，迭代过程中小数点后保留4位。Jacobi迭代格式令则迭代得：x(1)=(0.5000,2.6667,-2.5000)Tx(21)=(2.0000,3.0000,-1.0000)T举例解：例：解线性方程组取初始向量x(0)=(0,107举例（续）GS迭代格式得x(1)=(0.5000,2.8333,-1.0833)Tx(9)=(2.0000,3.0000,-1.0000)T举例（续）GS迭代格式得x(1)=(0.5000,108举例（续）SOR迭代格式取w=1.1，得x(1)=(0.5500,3.1350,-1.0257)Tx(7)=(2.0000,3.0000,-1.0000)T如何确定SOR迭代中的最优松弛因子是一件很困难的事。

举例（续）SOR迭代格式取w=1.1，得x(1)=109几种迭代法的统一

Jacobi迭代

GS迭代

SOR迭代A=M-

NM=

D,N=M–A=L+UM=

D–L,N=U几种迭代法的统一Jacobi迭代GS迭代SOR迭110第一节解线性方程组的迭代法

作业题P260习题14(1)（用G－S迭代法解方程组）P260习题14(2)（用Jacobi迭代法解方程组）第一节解线性方程组的迭代法

作业题P260习题16.2矩阵和向量的范数一、向量范数二、矩阵范数三、迭代法的收敛性6.2矩阵和向量的范数一、向量范数112第二节矩阵和向量的范数

一、向量范数1.问题非负性齐次性三角不等式向量范数

||||是一个满足三个条件的实数：2.定义范数是一个数||||∈Rn为了研究迭代过程的收敛性，要对向量的“大小”引入某种度量例如：向量的长度：即：第二节矩阵和向量的范数

一、向量范数1.问题非负性齐次性三第二节矩阵和向量的范数

一、向量范数在Rn中,常用的几种向量范数有:3.四种向量范数1-范数(2)2-范数(3)∞-范数(4)推广p-范数P=1P=2P=∞第二节矩阵和向量的范数

一、向量范数在Rn中,常用的几种向第二节矩阵和向量的范数

一、向量范数P202例1：设x=(1,2,-3,-4)T,则4.性质第二节矩阵和向量的范数

一、向量范数P202例1：设x第二节矩阵和向量的范数

二、矩阵范数1.矩阵算子范数定义(1)

非负性

(2)齐次性(3)三角不等式

(4)*相容性(5)*相容性2.性质是向量范数第二节矩阵和向量的范数

二、矩阵范数1.矩阵算子范数定义(（A所有行绝对和的最大值）（A所有列绝对和的最大值）（ATA最大特征值开方）（A所有元素平方和开方）第二节矩阵和向量的范数

二、矩阵范数3.四种矩阵范数行和范数：列和范数：谱范数：F-范数：P204例2（A所有行绝对和的最大值）（A所有列绝对和的最大值）（ATA第二节矩阵和向量的范数

二、矩阵范数（1）求ATA（2）求ATA的全部特征值（3）求||A||2第二节矩阵和向量的范数

二、矩阵范数（1）求ATA（2）求第二节矩阵和向量的范数

二、矩阵范数4.矩阵的谱半径（P204定义1.4）(A)=，其中i

为A∈Rn×n的特征根。谱半径与矩阵范数的关系：||A||≥(A)ReIm(A)将任意一个特征根所对应的特征向量代入证明：由算子范数的相容性，得到由的任意性：第二节矩阵和向量的范数

二、矩阵范数4.矩阵的谱半径（P2第二节矩阵和向量的范数

二、矩阵范数例3：求矩阵B的谱半径(B)，其中

解：第二节矩阵和向量的范数

二、矩阵范数例3：求矩阵B的谱半径误差分析（外招不要求）线性方程组：

A为非奇异矩阵，x为方程组的精确解.

估计x-y,其中y是的解。由于测量或者计算误差，我们处理的实际矩阵是(或).

数据A(或b)的微小误差对解的影响如何？

？误差分析（外招不要求）线性方程组：A为非奇异矩阵，x为方121误差分析（外招不要求）记为,它的精确解为给常数项进行微小变化，即考察如下的方程组可表示为

,

其中该方程组的解为：

例：设方程组如下：

误差分析（外招不要求）记为,它的精确解为给常数122误差分析（外招不要求）

可以看到方城组的常数项的第2个分量只有的微小变化，方程组的解却变化很大.这样的方程组称为病态方程组.

如果矩阵A或常数项b的微小变化，引起方程组AX＝b解的巨大变化，则矩阵A称为“病态”矩阵(相对于方程组而言)，否则称方程组为“良态”方程组，称为“良态”矩阵.定义误差分析（外招不要求）可以看到方城组的常数项的第2123误差分析（外招不要求）设有方程组

其中A为非奇异阵，x为准确解.

设是精确的，有误差，解为,

则利用有由

有

误差分析（外招不要求）设有方程组其中A为非奇异阵，x为124误差分析（外招不要求）

设A为非奇异阵Ax＝b≠0，且定理则

关于b有微小扰动的误差估计

设A为非奇异阵Ax＝b≠0，且定理如果，则关于A有微小扰动的误差估计误差分析（外招不要求）设A为非奇异阵Ax＝b≠0，且定125误差分析（外招不要求）可见量愈小，由(或)的相对误差引起的解的相对误差就愈小；

量愈大，解的相对误差就可能愈大.

所以量实际上刻画了解对原始数据变化的灵敏程度，即刻画了方程组的“病态”程度，定义：设A为非奇异阵，称数为矩阵A的条件数.

注意：矩阵的条件数与范数有关.

误差分析（外招不要求）可见量愈小，由126误差分析（外招不要求）

由上面讨论知，当的条件数相对的大，即

方程组病态性质是方程组本身的特性.的条件数愈大，方程组的病态程度愈严重，也就愈难用一般的计算方法求得比较准确的解.时，是“病态”的(即是“病态”矩阵，或者说是坏条件的，相对于解方程组).

当的条件数相对的小，则是“良态”的(或者说是好条件的).误差分析（外招不要求）由上面讨论知，当的条件数相127误差分析（外招不要求）常用的条件数有

(1)

当A为对称矩阵时，

其中为A的绝对值最大和绝对值最小的特征值.

(2)A的谱条件数

误差分析（外招不要求）常用的条件数有(1)当A128误差分析（外招不要求）

例：已知希尔伯特（Hilbert）矩阵解：计算的条件数.

,408,6/11133==¥-¥HH所以的条件数

误差分析（外招不要求）例：已知希尔伯特（Hilbert）矩129误差分析（外招不要求）

可见，要判别一个矩阵是否病态需要计算条件数而计算比较费劲，最好在计算中能发现病态情况.计算中有如下判断：

(1)如果在的三角约化时(尤其是用主元素消去法解时)出现小主元，对大多数矩阵来说，是病态矩阵.

(2)

系数矩阵的行列式值相对说很小，或系数矩阵某些行近似线性相关，这时可能病态.

(3)

系数矩阵元素间数量级相差很大，并且无一定规则，可能病态.误差分析（外招不要求）可见，要判别一个矩阵是否病态需130误差分析（外招不要求）

病态方程组的求解处理：（1）对于病态方程组可采用高精度的算术运算（采用双倍字长进行运算）。（2）采用预处理方法，即将AX＝b转化为一组等价方程组选择非奇异矩阵使

一般选择为对角阵或者三角矩阵.误差分析（外招不要求）病态方程组的求解处理：（1）对131定理2.2

对及f∈Rn

都收敛(B)<1第二节矩阵和向量的范数

三、迭代法的收敛性定理2.1

对某种迭代式若方程的精确解为，则:0kB定理2.4

若Ax=b中的A式严格对角占优矩阵，则Jacobi和G-S迭代均收敛。对角占优矩阵：严格对角占优矩阵：Buthey,youdon’tseriouslyexpectmetocomputeBk

wheneverIwanttochecktheconvergence,doyou?定理2.3

对迭代式若迭代矩阵满足||B||<1，则：对∈Rn该迭代收敛。||A||≥(A)定理2.3

对迭代式若迭代矩阵满足||B||<1，则：对∈Rn该迭代收敛。定理2.3

对迭代式若迭代矩阵满足||B||<1，则：对∈Rn该迭代收敛。定理2.3

对迭代式若迭代矩阵满足||B||<1，则：对∈Rn该迭代收敛。定理2.2第二节矩阵和向量的范数

三、迭代法的收敛性P219例4：对方程组讨论其Jacobi和G-S迭代是否收敛解：求迭代矩阵判别其谱半径是否小于1第二节矩阵和向量的范数

三、迭代法的收敛性P219例4：对第六章逐次逼近法lz课件第六章逐次逼近法lz课件迭代法收敛性定理

SOR

迭代收敛的必要条件是

0<<2。证：设1,

...,n

是BS=(D-L)-1[(1-)D+U]的n

个特征值，则SOR

迭代收敛(BS)<1

迭代法收敛性定理SOR迭代收敛的必要条件是0<定理

Bk0(B)<1证明：“”若是B

的eigenvalue,则k

是Bk

的eigenvalue。

则[(B)]k=[max||]k=|mk|(Bk)

||Bk||0(B)<1“”首先需要一个引理/*Lemma*/对任意

>0,存在算子范数||·||

使得||A||(A)+

。

由

(B)<1可知存在算子范数||·||使得||B||<1。||Bk||||B||k0ask

Bk

0迭代从任意向量出发收敛Bk0(B)<1

证明：对A

做Jordan分解，有，其中，，i

为A的eigenvalue。令，则有易证：是由导出的算子范数。所以只要取<

，就有||A||<(A)+

。定理Bk0(B)<1证明：“第二节矩阵和向量的范数

作业题P260习题14(1)（判断及论证其Jacobi和G-S迭代是否收敛）P260习题14(2)（判断及论证其Jacobi和G-S迭代是否收敛）第二节矩阵和向量的范数

作业题P260习题146.3非线性方程的迭代法一、简单迭代法二、Newton迭代法三、弦截法6.3非线性方程的迭代法一、简单迭代法139第三节非线性方程的迭代法

一、简单迭代法1.思想2.简单迭代法几何意义f(x)=0x=(x)等价变换f(x)的根(x)的不动点取一个初值x