Решение задач на делимость многочленов. Применение алгоритма Горнера


Определим ключевые понятие для решения задач.

Определение 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). $

Алгоритм:

  1. Делим первый элемент делимого на старший элемент делителя, помещаем результат под чертой.
  2. Умножаем делитель на полученный выше результат деления. Записываем результат под первыми двумя элементами делимого.
  3. Вычитаем полученный после умножения многочлен из делимого, записываем результат под чертой.
  4. Если степень полученного многочлена в пункте 3 меньше степени делителя – завершаем процесс, в противном случае – перейти к пункту 5.
  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. Конспект по линейной алгебре и геометрии. 1 курс. Геннадий Сергеевич Белозеров. Глава 3.
  2. Сканави М. И. Элементарная математика. — 2-е изд., перераб. и доп. — М.: Наука, 1972. — 142—147 c.
  3. Волков Е. А. § 2. Вычисление значений многочлена. Схема Горнера — Учеб. пособие для вузов. — 2-е изд., испр. — М.: Наука, 1987. — 248 с.

Тест на тему: Решение задач на делимость многочленов. Применение алгоритма Горнера.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *