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

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$ в левой и правой части:

Rendered by QuickLaTeX.com

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

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

Rendered by QuickLaTeX.com

$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$ .

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

$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.$

Значит,

$a_0p^n+a_1p^{n-1}q+\ldots+a_{n-1}pq^{n-1}+a_nq^n=0.$

Так как все слагаемые, кроме последнего, делятся на $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} f(x)=(x-\alpha)g(x),\\ f(1)=1-15+69-72-108=-125,\\ f(1)=(1-\alpha)g(1),\\ f(1)\vdots(\alpha-1). \end{array}$

$2,-4,6$ .

Rendered by QuickLaTeX.com

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

Комментарии (RSS) | Трекбек

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

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

[...] является Уильям Джордж Горнер (1786 – 1837), известный по схеме Горнера. Опубликована теорема была в 1815 г. в Англии, в журнале [...]
19 Март 2011, 18:55
2 Еврейские задачи | Математика, которая мне нравится:

[...] которое не имеет рациональных корней. [...]
17 Октябрь 2012, 0:05
3 А.:

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

[Ответить]
Елизавета Александровна Калинина Reply:
Январь 8th, 2015 at 1:23
Ну знаете… Попробуйте здесь почитать: http://pmpu.ru/vf4/polynomial

[Ответить]
Аз есмь темь ясную Reply:
Ноябрь 28th, 2015 at 16:41
Ну знаете тут такое, я лично читаю сайт пм-пу, ничего особенного.

[Ответить]
Елизавета Александровна Калинина Reply:
Ноябрь 29th, 2015 at 12:22
Вам непонятно, или Вы о чем-то другом?

[Ответить]
7 Январь 2015, 23:30

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

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

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

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

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

3 А.:

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

Навигация по сайту

Разделы

Новые комментарии

Хороший книжный магазин

Подписка на обновления сайта

Твиттер