数值分析英文版课件.ppt

1、1数值方法数值方法主讲：郭同彤主讲：郭同彤哈尔滨工业大学深圳研究生院哈尔滨工业大学深圳研究生院基础科学学科部基础科学学科部2今日主题今日主题n第三章：非线性方程的数值解法第三章：非线性方程的数值解法n3.1 引言引言n3.2 二分法和试位法二分法和试位法n3.3 不动点迭代法不动点迭代法n3.4 迭代加速收敛的方法迭代加速收敛的方法n3.5 Newton 迭代法迭代法3今日主题今日主题n第三章：非线性方程的数值解法第三章：非线性方程的数值解法n3.1 引言引言n3.2 二分法和试位法二分法和试位法n3.3 不动点迭代法不动点迭代法n3.4 迭代加速收敛的方法迭代加速收敛的方法n3.5 Newt

2、on 迭代法迭代法43.1 引言引言(1)n本章主要讨论数值求解方程本章主要讨论数值求解方程 f(x)=0 （4.1.1）其中xR,f Ca,b。根和零点的定义。n如果函数f(x)是多项式函数，即1110()nnnnf xa xaxa xan则称为代数方程，另一类方程称为超越方程：xxsinx,xe2130253.1 引言引言(2)n设设f(x)可分解为可分解为 *()()()mf xxxg xn其中m为正整数，n函数g满足g(x*)0。n则称则称x*是是 f(x)的的 m重零点，重零点，n或或x*是方程是方程 f(x)=0 的的m重根重根。6今日主题今日主题n第三章：非线性方程的数值解法第三

3、章：非线性方程的数值解法n3.1 引言引言n3.2 二分法和试位法二分法和试位法n3.3 不动点迭代法不动点迭代法n3.4 迭代加速收敛的方法迭代加速收敛的方法n3.5 Newton 迭代法迭代法73.2.1 二分法二分法(1)n假设假设n已找到方程 f(x)=0 的一个有根区间 a,b；n f(a)f(b)0；n方程在区间 a,b 只有一个根。n二分法步骤：二分法步骤：令 a1,b1=a,b,执行以下迭代步骤：n对于区间 an,bn,其中点为 xn=1/2(an+bn)；n若 f(an)f(xn)0,则将 an+1,bn+1 替换为 xn,bn。83.2.1 二分法二分法(2)*nnlim

4、xx n区间中点序列区间中点序列x xn n 就是方程的根就是方程的根x x*的近似解序列。的近似解序列。11()2nnnbaban而而xn是是an,bn的中点，所以有的中点，所以有*11|()()22nnnnxxbaba93.2.1 二分法二分法(3)n例例 4.2.1 X3-15x2+319=0，是否可以用二分法在，是否可以用二分法在区间区间5,10 内求解，要求误差小于内求解，要求误差小于0.510-5，需要，需要用二分法计算多少次？用二分法计算多少次？n设 f(x)=X3-15x2+319 =f(5)0,f(10)0,f(p)0f(x)=cosx-p/20,x p/2,p因此，f(x)

5、在 p/2,p 内为单调下降函数，有唯一的实根可取a,b=p/2,p类似解法1进行求解。123.2.2 试位法试位法n假设假设n已找到方程 f(x)=0 的一个有根区间 a,b；n f(a)f(b)0,则 an+1,bn+1=xn,bn；n若 f(an)f(xn)1 时，称 xk 超线性收敛n当 p=2 时，称 xk 平方收敛k 1pxkelimCe17今日主题今日主题n第三章：非线性方程的数值解法第三章：非线性方程的数值解法n3.1 引言引言n3.2 二分法和试位法二分法和试位法n3.3 不动点迭代法不动点迭代法n3.4 迭代加速收敛的方法迭代加速收敛的方法n3.5 Newton 迭代法迭代

6、法183.4.1 Aitken加速方法加速方法(1)n设设 xk 线性收敛到线性收敛到 x*，记，记 ek=xk x*，有，有n当充分大时有n其中|c|=C，由n可解出k 1kkelimC,0C1e*k 1kk 2K1xxc(xx),xxc(xx)211kkkkxxxxxxxx221212kkkkkkx xxxxxx193.4.1 Aitken加速方法加速方法(2)n定义差分记号，定义差分记号，n写成n它是x*的一个新的近似值n从序列从序列xk,用上式得到序列用上式得到序列 的方法，的方法，称为称为itken加速方法。加速方法。2kk 1kkk 2k 1kxxx,xx2xx22kk 2k 1k

7、kk2k 2K 1kkx xx(x)xxx2xxxkx203.4.1 Aitken加速方法加速方法(3)n可以证明，只要xk满足n且n则序列 是完全确定的，而且有n说明?,1,2,kxx k1lim,1kkkee*lim0kkkxxxxkx21今日主题今日主题n第三章：非线性方程和方程组的数值解第三章：非线性方程和方程组的数值解法法n3.1 引言引言n3.2 二分法和试位法二分法和试位法n3.3 不动点迭代法不动点迭代法n3.4 迭代加速收敛的方法迭代加速收敛的方法n3.5 Newton 迭代法迭代法223.5.1 Newton迭代法公式和收敛性迭代法公式和收敛性(1)n为求解方程为求解方程

