1產生背景

牛頓迭代法(Newton's method)又稱為牛頓-拉夫遜方法(Newton-Raphson method),它是牛頓在17世紀提出的一種在實數域和複數域上近似求解方程的方法。多數方程不存在求根公式,因此求精確根非常困難,甚至不可能,從而尋找方程的近似根就顯得特別重要。方法使用函數f(x)的泰勒級數的前面幾項來尋找方程f(x) = 0的根。牛頓迭代法是求方程根的重要方法之一,其最大優點是在方程f(x) = 0的單根附近具有平方收斂,而且該法還可以用來求方程的重根、復根,此時線性收斂,但是可通過一些方法變成超線性收斂。另外該方法廣泛用於計算機編程中。

2牛頓迭代公式

設r是f(x) = 0的根,選取x0作為r的初始近似值,過點(x0,f(x0))做曲線y = f(x)的切線L,L的方程為y = f(x0)+f'(x0)(x-x0),求出L與x軸交點的橫坐標 x1 = x0-f(x0)/f'(x0),稱x1為r的一次近似值。過點(x1,f(x1))做曲線y = f(x)的切線,並求該切線與x軸交點的橫坐標 x2 = x1-f(x1)/f'(x1),稱x2為r的二次近似值。重複以上過程,得r的近似值序列,其中,x(n+1)=x(n)-f(x(n))/f'(x(n))稱為r的n+1次近似值,上式稱為牛頓迭代公式
用牛頓迭代法解非線性方程f(x)=0,是把非線性方程線性化的一種近似方法。把f(x)在點x0的某鄰域內展開成泰勒級數 f(x) = f(x0)+(x-x0)f'(x0)+(x-x0)^2*f''(x0)/2! +… ,取其線性部分(即泰勒展開的前兩項),並令其等於0,即f(x0)+f'(x0)(x-x0)=0 ,以此作為非線性方程f(x) = 0的近似方程,若f'(x0)≠0,則其解為x1=x0-f(x0)/f'(x0), 這樣,得到牛頓迭代法的一個迭代關係式:x(n+1)=x(n)-f(x(n))/f'(x(n))。
牛頓迭代法示意圖

  牛頓迭代法示意圖

軍人在進攻時常採用交替掩護進攻的方式,若在數軸上的點表示A,B兩人的位置,規定在前面的數大於後面的數,則是A>B,B>A交替出現。但現在假設軍中有一個膽小鬼,同時大家又都很照顧他,每次衝鋒都是讓他跟在後面,每當前面的人佔據一個新的位置,就把位置交給他,然後其他人再往前佔領新的位置。也就是A始終在B的前面,A向前邁進,B跟上,A把自己的位置交給B(即執行B = A),然後A 再前進佔領新的位置,B再跟上,直到佔領所有的陣地,前進結束。像這種兩個數一前一後逐步向某個位置逼近的方法稱為迭代法。
迭代法也稱輾轉法,是一種不斷用變數的舊值遞推新值的過程,跟迭代法相對應的是直接法(或者稱為一次解法),即一次性解決問題。迭代演算法是用計算機解決問題的一種基本方法。它利用計算機運算速度快、適合做重複性操作的特點,讓計算機對一組指令(或一定步驟)重複執行,在每次執行這組指令(或這些步驟)時,都從變數的原值推出它的一個新值。
利用迭代演算法解決問題,需要做好以下三個方面的工作:
一、確定迭代變數
在可以用迭代演算法解決的問題中,至少存在一個可直接或間接地不斷由舊值遞推出新值的變數,這個變數就是迭代變數。
二、建立迭代關係式
所謂迭代關係式,指如何從變數的前一個值推出其下一個值的公式(或關係)。迭代關係式的建立是解決迭代問題的關鍵,通常可以使用遞推或倒推的方法來完成。
三、對迭代過程進行控制
在什麼時候結束迭代過程?這是編寫迭代程序必須考慮的問題。不能讓迭代過程無休止地執行下去。迭代過程的控制通常可分為兩種情況:一種是所需的迭代次數是個確定的值,可以計算出來;另一種是所需的迭代次數無法確定。對於前一種情況,可以構建一個固定次數的循環來實現對迭代過程的控制;對於后一種情況,需要進一步分析得出可用來結束迭代過程的條件。
最經典的迭代演算法是歐幾里德演算法,用於計算兩個整數a,b的最大公約數。其計算原理依賴於下面的定理:
定理:gcd(a,b) = gcd(b,a mod b)
證明:a可以表示成a = kb + r,則r = a mod b。假設d是a,b的一個公約數,則有 a%d==0,b%d==0,而r = a - kb,因此r%d==0 ,因此d是(b,a mod b)的公約數
同理,假設d 是(b,a mod b)的公約數,則 b%d==0,r%d==0 ,但是a = kb +r ,因此d也是(a,b)的公約數。
因此(a,b)和(b,a mod b)的公約數是一樣的,其最大公約數也必然相等,得證。
歐幾里德演算法就是根據這個原理來做的,歐幾里德演算法又叫輾轉相除法,它是一個反覆迭代執行,直到餘數等於0停止的步驟,這實際上是一個循環結構。其演算法用C語言描述為:
int Gcd_2(int a,int b)// 歐幾里德演算法求a,b的最大公約數
{
if (a<=0 || b<=0)//預防錯誤
return 0;
int temp;
while (b > 0)//b總是表示較小的那個數,若不是則交換a,b的值
{
temp = a % b;//迭代關係式
a = b; //是那個膽小鬼,始終跟在b的後面
b = temp; //向前衝鋒佔領新的位置
}
return a;
}
從上面的程序我們可以看到a,b是迭代變數,迭代關係是temp = a % b;根據迭代關係我們可以由舊值推出新值,然後循環執a = b; b = temp;直到迭代過程結束(餘數為0)。在這裡a好比那個膽小鬼,總是從b手中接過位置,而b則是那個努力向前沖的先鋒。
還有一個很典型的例子是斐波那契(Fibonacci)數列。斐波那契數列為:0、1、1、2、3、5、8、13、21、…,即 fib⑴=0; fib⑵=1;fib(n)=fib(n-1)+fib(n-2) (當n>2時)。
在n>2時,fib(n)總可以由fib(n-1)和fib(n-2)得到,由舊值遞推出新值,這是一個典型的迭代關係,所以我們可以考慮迭代演算法。
int Fib(int n) //斐波那契(Fibonacci)數列
{
if (n < 1)//預防錯誤
return 0;
if (n == 1 || n == 2)//特殊值,無需迭代
return 1;
int f1 = 1,f2 = 1,fn;//迭代變數
int i;
for(i=3; i<=n; ++i)//用i的值來限制迭代的次數
{
fn = f1 + f2; //迭代關係式
f1 = f2;//f1和f2迭代前進,其中f2在f1的前面
f2 = fn;
}
return fn;
}

3C語言代碼

double func(double x) //函數
{
return x*x*x*x-3*x*x*x+1.5*x*x-4.0;
}
double func1(double x) //導函數
{
return 4*x*x*x-9*x*x+3*x;
}
int Newton(double *x,double precision,int maxcyc) //迭代次數
{
double x1,x0;
int k;
x0=*x;
for(k=0;k<maxcyc;k++)
{
if(func1(x0)==0.0)//若通過初值,函數返回值為0
{
printf("迭代過程中導數為0!\n");
return 0;
}
x1=x0-func(x0)/func1(x0);//進行牛頓迭代計算
if(fabs(x1-x0)<precision || fabs(func(x1))<precision) //達到結束條件
{
*x=x1; //返回結果
return 1;
}
else //未達到結束條件
x0=x1; //準備下一次迭代
}
printf("迭代次數超過預期!\n"); //迭代次數達到,仍沒有達到精度
return 0;
}
int main()
{
double x,precision;
int maxcyc;
printf("輸入初始迭代值x0:");
scanf("%lf",&x);
printf("輸入最大迭代次數:");
scanf("%d",&maxcyc);
printf("迭代要求的精度:");
scanf("%lf",&precision);
if(Newton(&x,precision,maxcyc)==1) //若函數返回值為1
printf("該值附近的根為:%lf\n",x);
else //若函數返回值為0
printf("迭代失敗!\n");
getch();
return 0;
}

4C++代碼

//此函數是用來求一元3次方程ax^3+bx^2+cx+d=0的解
//比如 x^3-27=0,我們就可以輸入1 0 0 -27,這樣我們就可以得到一個解
#include<iostream>
#include<cmath>
using namespace std;
int main()
{
double diedai(double a,double b,double c,double d,double x);
double a,b,c,d;
double x=10000.0;
cout<<"請依次輸入方程四個係數:";
cin>>a>>b>>c>>d;
x=diedai(a,b,c,d,x);
cout<<x<<endl;
return 0;
}
double diedai(double a,double b,double c,double d,double x)
{
while(abs(a*x*x*x+b*x*x+c*x+d)>0.000001)
{
x=x-(a*x*x*x+b*x*x+c*x+d)/(3*a*x*x+2*b*x+c);
}
return x;
}

5matlab代碼

主程序
x=X;%迭代初值
i=0;%迭代次數計算
while i<= 100%迭代次數
x0=X-f(X)/h(X);%牛頓迭代格式
if abs(x0-X)>0.01;%收斂判斷
X=x0;
else break
end
i=i+1;
end
fprintf('\n%s%.4f\t%s%d','X=',X,'i=',i) %輸出結果

6Python代碼

Python代碼以實例展示求解f(x) = (x-3)**3,f(x) = 0 的根。
牛頓迭代法
def f(x):
return (x-3)**3 』''定義f(x) = (x-3)**3'''
def fd(x):
return 3*((x-3)**2) 』''定義f'(x) = 3*((x-3)**2)
def newtonMethod(n,assum):
time = n
x = assum
Next = 0
A = f(x)
B = fd(x)
print('A = ' + str(A) + ',B = ' + str(B) + ',time = ' + str(time))
if f(x) == 0.0:
return time,x
else:
Next = x - A/B
print('Next x = '+ str(Next))
if A == f(Next): print('Meet f(x) = 0,x = ' + str(Next)) 』''設置迭代跳出條件,同時輸出滿足f(x) = 0的x值'''
else:
returnnewtonMethod(n+1,Next)
newtonMethod(0,4.0) 』''設置從0開始計數,x0 = 4.0'''
上一篇[HTC Flyer]    下一篇 [HTC Firestone]

相關評論

同義詞:暫無同義詞