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

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

Опис алгоритму

Дано многочлен $P(x)$ :

P(x)=a_{0}+a_{1}x+a_{2}x^{2}+a_{3}x^{3}+\ldots +a_{n}x^{n},\quad a_{i}\in \mathbb {R}

.

Нехай потрібно обчислити значення даного многочлена при фіксованому значенні $x=x_{0}$ . Представимо многочлен $P(x)$ в наступному вигляді:

P(x)=a_{0}+x(a_{1}+x(a_{2}+\cdots x(a_{n-1}+a_{n}x)\dots ))

.

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

b_{n}=a_{n}\,\!

b_{n-1}=a_{n-1}+b_{n}x\,\!

…

b_{i}=a_{i}+b_{i+1}x\,\!

…

b_{0}=a_{0}+b_{1}x\,\!

Шукане значення $P(x_{0})=b_{0}$ . Покажемо, що це правильно.

В отриману форму запису $P(x)$ підставимо $x=x_{0}$ і будемо обчислювати значення виразу, починаючи з внутрішніх дужок. Для цього будемо замінювати підвирази на $b_{i}$ :

{\begin{aligned}P(x_{0})&=a_{0}+x_{0}(a_{1}+x_{0}(a_{2}+\cdots x_{0}(a_{n-1}+a_{n}x_{0})\dots ))\\&=a_{0}+x_{0}(a_{1}+x_{0}(a_{2}+\cdots x_{0}(b_{n-1})\dots ))\\&{}\ \ \vdots \\&=a_{0}+x_{0}(b_{1})\\&=b_{0}\end{aligned}}

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

При діленні многочлена $a_{0}x^{n}+a_{1}x^{n-1}+\cdots +a_{n-1}x+a_{n}$ на $x-c$ отримуємо многочлен $b_{0}x^{n-1}+b_{1}x^{n-2}+\cdots +b_{n-2}x+b_{n-1}$ з остачею $b_{n}$ .

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

b_{0}=a_{0}

,

b_{k}=a_{k}+cb_{k-1}

.

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

Так само схему можна використовувати для знаходження коефіцієнтів при розкладу поліному по степенях $x-c$ :

$P(x)=A_{0}+A_{1}(x-c)+A_{2}(x-c)^{2}+\cdots +A_{n}(x-c)^{n}$

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

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 2012. — 565 с. (англ.)
Волков Е. А. § 2. Вычисление значений многочлена. Схема Горнера // Численные методы. — Учеб. пособие для вузов. — 2-е изд., испр. — М.: Наука, 1987. — 248 с. (рос.)
С. Б. Гашков §14. Схема Горнера и перевод из одной позиционной системы в другую // Системы счисления и их применение. — М.: МЦНМО, 2004. — С. 37—39. — (Библиотека «Математическое просвещение»). — ISBN 5-94057-146-8 (рос.)

Посилання

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.