8、f(x)=0 的根的根 x，假设，假设n有一个近似值xk x nf 存在且连续n因因 f(x*)=0,则：则：n若若 f (x*)0,2kkkkf()f(x)f(x)f(x)(xx)(xx)22kkkkkfxf()(xx)xxf(x)2 f(x)233.5.1 Newton迭代法公式和收敛性迭代法公式和收敛性(2)n其中其中 在在x*与与xk之间。之间。n略去最后一项，右端为略去最后一项，右端为x*的一个新的近似值，记为的一个新的近似值，记为xk+1:1()()kkkkf xxxfx即即Newton迭代法的迭代公式迭代法的迭代公式243.5.1 Newton迭代法公式和收敛性迭代法公式和收敛性

9、(3)Newton 法的几何解释253.5.1 Newton迭代法公式和收敛性迭代法公式和收敛性(4)Newton 法不收敛的情形263.5.1 Newton迭代法公式和收敛性迭代法公式和收敛性(5)n Newton迭代法的几何解释：迭代法的几何解释：n求 x*就是求曲线 y=f(x)与x轴的交点。n在曲线 y=f(x)上的点（xk,f(xk)上作曲线的切线，切线方程为 y-f(xk)=f(xk)(x-xk),n切线与x轴交点的横坐标就是 xk+1,把它作为 x*新的近似。n可以证明Newton迭代法是超线性收敛的。273.5.1 Newton迭代法公式和收敛性迭代法公式和收敛性(6)n 定理

10、定理4.5.1 n设 f(x*)=0,f(x*)0,且 f 在包含 x*的一个区间上有二阶连续导数，则 Newton 迭代法局部收敛到x*,且至少是二阶导数，并有k 12kkxxf(x)lim(xx)2 f(x)283.5.1 Newton迭代法公式和收敛性迭代法公式和收敛性(7)input output for to do output end dox,Myf x0,x,yk1Myxxfxyf xk,x,y293.5.1 Newton迭代法公式和收敛性迭代法公式和收敛性(8)input x,M,vfx output,x,v if v then stop for k to M dov xxfx

11、 vfx output k,x,v if xx 000100111001 or v then stop xx end do01303.5.1 Newton迭代法公式和收敛性迭代法公式和收敛性(9)n例例 n用Newton法计算方程 x3+4x2-10=0 在区间 1，2 的根，计算公式是n取 x0=1.5nx1=1.3733333,x2=1.3652620,x3=1.3652300nNewton法是二阶的，所以收敛较快。3212410,0,1,38kkkkkkxxxxkxx313.5.2 Newton 法的重根情形法的重根情形(1)n设设x*是方程是方程f(x)=0的的m重根，重根，m1,即即

12、nf(x)=(x-x*)m g(x)n其中g(x)有二阶导数，g(x*)0，重根情况下有 nf (x*)=0:()()()()()()()()()()()()1()()()1()()()()()()f xxxg xxxxfxmg xxxg xg xxxg xxmg xxxg xxxg xmg xxxg x 323.5.2 Newton 法的重根情形法的重根情形(2)()()()()1()()()1()()()()()()g xxx g xxmg xxx g xxx g xmg xxx g x n有有:f f(x*)=1-1/mn因因m1,所以所以 f f (x*)0，且，且|f f (x*)|

13、1nNewton法是收敛的，但只是线性收敛。法是收敛的，但只是线性收敛。33n第二种迭代方法：将迭代函数改取为n可验证 f(x*)=x*,f(x*)=0n此种迭代至少有两阶收敛()()()mf xxxfx1(),0,1,()kkkkmf xxxkfx3.5.2 Newton 法的重根情形法的重根情形(3)34n第三种迭代方法：第三种迭代方法：n令 m(x)=f(x)/f(x)n若x*是方程 f(x)=0 的m重根，则 n所以x*是方程 m(x)=0 的单根*()()()()()()xx g xxmg xxx g xm3.5.2 Newton 法的重根情形法的重根情形(4)35n应用应用Newt

14、on法，迭代函数为：法，迭代函数为：n得到迭代法：n这种方法也是至少二阶收敛的。12()(),0,1,()()()kkkkkkkf xfxxxkfxf xfx2()()()()()()()()xf x fxxxxxfxf x fxmm3.5.2 Newton 法的重根情形法的重根情形(5)363.5.2 Newton 法的重根情形法的重根情形(6)n 例例n方程 x4-4x2+4=0 的根x*=是二重根，用3种方法求解。f(x)=(x2-2)2f(x)=4x(x2-2)f(x)=4(3x2-2).n方法1（Newton法）：22kk 1kkx2xx4x1()()kkkkf xxxfx373.5

15、.2 Newton 法的重根情形法的重根情形(7)n方法2（上述第二种方法，m=2）;n方法3（上述第三种方法）1(),0,1,()kkkkmf xxxkfx2kk 1kkx2xx2x2kkk 1k2kx(x2)xxx212()(),0,1,()()()kkkkkkkf xfxxxkfxf xfx38方法方法1方法方法2方法方法3X0X1X2x31.51.4583333331.4363071431.4254976191.51.4166666671.4142156861.4142135621.51.4117647061.4142114381.4142135623.5.2 Newton 法的重根情形法的重根情形(8)n 3种方法均取 x0=1.5,各迭代三次结果如下表：n方法2和方法3都是二阶方法，x3都达到了10-9的精确度n而方法1要近30次迭代才能达到同样的精确度。