Chap 1. Polynomial Interpolation Flashcards
How do you write a polynomial of degree n?
Why do we write it as such?
pn = c * sum[i=1, i=n]: (x - ri).
A polynomial of degree n can never have more than n roots. This is the factored form.
What are the three techniques in this chap for interpolating a polynomial?
What are their differences?
The direct approach
Lagrange interpolation
Newton interpolation
Lagrange interpolation reconstructs the entire polynomial when adding an additional point, while Newton interpolation simply adds another component.
How do you execute Lagrange interpolation?
- Find the interpolation polynomial
pn(x) = sum(i=0, i=n): [yi * li(x)].
For this you need the cardinal functions li - Find the cardinal functions, given by
li(x) = prod[j=0, j!=i, j=n]: ((x - xj)/(xi - xj)).
Properties: li(xj) = {1 if i=j, 0 if i!=j}. Linearily independent, this forms a basis for Pn
What is the existence and uniqueness theorem?
Why is it such?
Theorem: Given n+1 points (xi,yi), [i=0, i=n], there only exists one interpolation polynomial of degree n that satisfies the following: pn(xi) = yi, i=0,…,n.
Reasoning: Given pn(x) and qn(x) as different polynomials covering these points, we can construct r(x) = pn(x)-qn(x). But given the above definitions, in all points xi is equal to 0, hence r = 0 and pn(x) = qn(x).
Extra note: this holds for a polynomial of degree n with n+1 points. Also, we’re not talking “n+1 roots”, but “n+1 points”.
How do you execute Newton interpolation?
- Find the interpolation polynomial
p(x) = sum[i=0,i=n] (ci*wi(x))
For this you need ci and wi - Find the weight, wi
wi(x) = sum[k=0, i-1] (x-xk)
w0 = 1. w1 = (x-x0). w2 = (x-x0)(x-x1), w3 = w2(x-x2)… - Find ci
Set up table of divided differences
a | f[x0]
b | f[x1] f[x0,x1]
c | f[x2] f[x1,x2] f[x0,x1,x2]
d | f[x3] f[x2,x3] f[x1,x2,x3] f[x0,x1,x2,x3]
And select the rightmost element in each row, where
f[x0…xn] = (f[x1…xn] - f[x0…xn-1])/(xn-x0) and
ci = f[x0…xi]
What is the interpolation error theorem?
f(x) - pn(x) = Mn+1 / (n+1)! * prod[i=0,i=n] (x-xi)
What is the error in equidistributed nodes?
|e(x)| =< h^(n+1) / (4*(n+1)) * Mn+1, where h = (b-a)/n
What are Chebyshev nodes?
How do we find them?
And how do we calculate the error?
Nodes that cause the least possible error in interpolation. The optimal interpolation points on a given interval [a,b] for n+1 nodes.
x~i = cos((2i+1)pi/(2(n+1)), i = 0…n
w_cheb(x) = prod[j=1, j=n] (x - x~i)
Transfer to an intervall [a,b]: x = (b-a)*x~/2 + (b+a)/2
max[a,b] |f(x)-pn(x)|_cheb:
<= (b-a)^(n+1) / (2^(2n+1)*(n+1)! * Mn+1
