Lagrange interpolation and partial fraction decomposition

Правка en2, от 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)$$$.

Теги polynomial interpolation, lagrange-interpolation, chinese remainder theo., crt, polynomials, partial fraction

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
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
en9 Английский adamant 2021-12-27 23:59:16 44
en8 Английский adamant 2021-12-27 23:57:40 7
en7 Английский adamant 2021-12-27 23:55:41 234
en6 Английский adamant 2021-12-27 23:52:54 1150 (published)
en5 Английский adamant 2021-12-27 19:00:47 541
en4 Английский adamant 2021-12-27 17:05:24 2
en3 Английский adamant 2021-12-27 17:04:17 2638
en2 Английский adamant 2021-12-27 14:45:47 555
en1 Английский adamant 2021-12-27 02:35:01 477 Initial revision (saved to drafts)