Руффіні-Горнера метод

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

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

Дано многочлен ${\displaystyle P(x)}$:

${\displaystyle 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} }$.

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

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

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

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

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

…

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

…

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

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

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

${\displaystyle {\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}}}$

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

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

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

${\displaystyle b_{0}=a_{0}}$, ${\displaystyle b_{k}=a_{k}+cb_{k-1}}$.

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

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

${\displaystyle 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 [ 1 травня 2021 у Wayback Machine.] 2012. — 565 с. (англ.)

Посилання

• Обчислення значення полінома використовуючи схему Горнера [ 27 жовтня 2020 у Wayback Machine.]
• Схема Горнера [ 8 травня 2017 у Wayback Machine.]