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)