Обчислення значення полінома використовуючи схему Горнера
Нехай дано многочлен -ї степені:
коефіцієнтами якого являються дійсні числа. І примустимо, що нам необхідно обчислити значення даного многочлена в точці
:
Найпростіший спосіб обчислення числа полягає в тому, щоб послідовно піднести
до другої, третьої і так далі, аж до
-ї степені. Після цього кожне отримане число
помножити на відповідний коефіцієнт
і все просумувати. При цьому нам необхідно зробити
операцій додавання і
-ну операцію множення.
Проте, існують і більш економні способи обчислення числа . Наприклад, загальновідома схема Горнера, яка дозволяє обчислити значення многочлена за
операцій множення та
операцій додавання. Для того, щоб розглянути дану схему більш детально, перепишемо формулу (2) у наступному вигляді:
Звідси, послідовно обчислюючи числа:
знаходимо . Покажемо також, що числа
є коефіцієнтами полінома
, отриманого при діленні даного полінома
на двочлен
. Справді, нехай
і
, де
— остаток від лілення, який на підставі теореми Безу, можна вважати рівним значенню многочлена в точці
, тобто
. З формул (4), (5) отримаємо:
або, розкривши дужки і зробивши приведення подібних членів, матимемо:
Порівнюючи коефіцієнти при однакових степенях змінної в лівій і правій частинах останньої рівності, отримаємо:
що і потрібно було довести.
Таким чином, формули (3) дозволяють, не здійснюючи операції ділення, визначати коефіцієнти частки , а також залишок. Практично, обчислення здійснюються за наступною схемою, яку і називають схемою Горнера:
Схема Горнера — приклад:
Обчислити значення многочлена при
. Для цього, складемо наступну схему Горнера:
Це круто!