Polynomial interpolation Flashcards

1
Q

What is the main question in polynomial interpolation?

A

How do we represent mathematical functions on a computer?

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Why are polynomials easy to store?

A

Only need to store n + 1 coefficients

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

What is the Weierstrass Approximation Theorem?

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

What is interpolation?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

What is the simplest interpolating polynomial?

A

Truncated taylor series

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Why is a truncated Taylor series the simplest interpoalting polynomial?

A

It uses only a single node x0

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

What is Taylor’s Theorem?

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

What is the following known as?

A

Taylor polynomial of degree n

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

What is the remainder in Taylor’s theorem called?

A

Lagrange form of the remainder

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

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

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

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

A

The Lagrange remainder

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

What is truncation error?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

How does truncation error change as you use more terms?

A

It decreases

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

What is Rolle’s Theorem?

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Prove the Lagrane form of the remainder.

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

For general n, what are the polynomial interpolation conditions?

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

What is another way to write the following conditions?

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

What is the following called?

A

The Vandermonde matrix

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

What is the Vandermonde matrix?

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

What is the determinant of the Vandermonde matrix?

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

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

A

Problem Sheet

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

What is the existence/uniqueness theorem for interpolating polynomials?

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

Prove the unique part of the following theorem.

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

What is one way to solve the Vandermode matrix?

A

Gaussian elimination

25
Q

What basis do we use in the Vandermode matrix?

A

{1, x, x2 .. }

26
Q

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

27
Q

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

28
Q

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

A
  • 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
Q

How is the basis {lk} picked?

A

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

30
Q

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

A

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
Q

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

32
Q

What is the Newton form of the interpolating polynomial?

33
Q

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

A

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

34
Q

What is the theorem about the divided differences?

35
Q

Prove the following theorem.

36
Q

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

A

Tree diagrams

37
Q

What is the generic error for an interpolating formula?

A

f(x) - pn(x) |

38
Q

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

39
Q

Prove the following theorem.

40
Q

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

A

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
Q

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

42
Q

What is the Runge phenomenon?

A

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

43
Q

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

A

Chebyshev nodes

44
Q

How do the spacing of chebyshev nodes change?

A

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

45
Q

What is the xj formula to find the Chebyshev nodes?

46
Q

What is the Lemma about the Chebyshev points?

47
Q

Prove the following Lemma.

48
Q

What is the theorem about Chebyshev interpolation?

49
Q

Prove the following theorem.

50
Q

What are the Chebshev nodes projections of?

A

Equally spaced points around a circle

51
Q

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

52
Q

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

A

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

53
Q

What two interpolating polynomials have derivative conditions?

A
  1. Taylor polynomial
  2. Herminite polynomial
54
Q

What is the theorem about Hermite interpolation?

55
Q

Prove the following theorem.

56
Q

What is the formula for the Hermite basis functions?

57
Q

What is the formula for the Hermite interpolating polynomial?