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

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

${\displaystyle x-a,\ }$

но метод обобщается на деление на любые монический многочлен, и любому многочлен.

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

Синтетическое деление для линейных знаменателей также называется делением на Правило Руффини.

Регулярное синтетическое деление

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

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

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

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

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

${\displaystyle {\begin{array}{rr}-1x&+3\end{array}}}$

Впишите все коэффициенты делителя, кроме первого слева.

${\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}1&-12&0&-42\\&&&\\\hline 1&&&\\\end{array}}\end{array}}}$

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

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

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

${\displaystyle {\begin{array}{cc}{\begin{array}{c}\\3\\\\\end{array}}&{\begin{array}{|rrrr}1&-12&0&-42\\&3&&\\\hline 1&-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}}}$

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

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

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

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

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

${\displaystyle {\frac {x^{3}-12x^{2}-42}{x-3}}=x^{2}-9x-27-{\frac {123}{x-3}}}$

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

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

Для немонических делителей

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

${\displaystyle h(x)={\frac {g(x)}{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}}}$

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

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

1. Напишите коэффициенты дивиденда на полосе${\displaystyle {\begin{array}{cc}{\begin{array}{|rrrrrrrr}\ a&b&c&d&e&f&g&h\\\hline \end{array}}\end{array}}}$
2. Игнорируя первый (ведущий) коэффициент делителя, отмените все коэффициенты и поместите их в левую часть полосы.${\displaystyle {\begin{array}{cc}{\begin{array}{rrrr}j&k&l&m\\\end{array}}&{\begin{array}{|rrrrrrrr}\ a&b&c&d&e&f&g&h\\\hline \end{array}}\end{array}}}$
3. Из числа коэффициентов, размещенных в левой части полосы, подсчитайте количество коэффициентов деления над полосой, начиная с самого правого столбца. Затем поместите вертикальную полосу слева, а также строку ниже этого столбца. Эта вертикальная черта обозначает разделение между частным и остатком.${\displaystyle {\begin{array}{cc}{\begin{array}{rrrr}j&k&l&m\\\\\end{array}}&{\begin{array}{|rrrr|rrrr}a&b&c&d&e&f&g&h\\\hline &&&&&&&\\\end{array}}\end{array}}}$
4. Опустите первый коэффициент дивиденда под столбик.${\displaystyle {\begin{array}{cc}{\begin{array}{rrrr}j&k&l&m\\\\\end{array}}&{\begin{array}{|rrrr|rrrr}a&b&c&d&e&f&g&h\\\hline a&&&&&&&\\\end{array}}\end{array}}}$
5. • Разделите ранее выпавшее / суммированное число на ведущий коэффициент делителя и поместите его в строку ниже (этого делать не нужно, если ведущий коэффициент равен 1). ${\displaystyle n={\dfrac {a}{i}}}$.
   • Умножьте ранее выпавшее / суммированное число (или разделенное отброшенное / суммированное число) на каждый отрицательный коэффициент делителя слева (начиная с самого левого); пропустить, если отброшенное / суммированное число равно нулю. Поместите каждый продукт поверх следующих столбцов.
   ${\displaystyle {\begin{array}{cc}{\begin{array}{rrrr}\\j&k&l&m\\\end{array}}&{\begin{array}{|rrrr|rrrr}&nj&nk&nl&nm&&&\\a&b&c&d&e&f&g&h\\\hline a&&&&&&&\\n&&&&&&&\\\end{array}}\end{array}}}$
6. Выполните добавление по столбцам в следующем столбце.
   ${\displaystyle {\begin{array}{cc}{\begin{array}{rrrr}\\j&k&l&m\\\end{array}}&{\begin{array}{|rrrr|rrrr}&nj&nk&nl&nm&&&\\a&b&c&d&e&f&g&h\\\hline a&o_{0}&&&&&&\\n&&&&&&&\\\end{array}}\end{array}}}$
7. Повторите два предыдущих шага. Остановитесь, когда вы выполнили предыдущие два шага над числом непосредственно перед вертикальной чертой. ${\displaystyle o={\dfrac {o_{0}}{i}}}$.${\displaystyle {\begin{array}{cc}{\begin{array}{rrrr}\\\\j&k&l&m\\\end{array}}&{\begin{array}{|rrrr|rrrr}&&oj&ok&ol&&&\\&nj&nk&nl&nm&om&&\\a&b&c&d&e&f&g&h\\\hline a&o_{0}&p_{0}&&&&&\\n&o&&&&&&\\\end{array}}\end{array}}}$Позволять ${\displaystyle p={\dfrac {p_{0}}{i}}}$.${\displaystyle {\begin{array}{cc}{\begin{array}{rrrr}\\\\\\j&k&l&m\\\end{array}}&{\begin{array}{|rrrr|rrrr}&&&pj&pk&&&\\&&oj&ok&ol&pl&&\\&nj&nk&nl&nm&om&pm&\\a&b&c&d&e&f&g&h\\\hline a&o_{0}&p_{0}&q_{0}&&&&\\n&o&p&&&&&\\\end{array}}\end{array}}}$Позволять ${\displaystyle q={\dfrac {q_{0}}{i}}}$.${\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&&&\\n&o&p&q&&&&\\\end{array}}\end{array}}}$
8. Выполните добавление оставшихся столбцов в последующих столбцах (вычисляя остаток).
   ${\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}}}$
9. Самые нижние результаты под горизонтальной полосой - это коэффициенты полиномов, остатка и частного. Где коэффициенты частного находятся слева от вертикальной черты разделения, а коэффициенты остатка - справа. Эти коэффициенты будут интерпретироваться с возрастающей степенью справа налево, начиная с нулевой степени как для остатка, так и для частного. Мы интерпретируем результаты, чтобы получить:${\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}}}$

Реализация Python

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

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

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

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

Рекомендации

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

внешняя ссылка

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