Схе́ма Го́рнера (або правило Горнера, метод Горнера) — алгоритм обчислення значення многочлена, записаного у вигляді суми (одночленів), при заданому значенні змінної. Метод Горнера дозволяє знайти (корені многочлена), а також обчислити похідні поліному в заданій точці. Схема Горнера також є простим алгоритмом для ділення многочлена на (біном) у вигляді . Метод названо на честь (Вільяма Джорджа Горнера).
Опис алгоритму
Дано многочлен :
.
Нехай потрібно обчислити значення даного многочлена при фіксованому значенні . Представимо многочлен
в такому вигляді:
.
Визначимо таку послідовність:
- …
- …
Шукане значення . Покажемо, що це правильно.
В отриману форму запису підставимо
і будемо обчислювати значення виразу, починаючи з внутрішніх дужок. Для цього будемо замінювати підвирази на
:
Використання схеми Горнера для ділення многочлена на біном
При діленні многочлена на
отримуємо многочлен
з остачею
.
За такої умови коефіцієнти отриманого многочлена задовольняють рекурентним співвідношенням:
,
.
Так само можна визначити кратність кореня (використати схему Горнера для нового полінома).
Так само схему можна використовувати для знаходження коефіцієнтів при розкладу поліному по степенях :
Приклади реалізації обчислення значення
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[0] = a[0]; 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 [ 1 травня 2021 у Wayback Machine.] 2012. — 565 с. (англ.)
Посилання
- Обчислення значення полінома використовуючи схему Горнера [ 27 жовтня 2020 у Wayback Machine.]
- Схема Горнера [ 8 травня 2017 у Wayback Machine.]
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет