2) Interpolation Flashcards
What is Weierstrass’ Theorem
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) | ≤ ε.
What is the Interpolation Problem
What is the Lagrange Basis Polynomial and the Lagrange Interpolation Polynomial
Describe the proof of the formation of the Lagrange Polynomial
How many complex roots does a non-zero polynomial of degree n have
Exactly n complex roots
What is the Lagrange Interpolation Theorem
What is the proof for the uniqueness of the Lagrange Interpolating Polynomial
What is the difference between the Lagrange Form and Ordinary Form of the Interpolation Polynomial
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
- 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
Explain briefly why it is important in interpolation problems that the xi are distinct
- 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
Give the expression (x+2)^1/2 - x^1/2 how could you rewrite this expression to avoid cancellation
What is the error formula for Lagrange interpolation in a function continuously differentiable up to order n+1
What is the bound on the error in Lagrange Interpolation for a function’s nth-degree polynomial approximation
What is the Newton’s Divided Difference formula for an interpolation polynomial
How are the coefficients in Newton’s Divided Difference formula computed
Using the divided difference table
What is the Runge Phenomenon
The case when increasing the number of equispaced interpolation points does not always result in a decrease in interpolation error
What are the drawbacks of the standard Lagrange interpolation polynomial representation
- 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
What is the Barycentric form of the Lagrange interpolation polynomial
Describe the proof for the Barycentric form of the Lagrange interpolation polynomial
How does the Barycentric form improve the computation of the Lagrange interpolation polynomial
- 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.
