簡介
![牛頓逼近法](/img/b/cd4/wZwpmLxcTNyUjNwMDO4EDN0UTMyITNykTO0EDMwAjMwUzLzgzLzIzLt92YucmbvRWdo5Cd0FmLwE2LvoDc0RHa.jpg)
![牛頓逼近法](/img/e/524/wZwpmLwADO5IzN2kzN0YzM1UTM1QDN5MjM5ADMwAjMwUzL5czL1YzLt92YucmbvRWdo5Cd0FmL0E2LvoDc0RHa.jpg)
牛頓逼近法,又稱牛頓法(英語:Newton's method)又稱為 牛頓-拉弗森方法(英語:Newton-Raphson method),它是一種在實數域和複數域上近似求解方程的方法。方法使用函式 的泰勒級數的前面幾項來尋找方程 的根。
起源
牛頓法最初由艾薩克·牛頓在《流數法》( Method of Fluxions,1671年完成,在牛頓去世後的1736年公開發表)中提出。約瑟夫·鮑易也曾於1690年在 Analysis Aequationum中提出此方法。
方法說明
![方法說明示意圖](/img/6/b4f/wZwpmLxYDO2ETO5ITN0YzM1UTM1QDN5MjM5ADMwAjMwUzLyUzL3czLt92YucmbvRWdo5Cd0FmLzE2LvoDc0RHa.jpg)
![牛頓逼近法](/img/8/778/wZwpmL2MzN5UzM2MzNwIDN0UTMyITNykTO0EDMwAjMwUzLzczL4MzLt92YucmbvRWdo5Cd0FmLzE2LvoDc0RHa.jpg)
![牛頓逼近法](/img/1/43e/wZwpmLwQTO5MTO4IzN0YzM1UTM1QDN5MjM5ADMwAjMwUzLyczLzMzLt92YucmbvRWdo5Cd0FmLyE2LvoDc0RHa.jpg)
![牛頓逼近法](/img/d/659/wZwpmLzUDMzkDOwMjM4IDN0UTMyITNykTO0EDMwAjMwUzLzIzL1MzLt92YucmbvRWdo5Cd0FmLzE2LvoDc0RHa.jpg)
![牛頓逼近法](/img/8/778/wZwpmL2MzN5UzM2MzNwIDN0UTMyITNykTO0EDMwAjMwUzLzczL4MzLt92YucmbvRWdo5Cd0FmLzE2LvoDc0RHa.jpg)
![牛頓逼近法](/img/1/036/wZwpmL3QzM5YjNzMjM0EDN0UTMyITNykTO0EDMwAjMwUzLzIzL3EzLt92YucmbvRWdo5Cd0FmLwE2LvoDc0RHa.jpg)
藍線表示方程 而紅線表示切線。可以看出 比 更靠近 所要求的根 。
![牛頓逼近法](/img/b/cd4/wZwpmLxcTNyUjNwMDO4EDN0UTMyITNykTO0EDMwAjMwUzLzgzLzIzLt92YucmbvRWdo5Cd0FmLwE2LvoDc0RHa.jpg)
![牛頓逼近法](/img/d/58f/wZwpmLyEjN4ITNyMTMzEDN0UTMyITNykTO0EDMwAjMwUzLzEzLxczLt92YucmbvRWdo5Cd0FmL0E2LvoDc0RHa.jpg)
![牛頓逼近法](/img/5/4c0/wZwpmL3MTN1cTN2EDN2EzM1UTM1QDN5MjM5ADMwAjMwUzLxQzL4MzLt92YucmbvRWdo5Cd0FmL0E2LvoDc0RHa.jpg)
![牛頓逼近法](/img/4/9a6/wZwpmL3EzN3YjNykjNwMzM1UTM1QDN5MjM5ADMwAjMwUzL5YzLwQzLt92YucmbvRWdo5Cd0FmLyE2LvoDc0RHa.jpg)
![牛頓逼近法](/img/6/338/wZwpmLzQDOwADN3QDOxMzM1UTM1QDN5MjM5ADMwAjMwUzL0gzLyMzLt92YucmbvRWdo5Cd0FmL0E2LvoDc0RHa.jpg)
![牛頓逼近法](/img/8/778/wZwpmL2MzN5UzM2MzNwIDN0UTMyITNykTO0EDMwAjMwUzLzczL4MzLt92YucmbvRWdo5Cd0FmLzE2LvoDc0RHa.jpg)
![牛頓逼近法](/img/9/869/wZwpmLzYzMzczNxIjN0YzM1UTM1QDN5MjM5ADMwAjMwUzLyYzL0QzLt92YucmbvRWdo5Cd0FmLwE2LvoDc0RHa.jpg)
![牛頓逼近法](/img/4/9a6/wZwpmL3EzN3YjNykjNwMzM1UTM1QDN5MjM5ADMwAjMwUzL5YzLwQzLt92YucmbvRWdo5Cd0FmLyE2LvoDc0RHa.jpg)
![牛頓逼近法](/img/1/036/wZwpmL3QzM5YjNzMjM0EDN0UTMyITNykTO0EDMwAjMwUzLzIzL3EzLt92YucmbvRWdo5Cd0FmLwE2LvoDc0RHa.jpg)
![牛頓逼近法](/img/1/036/wZwpmL3QzM5YjNzMjM0EDN0UTMyITNykTO0EDMwAjMwUzLzIzL3EzLt92YucmbvRWdo5Cd0FmLwE2LvoDc0RHa.jpg)
首先,選擇一個接近函式 零點的 ,計算相應的 和切線斜率 (這裡 表示函式 的導數)。然後我們計算穿過點 並且斜率為 的直線和 軸的交點的 坐標,也就是求如下方程的解:
![牛頓逼近法](/img/2/912/wZwpmL3gDO5UjN1ETN0YzM1UTM1QDN5MjM5ADMwAjMwUzLxUzL1AzLt92YucmbvRWdo5Cd0FmLwE2LvoDc0RHa.jpg)
![牛頓逼近法](/img/1/036/wZwpmL3QzM5YjNzMjM0EDN0UTMyITNykTO0EDMwAjMwUzLzIzL3EzLt92YucmbvRWdo5Cd0FmLwE2LvoDc0RHa.jpg)
![牛頓逼近法](/img/1/b32/wZwpmL1IDM1ADNyMTMzEDN0UTMyITNykTO0EDMwAjMwUzLzEzL1IzLt92YucmbvRWdo5Cd0FmLxE2LvoDc0RHa.jpg)
![牛頓逼近法](/img/1/b32/wZwpmL1IDM1ADNyMTMzEDN0UTMyITNykTO0EDMwAjMwUzLzEzL1IzLt92YucmbvRWdo5Cd0FmLxE2LvoDc0RHa.jpg)
![牛頓逼近法](/img/d/58f/wZwpmLyEjN4ITNyMTMzEDN0UTMyITNykTO0EDMwAjMwUzLzEzLxczLt92YucmbvRWdo5Cd0FmL0E2LvoDc0RHa.jpg)
![牛頓逼近法](/img/a/82f/wZwpmL1MDOwYTN4UTMzEzM1UTM1QDN5MjM5ADMwAjMwUzL1EzLzAzLt92YucmbvRWdo5Cd0FmLxE2LvoDc0RHa.jpg)
![牛頓逼近法](/img/1/b32/wZwpmL1IDM1ADNyMTMzEDN0UTMyITNykTO0EDMwAjMwUzLzEzL1IzLt92YucmbvRWdo5Cd0FmLxE2LvoDc0RHa.jpg)
我們將新求得的點的 坐標命名為 ,通常 會比 更接近方程 的解。因此可以利用 開始下一輪疊代。疊代公式可化簡為如下所示:
![牛頓逼近法](/img/c/d51/wZwpmLwgDM5cTOxMTOwMzM1UTM1QDN5MjM5ADMwAjMwUzLzkzLzYzLt92YucmbvRWdo5Cd0FmLyE2LvoDc0RHa.jpg)
![牛頓逼近法](/img/6/338/wZwpmLzQDOwADN3QDOxMzM1UTM1QDN5MjM5ADMwAjMwUzL0gzLyMzLt92YucmbvRWdo5Cd0FmL0E2LvoDc0RHa.jpg)
![牛頓逼近法](/img/1/036/wZwpmL3QzM5YjNzMjM0EDN0UTMyITNykTO0EDMwAjMwUzLzIzL3EzLt92YucmbvRWdo5Cd0FmLwE2LvoDc0RHa.jpg)
![牛頓逼近法](/img/1/036/wZwpmL3QzM5YjNzMjM0EDN0UTMyITNykTO0EDMwAjMwUzLzIzL3EzLt92YucmbvRWdo5Cd0FmLwE2LvoDc0RHa.jpg)
![牛頓逼近法](/img/d/58f/wZwpmLyEjN4ITNyMTMzEDN0UTMyITNykTO0EDMwAjMwUzLzEzLxczLt92YucmbvRWdo5Cd0FmL0E2LvoDc0RHa.jpg)
已經證明,如果 是連續的,並且待求的零點 是孤立的,那么在零點 周圍存在一個區域,只要初始值 位於這個鄰近區域內,那么牛頓法必定收斂。
![牛頓逼近法](/img/c/8ca/wZwpmL0YjM2YDO4ETN0YzM1UTM1QDN5MjM5ADMwAjMwUzLxUzL2YzLt92YucmbvRWdo5Cd0FmL0E2LvoDc0RHa.jpg)
並且,如果 ,那么牛頓法將具有平方收斂的性能。粗略的說,這意味著每疊代一次,牛頓法結果的有效數字將增加一倍 。
具體介紹
![牛頓逼近法](/img/a/82f/wZwpmL1MDOwYTN4UTMzEzM1UTM1QDN5MjM5ADMwAjMwUzL1EzLzAzLt92YucmbvRWdo5Cd0FmLxE2LvoDc0RHa.jpg)
![牛頓逼近法](/img/b/cd4/wZwpmLxcTNyUjNwMDO4EDN0UTMyITNykTO0EDMwAjMwUzLzgzLzIzLt92YucmbvRWdo5Cd0FmLwE2LvoDc0RHa.jpg)
求代數方程 的精確解是很難的事情,特別地當 是 高於5次的多項式時,不能通過多項式係數的有限次運算得到根的表達式。在這種情況下求 方程的近似解卻是可以的,牛頓法就是一種比較好的逐次逼近法。牛頓法在求根過程中逼近很快,用計算機計算是十分方便的。
![牛頓逼近法](/img/c/fc0/wZwpmL2YTO2YTM0gzN0YzM1UTM1QDN5MjM5ADMwAjMwUzL4czL1IzLt92YucmbvRWdo5Cd0FmLxE2LvoDc0RHa.jpg)
![牛頓逼近法](/img/1/69b/wZwpmL1ITO0MjNwcTO0YzM1UTM1QDN5MjM5ADMwAjMwUzL3kzL2YzLt92YucmbvRWdo5Cd0FmLzE2LvoDc0RHa.jpg)
![牛頓逼近法](/img/b/cd4/wZwpmLxcTNyUjNwMDO4EDN0UTMyITNykTO0EDMwAjMwUzLzgzLzIzLt92YucmbvRWdo5Cd0FmLwE2LvoDc0RHa.jpg)
![牛頓逼近法](/img/2/715/wZwpmL0AjNzgzM3ITN0YzM1UTM1QDN5MjM5ADMwAjMwUzLyUzLxczLt92YucmbvRWdo5Cd0FmL0E2LvoDc0RHa.jpg)
![牛頓逼近法](/img/2/f07/wZwpmL3gzNyYTM3MTN0YzM1UTM1QDN5MjM5ADMwAjMwUzLzUzLyIzLt92YucmbvRWdo5Cd0FmLwE2LvoDc0RHa.jpg)
牛頓法的本質仍然是“以直代曲”,首先猜測一個值x1,用它近似方程的根 c,用過 點的切線 近似代替曲線,然後用切線方程 的根 近似代替曲線方程的根c,這樣就得到c的第二個近似值。依此類推可得到疊代公式
![牛頓逼近法](/img/7/2a5/wZwpmLxgTOzkzN3UjN0YzM1UTM1QDN5MjM5ADMwAjMwUzL1YzL3IzLt92YucmbvRWdo5Cd0FmLzE2LvoDc0RHa.jpg)
在複平面上選定一個區域,對於任意初始點(除去(0,0)點),討論它在牛頓法疊代過程中的行為。一般選 ,其中p是大於2的正整數。這樣,疊代公式還可以 改寫為
![牛頓逼近法](/img/4/4db/wZwpmL3MDN4ADN0MjN0YzM1UTM1QDN5MjM5ADMwAjMwUzLzYzLxAzLt92YucmbvRWdo5Cd0FmLzE2LvoDc0RHa.jpg)
![牛頓逼近法](/img/c/ada/wZwpmL2gjN1AzM2gTN0YzM1UTM1QDN5MjM5ADMwAjMwUzL4UzL0YzLt92YucmbvRWdo5Cd0FmLxE2LvoDc0RHa.jpg)
對於 ,有三個根: ,三個根均勻地分布在單位圓上 。
疊代過程照例要先將複數分解為實部和虛部:
![牛頓逼近法](/img/b/5bd/wZwpmL3YTO4ITMyQTN0YzM1UTM1QDN5MjM5ADMwAjMwUzL0UzLzAzLt92YucmbvRWdo5Cd0FmL0E2LvoDc0RHa.jpg)
![牛頓逼近法](/img/2/d1c/wZwpmLzcjM4czNyQzN0YzM1UTM1QDN5MjM5ADMwAjMwUzL0czL2UzLt92YucmbvRWdo5Cd0FmL0E2LvoDc0RHa.jpg)
![牛頓逼近法](/img/2/5b0/wZwpmLwcTN3UTO0gTN0YzM1UTM1QDN5MjM5ADMwAjMwUzL4UzL3QzLt92YucmbvRWdo5Cd0FmLzE2LvoDc0RHa.jpg)
以 為例,用牛頓法生成分形圖形的一個簡單的matlab源程式如下:
% 牛頓求根法
N=160;
warning off
[X,Y]=meshgrid((-N:N)/N*2);
[m,n]=find(X==0&Y==0);
X(m,n)=1;
Y(m,n)=1;
R=zeros(321);
G=R;
B=R;
for k=1:30;
Xn=2*X/3+(X.^2-Y.^2)./(3*(X.^2+Y.^2));
Yn=2*Y/3-2*X.*Y./(3*(X.^2+Y.^2));
X=Xn;
Y=Yn;
end
R(X>0.8)=1;
G(Y<-0.5)=1;
B(Y>0.5)=1;
imshow(cat(3,R,G,B))