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

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

shema_gornera2

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

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

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

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

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

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

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

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

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

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

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

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

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

Схема Горнера алгоритм

Матеріал був корисним, поділись в соціальних мережах:

Якщо тобі сподобалась дана тема, залиш свій коментар