Полиномиальное деление в столбик

Алгоритм деления многочленов

В алгебре , многочленное длинное деление — это алгоритм деления многочлена на другой многочлен той же или более низкой степени , обобщенная версия знакомого арифметического метода, называемого длинным делением . Его можно легко выполнить вручную, поскольку он разделяет сложную задачу деления на более мелкие. Иногда использование сокращенной версии, называемой синтетическим делением , быстрее, с меньшим количеством записей и вычислений. Другой сокращенный метод — многочленное короткое деление (метод Бломквиста).

Полиномиальное деление столбиком — это алгоритм, реализующий евклидово деление многочленов , который, начиная с двух многочленов A ( делимого ) и B ( делителя ), производит, если B не равно нулю, частное Q и остаток R, такие что

А = БК + Р ,

и либо R = 0, либо степень R ниже степени B. Эти условия однозначно определяют Q и R , что означает, что Q и R не зависят от метода, используемого для их вычисления.

Результат R = 0 возникает тогда и только тогда, когда многочлен A имеет B в качестве множителя . Таким образом, деление в столбик является средством проверки того, имеет ли один многочлен другой в качестве множителя, и, если это так, для разложения его на множители. Например, если известен корень r из A , его можно разложить на множители, разделив A на ( x  –  r ).

Пример

Полиномиальное деление в столбик

Найдите частное и остаток от деления делимого на делитель . ${\displaystyle (x^{3}-2x^{2}-4)}$ ${\displaystyle (x-3)}$

Сначала дивиденды переписываются следующим образом:

${\displaystyle x^{3}-2x^{2}+0x-4.}$

Частное и остаток можно определить следующим образом:

1. Разделите первый член делимого на наибольший член делителя (имеется в виду тот, который имеет наибольшую степень x , что в данном случае равно x ). Результат поместите над чертой ( x ³ ÷ x = x ² ).

   ${\displaystyle {\begin{array}{l}{\color {White}x-3\ )\ x^{3}-2}x^{2}\\x-3\ {\overline {)\ x^{3}-2x^{2}+0x-4}}\end{array}}}$

2. Умножьте делитель на только что полученный результат (первый член конечного частного). Запишите результат под первыми двумя членами делимого ( x ² · ( x − 3) = x ³ − 3 x ² ).

   ${\displaystyle {\begin{array}{l}{\color {White}x-3\ )\ x^{3}-2}x^{2}\\x-3\ {\overline {)\ x^{3}-2x^{2}+0x-4}}\\{\color {White}x-3\ )\ }x^{3}-3x^{2}\end{array}}}$

3. Вычтите только что полученный результат из соответствующих членов исходного делимого (помните, что вычитание чего-либо со знаком минус эквивалентно прибавлению чего-либо со знаком плюс) и запишите результат ниже: ( x ³ − 2 x ² ) − ( x ³ − 3 x ² ) = −2 x ² + 3 x ² = x ² Затем «вычтите» следующий член из делимого.

   ${\displaystyle {\begin{array}{l}{\color {White}x-3\ )\ x^{3}-2}x^{2}\\x-3\ {\overline {)\ x^{3}-2x^{2}+0x-4}}\\{\color {White}x-3\ )\ }{\underline {x^{3}-3x^{2}}}\\{\color {White}x-3\ )\ 0x^{3}}+{\color {White}}x^{2}+0x\end{array}}}$

4. Повторите предыдущие три шага, но на этот раз используйте два члена, которые только что были записаны, в качестве делимого.

   ${\displaystyle {\begin{array}{r}x^{2}+{\color {White}1}x{\color {White}{}+3}\\x-3\ {\overline {)\ x^{3}-2x^{2}+0x-4}}\\{\underline {x^{3}-3x^{2}{\color {White}{}+0x-4}}}\\+x^{2}+0x{\color {White}{}-4}\\{\underline {+x^{2}-3x{\color {White}{}-4}}}\\+3x-4\\\end{array}}}$

5. Повторите шаг 4. На этот раз «сносить» нечего.

   ${\displaystyle {\begin{array}{r}x^{2}+{\color {White}1}x+3\\x-3\ {\overline {)\ x^{3}-2x^{2}+0x-4}}\\{\underline {x^{3}-3x^{2}{\color {White}{}+0x-4}}}\\+x^{2}+0x{\color {White}{}-4}\\{\underline {+x^{2}-3x{\color {White}{}-4}}}\\+3x-4\\{\underline {+3x-9}}\\+5\end{array}}}$

