Numerical Analysis

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

(03.10.97) \underline{Approximation Theory (Continued)} In approximation theory, like with interpolation, we 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. So we define the deviation as δ_{k} = P (x_{k}) − y_{k} and find a function P (x) such that the total 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.

We define a function E which represents the total deviation we are trying to minimize and we want to find P which minimizes E, where E can have different forms. Some Ways To Formulate E Are:

E_{1} = ∑_{k=1}^{m} |P (x_{k}) − y_{k}|

OR

E_{∞} = max_{1≤k≤m}|P (x_{k}) − y_{k}|

OR

E_{2} = ∑_{k=1}^{m}[P (x_{k}) − y_{k}]^{2}

From statistics we know that if the data are normally distributed then the square error is the best form of the error to use to measure how well P (x) is approximating the unknown function f(x) represented by the data y_{k}.

Let’s assume that the polynomial we choose for P (x) is linear so that P (x) = ax + b then the problem of finding P becomes …

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

Let’s do it:

The solution is:

Therefore

a = b =

The line P (x) = ax+b is known as the “least squares” line, or “line of best fit” or “regression line” Polynomial Of Best Fit What if P (x) is not a line but a polynomial of degree n? Let’s assume that

P (x) = ∑_{k=0}^{n} a_{k}x^{k}, where n < m − 1

Again, E = ∑_{k=1}^{m}[P (x_{k}) − y_{k}]^{2} which we want to minimize

This leads to n + 1 normal equations in the n + 1 unknowns a_{0}, a_{1}, … a_{n} \underline{Example} Consider the following data. We shall compute the line of best fit for the data and sketch it on the graph paper on the next page. You may try drawing what looks like a line of best fit by “eye” in one ink color and seeing how that compares with the computed regression line in a different ink color.

x_{i}  y_{i}  x_{i}^{2}  x_{i}y_{i}  P (x_{i})  |y_{i} − P (x_{i})|
1  1.3
2  3.5
3  4.2
4  5.0
5  7.0
6  8.8
7  10.1
8  12.5
9  13.0
10 15.6

\underline{Example} Let’s try and compute the least squares polynomial of degree 2 for the following data:

\begin{matrix}i & 1 & 2 & 3 & 4 & 5 \\ x_{i} & 0 & 0.25 & 0.5 & 0.75 & 1.00 \\ y_{i} & 1.0000 & 1.2840 & 1.6487 & 2.1170 & 2.7183 \end{matrix}

How many unknowns are you solving for? How many equations do you have? Write down the equations: