非线性方程的牛顿法课件

数值分析

非线性方程的牛顿法

(NewtonMethodofNonlinearEquations)内容提纲（Outline)牛顿法及其几何意义收敛性及其收敛速度计算实例及其程序演示取x0作为初始近似值，将f(x)在x0做Taylor展开:重复上述过程作为第一次近似值一、牛顿法及其几何意义Newton迭代公式基本思路：将非线性方程f(x)=0线性化牛顿法的几何意义xyx*x0x

1x

2牛顿法也称为切线法（局部收敛性定理）设f(x)C2[a,b]，若x*

为f(x)在[a,b]上的根,且f(x*)0，则存在x*的邻域使得任取初始值，Newton法产生的序列{xk}收敛到x*，且满足至少平方收敛二、牛顿法的收敛性与收敛速度在x*的附近收敛由Taylor展开：令k，由f(x*)0，即可得结论。证明：Newton法实际上是一种特殊的迭代法思考题1

若，Newton法是否仍收敛？设x*是f

的m

重根，则令：且Answer1:

有局部收敛性Answer2:

线性收敛思考题2当x*是f(x)=0的m重根,是否平方收敛？注：Newton法的收敛性依赖于x0

的选取。x*x0x0x0有根根唯一全局收敛性定理(定理4.7)：设f(x)C2[a,b]，若f(a)f(b)<0；在整个[a,b]上f(x)0；f(x)在[a,b]上不变号

选取初始值x0

[a,b]使得f(x0)f(x0)>0；则由Newton法产生的序列{xk}单调地收敛到f(x)=0在[a,b]的唯一根x*,且收敛速度至少是二阶的保证产生的序列{xk}单调有界保证Newton迭代函数将[a,b]映射于自身将f(x*)在xk处作Taylor展开对迭代公式两边取极限，得证明：以为例证明

说明数列{xk}有下界故{xk}单调递减,从而{xk}收敛.令？三、计算实例及其程序演示辅助工具:VC程序设计语言Matlab数学软件

(1)选定初值x0,计算f(x0),f(x0)计算步骤(2)按公式迭代得新的近似值xk+1

(3)对于给定的允许精度，如果

则终止迭代，取;否则k=k+1，再转步骤(2)计算允许精度最大迭代次数迭代信息例题1用Newton法求方程的根,要求迭代格式一：迭代格式二：取初值x0＝0.0,计算如下：对迭代格式一:theiterativenumberis27,thenumericalsolutionis0.442852706对迭代格式二:theiterativenumberis3,thenumericalsolutionis0.442854401例题2求函数的正实根精度要求：从图形中我们可以看出：在x=7和x=8

之间有一单根；在x=1和x=2

之间有一重根。用Matlab画图，查看根的分布情形初值x0＝8.0

时,计算的是单根,Theiterativenumberis28,Thenumericalsolutionis7.600001481初值x0＝1.0,计算的是重根,Theiterativenumberis1356,Thenumericalsolutionis1.198631981例3:设C为正实数,导出用牛顿法求的公式,并证明解：设，则于是有由于所以在内有一正根.又在内,

根据定理得牛顿迭代格式为:迭代序列的误差满足因为，所以注意:由上式可得:即该迭代格式是2阶收敛的.例4

求方程的解解：设，则f(0)=1,f(2)=-1在[0,2]内,f’(x)<0,f’’(x)>0,f(0)f’’(0)>0,所以迭代格式为:MATLAB程序为:function[x,k]=Newton(x0,dx,eps)%eps:tolerancek=0;whiledx>epsx(k+1)=x0-(exp(-x0/4)*(2-x0)-1)/(exp(-x0/4)*((x0-6)/4));dx=abs(x(k+1)-x0);x0=x(k+1);k=k+1;end取x0=0及x0=3,计算结果比较精确。如果改写x0=8,又会怎样呢?计算结果如下.x(1)=8;fork=2:3x(k)=x(k-1)-((2-x(k-1))*exp(-x(k-1)/4)-1)/(exp(-x(k-1)/4)*(x(k-1)-6)/4);endxx=8.000034.7781869.1528定理4.7指出：x0的选取是很要紧的。例如此例，选x0=0则完全符合定理条件，可确保迭代格式收敛；选x0=3也可收敛；说明定理条件是充分条件；但如果选x0=8则发散。小结(1)当f

(x)充分光滑且x*是f

(x)=0的单根时，牛顿法在x*的附近至少是平方收敛的。(2)当f

(x)充分光滑且x*是f

(x)=0的重根时，牛顿法在x*的附近是线性收敛的。(3)Newton法在区间[a,b]上的收敛性依赖于初值x0

的选取。改进与推广/*improvementandgeneralization*/重根/*multipleroot*/

加速收敛法：Q1:

若，Newton’sMethod是否仍收敛？设x*是f

的n

重根，则：且。因为Newton’sMethod事实上是一种特殊的不动点迭代，其中，则A1:

有局部收敛性，但重数n

越高，收敛越慢。Q2:

如何加速重根的收敛？A2:

将求

f

的重根转化为求另一函数的单根。令，则f

的重根=

的单根。正割法/*SecantMethod*/

：Newton’sMethod

一步要计算f

和f’，相当于2个函数值，比较费时。现用f

的值近似f’，可少算一个函数值。x0x1切线

/*tangentline*/割线

/*secantline*/切线斜率

割线斜率需要2个初值x0

和x1。收敛比Newton’sMethod慢，且对初值要求同样高。下山法/*DescentMethod*/

——Newton’sMethod

局部微调：原理：若由xk

得到的xk+1不能使|f|减小，则在xk和xk+1之间找一个更好的点，使得。xkxk+1注：=1时就是Newton’sMethod公式。当=1代入效果不好时，将减半计算。Algorithm:Newton’sDescentMethodFindasolutiontof(x)=0givenaninitialapproximationx0.Input:initialapproximationx0;f(x)andf’(x);minimumstepsizeofxmin;

toleranceTOL1forx;toleranceTOL2for

;maximumnumberofiterationsNmax.Output:approximatesolutionxormessageoffailure.Step1Setk=1;Step2While(kNmax)dosteps3-10

Step3Set=1;

Step4Set

;/*computexk*/

Step5If|xx0|<TOL1thenOutput(x);STOP;/*successful*/

Step6Ifthenx0=x;GOTOStep10;/*updatex0*/

Step7Set=/2;/*updatetodescend*/

Step8If>TOL2thenGOTOStep4;/*computeabetterxi*/

Step9Setx0=x0+xmin;/*moveforwardanywaytoavoiddeadlock*/

Step10Setk++;Step11Output(MethodfailedafterNmaxiterations);STOP./*unsuccessful*/计算量未见得减小求复根/*FindingComplexRoots*/

——

Newton公式中的自变量可以是复数记z=x+iy,z0

为初值，同样有设代入公式，令实、虚部对应相等，可得解非线性方程组的牛顿法将非线性方程组线性化，得到：其中F(xk)为F(x)在xk处的Jacobi矩阵：例：用牛顿法解方程组取初始值（1，1，1），计算如下Nxyz01.00000001.00000001.000000002.18932601.59847511.39390061.85058961.44425141.27822401.78016111.42443591.23929241.77767471.42396091.23747381.77