Newton疊代法與Newton下山法的Python實作

Newton疊代法是利用Taylor展開将f(x)線性化，忽略二次導及以上的高階項，得到x*=x0-f(x0)/f’(x0)，令x*=x(k+1)，x0=x(k)，重複疊代

Newton又稱切線法

Newton下山法是在考慮到Newton法在區間内可能是發散的，因而增加一項參數l，要求abs（f（x(k)））在疊代時具有單調性，若不具有單調性，則令l減半

例子同前

利用向後差商估計導數

代碼如下

# -*- coding: utf-8 -*-
"""
Created on Sat Feb 16 20:06:57 2019

@author: Minghua Chen
"""

#牛頓疊代法
def f(x):
    return x**3-x-1

def df(x):
    df=(f(ans[-1])-f(ans[-1]-(ans[-1]-ans[-2])/(1000000000)))/(ans[-1]-(ans[-1]-(ans[-1]-ans[-2])/(1000000000)))
    return df

ans=[1.0,2.0]

def roll(x,l):
    f1=f(x)
    df1=df(f1)
    x1=x-l*f1/df1
    return x1

def main(x,a,b,e):
    l=1
    a=float(a)
    b=float(b)
    ans=[a,b]
    while abs(f(ans[-1]))>e:
        x=roll(x,l)
        ans.append(x)
        if abs(f(ans[-1]))>abs(f(ans[-2])):
            l=l/2
            x=ans[-2]
            ans.pop
        else:
            pass
    return ans[-1]

a=1
b=2
e=0.0000001
x=ans[-1]
print main(x,a,b,e)