Полиномиальное длинное деление

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

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

А = BQ + Р ,

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

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

Пример

Полиномиальное длинное деление

Найдите частное и остаток от деления $x^{3}-2x^{2}-4,$ дивиденд по , $x-3,$ делитель .

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

x^{3}-2x^{2}+0x-4.

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

Разделите первый член дивиденда на самый высокий член делителя (имеется в виду тот, у которого наибольшая степень x , которая в данном случае равна x ). Поместите результат над полосой ( x ³ ÷ х = х ²).
${\begin{array}{l}{\color {White}x-3\ )\ x^{3}-2}x^{2}\\x-3\ {\overline {)\ x^{3}-2x^{2}+0x-4}}\end{array}}$
Умножьте делитель на только что полученный результат (первый член конечного частного). Запишите результат под первыми двумя членами делимого ( $x 2 \cdot (х - 3) = х 3 - 3x 2$ ).
${\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}}$
Вычтите только что полученное произведение из соответствующих членов исходного дивиденда (следя за тем, чтобы вычитание чего-либо, имеющего знак минус, эквивалентно добавлению чего-либо, имеющего знак плюс), и запишите результат внизу ( $(x 3 - 2 х 2) - (х 3 - 3x 2) = -2 х 2 + 3x 2 = х 2$ ). Затем «сбросьте» следующий член из дивиденда.
${\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}}$
Повторите предыдущие три шага, но на этот раз используйте два только что записанных члена в качестве делимого.
${\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}}$
Повторите шаг 4. На этот раз «валить» нечего.
${\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 ).

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

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

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

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

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

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

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

{\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 затем умножается на второй член делителя −3 = −3 x . Определите частичный остаток, вычитая 0 x − (−3 x ) = 3 x . Отметьте 0 x как использованное и поместите новый остаток 3 x над ним.

{\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 над ним.

{\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 ).

Псевдокод

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

function n / d is
    require d ≠ 0
    q ← 0
    r ← n             // At each step n = d × q + r

    while r ≠ 0 and degree(r) ≥ degree(d) do
        t ← lead(r) / lead(d)       // Divide the leading terms
        q ← q + t
        r ← r − t × d

    return (q, r)

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

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

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

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

A=BQ+R,

и либо R =0, либо степень( R ) < степень( 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 ) и т. д. В качестве альтернативы, квадратичный коэффициент фактор $(x-r)(x-s)=x^{2}-(r{+}s)x+rs$ можно разделить на P ( x ), чтобы получить частное степени n - 2.

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

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

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

Пример

Найдите уравнение линии, касающейся следующей кривой в точке x = 1 :

y=x^{3}-12x^{2}-42.

Начните с деления многочлена на ( x − 1). ² = х ² − 2 х + 1 :

{\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}}

Касательная линия: y = −21 x − 32 .

Проверка циклическим избыточностью

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

См. также

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

Ссылки

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

[1] Архивировано в Ghostarchive и Wayback Machine : Деление Бломквиста: самый простой метод решения делений? , получено 10 декабря 2019 г.

[2] С. Барнард (2008). Высшая алгебра . ЧИТАЙТЕ КНИГИ. п. 24. ISBN 978-1-4437-3086-0 .

[3] Стрикленд-Констебль, Чарльз, «Простой метод поиска касательных к полиномиальным графикам», Mathematical Gazette 89, ноябрь 2005 г.: 466-467.

[1]

[2]

[3]

v т и Полиномы и полиномиальные функции
По степени	Нулевой полином (степень неопределена или −1 или −∞) Постоянная функция (0) Линейная функция (1) Линейное уравнение Квадратичная функция (2) Квадратное уравнение Кубическая функция (3) Кубическое уравнение Функция четвертой степени (4) Уравнение четвертой степени Квинтическая функция (5) Секстическое уравнение (6) Септическое уравнение (7)
По свойствам	Одномерный Двумерный Многомерный моном Биномиальный Трехчленный Нередуцируемый без квадратов Однородный Квазиоднородный
Инструменты и алгоритмы	Факторизация Наибольший общий делитель Разделение Метод оценки Горнера Проверка полиномиальной идентичности Результирующий Дискриминант База Грёбнер