[Math] Interpolating $n$ points by piecewise quadratic polynomial

numerical methods

Given $n$ data points. Is it possible to interpolate them by piecewise quadratic polynomials with knots at the given data such that the quadratic interpolant is:

(a) Once continuously differentiable?

(b) Twice continuously differentiable? If it's not possible, what is the maximum number of given data points to meet this requirement?

My Progress By experimenting with different sets of $n$ data points, I realized that for part (a), I can do it since given any 2 points not on the same vertical line, we can always have a quadratic polynomial go through them. Now, for combining all piecewise quadratic polynomial, at each knot $2,3,4,5,..,n-1$, we need to have: $a_i(x_i)^2 + b_ix_i+c_i = a_{i+1}(x_{i})^2 + b_{i+1}x_{i} + c_{i+1}$, $2a_{i}x_i + b_i = 2a_{i+1}x_i+b_{i+1}$ for $i=1,2,…,n-1$. This is possible because we only have 3 unknowns with 2 data points $(x_i, y_i)$ and $(x_{i+1}, y_{i+1})$, so part (a) is done.

For part (b), we need $a_{i}=a_{i+1}$, $2a_{i}x_i + b_i = 2a_{i+1}x_i+b_{i+1}$ and $a_i(x_i)^2 + b_ix_i+c_i = a_{i+1}(x_{i})^2 + b_{i+1}x_{i} + c_{i+1}$ for $i=1,2,…,n-1$. But this is not possible since the only solution is $a_i = a_{i+1}, b_{i}= b_{i+1}$ and $c_{i}=c_{i+1}$.

From this conclusion, we can that the maximum given number of points to satisfy part (b) is $2$, since there is only an unique quadratic polynomials that can go through more than 2 given points, but we assume these $n$ points are randomly positioned for $n\geq 3$, so they can't all be on the same parabola.

Can someone please help review my solution above?

Best Answer

For a, at each knot you have two conditions plus the requirement that the quadratic go through the next point. That is three conditions and you have three coefficients to choose, so there should be a unique solution. In the first interval you do not have any match conditions but do have two points to go through. You expect a single parameter family of solutions, each of which should propagate through all your data.

For b, you can clearly do it for three points because one quadratic will go through them. There is nothing to match at the center point. Your argument is correct starting with four.

Related Solutions

Newton polynomial divided differences

The subject is better caught using a matricial reperesentation, and it is preferrable to index from $0$, as it provides a neater handling of the sums and products.

Given an assigned sequence $\left\{ {t_{\,0} ,t_{\,1} , \cdots ,t_{\,h} , \cdots } \right\}\quad \left| {\;t_{\,k} \ne t_{\,j} } \right.$, let's indicate by $\pi _{\,n} (t)$ the $n$-th degree polynomial $$ \pi _{\,n} (x,{\bf t}) = \prod\limits_{0\, \le \,j\, \le \,n-1} {\left( {x - t_{\,j} } \right)} $$ so that, with the convention of the null product, we have $$ \pi _{\,0} (x,{\bf t}) = 1\quad \pi _{\,1} (x,{\bf t}) = \left( {x - t_{\,0} } \right)\quad \cdots $$

We want to construct a polynomial of degree $h$ such that at the $h+1$ points $(t_0, \cdots,t_h)$ it takes the values $(f_0, \cdots,f_h)$, that is $$ p_{\,h} \left( {x,{\bf t},{\bf f}} \right)\;:\;\;p_{\,h} \left( {t_{\,k} ,{\bf t},{\bf f}} \right) = f_{\,k} \quad \left| {\,0 \le k \le h} \right. $$ While we could express it in terms of Lagrange polynomials, we want instead
to express it as a linear combination of the $\pi _{\,k} (x,{\bf t})$ polynomials $$ \eqalign{ & p_{\,h} \left( {x,{\bf t},{\bf f}} \right) = \left( {\matrix{ {\pi _{\,0} (x,{\bf t})} & {\pi _{\,1} (x,{\bf t})} & \cdots & {\pi _{\,h} (x,{\bf t})} \cr } } \right)\left( {\matrix{ {\beta _{\,0} } \cr {\beta _{\,1} } \cr \vdots \cr {\beta _{\,h} } \cr } } \right) = \cr & = \overline {{\bf \pi }_{\,h} } (x,{\bf t})\;{\bf \beta }_{\,h} \cr} $$ note that the vector ${\bf \pi }$ includes polynomials of varying degree.

