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

Схе́ма Го́рнера (або правило Горнера, метод Горнера) — алгоритм обчислення значення многочлену, записаного у вигляді суми одночленів, при заданому значенні змінної. Метод Горнера дозволяє знайти корені многочлену, а також обчислити похідні поліному в заданій точці. Схема Горнера також є простим алгоритмом для ділення многочлена на біном у вигляді$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{align} 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{align}$

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

При діленні многочлена $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 + c b_{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;
}

Див. також

• Ділення многочленів стовпчиком
• Ділення многочленів
• Ділення стовпчиком

Література

• Ананий В. Левитин Глава 6. Метод преобразования: Схема Горнера и возведение в степень // Алгоритмы: введение в разработку и анализ = Introduction to The Design and Analysis of Aigorithms. — М.: «Вильямс», 2006. — С. 284—291. — ISBN 0-201-74395-7
• Волков Е. А. § 2. Вычисление значений многочлена. Схема Горнера // Численные методы. — Учеб. пособие для вузов. — 2-е изд., испр. — М.: Наука, 1987. — 248 с.
• С. Б. Гашков §14. Схема Горнера и перевод из одной позиционной системы в другую // Системы счисления и их применение. — М.: МЦНМО, 2004. — С. 37-39. — (Библиотека «Математическое просвещение»). — ISBN 5-94057-146-8

Посилання

• Схема Горнера (рос.)