High School
SAT
ACT
University
MCAT
LSAT
DAT
Wize University Linear Algebra Textbook > Systems of Linear Equations (SLEs) (Linear Systems)

Polynomial Interpolation

Geometric Interpretation of Linear SystemsPrevious Section
Basics of MatricesNext Section
Popular Courses
Find My Course
0:00 / 0:00

Polynomial Interpolation

Consider being given nn distinct points (x1,y1), …, (xn,yn)(\colorOne{x_1},\colorTwo{y_1}),\ \dots,\ (\colorOne{x_n},\colorTwo{y_n}).
There is a unique interpolating polynomial which passes through all of the given points, which we can write in the form:
p(x)=r0+r1x+⋯+rn−1xn−1p(x)=r_0+r_1x+\cdots+r_{n-1}x^{n-1}
Plugging each given point into the form of this polynomial, we get the system of linear equations:
r0+r1x1+⋯+rn−1x1n−1=y1r0+r1x2+⋯+rn−1x2n−1=y2⋮⋮r0+r1xn+⋯+rn−1xnn−1=yn\begin{array}{ccc} r_0+r_1\colorOne{x_1}+\dots+r_{n-1}\colorOne{x_1}^{n-1} &=& \colorTwo{y_1}\\[0.8em] r_0+r_1\colorOne{x_2}+\dots+r_{n-1}\colorOne{x_2}^{n-1} &=& \colorTwo{y_2}\\ \vdots&&\vdots\\ r_0+r_1\colorOne{x_n}+\dots+r_{n-1}\colorOne{x_n}^{n-1}&=& \colorTwo{y_n} \end{array}
We have to solve this SLE to find the values of each rir_i in the interpolating polynomial.
We can do this by reducing the following augmented matrix (the coefficient matrix consists of the coefficients of the rir_i):
[1x1⋯x1n−1y11x2⋯x2n−1y2⋮⋮⋱⋮⋮1xn⋯xnn−1yn]\left[\begin{array}{cccc|c} 1 & x_1 & \cdots & x_1^{n-1} & y_1\\ 1 & x_2 & \cdots & x_2^{n-1} & y_2\\ \vdots & \vdots & \ddots & \vdots & \vdots\\ 1 & x_n & \cdots & x_n^{n-1} & y_n \end{array}\right]

PAGE BREAK

Polynomial Interpolation: Illustration

Given three points A(1,1),  B(2,2),  C(0,−2)A(1,1),\ \ B(2,2),\ \ C(0,-2), find the interpolating polynomial going through all points.
3 points   ⟹  \implies a polynomial of degree at most 3-1 = 2.
If we were to find the solution vector for this system, we would see that r⃗=[r0r1r2]=[−24−1]\vec r = \begin{bmatrix} r_0\\ r_1\\ r_2\\ \end{bmatrix} = \begin{bmatrix} -2\\ 4\\ -1\\ \end{bmatrix}.

0:00 / 0:00

Example: Polynomial Interpolation

