next up previous contents
下一頁: 有關本文件 ... 上一頁: Series and Taylor Polynomials 前一頁: Taylor's Polynomials 泰勒多項式   目 錄

Newton's Method 牛頓法


牛頓法



找出方程式的零是代數跟微積分的基本問題, 有的時候這一類的問題可以用代數的形式去解決 ,舉例來說 ,你可以找到二次方程式的根。

f (x) = 2x2 - 13x + 1

藉由使用二次公式去解

2x2 - 13x + 1 = 0

然而在現實生活中,你常常會遇到一些找不到他的零的方程式, 在某一些例子中你可以用不同的逼近法去求出根, 而其中一種叫做牛頓法, 而這一個方法將會在這一節提到。

檢視一個方程式 f ,就像是圖 10.11 所示, 再這一個方程式中當 x = c 將會出現零, 為了要逼近這一個根,我們選 x1 接近 c ,而且構置一個中心在 x1 的一階泰勒展開式,

S1(x) = f (x1) + f'(x1)(x - x1)

就圖形來看呢,你可以說明這一個展開式跟切線在 f 這一個函數的點 (x1, f (x1)) 上的圖是一樣的 ,牛頓法就是建構在假設 f 的圖跨過 x 軸交的點和這一個切線 跨過 x 軸時交的點相同, 伴隨著這個假設 ,令 S1(x) 等於 0, x 解出

\begin{displaymath}\begin{aligned}
f(x_{1})+f'(x_{1})(x-x_{1}) & =0 \\
x-x_{1...
...})} \\
x & =x_{1}-\frac{f(x_{1})}{f'(x_{1})}\\
\end{aligned}\end{displaymath}

而把這一個結果的值當作一個新的代入值 ,而且希望會更好 逼近這一個零值 c, 然而從這一個逼近值 x1 ,你將造成一個第二次的逼近

x2 = x1 - $\displaystyle {\frac{f(x_{1})}{f'(x_{1})}}$

如果你想要有一個更好的逼近,你可以用 x2 去算出 x3, 而不斷的重複應用這個過程就叫做牛頓法。


 -0.2cm牛頓法

c 為函數 f 的一個根且令函數為在包含 c 的一個開區間中為可微, 我們可以逼近 c,根據且使用底下的步驟:
1.
設一個"靠近" c 的啟使假設點。
2.
由此假設點來決定一個新的逼近點,根據此公式

xn + 1 = xn - $\displaystyle {\frac{f(x_{n})}{f'(x_{n})}}$

3.
假如 | xn - xn + 1| 小於我們所要的真確誤差量,則令 xn + 1 為我們最後的估計值,否則,回到第2個步驟,然後再求新的逼近值。
每一個逼近的過程我們稱為迭代。





範例 1    


用牛頓法
用牛頓法重複做三次去逼近

f (x) = x2 - 2

的根。 用 x1 = 1 當做第一個假設


解    f 的第一次微分是 f'(x) = 2x 然而牛頓法的重複計算公式是

xn + 1 = xn - $\displaystyle {\frac{f(x_{n})}{f'(x_{n})}}$ = xn - $\displaystyle {\frac{x_{n}^{2}-2}{2x_{n}}}$

這些三次重複計算的結果列於下表, 而第一次重複計算用圖形描述於圖 10.12。 然而逼近值是 x = 1.414216, 對於這一個特定的方程式你可以簡單的檢測零確定的位置。 $ \sqrt{2}$ $ \approx$ 1.414214, 然而再重複做三次牛頓法後你可以得到一個逼近值跟真正的根差距在 0.000002 之內。




範例 2    


用牛頓法
用牛頓法求 x = 0 的近似值

f (x) = 2x3 + x2 - x + 1

繼續重複直到兩個接近的近似值相差小於 0.001


解     看圖觀察 f 有唯一 0 發生在 x1 = - 1.2 附近,圖 10.13 ,重複三次牛頓法予以下表格。 因此,你可以估計 f (0) 約為 -1.23375




範例 3    


用牛頓法
用牛頓法求 x = 0 的近似值

f (x) = ex + x

繼續重複直到兩個接近的近似值相差小於 0.001


解     看圖觀察 f 有唯一 0 發生在 x1 = - 0.5 附近,圖 10.14 ,重複三次牛頓法予以下表格。 因此,你可以估計 f (0) 約為 -0.567143


牛頓法的收斂性



在例題 1.2.3 中近似值趨近於零,在牛頓法中表示為收斂, 但是牛頓法不是總是收斂,下面是兩種不收斂的情況:

1.
fxn = 0 ,對於一些 n ,看圖 10.15
2.
limn$\scriptstyle \to$$\scriptstyle \infty$ 不存在,看圖 10.15
這些類型的問題表示在圖 10.15 通常可以找到 x1 的較佳解, 這問題表示在圖 10.16 ,然而這通常都不能大意, 換句話說,牛頓法並不是對於所有的 x1 都會收斂。

f (x) = x$\scriptstyle {\frac{}{}}$13

試著跑跑看前幾頁的程式找方程式的近似值為 0 ,如果你做了,你會發現程式無法執行。




範例 4    


找兩函數圖形的交點
估計圖中交點

y = e-x2        和        y = x

表示於圖10.17,用牛頓法並持續重複直到兩接近的近似值小於 0.0001


解     兩圖的交點發生於 e-x2 = x ,表示

0 = x - e-x2

用牛頓法讓

f (x) = x - e-x2

並且重複公式

xn + 1 = xn - $\displaystyle {\frac{f (x_n) }{f (x_n) }}$ = xn - $\displaystyle {\frac{x_n-e^-x_n^2}{1+2x_ne^-x_n^2}}$

重複三次牛頓法予以下表格,開始於最初的近似值 x1 = 0.5 因此,你可以估計交點發生於當 x $ \thickapprox$ 0.65292 。


next up previous contents
下一頁: 有關本文件 ... 上一頁: Series and Taylor Polynomials 前一頁: Taylor's Polynomials 泰勒多項式   目 錄
math 2005-10-10