Многочлен над чертой — это частное q ( x ), а число, оставшееся после деления (5), — это остаток r ( x ).

${\displaystyle {x^{3}-2x^{2}-4}=(x-3)\,\underbrace {(x^{2}+x+3)} _{q(x)}+\underbrace {5} _{r(x)}}$

Алгоритм деления столбиком для арифметики очень похож на приведенный выше алгоритм, в котором переменная x заменяется (в десятичной системе счисления) на конкретное число 10.

Полиномиальное короткое деление

Метод Бломквиста ^[1] — это сокращенная версия длинного деления, описанного выше. Этот метод с ручкой и бумагой использует тот же алгоритм, что и длинное полиномиальное деление, но для определения остатков используется умственный расчет . Это требует меньшего количества записей и, следовательно, может быть более быстрым методом после освоения.

Деление сначала записывается аналогично умножению в столбик, с делимым вверху и делителем внизу. Частное записывается под чертой слева направо.

${\displaystyle {\begin{matrix}\qquad \qquad x^{3}-2x^{2}+{0x}-4\\{\underline {\div \quad \qquad \qquad \qquad \qquad x-3}}\end{matrix}}}$

Разделите первый член делимого на наибольший член делителя ( x ³ ÷ x = x ² ). Поместите результат под чертой. x ³ был разделен без остатка, и поэтому может быть отмечен как использованный с помощью обратной косой черты. Затем результат x ² умножается на второй член в делителе −3 = −3 x ² . Определите частичный остаток, вычитая −2 x ² − (−3 x ² ) = x ² . Отметьте −2 x ² как использованный и поместите новый остаток x ² над ним.

${\displaystyle {\begin{matrix}\qquad x^{2}\\\qquad \quad {\bcancel {x^{3}}}+{\bcancel {-2x^{2}}}+{0x}-4\\{\underline {\div \qquad \qquad \qquad \qquad \qquad x-3}}\\x^{2}\qquad \qquad \end{matrix}}}$

Разделите наибольший член остатка на наибольший член делителя ( x ² ÷ x = x ). Поместите результат (+x) под чертой. x ² был разделен без остатка, и поэтому может быть отмечен как использованный. Затем результат x умножается на второй член в делителе −3 = −3 x . Определите частичный остаток, вычитая 0 x − (−3 x ) = 3 x . Отметьте 0 x как использованный и поместите новый остаток 3 x над ним.

${\displaystyle {\begin{matrix}\qquad \qquad \quad {\bcancel {x^{2}}}\quad 3x\\\qquad \quad {\bcancel {x^{3}}}+{\bcancel {-2x^{2}}}+{\bcancel {0x}}-4\\{\underline {\div \qquad \qquad \qquad \qquad \qquad x-3}}\\x^{2}+x\qquad \end{matrix}}}$

Разделите наибольший член остатка на наибольший член делителя (3x ÷ x = 3). Разместите результат (+3) под чертой. 3x было разделено без остатка, и поэтому может быть отмечено как использованное. Затем результат 3 умножается на второй член в делителе −3 = −9. Определите частичный остаток, вычитая −4 − (−9) = 5. Разместите −4 как использованное и разместите новый остаток 5 над ним.

${\displaystyle {\begin{matrix}\quad \qquad \qquad \qquad {\bcancel {x^{2}}}\quad {\bcancel {3x}}\quad 5\\\qquad \quad {\bcancel {x^{3}}}+{\bcancel {-2x^{2}}}+{\bcancel {0x}}{\bcancel {-4}}\\{\underline {\div \qquad \qquad \qquad \qquad \qquad x-3}}\\x^{2}+x+3\qquad \end{matrix}}}$

Многочлен под чертой — это частное q ( x ), а число, оставшееся после деления (5), — это остаток r ( x ).

Псевдокод

Алгоритм можно представить в псевдокоде следующим образом, где +, − и × представляют полиномиальную арифметику, а / представляет простое деление двух членов:

Функция n / d есть требуется d ≠ 0 д ← 0 r ← n // На каждом шаге n = d × q + r пока r ≠ 0 и degree(r) ≥ degree(d) делают t ← lead(r) / lead(d) // Разделить ведущие члены д ← д + т г ← г − т × д возврат (q, r)

Это работает одинаково хорошо, когда degree( n ) < degree( d ); в этом случае результатом будет просто тривиальное число (0, n ).

