反復ニュートンの方法

Question

私はこのコードを与えられた多項式と初期推測値のニュートンの方法を解くことができます。私はニュートンの方法が実際に反復的なプロセスに変わりたいと思っています。プログラムは、出力値 "x_n"が一定になるまで実行し続ける必要があります。 x_nの最終的な値は実際のルートです。また、私のアルゴリズムでこのメソッドを使用している間、常に0と1の間の正のルートを生成する必要があります。したがって、負の出力（ルート）を正の数に変換すると違いがありますか？ありがとうございました。

import copy 

poly = [[-0.25,3], [0.375,2], [-0.375,1], [-3.1,0]] 

def poly_diff(poly): 
    """ Differentiate a polynomial. """ 

    newlist = copy.deepcopy(poly) 

    for term in newlist: 
     term[0] *= term[1] 
     term[1] -= 1 

    return newlist 

def poly_apply(poly, x): 
    """ Apply a value to a polynomial. """ 

    sum = 0.0 

    for term in poly: 
     sum += term[0] * (x ** term[1]) 

    return sum 

def poly_root(poly): 
    """ Returns a root of the polynomial""" 

    poly_d = poly_diff(poly) 
    x = float(raw_input("Enter initial guess:")) 

    x_n = x - (float(poly_apply(poly, x))/poly_apply(poly_d, x)) 

    print x_n 

if __name__ == "__main__" : 
    poly_root(poly) 

Answer 1

最初に、poly_diffでは、指数部がゼロであるかどうかを確認して、単純に結果からその用語を削除する必要があります。さもなければ、微分がゼロで定義されていない状態になります。

def poly_root(poly): 
    """ Returns a root of the polynomial""" 
    poly_d = poly_diff(poly) 
    x = None 
    x_n = float(raw_input("Enter initial guess:")) 
    while x != x_n: 
     x = x_n 
     x_n = x - (float(poly_apply(poly, x))/poly_apply(poly_d, x)) 
    return x_n 

これでいいはずです。しかし、私は浮動小数点の丸め誤差のために、これが終了しないかもしれない特定の多項式に対して可能性があると思います。それは、最下位ビットのみが異なる近似の反復サイクルで終わることがある。変更の割合が下限に達するか、または反復回数の後に終了することがあります。

Answer 2

import copy 

poly = [[1,64], [2,109], [3,137], [4,138], [5,171], [6,170]] 

def poly_diff(poly): 

    newlist = copy.deepcopy(poly) 

    for term in newlist: 
     term[0] *= term[1] 
     term[1] -= 1 

    return newlist 

def poly_apply(poly, x): 

    sum = 0.0 

    for term in poly: 
     sum += term[0] * (x ** term[1]) 

    return sum 

def poly_root(poly): 

    poly_d = poly_diff(poly) 
    x = float(input("Enter initial guess:")) 

    x_n = x - (float(poly_apply(poly, x))/poly_apply(poly_d, x)) 

    print (x_n) 

if __name__ == "__main__" : 
    poly_root(poly)