CoCalc Public Filesassignment5.htmlOpen with one click!
Authors: Pat Monardo, Benjamin Young
Views : 80
Description: Jupyter html version of assignment5.ipynb
Compute Environment: Ubuntu 18.04 (Deprecated)

Exercise 1


Use a divided difference table to show that the following data can be represented by a polynomial of degree 3:

x -2 -1 0 1 2 3
y 1 4 11 16 13 -4
In [1]:
#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][0] = points[row][1]

    #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][0] - points[row][0]))
    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][0],"\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
    p(x) = points[0][1]
    #new term will be x-x0
    #it will eventually store (xk-x0)(xk-x1)...(xk-xk-1)
    newTerm(x) = x - points[0][0]
    for k in range(1,n+1):
        #we repeatedly add the new data point
        #first compute the new c
        c = ((points[k][1] - p(points[k][0])) / newTerm(points[k][0]))
        #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][0])
    return p
In [2]:
points = [[-2, 1],[-1, 4],[0, 11],[1,16],[2,13],[3,-4]]
print "Create Newton interpolation polynomial and check results"
#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[0]) for pt in points]
-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.

Exercise 2


Linear interpolation in a table of function values means the following: if y0=f(x0)y_0 = f(x_0) and y1=f(x1)y_1 = f(x_1) are tabulated values, and if x0<x<x1x_0 < x < x_1, then an interpolated value of f(x)f(x) is

How accurately can we determine sinx\sin x by linear interpolation, given a table of sinx\sin x to 10 decimal places for x[0,2]x \in [0, 2], with h=0.01h = 0.01?

In [3]:
n = 1
M = 1
h = 0.01



Let ff be a function such that f(n+1)f^{(n+1)} is continuous on [a,b][a, b] and satisfies f(n+1)(x)M|f^{(n+1)}(x)| \leq M. Let pp be the polynomial of degree n\leq n that interpolates ff at n+1n + 1 equally spaced nodes in [a,b][a, b], including the endpoints. Then on [a,b][a, b], where h = (b − a)/n is the spacing between nodes.

Linear interpolation is used for each segment therefore we have n+1=2n+1=2 points and with h=0.01h=0.01 interval width the accuracy is determined by

Setting M=1M = 1 is justified by trigonometric analysis since all derivatives of sin\sin or cos\cos are themselves sin\sin or cos\cos trig functions and hence bounded by 1.
The maximum accuracy of sinx\sin x given by this linear interpolation is 1.25×1051.25\times10^{-5}.

Exercise 3


A table of values of cosx\cos x is required so that the linear interpolation will yield five decimal places accuracy for any value of xx in [0,π][0, \pi]. Assume that the tabular values are equally spaced, and determine the minimum number of entries needed in this table.

In [4]:
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 12×105\leq \frac{1}{2} \times 10^{-5}.
Linear interpolation is used for each segment so we have n+1=2n+1=2 points.

The minimum number of entries needed is 497.

Exercise 4


Using Taylor series, establish the error term for the formula

Exercise 5


Derive the approximation formula

and show that its error term is of the form

Exercise 6


Averaging the forward-difference formula f(x)[f(x+h)f(x)]/hf'(x) ≈ [f(x + h) − f(x)]/h and the backward difference formula f(x)[f(x)f(xh)]/hf'(x) ≈ [f(x) − f(x − h)]/h, each with error term O(h)O(h), results in the central-difference formula f(x)[f(x+h)f(xh)]/(2h)f'(x) ≈ [f(x + h) − f(x − h)]/(2h), with error term O(h2)O(h^2). Show why Hint: Determine at least the first term in the error seriesfor each formula.

Exercise 7


Criticize the following analysis. By Taylor’s formula, we have

So by adding, it seems that we obtain an exact(!)exact(!) expression for f(x)f''(x): f(x+h)+f(xh)2f(x)=h2f(x). f(x + h) + f(x − h) − 2f(x) = h^2 f''(x). Is this correct?

No. The formulas are incomplete. The correct formulas are: