Синтетическое подразделение

В алгебре , то синтетическое разделение представляет собой способ для ручного выполнения евклидова деления многочленов , с меньшим количеством письменной формы и меньше вычислений , чем длинное деление .

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

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

Регулярное синтетическое деление [ править ]

Первый пример - синтетическое деление с моническим линейным знаменателем .${\displaystyle x-a}$

${\displaystyle {\frac {x^{3}-12x^{2}-42}{x-3}}}$

Числитель можно записать как .${\displaystyle p(x)=x^{3}-12x^{2}+0x-42}$

Нуль знаменателя является .${\displaystyle g(x)}$${\displaystyle 3}$

Коэффициенты расположены следующим образом, с нулем слева: ${\displaystyle p(x)}$${\displaystyle g(x)}$

${\displaystyle {\begin{array}{cc}{\begin{array}{r}\\3\\\end{array}}&{\begin{array}{|rrrr}\ 1&-12&0&-42\\&&&\\\hline \end{array}}\end{array}}}$

Первый коэффициент после бара «упал» до последней строки.

${\displaystyle {\begin{array}{cc}{\begin{array}{r}\\3\\\\\end{array}}&{\begin{array}{|rrrr}\color {blue}1&-12&0&-42\\&&&\\\hline \color {blue}1&&&\\\end{array}}\end{array}}}$

Сократилось число умножается на числа до бара, и место в следующей колонке .

${\displaystyle {\begin{array}{cc}{\begin{array}{r}\\\color {grey}3\\\\\end{array}}&{\begin{array}{|rrrr}1&-12&0&-42\\&\color {brown}3&&\\\hline \color {blue}1&&&\\\end{array}}\end{array}}}$

В следующем столбце выполняется добавление .

${\displaystyle {\begin{array}{cc}{\begin{array}{c}\\3\\\\\end{array}}&{\begin{array}{|rrrr}1&\color {green}-12&0&-42\\&\color {green}3&&\\\hline 1&\color {green}-9&&\\\end{array}}\end{array}}}$

Предыдущие два шага повторяются, и получается следующее:

${\displaystyle {\begin{array}{cc}{\begin{array}{c}\\3\\\\\end{array}}&{\begin{array}{|rrrr}1&-12&0&-42\\&3&-27&-81\\\hline 1&-9&-27&-123\end{array}}\end{array}}}$

Здесь последний член (-123) - это остаток, а остальные соответствуют коэффициентам частного.

Члены записываются с возрастающей степенью справа налево, начиная с нулевой степени для остатка и результата.

${\displaystyle {\begin{array}{rrr|r}1x^{2}&-9x&-27&-123\end{array}}}$

Следовательно, частное и остаток равны:

${\displaystyle q(x)=x^{2}-9x-27}$

${\displaystyle r(x)=-123}$

Вычисление многочленов по теореме об остатке [ править ]

Вышеупомянутая форма синтетического деления полезна в контексте теоремы о полиномиальном остатке для вычисления одномерных полиномов. Подводя итог, значение at равно оставшейся части . Преимущество вычисления значения таким способом состоит в том, что он требует чуть более половины шагов умножения, чем наивная оценка. Альтернативная стратегия оценки - метод Хорнера .${\displaystyle p(x)}$${\displaystyle a}$${\displaystyle {\frac {p(x)}{(x-a)}}}$

Расширенное синтетическое подразделение [ править ]

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

${\displaystyle {\frac {x^{3}-12x^{2}-42}{x^{2}+x-3}}}$

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

${\displaystyle {\begin{array}{|rrrr}\ 1&-12&0&-42\end{array}}}$

Отбросить коэффициенты делителя.

${\displaystyle {\begin{array}{rrr}-1x^{2}&-1x&+3\end{array}}}$

Впишите все коэффициенты, кроме первого слева, по диагонали направленной вверх (см. Следующую диаграмму).

