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

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

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).\]

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

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

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

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

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

  3. 3 А.:

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

    [Ответить]

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

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

    [Ответить]

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

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

    [Ответить]

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

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

    [Ответить]

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

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