CoCalc Shared Filesassignment5.html
Authors: Pat Monardo, Benjamin Young
Views : 17
Description: Jupyter html version of assignment5.ipynb
assignment5

### Exercise 1¶

#### $4.2-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
#p0(x)=y0
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]]
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[0]) 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]



#### Analysis¶

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¶

#### $4.2-6$¶

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

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

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

1/(4*(n+1))*M*h^(n+1)

Out[3]:
0.0000125000000000000

#### Analysis¶

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

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

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

### Exercise 3¶

#### $4.2-8$¶

A table of values of $\cos x$ is required so that the linear interpolation will yield ﬁve decimal places accuracy for any value of $x$ in $[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

Out[4]:
497

#### Analysis¶

This analysis is based on the same error estimation formula used in Exercise 2.
Five decimal places of accuracy means the error must be $\leq \frac{1}{2} \times 10^{-5}$.
Linear interpolation is used for each segment so we have $n+1=2$ points.
Therefore,

The minimum number of entries needed is 497.

### Exercise 4¶

#### $4.3-2$¶

Using Taylor series, establish the error term for the formula

### Exercise 5¶

#### $4.3-3$¶

Derive the approximation formula

and show that its error term is of the form

### Exercise 6¶

#### $4.3-5$¶

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

### Exercise 7¶

#### $4.3-6$¶

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

So by adding, it seems that we obtain an $exact(!)$ expression for $f''(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: