3. Схема Горнера. Наибольший общий делитель. Разложение на множители. Многочлены с целыми коэффициентами

Схема Горнера предназначена для вычисления значения полинома в точке. Пусть дан полином

f(x)=a_0x^n+a_1x^{n-1}+\ldots+a_n

над полем или кольцом \mathbb{K} (с коэффициентами из этого поля или кольца). Дано число \alpha\in \mathbb{K}. Требуется найти f(\alpha). Разделим f(x) на x-\alpha с остатком:

a_0x^n+a_1x^{n-1}+\ldots+a_{n-1}x+a_n=(x-\alpha)(b_0x^{n-1}+b_1x^{n-2}+\ldots+b_{n-1})+f(\alpha).

Приравняем коэффициенты при одинаковых степенях x в левой и правой части:

\begin{tabular}{l|l}<br />
$a_0=b_0$&$b_0=a_0$\\<br />
$a_1=b_1-\alpha b_0$&$b_1=\alpha b_0+a_1$\\<br />
$a_2=b_2-\alpha b_1$&$b_2=\alpha b_1+a_2$\\<br />
$\ldots$&$\ldots$\\<br />
$a_{n-1}=b_{n-1}-\alpha b_{n-2}$&$b_{n-1}=\alpha b_{n-2}+a_{n-1}$\\<br />
$a_n=f(\alpha)-\alpha b_{n-1}$&$f(\alpha)=\alpha b_{n-1}+a_n$.<br />
\end{tabular}

Это можно записать в виде таблицы:

\begin{tabular}{|c|c|c|c|c|c|}<br />
\hline<br />
&$a_0$&$a_1$&$a_2$&$\ldots$&$a_n$\\<br />
\hline<br />
$\alpha$&$b_0$&$b_1$&$b_2$&$\ldots$&$b_n$\\<br />
\hline<br />
\end{tabular}

Пример. f(x)=3x^5-2x^4+7x^2+3x-4,f(3)-?

\begin{tabular}{|c|c|c|c|c|c|c|}<br />
\hline<br />
&3&-2&0&7&3&-4\\<br />
\hline<br />
3&3&7&21&70&213&635\\<br />
\hline<br />
-2&3&-8&16&-25&53&-110\\<br />
\hline<br />
\end{tabular}

f(x)=(x+2)(3x^4-8x^3+16x^2-25x+53)-110.

Примечание. Схема Горнера показывает, что если f — многочлен с целыми коэффициентами, \alpha\in\mathbb{Z}, то при делении f(x) на x-\alpha получается целое число — остаток, и неполное частное имеет целые коэффициенты.

Наибольший общий делитель полиномов

Определение. Наибольшим общим делителем полиномов f_1,f_2 над полем \mathbb{K} называется полином наибольшей степени среди полиномов над \mathbb{K}, делящих оба полинома f_1,f_2.

Теорема. Н.О.Д.(f_1,f_2) единствен с точностью до константы и делится на любой общий делитель этих полиномов. Н.О.Д.(f_1,f_2)=d(x) допускает линейное представление в виде d(x)=f_1(x)M_1(x)+f_2(x)M_2(x), где M_1,M_2 — некоторые полиномы из \mathbb{K}[x].

