Lagrange interpolation and partial fraction decomposition

Revision en2, by adamant, 2021-12-27 14:45:47

Hi everyone!

Today I'd like to write yet another blog about polynomials. It's quite well-known that the system

$\begin{cases}P(x_0) = y_0, \\ P(x_1) = y_1, \\ \dots \\ P(x_n) = y_n\end{cases}$

has a unique solution $P(x)$ among polynomials of degree at most $n$. One of direct ways to prove that such a polynomial exists is through Lagrange's interpolation. To have a better grasp of it, let's recall that $P(x) \equiv P(x_0) \pmod{x-x_0}$, thus the given system of equations can be perceived as

$\begin{cases}P(x) \equiv y_0 \pmod{x-x_0}, \\ P(x) \equiv y_1 \pmod{x-x_1}, \\ \dots \\ P(x) \equiv y_n \pmod{x-x_n}\end{cases}.$

It is known from the Chinese remainder theorem that $P(x)$ is unique modulo $Q(x) = (x-x_0)\dots(x-x_n)$ and can be explicitly computed as

$P(x) = \sum\limits_{i=0}^n y_i \frac{Q_i(x)}{Q_i(x_i)},$

where $Q_i(x) = \frac{Q(x)}{x-x_i}$. Noteworthy, $Q_i(x_i) = Q'(x_i)$, as $Q'(x) = Q_0(x) + \dots + Q_n(x)$.

History

Revisions

Rev. Lang. By When Δ Comment
en11 adamant 2021-12-28 14:17:03 1113 extra about switching from x^k to (x+a)^k
en10 adamant 2021-12-28 00:19:18 13 cut