${\displaystyle {\begin{array}{cc}{\begin{array}{rr}\\&3\\-1&\\\end{array}}&{\begin{array}{|rrrr}\ 1&-12&0&-42\\&&&\\&&&\\\hline \end{array}}\end{array}}}$

Обратите внимание на изменение знака с 1 на −1 и с −3 на 3 . «Перетащите» первый коэффициент после полосы в последнюю строку.

${\displaystyle {\begin{array}{cc}{\begin{array}{rr}\\&3\\-1&\\\\\end{array}}&{\begin{array}{|rrrr}1&-12&0&-42\\&&&\\&&&\\\hline 1&&&\\\end{array}}\end{array}}}$

Умножьте выпавшее число на диагональ перед полосой и разместите полученные записи по диагонали справа от выпавшей записи.

${\displaystyle {\begin{array}{cc}{\begin{array}{rr}\\&3\\-1&\\\\\end{array}}&{\begin{array}{|rrrr}1&-12&0&-42\\&&3&\\&-1&&\\\hline 1&&&\\\end{array}}\end{array}}}$

Выполните сложение в следующем столбце.

${\displaystyle {\begin{array}{cc}{\begin{array}{rr}\\&3\\-1&\\\\\end{array}}&{\begin{array}{|rrrr}1&-12&0&-42\\&&3&\\&-1&&\\\hline 1&-13&&\\\end{array}}\end{array}}}$

Повторяйте предыдущие два шага, пока не пройдете записи вверху со следующей диагональю .

${\displaystyle {\begin{array}{cc}{\begin{array}{rr}\\&3\\-1&\\\\\end{array}}&{\begin{array}{|rrrr}1&-12&0&-42\\&&3&-39\\&-1&13&\\\hline 1&-13&16&\\\end{array}}\end{array}}}$

Затем просто сложите оставшиеся столбцы.

${\displaystyle {\begin{array}{cc}{\begin{array}{rr}\\&3\\-1&\\\\\end{array}}&{\begin{array}{|rrrr}1&-12&0&-42\\&&3&-39\\&-1&13&\\\hline 1&-13&16&-81\\\end{array}}\end{array}}}$

Подсчитайте термины слева от полосы. Поскольку их два, остаток имеет степень один, и это два крайних правых члена под чертой. Отметьте разделение вертикальной чертой.

${\displaystyle {\begin{array}{rr|rr}1&-13&16&-81\end{array}}}$

Члены записываются с возрастающей степенью справа налево, начиная с нулевой степени как для остатка, так и для результата.

${\displaystyle {\begin{array}{rr|rr}1x&-13&16x&-81\end{array}}}$

Результат нашего деления:

${\displaystyle {\frac {x^{3}-12x^{2}-42}{x^{2}+x-3}}=x-13+{\frac {16x-81}{x^{2}+x-3}}}$

Для немонических делителей [ править ]

Немного подтолкнув, расширенную технику можно еще больше обобщить для работы с любым многочленом, а не только с мониками . Обычный способ сделать это - разделить делитель на его старший коэффициент (назовите его a ):${\displaystyle g(x)}$

${\displaystyle h(x)={\frac {g(x)}{a}}}$

затем используйте синтетическое деление с в качестве делителя, а затем разделите частное на a, чтобы получить частное от исходного деления (остаток остается неизменным). Но это часто приводит к некрасивым дробям, которые позже удаляются и, следовательно, более подвержены ошибкам. Это можно сделать без предварительного уменьшения коэффициентов .${\displaystyle h(x)}$${\displaystyle g(x)}$

Как можно заметить, сначала выполняя длинное деление с таким немоническим делителем, коэффициенты делятся на ведущий коэффициент после «отбрасывания» и до умножения.${\displaystyle f(x)}$${\displaystyle g(x)}$

Проиллюстрируем, выполнив следующее деление:

