非线性方程的数值解法.ppt

《非线性方程的数值解法.ppt》由会员分享，可在线阅读，更多相关《非线性方程的数值解法.ppt（19页珍藏版）》请在三一办公上搜索。

1、4 牛顿法,一、牛顿迭代公式的推导(Taylor展开法),思想：非线性方程线性化（以直代曲）,取 x0 x*，将 f(x)在 x0 做一阶Taylor展开:,，在 x0 和 x 之间,将(x*x0)2 看成高阶小量，则有：,令,Newton Raphson迭代格式,称之为牛顿拉夫森方法，简称牛顿法.,解：,等价于求方程 的正根,解法一：,等价于求方程 的正根,解法二：,等价于求方程 的正根,证明：Newtons Method 事实上是一种特殊的不动点迭代 其中，则,收敛,由 Taylor 展开：,只要，则令 可得结论。,Th2.5,有根,根唯一,产生的序列单调有界保证收敛,证明省略。,证明省略

2、。,注：Newtons Method 收敛性依赖于x0 的选取。,x*,重根 加速收敛法：,Q1:若，Newtons Method 是否仍收敛？,设 x*是 f 的 n 重根，则：且。,因为 Newtons Method 事实上是一种特殊的不动点迭代,其中，则,A1:有局部收敛性，但重数 n 越高，收敛越慢。,Q2:如何加速重根情况时的收敛速度？,A2:将求 f 的重根转化为求另一函数的单根。,令，则 f 的重根=的单根。,求复根 Newton 公式中的自变量可以是复数,记 z=x+i y,z0 为初值，同样有,设,代入公式，令实、虚部对应相等，可得,5 弦割法与抛物线法,割线,切线斜率割线斜

3、率,需要2个初值 x0 和 x1。,Newtons Method每一步要计算，为了避免计算导数值，现用 的近似，得到弦割法（割线法）。,x2,一、弦割法,收敛速度介于Newton and Bisection 之间,Muller方法的思想来源于弦割法:利用3个已知点构造一条抛物线,取其与x轴的交点构造下一次迭代值.,x*,二、抛物线法(Muller),几何图示,xk+1,Muller方法的具体实现:,设已知三个点,则过上述三个点的抛物线方程为:,取该抛物线与x轴的交点作为下一次迭代值,即,然后取新的相邻的三次迭代值重复上述过程,即为Muller方法.,Muller方法中抛物线根的计算方法:,首先

4、要将抛物线化为规范形式:,引入新的变量,其中,的两个零点为:,可以写为：,取 的两个零点中靠近 的那个零点,则有,Muller方法的迭代公式为:,具体计算步骤见教材P39.,算法:Muller方法给定初始近似值 x0，x1，x2,求f(x)=0 的根.输入:初值 x0，x1，x2;容许误差 TOL.输出:近似解 x.Step 1 Set i=1;Step 4 If|t4(x2-x1)|TOLStep 2 do steps 3-7 then Output(x);STOP;Step 3 Compute t3=(x2 x1)/(x1 x0);Step 5 Set i+;d3=1+t3;Step 6 Set x0=x1,x1=x2,x2=x;a=f(x0)t32-f(x1)t3d3+f(x2)t3;Step 7 goto Step 2.b=f(x0)t32-f(x1)d32+f(x2)(t3+d3);c=f(x2)d3;t4=-2c/b+sign(b)sqrt(b2-4ac);x=x2+t4(x2-x1);,Muller法的优点：初值的选取范围比Newton法和弦割法宽,但计算量比弦割法大。进一步研究可知Muller法可求复根。,