Комбинаторные алгоритмы для программистов



     юридическая консультация бесплатно по кредитам. |         

Деление многочленов


Если заданы два многочлена

f(x)
и
\varphi (x)
, то всегда существуют многочлены
q(x)
(частное) и
r(x)
(остаток), такие, что
f(x) = \varphi (x)q(x) + r(x)
, причем степень
r(x)
меньше степени
\varphi (x)
или
r(x) = 0
. При этом
f(x)
называется делимым, а
\varphi (x)
- делителем. Если же мы хотим, чтобы деление выполнялось без остатка, то придется допустить в качестве частного не только многочлены, но и бесконечные степенные ряды. Для получения частного надо расположить многочлены по возрастающим степеням
x
и делить "углом", начиная с младших членов. Рассмотрим, например, деление
1
на
1 - x

 \arraycolsep=0pt \begin{array}{rrrrl} 1 &&&&\multicolumn{1}{|l}{1-x}\\ \cline{5-5} \mp1&{}\pm x &&& \multicolumn{1}{|l}{1+x+x^2+\ldots}\\ \cline{1-4} & x \\ &{}\mp x &\pm x^2\\ \cline{2-3} && x^2\\ && \mp x^2&\pm x^3\\ \cline{3-4} &&& x^3\hbox to 0pt{\ldots\hss} \end{array}

Ясно, что процесс деления никогда не закончится ( так же, например, как при обращении числа

\frac{1}{3}
в бесконечную десятичную дробь). С помощью индукции легко убедиться, что все коэффициенты частного равны единице. Поэтому в качестве частного получается бесконечный ряд
1 + x + x^2 + \ldots + x^n + \ldots
. Вообще, если
f(x)
и
\varphi (x)
- два многочлена

f(x) = a_0 + \ldots + a_n x^n,

\varphi (x) = b_0 + \ldots + b_m x^m,

причем свободный член

b_0
многочлена
\varphi (x)

отличен от нуля,

b_0^{} \ne 0
, то при делении
f(x)

на

\varphi (x)
получается бесконечный ряд

c_0+c_1x+\ldots+c_kx^k+\ldots

(9.1)

Лишь в случае, когда

f(x)
делится без остатка на
\varphi (x)
, ряд (9.1) обрывается и мы получаем многочлен.




Содержание  Назад  Вперед