${\displaystyle {\frac {6x^{3}+5x^{2}-7}{3x^{2}-2x-1}}}$

Используется немного измененная таблица:

${\displaystyle {\begin{array}{cc}{\begin{array}{rrr}\\&1&\\2&&\\\\&&/3\\\end{array}}{\begin{array}{|rrrr}6&5&0&-7\\&&&\\&&&\\\hline &&&\\&&&\\\end{array}}\end{array}}}$

Обратите внимание на дополнительную строку внизу. Это используется для записи значений, найденных путем деления "отброшенных" значений на ведущий коэффициент (в данном случае, обозначенный / 3 ; обратите внимание, что, в отличие от остальных коэффициентов , знак этого числа не изменяется) .${\displaystyle g(x)}$${\displaystyle g(x)}$

Далее, как обычно, опускается первый коэффициент :${\displaystyle f(x)}$

${\displaystyle {\begin{array}{cc}{\begin{array}{rrr}\\&1&\\2&&\\\\&&/3\\\end{array}}{\begin{array}{|rrrr}6&5&0&-7\\&&&\\&&&\\\hline 6&&&\\&&&\\\end{array}}\end{array}}}$

а затем выпавшее значение делится на 3 и помещается в строку ниже:

${\displaystyle {\begin{array}{cc}{\begin{array}{rrr}\\&1&\\2&&\\\\&&/3\\\end{array}}{\begin{array}{|rrrr}6&5&0&-7\\&&&\\&&&\\\hline 6&&&\\2&&&\\\end{array}}\end{array}}}$

Затем новое (разделенное) значение используется для заполнения верхних строк числами, кратными 2 и 1, как в расширенной технике:

${\displaystyle {\begin{array}{cc}{\begin{array}{rrr}\\&1&\\2&&\\\\&&/3\\\end{array}}{\begin{array}{|rrrr}6&5&0&-7\\&&2&\\&4&&\\\hline 6&&&\\2&&&\\\end{array}}\end{array}}}$

Затем отбрасывается 5 с обязательным добавлением 4 под ним, и ответ снова делится:

${\displaystyle {\begin{array}{cc}{\begin{array}{rrr}\\&1&\\2&&\\\\&&/3\\\end{array}}{\begin{array}{|rrrr}6&5&0&-7\\&&2&\\&4&&\\\hline 6&9&&\\2&3&&\\\end{array}}\end{array}}}$

Затем цифра 3 используется для заполнения верхних строк:

${\displaystyle {\begin{array}{cc}{\begin{array}{rrr}\\&1&\\2&&\\\\&&/3\\\end{array}}{\begin{array}{|rrrr}6&5&0&-7\\&&2&3\\&4&6&\\\hline 6&9&&\\2&3&&\\\end{array}}\end{array}}}$

На этом этапе, если бы после получения третьей суммы мы попытались использовать ее для заполнения верхних строк, мы бы «отвалились» от правой стороны, таким образом, третья сумма является первым коэффициентом остатка, как в обычном синтетическое деление. Но значения остатка не делятся на старший коэффициент делителя:

${\displaystyle {\begin{array}{cc}{\begin{array}{rrr}\\&1&\\2&&\\\\&&/3\\\end{array}}{\begin{array}{|rrrr}6&5&0&-7\\&&2&3\\&4&6&\\\hline 6&9&8&-4\\2&3&&\\\end{array}}\end{array}}}$

Теперь мы можем считать коэффициенты ответа. Как и в расширенном синтетическом делении, последние два значения (2 - степень делителя) являются коэффициентами остатка, а остальные значения являются коэффициентами частного:

${\displaystyle {\begin{array}{rr|rr}2x&+3&8x&-4\end{array}}}$

и результат

${\displaystyle {\frac {6x^{3}+5x^{2}-7}{3x^{2}-2x-1}}=2x+3+{\frac {8x-4}{3x^{2}-2x-1}}}$

Компактное расширенное синтетическое подразделение [ править ]

