数值分析牛顿迭代法

数值分析牛顿迭代法第1页，共24页，2023年，2月20日，星期五《数值分析》4Newton迭代格式Newton迭代法的收敛性Newton迭代法收敛速度弦截法迭代格式2023/4/10第2页，共24页，2023年，2月20日，星期五NatureandNature'lawlayhidinnight.Godsaid,"LetNewtonbe,"andallwaslight.AlexanderPope2023/4/10第3页，共24页，2023年，2月20日，星期五给定初值

x0,迭代产生数列x0,x1,x2,···,

xn,

···2023/4/10第4页，共24页，2023年，2月20日，星期五设

x*是方程

f(x)=0的根,x0是x*的近似值。在

x0附近对函数做局部线性化x1比x0更接近于x*x0x1x*f(x)=0化难为易化繁为简2023/4/10第5页，共24页，2023年，2月20日，星期五应用——求正数平方根算法设C>0,x2–C=0令

f(x)=x2–C,则2023/4/10第6页，共24页，2023年，2月20日，星期五初值:x0=1.5迭代格式:xn+1=0.5(xn+2/xn)(n=0,1,2,·····)例1.平方根算法求xn

|en|1.4166666666666672.45e-0031.4142156862745102.12e-0061.4142135623746901.59e-0121.4142135623730952.22e-0161.4142135623730952.22e-016表1平方根算法实验2023/4/10第7页，共24页，2023年，2月20日，星期五收敛性:(1)符合不动点框架(2)从序列收敛的角度(单调有界序列)2023/4/10第8页，共24页，2023年，2月20日，星期五由此可知平方根算法具有

2阶收敛速度。

思考:如何求倒数、平方根和立方根？第9页，共24页，2023年，2月20日，星期五Newton迭代法的局部收敛性定理2.7设

f(x)在点x*的某邻域内具有二阶连续导数,且

f(x*)=0和

f′(x*)≠0,则对充分靠近点x*的初值x0,Newton迭代法至少平方收敛。所以Newton迭代法至少平方收敛。2023/4/10第10页，共24页，2023年，2月20日，星期五例2.求

x3+10x–20=0在

x0=1.5附近的根解:取牛顿迭代格式则有nxn|en|01.511.597014925370.00245280874198121.594563748761.632137654805e-0631.594562116637.227551890309e-1341.594562116632.220446049250e-16表2牛顿迭代法实验2023/4/10第11页，共24页，2023年，2月20日，星期五注释1:为了二次收敛有意义我们需要f′(x)相除,这个假设是关键的。

f(x)=x3–3x+2=0在x*=1附近2023/4/10第12页，共24页，2023年，2月20日，星期五x*x0x0x0Newton方法收敛性依赖于x0

的选取。存在

x0使Newton迭代法陷入死循环。注释2:2023/4/10第13页，共24页，2023年，2月20日，星期五Newton迭代法的变型－弦截法由于代入牛顿迭代格式x0x12023/4/10第14页，共24页，2023年，2月20日，星期五n xn

|en| |en+1|/|en|1.6181-1.5 5.00e-001 2-2.5 5.00e-001 1.53473-1.83783783783 1.62e-001 0.49784-1.95420890762 4.57e-002 0.86915-2.00552244119 5.52e-003 0.81096-1.99982796307 1.72e-004 0.77427-1.99999936831 6.31e-007 0.77858-2.00000000007 7.24e-011 0.7778表3弦截法收敛速度实验例3.已知方程有两根:取根附近值做初值,分析牛顿迭代法实验的数据。

参考:数值分析基础,关冶陆金甫第15页，共24页，2023年，2月20日，星期五表4初值取

–1.5时牛顿迭代法速度n xn

|en||en+1|/|en|20 -1.5 5.00e-001 1 -2.33333333333 3.33e-001 1.33332 -2.05555555555 5.55e-002 0.50003 -2.00194931773 1.94e-003 0.63164 -2.00000252829 2.52e-006 0.66545 -2.00000000000 4.26e-012 0.66672023/4/10第16页，共24页，2023年，2月20日，星期五表5初值取

1.5时牛顿迭代法速度n xn

|en| |en+1|/|en|0 1.5 5.00e-001 1 1.2666666 2.66e-001 0.53332 1.1385620 1.38e-001 0.51963 1.0707773 7.07e-0020.51084 1.0357918 3.57e-002 0.50575 1.0180008 1.80e-002 0.50296 1.0090271 9.02e-003 0.50157 1.0045203 4.52e-003 0.50078 1.0022618 2.26e-003 0.50049 1.0011313 1.13e-003 0.500210 1.0005657 5.65e-004 0.500111 1.0002829 2.82e-004 0.50002023/4/10第17页，共24页，2023年，2月20日，星期五推论:

设x*是f(x)=0的二重根,

则牛顿迭代法只具有一阶收敛。证:x*是二重根

f(x)=(x–x*)2g(x)牛顿迭代法只是一阶收敛。2023/4/10第18页，共24页，2023年，2月20日，星期五n xn

|en| |en+1|/|en|20 1.5 5.00e-001 1 1.03333333333 3.33e-002 0.13332 1.00018214936 1.85e-004 0.16393 1.00000000552 5.52e-009 0.1667

若

x*是

f(x)=0的

m重根,修正的牛顿迭代法为二阶收敛

表5x*为二重根时修正的牛顿迭代实验m=2

[f(x)]1/m或f(x)/f′(x)单根2023/4/10第19页，共24页，2023年，2月20日，星期五Examinethefunctiongraphically(tolocateroughlywheretherootsareandhowmanytheremaybe)curvesketchingisonewayor...best:useaMatlabplottogetthelayofthelandsettheintervalorthestartingpoint

(findarangeofx-valuesoverwhichthefunctionchangessign)iterativelyrefinetheinitialguesswitharoot-findingalgorithm(bisectionisdependablebutslow;Newtonisfastiftheinitialvalueisgood)一些建议第20页，共24页，2023年，2月20日，星期五迭代方法比较二分法

函数值的正负号不动点家族(牛顿法)函数值(函数的导数值)

收敛速度慢

收敛速度快(特别快)

总是收敛

收敛是有条件的2023/4/10第21页，共24页，2023年，2月20日，星期五非线性方程组:Gauss–Newton方法2023/4/10第22页，共24页，2023年，2月20日，星期五例3.用牛顿迭代法求解非线性方程组第23页，共24页，2023年，2月20日，星期五分别取初值(1,0)和(2,2),牛顿迭代法计算数据如