Lagrange interpolation and partial fraction decomposition

Revision en10, by adamant, 2021-12-28 00:19:18

Hi everyone!

Today I'd like to write yet another blog about polynomials. Specifically, I will cover the relationship between polynomial interpolation and Chinese remainder theorem, and I will also highlight how it is useful when one needs an explicit meaningful solution for partial fraction decomposition.

Lagrange interpolation

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$. A direct way to prove that $P(x)$ 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 system becomes

$\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}$

From the Chinese remainder theorem follows that $P(x)$ is unique modulo $Q(x) = (x-x_0)\dots(x-x_n)$ and is explicitly given 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)$ and $Q_j(x_i)=0$ when $i \neq j$.

Partial fraction decomposition

The other well-known fact is that for $\deg P < \deg Q$, rational function

$\frac{P(x)}{Q(x)}=\frac{P(x)}{(x-x_0)^{d_0} \dots (x-x_n)^{d_n}}$

can be represented as the sum

$\frac{P(x)}{Q(x)} = \sum\limits_{i=0}^n \frac{С_i(x)}{(x-x_i)^{d_i}}$

where $\deg C_i < d_i$. A bit less well-known are the explicit formulas to compute $C_i(x)$ and their connection to Lagrange interpolation. To begin with, let's look on this expression in the case $d_0= \dots = d_n = 1$ and multiply both sides with $Q(x)$. What we obtain is

$P(x) = \sum\limits_{i=0}^n c_i \frac{Q(x)}{x-x_i}=\sum\limits_{i=0}^n c_i Q_i(x).$

It is strikingly similar to the Lagrange interpolation expression, from which we may derive that

$c_i = \frac{P(x_i)}{Q_i(x_i)} = \frac{P(x_i)}{Q'(x_i)}.$

Thus, for monic square-free polynomial $Q(x)$ with $\deg P < \deg Q$ it holds that

$\frac{P(x)}{Q(x)}=\sum\limits_{i=0}^n \frac{P(x_i)}{Q'(x_i)}\frac{1}{x-x_i}.$

Multiplicities

Let's now understand what's going on when $Q(x)$ have multiple roots. The corresponding system of equations would look like this:

$\begin{cases} P(x) \equiv Y_0(x) \pmod{(x-x_0)^{d_0}},\\ P(x) \equiv Y_1(x) \pmod{(x-x_1)^{d_1}},\\ \dots \\ P(x) \equiv Y_n(x) \pmod{(x-x_n)^{d_n}}. \end{cases}$

Utilizing Chinese remainder theorem again, the solution to the whole system is given as

$P(x) = \sum\limits_{i=0}^n Q_i(x) \cdot [Y_i(x) \cdot Q_i^{-1}(x) \bmod (x-x_i)^{d_i}],$

where $Q_i(x) = \frac{Q(x)}{(x-x_i)^{d_i}}$. Let's get back to partial fraction decomposition. If both parts are multiplied by $Q(x)$, we get

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

thus $C_i(x) = [P(x) \cdot Q_i^{-1}(x) \bmod (x-x_i)^{d_i}]$ and the final formula is as follows:

$\frac{P(x)}{Q(x)} = \sum\limits_{i=0}^n \frac{[P(x) \cdot Q_i^{-1}(x) \bmod (x-x_i)^{d_i}]}{(x-x_i)^{d_i}}.$

Shifted remainders

For $d_i=1$ we knew that $Q^{-1}(x)$ modulo $x-x_i$ is equial to the inverse of $Q(x_i)$. To compute $Q^{-1}(x) \bmod (x-x_i)^{d_i}$, we should change the basis from $1,x,x^2, \dots$ to $1, x-x_i, (x-x_i)^2,\dots$, so that $Q(x) = Q_{x_i}(x-x_i)$. Now, computing $Q^{-1}(x)$ modulo $(x-x_i)^{d_i}$ is the same as computing $Q^{-1}_{x_i}(x)$ modulo $x^{d_i}$ and changing the basis back to $1,x,x^2,\dots$, which is left as an exercise.

Finally, to interpret the set of equations with multiplicities, we may reckon

$P(x) \equiv P(x_i) + P'(x_i) (x-x_i) + \dots + P^{(k)}(x_i) \frac{(x-x_i)^{k}}{k!}+ \dots$

Thus, we have the following equivalence:

$P(x) \equiv Y_i(x) \pmod{(x-x_i)^{d_i}} \iff \begin{cases} P(x_i) = Y_i(x_i),\\ P'(x_i)=Y_i'(x_i),\\ \dots\\ P^{(d_i-1)}(x_i) = Y_i^{(d_i-1)}(x_i) \end{cases}$

So, equivalence modulo the polynomial which have multiple roots is, essentially, still equivalent to equalities on values in the roots of this polynomial, but not only of $P(x)$, but also its derivatives up to the multiplicity of the root.

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