Однако указанный выше диагональный формат становится менее компактным, когда степень делителя превышает половину степени делимого. Легко видеть, что у нас есть полная свобода писать каждый продукт в любой строке, если он находится в правильном столбце. Таким образом, алгоритм может быть компактифицирован с помощью жадной стратегии , как показано в разделе ниже.

${\displaystyle {\dfrac {ax^{7}+bx^{6}+cx^{5}+dx^{4}+ex^{3}+fx^{2}+gx+h}{ix^{4}-jx^{3}-kx^{2}-lx-m}}=nx^{3}+ox^{2}+px+q+{\dfrac {rx^{3}+sx^{2}+tx+u}{ix^{4}-jx^{3}-kx^{2}-lx-m}}}$

${\displaystyle {\begin{array}{cc}{\begin{array}{rrrr}\\\\\\\\j&k&l&m\\\end{array}}&{\begin{array}{|rrrr|rrrr}&&&&qj&&&\\&&&pj&pk&qk&&\\&&oj&ok&ol&pl&ql&\\&nj&nk&nl&nm&om&pm&qm\\a&b&c&d&e&f&g&h\\\hline a&o_{0}&p_{0}&q_{0}&r&s&t&u\\n&o&p&q&&&&\\\end{array}}\end{array}}}$

Ниже описывается, как выполнять алгоритм; этот алгоритм включает шаги для деления немонических делителей:

Реализация Python [ править ]

Следующий фрагмент реализует расширенное синтетическое разделение для немонических многочленов (которое также поддерживает монические многочлены, поскольку это обобщение):

def  extended_synthetic_division ( делимое ,  делитель ):  "" "Быстрое полиномиальное деление с помощью расширенного синтетического деления.  Также работает с немоническими полиномами. Дивиденд и делитель - это многочлены, которые здесь просто списки коэффициентов.  Например: х ** 2 + 3 * х + 5 будет представлен в виде [1, 3, 5]  ""»  из  =  список ( дивидендов )  # Скопировать дивиденды  нормализатор  =  делитель [ 0 ]  для  ввода  в  диапазоне ( LEN ( дивиденды )  -  len ( divisor )  +  1 ):  # Для общего деления многочленов (когда многочлены немоничны), # нам нужно нормализовать, разделив коэффициент на первый коэффициент делителя  out [ i ]  / =  normalizer coef  =  out [ i ]  if  coef  ! =  0 :  # Бесполезно умножать, если coef равен 0  # При синтетическом делении мы всегда пропускаем первый коэффициент делителя,  # потому что он используется только для нормализации коэффициентов  деления для  j  в  диапазоне ( 1 ,  len ( divisor )):  out [ i  +  j ]  + =  - divisor [ j ]  *  coef # Результирующий результат содержит как частное, так и остаток,  # остаток равен размеру делителя (остаток  # обязательно имеет ту же степень, что и делитель, поскольку это  # то, что мы не можем разделить из делимого), поэтому мы вычислить индекс  #, где находится это разделение, и вернуть частное и остаток.  separator  =  1  -  len ( делитель )  return  out [: separator ],  out [ separator :]  # Возвращает частное, остаток.

См. Также [ править ]

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

Ссылки [ править ]

• Лянхуо Фань (2003). «Обобщение синтетического деления и общая теорема о делении многочленов» (PDF) . Математическое попурри . 30 (1): 30–37.
• Ли Чжоу (2009). «Краткое деление многочленов». Журнал математики колледжа . 40 (1): 44–46. DOI : 10.4169 / 193113409x469721 .

Внешние ссылки [ править ]

• Гудман, Лен ; Стовер, Кристофер и Вайсштейн, Эрик В. «Синтетическое подразделение» . MathWorld .
• Стовер, Кристофер . «Правило Руффини» . MathWorld .
• Синтетическое разделение (математика) в Британской энциклопедии