Correct Recursive Python Implementation Of Newton 's Differences Interpolation Method, Obtaining Some Of The Returned Values Inside Recursion

I wrote a recursion function in python to evaluate the sequence of an interpolation method. It's graphically explained in this image: f[x]=f(x) and f[x0,x1]= f[x1]-f[x0]) / (x1 -

Solution 1:

I have modified the script a bit.

    array=[]
    r='s'
    s=0
    def a_j(xx,yy):
        global r,s
        if r == 's':
            s=xx[0]
            r=0.0
        if len(yy) == 1:
            if xx[0]==s: array.append(yy[0])
            return float(yy[0])

        else:
            r=( a_j(xx[1:],yy[1:])  - a_j(xx[:-1],yy[:-1])) / (xx[-1]-xx[0])
            if xx[0]==s: array.append(r)
            return float(r)

    a_j([1,2,3,5],[4,3.5,4,5.6])
    print array

Output: [4, -0.5, 0.5, -0.10000000000000002]

also, the second example that you have given doesnt look correct. a_j([-2,-1,0,1,2], [13,24,39,65,106]) --> [13,11,4,7,-3]

above answer says that the 3rd element is 4.

    3rd element means --> x(-2,-1,0) -> x(-1,0)  -  x(-2,-1)/(2)
                                     -> x(0)-x(-1)/1  -  x(-1)-x(-2)/(1) /(2)
                                     ->(39-24) - (24-13)   /(2)
                                     ->15-11/(2)
                                     ->4/2 =2

Please correct me if i am wrong.

Solution 2:

You are getting negative values here because you have not enclosed the subtraction in parenthesis.Otherwise the code looks good.

   r = ( a_j(xx1,yy1)  - a_j(xx0,yy0)  ) / (xx[len(xx)-1]-xx[0])

http://www.mathcs.emory.edu/~valerie/courses/fall10/155/resources/op_precedence.html

Solution 3:

Try this:

    array=[]
    h={}
    r=0

    def a_j(xx,yy):
        global r
        if len(yy) == 1:
            h[int(xx[0])]=yy[0]
            return yy[0]

        else:
            r=( a_j(xx[1:],yy[1:])  - a_j(xx[:-1],yy[:-1])) / (xx[-1]-xx[0])
            h[int(''.join(str(i) for i in xx[::-1]))]=r
            return r

    a_j([0,1,2,3], [1,2.71828,7.38906,20.08554])
    array=[h[key] for key in  sorted(h.keys())]
    print array

Output: [1, 2.71828, 7.3890599999999997, 20.085540000000002, 1.71828, 4.6707799999999997, 12.696480000000001, 1.4762499999999998, 4.0128500000000003, 0.84553333333333347]

In this code, the values are first assigned to a dict with keys as the elements of xx reversed and converted to an integer.

Solution 4:

Since you are doing recursion, you will append each value as it exits the function, you will wind up getting the appending done in reverse xn, ... , x3, x2, x1

Once you finish the total recursion and exit for the last time, just reverse the list, which is relatively simple by several methods and has been asked before. I leave the method you want to use up to you (or remember "Google is your friend")