21
$\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$
6
  • 1
    $\begingroup$ You seem to be looking for interpolating polynomials. See this: en.wikipedia.org/wiki/… $\endgroup$
    – Adriano
    Jun 17, 2014 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$ Jun 18, 2014 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, 2014 at 4:46
  • 1
    $\begingroup$ Any arbitrary 3 points, then. $\endgroup$
    – chharvey
    Jun 18, 2014 at 4:49
  • 1
    $\begingroup$ There is no quadratic (degree two) polynomial which passes through the points $(0,1)$, $(1,1)$, and $(2,1)$. There is however a constant function which does. $\endgroup$
    – user123641
    Apr 18, 2015 at 17:01

4 Answers 4

18
$\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+1}^n+a_{n-1}x_{n+1}^{n-1}\cdots+a_1x_{n+1}+a_0 & =& y_{n+1} \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+1}^n & x_{n+1}^{n-1}& \cdots & x_{n+1} & 1\end{pmatrix} \begin{pmatrix} a_n \\ \vdots \\ a_0 \end{pmatrix}=\begin{pmatrix} y_1 \\ \vdots \\ y_{n+1} \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$
4
  • 3
    $\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$ Oct 12, 2017 at 3:54
  • $\begingroup$ I think you forgot the equation for $(x_{n+1}, y_{n+1})$. Otherwise your Vandermonde matrix wouldn't even be quadratic ($n$ rows, $n+1$ columns) and you couldn't argue with the determinant $\endgroup$ Jun 16, 2021 at 15:00
  • $\begingroup$ @Quotenbanane You are right. Thank you for pointing out my mistake. $\endgroup$
    – mfl
    Jun 17, 2021 at 7:36
  • $\begingroup$ @JosephGarvin The first half of the answer already clearly shows n unknowns with n equations. So, if you want to stop there, you can stop there. He's just noting that the difficulty of proving that those n equations have a solution, is equal to the difficulty in proving that a Vandermonde has non-zero determinant, because both are proving the exact same thing. (Such a proof isn't that hard though) $\endgroup$ Oct 31, 2021 at 16:48
12
$\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$
1
  • $\begingroup$ Just to make sure I am following, does the "two points" then mean we're approximating a 2 degree polynomial? thank you! $\endgroup$
    – Guenter
    Oct 3, 2021 at 8:50
12
$\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$
3
$\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.