Since the above holds for whichever value of $x$, it shall hold in particular for each $x=t_k$, and we get the LT matrix equation you already know $$ \bbox[lightyellow] { \eqalign{ & \left( {\matrix{ {f_{\,0} } \cr {f_{\,1} } \cr \vdots \cr {f_{\,h} } \cr } } \right) = \left( {\matrix{ 1 & 0 & \cdots & 0 \cr 1 & {\left( {t_1 - t_0 } \right)} & \cdots & 0 \cr \vdots & \vdots & \ddots & \vdots \cr 1 & {\prod\limits_{0\, \le \,j\, \le \,0} {\left( {t_h - t_{\,j} } \right)} } & \cdots & {\prod\limits_{0\, \le \,j\, \le \,h - 1} {\left( {t_h - t_{\,j} } \right)} } \cr } } \right)\left( {\matrix{ {\beta _{\,0} } \cr {\beta _{\,1} } \cr \vdots \cr {\beta _{\,h} } \cr } } \right) = \cr & = {\bf f} = {\bf P}({\bf t})\;{\bf \beta } \cr} }\tag{1}$$

Consider now that the Divided Difference of a sequence $y_k$ wrt $x_k$ $$ \left\{ \matrix{ \left[ {y_{\,q} } \right] = y_{\,q} \hfill \cr \left[ {y_{\,q} ,\, \ldots ,\,y_{\,q + n} } \right] = {{\left[ {y_{\,q + 1} ,\, \ldots ,\,y_{\,q + n} } \right] - \left[ {y_{\,q} ,\, \ldots ,\,y_{\,q + n - 1} } \right]} \over {x_{\,q + n} - x_{\,q} }} \hfill \cr} \right. $$ can be expressed as a linear combination of the $y_k$ values as follows $$ \bbox[lightyellow] { \left[ {y_{\,q} ,\, \ldots ,\,y_{\,q + n} } \right] = \sum\limits_{0\, \le \,m\, \le \,n} {{{y_{m + q} } \over {\prod\limits_{0\, \le \,k\, \ne \,m\, \le \,n} {\left( {x_{\,m + q} - x_{\,k + q} } \right)} }}} }\tag{2}$$ because in fact, taking $q=0$ wlog, it is $$ \eqalign{ & \left[ {y_{\,1} ,\, \ldots ,\,y_{\,n + 1} } \right] - \left[ {y_{\,0} ,\, \ldots ,\,y_{\,n} } \right] = \cr & = \sum\limits_{0\, \le \,m\, \le \,n} {{{y_{m + 1} } \over {\prod\limits_{0\, \le \,k\, \ne \,m\, \le \,n} {\left( {x_{\,m + 1} - x_{\,k + 1} } \right)} }}} - \sum\limits_{0\, \le \,m\, \le \,n} {{{y_m } \over {\prod\limits_{0\, \le \,k\, \ne \,m\, \le \,n} {\left( {x_{\,m} - x_{\,k} } \right)} }}} = \cr & = \sum\limits_{1\, \le \,m + 1\, \le \,n + 1} {{{y_{m + 1} } \over {\prod\limits_{1\, \le \,k + 1\, \ne \,m + 1\, \le \,n + 1} {\left( {x_{\,m + 1} - x_{\,k + 1} } \right)} }}} - \sum\limits_{0\, \le \,m\, \le \,n} {{{y_m } \over {\prod\limits_{0\, \le \,k\, \ne \,m\, \le \,n} {\left( {x_{\,m} - x_{\,k} } \right)} }}} = \cr & = \sum\limits_{1\, \le \,m\, \le \,n + 1} {{{y_m } \over {\prod\limits_{1\, \le \,k\, \ne \,m\, \le \,n + 1} {\left( {x_{\,m} - x_{\,k} } \right)} }}} - \sum\limits_{0\, \le \,m\, \le \,n} {{{y_m } \over {\prod\limits_{0\, \le \,k\, \ne \,m\, \le \,n} {\left( {x_{\,m} - x_{\,k} } \right)} }}} = \cr & = \sum\limits_{1\, \le \,m\, \le \,n} {{{y_m } \over {\prod\limits_{1\, \le \,k\, \ne \,m\, \le \,n + 1} {\left( {x_{\,m} - x_{\,k} } \right)} }}} + {{y_{n + 1} } \over {\prod\limits_{1\, \le \,k\, \le \,n} {\left( {x_{\,n + 1} - x_{\,k} } \right)} }} - {{y_0 } \over {\prod\limits_{1\, \le \,k\, \le \,n} {\left( {x_{\,0} - x_{\,k} } \right)} }} - \sum\limits_{1\, \le \,m\, \le \,n} {{{y_m } \over {\prod\limits_{0\, \le \,k\, \ne \,m\, \le \,n} {\left( {x_{\,m} - x_{\,k} } \right)} }}} = \cr & = - {{y_0 } \over {\prod\limits_{1\, \le \,k\, \le \,n} {\left( {x_{\,0} - x_{\,k} } \right)} }} + \sum\limits_{1\, \le \,m\, \le \,n} {y_m \left( {{1 \over {\prod\limits_{1\, \le \,k\, \ne \,m\, \le \,n + 1} {\left( {x_{\,m} - x_{\,k} } \right)} }} - {1 \over {\prod\limits_{0\, \le \,k\, \ne \,m\, \le \,n} {\left( {x_{\,m} - x_{\,k} } \right)} }}} \right)} + {{y_{n + 1} } \over {\prod\limits_{1\, \le \,k\, \le \,n} {\left( {x_{\,n + 1} - x_{\,k} } \right)} }} = \cr & = - {{\left( {x_{\,0} - x_{\,n + 1} } \right)y_0 } \over {\prod\limits_{1\, \le \,k\, \le \,n + 1} {\left( {x_{\,0} - x_{\,k} } \right)} }} + \sum\limits_{1\, \le \,m\, \le \,n} {y_m \left( {{{\left( {x_{\,m} - x_{\,0} } \right)} \over {\prod\limits_{0\, \le \,k\, \ne \,m\, \le \,n + 1} {\left( {x_{\,m} - x_{\,k} } \right)} }} - {{\left( {x_{\,m} - x_{\,n + 1} } \right)} \over {\prod\limits_{0\, \le \,k\, \ne \,m\, \le \,n + 1} {\left( {x_{\,m} - x_{\,k} } \right)} }}} \right)} + {{\left( {x_{\,n + 1} - x_{\,0} } \right)y_{n + 1} } \over {\prod\limits_{0\, \le \,k\, \le \,n} {\left( {x_{\,n + 1} - x_{\,k} } \right)} }} = \cr & = \left( {x_{\,n + 1} - x_{\,0} } \right)\sum\limits_{0\, \le \,m\, \le \,n + 1} {{{y_m } \over {\prod\limits_{0\, \le \,k\, \ne \,m\, \le \,n + 1} {\left( {x_{\,m} - x_{\,k} } \right)} }}} = \cr & = \left( {x_{\,n + 1} - x_{\,0} } \right)\left[ {y_{\,0} ,\, \ldots ,\,y_{\,n + 1} } \right] \cr} $$

Therefore, in matrix notation we will have $$ \bbox[lightyellow] { \eqalign{ & \left( {\matrix{ {\left[ {f_{\,0} } \right]} \cr {\left[ {f_{\,0} ,f_{\,1} } \right]} \cr \vdots \cr {\left[ {f_{\,0} , \ldots ,f_{\,h} } \right]} \cr } } \right) = \left( {\matrix{ 1 & 0 & \cdots & 0 \cr {{1 \over {\left( {t_{\,0} - t_{\,1} } \right)}}} & {{1 \over {\left( {t_{\,1} - t_{\,0} } \right)}}} & \cdots & 0 \cr \vdots & \vdots & \ddots & \vdots \cr {{1 \over {\prod\limits_{0\, \le \,k\, \ne \,0\, \le \,h} {\left( {t_{\,0} - t_{\,k} } \right)} }}} & {{1 \over {\prod\limits_{0\, \le \,k\, \ne \,1\, \le \,h} {\left( {t_{\,1} - t_{\,k} } \right)} }}} & \cdots & {{1 \over {\prod\limits_{0\, \le \,k\, \ne \,h\, \le \,h} {\left( {t_{\,h} - t_{\,k} } \right)} }}} \cr } } \right) \left( {\matrix{ {f_{\,0} } \cr {f_{\,1} } \cr \vdots \cr {f_{\,h} } \cr } } \right) = \cr & = {\bf D}_{\,{\bf div}} ({\bf t})\;{\bf f} \cr} }\tag{3}$$

The crucial point is that $$ \bbox[lightyellow] { {\bf D}_{\,{\bf div}} ({\bf t}) = {\bf P}({\bf t})^{\, - \,{\bf 1}} }\tag{4}$$ which in connection with (1) demonstrates the thesis.

In fact $$ \eqalign{ & \left[ {y_{\,0} ,\, \ldots ,\,y_{\,n} } \right]\quad \left| {\;y = f(x) = \prod\limits_{0\, \le \,j\, \le \,g - 1} {\left( {x - x_{\,j} } \right)} } \right.\quad = \cr & = \sum\limits_{0\, \le \,m\, \le \,n} {{{f\left( {x_m } \right)} \over {\prod\limits_{0\, \le \,k\, \ne \,m\, \le \,n} {\left( {x_{\,m} - x_{\,k} } \right)} }}} = \cr & = \left[ {g \le n} \right]\sum\limits_{g\, \le \,m\, \le \,n} {{{f\left( {x_m } \right)} \over {\prod\limits_{0\, \le \,k\, \ne \,m\, \le \,n} {\left( {x_{\,m} - x_{\,k} } \right)} }}} = \cr & = \left[ {g \le n} \right]\sum\limits_{g\, \le \,m\, \le \,n} {{{\prod\limits_{0\, \le \,j\, \le \,g - 1} {\left( {x_{\,m} - x_{\,j} } \right)} } \over {\prod\limits_{0\, \le \,k\,\, \le \,g - 1} {\left( {x_{\,m} - x_{\,k} } \right)} \prod\limits_{g\, \le \,k\, \ne \,m\, \le \,n} {\left( {x_{\,m} - x_{\,k} } \right)} }}} = \cr & = \left[ {g \le n} \right]\sum\limits_{g\, \le \,m\, \le \,n} {{1 \over {\prod\limits_{g\, \le \,k\, \ne \,m\, \le \,n} {\left( {x_{\,m} - x_{\,k} } \right)} }}} = \cr & = \left[ {g \le n} \right]\sum\limits_{0\, \le \,m\, \le \,n - g} {{1 \over {\prod\limits_{0\, \le \,k\, \ne \,m\, \le \,n - g} {\left( {x_{\,m + g} - x_{\,k + g} } \right)} }}} = \cr & = \left[ {g \le n} \right]\left[ {1_{\,g} ,\, \ldots ,\,1_{\,g + \left( {n - g} \right)} } \right] = \left[ {g = n} \right] \cr} $$ where the second step follows from being $f(x_m)=0$ for $m<g$ and where $[g \le n],\,[g = n]$ denotes the Iverson bracket.

Finding a polynomial that interpolates data (Newton’s method with Horner’s method)

As you stated, $p$ forms the Newton polynomial, which is just one way to write/find a polynomial interpolation.

Horner's method is a special way of writing polynomials which allows for more efficient evaluation. In the the particular case of Newton polynomials, one may write the solution in the form

$$c_0+(x-x_0)(c_1+(x-x_1)(c_2+\dots))$$

which allows one to avoid evaluating lots of products (repeated calculation of $(x-x_0)(x-x_1)(x-x_2)\dots$).

Best Answer

Related Solutions

Newton polynomial divided differences

Finding a polynomial that interpolates data (Newton’s method with Horner’s method)

Related Question