牛頓迭代法.doc

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