2

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?

ghjk
  • 2,859

1 Answers1

2

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.

Ross Millikan
  • 374,822
  • Thank you for your insight, Ross:) However, for (b), I don't think we can fit a parabola going through 3 points if those 3 points are really RANDOM. I meant, if we have exactly 3 points which are roots of cubic polynomial, but not all of these 3 points are roots of a quadratic. – ghjk Apr 24 '15 at 03:33
  • Any three points that don't have the same $x$ coordinate can be fitted to a quadratic. Naively (which works here) a quadratic has three parameters and each point is one constraint. Lagrange interpolation provides an effective calculation of the parameters, which proves it works. Generally, you can fit an $n-1$ degree polynomial through $n$ points. – Ross Millikan Apr 24 '15 at 03:46