计算方法迭代法.ppt

3.1二分法3.2迭代法原理3.3Newton迭代法和迭代加速3.4解线性方程组的迭代法第三章迭代法根的估计01二分法023.1二分法根的估计f(x)=x3?3x?1二分法”条件:设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.例3.2x3?3x?1=0,[1,2],精度0.5e-1算法简单收敛有保证只要f(x)连续优点对区间两端点选取条件苛刻收敛速度慢缺点二分法迭代法的思想不动点原理局部收敛性收敛性的阶3.2迭代法原理条件:f(x)=0在x0附近有且仅有一个根设计同解变形x=g(x)迭代式xk=g(xk-1),k=1,2,…如果收敛xk?x*,则x*是f(x)=0的根迭代法的思想不动点原理(迭代过程收敛)后验估计先验估计算法设计中迭代结束条件:近似使用|xk-xk-1|?证明步骤解的存在性;解的唯一性;解的收敛性;误差估计式。01例3.302不动点原理证明：利用定理3.1,取L=而不具有局部收敛性的迭代对任何初值都不可能收敛。定理3.2（局部收敛性）设g’(x)连续,则存在充分靠近x*的初值，使迭代收敛于x*。具有局部收敛性的迭代计算上不一定收敛，它是否收敛还要看初值是否取的恰当；应用中:近似使用|g(x0)|1判断局部收敛性(格式收敛)收敛性的阶(局部收敛速度)定义3.1当xk?x*，记ek=x*-xk，若存在实数p，使ek+1/epk?c?0，则称{xk}有p阶收敛速度。线性收敛p=1平方收敛p=2定理3.3设xk=g(xk-1)?x*，则(1)当g(x*)?0时，{xk}线性收敛；(2)当g(x*)=0,而g(x*)?0时，{xk}平方收敛。3.3Newton迭代法和迭代加速AB“迭代－加速”技术牛顿(Newton)迭代法原理(1次近似,直线代替曲线)牛顿格式牛顿(Newton)迭代法Newton法几何意义：切线法切线代替曲线Newton法局部收敛性加快迭代过程的收敛速度将发散的迭代格式加工成收敛的若g’(x)在x*附近大约为D,改进xk=g(xk-1)为例3.6（P57)01030204“迭代－加速”技术迭代思想Jacobi迭代和Gauss-Seidel迭代迭代的收敛性迭代加速——逐次超松弛（SOR）法4解线性方程组的迭代法解大型稀疏型方程组比直接法存储量小01条件:Ax=b解存在唯一02设计同解变形x=Gx+f03迭代式x(k)=Gx(k-1)+f,k=1,2,…04取初值x(0)，如果收敛x(k)?x*,则x*是Ax=b的解05x(k)?x*061迭代思想2Jacobi迭代和Gauss-Seidel迭代例3.7解：变形壹贰STEP03STEP01STEP02Jacobi迭代初值取，精度要求?=10-3。计算得||x(6)?x(5)||??10-3.Jacobi迭代213Gauss-Seidel迭代初值取，精度要求?=10-3。计算得||x(5)?x(4)||??10-3.Gauss-Seidel迭代Jacobi迭代01迭代结束条件一般用||x(k)?x(k-1)||??03Gauss-Seidel迭代02问题(1)收敛性条件?(2)||x(k)?x(k-1)||??作为结束条件是否可靠?04编程计算公式