Умножение и деление многочленов. Горнер

Краткий план ответа

При умножении каждый член первого многочлена умножаем на каждый член второго и приводим подобные. Для ненулевых многочленов $\deg(PQ)=\deg P+\deg Q$.

Теорема о делении с остатком: для $Q\ne0$ существуют единственные $S,R$, такие что $P=QS+R$, где $R=0$ либо $\deg R<\deg Q$.

Существование даёт деление уголком: последовательно убираем старший член остатка. Единственность: из двух представлений следует $Q(S_1-S_2)=R_2-R_1$; ненулевой левый многочлен имел бы степень не ниже $\deg Q$, правый — ниже, противоречие.

Схема Горнера для деления $P=a_0z^n+\cdots+a_n$ на $z-c$:

Частное имеет коэффициенты $b_0,\ldots,b_{n-1}$, остаток $b_n=P(c)$. В таблицу обязательно вписываем нулевые коэффициенты пропущенных степеней.

Пример: $P=z^3-3z+2$, $c=1$. Верхняя строка $1,0,-3,2$, нижняя $1,1,-2,0$. Значит, $P=(z-1)(z^2+z-2)$.

Подробный разбор

Формула умножения и степень

Если $P=\sum_{j=0}^m p_jz^j$ и $Q=\sum_{k=0}^n q_kz^k$, то коэффициент при $z^l$ в произведении равен $\sum_{j+k=l}p_jq_k$. Старший коэффициент $p_mq_n\ne0$, поэтому степень произведения равна $m+n$. Умножение коммутативно, ассоциативно и дистрибутивно — это следует из раскрытия конечных сумм.

Деление уголком подробно

Разделим $z^2+3z+5$ на $z+1$. Первый член частного $z^2/z=z$. Вычитая $z(z+1)$, получаем $2z+5$. Следующий член частного 2; вычитаем $2(z+1)$ и получаем остаток 3. Итак:

На каждом шаге степень остатка уменьшается, поэтому процесс заканчивается. Если степень делимого меньше степени делителя, частное 0, остаток — всё делимое. При постоянном ненулевом делителе остаток всегда 0.

Обоснование схемы Горнера

Сравним коэффициенты в $P(z)=(z-c)(b_0z^{n-1}+\cdots+b_{n-1})+R$. При старшей степени $b_0=a_0$; далее $b_k-cb_{k-1}=a_k$, а в свободном члене $R-cb_{n-1}=a_n$. Отсюда рекуррентные формулы схемы. Это одновременно деление и вычисление значения $P(c)$ без отдельных степеней.

Пример с пропущенной степенью

Для $P=z^4-6z^3-z+5$ и $c=2$ коэффициенты $1,-6,0,-1,5$. Нижняя строка Горнера: $1,-4,-8,-17,-29$. Частное $z^3-4z^2-8z-17$, остаток $-29$. Проверка $P(2)=16-48-2+5=-29$.

Проверка себя

Как выбрать c при делении на z+3?