11
$\begingroup$

I know given two points in the plane $(x_1,y_1)$ and $(x_2,y_2)$ there exists a unique 1st degree (linear) polynomial that passes through those points. We all learned in Algebra how to find the slope between those points and then calculate the y-intercept.

To take it down a notch, given the point $(a,b)$, the unique 0th degree polynomial that passes through it is $y=b$.

My conjecture is that given three points $(x_1,y_1)$, $(x_2,y_2)$, and $(x_3,y_3)$, there exists a 2nd degree (quadratic) polynomial that passes through these points, and furthermore, that polynomial is unique. I wonder, how would one determine the equation of this quadratic?

If my conjecture is correct, a corollary would be the generalization that given any $\left(n+1\right)$ points in the plane, there exists one unique $n$th degree polynomial that passes through those points.

Please prove, or disprove with a counter-example.

Further Readings:

$\endgroup$
  • 1
    $\begingroup$ You seem to be looking for interpolating polynomials. See this: en.wikipedia.org/wiki/… $\endgroup$ – Adriano Jun 17 '14 at 23:40
  • $\begingroup$ There is a unique polynomial of degree $\le n$ through $n+1$ points $(x_i,y_i)$, where the $x_i$ are distinct. The polynomial need not have degree exactly $n$. $\endgroup$ – André Nicolas Jun 18 '14 at 4:00
  • $\begingroup$ @AndréNicolas Not true. Given the points $(0,0)$, $(1,1)$, and $(2,3)$, there does not exist a 1st degree polynomial (a line) that goes through all 3 points. Did you mean "$\ge$"? $\endgroup$ – chharvey Jun 18 '14 at 4:46
  • $\begingroup$ I asked that the $x_i$ be distinct. $\endgroup$ – André Nicolas Jun 18 '14 at 4:47
  • $\begingroup$ Any arbitrary 3 points, then. $\endgroup$ – chharvey Jun 18 '14 at 4:49
9
$\begingroup$

Assume you have given $n+1$ points $(x_1,y_1),\cdots, (x_{n+1},y_{n+1}).$ (Of course, $x_i\ne x_j$ if $i\ne j.$) A polynomial of degree $n$ is of the form $p_n(x)=a_nx^n+\cdots+a_1x+a_0.$ To study the existence and uniqueness of such a polynomial consider the system of linear equations:

$$ \left\{\begin{array}{ccc} a_nx_1^n+a_{n-1}x_1^{n-1}\cdots+a_1x_1+a_0 & =& y_1\\ \vdots & &\\ a_nx_n^n+a_{n-1}x_n^{n-1}\cdots+a_1x_n+a_0 & =& y_n \end{array}\right. $$

We write the system as

$$ \begin{pmatrix}x_1^n & x_1^{n-1} &\cdots & x_1 & 1 \\ \vdots & \vdots & \ddots & \vdots \\ x_n^n & x_n^{n-1}& \cdots & x_n & 1\end{pmatrix} \begin{pmatrix} a_n \\ \vdots \\ a_0 \end{pmatrix}=\begin{pmatrix} y_1 \\ \vdots \\ y_n \end{pmatrix} $$

Since the matrix of coefficients of the system is non singular (it is a Vandermonde matrix (see Vandermonde)) the system has a unique solution, that is, there exists one polynomial of degree $n$ through the $n+1$ given points, and it is unique.

$\endgroup$
  • $\begingroup$ I think it would be waaaaay simpler to just say there are n unknowns with n equations. People are much more likely to be familiar with this resulting in a unique answer than they are to know what a Vandermonde matrix is (even though saying n unknowns with n equations is a slight simplification since the equations must be linearly independent). $\endgroup$ – Joseph Garvin Oct 12 '17 at 3:54
4
$\begingroup$

You can define

$$ P_k(x) = \prod_{\jmath \ne k}^n \frac{ x - x_\jmath }{ x_k - x_\jmath } $$

It is clear that

$$ P_k(x_\ell) = \delta_{k\ell} $$

Then you can define

$$ f(x) = \sum_{k=1}^n y_k P_k(x) $$

and you will find

$$ f(x_\ell) = \sum_{k=1}^n y_k \delta_{k\ell} = y_l$$

The function $f(x)$ is a polynomial of degree $n-1$

So in general, such a polynomial is given by

$$ f(x) = \sum_{k=1}^n y_k \prod_{\ell \ne k}^n \frac{ x - x_\ell }{ x_k - x_\ell} $$


Two points gives

$$ f(x) = y_1 \frac{x-x_2}{x_1-x_2} + y_2 \frac{x-x_1}{x_2-x_1} $$

Three points gives

$$ f(x) = y_1 \frac{x-x_2}{x_1-x_2} \frac{x-x_3}{x_1-x_3} + y_2 \frac{x-x_1}{x_2-x_1} \frac{x-x_3}{x_2-x_3} + y_3 \frac{x-x_1}{x_3-x_1} \frac{x-x_2}{x_3-x_2} $$

Four points gives

$$ f(x) = y_1 \frac{x-x_2}{x_1-x_2} \frac{x-x_3}{x_1-x_3} \frac{x-x_4}{x_1-x_4} + y_2 \frac{x-x_1}{x_2-x_1} \frac{x-x_3}{x_2-x_3} \frac{x-x_4}{x_2-x_4}\\ + y_3 \frac{x-x_1}{x_3-x_1} \frac{x-x_2}{x_3-x_2} \frac{x-x_4}{x_3-x_4} + y_4 \frac{x-x_1}{x_4-x_1} \frac{x-x_2}{x_4-x_2} \frac{x-x_3}{x_4-x_3}$$

and so on...

$\endgroup$
4
$\begingroup$

For an easy proof of uniqueness of such a polynomial (johannesvalks gives existence) assume we have $f,g$ of degree $n$ with $f(x_i)=g(x_i)=y_i$ for $1\leq i \leq n+1$.

Then $f-g$ has degree no bigger than $n$, so if $f-g\ne 0$ then $f-g$ has at most $n$ roots, but $f-g$ has at least $n+1$ roots so $f=g$.

$\endgroup$
0
$\begingroup$

johannesvalks' answer proves existence but not uniqueness. The Lagrange interpolation polynomials used will have degree $\le n$, as each is the sum of polynomials. Given two polynomials $P,Q$ with $\deg(P),\deg(Q)\le n$ both passing through $n+1$ distinct points $(x_i,y_i)$ with $1\le i\le n+1$, divide to get $P=(x-x_i)P_i+y_i$ and $Q=(x-x_i)Q_i+y_i$, for some $P_i,Q_i$, so that $$P-Q=(x-x_i)(P_i-Q_i).$$ Then $P-Q$ has $n+1$ distinct roots, while $P$ and $Q$ have at most $n$, so $P-Q$ must be the zero polynomial.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.