Определим ключевые понятие для решения задач.
Определение 1
$ f(x), g(x) \in \mathbb{P} { [ x ] },\quad g(x) \neq 0 $. $ f(x)$ делится на $ g(x)$
$\Big( f(x)$ $\vdots$ $ g(x)\Big)$ , если $f$ представимо в следующем виде: $$ f(x)=g(x) \cdot h(x),\quad где \quad h(x) \in \mathbb{P} [x].$$
Определение 2
Пусть $ f(x), g(x),h(x) \in \mathbb{P} { [ x ] }$, если $h(x)$ $|$ $f(x)$ и $h(x)$ $ |$ $g(x)$, то $h(x)$ называется общим делителем $ f(x)$, $g(x)$.
Алгоритм Горнера
Алгоритм вычисления значения многочлена, записанного в виде суммы мономов, при заданном значении переменной.
$f(x)=a_{n}x^n+a_{n-1}x^{n-1}+\dots+a_1x+a_0$
$q(x)=b_{n-1}x^{n-1}+b_{n-2}x^{n-2}+\dots+b_1x+b_0$
$f(x)=(x-\alpha)q(x)+f(\alpha)$
Умножаем $q(x)$ на $x-\alpha$ и приравниваем:
| $\large f(x)=(x-\alpha)q(x)+f(\alpha)$ | ||
| $\large n$ | $\large a_n=b_{n-1}$ | $\large b_{n-1}=a_n$ |
| $\large n-1$ | $\large a_{n-1}=b_{n-2}-\alpha b_{n-1}$ | $\large b_{n-2}=a_{n-1}+\alpha b_{n-1}$ |
| $\large n-2$ | $\large a_{n-2}=b_{n-3}-\alpha b_{n-2}$ | $\large b_{n-3}=a_{n-2}+\alpha b_{n_2} $ |
| $\large \vdots$ | $\large \dots$ | $\large \dots$ |
| $\large 1$ | $\large a_1=b_0-\alpha b_1$ | $\large b_0=a_1+\alpha b_1$ |
| $\large 0$ | $\large a_0=f(\alpha)-\alpha b_0 $ | $\large f(\alpha)=a_0+\alpha b_0 $ |
Схема Горнера
| $\large a_n$ | $\large a_{n-1}$ | $\large a_{n-2}$ | $\large \dots$ | $\large a_1$ | $\large a_0$ | |
| $\large \alpha$ | $\large b_{n-1}$ | $\large b_{n-2}$ | $\large b_{n-3}$ | $\large \dots$ | $\large b_0$ | $\large f(\alpha)$ |
Комбинируя алгоритм Горнера и занося результаты в схему Горнера получаем простой алгоритм нахождения остатка и частного, при делении на заданный линейный двухчлен.
Задача 1
Указать делит ли многочлен $g(x)$ многочлен $f(x). $
Алгоритм:
- Делим первый элемент делимого на старший элемент делителя, помещаем результат под чертой.
- Умножаем делитель на полученный выше результат деления. Записываем результат под первыми двумя элементами делимого.
- Вычитаем полученный после умножения многочлен из делимого, записываем результат под чертой.
- Если степень полученного многочлена в пункте 3 меньше степени делителя – завершаем процесс, в противном случае – перейти к пункту 5.
- Повторяем предыдущие 4 шага, используя в качестве делимого многочлен, записанный под чертой.
- $$ \large f(x)=x^3-12x^2-42 \quad g(x)=x-3$$
$\large x^3$ $\large — $ $\large 12x^2$ $\large +$ $\large 0x$ $\large -$ $\large 42$ $\large x$ $\large -$ $\large 3$ $\large $ $\large $ $\large x^3$ $\Large -$ $\large 3x^2$ $\large $ $\large $ $\large $ $\large $ $\large x^2$ $\large -$ $\large 9x$ $\large -$ $\large 27$ $\large $ $\large -$ $\large 9x^2$ $\large +$ $\large 0x$ $\large -$ $\large 42$ $\large $ $\large $ $\large $ $\large $ $\large $ $\large $ $\large -$ $\large 9x^2$ $\large +$ $\large 27x$ $\large $ $\large $ $\large $ $\large $ $\large $ $\large $ $\large $ $\large $ $\large $ $\large $ $\large -$ $\large 27x$ $\large -$ $\large 42$ $\large $ $\large $ $\large $ $\large $ $\large $ $\large $ $\large $ $\large $ $\large -$ $\large 27x$ $\large +$ $\large 81$ $\large $ $\large $ $\large $ $\large $ $\large $ $\large $ $\large $ $\large $ $\large $ $\large $ $\large -$ $\large 123$ $\large $ $\large $ $\large $ $\large $ $\large $ Ответ: $r(x)=-123 \Rightarrow g(x)$ не делит $f(x)$.
- $$\large f(x)=x^2+3x+2 \quad g(x)=x+2 $$
$\large x^2$ $\large +$ $\large 3x$ $\large +$ $\large 2$ $\large x$ $\large +$ $\large2$ $\large x^2$ $\large +$ $\large x$ $\large x$ $\large +$ $\large 1$ $\large 2x$ $\large +$ $\large 2$ $\large 2x$ $\large +$ $\large 2$ $\Large 0$ Ответ: $r(x)=0 \Rightarrow g(x) $ делит $f(x)$.
Задача 2
Найти частное и остаток от деления на линейный двучлен используя метод Горнера.
$$\large f(x)=2x^4-3x^3-x^2+4x+13$$ $$\large Линейный \quad двучлен:\quad x-1$$
Применим предложенный выше алгоритм:
| $\large a_4=2$ | $\large a_3=-3$ | $\large a_2=-1$ | $\large a_1=4$ | $\large a_0=13$ | |
| $\large \alpha=1$ | $\large b_3=a_4$ $b_3=2$ |
$\large b_2=a_3+\alpha b_3$ $b_2=-1$ |
$\large b_1=a_2+\alpha b_2$ $b_1=-2$ |
$\large b_0=a_1+\alpha b_1$ $b_0=2$ |
$\large f(\alpha)=15$ |
Ответ: $ q(x)=2x^3-x^2-2x+2, \quad f(\alpha)=15$.
Список литературы:
- Конспект по линейной алгебре и геометрии. 1 курс. Геннадий Сергеевич Белозеров. Глава 3.
- Сканави М. И. Элементарная математика. — 2-е изд., перераб. и доп. — М.: Наука, 1972. — 142—147 c.
- Волков Е. А. § 2. Вычисление значений многочлена. Схема Горнера — Учеб. пособие для вузов. — 2-е изд., испр. — М.: Наука, 1987. — 248 с.
Тест на тему: Решение задач на делимость многочленов. Применение алгоритма Горнера.