Этот алгоритм в точности описывает описанный выше метод бумаги и карандаша: d записывается слева от «)»; q записывается, член за членом, над горизонтальной линией, причем последний член является значением t ; область под горизонтальной линией используется для вычисления и записи последовательных значений r .

Евклидово деление

Для каждой пары многочленов ( A , B ) таких, что B ≠ 0, деление многочленов дает частное Q и остаток R, такие что

${\displaystyle A=BQ+R,}$

и либо R = 0, либо degree( R ) < degree( B ). Более того, ( Q , R ) — единственная пара многочленов, обладающая этим свойством.

Процесс получения однозначно определенных многочленов Q и R из A и B называется евклидовым делением (иногда преобразованием деления ). Таким образом, длинное деление многочленов является алгоритмом для евклидова деления. ^[2]

Приложения

Факторизация многочленов

Иногда известны один или несколько корней многочлена, возможно, найденных с помощью теоремы о рациональных корнях . Если известен один корень r многочлена P ( x ) степени n , то можно использовать деление многочлена в столбик для разложения P ( x ) в форму ( x − r ) Q ( x ) , где Q ( x ) — многочлен степени n − 1. Q ( x ) — это просто частное, полученное в результате деления; поскольку известно, что r является корнем P ( x ), известно, что остаток должен быть равен нулю.

Аналогично, если известны несколько корней r , s , . . . уравнения P ( x ), линейный множитель ( x − r ) можно разделить, чтобы получить Q ( x ), а затем ( x − s ) можно разделить из Q ( x ) и т. д. В качестве альтернативы квадратичный множитель можно разделить из P ( x ), чтобы получить частное степени n − 2. ${\displaystyle (x-r)(x-s)=x^{2}-(r{+}s)x+rs}$

Этот метод особенно полезен для кубических полиномов, и иногда можно получить все корни полинома более высокой степени. Например, если теорема о рациональных корнях дает один (рациональный) корень полинома пятой степени , его можно разложить на множители, чтобы получить частное четвертой степени; явная формула для корней полинома четвертой степени может затем использоваться для нахождения остальных четырех корней полинома пятой степени. Однако общего способа решения квинтики чисто алгебраическими методами не существует, см. теорему Абеля–Руффини .

Нахождение касательных к полиномиальным функциям

Деление полиномов в столбик можно использовать для нахождения уравнения линии, касательной к графику функции, определяемой полиномом P ( x ) в конкретной точке x = r . ^[3] Если R ( x ) является остатком от деления P ( x ) на ( x – r ) ² , то уравнение касательной в точке x = r к графику функции y = P ( x ) равно y = R ( x ), независимо от того, является ли r корнем полинома.

Пример

Найдите уравнение линии, касательной к следующей кривой: ${\displaystyle y=(x^{3}-12x^{2}-42)}$

в: ${\displaystyle x=1}$

Начнем с деления многочлена на: ${\displaystyle (x-1)^{2}=(x^{2}-2x+1)}$

${\displaystyle {\begin{array}{r}x-10\\x^{2}-2x+1\ {\overline {)\ x^{3}-12x^{2}+0x-42}}\\{\underline {x^{3}-{\color {White}0}2x^{2}+{\color {White}1}x}}{\color {White}{}-42}\\-10x^{2}-{\color {White}01}x-42\\{\underline {-10x^{2}+20x-10}}\\-21x-32\end{array}}}$

Касательная линия - это ${\displaystyle y=(-21x-32)}$

Циклическая проверка избыточности

Циклическая проверка избыточности использует остаток от деления полинома для обнаружения ошибок в передаваемых сообщениях.

Смотрите также

• Теорема о полиномиальном остатке
• Синтетическое деление , более краткий метод выполнения деления евклидовых многочленов.
• Правило Руффини
• Евклидова область
• основа Грёбнера
• Наибольший общий делитель двух многочленов

Ссылки

1. Архивировано в Ghostarchive и Wayback Machine: Деление Бломквиста: простейший метод решения делений? , получено 10.12.2019
2. S. Barnard (2008). Высшая алгебра . ЧИТАЙТЕ КНИГИ. стр. 24. ISBN 978-1-4437-3086-0.
3. Стрикленд-Констебль, Чарльз, «Простой метод нахождения касательных к полиномиальным графикам», Mathematical Gazette 89, ноябрь 2005 г.: 466-467.