非线性方程的求根方法.pptx

非线性方程的求根方法非线性方程的求根方法Newton迭代格式迭代格式Newton迭代法的收敛性迭代法的收敛性Newton迭代法的变形迭代法的变形数值实验练习题数值实验练习题牛顿法是方程求根问题的一个极其基本的、十分牛顿法是方程求根问题的一个极其基本的、十分重要的算法。重要的算法。基本思想基本思想：是将非线性方程：是将非线性方程f(x)=0逐步线性化而逐步线性化而形成迭代公式。形成迭代公式。具体作法：具体作法：已知方程已知方程 f(x)=0的根的根 xk，将将 f(x)在在xk处作一阶泰勒展开处作一阶泰勒展开 所以所以f(x)=0可近似表示为可近似表示为 线性方程线性方程记其根为记其根为xk+1，则，则xk+1是方程是方程f(x)=0的一个新的近似根的一个新的近似根 这就是著名的这就是著名的牛顿迭代公式牛顿迭代公式，相应的，相应的迭代函数迭代函数是是几何意义：几何意义：牛顿法是在牛顿法是在x*的附近以的附近以xk做为第做为第k次迭代次迭代值，以值，以y=f(x)在点在点(xk,f(xk)的切线与的切线与x轴的交点轴的交点xk+1作作为为f(x)=0方程的根方程的根x*的第的第k+1次迭代近似值，如此反复次迭代近似值，如此反复下去，逐步逼近方程下去，逐步逼近方程f(x)=0的根的根x*。所以牛顿法又称切线法所以牛顿法又称切线法(k=0,1,2,)y=0 xk+1比比xk更接近于更接近于x*xkxk+1x*y=f(x)yxo几何意义几何意义:以切线代替曲线以切线代替曲线,求根求根 x*的近似值的近似值牛顿迭代法的一个应用牛顿迭代法的一个应用求正数平方根求正数平方根设设C 0,x2 C=0令令 f(x)=x2 C,则则牛顿迭代法求解牛顿迭代法求解 x2 C=0 的计算格式的计算格式化简化简,得得例例1 平方根迭代平方根迭代 (k=0,1,)的收敛性证明及收敛阶估计的收敛性证明及收敛阶估计.解解 对对k0,当当 xk 0时时(k=0,1,)(k 0)数列数列 xk 单减有下界单减有下界,故必有极限故必有极限.设为设为x*,对递推式对递推式取极限取极限,有有由此可知由此可知,平方根迭代平方根迭代 是是 平方收敛平方收敛.Newton迭代法的局部收敛性迭代法的局部收敛性牛顿法可以看成关于方程牛顿法可以看成关于方程的迭代公式的迭代公式如果如果x*为方程为方程f(x)=0 的一个单根，则有的一个单根，则有f(x*)=0,f(x*)0而而由定理由定理2.5知牛顿迭代公式具有局部收敛性。知牛顿迭代公式具有局部收敛性。由定理由定理2.6知知 Newton迭代法迭代法至少平方收敛至少平方收敛。因此用。因此用Newton法求单根的收敛速度是较快的。法求单根的收敛速度是较快的。则则所以只要所以只要 就有就有由定理由定理2.6知知 Newton迭代法平方收敛。迭代法平方收敛。由于牛顿迭代法是局部收敛的，故初值由于牛顿迭代法是局部收敛的，故初值x0应充分靠近应充分靠近根根x*才能保证收敛，这在一般情况下不容易做到。才能保证收敛，这在一般情况下不容易做到。实用中可先用二分法做求根预处理，二分若干次后实用中可先用二分法做求根预处理，二分若干次后得到较靠近根得到较靠近根x*的近似根的近似根x0，再用此根作为牛顿迭代，再用此根作为牛顿迭代法的初值来求根，可以达到取长补短的作用。法的初值来求根，可以达到取长补短的作用。缺陷缺陷1.被零除错误被零除错误2.程序死循环程序死循环y=arctan x方程方程:f(x)=x3 3x+2=0在重根在重根x*=1附近附近,f(x)近近似为零似为零对对 f(x)=arctan x存在存在 x0,Newton迭代迭代法陷入死循环法陷入死循环Newton迭代法陷入死循环的另一个例子迭代法陷入死循环的另一个例子取取 x0=0,(k=0,1,)f0 f0,f”0 f0,f”0 f0,f”0 牛顿法的计算步骤：牛顿法的计算步骤：1）给出初始近似值）给出初始近似值x0，及精度，及精度2）计算：按迭代公式）计算：按迭代公式计算出计算出x13）若）若 ，则转向，则转向4);否则否则 转向转向2)4）输出满足精度的根）输出满足精度的根x1，结束，结束例例2.5 用牛顿法解方程用牛顿法解方程 x=ex在在 x0=0.5 附近的根。附近的根。(k=0,1,)取取x00.5作为迭代初值。迭代结果如下表作为迭代初值。迭代结果如下表k0123x k0.50.571020.567160.56714经过经过3次迭代后得次迭代后得x 3 0.56714，比较例，比较例2.3和例和例2.5可发可发现牛顿迭代法的收敛速度是相当快的。现牛顿迭代法的收敛速度是相当快的。例例2.6 用牛顿法求用牛顿法求(k=0,1,)取初值取初值x 0 10，经，经4次迭代便得所要求的近似值次迭代便得所要求的近似值定定理理(全全局局收收敛敛性性):若若函函数数f(x)在在a，b 上上满满足条件足条件（1）f(a)f(b)0。则则方方程程 f(x)=0 在在a，b 上上有有唯唯一一根根 x*，且且由由初初值值x0按按牛牛顿顿迭迭代代公公式式求求得得的的序序列列 xk 二二阶收敛于阶收敛于x*。Newton迭代法的变形迭代法的变形弦截法弦截法牛顿法的突出优点是收敛速度快，但它有个明显牛顿法的突出优点是收敛速度快，但它有个明显的缺点，就是每迭代一次都要计算导数的缺点，就是每迭代一次都要计算导数f(xk),当当f(x)比较复杂时，计算比较复杂时，计算f(xk)可能十分麻烦。可能十分麻烦。为了避免牛顿法中的导数计算，我们用差商为了避免牛顿法中的导数计算，我们用差商 替换牛顿公式中的导数替换牛顿公式中的导数f(xk),则得则得到迭代公式到迭代公式 弦截公式弦截公式xk+1x0 x*xkpkp0设设x*是方程是方程 f(x)=0 的根的根,x0和和x1是是x*附近附近的两个点的两个点.Newton迭代法的变形迭代法的变形弦截法弦截法曲线曲线 y=f(x)在点在点(x0,f(x0)和点和点(x1,f(x1)处的处的割线与割线与x轴交点轴交点x1x0 x*(k=1,2,)例例2.8确定悬链线方程确定悬链线方程 已知已知 y(50)=y(0)+10求解方程求解方程:a=126.6324f=inline(u.*cosh(50/u)-u-10);a0=120;a=150;k=1;y0=f(a0);y=f(a);while abs(a0-a)0.0001 t=a-y*(a-a0)/(y-y0);a0=a;y0=y;a=t;y=f(a);k=k+1;endAnsK=6,a=126.6324f=inline(u.*cosh(50/u)-u-10);f1=inline(cosh(50/u)-50*sinh(50/u)/u-1);a0=150;y0=f(a0);k=1;er=1;while er0.0001 t=a0-f(a0)/f1(a0);er=abs(t-a0);a0=t;k=k+1;endAnsK=6,t=126.6324割线法割线法:切线法切线法:牛顿迭代法的收敛域问题牛顿迭代法的收敛域问题:用用牛牛顿顿迭迭代代法法求求解解复复数数方方程程 z3 1=0，该该方方程程在在复复平面上三个根分别是平面上三个根分别是z1=1选择中心位于坐标原点，边长选择中心位于坐标原点，边长为为2的正方形内的任意点作初始的正方形内的任意点作初始值，进行迭代，把收敛到三个值，进行迭代，把收敛到三个根的初值分为三类，并分别标根的初值分为三类，并分别标上不同颜色（例如红、黄、蓝）上不同颜色（例如红、黄、蓝）。对充分多的初始点进行实验，。对充分多的初始点进行实验，绘出牛顿迭代法对该方程的收绘出牛顿迭代法对该方程的收敛域彩色图。敛域彩色图。