牛頓迭代法.doc

牛頓迭代法摘要：迭代法是一種不斷用變量的舊值遞推新值的過程，在現(xiàn)代計算機(jī)計算方面有著重要應(yīng)用。牛頓迭代法是牛頓在17世紀(jì)提出的一種在實(shí)數(shù)域和復(fù)數(shù)域上近似求解方程的方法，多數(shù)方程不存在求根公式，因此求精確根非常困難，甚至不可能，從而尋找方程的近似根就顯得特別重要。關(guān)鍵字：迭代；方程；算法前言：牛頓法（Newtons method）又稱為牛頓-拉弗森方法（Newton-Raphson method），牛頓法是一種特殊形式的迭代法，它是求解非線性方程最有效的方法之一。其基本思想是：利用泰勒公式將非線性函數(shù)在方程的某個近似根處展開，然后截取其線性部分作為函數(shù)的一個近似，通過解一個一元一次方程來獲得原方程的一個新的近似根。一、牛頓迭代法的起源在計算數(shù)學(xué)中，迭代是通過從一個初始估計出發(fā)尋找一系列近似解來解決問題（一般是解方程或者方程組）的數(shù)學(xué)過程，為實(shí)現(xiàn)這一過程所使用的方法統(tǒng)稱為迭代法。迭代法是求方程近似根的一個重要方法，也是計算方法中的一種基本方法，它的算法簡單，是用于求方程或方程組近似根的一種常用的算法設(shè)計方法。牛頓迭代法是求方程根的重要方法之一，其最大優(yōu)點(diǎn)是在方程f(x) = 0的單根附近具有平方收斂，而且該法還可以用來求方程的重根、復(fù)根。牛頓法是方程求根的一個有力方法，常常能快速求出其他方法求不出或者難以求出的解。牛頓法最初由艾薩克牛頓在流數(shù)法（Method of Fluxions，1671年完成，在牛頓死后的1736年公開發(fā)表）。約瑟夫拉弗森也曾于1690年在Analysis Aequationum中提出此方法。二、牛頓迭代法的思想及分析設(shè)當(dāng)前點(diǎn)為xk，將f(x)在xk處泰勒展開并截取線性部分得f(x)f(xk)+f(xk)(xxk)令上式右端為0，解得xk+1=xkf(xk)/f(xk),k=0,1,該式稱為牛頓迭代公式。根據(jù)導(dǎo)數(shù)的幾何意義及上述推導(dǎo)過程可知，牛頓法的幾何上表現(xiàn)為：xk+1是函數(shù)f(x)在點(diǎn)(xk,f(xk)處的切線與x軸的交點(diǎn)。因此，牛頓法的本質(zhì)是一個不斷用切線來近似曲線的過程，故牛頓法也稱為切線法。牛頓迭代法實(shí)質(zhì)上是一種線性化方法其基本思想是將非線性方程逐步歸結(jié)為某種線性方程來求解。牛頓迭代方法能夠有效的基本條件是：迭代公式必須是收斂的（也就是通過迭代運(yùn)算，每一次的結(jié)果必須是更接近真實(shí)值的）。具體使用迭代法求根時應(yīng)注意以下兩種可能發(fā)生的情況：（1）如果方程無解，算法求出的近似根序列就不會收斂，迭代過程會變成死循環(huán)，因此在使用迭代算法前應(yīng)先考察方程是否有解，并在程序中對迭代的次數(shù)給予限制；（2） 方程雖然有解，但迭代公式選擇不當(dāng)，或迭代的初始近似根選擇不合理，也會導(dǎo)致迭代失敗。牛頓迭代法具有較高的收斂速度，它的收斂階數(shù)為P=2；而牛頓迭代法的局部收斂性較強(qiáng)，只有初值充分地接近x才能確保迭代序列的收斂性。為了放寬對局部收斂性的限制，必須再增加條件建立以下收斂的充分條件。設(shè)函數(shù)f(x)C2a,b,且滿足1) f(a)f(b)0；2) f(x)0，（xa,b）；3) f”(x)在a,b上恒正或恒負(fù)；初值x0a,b滿足f(x0)f”(x0)0時，由牛頓法產(chǎn)生的序列收斂到f(x)=0在a,b上的唯一根。由此可知，牛頓法的收斂性依賴于初值x0的選取，如果x0偏離x較遠(yuǎn)，則牛頓法可能收斂緩慢甚至發(fā)散。例如，用牛頓法求方程x3x1=0的近似根，如果取x0=1.5，用牛頓迭代公式:xk+1=xk(x3kxk1)/(3x2k1)迭代3次可得結(jié)果：x1=1.3478，x2=1.3252，x3=1.3247,其誤差小于105。但如果取x0=2.0，則要得到同樣精度的解需要迭代65次！因此，為了保證當(dāng)x0遠(yuǎn)離x時，迭代仍然收斂，可在牛頓迭代公式中增加一個參數(shù)，改為xk+1=xkkf(xk)/f (xk),k=0,1,其中k的選擇保證|f(xk+1)|f(xk)|。兩式合起來稱為阻尼牛頓法或牛頓下降法。三、牛頓迭代法的求根與C+程序代碼算法框圖：牛頓迭代求根的方法：設(shè)方程為f(x)=0，用某種數(shù)學(xué)方法導(dǎo)出等價的形式x=g(x)，按下面步驟執(zhí)行：（1）選一個方程的近似根，賦給變量x0；（2） 將x0的值保存于變量x1，然后計算g(x1)，并將結(jié)果存于變量x0；（3） 當(dāng)x0與x1的差的絕對值還小于指定的精度要求時，重復(fù)步驟（2）的計算。 若方程有根，并且用上述方法計算出來的近似根序列收斂，則按上述方法求得的x0就認(rèn)為是方程的根。C+程序代碼：#include #include using namespace std; int main() double diedai(int a,int b,int c,int d,double x); int a,b,c,d; double x=10000.0; coutabcd; x=diedai(a,b,c,d,x); coutx; return 0; double diedai(int a,int b,int c,int d,double x) x=x-(a*pow(x,3.0)+b*pow(x,2.0)+c*pow(x,1.0)+d)/(3*a*pow(x,2.0)+2*b*pow(x,1.0)+c); if(abs(a*x*x*x+b*x*x+c*x+d)=0.000001) return x; else return diedai(a,b,c,d,x); 四、牛頓迭代法的優(yōu)缺點(diǎn)牛頓迭代法公式簡單，使用方便，易于編程，收斂速度快，是易于求解非線性方程根的有效方法。但同時牛頓迭代法的計算量大，每次迭代都要計算函數(shù)值與導(dǎo)數(shù)值，迭代速度較慢。結(jié)論：在多數(shù)方程不存在求根公式，求精確根非常困難，甚至不可能的情況下，尋找方程的近似根就顯得特別重要。方法使用函數(shù)f(x）的泰勒級數(shù)的前面幾項(xiàng)來尋找方程f(x) = 0的根。牛頓迭代法是求方程根的重要方法之一，其最大優(yōu)點(diǎn)是在方程f(x) = 0的單根附近具有平方收斂，而且該法還可以用來求方程的重根、復(fù)根，此時線性收