Polynomial interpolation

Question 1

What is the main question in polynomial interpolation?

Answer 1

How do we represent mathematical functions on a computer?

Question 2

Why are polynomials easy to store?

Answer 2

Only need to store n + 1 coefficients

Question 3

What is the Weierstrass Approximation Theorem?

Answer 3

Question 4

What is interpolation?

Answer 4

Finding a p_n(x_i) = f(x_i) at a finite set of points x_i called nodes. Sometimes we also require the derivatives to match.

Question 5

What is the simplest interpolating polynomial?

Answer 5

Truncated taylor series

Question 6

Why is a truncated Taylor series the simplest interpoalting polynomial?

Answer 6

It uses only a single node x₀

Question 7

What is Taylor’s Theorem?

Answer 7

Question 8

What is the following known as?

Answer 8

Taylor polynomial of degree n

Question 9

What is the remainder in Taylor’s theorem called?

Answer 9

Lagrange form of the remainder

Question 10

What is the formula for the Lagrange form of the remainder?

Answer 10

Question 11

What can we use to bound the error of an approximation using Taylor’s theorem?

Answer 11

The Lagrange remainder

Question 12

What is truncation error?

Answer 12

The error that arises from approxiamting f with a truncated series, rather than due to rounding

Question 13

How does truncation error change as you use more terms?

Answer 13

It decreases

Question 14

What is Rolle’s Theorem?

Answer 14

Question 15

Prove the Lagrane form of the remainder.

Answer 15

Question 16

For general n, what are the polynomial interpolation conditions?

Answer 16

Question 17

What is another way to write the following conditions?

Answer 17

Question 18

What is the following called?

Answer 18

The Vandermonde matrix

Question 19

What is the Vandermonde matrix?

Answer 19

Question 20

What is the determinant of the Vandermonde matrix?

Answer 20

Question 21

Prove that the determinant of the Vandermonde matrix is the following.

Answer 21

Problem Sheet

Question 22

What is the existence/uniqueness theorem for interpolating polynomials?

Answer 22

Question 23

Prove the unique part of the following theorem.

Answer 23

Question 24

What is one way to solve the Vandermode matrix?

Answer 24

Gaussian elimination

Question 25

What basis do we use in the Vandermode matrix?

Answer 25

{1, x, x² .. }

Question 26

When we use the basis of polynomials {l_k} what does p_n(x) equal?

Answer 26

Question 27

For general n, what is the equation of the n+1 Lagrange polynomials?

Answer 27

Question 28

What is a problem with the Lagrange form of the interpolating polynomial?

Answer 28

* Expensive to evaluate since all the l_k must be computed * Chaning any nodes or adding a new node means all the l_k must all be recomputed from scratch

Question 29

How is the basis {l_k} picked?

Answer 29

So that we get the identity matrix meaning we get the following p_n(x). So we need the following.

Question 30

What is the main idea for the Newton form of the basis?

Answer 30

Find a basis where p_n+1 = p_n + g_n+1(x) so that adding new nodes is easier than the lagrange form os the basis

Question 31

What is the formula for the {n_k} in the Newton basis.

Answer 31

Question 32

What is the Newton form of the interpolating polynomial?

Answer 32

Question 33

What is the the other notation which is commonly used for a_k in the Newton form of the interpolating polynomial?

Answer 33

a_k = f[x₀,x₁, ..., x_n]

Question 34

What is the theorem about the divided differences?

Answer 34

Question 35

Prove the following theorem.

Answer 35

Question 36

What do the diagrams for the Newton form of the interpolting polynomial look like?

Answer 36

Tree diagrams

Question 37

What is the generic error for an interpolating formula?

Answer 37

| f(x) - p_n(x) |

Question 38

What is Cauchy's theorem for the error in an interpolating formula?

Answer 38

Question 39

Prove the following theorem.

Answer 39

Question 40

How do you find what the maximum value of the error in Cauchy's formula?

Answer 40

The maximum of the node polynomial w(x) occurs at a turning point or at an end point, so find and use that value of x.

Question 41

What is the formula for w(x), the node polynomial?

Answer 41

Question 42

What is the Runge phenomenon?

Answer 42

When p_n converges to f in the middle, but diverges more and more near the ends.

Question 43

What type of nodes do we choose to avoid the Runge phenomenon?

Answer 43

Chebyshev nodes

Question 44

How do the spacing of chebyshev nodes change?

Answer 44

Places more nodes at the end of the interbal where most of the error is occuring at

Question 45

What is the x_j formula to find the Chebyshev nodes?

Answer 45

Question 46

What is the Lemma about the Chebyshev points?

Answer 46

Question 47

Prove the following Lemma.

Answer 47

Question 48

What is the theorem about Chebyshev interpolation?

Answer 48

Question 49

Prove the following theorem.

Answer 49

Question 50

What are the Chebshev nodes projections of?

Answer 50

Equally spaced points around a circle

Question 51

What is the upper bound for the error in a Chebyshev polynomial?

Answer 51

Question 52

What is the basic idea behind adding derivative conditions to interpolating polynomials?

Answer 52

Find polynomial that match one or more derivatives of f at the nodes, as well as function values

Question 53

What two interpolating polynomials have derivative conditions?

Answer 53

1. Taylor polynomial 2. Herminite polynomial

Question 54

What is the theorem about Hermite interpolation?

Answer 54

Question 55

Prove the following theorem.

Answer 55

Question 56

What is the formula for the Hermite basis functions?

Answer 56

Question 57

What is the formula for the Hermite interpolating polynomial?

Answer 57