數(shù)值分析牛頓迭代法

數(shù)值分析牛頓迭代法第1頁，課件共24頁，創(chuàng)作于2023年2月《數(shù)值分析》4Newton迭代格式Newton迭代法的收斂性Newton迭代法收斂速度弦截法迭代格式2023/7/13第2頁，課件共24頁，創(chuàng)作于2023年2月NatureandNature'lawlayhidinnight.Godsaid,"LetNewtonbe,"andallwaslight.AlexanderPope2023/7/13第3頁，課件共24頁，創(chuàng)作于2023年2月給定初值

x0,迭代產(chǎn)生數(shù)列x0,x1,x2,···,

xn,

···2023/7/13第4頁，課件共24頁，創(chuàng)作于2023年2月設

x*是方程

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

x0附近對函數(shù)做局部線性化x1比x0更接近于x*x0x1x*f(x)=0化難為易化繁為簡2023/7/13第5頁，課件共24頁，創(chuàng)作于2023年2月應用——求正數(shù)平方根算法設C>0,x2–C=0令

f(x)=x2–C,則2023/7/13第6頁，課件共24頁，創(chuàng)作于2023年2月初值: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/7/13第7頁，課件共24頁，創(chuàng)作于2023年2月收斂性:(1)符合不動點框架(2)從序列收斂的角度(單調有界序列)2023/7/13第8頁，課件共24頁，創(chuàng)作于2023年2月由此可知平方根算法具有

2階收斂速度。

思考:如何求倒數(shù)、平方根和立方根？第9頁，課件共24頁，創(chuàng)作于2023年2月Newton迭代法的局部收斂性定理2.7設

f(x)在點x*的某鄰域內具有二階連續(xù)導數(shù),且

f(x*)=0和

f′(x*)≠0,則對充分靠近點x*的初值x0,Newton迭代法至少平方收斂。所以Newton迭代法至少平方收斂。2023/7/13第10頁，課件共24頁，創(chuàng)作于2023年2月例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/7/13第11頁，課件共24頁，創(chuàng)作于2023年2月注釋1:為了二次收斂有意義我們需要f′(x)相除,這個假設是關鍵的。

f(x)=x3–3x+2=0在x*=1附近2023/7/13第12頁，課件共24頁，創(chuàng)作于2023年2月x*x0x0x0Newton方法收斂性依賴于x0

的選取。存在

x0使Newton迭代法陷入死循環(huán)。注釋2:2023/7/13第13頁，課件共24頁，創(chuàng)作于2023年2月Newton迭代法的變型－弦截法由于代入牛頓迭代格式x0x12023/7/13第14頁，課件共24頁，創(chuàng)作于2023年2月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.已知方程有兩根:取根附近值做初值,分析牛頓迭代法實驗的數(shù)據(jù)。

參考:數(shù)值分析基礎,關冶陸金甫第15頁，課件共24頁，創(chuàng)作于2023年2月表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/7/13第16頁，課件共24頁，創(chuàng)作于2023年2月表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/7/13第17頁，課件共24頁，創(chuàng)作于2023年2月推論:

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

則牛頓迭代法只具有一階收斂。證:x*是二重根

f(x)=(x–x*)2g(x)牛頓迭代法只是一階收斂。2023/7/13第18頁，課件共24頁，創(chuàng)作于2023年2月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/7/13第19頁，課件共24頁，創(chuàng)作于2023年2月Examinethefunctiongraphically(tolocateroughlywheretherootsareandhowmanytheremaybe)curvesketchingisonewayor...best:useaMatlabplottogetthelayofthelandsettheintervalorthestartingpoint

(findarangeofx-valuesoverwhichthefunctionchangessign)iterativelyrefinetheinitialguesswitharoot-findingalgorithm(bisectionisdependablebutslow;Newtonisfastiftheinitialvalueisgood)一些建議第20頁，課件共24頁，創(chuàng)作于2023年2月迭代方法比較二分法

函數(shù)值的正負號不動點家族(牛頓法)函數(shù)值(函數(shù)的導數(shù)值)

收斂速度慢

收斂速度快(特別快)

總是收斂

收斂是有條件的2023/7/13第21頁，課件共24頁，創(chuàng)作于2023年2月非線性方程組:Gauss–Newton方法2023/7/13第22頁，課件共24頁，創(chuàng)作于2023年2月例3.用牛頓迭代法求解非線性方程組第23頁，課件共24頁，創(chuàng)作于2023年2月分別取初值(1,0)和(2,2),牛頓迭代法計算數(shù)據(jù)如下