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

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

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

над полем или кольцом mathbb{K} (с коэффициентами из этого поля или кольца). Дано число alphain 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 — многочлен с целыми коэффициентами, alphainmathbb{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_2inmathbb{K}[x] (из кольца полиномов над полем mathbb{K}). Выберем в этом множестве отличный от нуля полином d(x) наименьшей степени. Докажем, что d=Н.О.Д.(f_1,f_2).

Пусть d=f_1M_1+f_2M_2. Докажем, что f_kvdots d. Пусть f_1notvdots 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,rin D. Противоречие. Значит, f_1,f_2vdots d.

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

    [d=f_1M_1+f_2M_2.]

Пусть delta — общий делитель f_1,f_2. f_1vdotsdelta,f_2vdotsdelta. Значит, f_1M_1,f_2,M_2vdotsdeltaLongrightarrow dvdotsdelta. Поскольку {rm deg}, dge{rm deg},delta, то d — наибольший общий делитель.

Пусть {rm deg}, d,{rm deg}, d' — максимальны. Тогда {rm deg}, d={rm deg}, d',dvdots 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_iinmathbb{Z},i=overline{0,n}.]

Пусть p и q — взаимно простые целые числа, не равные нулю. Предположим, что fleft({pover q}right)=0. Тогда a_nvdots p,a_0vdots q.

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

    [fleft({pover q}right)=0Longrightarrow a_0{p^nover 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 и 0vdots p, то a_nq^nvdots p. Так как p и q взаимно просты, то a_nvdots p.

Аналогично a_0vdots 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).]

Ссылка на основную публикацию