Схема Горнера

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Схе́ма Го́рнера (або правило Горнера, метод Горнера) — алгоритм обчислення значення многочлену, записаного у вигляді суми одночленів, при заданому значенні змінної. Метод Горнера дозволяє знайти корені многочлену, а також обчислити похідні поліному в заданій точці. Схема Горнера також є простим алгоритмом для ділення многочлена на біном у вигляді . Метод названий на честь Вільяма Джорджа Горнера.

Опис алгоритму[ред.ред. код]

Дано многочлен :

.

Нехай потрібно обчислити значення даного многочлена при фіксованому значенні . Представимо многочлен в наступному вигляді:

.

Визначимо наступну послідовність:

Шукане значення . Покажемо, що це вірно.

В отриману форму запису підставимо і будемо обчислювати значення виразу, починаючи з внутрішніх дужок. Для цього будемо замінювати підвирази на :

Використання схеми Горнера для ділення многочлена на біном[ред.ред. код]

При діленні многочлена на отримуємо многочлен з остачею .

При цьому коефіцієнти отриманого многочлена задовільняють рекурентним співвідношенням:

, .

Таким же чином можна визначити кратність кореня (використати схему Горнера для нового полінома). Так само схему можна використовувати для знаходження коефіцієнтів при розкладу поліному по степенях x — c:

Приклади реалізації обчислення значення[ред.ред. код]

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;
}

Див. також[ред.ред. код]

Література[ред.ред. код]

Посилання[ред.ред. код]