数值分析课件第4章_非线性方程求根.ppt

由上述讨论可知，构造满足收敛定理条件的等价形 式一般难于做到。要构造收敛迭代格式有两个要素： 1. 等价形式 2. 初值选取 下面我们开始介绍若干种迭代法的构造方法 4.3 Newton 法 对于方程f(x)=0，可以构造多种迭代格式。牛顿法其基本思想是将非线性方程f(x)=0做Taylor展开，取其线性部分构造的一种迭代格式。实质上是一种线性化方法， Newton法迭代公式 设已知方程f(x)=0有近似根x0，且在 x0附近f(x)可用一阶泰勒多项式近似，表示为 当f?(x0)≠0时，方程f(x)=0可用线性方程(切线) 近似代替，即 f(x0)+f?(x0)(x-x0)=0.　　　　 (4.1) 解此线性方程得 得迭代公式 此式称为牛顿(Newton)迭代公式. 　　牛顿法有显然的几何意义，方程f(x)=0的根x*可解释为曲线y=f(x)与x轴交点的横坐标. 设xk是根x*的某个近似值，过曲线y=f(x)上横坐标为xk的点Pk引切线，并将该切线与x轴交点的横坐标xk+1作为x*的新的近似值. 注意到切线方程为　 这样求得的值xk+1必满足(4.1), 从而就是牛顿公式(4.2)的计算结果. 由于这种几何背景，所以牛顿迭代法也称切线法. x y x* xk y=f(x) xk+1 Pk Pk+1 xk+2 2. 牛顿迭代法的收敛性 设x*是f(x)的一个单根，即f(x*)=0，f?(x*)≠0, 有 牛顿迭代法的迭代函数为 由定理4的(2.9)式可得(4.3)式 　　由此得到，当x*为单根时，牛顿迭代法在根x*的邻近是二阶(平方)收敛的. 　　关于x*为重根时，牛顿迭代法在根x*的邻近的收敛性在后面讨论. 　　定理(局部收敛性) 设f?C2[a, b], 若x*为f(x)在[a, b]上的根，且f?(x*)?0，则存在x*的邻域U, 使得任取初值x0?U，牛顿法产生的序列{xk}收敛到x*，且满足 　　即有下面的局部收敛性定理. (1) 选定初值x0 ,计算f (x0) , f ?(x0) 计算步骤 (2) 按公式 迭代 得新的近似值xk+1 (3) 对于给定的允许精度?，如果 则终止迭代，取 ;否则k=k+1，再转 步骤(2)计算 允许精度 最大迭代次数 迭代信息 　 解 将原方程化为x–e–x= 0，则 牛顿迭代公式为 取 x0=0.5，迭代得 x1=0.566311, x2=0.5671431, x3=0.5671433. 　　　 f(x)=x–e–x， f?(x)=1+e–x， 例1 用牛顿迭代法求方程x=e–x在x=0.5附近的根. 例题2：用Newton法求方程 的根, 要求 迭代格式一： 迭代格式二： 取初值x0＝0.0,计算如下： 对迭代格式一: the iterative number is 27, the numerical solution is 0.442852706 对迭代格式二: the iterative number is 3, the numerical solution is 0.442854401 例3.求函数 的正实根。精度 要求： 从图形中我们可以看出： 在x=7和x=8 之间有一单根； 在x=1和x=2 之间有一重根。 用Matlab画图，查看根的分布情形 初值x0＝8.0 时,计算的是单根, The iterative number is 28,The numerical solution is 7.600001481 初值x0＝1.0 ,计算的是重根, The iterative number is 1356,The numerical solution is 1.198631981 取初值x0＝8.0,用牛顿迭代公式计算如下： 取初值x0＝1.0,用牛顿迭代公式计算如下： 重根情形 　　当x*为f(x)的m(m0)重根时，则f(x)可表为 f(x)=(x-x*)mg(x). 其中g(x*)≠0，此时用牛顿迭代法(4.2)求x*仍然收敛，只是收敛速度将大大减慢. 事实上，因为迭代公式 令ek=xk–x*，则 可见用牛顿法求方程的重根时仅为线性收敛. 从而有 　　两种提高求重根的收敛速度的方法： 　　1) 取如下迭代函数 得到迭代公式 * 上页 下页 * 上页 下页