Loading [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js

Lagrange interpolation and partial fraction decomposition

Revision en9, by adamant, 2021-12-27 23:59:16

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

{P(x0)=y0,P(x1)=y1,P(xn)=yn

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.

Tags polynomial interpolation, lagrange-interpolation, chinese remainder theo., crt, polynomials, partial fraction

History

 
 
 
 
Revisions
 
 
  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)