схема Горнера

Схема Горнера - спосіб розподілу багаточлена

на біном $ x-a $. Працювати доведеться з таблицею, перший рядок якої містить коефіцієнти заданого многочлена. Першим елементом другого рядка буде число $ a $, взяте з бинома $ x-a $:

Після поділу многочлена n-го ступеня на біном $ x-a $, отримаємо многочлен, ступінь якого на одиницю менше вихідного, тобто дорівнює $ n-1 $. Безпосереднє застосування схеми Горнера найпростіше показати на прикладах.

Розділити $ 5x ^ 4 + 5x ^ 3 + x ^ 2-11 $ на $ x-1 $, використовуючи схему Горнера.

Складемо таблицю з двох рядків: в першому рядку запишемо коефіцієнти многочлена $ 5x ^ 4 + 5x ^ 3 + x ^ 2-11 $, розташовані по спадаючій ступенів змінної $ x $. Зауважте, що даний многочлен не містить $ x $ в першого ступеня, тобто коефіцієнт перед $ x $ в першого ступеня дорівнює 0. Так як ми ділимо на $ x-1 $, то у другому рядку запишемо одиницю:

Почнемо заповнювати порожні клітинки в другому рядку. У другу осередок другого рядка запишемо число $ 5 $, просто перенісши його з відповідної комірки першого рядка:

Наступну осередок заповнимо за таким принципом: $ 1 \ cdot 5 + 5 = 10 $:

Аналогічно заповнимо і четверту осередок другого рядка: $ 1 \ cdot 10 + 1 = 11 $:

Для п'ятої осередку отримаємо: $ 1 \ cdot 11 + 0 = 11 $:

І, нарешті, для останньої, шостої осередки, маємо: $ 1 \ cdot 11 + (- 11) = 0 $:

Завдання вирішена, залишилося тільки записати відповідь:

Як бачите, числа, розташовані в другому рядку (між одиницею і нулем), є коефіцієнти многочлена, отриманого після ділення $ 5x ^ 4 + 5x ^ 3 + x ^ 2-11 $ на $ x-1 $. Природно, що так як ступінь вихідного многочлена $ 5x ^ 4 + 5x ^ 3 + x ^ 2-11 $ дорівнювала чотирьом, то ступінь отриманого многочлена $ 5x ^ 3 + 10x ^ 2 + 11x + 11 $ на одиницю менше, тобто . дорівнює трьом. Останнє число у другому рядку (нуль) означає залишок від ділення многочлена $ 5x ^ 4 + 5x ^ 3 + x ^ 2-11 $ на $ x-1 $. У нашому випадку залишок дорівнює нулю, тобто многочлени діляться без остачі. Цей результат ще можна охарактеризувати так: значення многочлена $ 5x ^ 4 + 5x ^ 3 + x ^ 2-11 $ при $ x = 1 $ дорівнює нулю.

Можна сформулювати висновок і в такій формі: так як значення многочлена $ 5x ^ 4 + 5x ^ 3 + x ^ 2-11 $ при $ x = 1 $ дорівнює нулю, то одиниця є коренем многочлена $ 5x ^ 4 + 5x ^ 3 + x ^ 2-11 $.

Розділити многочлен $ x ^ 4 + 3x ^ 3 + 4x ^ 2-5x-47 $ на $ x + 3 $ за схемою Горнера.

Відразу обмовимося, що вираз $ x + 3 $ потрібно представити в формі $ x - (- 3) $. У схемі Горнера прийматиме участь саме $ -3 $. Так як ступінь вихідного многочлена $ x ^ 4 + 3x ^ 3 + 4x ^ 2-5x-47 $ дорівнює чотирьом, то в результаті поділу отримаємо многочлен третього ступеня:

Отриманий результат означає, що

$$ x ^ 4 + 3x ^ 3 + 4x ^ 2-5x-47 = (x + 3) (x ^ 3 + 0 \ cdot x ^ 2 + 4x-17) + 4 = (x + 3) (x ^ 3 + 4x-17) + 4 $$

У цій ситуації залишок від ділення $ x ^ 4 + 3x ^ 3 + 4x ^ 2-5x-47 $ на $ x + 3 $ дорівнює $ 4 $. Або, що те саме, значення многочлена $ x ^ 4 + 3x ^ 3 + 4x ^ 2-5x-47 $ при $ x = -3 $ дорівнює $ 4 $. До речі, це нескладно перевірити безпосередній підстановкою $ x = -3 $ в заданий многочлен:

$$ x ^ 4 + 3x ^ 3 + 4x ^ 2-5x-47 = (- 3) ^ 4 + 3 \ cdot (-3) ^ 3-5 \ cdot (-3) -47 = 4. $$

Тобто схему Горнера можна використовувати, якщо необхідно знайти значення многочлена при заданому значенні змінної. Якщо наша мета - знайти всі корені многочлена, то схему Горнера можна застосовувати кілька разів поспіль, - до тих пір, поки ми не вичерпаємо все коріння, як розглянуто в прикладі №3.

Знайти всі цілочисельні корені многочлена $ x ^ 6 + 2x ^ 5-21x ^ 4-20x ^ 3 + 71x ^ 2 + 114x + 45 $, використовуючи схему Горнера.

Коефіцієнти розглянутого багаточлена є цілі числа, а коефіцієнт перед старшої ступенем змінної (тобто перед $ x ^ 6 $) дорівнює одиниці. В цьому випадку цілочисельні корені многочлена потрібно шукати серед дільників вільного члена, тобто серед дільників числа 45. Для заданого многочлена такими країнами можуть бути числа $ 45; \; 15; \; 9; \; 5; \; 3; \; 1 $ і $ -45; \; -15; \; -9; \; -5; \; -3; \; -1 $. Перевіримо, наприклад, число $ 1 $:

