Hi everyone!
Today I'd like to write yet another blog about polynomials.
Lagrange interpolation
It's quite well-known that the system
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
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
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
can be represented as the sum
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
It is strikingly similar to the Lagrange interpolation expression, from which we may derive that
Thus, for monic square-free polynomial $$$Q(x)$$$ with $$$\deg P < \deg Q$$$ it holds that
Multiplicities
Let's now understand what's going on when $$$Q(x)$$$ have multiple roots. To do this, we utilize the Chinese remainder theorem again.
By CRT, this system has a unique solution modulo $$$Q(x)$$$. To find its explicit form, we should notice the Taylor expansion formula:
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:
Utilizing Chinese remainder theorem again, the solution to the whole system is given as
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
thus $$$C_i(x) = P(x) \cdot Q_i^{-1}(x) \bmod (x-x_i)^{d_i}$$$ and the final formula is as follows:
