Encyclopedia > Newton polynomial

  Article Content

Newton polynomial

Newton polynomials (named after their inventor Isaac Newton) are polynomials used for polynomial interpolation. Rather than solving the huge Vandermonde matrix equation obtained in the polynomial interpolation by Gauss-Jordan elimination, we notice that we can do clever tricks by writing the polynomial in a different way. Given a data set:

<math>(t_0,y_0), (t_1,y_1), ... (t_n,y_n)</math>

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:

<math>P(t) = c_0 + c_1(t-t_1) + c_2(t-t_1)(t-t_2) + ... + c_n(t-t_1)(t-t_2)...(t-t_n)</math>

or more formal:

<math>P(t) = \sum_{i=0}^n c_i \prod_{j=0}^i (t-t_j)</math>

We notice that:

<math>P(t_k) = f(t_k), \forall k</math>

And the equation may be written:

<math>c_0 = f_1</math>
<math>c_0 + c_1(t_2-t_1) = f_2</math>
<math>c_0 + c_1(t_3-t_1) + c_2(t_3-t_1)(t_3-t_2) = f_3</math>

And the solution giving the coefficients <math>c_i</math> is thus:

<math>c_0 = f_1</math>
<math>c_1 = \frac{f_2-f_1}{t_2-t_1}</math>
<math>c_2 = \frac{f_3-f_1-\frac{t_3-t_1}{t_2-t_1}(f_2-f_1)}{(t_3-t_1)(t_3-t_2)}</math>

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.

Divided Differences

We see that the polynomial <math>P_k(t)</math> for a certain <math>k</math> may be defined recursively, thus:

<math>P_0(t) = c_0</math>
<math>P_k(t) = P_{k-1}(t) + c_k(t-t_1)(t-t_2)...(t-t_k)</math>

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:

<math>c_k = f[t_0, t_1, t_2, ..., t_k]</math>

This definition gives us the formal definition of the divided differences:

<math>f[t_i] = f(t_i) = f_i = y_i</math>
<math>f[t_1,t_2,t_3, ..., t_{k+1}] = \frac{f[t_1, t_2, ..., t_{k+1}] - f[t_1, t_2, ..., t_k]}{t_{k+1} - t_1}</math>

So that for example:

<math>f[t_1,t_2] = \frac{f_2-f_1}{t_2-t_1}</math>
<math>f[t_1,t_2,t_3] = \frac{f[t_2,t_3] - f[t_1, t_2]}{t_3-t_1}</math>

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:

<math>P_n(t) = \sum_{i=0}^n f[t_i] \prod_{j=0}^i (t-t_j)</math>

expanding into:

<math>P_n(t) = f_1 + f[t_1,t_2](t-t_1) + ... +f[t_1,...,t_n](t-t_1)...(t-t_n)</math>

This is usually called the common newtonian interpolation polynomial.


to be written

See Also

All Wikipedia text is available under the terms of the GNU Free Documentation License

  Search Encyclopedia

Search over one million articles, find something about almost anything!
  Featured Article
East Farmingdale, New York

... makeup of the town is 73.33% White, 14.83% African American, 0.15% Native American, 4.09% Asian, 0.09% Pacific Islander, 4.52% from other races, and 2.98% from two or ...

This page was created in 23 ms