'''Newton's method for cubic equations of the form
f(x) = x**3 + c[0]*x**2 + c[1]*x + c[2] = 0

Input:
    c = [c[0], c[1], c[2]]... vector of coefficients 
    x0 ... starting value
    tol ... desired accuracy of f(xi): computation stops if |f(xi)| <= tol
    maxk ... maximal number of iterations: program terminates after maxk 
        	iterations

Output:
    root xi and sequence of approximations X

Typical call of program: 
    from python08_1 import newton
    newton([0,0,-2], 1.0)   # newton(c, x0, tol, maxk)

'''

def newton(c, x0 = 0.0, tol = 1e-12, maxk = 100):
    
    x = x0
    X = [x] 
    
    for k in range(maxk):
       fx = x**3 + c[0]*x**2 + c[1]*x + c[2]
       dfx = 3*x**2 + 2*c[0]*x + c[1]
       
       x -= fx/dfx
       X += [x]
       
       '''If the error is small enough, we stop'''
       if abs(fx) < tol:
           break
    xi = x
    
    print('root = ', xi)
    print('convercence history = ', X)