Weierstrass Approximation Theorem: If feC[a,b], then there exists a polynomial P(x) such that P(x) is arbitrarily close to f(x) on [a,b].

Remark: This is an existence theorem. In practice, finding the polynomial might be very difficult and of very high degree.

Taylor Polynomials: These are created by using Taylor's theorem and throwing away the remainder term.

• One must know the actual function value as well as its derivatives values at x=c  before this can be used. Often this is requiring too much and so this may not be useful.
• The Taylor's polynomial is only valid for interpolation in a small interval about x=c.  Look at error bound.
• This is not such a great method to use for real-life examples where the derivative values would most likely not be given or even easily approximated.
• Generally, Taylor's polynomials are only used for theoretical purposes.

Bad Ex: Approximate f(x)=1/x about c=1 using higher and higher Taylor's polynomials. The approximation gets worse and worse as the degree of the polynomial gets larger.

LaGrange Polynomials: Given n+1 values of the function (x₀,f(x₀)) , (x₁,f(x₁)) , ... , (x_n,f(x_n)), find the polynomial of degree at most n which passes through all these points.

Derivation:

1. Utilize a general nth degree polynomial and plug in the data values to get a system of equations in the coefficients.
2. Use Lagrange cardinal formulas. Writing these using a Horner-type arrangement gives a faster implementation.
3. Newton's Divided Differences...generally used when actually computing the polynomial.

Neville's Method: A recursive way to generate values of the Lagrange polynomial. It does not, however, give a formula but a value for each variable x.

Error bound: See page 57 for bound on the error of approximating f(x) with it's Lagrange polynomial.

Result: Any two polynomials of the same degree n which agree at n+1 points are equal.

Pf: Suppose f(x), g(x) are of degree n and agree at n+1 points.
Then, r(x)=f(x)-g(x) is of degree at most n with n+1 roots gives r(x)=0.

4 = a + b + c
0 = a - b + c
9 = 4a + 2b + c

But if we write p(x)=c + b(x-1) + a(x-1)(x+1), then plugging in the points yields (solving as we go along)

4 = c
0 = c - 2b, or b=2
9 = c + b + 3a, or a=1,

Newton's Divided Differences: Successively build up the polynomial by finding the coefficients as above.
 

(x₀,f₀) gives p₀(x) = f₀, passes through the one point.

(x₁,f₁) gives p₁(x) = p₀(x) + (x-x₀)b₁, passes through the first two points if b₁=(f₁-f₀)/(x₁-x₀).

(x₂,f₂) gives p₂(x) = p₁(x) + (x-x₀)(x-x₁)b₂, passes through the first three points if b₂=?.
 

f[x_j,...,x_k] = (f[x_j+1,...,x_k] - f[x_j,...,x_k-1]) / (x_k - x_j), for j<k.

If x₀ > x₁ > ... > x_n, this is called Newton's Backward Divided Difference Polynomial.

If Dx is constant, the Divided Difference Formulas can be written in a closed form involving the binomial coefficents.
 

Program Subroutine To Determine the Newton's Divided Differences:

c_j=f(x_j) for j=0,1,...,n

for k= 1:n

    for j=n:-1:k

        c_j:=(c_j-c_j-1)/(x_j-x_j-k)

    end

end

Storage: Only need one vector, replacing as below:

f₀= c₀

f₁     f[x₀,x₁] = c₁

f₂     f[x₁,x₂]    f[x₀,...,x₂] = c₂

...

f_n      f[x_n-1,x_n]         f[x_n-2,...,x_n]       f[x_n-3,...,x_n]    ... f[x₀,...,x_n] = c_n
 

Programming Assignment: Implement Newton's divided difference method for determining the interpolating polynomial for an input set (of up to 20) data points. Evaluate the resulting polynomial for at least 100 equally spaced values and write these (x,y) points to a file. Read this file into some graphing software and graph them there. Use several example data sets and see what you get for approximations. For one example, compute your data points using the function f(x)=1/(1+x²) on the interval [-5,5]. What happens as the number of data points "n" used here increases?

