# Interpolation of Symmetric Data

For symmetric data

$(x_i,y_i), i=-n,-n+1,..., n-1, n$

such that

$x_{-i}=-x_i$ and $y_{-i}=-y_i, i=0,1,...n$

what is the required degree for an interpolating polynomial $p$? Since there are $2n+1$ data points (one for each $\pm n$ plus one for when $i=0$) would the degree be at most $2n$? Or would only the points when $i\ge0$, be considered for a degree at most $n$?

Also, to show that the polynomial is odd (which is information given) so $-p(x)=p(-x)$, is it sufficient to show that since $p(x_{-i})=p(-x_i)$, then $p(-x_i)=-p(x_i)$?

Well, that is frequently a confusing issue. Let me try and organize it in this way.
In general, $2n+1$ points will be interpolated by a polynomial of degree at most $2n$.

When, like in this case, the $2n+1$ points $$\left( {x_{\,i} ,y_{\,i} } \right)\quad \left| {\;\left\{ \matrix{ i = - n, \ldots ,0, \ldots ,n \hfill \cr x_{\,i} = - x_{\,i} \hfill \cr y_{\,i} = - y_{\,i} \hfill \cr} \right.} \right.\quad \to \quad \left( {x_{\,0} ,y_{\,0} } \right) = \left( {0,0} \right)$$ constitute an anti-symmentric pattern, then they will be interpolated by a odd polynomial $$y(x)\quad \left| {\;y( - x) = - y(x)} \right.\quad \to \quad y(x) = \sum\limits_{1\, \le \,k\, \le \;n} {c_{\;2k - 1} x^{\,2k - 1} }$$

of degree (at most) $2n-1$ , thus having only $n$ undetermined coefficients, which you will set by imposing to pass through $n$ points.
These can be obviously the points with $i = 1, \ldots ,n$ (but not necessarily, they could also be chosen as $i = \pm k\quad \left| {\;k = 1, \ldots ,n} \right.$ ). The $n+1$ even coefficient $c_{\;0} ,c_{\;2} ,\, \ldots ,c_{\;2n}$ are null due to the anti-simmetry.
If the points where instead symmetric then the polynomial would be of degree (<=) $2n$, with $n+1$ undetermined coefficients. The additional indetermination ($c_{\;0}$) being due to that in this case ${y_{\,0} }$ is not fixed.
In conclusion, you can always apply the general method of interpolation. But when there is a symmetry, you can profitably reduce the interpolation and consider only the "independent" points.

• what is the difference between the symmetric and anti-symmetric patterns? Also, not sure if you couldn't see in my original post or if you just typed it wrong (negatives in the subscript are hard to see, not sure how to change it...), but $x_{-i}=-x_i$ so x sub -i (not i) equals -x sub i, and the same for the y's. Does this make the pattern symmetric or is it still anti-symmetric? – bowen.jane Jun 17 '16 at 2:00
• Take an example: $3$ points, $x={-1,0,1}$ , $y={-2,0,2}$ is according to the rules you gave, it has a symmetric pattern with respect to the origin, but it's anti-symmetric in the sense $y(-x)=-y(x)$, i.e. odd, it is interpolated by a line, degree =$1$, $y=mx$ to determine on $1$ point: e.g. $2=m1$. A symmetric (even) case ($y(-x)=y(x)$) would be $x={-1,0,1}$ , $y={2,1,2}$, a parabola, degree $2$, $y=a+bx^2$, two parameters to fix, by imposing $y(0)=1 and y(1)=2$, or $y(0)=1 and y(-1)=2$, **but not ** $y(-1)=2 and y(1)=2$. – G Cab Jun 17 '16 at 9:12
• Okay, that makes sense. Thanks!! – bowen.jane Jun 17 '16 at 14:25
• @GCab Would you please explain why the interpolating polynomial would be of degree at most $2n-1$? I understand why the polynomial should be odd, but I'm not sure why $(0, 0)$ is guaranteed to be one of the data points. And, even if $(0, 0)$ is in the data, aren't there still $2n+1$ distinct points, thus requiring an interpolant of degree at most $2n$? – sawghol Nov 17 at 17:33
• @sawghol: let's go by simple steps. Take a straight line. Take 3 points out of that - wherever placed - and interpolate with a degr. 2 ($y=a_0 + a_1 x+ a_2 x^2$) what will you obtain ? simply that $a_2=0$. If you take $10$ points on the line and interpolate with a deg. 9 poly, still you will have that all the higher coefficients will be null. Now, if the line is passing through the origin, if you take 2, 3, ..10 points, either all with positive abscissas, or all negative, or partly positive and negative, you always get the equation of a line trough the origin. Then see the examples above. – G Cab Nov 17 at 23:02

Thanks to G Cab for their help!

Here's an alternative solution that I pieced together with help from my professor:

Let $$p(x)$$ be the interpolating polynomial of degree at most $$2n$$ for these data. Define a new polynomial $$$$q(x) := p(x) + p(-x).$$$$ Then, $$q(x)$$ is also a polynomial of degree at most $$2n$$. Observe that $$p(x)$$ is odd on all of our abscissas; i.e., for all $$x_i$$ with $$i=-n,-n+1,...,n-1,n$$, we have $$$$p(x_i) = y_i = -y_{-i} = -p(x_{-i}) = -p(-x_i).$$$$ That is, for all $$x_i$$, we have \begin{align} p(x_i) + p(-x_i) = 0. \end{align} Therefore, all of the abscissas are roots of $$q(x)$$. This means that $$q(x)$$ has $$2n+1$$ roots. But, $$q(x)$$ is a polynomial of degree at most $$2n$$. The only polynomial that has a greater number of roots than its exact degree is the zero polynomial. Therefore, it must be that $$q(x) \equiv 0$$. This implies that $$p(x)$$ is odd for all real values of $$x$$, since \begin{align} q(x) = 0 & \implies \\ p(x) + p(-x) = 0 & \implies \\ p(x) = -p(-x). \end{align} Finally, we note that since $$p(x)$$ is odd, it cannot be of exact degree $$2n$$, because $$2n$$ is an even number. Therefore, $$p(x)$$ must be of degree at most $$2n-1$$.