Схе́ма Го́рнера (або правило Горнера, метод Горнера) — алгоритм обчислення значення многочлена, записаного у вигляді суми одночленів, при заданому значенні змінної. Метод Горнера дозволяє знайти корені многочлена, а також обчислити похідні поліному в заданій точці. Схема Горнера також є простим алгоритмом для ділення многочлена на біном у вигляді . Метод названо на честь Вільяма Джорджа Горнера.
Опис алгоритму Дано многочлен : .
Нехай потрібно обчислити значення даного многочлена при фіксованому значенні . Представимо многочлен в такому вигляді: .
Визначимо таку послідовність:
…
…
Шукане значення . Покажемо, що це правильно.
В отриману форму запису підставимо і будемо обчислювати значення виразу, починаючи з внутрішніх дужок. Для цього будемо замінювати підвирази на :
Використання схеми Горнера для ділення многочлена на біном При діленні многочлена на отримуємо многочлен з остачею .
За такої умови коефіцієнти отриманого многочлена задовольняють рекурентним співвідношенням: , .
Так само можна визначити кратність кореня (використати схему Горнера для нового полінома).
Так само схему можна використовувати для знаходження коефіцієнтів при розкладу поліному по степенях :
Приклади реалізації обчислення значення C++
/* * 6 * 3 * 1 3 -2 1 -1 1 * * Відповідь: 439 */
# include <stdlib.h> /** EXIT_FAILURE **/ # include <iostream> using namespace std;
int main(int argc, char *argv[]) { register unsigned int i; unsigned int n; cout << "Введіть кількість елементів: "; cin >> n;
if (n < 1 ) { cerr << "Потрібно хоча б два елементи." << endl; return EXIT_FAILURE;
double *a = new double [n]; double *b = new double [n];
cout << "Введіть епсилон: "; double eps; cin >> eps;
cout << "Введіть" << n << " вихідний елемент:" << endl; for ( i = 0; i < n; i++ ) cin >> a[i];
cout << endl;
/* Малюємо верхню рамку */ for ( i = 0; i < n; i++ ) cout << "+-------"; cout << "+" << endl;
/* Виводимо вихідні елементи */ for ( i = 0; i < n; i++ ) cout << "| " << a[i] << "\t"; cout << "|" << endl;
/* Знову рамка */ for ( i = 0; i < n; i++ ) cout << "+-------"; cout << "+" << endl;
/* За умовою, перший елемент b дорівнює першому елементу a */ b = a; cout << "| " << *b << "\t"; for( i = 1; i < n; i++ ) { b[i] = b[i - 1] * eps; /* В цьому місці b[i] буде дорівнювати значенню, що записується в другий рядок */ b[i] += a[i]; cout << "| " << b[i] << "\t"; } cout << "+" << endl;
/* І ще одна завершальна рамка */ for ( i = 0; i < n; i++ ) cout << "+-------"; cout << "+" << endl << endl; cout << "Відповідь: " << b[n-1] << endl;
delete []b; delete []a; return 0; }
Див. також Корінь многочлена Ділення многочленів Ділення стовпчиком Метод Ліля
Література Anany Levitin Introduction to the Design and Analysis of Algorithms, 3rd Edition Chapter 6.5 Horner's Rule 2012. — 565 с.
Посилання Схема Горнера