#computes the set of divided differences def DividedDifferences(points): #we compute n from the size of the array n = len(points)-1 #create an array n+1 by n+1 divDiff = [[0 for i in range(n+1)] for i in range(n+1)] #first column will contain the y values #this is column 0! for row in [0,1,2,..,n]: divDiff[row] = points[row] #compute, recursively the div differences #one column at a time #in second column will have f[.] #in third column will have f[.,.], etc for column in [1,2,..,n]: #for a column, compute the value in each row for row in [0,1, 2, .., n-column]: divDiff[row][column] = ((divDiff[row+1][column-1] - divDiff[row][column-1]) / (points[row+column] - points[row])) return divDiff def printDividedDifferences(points): #we compute n from the size of the array n = len(points)-1 divDiff = DividedDifferences(points) for row in [0,1, 2, .., n]: print points[row],"\t|", [divDiff[row][column] for column in [0,1,2,..,n-row]] #compute the Newton interpolation polynomial def Newton_Interpolation(x, points): #we compute n from the size of the array n = len(points) - 1 #the very first step is computed here #p0(x)=y0 p(x) = points #new term will be x-x0 #it will eventually store (xk-x0)(xk-x1)...(xk-xk-1) newTerm(x) = x - points for k in range(1,n+1): #we repeatedly add the new data point #first compute the new c c = ((points[k] - p(points[k])) / newTerm(points[k])) #and then add it to the interpolating function p(x) = p(x) + c*newTerm(x) #prepare for next iteration newTerm(x) = newTerm(x) * (x-points[k]) return p
points = [[-2, 1],[-1, 4],[0, 11],[1,16],[2,13],[3,-4]] printDividedDifferences(points) print print "Create Newton interpolation polynomial and check results" print #call the function and find the final answer f(x) = Newton_Interpolation(x, points) print "Interpolating polynomial f(x) = ", f(x) print "f([points]) = ", [f(pt) for pt in points] print
-2 | [1, 3, 2, -1, 0, 0] -1 | [4, 7, -1, -1, 0] 0 | [11, 5, -4, -1] 1 | [16, -3, -7] 2 | [13, -17] 3 | [-4] Create Newton interpolation polynomial and check results Interpolating polynomial f(x) = -(x + 2)*(x + 1)*x + 2*(x + 2)*(x + 1) + 3*x + 7 f([points]) = [1, 4, 11, 16, 13, -4]
We get a cubic interpolating polynomial from the difference table.
This divided difference table when augmented with two additional data points, shows 0 coefficients for higher power terms
and so the interpolating polynomial remains unchanged as a cubic.
n = 1 M = 1 h = 0.01 1/(4*(n+1))*M*h^(n+1)
Let be a function such that is continuous on and satisfies . Let be the polynomial of degree that interpolates at equally spaced nodes in , including the endpoints. Then on , where h = (b − a)/n is the spacing between nodes.
Linear interpolation is used for each segment therefore we have points and with interval width the accuracy is determined by
Setting is justified by trigonometric analysis since all derivatives of or are themselves or trig functions
and hence bounded by 1.
The maximum accuracy of given by this linear interpolation is .
n = 1 M = 1 h = sqrt(8 * .5 * 10^-5.) N = ceil(pi.n(100) / h); N
This analysis is based on the same error estimation formula used in Exercise 2.
Five decimal places of accuracy means the error must be .
Linear interpolation is used for each segment so we have points.
The minimum number of entries needed is 497.
No. The formulas are incomplete. The correct formulas are: