Ділення многочленів
В алгебрі ділення многочленів стовпчиком — алгоритм ділення многочлена на многочлен , степінь якого менше або дорівнює степеню многочлена . Алгоритм являє собою узагальнену форму ділення чисел стовпчиком, легко реалізується вручну. Для будь-яких многочленів та , , існують єдині поліноми та , такі що
- ,
причому має нижчу ступінь, ніж .
Метою алгоритму ділення многочленів в стовпчик є знаходження частки і остачі для заданих діленого та ненульового дільника .
Ділення многочленів у стовпчик
ред.Ділити многочлени в стовпчик можна алгоритмом, аналогічним до того, як діляться натуральні числа.
- Спочатку треба перевірити, чи обидва многочлени впорядковані за спадними степенями тієї самої змінної; якщо ні, то впорядкувати їх, дописуючи також ті члени, яких немає (наприклад, замість писатиметься ).
- «Підготувати» многочлени до ділення.
- Поділити найстарший член діленого на найстарший член дільника.
- Помножити отриманий одночлен на дільник.
- Відняти отриманий многочлен від діленого.
- Продовжувати так само, поки не отримаємо нуль або многочлен зі степенем меншим за степінь дільника. Це і є остача даного ділення.
Приклад
ред.Покажемо, що
Частка і остача від ділення можуть бути знайдені при виконанні наступних кроків:
1. Ділимо перший елемент діленого на старший елемент дільника, розташовуємо результат під рисою .
2. Множимо дільник на отриманий вище результат ділення (на перший елемент частки). Записуємо результат під першими двома елементами діленого .
3. Віднімаємо, отриманий після множення, многочлен від діленого, записуємо результат під рискою .
4. Повторюємо попередні 3 кроки, використовуючи як ділене многочлен, записаний під рискою.
5. Повторюємо крок 4.
6. Кінець алгоритму.
Таким чином, многочлен — частка від ділення, а — остача.
Див. також
ред.Джерела
ред.- Завало С. Т. (1985). Курс алгебри. Київ: Вища школа. с. 503. (укр.)
- Прасолов В. В. Многочлены. — 2-е. — Москва : МЦНМО, 2001. — 336 с. — ISBN 5-94057-077-1.(рос.)
- Дональд Кнут. Seminumerical Algorithms // The Art of Computer Programming. — 3rd. — Massachusetts : Addison–Wesley, 1997. — Т. 2. — 762 с. — ISBN 0-201-89684-2.(англ.)