Unexpected output from Newton's method

I have this code for solving Newton's method and in the last iteration, the output values have come wrong. Those values should not be negative as I checked it manually on paper. As far as I know the code is right but I cannot figure out why is it displaying negative values and also the final u value should ideally be a positive value in between 0开发者_开发百科 and 1. Here is the code:

import copy
import math

tlist = [0.0, 0.07, 0.13, 0.15, 0.2, 0.22] # list of start time for the phonemes

w = 1.0

def time() :
    t_u = 0.0
    for i in range(len(tlist)- 1) :
        t_u = t_u + 0.04 # regular time interval
        print t_u
        print tlist[i], ' ' , tlist[i+1], ' ', tlist[i -1]
        if t_u >= tlist[i] and t_u <= tlist[i + 1] :
            poly = poly_coeff(tlist[i], tlist[i + 1], t_u)
            Newton(poly) 
        else :
            poly = poly_coeff(tlist[i - 1], tlist[i], t_u)
            Newton(poly) 

def poly_coeff(start_time, end_time, t_u) :
    """The equation is k6 * u^3 + k5 * u^2 + k4 * u + k0 = 0. Computing the coefficients for this polynomial."""
    """Substituting the required values we get the coefficients."""
    t0 = start_time
    t3 = end_time
    t1 = t2 = (t0 + t3) / 2
    w0 = w1 = w2 = w3 = w
    k0 = w0 * (t_u - t0)
    k1 = w1 * (t_u - t1)
    k2 = w2 * (t_u - t2)
    k3 = w3 * (t_u - t3)
    k4 = 3 * (k1 - k0)
    k5 = 3 * (k2 - 2 * k1 + k0)
    k6 = k3 - 3 * k2 + 3 * k1 -k0 

    print k0, k1, k2, k3, k4, k5, k6
    return [[k6,3], [k5,2], [k4,1], [k0,0]]

def poly_differentiate(poly):
    """ Differentiate polynomial. """
    newlist = copy.deepcopy(poly)

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

    return newlist

def poly_substitute(poly, x):
    """ Apply value to polynomial. """
    sum = 0.0 

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

def Newton(poly):
    """ Returns a root of the polynomial"""
    x = 0.5  # initial guess value 
    epsilon = 0.000000000001
    poly_diff = poly_differentiate(poly) 

    while True:
        x_n = x - (float(poly_substitute(poly, x)) / float(poly_substitute(poly_diff, x)))

        if abs(x_n - x) < epsilon :
            break
        x = x_n
        print x_n
    print "u: ", x_n
    return x_n

if __name__ == "__main__" :
    time()

The output for the last iteration is the following,

where k6 = -0.02, k5 = 0.03, k4 = -0.03 and k0 = 0.0

0.2
0.2   0.22   0.15
0.0 -0.01 -0.01 -0.02 -0.03 0.03 -0.02
-0.166666666667
-0.0244444444444
-0.000587577730193
-3.45112269878e-07
-1.19102451449e-13
u: -1.42121180685e-26

The initial guess value is 0.5 so if it is substituted in the polynomial then the output is -0.005.

Then again the same initial value is substituted in the differentiated polynomial. The result of that is -0.015.

Now these values are substituted in the Newton's equation then the answer should come as 0.166666667. But the actual answer is a negative value.

Thank you.

---

Ah, I see now.

Just as you say,

float(poly_substitute(poly, x))

evaluates to -0.015. Then,

float(poly_substitute(poly_diff, x))

evaluates to -0.01. Thus, substituting for these values and for x,

x_n = 0.5 - ( (-0.015) / (-0.01) )
x_n = 0.5 - 0.6666666...
x_n = -0.166666...

Your manual math was what was at fault, not the code.

---

The polynomial as given has a single solution at x = 0. The code is working fine.