2) Interpolation Flashcards

1
Q

What is Weierstrass’ Theorem

A

For any f ∈ C([0,1]) and any ε > 0 there exists a polynomial p(x) such that max 0≤x≤1 | f (x) − p(x) | ≤ ε.

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

What is the Interpolation Problem

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

What is the Lagrange Basis Polynomial and the Lagrange Interpolation Polynomial

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

Describe the proof of the formation of the Lagrange Polynomial

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

How many complex roots does a non-zero polynomial of degree n have

A

Exactly n complex roots

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

What is the Lagrange Interpolation Theorem

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

What is the proof for the uniqueness of the Lagrange Interpolating Polynomial

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

What is the difference between the Lagrange Form and Ordinary Form of the Interpolation Polynomial

A

Interpolation polynomials are unique in the polynomial space P but can be expressed in various forms.
The term ‘Lagrange interpolation polynomial’ refers specifically to its representation in the Lagrange form

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q
A
  • Li(x) is equal to 1 at x = xi and 0 at all other xj for j ≠ i
  • P(xi) = xi * 1 + ∑j ≠ i xj * 0 = xi
  • Since the interpolating ploynomial is unique, P(x) must be unique hence ∑xiLi(x) = x for all x
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Explain briefly why it is important in interpolation problems that the xi are distinct

A
  • Distinct xi values ensure the uniqueness of the interpolating polynomial. If xi values are not distinct, finding a unique interpolating polynomial becomes impossible
  • The Lagrange basis functions Li (x) require distinct xi to avoid division by zero in their formulation
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Give the expression (x+2)^1/2 - x^1/2 how could you rewrite this expression to avoid cancellation

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

What is the error formula for Lagrange interpolation in a function continuously differentiable up to order n+1

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

What is the bound on the error in Lagrange Interpolation for a function’s nth-degree polynomial approximation

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

What is the Newton’s Divided Difference formula for an interpolation polynomial

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

How are the coefficients in Newton’s Divided Difference formula computed

A

Using the divided difference table

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

What is the Runge Phenomenon

A

The case when increasing the number of equispaced interpolation points does not always result in a decrease in interpolation error

17
Q

What are the drawbacks of the standard Lagrange interpolation polynomial representation

A
  • Computational Complexity: Evaluating the polynomial requires O(n^2 ) operations, which becomes inefficient as n increases.
  • Updating Difficulty: When new interpolation points are added, all the Lagrange basis polynomials must be recalculated
18
Q
A
19
Q

What is the Barycentric form of the Lagrange interpolation polynomial

A
20
Q

Describe the proof for the Barycentric form of the Lagrange interpolation polynomial

A
21
Q

How does the Barycentric form improve the computation of the Lagrange interpolation polynomial

A
  • Reducing Complexity: It allows the polynomial to be evaluated with only O(n) operations.
  • Simplifying Updates: New interpolation points can be added with an update cost of also O(n) operations by recalculating only the weights.