Математика, которая мне нравится

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

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

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

\begin{tabular}{l|l}
&\\
&\\
&\\
&\\
&\\
&.
\end{tabular}

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

\begin{tabular}{|c|c|c|c|c|c|}
\hline
&&&&&\\
\hline
&&&&&\\
\hline
\end{tabular}

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

\begin{tabular}{|c|c|c|c|c|c|c|}
\hline
&3&-2&0&7&3&-4\\
\hline
3&3&7&21&70&213&635\\
\hline
-2&3&-8&16&-25&53&-110\\
\hline
\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.

Тогда 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.

Пусть \delta — общий делитель f_1,f_2f_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 — полином с целыми коэффициентами.

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

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

Значит,

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

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

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

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

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

2,-4,6.

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