Lagrange interpolation and partial fraction decomposition

Revision en3, by adamant, 2021-12-27 17:04:17

Hi everyone!

Today I'd like to write yet another blog about polynomials.

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


Let's now understand what's going on when $$$Q(x)$$$ have multiple roots. To do this, we utilize the Chinese remainder theorem again.

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

By CRT, this system has a unique solution modulo $$$Q(x)$$$. To find its explicit form, we should notice the Taylor expansion formula:

$$$P(x) = P(x_i) + P'(x_i) \cdot (x-x_i) + P' '(x_i) \cdot \frac{(x-x_i)^2}{2} + \dots + P^{(n)}(x_i) \cdot \frac{(x-x_i)^n}{n!},$$$

where $$$P^{(k)}(x)$$$ is the $$$k$$$-th derivative of $$$P(x)$$$. Thus, $$$P(x) \equiv Y_i(x) \pmod{(x-x_i)^{d_i}}$$$ is equivalient to the following system:

$$$\begin{align}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{align}$$$

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^{-1}(x) \bmod (x-x_i)^{d_i}}{(x-x_i)^{d_i}}$$$
Tags polynomial interpolation, lagrange-interpolation, chinese remainder theo., crt, polynomials, partial fraction


  Rev. Lang. By When Δ Comment
en11 English adamant 2021-12-28 14:17:03 1113 extra about switching from x^k to (x+a)^k
en10 English adamant 2021-12-28 00:19:18 13 cut
en9 English adamant 2021-12-27 23:59:16 44
en8 English adamant 2021-12-27 23:57:40 7
en7 English adamant 2021-12-27 23:55:41 234
en6 English adamant 2021-12-27 23:52:54 1150 (published)
en5 English adamant 2021-12-27 19:00:47 541
en4 English adamant 2021-12-27 17:05:24 2
en3 English adamant 2021-12-27 17:04:17 2638
en2 English adamant 2021-12-27 14:45:47 555
en1 English adamant 2021-12-27 02:35:01 477 Initial revision (saved to drafts)