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?

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?

8

What is the following known as?

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?

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?

15

Prove the Lagrane form of the remainder.

16

For general n, what are the polynomial interpolation conditions?

17

What is another way to write the following conditions?

18

What is the following called?

The Vandermonde matrix 

19

What is the Vandermonde matrix?

20

What is the determinant of the Vandermonde matrix?

21

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

Problem Sheet

22

What is the existence/uniqueness theorem for interpolating polynomials?

23

Prove the unique part of the following theorem.

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?

27

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

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.

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.

32

What is the Newton form of the interpolating polynomial?

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?

35

Prove the following theorem.

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?

39

Prove the following theorem.

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?

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?

46

What is the Lemma about the Chebyshev points?

47

Prove the following Lemma.

48

What is the theorem about Chebyshev interpolation?

49

Prove the following theorem.

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?

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?

55

Prove the following theorem.

56

What is the formula for the Hermite basis functions?

57

What is the formula for the Hermite interpolating polynomial?

58