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

Сокращенную версию этого метода см. в разделе синтетическое деление .

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

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

А = BQ + Р ,

и либо R = 0, либо степень R ниже B. степени Эти условия однозначно определяют 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.$

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

1. Разделите первый член дивиденда на самый высокий член делителя (имеется в виду тот, у которого наибольшая степень 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}}$

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

   ${\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 х ² ) − ( х ³ − 3x ² ) = −2 х ² + 3x ² = х ² ). Затем «сбросьте» следующий член из дивиденда.

   ${\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. Повторите предыдущие три шага, но на этот раз используйте два только что записанных члена в качестве делимого.

   ${\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. На этот раз «валить» нечего.

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

короткое

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

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

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

Псевдокод

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

функция  n/d  есть 
      требуется d ≠ 0 
      д ← 0 
      r ← n // На каждом шаге n = d × q + r 

      в то время как  r ≠ 0  и  степень (r) ≥ степень (d)  делают 
          t ← lead(r) / lead(d) // Разделение главных членов 
          q ← q + т 
          г ← г - т × d 

      возврат  (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 называется евклидовым делением (иногда преобразованием деления ). Таким образом, полиномиальное деление в длину является алгоритмом евклидова деления.

Приложения

Факторизация полиномов

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

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

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

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

Полиномиальное деление в длину можно использовать для нахождения уравнения линии, касательной к графику функции , определяемой полиномом P ( x ) в конкретной точке x = r . Если 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 .

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

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

См. также

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