[工学]第二章 方程组迭代法.pptVIP

《数值分析》 主讲教师 谭高山 第二章 非线性方程（组）的迭代法 2.0 引言 2.1 求实根的二分法 2.2 迭代法及收敛性 局部收敛性与收敛阶 2.3 Steffensen加速迭代法 2.4 Newton迭代法 Newton下山法 弦位法（割线法） 2.5* 解非线性方程组的Newton迭代法 2.6 *最速下降迭代法（规划法）解非线性方程组 2.0 引言 2.1 求实根的二分法 The Bisection Method 2.2 迭代法及收敛性 2.2 迭代法及收敛性 2.2 迭代法及收敛性 2.2 迭代法及收敛性 局部收敛性 局部收敛性 局部收敛性 局部收敛性 收敛阶 收敛阶 收敛阶 2.3 Steffensen加速技巧 2.3 Steffensen加速技巧 2.3 Steffensen加速技巧 2.4 Newton迭代法 几何意义（切线法） Newton法局部收敛定理 Newton下山法 从Newton迭代法的收敛性可见，他仅是局部收敛的，为扩大收敛范围，可改进迭代公式为： 重根的情形 弦位法（割线法） 几何意义 2.5* 解非线性方程组的Newton迭代法 2.6 最速下降迭代法（规划法）解非线性方程组 据此抽出不动点形式，进而构造Newton迭代公式： * * 局限性：只能求一个实根，不能辨识重根或求复根，收敛速度对任何函数均一样且慢，对多元方程的情形须做修改。 INPUT a,b;TOL; maximum number of iteration N.OUTPUT approximation solution p or message of failure.Step 1 Set i=1;FA=f(a),give N Step 2 while i= N do step 3-6Step 3 set p=a+(b-a)/2; FP=f(p) Step 4 If FP=0 or (b-a)/2TOL then OUTPUT p; STOP. Step 5 Set i=i+1 Step 6 If FA·FP0 then set a=p ;FA=FP else set b=pStep 7 OUTPUT(‘method failed after N iteration,N=’,N)STOP Describe the Algorithm of Bisection 迭代法 求非线性方程f(x)=0的根的迭代解法是指从给定的 一个或者几个初始值出发，按某种方法产生一个解的序列， 该序列称为迭代序列，使得此序列收敛于非线性方程f(x)=0的 一个根。 迭代法可分为两类： （1）从任何初始值出发都收敛（全局收敛）； （2）只有初始值充分接近于所求根时才收敛（局部收敛）。 方程f(x)=0改为等价形式x=g(x)，若x1满足x1=g(x1) 则称x1为g(x)的一个不动点， x1也是f(x)=0的一个根。 构造不动点迭代法： ，g(x)成为迭代函数， 若 固定点迭代： 迭代法的几何意义 通常将方程 f(x)=0 化为与它同解的方程 的方法不止一种,有的收敛,有的不收敛,这取决于 的性态。 (a) (b) 上式的最后两项分别用于事后估计和事先估计。 定义： 定理： （例题中迭代公式的选取） 证明： 例：试用不同迭代法 收敛阶（刻画收敛速度的标准之一）： 定理： 证明： Steffensen加速技巧的几何意义由Aitken给出。 证明:注意到 定理2.3