Numerical Analysis

Math 370  MWF 2:30-3:25
Spring 1997  127 Fowler

(03.07.97) \underline{End of Interpolation; Intro to Approximation Theory} We have come to the end of the section on Interpolation. Before we do so let’s recall what we know about cubic splines. There isn’t a known error formula for the natural cubic spline, but there is one for the clamped cubic spline: Let M be a bound for f^{(4)}(x) on [a, b]. Then if S is the unique clamped spline interpolant with respect to the nodes a = x_{0} < x_{1} < … < x_{n} = b then

{max \atop a ≤ x ≤ b} |f(x) − S(x)| ≤ \frac{5M}{384} {max \atop 0 ≤ j ≤ n − 1} (x_{j+1} − x_{j})^{4}

Let’s recall the definition of a cubic spline interpolating function. That, is write down what the function S(x) which interpolates f(x) on the nodes a = x_{0} < x_{1} < … < x_{n−1} < x_{n}

What are the equations that one has to solve in order to find the cubic spline explicitly?

If the spline is clamped? If the spline is “free”? \underline{Example} Let’s compute the clamped cubic spline between the data points (8.6,18.50515) and (8.7,18.82091) given that at 8.6 we want f′ = 3.1517622 and at x = 8.7 we want f′ = 3.163323.

If I tell you the function f(x) = x ln(x) compare the exact error at x = 8.65 to the theoretical error bound at x = 8.65 Approximation Theory When we are doing interpolation we are given a set of n + 1 data points (x_{k}, f_{k}) which we believe are highly accurate. Our task is to try and use those values to obtain a function P (x) which approximates the unknown function f(x) at any x value.

In approximation theory, we also have a set of m data points (x_{k}, y_{k}) but this time we do not know that these values accurately reflect coordinates that the unknown function f(x) passes through. We define the deviation as δ_{k} = f(x_{k}) − y_{k}.

However, now we try and find a function P (x) such that the deviations between the function P (x) and the data points (x_{k}, y_{k}) is minimised. There is more than one way to do this.

How can we express these ideas mathematically? Can you picture it graphically?

Let’s assume that the polynomial we choose for P (x) is linear so that P (x) = ax + b Now what do we have to minimise? How can we do this minimization problem?

Some of these minimization problems are harder than others (why?) so we make the choice think about minimizing the least squares error. The least squares error E is defined as:

How do we find the minimum of this function? What are the variables in this function?

Let’s do it:

The solution is:

The line P (x) = ax + b is known as the “least squares” line, or “line of best fit”.

READ: Section 3.4 and 8.1