Метод неопределенных коэффициентов

Рассмотрим два многочлена $P_n(x),\ Q_m(x)$ степени

соответственно, т.е.

$\displaystyle P_n(x)=a_nx^n+a_{n-1}x^{n-1}+\ldots+a_0,$

$\displaystyle Q_m(x)=b_mx^m+b_{m-1}x^{m-1}+\ldots+b_0,$

предположим, что $n\geq m$ .

При делении многочлена на многочлен , где $n\geq m$ , нужно найти многочлены $R_{n-m}(x)$ и $r_{m-1}(x)$ такие, чтобы выполнялось равенство

$\displaystyle R_{n-m}(x)Q_m(x)+r_{m-1}(x)=P_n(x).$

Опишем метод неопределенных коэффициентов. Этот метод основывается на том, что многочлен -ой степени имеет ровно корней с учетом их кратности. Это означает, что если многочлен обращается в нуль более чем в точках, то этот многочлен нулевой (все коэффициенты равны нулю).

Запишем многочлены $R_{n-m}(x)$ и $r_{m-1}(x)$ с произвольными коэффициентами, т.е.

$\displaystyle R_{n-m}(x)=c_{n-m}x^{n-m}+c_{n-m-1}x^{n-m-1}+\ldots + c_0$

$\displaystyle r_{m-1}(x)=d_{m-2}x^{m-2}+d_{m-3}x^{m-3}+\ldots + d_0.$

Умножим и сложим многочлены в левой части равенства:

$\displaystyle R_{n-m}(x)Q_m(x)+r_{m-1}(x)=P_n(x),$

получим

$\displaystyle (c_{n-m}x^{n-m}+c_{n-m-1}x^{n-m-1}+ \ldots +c_0) (b_mx^m+b_{m-1}x^{m-1}+\ldots+b_0)+$

$\displaystyle + d_{m-2}x^{m-2}+d_{m-3}x^{m-3}+\ldots+d_0=$

$\displaystyle = c_{n-m}b_mx^n+c_{n-m}b_{m-1}x^{n-1}+\ldots+c_0b_0+d_0=$

$\displaystyle = A_nx^n+A_{n-1}x^{n-1}+\ldots+A_0.$

здесь приведены подобные, т.е. группировка по степеням

В итоге получим, что для любого значения переменной выполняется равенство левой и правой частей. Это означает, что многочлен -ой степени обращается в нуль более, чем в точках. Для равенства нулю многочлена достаточно потребовать равенства нулю всех его коэффициентов.

Приравняем друг к другу коэффициенты при одинаковых степенях в равенстве

$\displaystyle c_{n-m}b_mx^n+c_{n-m}b_{m-1}x^{n-1}+\ldots+c_0b_0+d_0= a_nx^n+a_{n-1}x^{n-1}+\ldots+a_0$

или

$\displaystyle A_nx^n+A_{n-1}x^{n-1}+\ldots+A_0= a_nx^n+a_{n-1}x^{n-1}+\ldots+a_0.$

Имеем систему линейных алгебраических уравнений:

$\displaystyle x^n:\quad A_n=c_{n-m}b_m=a_n;$

$\displaystyle x^{n-1}:\quad A_{n-1}=a_{n-1};$

$\displaystyle \dots$

$\displaystyle x^0:\quad A_0=c_0b_0+d_0=a_0;$

из которой определяются неизвестные коэффициенты.