Polynomial interpolation Flashcards Preview

Numerical - Michaelmas > Polynomial interpolation > Flashcards

Flashcards in Polynomial interpolation Deck (58):
1

What is the main question in polynomial interpolation?

How do we represent mathematical functions on a computer?

2

Why are polynomials easy to store?

Only need to store n + 1 coefficients 

3

What is the Weierstrass Approximation Theorem?

A image thumb
4

What is interpolation?

Finding a pn(xi) = f(xi) at a finite set of points xcalled nodes. Sometimes we also require the derivatives to match.

5

What is the simplest interpolating polynomial?

Truncated taylor series 

6

Why is a truncated Taylor series the simplest interpoalting polynomial?

It uses only a single node x0

7

What is Taylor's Theorem?

A image thumb
8

What is the following known as?

Q image thumb

Taylor polynomial of degree n

9

What is the remainder in Taylor's theorem called?

Lagrange form of the remainder

10

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

A image thumb
11

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

The Lagrange remainder

12

What is truncation error?

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

13

How does truncation error change as you use more terms?

It decreases

14

What is Rolle's Theorem?

A image thumb
15

Prove the Lagrane form of the remainder.

A image thumb
16

For general n, what are the polynomial interpolation conditions?

A image thumb
17

What is another way to write the following conditions?

Q image thumb

A image thumb
18

What is the following called?

Q image thumb

The Vandermonde matrix 

19

What is the Vandermonde matrix?

A image thumb
20

What is the determinant of the Vandermonde matrix?

A image thumb
21

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

Q image thumb

Problem Sheet

22

What is the existence/uniqueness theorem for interpolating polynomials?

A image thumb
23

Prove the unique part of the following theorem.

Q image thumb

A image thumb
24

What is one way to solve the Vandermode matrix?

Gaussian elimination 

25

What basis do we use in the Vandermode matrix?

{1, x, x2 .. }

26

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

A image thumb
27

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

A image thumb
28

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

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

29

How is the basis {lk} picked?

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

A image thumb
30

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

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

31

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

A image thumb
32

What is the Newton form of the interpolating polynomial?

A image thumb
33

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

ak = f[x0,x1, ..., xn]

34

What is the theorem about the divided differences?

A image thumb
35

Prove the following theorem.

Q image thumb

A image thumb
36

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

Tree diagrams

37

What is the generic error for an interpolating formula?

| f(x) - pn(x) |

38

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

A image thumb
39

Prove the following theorem.

Q image thumb

A image thumb
40

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

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.

41

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

A image thumb
42

What is the Runge phenomenon?

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

43

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

Chebyshev nodes

44

How do the spacing of chebyshev nodes change?

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

45

What is the xj formula to find the Chebyshev nodes?

A image thumb
46

What is the Lemma about the Chebyshev points?

A image thumb
47

Prove the following Lemma.

Q image thumb

A image thumb
48

What is the theorem about Chebyshev interpolation?

A image thumb
49

Prove the following theorem.

Q image thumb

A image thumb
50

What are the Chebshev nodes projections of?

Equally spaced points around a circle

51

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

A image thumb
52

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

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

53

What two interpolating polynomials have derivative conditions?

  1. Taylor polynomial
  2. Herminite polynomial

54

What is the theorem about Hermite interpolation?

A image thumb
55

Prove the following theorem.

Q image thumb

A image thumb
56

What is the formula for the Hermite basis functions?

A image thumb
57

What is the formula for the Hermite interpolating polynomial?

A image thumb
58