where no two <math>t_i</math> are the same, we assume the <math>y_n</math>:s are values of a function, <math>f</math>, at some certain <math>t</math>-points named <math>f(t_n)</math>. We know from Weierstrass' theorem[?] that there exists a unique polynomial of degree <math>n-1</math> that pass through all these points, and we write it thusly:
or more formal:
We notice that:
And the equation may be written:
And the solution giving the coefficients <math>c_i</math> is thus:
and this equation system will quickly grow to unrealistic proportions. Thus we need to find a better way to retrieve the coefficients <math>c_k</math>. It turns out there exists a recusive formula for doing this in an efficient way.
We see that the polynomial <math>P_k(t)</math> for a certain <math>k</math> may be defined recursively, thus:
so that <math>P_k</math> interpolates the function <math>f</math> in the points <math>t_1, t_2, ... t_n</math>. The coefficients <math>c_k</math> are dependent only on the obtained function values of <math>f</math> (our <math>y_k</math>:s), so it is natural to say that as <math>c_0</math> only depends on <math>f_1</math>, <math>c_1</math> only on <math>f_1, f_2</math> and <math>c_k</math> only on <math>f_1, f_2, ... f_k</math>, and we define a notation for the divided differences:
This definition gives us the formal definition of the divided differences:
So that for example:
These are not easily grasped when put like this, but once the functions are arranged in a tabular form, things look simpler. Here for example, for a data set of <math>(t_1,y_1), (t_2, y_2), (t_3, y_3), (t_4, y_4), (t_5, y_5)</math> (and we know that <math>f_k = y_k</math> for all <math>k</math>):
<math>t_1</math> | <math>f_1</math> | ||||
<math>t_2</math> | <math>f_2</math> | <math>f[t_1, t_2]</math> | |||
<math>t_3</math> | <math>f_3</math> | <math>f[t_2, t_3]</math> | <math>f[t_1, t_2, t_3]</math> | ||
<math>t_4</math> | <math>f_4</math> | <math>f[t_3, t_4]</math> | <math>f[t_2, t_3, t_4]</math> | <math>f[t_1, t_2, t_2, t_4]</math> | |
<math>t_5</math> | <math>f_5</math> | <math>f[t_4, t_5]</math> | <math>f[t_3, t_4, t_5]</math> | <math>f[t_2, t_3, t_4, t_5]</math> | <math>f[t_1, t_2, t_3, t_4, t_5]</math> |
On the diagonal of this table you will find the coefficients, as <math>c_0=f_1, c_1=f[t_1,t_2], c_2=f[t_1,t_2,t_3], c_3=f[t_1,t_2,t_3,t_4], c_4=f[t_1,t_2,t_3,t_4,t_5]</math>. Insert these into the formula at the top and you have your unique interpolation polynomial:
expanding into:
This is usually called the common newtonian interpolation polynomial.
Search Encyclopedia
|
Featured Article
|