Let's revisit the example from the lesson.
Find an interpolating polynomial for the points A(1,1),  B(2,2),  C(0,−2)A(1,1),\ \ B(2,2),\ \ C(0,-2).
3 points   ⟹  \implies 2nd order polynomial:
p(x)=r0+r1x+r2x2p(x) = r_0+r_1x+r_2x^2
Plugging each point into p(x)p(x) gives:
(1,1):1r0+1r1+12r2=1(2,2):1r0+2r1+22r2=2(0,−2):1r0+0r1+02r2=−2\begin{array}{r ccrcr cr} (\colorOne{1},\colorTwo{1}): & 1r_0&+&\colorOne{1}r_1&+&\colorOne{1}^2r_2&=&\colorTwo{1}\\[0.6em] (\colorOne{2},\colorTwo{2}):& 1r_0&+&\colorOne{2}r_1&+&\colorOne{2}^2r_2&=&\colorTwo{2}\\[0.6em] (\colorOne{0},\colorTwo{-2}):& 1r_0&+&\colorOne{0}r_1&+&\colorOne{0}^2r_2&=&\colorTwo{-2} \end{array}
We can write the augmented matrix for this linear system and reduce:
[11111242100−2]R1↔R3⟶[100−212421111]R2−R1R3−R1⟶[100−202440113]12R2⟶[100−201220113]R3−R2⟶[100−2012200−11](−1)R3⟶[100−20122001−1]R2−2R3⟶[100−20104001−1]\begin{aligned} &\left[\begin{array}{rrr|r} 1 & 1 & 1 & 1\\ 1 & 2 & 4 & 2\\ 1 & 0 & 0 & -2\\ \end{array} \right] \begin{array}{l} R_1 \leftrightarrow R_3\\ \\ \\ \end{array}\\[2.5em] \longrightarrow &\left[\begin{array}{rrr|r} 1 & 0 & 0 & -2\\ 1 & 2 & 4 & 2\\ 1 & 1 & 1 & 1\\ \end{array} \right] \begin{array}{l} \\ R_2 - R_1\\ R_3 - R_1\\ \end{array}\\[2.5em] \longrightarrow &\left[\begin{array}{rrr|r} 1 & 0 & 0 & -2\\ 0 & 2 & 4 & 4\\ 0 & 1 & 1 & 3\\ \end{array} \right] \begin{array}{l} \\ \dfrac{1}{2}R_2\\ \\ \end{array}\\[2.5em] \longrightarrow &\left[\begin{array}{rrr|r} 1 & 0 & 0 & -2\\ 0 & 1 & 2 & 2\\ 0 & 1 & 1 & 3\\ \end{array} \right] \begin{array}{l} \\ \\ R_3 - R_2\\ \end{array}\\[2.5em] \longrightarrow &\left[\begin{array}{rrr|r} 1 & 0 & 0 & -2\\ 0 & 1 & 2 & 2\\ 0 & 0 & -1 & 1\\ \end{array} \right] \begin{array}{l} \\ \\ (-1)R_3\\ \end{array}\\[2.5em] \longrightarrow &\left[\begin{array}{rrr|r} 1 & 0 & 0 & -2\\ 0 & 1 & 2 & 2\\ 0 & 0 & 1 & -1\\ \end{array} \right] \begin{array}{l} \\ R_2 - 2R_3\\ \\ \end{array}\\[2.5em] \longrightarrow &\left[\begin{array}{rrr|r} 1 & 0 & 0 & -2\\ 0 & 1 & 0 & 4\\ 0 & 0 & 1 & -1\\ \end{array} \right] \end{aligned}
Since this is in RREF, we can now read off the unique solution for the coefficients of the interpolating polynomial:
r0=−2r1=4r2=−1  ⟹  P(x)=−2+4x−x2\begin{array}{rrr} r_0 &=& -2\\ r_1 &=& 4\\ r_2 &=& -1 \end{array} \quad \implies \quad P(x)=-2+4x-x^2

Find the interpolating polynomial of least degree for the data points (0,−3)\left(0,-3\right), (1,−1)\left(1,-1\right), and (−2,5)\left(-2,5\right).

Extra Practice
Find an interpolating polynomial of degree at most 2 of the data points (1,2)\left(1,2\right), (2,0)\left(2,0\right), and (3,12)\left(3,12\right).
Applications
Example: Polynomial Interpolation
Find an interpolating polynomial for the points A(1,1),  B(2,2),  C(0,−2)A(1,1),\ \ B(2,2),\ \ C(0,-2).
Find an interpolating polynomial of degree at most 2 of the data points (0,2)\left(0,2\right), (1,−1)\left(1,-1\right), and (2,1)\left(2,1\right).
Polynomial of least degree
Find the interpolating polynomial of least degree for the data points (0,−3)\left(0,-3\right), (1,−1)\left(1,-1\right), and (−2,5)\left(-2,5\right).
Quadratic equations and matrices
Find a quadratic equation (of the form ax2+bx+c=0ax^2+bx+c=0) that passes through the points (0,-3), (1,-1) and (2,3).
Practice Question: Least Squares for Polynomials
Find the cubic polynomial which best fits the data points (−2,−1),(−1,1),(0,0),(1,−2),(2,3)(-2,-1),(-1,1),(0,0),(1,-2),(2,3) in the least squares sense.
Example: Least Squares for Linear Functions
Example: Least Squares for Linear Functions
Find the equation of the line that comes as close as possible to passing through the points: (0,1),(2,3),(3,4),(4,7)(0,1),(2,3),(3,4),(4,7).
Example: Least Squares for Linear Functions
Example: Least Squares for Linear Functions
Find the equation of the line that comes as close as possible, in the least squares sense, to passing through the points: (0,1),(2,3),(3,4),(4,7)(0,1),(2,3),(3,4),(4,7) .
Solution:
Example: Least Squares for Polynomials
Example: Least Squares for Polynomials
Find the equation of a quadratic polynomial that comes as close as possible to passing through the points: (1,2),(1,3),(2,3)(1,2),(1,3),(2,3).