资源描述:
《计算方法迭代法.ppt》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、第三章迭代法§3.1二分法§3.2迭代法原理§3.3Newton迭代法和迭代加速§3.4解线性方程组的迭代法§3.1二分法根的估计二分法根的估计引理3.1(连续函数的介值定理)设f(x)在[a,b]上连续,且f(a)f(b)<0,则存在x*(a,b)使f(x*)=0。例3.1证明x33x1=0有且仅有3个实根,并确定根的大致位置使误差不超过=0.5。解:单调性分析和解的位置选步长h=2,扫描节点函数值异号区间内有根f(x)=x33x1二分法条件:设f(x)在[a,b]上连续,f(x)=0在[a,b]上存在唯一解,且f(a)f(b)<0。记Step1:Iff(a0)
2、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.收敛性及截断误差分析:例3.2x33x1=0,[1,2],精度0.5e-1二分法优点算法简单收敛有保证只要f(x)连续缺点对区间两端点选取条件苛刻收敛速度慢§3.2迭代法原理迭代法的思想
3、不动点原理局部收敛性收敛性的阶迭代法的思想条件:f(x)=0在x0附近有且仅有一个根设计同解变形x=g(x)迭代式xk=g(xk-1),k=1,2,…如果收敛xkx*,则x*是f(x)=0的根不动点原理(迭代过程收敛)定理3.1(不动点原理)设映射g(x)在[a,b]上有连续的一阶导数且满足1o封闭性:x[a,b],g(x)[a,b],2o压缩性:L(0,1)使对x[a,b],
4、g'(x)
5、L,则在[a,b]上存在唯一的不动点x*,且对x0[a,b],xk=g(xk-1)收敛于x*。进一步,有误差估计式后验估计先验估计算法设计中迭代结束条件:近似使用
6、xk
7、-xk-1
8、<不动点原理证明步骤解的存在性;解的唯一性;解的收敛性;误差估计式。例3.3局部收敛性(格式收敛)定理3.2(局部收敛性)设g’(x)连续,则存在充分靠近x*的初值,使迭代收敛于x*。证明:利用定理3.1,取L=具有局部收敛性的迭代计算上不一定收敛,它是否收敛还要看初值是否取的恰当;而不具有局部收敛性的迭代对任何初值都不可能收敛。应用中:近似使用
9、g'(x0)
10、<1判断收敛性的阶(局部收敛速度)定义3.1当xkx*,记ek=x*-xk,若存在实数p,使ek+1/epkc0,则称{xk}有p阶收敛速度。线性收敛p=1平方收敛p=2定理3.3设xk=g(xk-1
11、)x*,则(1)当g'(x*)0时,{xk}线性收敛;(2)当g'(x*)=0,而g''(x*)0时,{xk}平方收敛。3.3Newton迭代法和迭代加速牛顿(Newton)迭代法“迭代-加速”技术牛顿(Newton)迭代法原理(1次近似,直线代替曲线)牛顿格式Newton法几何意义:切线法切线代替曲线Newton法局部收敛性单根:平方收敛m重根:线性收敛例3.5(P56)Newton迭代法,计算3次达到4位有效数字计算4次达到4位有效数字越是精度要求高,Newton迭代法优势越明显“迭代-加速”技术加快迭代过程的收敛速度将发散的迭代格式加工成收敛的若g’(x)在x*附近
12、大约为D,改进xk=g(xk-1)为例3.6(P57)§4解线性方程组的迭代法1迭代思想2Jacobi迭代和Gauss-Seidel迭代3迭代的收敛性4迭代加速——逐次超松弛(SOR)法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*2Jacobi迭代和Gauss-Seidel迭代例3.7解:变形Jacobi迭代Jacobi迭代初值取,精度要求=10-3。计算得
13、
14、x(6)x(5)
15、
16、10-3.Gauss
17、-Seidel迭代Gauss-Seidel迭代初值取,精度要求=10-3。计算得
18、
19、x(5)x(4)
20、
21、10-3.编程计算公式Jacobi迭代Gauss-Seidel迭代迭代结束条件一般用
22、
23、x(k)x(k-1)
24、
25、问题(1)收敛性条件?(2)
26、
27、x(k)x(k-1)
28、
29、作为结束条件是否可靠?计算公式矩阵形式和分解:A=L(下三角)+D(对角)+U(上三角)迭代x(k)=Gx(k-1)+f,k=1,2,…Jacobi迭代G=-D-1(L+U)=I-D-1Af=D-1bGa