【文章內容簡介】 p的切線與 x 軸的交點， 通過下圖的顯示可以看出 1p 比 0p 更靠近于 p，寫出切線 L 的兩種表達式，則可得到 0p 與 1p 的相關方程，如下所示： 0 0100 ( ) ()fpm f ppp? ???? 解出 0100()()fppp fp??? 。重復上述過程可得到序列 {}kp 收斂到 p y p 1p 0p x 2p O 11( , ( ))p f p ? ?00, ( )p f p 定理 設 2[ , ]f C a b? ，且存在數(shù) [ , ]p ab? ，滿足 ( ) 0fp? 。如果 ( ) 0fp? ? ，則存在一個數(shù) 0?? 。對任意初始近似值 0 [ , ]p p p??? ? ?，使得由如下迭代定義的序列 0{}kkp ?? 收斂到 p： 12 1111()()()kk k k kfpp g p pfp ??? ?? ? ? ? 其中 k=1， 2?? 注：函數(shù) ()gx由如下公式定義 ()() ()fxg x x fx?? ? ，并稱為牛頓 拉夫森迭代函數(shù)。由于 ()g p p? ，這樣尋找函數(shù) ()gx的不動點，可以實現(xiàn)尋找方程 ( ) 0fx?根的牛頓 拉夫森迭代 證明 ： 我們從 1 階泰勒多項式和它的余項開始分析 200 0 0 ( ) ( )( ) ( ) ( ) ( ) 2!f c x pf x f p f p x p ?? ??? ? ? ? 這里， c 位于 0p 與 x 之間。用 x=p代入上式，并利用 0( ) 0fp? ，可得 0= 200 0 0 ( ) ( )( ) ( ) ( ) 2!f c p pf p f p p p?? ??? ? ? 如果 0p 足夠逼近 p，上式右邊的最后一項比前兩項的和小。因此最后一項可以被忽略，而且可以利用如下近似表達式： 0 0 00 ( ) ( ) ( )f p f p p p?? ? ?，推出0 0 0( ) / ( )p p f p f p??? 。 這可以用來定義下一個根的近似值 1p 1 0 0 0( ) / ( )p p f p f p??? ，當 1kp? 用在上式的時候，就可以建立一般規(guī)律，即可得證！ 推論 求平方根的牛頓迭代： 設 A 為實數(shù)，且 A0，而且令 0p 0 為 A的初始 近似值，使用下列遞推規(guī)則 1 12k kkAppp ? ??? ， k=1， 2?? 定義序列 0{}kkp ?? ，則序列 0{}kkp ?? 收斂到 A ，也可表示為 limkn pA?? ?。 證明： 從函數(shù) 2()f x x A??開始，方程 2x A=0 的根為 A? ?，F(xiàn)在利用牛頓 拉夫森函數(shù)中的 ()fx和 ()fx? ，可寫出牛頓 拉夫森迭代公式 13 2()()( ) 2f x x Ag x x xf x x?? ? ? ?? 簡化為 () 2Axxgx ?? ，用此式中的 ()gx 來定義牛頓 拉夫森定理中的遞歸迭代時，結果得證。 例題： ① 用牛頓平方根算法求 5 的近似值。從 0 2p? 開始。 運用公式計算得：1 2 5 / 2 2 .2 52p ??? 2 2 .2 5 2 .2 5 / 2 2 .2 3 6 1 1 1 1 1 12p ??? 3 ? 4 067 978p ? ② 設 3( ) 3 2f x x x? ? ?，從 0 ? 開始，求 1 2 3 4,p p p p和 1111()()()kk k k kfpp g p pfp ??? ?? ? ? ?，所以 1p = 32 .1 6 .3 22 .1 3 * 4 .2 3?????2. 2 3 4,p p p和 都是無限接近與 2。 收斂速度與缺陷 通過上面的討論，我們可以得到一個很顯著的性質：如果 p是 f（ x）=0 的單根，則牛頓法收斂很快，如果 p 是重根，每個連續(xù)的近似值誤差是前一個誤差的一小部分，我們可以定義 收斂階 來測量序列的收斂速度 定義 設序列 0{}nnp ?? 收斂到 p，并令 nnE p p?? ， 0n? 。如果兩個常量00AR??和 存在，而且 11l i m l i mnnRRnnp p E Ap p E??? ? ? ?? ???，則該序列稱為以 收斂階 R 收斂到 p，數(shù) A 稱為漸進誤差常數(shù) 。 R=1， 2 的情況為特殊情況 如果 R=1，稱序列 0{}nnp ?? 的收斂性為線性收斂 14 如果 R=2，稱序列 0{}nnp ?? 的收斂性為二次收斂。 如果 R 很大，則序列 {}np 很快收斂到 p；這意味著，關系式中對于大的值 n，有近似值 1 RnnE A E? ? 。例如 R=2 且 210nE ?? ，則 41 10nEA?? ?? 下面我們用 2 個例題給出比較 （ 單根的二次收斂 ） 從 0p = 開始 ，用牛頓 拉夫森迭代求多項式3( ) 3 2f x x x? ? ?的根 p=2. 計算 {}kp 的迭代公式是：3 11 2 122() 33kkk kpp g p p ?? ? ??? ? 解：用 R=2 并利用收斂階檢查二次收斂，可得到下表中的值 通過分析上面的收斂速度，可發(fā)現(xiàn)每個連續(xù)迭代的誤差是前一個迭代誤差的一小部分， 即 21kkp p A p p?? ? ?，其中 2/3A? ，為了檢查上式，利用 3 0 .0 0 0 0 0 8 5 8 9pp?? 和 22 0 .0 0 0 0 1 2 9 3 5pp?? 而且很容易看出 k kp 1kkpp? ? kkE p p?? 12kkEE? 0 1 2 3 4 2 0 0 15 2322 / 3p p p p? ? ? （在二重根處線性收斂） 從 0 ? 開始用牛頓 拉夫森迭代求多項式3( ) 3 2f x x x? ? ?的二重根 p=，可得到下表中的值 k kp 1kkpp? ? kkE p p?? 1kkEE? 0 1 2 3 4 5 ? ?? ?? ?? ?? 可以看出，牛頓 拉夫森法收斂到二重根，但收斂速度很慢。 ( ) ( )kkf p f p?的 值 比的值趨近于 0 更快，因此當 kpp? 時， ()()kkfpfp?有定義。序列線性收斂，而且在每次迭代后，誤差以 1/2 的比例下降。我們總結下牛頓法在單根和二重根上的性能。 定理 （牛頓 拉夫森迭代的收斂速度） 設牛頓 拉夫森產生的序列 0{}nnp ?? ，收斂到函數(shù) ()fx的根 p，如果 p 是單根，則是二次收 斂，而且對于足夠大的 n有 21 ()2 ( )nnfpEEfp? ??? ? 16 如果 p 是 M 階多重根，則是線性收斂的，而且對于足夠大的 n 有1 1nnMEEM? ?? 值得注意的是：有時序列并不一定收斂，因為并不可能在 N 此迭代后總能找到結果，我們可以盡量的通過畫圖等各種方法來選擇 P0. 例如 ：設 () xf x x ?? ，而且 0 ? ，則 1 4p? ， 2 ? ，?? 15 354 943 4p ? 而且 {}kp 緩慢發(fā)散到無窮大。 割線法與加速收斂 割線法是對牛頓 拉夫森法的改進，它采用了試值法一樣的思想。 我們需要 2個靠近點 ( ,0)p 的初始點 00( , ( ))p f p 和 11( , ( ))p f p 。定義 2p 為經過兩個初始點的直線與 x 軸相交的橫坐標，由圖可以看出 P2 比 P0 或 P1 更靠近于P。 p2， p1， p0 相關的表示斜率方程為： 1010( ) ( )f p f pm pp?? ? 1210 ( )fpm pp?? ? 所以 1 1 02 1 0 1 10( ) ( )( , ) ( ) ( )f p p pp g p p p f p f p?? ? ? ?，根據(jù)兩點迭代公式可得到一般項為 1111( ) ( )( , ) ( ) ( )k k kk k k kkkf p p pp g p p p f p f p ?????? ? ? ? 單根上的割線法 ： 從 0p = 和 1p = 開始，利用割線法求多項式函數(shù)3( ) 3 2f x x x? ? ?的根 p=2. 解：根據(jù)迭代公式我們得 221111 33 2( , ) 33k k k kk k k k k k kp p p pp g p p p p p p???? ???? ? ? ? 我們得如下的迭代序列 17 其中收斂階為 R=（ 15? ） /2=； 當 P 是一個 M 階根時，我們可以通過對牛頓法改進，使得其在多重根的情況下的收斂階為 2 定理 （牛頓 拉夫森迭代的加速收斂） 設牛頓 拉夫森算法產生的序列線性收斂到根 x=p，其中 M1，則牛頓 拉夫森迭代公式 111()()kkkkM f ppp fp ????? ? 將產生 一個收斂序列 0{}kkp ?? 二次收斂到 p。 （二重根情況下的加速收斂） 從 p0= 開始，使用加速牛頓 拉夫森迭代求函數(shù) 3( ) 3 2f x x x? ? ?的二重根 p=1 解： 由于 M=2，加速公式變?yōu)? 31 1 11 211( ) 3 42 ( ) 3 3k k kkk kkf p p ppp f p p? ? ?? ????? ? ?? ? 可得到下表中的值 k kp 1kkpp? ? kkE p p?? /kkEE? 0 1 2 3