牛頓法求解非線性方程

基礎知識

• [步驟1] 準備：標明初始近似值 x 0 x_0 x0​，計算 f 0 = f ( x 0 ) , f 0 ′ = f ′ ( x 0 ) f_0=f(x_0),f_0'=f'(x_0) f0​=f(x0​),f0′​=f′(x0​)

• [步驟2] 疊代：按公式：

  x 1 = x 0 − f 0 / f 0 ′ x_1=x_0-f_0/f_0' x1​=x0​−f0​/f0′​

  疊代一次，得到新的近似值 x 1 x_1 x1​，計算 f 1 = f ( x 1 ) , f 1 ′ = f ( x 1 ) f_1=f(x_1),f_1'=f(x_1) f1​=f(x1​),f1′​=f(x1​)

• [步驟3]

  控制：如果 x 1 x_1 x1​滿足 ∣ δ ∣ < ε 1 |\delta|<\varepsilon_1 ∣δ∣<ε1​或 ∣ δ ∣ < ε 2 |\delta|<\varepsilon_2 ∣δ∣<ε2​，則終止疊代，以 x 1 x_1 x1​作為所求的根；否則轉步驟4。此處 ε 1 , ε 2 \varepsilon_1,\varepsilon_2 ε1​,ε2​是允許誤差，而

  δ = { ∣ x 1 − x 0 ∣ , ∣ x 1 ∣ < C ∣ x 1 − x 0 ∣ ∣ x 1 ∣ , ∣ x 1 ∣ ≥ C \delta= \left\{ \begin{aligned} |x_1-x_0|,|x_1|<C\\ \frac{|x_1-x_0|}{|x_1|},|x_1|\geq C\\ \end{aligned} \right. δ=⎩⎪⎨⎪⎧​∣x1​−x0​∣,∣x1​∣<C∣x1​∣∣x1​−x0​∣​,∣x1​∣≥C​

  其中C是取絕對誤差或相對誤差的控制常熟，一般可取 C = 1 C=1 C=1

• [步驟4]

  修改：如果疊代次數達到預先指定的次數N，或者 f 1 ′ = 0 f_1'=0 f1′​=0,則方法失敗；否則以 ( x 1 , f 1 , f 1 ′ ) (x_1,f_1,f_1') (x1​,f1​,f1′​)代替 ( x 0 , f 0 , f 0 ′ ) (x_0,f_0,f_0') (x0​,f0​,f0′​)轉步驟2繼續疊代。

代碼部分

import math
import numpy as np
import sympy
from sympy import *

x = symbols("x")
x_value=[]
x_iteration=[]
x_diff_iteration=[]


def function_value():
    return x*exp(x)-1

def Newton_Methods(x0,f):  #此處x0為初值,f為函數方程
    k=0                    #記錄疊代次數
    x_value.append(x0)
    x_iteration.append(f.subs(x,x0))
    x_diff_iteration.append(diff(f,x).subs(x,x0))
    while(k<10):            #小于規定疊代次數
        x_value.append(x_value[k]-(x_iteration[k]/x_diff_iteration[k]))
        x_iteration.append(f.subs(x,x_value[k+1]))
        x_diff_iteration.append(diff(f,x).subs(x,x_value[k+1]))
        if(x_iteration[-1]==x_iteration[-2]):    #終止疊代條件
            break
        k=k+1
    return x_value


result=Newton_Methods(0.5,function_value())

#格式化輸出
for i in range(len(result)):
    print('When k=%d,the x value is %.10f'%(i,result[i]))
           

運作結果

使用課本P223頁例題7驗證程式結果

用牛頓法解方程:

x e x − 1 = 0 xe^x-1=0 xex−1=0

結果如下：