(To do this project, perhaps write a function which accepts as input the points to interpolate and returns the Newton's coefficients. Write another function which accepts as input the x-values and these Newton's coefficients and returns one y-value along the interpolant.)
 

Hermite Interpolation: Not only are the function values specified but also several derivative values. We will only consider the case when we match function values and 1st derivative values. This is implemented using a set of basis functions similar to Lagrange.
 

Piecewise Interpolation: Instead of using one polynomial (possibly of very high degree) for the entire interval of interest, use several polynomials each defined on small intervals. Then, to obtain the y-value for a given x-value, one must first determine which formula to use. Then, evaluate that formula for the given x-value. If x₀ < x₁ < ... < x_n, and x₀ < x < x_n, then one can determine which interval x belongs to by considering the iteration:

k = 0

Repeat

    k = k+1

    (Use the kth formula...)

Until x < x_k

Return k

    p(u) = H₀(u) f(0) + H₁(u) f '(0) + H₂(u) f '(1) + H₃(u) f(1) , where

• H₀(u) = (1-u)²(1+2u)
• H₁(u) = (1-u)²u
• H₂(u) = (u-1)u²
• H₃(u) = (3-2u)u².

If data points (x_k, y_k) and slope values m_k are given, then the piecewise formula for the interval [x_k-1 , x_k] is given by

    p_k(x) = H₀( (x-x_k-1)/Dx_k )y_k-1 + H₁((x-x_k-1)/Dx_k )m_k-1Dx_k + H₂((x-x_k-1)/Dx_k )m_kDx_k + H₃((x-x_k-1)/Dx_k )y_k.

Notice, if we desire to evaluate this piecewise approximation for a fixed number of equally spaced points in each sub-interval, we can evaluate the basis polynomials once and store the results in vectors. These then can be reused for each interval.
 

Cubic Splines: Piece cubics S_k(x) = a_k + b_k(x-x_k-1) + c_k(x-x_k-1)² + d_k(x-x_k-1)³, for x_k-1 < x < x_k, together in such a way that the resulting approximation is continuous and has 2 continuous derivatives (no visible kinks). So, we impose the conditions:

• S_k(x_k-1) = y_k-1, which yields n equations, for k=1 to n,

a_k = y_k-1,
• S_k(x_k) = y_k, which yields n equations, for k=1 to n,
  a_k + b_kDx_k + c_kDx_k² + d_kDx_k³ = y_k,
• S_k^'(x_k) = S_k+1^'(x_k), which yields n-1 equations, for k=1 to n-1, 
  b_k + 2c_kDx_k + 3d_kDx_k² = b_k+1,
• S_k^''(x_k) = S_k+1^''(x_k), which yields n-1 equations, for k=1 to n-1,
  2c_k + 6d_kDx_k = 2c_k+1.

End Conditions:

1. Free spline - Assume S''(a) = S''(b)=0. This means the curve "loses" its concavity as you approach the endpoints.
2. Clamped spline - For m_k given, set S'(a)=m₀, S'(b)=m₁. This means the curve is forced to go in a given direction at each end.
3. Bessel ends - Set m_k automatically by using the tangent to the parabola which passes through the first three data points.
4. Quadratic ends - For a=x₀, set S''(a)=S''(x₁) and similarly for the other end.
5. Not-a-knot - Force the cubic polynomials on the first two and the last two intervals to actually be the same spline

Introduce Bezier curves as recursively linearly interpolating....
 

Bezier Interpolants: Suppose that we are given "control points" b_k = (bx_k, by_k) such that we desire a polynomial interpolant which passes through the first control point b₀ and the last one b_n, while the other points serving as attractors of the curve. Then, the curve can be given parametrically as

x(t) = S bx_k B_k(t), and

y(t) = S by_k B_k(t),

Derivative Continuity of Bezier Interpolants: The derivative of a Bezier curve is a Bezier curve of one less degree by simply taking the derivative of the formulas above. By equating these derivatives at the points where two curves meet, we force the resulting piecewise interpolant to be smooth. We can continue to force successive derivative to be equal at the points where the curves meet to get an interpolant with very high degree of smoothness. Notice, the similarity to splines.