Як бачите, значення многочлена $ x ^ 6 + 2x ^ 5-21x ^ 4-20x ^ 3 + 71x ^ 2 + 114x + 45 $ при $ x = 1 $ дорівнює $ 192 $ (останнє число в другому рядку), а не $ 0 $, тому одиниця не є коренем даного многочлена. Так як перевірка для одиниці закінчилася невдачею, перевіримо значення $ x = -1 $. Нову таблицю для цього складати не будемо, а продовжуватимемо використовувати табл. №1, дописавши в неї нову (третю) рядок. Другий рядок, в якій перевірялося значення $ 1 $, виділимо червоним кольором і в подальших міркуваннях використовувати її не будемо.

Можна, звичайно, просто переписати таблицю заново, але при заповненні вручну це займе чимало часу. Тим більше, що чисел, перевірка яких закінчиться невдачею, може бути кілька, і кожен раз записувати нову таблицю важко. При обчисленні «на папері» червоні рядки можна просто викреслювати.

Отже, значення многочлена $ x ^ 6 + 2x ^ 5-21x ^ 4-20x ^ 3 + 71x ^ 2 + 114x + 45 $ при $ x = -1 $ дорівнює нулю, тобто число $ -1 $ є корінь цього многочлена. Після поділу многочлена $ x ^ 6 + 2x ^ 5-21x ^ 4-20x ^ 3 + 71x ^ 2 + 114x + 45 $ на біном $ x - (- 1) = x + 1 $ отримаємо многочлен $ x ^ 5 + x ^ 4-22x ^ 3 + 2x ^ 2 + 69x + 45 $, коефіцієнти якого взяті з третього рядка табл. №2 (див. Приклад №1). Результат обчислень можна також представити у такій формі:

Продовжимо пошук цілочисельних коренів. Тепер вже потрібно шукати коріння многочлена $ x ^ 5 + x ^ 4-22x ^ 3 + 2x ^ 2 + 69x + 45 $. Знову-таки, цілочисельні корені цього многочлена шукають серед дільників його вільного члена, - числа $ 45 $. Спробуємо ще раз перевірити число $ -1 $. Нову таблицю становити не будемо, а продовжуватимемо використовувати попередній табл. №2, тобто допишемо в неї ще один рядок:

Отже, число $ -1 $ є коренем многочлена $ x ^ 5 + x ^ 4-22x ^ 3 + 2x ^ 2 + 69x + 45 $. Цей результат можна записати так:

З огляду на рівність (2), рівність (1) можна переписати в такій формі:

Тепер вже потрібно шукати коріння многочлена $ x ^ 4-22x ^ 2 + 24x + 45 $, - природно, серед дільників його вільного члена (числа $ 45 $). Перевіримо ще раз число $ -1 $:

Число $ -1 $ є коренем многочлена $ x ^ 4-22x ^ 2 + 24x + 45 $. Цей результат можна записати так:

З урахуванням рівності (4), рівність (3) перепишемо в такій формі:

Тепер шукаємо корені многочлена $ x ^ 3-x ^ 2-21x + 45 $. Перевіримо ще раз число $ -1 $:

Перевірка закінчилася невдачею. Виділимо шостий рядок червоним кольором і спробуємо перевірити інше число, наприклад, число $ 3 $:

У залишку нуль, тому число $ 3 $ - корінь даного многочлена. Отже, $ x ^ 3-x ^ 2-21x + 45 = (x-3) (x ^ 2 + 2x-15) $. Тепер рівність (5) можна переписати так:

Перевіримо ще раз число $ 3 $:

Отриманий результат можна записати так (це продовження рівності (6)):

З останньої дужки видно, що число $ -5 $ також є коренем даного многочлена. Можна, звичайно, формально продовжити схему Горнера, перевіривши значення $ x = -5 $, але необхідності в цьому немає. Отже,

Числа $ 1; \; 3; \; 5 $ - коріння даного многочлена. Причому, так як дужка $ (x + 1) $ в третього ступеня, то $ -1 $ - корінь третього порядку; так як дужка $ (x-3) $ в другому ступені, то $ 3 $ - корінь другого порядку; так як дужка $ (x + 5) $ в першого ступеня, то $ x = -5 $ - корінь першого порядку (простий корінь).

Взагалі, звичайно оформлення таких прикладів складається з таблиці, в якій перебираються можливі варіанти коренів, і відповіді:

З таблиці випливає висновок, отриманий нами раніше з докладним рішенням:

Переконатися, що числа $ 2 $ і $ -5 $ є корінням багаточлена $ 3x ^ 6 + 9x ^ 5-28x ^ 4 + 6x ^ 3-30x ^ 2-30x + 100 $. Розділити заданий многочлен на біном $ x-2 $ і $ x + 5 $.

Ступінь многочлена $ 3x ^ 6 + 9x ^ 5-28x ^ 4 + 6x ^ 3-30x ^ 2-30x + 100 $ дорівнює $ 6 $. Після поділу на два заданих бинома ступінь заданого многочлена зменшиться на $ 2 $, тобто стане дорівнює $ 4 $.

Звичайно, даний метод підбору малоефективний в загальному випадку, коли коріння не є цілими числами, але для цілочисельних коренів метод досить-таки непоганий.