Обчислення значення полінома використовуючи схему Горнера

Нехай дано многочлен -ї степені:

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

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

Проте, існують і більш економні способи обчислення числа . Наприклад, загальновідома схема Горнера, яка дозволяє обчислити значення многочлена за  операцій множення та  операцій  додавання. Для того, щоб розглянути дану схему більш детально, перепишемо формулу (2) у наступному вигляді:

Звідси, послідовно обчислюючи числа:

знаходимо . Покажемо також, що числа є коефіцієнтами полінома , отриманого при діленні даного полінома  на двочлен . Справді, нехай і , де — остаток від лілення, який на підставі теореми Безу, можна вважати рівним значенню многочлена в точці , тобто . З формул (4), (5) отримаємо:

або, розкривши дужки і зробивши приведення подібних членів, матимемо:

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

що і потрібно було довести.

Таким чином, формули (3) дозволяють, не здійснюючи операції ділення, визначати коефіцієнти частки , а також залишок. Практично, обчислення здійснюються за наступною схемою, яку і називають схемою Горнера:

Схема Горнера — приклад:

Обчислити значення многочлена при . Для цього, складемо наступну схему Горнера:

Блок-схема алгоритму обчислення значення многочлена в точці  використовуючи схему Горнера: