第三章迭代法

第三章迭代法第1页，课件共36页，创作于2023年2月§3.1二分法根的估计二分法第2页，课件共36页，创作于2023年2月根的估计引理3.1（连续函数的介值定理）设f(x)在[a,b]上连续，且f(a)f(b)<0，则存在x*(a,b)使f(x*)=0。例3.1证明x3

3x

1=0有且仅有3个实根，并确定根的大致位置使误差不超过

=0.5。解:单调性分析和解的位置选步长h=2,扫描节点函数值异号区间内有根第3页，课件共36页，创作于2023年2月f(x)=x3

3x

1第4页，课件共36页，创作于2023年2月二分法(更快的扫描法)条件:设f(x)在[a,b]上连续，f(x)=0在[a,b]上存在唯一解，且f(a)f(b)<0。记Step1:Iff(a0)f(x0)<0,thenx*(a0,x0)leta1=a0,b1=x0;Elsex*(x0,b0)leta1=x0,b1=b0;Letx1=(a1+b1)/2.

Stepk:Iff(ak-1)f(xk-1)<0,thenx*(ak-1,xk-1)letak=ak-1,bk=xk-1;Elsex*(xk-1,bk-1)letak=xk-1,bk=bk-1;Letxk=(ak+bk)/2.

收敛性及截断误差分析:第5页，课件共36页，创作于2023年2月例3.2x33x

1=0,[1,2],精度0.5e-1第6页，课件共36页，创作于2023年2月二分法优点算法简单收敛有保证只要f(x)连续缺点对区间两端点选取条件苛刻收敛速度慢难以推广至多维情形第7页，课件共36页，创作于2023年2月§3.2迭代法原理迭代法的思想

不动点原理

局部收敛性收敛性的阶

第8页，课件共36页，创作于2023年2月迭代法的思想

条件:f(x)=0在x0附近有且仅有一个根设计同解变形x=g(x)迭代式xk=g(xk-1),k=1,2,…如果收敛xk

x*,则x*是f(x)=0的根第9页，课件共36页，创作于2023年2月不动点原理(迭代过程收敛)定理3.1(不动点原理)设映射g(x)在[a,b]上有连续的一阶导数且满足1o

封闭性：x[a,b],g(x)[a,b],2o

压缩性：L(0,1)使对x[a,b],|g'(x)|L,则在[a,b]上存在唯一的不动点x*，且对x0[a,b],xk=g(xk-1)收敛于x*。进一步，有误差估计式

后验估计先验估计算法设计中迭代结束条件:近似使用|xk-xk-1|<

第10页，课件共36页，创作于2023年2月不动点原理例3.3x3

x

1=0，[1,2],x0=1.5,第11页，课件共36页，创作于2023年2月不动点原理证明步骤解的存在性;解的唯一性;解的收敛性;误差估计式。第12页，课件共36页，创作于2023年2月局部收敛性(格式收敛)定理3.2（局部收敛性）设g’(x)连续,则存在充分靠近x*的初值，使迭代收敛于x*。证明：利用定理3.1,取L=

具有局部收敛性的迭代计算上不一定收敛，它是否收敛还要看初值是否取的恰当；而不具有局部收敛性的迭代对任何初值都不可能收敛。应用中:近似使用|g'(x0)|<1判断第13页，课件共36页，创作于2023年2月收敛性的阶(局部收敛速度)定义3.1当xkx*，记ek=x*-xk，若存在实数p，使ek+1/epk

c0，则称{xk}有p阶收敛速度。线性收敛p=1平方收敛p=2

第14页，课件共36页，创作于2023年2月收敛性的阶(局部收敛速度)定理3.3设xk=g(xk-1)

x*，则(1)当g'(x*)0时，{xk}线性收敛；(2)当g'(x*)=0,而g''(x*)0时，{xk}平方收敛。

证明(2)第15页，课件共36页，创作于2023年2月3.3Newton迭代法和迭代加速

牛顿(Newton)迭代法

“迭代－加速”技术（略）第16页，课件共36页，创作于2023年2月牛顿(Newton)迭代法原理(1次近似,直线代替曲线)牛顿格式第17页，课件共36页，创作于2023年2月Newton法几何意义：切线法切线代替曲线第18页，课件共36页，创作于2023年2月Newton法局部收敛性单根：平方收敛m重根：线性收敛,f(x)=(x-x*)mq(x),q(x*)

