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

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

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

А = BQ + р,

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

Результат р = 0 встречается если и только если многочлен А имеет B как фактор. Таким образом, деление в столбик - это средство проверки того, есть ли у одного многочлена другой фактор, и, если он есть, для его разложения. Например, если корень р из А известно, его можно вычленить, разделив А к (Икс–р).

Пример

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

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

Дивиденд сначала переписывается так:

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

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

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

${ displaystyle {x ^ {3} -2x ^ {2} -4} = (x-3) , underbrace {(x ^ {2} + x + 3)} _ {q (x)} + подвязка {5} _ {r (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}}}$

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

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

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

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

Разделите самый высокий член остатка на самый высокий член делителя (3x ÷ Икс = 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 {-2}} x ^ {2} + { bcancel {0x}} { bcancel {-4}} { underline { div qquad qquad qquad qquad qquad x-3}} x ^ {2} + x + 3 qquad end {matrix}}}$

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

Псевдокод

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

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

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

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

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

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

${ displaystyle A = BQ + R,}$

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

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

Приложения

Факторинг полиномов

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

Аналогично, если известно более одного корня, линейный коэффициент (Икс − р) в одном из них (р) можно разделить, чтобы получить Q(Икс), а затем линейный член в другом корне, s, можно выделить из Q(Икс) и т. д. В качестве альтернативы все они могут быть разделены сразу: например, линейные коэффициенты Икс − р и Икс − s можно перемножить, чтобы получить квадратичный множитель Икс² − (р + s)Икс + RS, который затем можно разделить на исходный многочлен п(Икс) для получения частного степени п − 2.

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

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

Полиномиальное деление в длину можно использовать, чтобы найти уравнение прямой, которая касательная к график функции определяется полиномом п(Икс) в определенной точке Икс = р.^[3] Если р(Икс) - остаток от деления п(Икс) к (Икс – р)², то уравнение касательной при Икс = р графику функции у = п(Икс) является у = р(Икс), независимо от того, есть ли р является корнем многочлена.

Пример

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

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

Начнем с деления полинома на ${ Displaystyle (х-1) ^ {2} = х ^ {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 {Белый} 01} x-42 { underline {-10x ^ {2} + 20x-10}} - 21x-32 end {array}}}$

Касательная линия ${ displaystyle y = -21x-32.}$

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

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

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

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

Примечания