22
$\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
    Commented Jun 17, 2014 at 23:40
  • 1
    $\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$ Commented 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
    Commented Jun 18, 2014 at 4:46
  • 1
    $\begingroup$ Any arbitrary 3 points, then. $\endgroup$
    – chharvey
    Commented 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
    Commented Apr 18, 2015 at 17:01

4 Answers 4

19
$\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 equal to or smaller than $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$
5
  • 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$ Commented 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$ Commented Jun 16, 2021 at 15:00
  • $\begingroup$ @Quotenbanane You are right. Thank you for pointing out my mistake. $\endgroup$
    – mfl
    Commented 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$ Commented Oct 31, 2021 at 16:48
  • $\begingroup$ The polynomial $p_n(x)$ as stated " of degree n" is not correct. It's of a degree $\leq n.$ This might seem trivial but it's extremely important to not remember the interpolation problem (and solution) as: throught $n+1$ points there is unique polynomial of degree $n$-- this is not true. What's true is that through $n+1$ points there is unique polynomial of degree $\leq n.$ For example every polynomial $p$ of degree $\leq n$ conincides with it's Lagrange interpolating polynomial $L_n(p,x)$ of $n+1$ nodes. And the Lagrange polynomial of any function of $n+1$ nodes is of degree most $n.$ $\endgroup$
    – Petar
    Commented Jul 3, 2023 at 12:59
15
$\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$
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
    Commented Oct 3, 2021 at 8:50
5
$\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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .