5.2 Lagrange Interpolation

Lagrange Interpolation

Lagrange interpolation is a method for constructing the unique polynomial of degree at most $d$ that passes through a given points number of points. For $d+1$ points $(x_1,y_1),\dots ,(x_{d+1},y_{d+1})$ with all $x$-values distinct, the Lagrange interpolating polynomial is defined as
$f(x)={\sum }_{i=1}^{d+1}{y}_i\cdot {\Delta }_i(x),$
where each ${\Delta }_i(x)$ is a polynomial that equals $1$ at $x_i$ and $0$ at all other $x_j$, defined by
${\Delta }_i(x)=\frac{{\prod }_{j\ne i}^{}(x-x_j)}{{\prod }_{j\ne i}^{}(x_i-x_j)}.$

Each term $y_i\cdot {\Delta }_i(x)$ “activates” the value $y_i$ at point $x_i$, and the sum reconstructs a polynomial that agrees with all $d+1$ given points.

Intuition

At its core, the Lagrange interpolation polynomial $f(x)$ acts like a selector. It’s designed so that at any known input $x_i$, only the corresponding output value $y_i$ “activates,” while all the other terms go to zero. That means at each known data point, the polynomial behaves exactly like a switchboard: it connects the input $x_i$ to the output $y_i$, and only that one. For all other $x_j\ne x_i$, the function returns zero, so their corresponding $y_j$ values are effectively ignored at that moment.

The key to this selective behavior lies in the construction of each basis function ${\Delta }_i(x)$. The numerator of ${\Delta }_i(x)$ includes the variable $x$ and every $x_j$ where $j\ne i.$ That’s why ${\Delta }_i(x)$ is zero when $x=x_j$ for any $j\ne i$: it contains a factor like $(x-x_j)$, which kills the whole term. But when $x=x_i$, none of those subtracted terms zero out, so the numerator becomes a meaningful, nonzero number. This structure ensures that ${\Delta }_i(x)$only “activates” for the one point it’s designed to represent.

The denominator plays the role of a normalizing constant. It’s calculated by plugging the target input $x_i$ into the same expression used in the numerator. Since we know that’s the only input that makes the numerator nonzero, we simply scale the entire fraction so that ${\Delta }_i(x_i)=1$. This is critical, as it ensures that when we multiply ${\Delta }_i(x)by{y}_i$, the result is exactly $y_i$ at $x=x_i$, not some scaled version of it. For every other $x_j$, the numerator vanishes, and ${\Delta }_i(x_j)=0$, meaning $y_j$ won’t interfere.

Examples

(Medium) Lagrange? More like Lamegrange.

In this problem, you will walk through an alternative to Lagrange interpolation.

To begin, let’s say we wanted to interpolate a polynomial through a single point, $(x_0,y_0)$.

What would be the polynomial that we would get? $f_0(x)=y_0$.

Since we’re only given a single point, there’s not enough information to determine any slope or curvature. The only polynomial that fits is a constant function, so we get a degree-zero polynomial

Call the polynomial from the previous part $f_0(x)$. Now say we wanted to define the polynomial $f_1(x)$ that passes through the points $(x_0,y_0)$ and $(x_1,y_1)$.

If we write $f_1(x)=f_0(x)+a_1(x-x_0)$, what value of $a_1$ causes $f_1(x)$ to pass through the desired points? Let $f_0(x)=y_0$. Then, $f_1(x)=y_0+a_1(x-x_0)$. For the nontrivial input-output pair $(x_1,y_1)$, the polynomial turns into $y_1=y_0+a_1(x_1-x_0)⟺a_1=\frac{y_1-y_0}{x_1-x_0}$, which is precisely the slope of the line connecting the two points.

Now say we want a polynomial $f_2(x)$ that passes through $(x_0,y_0)$, $(x_1,y_1)$, and $(x_2,y_2)$.

If we write $f_2(x)=f_1(x)+a_2(x-x_0)(x-x_1)$, what value of $a_2$ gives us the desired polynomial? Let $f_2(x)=y_0+\frac{y_1-y_0}{x_1-x_0}(x-x_0)+a_2(x-x_0)(x-x_1)$. Plugging $(x_2,y_2)$, we obtain $y_2=y_0+\frac{y_1-y_0}{x_1-x_0}(x_2-x_0)+a_2(x_2-x_0)(x_2-x_1),$ and solve for $a_2$ such that $a_2=\frac{y_2-y_0}{(x_2-x_0)(x_2-x_1)}-\frac{y_1-y_0}{(x_1-x_0)(x_2-x_1)}=\frac{\frac{y_2-y_0}{x_2-x_0}-\frac{y_1-y_0}{x_1-x_0}}{x_2-x_1}.$