0,例3.5（P56)Newton迭代法，计算3次达到4位有效数字计算4次达到4位有效数字越是精度要求高,Newton迭代法优势越明显第19页，课件共36页，创作于2023年2月“迭代－加速”技术(略)加快迭代过程的收敛速度将发散的迭代格式加工成收敛的若g’(x)在x*附近大约为D,改进xk

=g(xk-1)为例3.6（P57)第20页，课件共36页，创作于2023年2月§4解线性方程组的迭代法

1迭代思想2Jacobi迭代和Gauss-Seidel迭代3迭代的收敛性4迭代加速——逐次超松弛（SOR）法第21页，课件共36页，创作于2023年2月1迭代思想解大型稀疏型方程组比直接法存储量小条件:Ax=b解存在唯一设计同解变形x=Gx+f迭代式x(k)=Gx

(k-1)+f,k=1,2,…取初值x(0)，如果收敛x(k)

x*,则x*是Ax=b的解x(k)

x*第22页，课件共36页，创作于2023年2月2Jacobi迭代和Gauss-Seidel迭代例3.7解：变形第23页，课件共36页，创作于2023年2月Jacobi迭代Jacobi迭代初值取，精度要求

=10-3。计算得||x(6)

x(5)||

10-3.第24页，课件共36页，创作于2023年2月Gauss-Seidel迭代Gauss-Seidel迭代初值取，精度要求

=10-3。计算得||x(5)

x(4)||

10-3.第25页，课件共36页，创作于2023年2月编程计算公式Jacobi迭代Gauss-Seidel迭代迭代结束条件一般用||x(k)

x(k-1)||

问题(1)收敛性条件?(2)||x(k)

x(k-1)||

作为结束条件是否可靠?第26页，课件共36页，创作于2023年2月计算公式矩阵形式和分解：

A=L(下三角)+D(对角)+U(上三角)迭代

x(k)=Gx

(k-1)+f,k=1,2,…Jacobi迭代

G=-D-1(L+U)=I-D-1Af=D-1bGauss-Seidel迭代

G=-(L+D)-1Uf=(L+D)-1b第27页，课件共36页，创作于2023年2月3迭代的收敛性定理3.4设G的某种范数||G||<1，则x=Gx+f存在唯一解，且对任意初值，迭代序列x(k)=Gx

(k-1)+f收敛于x*，进一步有误差估计式证明思路：(1)解的存在唯一性;(2)解的收敛性;(3)误差估计式(习题)。

第28页，课件共36页，创作于2023年2月直接从Ax=b判断推论若A按行严格对角占优（），则解Ax=b的Jacobi迭代和Gauss-Seidel迭代均收敛。证明思路：用定理3.4.A严格对角占优，则无穷大范数||G||<1Jacobi迭代G=-D-1(L+U)(直接证||G||

<1)Gauss-Seidel迭代,令，先证存在某x,||x||

=1,使||Ĝ||

=||y||

再证当||x||

=1,有||y||

<1第29页，课件共36页，创作于2023年2月Jacobi迭代(直接证||G||

<1)G=-D-1(L+U)第30页，课件共36页，创作于2023年2月Gauss-Seidel迭代收敛性证明记迭代矩阵存在m,令那么且第31页，课件共36页，创作于2023年2月Gauss-Seidel迭代收敛性证明记，其中迭代矩阵那么存在k使得所以第32页，课件共36页，创作于2023年2月充分必要条件谱半径

(G)：G的特征值模的最大值定理3.5迭代x(k)=Gx

(k-1)+f对任意初值收敛

(G)<1.（证明较深，略）第33页，课件共36页，创作于2023年2月三种方法比较方法一(推论):从A判断,A严格对角占优，则Jacobi迭代和Gauss-Seidel迭代收敛,充分条件,最方便方法二(定理3.4):从G判断,有一种范数||G||<1,充分条件方法三(定理3.5):从G判断,谱半径

(G)<1,充要条件,最宽P63,例3.8（特征值的性质：特征值