Доказательство. Рассмотрим множество полиномов D=\{ f_1N_1+ f_2N_2|N_1, N_2\in\mathbb{K}[x] (из кольца полиномов над полем \mathbb{K}). Выберем в этом множестве отличный от нуля полином d(x) наименьшей степени. Докажем, что d=Н.О.Д.(f_1,f_2).

Пусть d=f_1M_1+f_2M_2. Докажем, что f_k\vdots d. Пусть f_1\not\vdots d.

f_1=qd+r,{\rm deg}\, r<{\rm deg}\, d.

Тогда r=f_1-qd=f_1-q(f_1M_1+f_2M_2). Получили, что {\rm deg}\, r<{\rm deg}\, D,r\in D. Противоречие. Значит, f_1,f_2\vdots d.

Докажем, что каждый общий делитель — делитель d.

d=f_1M_1+f_2M_2.

Пусть \delta — общий делитель f_1,f_2$.  $f_1\vdots\delta,f_2\vdots\delta. Значит, f_1M_1,f_2,M_2\vdots\delta\Longrightarrow d\vdots\delta. Поскольку {\rm deg}\, d\ge{\rm deg}\,\delta, то d — наибольший общий делитель.

Пусть {\rm deg}\, d,{\rm deg}\, d’ — максимальны. Тогда {\rm deg}\, d={\rm deg}\, d’,d\vdots d’,d’\vdots d. Следовательно, они равны с точностью до константы.

Для нахождения Н.О.Д. полиномов можно использовать алгоритм Евклида нахождения Н.О.Д.

Разложение многочлена на множители

Определение. полином f над полем \mathbb{K}, отличный от константы, называется неприводимым над полем \mathbb{K}, если его нельзя представить в виде произведения двух многочленов меньшей степени с коэффициентами из поля \mathbb{K}. Полином, отличный от константы и не являющийся неприводимым, называется приводимым.

Примеры неприводимых многочленов:

многочлены первой степени;

x^2-2 — неприводимый над \mathbb{Q}, приводимый над \mathbb{R}.

Теорема. f(x) делится на x-a тогда и только тогда, когда f(a)=0.

Доказательство. См. теорему Безу.

Теорема. Любой приводимый полином со старшим коэффициентом, равным 1, единственным образом представляется в виде произведения неприводимых полиномов со старшими коэффициентами, равными 1 (с точностью до порядка сомножителей).

Многочлены над полем \mathbb{Q}

Теорема. Пусть f — полином с целыми коэффициентами.

a_0x^n+a_1x^{n-1}+\ldots+a_n,\quad a_i\in\mathbb{Z},i=\overline{0,n}.

Пусть p и q — взаимно простые целые числа, не равные нулю. Предположим, что f\left({p\over q}\right)=0. Тогда a_n\vdots p,a_0\vdots q.

Доказательство.

\displaystyle f\left({p\over q}\right)=0\Longrightarrow a_0{p^n\over q^n}+a_1{p^{n-1}\over q^{n-1}}+\ldots+a_n=0.

Значит,

<br />
a_0p^n+a_1p^{n-1}q+\ldots+a_{n-1}pq^{n-1}+a_nq^n=0.<br />

Так как все слагаемые, кроме последнего, делятся на p и 0\vdots p, то a_nq^n\vdots p. Так как p и q взаимно просты, то a_n\vdots p.

Аналогично a_0\vdots q.

Задача. Разложить на множители многочлен над полем \mathbb{Q}

f(x)=x^4-15x^3+69x^2-72x-108.

Решение. Возможные целые корни — делители 108: \pm1, \pm2, \pm3, \pm4, \pm6, \pm9, \pm12, \pm27, \pm36, \pm54, \pm108.

Пусть \alpha — целый корень, f(\alpha)=0.

\begin{array}{l}<br />
f(x)=(x-\alpha)g(x),\\<br />
f(1)=1-15+69-72-108=-125,\\<br />
f(1)=(1-\alpha)g(1),\\<br />
f(1)\vdots(\alpha-1).<br />
\end{array}
2,-4,6.

\begin{tabular}{|c|c|c|c|c|c|}<br />
\hline<br />
&1&-15&69&-72&-108\\<br />
\hline<br />
2&1&-13&43&14&-80\\<br />
\hline<br />
-4&1&-19&119&590&$\ne0$\\<br />
\hline<br />
6&1&-9&15&18&0\\<br />
\hline<br />
6&1&-3&-3&0&\\<br />
\hline<br />
\end{tabular}

f(x)=(x-6)^2(x^2-3x-3).

Комментариев: 6

  1. 1 Одна красивая теорема из планиметрии | Математика, которая мне нравится:

    [...] является Уильям Джордж Горнер (1786 – 1837), известный по схеме Горнера. Опубликована теорема была в 1815 г. в Англии, в журнале [...]

  2. 2 Еврейские задачи | Математика, которая мне нравится:

    [...] которое не имеет рациональных корней. [...]

  3. 3 А.:

    Ничего не понятно. Нельзя было попроще как-то?

    [Ответить]

    Елизавета Александровна Калинина Reply:

    Ну знаете… Попробуйте здесь почитать: http://pmpu.ru/vf4/polynomial

    [Ответить]

    Аз есмь темь ясную Reply:

    Ну знаете тут такое, я лично читаю сайт пм-пу, ничего особенного.

    [Ответить]

    Елизавета Александровна Калинина Reply:

    Вам непонятно, или Вы о чем-то другом? :-)

    [Ответить]

Оставьте свой отзыв

Добавить изображение