2) Interpolation

Question 1

What is Weierstrass’ Theorem

Answer 1

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) | ≤ ε.

Question 2

What is the Interpolation Problem

Answer 2

Question 3

What is the Lagrange Basis Polynomial and the Lagrange Interpolation Polynomial

Answer 3

Question 4

Describe the proof of the formation of the Lagrange Polynomial

Answer 4

Question 5

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

Answer 5

Exactly n complex roots

Question 6

What is the Lagrange Interpolation Theorem

Answer 6

Question 7

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

Answer 7

Question 8

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

Answer 8

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

Question 9

Answer 9

• 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

Question 10

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

Answer 10

• 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

Question 11

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

Answer 11

Question 12

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

Answer 12

Question 13

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

Answer 13

Question 14

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

Answer 14

Question 15

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

Answer 15

Using the divided difference table

Question 16

What is the Runge Phenomenon

Answer 16

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

Question 17

What are the drawbacks of the standard Lagrange interpolation polynomial representation

Answer 17

• 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

Question 18

Answer 18

Question 19

What is the Barycentric form of the Lagrange interpolation polynomial

Answer 19

Question 20

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

Answer 20

Question 21

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

Answer 21

• 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.