close

為什麼會想實作牛頓法呢？因為覺得如果能夠叫電腦幫我把方程式的根求出來很潮，所以…，嗯…。

牛頓法，是一種實數域及複數域上近似求解方程式的方法。

就不推導了（其實是推不出來），想要了解，請至維基百科或是線代啟示錄…。

主要是欲解多元一次方程式，所以透過牛頓法的公式來實作。

由公式來看

$$x_{n+1}=x_n-\frac{f\left(x_n\right)}{f'\left(x_n\right)}$$

簡單講，就是讓$x_{n+1}$反覆（瘋狂）迭代$x_n$，順利的話就會收斂到一個值，使$x_{n+1}$其與$x_n$的差值絕對值小於$\epsilon$，或是代回原式之值之絕對值小於$\epsilon$（理論上是要等於0，但跳出迭代的條件如果等於0，有可能會算到天荒地老都算不出結果），可為原式的一個根。（應該是吧？汗）

所以，需要準備的工具要有…

  1. 程式化的微分方法
  2. 初始值$x_0$
  3. 迭代的迴圈
  4. 可接受的eps（$\epsilon$）

 再來，整理一下思路…，虛擬碼（pseudocode）大guy4醬子…（亂寫）

============================================

牛頓法    演算法（Algorithm）

初始化起點$x_0$、容許誤差eps（$\epsilon$） 、初始化次數$i=0$

$x_1=x_0-\frac{f\left(x_0\right)}{f'\left(x_0\right)}$

Do

$i+=1$

$x_0=x_1$

$x_1=x_0-\frac{f\left(x_0\right)}{f'\left(x_0\right)}$

Loop Until   $\left| {x_{n+1}-x_n} \right|<\epsilon$

程式結束

============================================

其時間複雜度為

接著…實作後，來看看…效果如何…。以 $x^4+8x^3+24x^2+29x+8=0$ 為例

採用初始值$x_0$=100 開始迭代

最後就會得到一個實數解$-0.381966011250105$

代回去驗算一下，誤差大概為…$2.1166765158723\times10^{-15}\$，嗯…，應該還ok吧。

不過這樣子好像只能解到一個根，感覺不太夠用，所以我做了些調整…。

讓它跑三個值來試試看…，我寫了亂數，會隨機從1~1000，跟-1~-1000各挑1個值來當初始值，再搭配1個以0開始的初始值來run

最後得到了另一個實數解$-2.61803398874989$，代回驗算的誤差大約為$-1.912263716578\times10^{-14}$

然後…，用了一下專業軟體確認過…，這個方程式確實只有兩個實數解，大概是這樣。

arrow
arrow
    文章標籤
    牛頓法 方程式
    全站熱搜

    haruka 發表在 痞客邦 留言(0) 人氣()

    E-mail轉寄