gibson:teaching:fall-2016:math753:newtondivdiff
====== Differences ====== This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision Next revision | Previous revision | ||
|
gibson:teaching:fall-2016:math753:newtondivdiff [2016/11/11 11:52] gibson |
gibson:teaching:fall-2016:math753:newtondivdiff [2016/11/11 12:15] (current) gibson |
||
|---|---|---|---|
| Line 3: | Line 3: | ||
| Newton's Divided Difference algorithm is a slick way to compute an $N$th order polynomial interpolant to a set of $N+1$ data points $(x_0, y_0), (x_1, y_1), \ldots, (x_N, y_N)$ with distinct $x_i$'s. | Newton's Divided Difference algorithm is a slick way to compute an $N$th order polynomial interpolant to a set of $N+1$ data points $(x_0, y_0), (x_1, y_1), \ldots, (x_N, y_N)$ with distinct $x_i$'s. | ||
| - | It produces a polynomial of in the form of [[gibson:teaching:fall-2016:math753:horner|Horner's method]] with base points, e.g. | + | It produces a polynomial in the form of [[gibson:teaching:fall-2016:math753:horner|Horner's method]] with base points, e.g. |
| \begin{equation*} | \begin{equation*} | ||
| - | P(x) = c_0 + (x - x_0) \, [c_1 + (x - x_1) [c_2 + (x - x_2) [c_3 + (x - x_3) \, c_4]]] | + | y = P(x) = c_0 + (x - x_0) \, [c_1 + (x - x_1) [c_2 + (x - x_2) [c_3 + (x - x_3) \, c_4]]] |
| \end{equation*} | \end{equation*} | ||
| + | If we plug in the data points $(x_i, y_i)$ for $i=0,1,\ldots, N$, to the $N$th-order generalization of the above equation, we get a series of $N+1$ equations in the $N+1$ unknowns $c_0, \ldots c_N$. | ||
| + | \begin{eqnarray*} | ||
| + | y_0 &=& c_0 \\ | ||
| + | y_1 &=& c_0 + (x_1-x_0) \, c_1 \\ | ||
| + | y_2 &=& c_0 + (x_2-x_0) \, c_1 + (x_2-x_0)(x_2-x_1) \, c_2 \\ | ||
| + | &\vdots& | ||
| + | \end{eqnarray*} | ||
| + | |||
| + | Lo and behold this is lower-triangular system of equations, which can be written in matrix form like this | ||
| \begin{equation*} | \begin{equation*} | ||
| Line 19: | Line 28: | ||
| 1 & x_k-x_0 & \ldots & \ldots & \prod_{j=0}^{N-1}(x_N - x_j) | 1 & x_k-x_0 & \ldots & \ldots & \prod_{j=0}^{N-1}(x_N - x_j) | ||
| \end{array}\right] | \end{array}\right] | ||
| - | \left[\begin{array}{c} c_0 \\ \\ \vdots \\ \\ c_{N} \end{array}\right] = | + | \left[\begin{array}{c} c_0 \\ c_1 \\ c_2 \\ \vdots \\ \\ c_{N} \end{array}\right] = |
| - | \left[\begin{array}{c} y_0 \\ \\ \vdots \\ \\ y_{N} \end{array}\right] | + | \left[\begin{array}{c} y_0 \\ y_1 \\ y_2 \\ \vdots \\ \\ y_{N} \end{array}\right] |
| \end{equation*} | \end{equation*} | ||
| + | |||
| + | Lower-triangular systems can be solved easily via forward substitution. It turns out that for this particular lower-triangular system, the solution can be computed easily by subtracting and dividing | ||
| + | numbers in a table. To see how that works, please refer to [[https://en.wikipedia.org/wiki/Newton_polynomial#Application|Newton Divided Difference Application]] (wikipedia). | ||
| + | |||
| + | Further reading: | ||
| + | |||
| + | * [[https://en.wikipedia.org/wiki/Newton_polynomial#Application|Newton Polynomial]] (wikipedia). | ||
gibson/teaching/fall-2016/math753/newtondivdiff.1478893945.txt.gz · Last modified: 2016/11/11 11:52 by gibson
Page Tools
Except where otherwise noted, content on this wiki is licensed under the following license: CC Attribution-Share Alike 3.0 Unported
