Схема Горнера: Алгоритмический Анализ, Вычислительная Эффективность и Применение в Численных Методах

Введение: Актуальность и Исторический Контекст Метода Горнера

В мире численных методов одной из наиболее фундаментальных и часто решаемых задач является вычисление значения полинома $P(x)$ в заданной точке $x_{0}$. Полиномы, представляющие собой базовые математические модели, лежат в основе интерполяции, аппроксимации функций, решения дифференциальных уравнений и цифровой обработки сигналов. Эффективность и точность алгоритма, используемого для этой задачи, напрямую влияет на производительность и надежность всего вычислительного процесса, следовательно, выбор правильного метода — не просто академический интерес, а практическая необходимость для инженера и математика.

Схема Горнера (или метод Горнера) — это классический алгоритм, который до сих пор остается эталоном эффективности в этом классе задач. Актуальность его изучения обусловлена не только исторической значимостью, но и его непревзойденной простотой и оптимальностью по числу арифметических операций в последовательной архитектуре, а также его применимостью в качестве основы для более сложных алгоритмов, в том числе для параллельных вычислений.

История возникновения: От Цинь Цзюшао до Горнера

История схемы Горнера является ярким примером того, как фундаментальные математические идеи могут возникать независимо в разных культурах и эпохах. Хотя метод носит имя Уильяма Джорджа Горнера, опубликовавшего его в 1819 году, его корни уходят значительно глубже.

В XIII веке, задолго до европейского Ренессанса, китайский математик Цинь Цзюшао в своем монументальном труде «Шу шу цзю чжан» («Девять книг по математике»), изданном в 1247 году, описал метод, который по своей сути являлся обобщением принципа последовательных приближений для решения алгебраических уравнений высших степеней. Этот метод, известный как «метод Тянь-юань», содержал алгоритмическую структуру, идентичную современной схеме Горнера.

В Европе алгоритм был заново открыт и систематизирован. В 1804 году итальянский математик Паоло Руффини представил схожий метод, известный как правило Руффини, для деления полинома на линейный двучлен. Однако наибольшую известность и признание в англоязычной научной традиции алгоритм получил благодаря Уильяму Джорджу Горнеру.

Горнер представил свой доклад «A New Method of Solving Numerical Equations of all Orders, by Continuous Approximation» («Новый метод решения численных уравнений всех порядков, путем непрерывного приближения») в Лондонском королевском обществе, который был опубликован в Philosophical Transactions of the Royal Society of London в 1819 году. Работа Горнера была посвящена решению алгебраических уравнений, где схема рекуррентного вычисления коэффициентов была использована как ключевой шаг. Таким образом, хотя Горнер не был первым, кто изобрел алгоритм, именно его подробное изложение и связь с общими вычислительными задачами закрепили за ним это название в мировой науке.

Математическая Основа и Последовательный Алгоритм

Схема Горнера представляет собой элегантную рекуррентную формулу, которая позволяет перевести многочлен из стандартной формы записи в форму вложенных скобок. Это преобразование критически важно для минимизации вычислительных затрат.

Формальное определение и рекуррентные формулы

Рассмотрим многочлен $P(x)$ степени $n$ с коэффициентами $a_k$:

$$P(x) = a_{n}x^{n} + a_{n-1}x^{n-1} + \dots + a_{1}x + a_{0}$$

Для вычисления значения $P(x)$ в точке $x_{0}$, схема Горнера реструктурирует полином следующим образом:

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

Эта структура, известная как вложенное представление, позволяет заменить вычисление $n$ степеней и $(2n-1)$ умножений на последовательность из $n$ умножений и $n$ сложений, обеспечивая линейную вычислительную сложность.

Математически схема Горнера определяется через последовательность коэффициентов $b_k$, где $b_0 = P(x_0)$. Рекуррентная формула задается следующим образом:

1. Начальное условие: Коэффициент старшей степени принимается как первый коэффициент частного:
   $$b_{n} = a_{n}$$
2. Рекуррентный шаг: Для $k = n-1, n-2, \dots, 0$:
   $$b_{k} = a_{k} + b_{k+1}x_{0}$$

Конечное значение $b_{0}$ является искомым значением полинома $P(x_{0})$.

Пошаговый алгоритм и табличное представление

Для практического применения алгоритм Горнера удобно представлять в табличной форме, что особенно наглядно при ручных расчетах и при работе с полиномами, содержащими нулевые коэффициенты.

Пошаговая процедура:

1. Подготовка: Записываются все коэффициенты $a_n, a_{n-1}, \dots, a_0$ в верхнюю строку таблицы по убыванию степеней. Если какая-либо степень отсутствует, ее коэффициент должен быть записан как ноль (это критически важно для корректности алгоритма).
2. Инициализация: В левый столбец (за пределами таблицы) помещается значение $x_0$, в котором требуется вычислить полином. Первый коэффициент $a_n$ переносится без изменений во вторую строку, становясь первым коэффициентом $b_n$.
3. Итерация: Последовательно вычисляются все $b_k$ по формуле $b_{k} = a_{k} + b_{k+1}x_{0}$.
   • Число $b_{k+1}$ (предыдущий результат) умножается на $x_0$.
   • Полученный результат прибавляется к коэффициенту $a_k$ (число над ячейкой).
   • Результат записывается как $b_k$.
4. Результат: Последний элемент во второй строке, $b_0$, является значением $P(x_{0})$.

Коэффициенты	$a_n$	$a_{n-1}$	$\dots$	$a_1$	$a_0$
$x_0$	$b_n = a_n$	$b_{n-1} = a_{n-1} + b_n x_0$	$\dots$	$b_1 = a_1 + b_2 x_0$	$b_0 = a_0 + b_1 x_0$

Применение Схемы Горнера для Деления и Поиска Корней

Практическая ценность схемы Горнера выходит за рамки простого вычисления значения: она является основой для синтетического деления полиномов и мощным инструментом для поиска их корней. Это расширяет область ее применения от элементарной алгебры до углубленного анализа вычислительной сложности в современных системах.

Деление полинома на линейный двучлен

Схема Горнера представляет собой алгоритмическую реализацию деления полинома $P(x)$ на линейный двучлен $(x — c)$. Согласно теореме Безу, остаток $R$ от деления полинома $P(x)$ на $(x — c)$ равен значению полинома в точке $c$, то есть $R = P(c)$.

При использовании схемы Горнера для деления $P(x)$ на $(x — c)$, коэффициенты $b_k$ во второй строке таблицы имеют двойное значение:

1. Последний элемент ($b_0$) является остатком $R$ от деления, который, как и предписывает теорема Безу, равен $P(c)$.
2. Остальные элементы ($b_n, b_{n-1}, \dots, b_1$) являются коэффициентами неполного частного $Q(x)$, причем степень $Q(x)$ на единицу меньше степени $P(x)$.

Таким образом, если $P(x)$ — многочлен степени $n$, то частное $Q(x)$ будет иметь степень $n-1$:

$$Q(x) = b_{n}x^{n-1} + b_{n-1}x^{n-2} + \dots + b_{2}x + b_{1}$$

Связь между полиномом, частным и остатком формально выражается тождеством деления:

$$P(x) = (x — c)Q(x) + R$$

Если остаток $R$ равен нулю, это немедленно означает, что $x = c$ является корнем многочлена $P(x)$, и полином делится нацело на $(x — c)$.

Нахождение рациональных корней

Схема Горнера является незаменимым инструментом при поиске рациональных корней многочленов с целыми коэффициентами. Поиск основан на Теореме о рациональных корнях (Теореме Гаусса), которая значительно сужает круг потенциальных кандидатов, что делает процесс ручного и машинного поиска корней упорядоченным и быстрым.

Теорема Гаусса гласит: если рациональное число $p/q$ (где $p$ и $q$ взаимно простые) является корнем многочлена $P(x) = a_{n}x^{n} + \dots + a_{0}$ с целыми коэффициентами, то числитель $p$ должен быть делителем свободного члена $a_0$, а знаменатель $q$ должен быть делителем старшего коэффициента $a_n$.

Алгоритм поиска корней с использованием схемы Горнера:

1. Определяются все возможные кандидаты $p/q$ на рациональные корни.
2. Каждый кандидат $c$ последовательно проверяется с помощью схемы Горнера.
3. Если при делении $P(x)$ на $(x — c)$ остаток $R$ (то есть $b_0$) равен нулю, то $c$ — корень.
4. После нахождения корня $c$, можно применить этот же процесс к полученному частному $Q(x)$ (пониженной степени), чтобы найти остальные корни. Этот процесс называется последовательным понижением степени (дефляцией) полинома.

Многократное применение схемы Горнера позволяет эффективно находить все рациональные корни, упрощая исходный многочлен до тех пор, пока не останется неприводимый многочлен более низкой степени.

Углубленный Анализ Вычислительной Сложности и Эффективности

Эффективность схемы Горнера является ее главным преимуществом. Анализ вычислительной сложности показывает, почему этот метод остается оптимальным для последовательных вычислений.

Последовательная сложность и преимущество по операциям

Вычислительная сложность алгоритма обычно оценивается по количеству элементарных арифметических операций.

Рассмотрим многочлен степени $n$: $P(x) = a_{n}x^{n} + \dots + a_{0}$.

Метод	Операции умножения	Операции сложения	Общая сложность
Прямое вычисление	$O(n^{2})$ или $(2n-1)$	$n$	$O(n^{2})$ или $O(n)$
Схема Горнера	$n$	$n$	$\Theta(n)$

Прямой метод (наивный) требует вычисления каждой степени $x^k$ отдельно, что в худшем случае дает квадратичную сложность. Даже при оптимизации, когда каждая степень $x^k$ вычисляется на основе $x^{k-1}$, требуется $(n-1) + n = (2n-1)$ умножений для получения всех членов $a_k x^k$.

Схема Горнера требует ровно $n$ умножений и $n$ сложений, что делает ее сложность линейной — $\Theta(n)$.

Критическое преимущество: В современных вычислительных системах операция умножения требует существенно больше времени, чем операция сложения. Схема Горнера минимизирует количество умножений до абсолютного минимума $n$. Именно это критическое снижение затрат на умножение обеспечивает высокую производительность, особенно при работе с полиномами высокой степени.

Параллельная сложность и схемы сдваивания

В контексте современных многоядерных и высокопроизводительных систем, необходимо рассмотреть, насколько схема Горнера поддается распараллеливанию. Как же добиться максимальной скорости на параллельных машинах?

Последовательная схема Горнера по своей природе является строго последовательной, поскольку каждый следующий коэффициент $b_k$ зависит от предыдущего $b_{k+1}$. Таким образом, стандартная схема не может быть легко распараллелена для сокращения временной сложности ниже $\Theta(n)$ на одном процессоре.

Однако в параллельной вычислительной математике существуют алгоритмы, которые позволяют обойти эту последовательную зависимость. Это достигается за счет использования метода, основанного на параллельном префиксном суммировании (Parallel Prefix Sum), или так называемой схемы сдваивания (doubling scheme).

Используя ассоциативность операций, можно переформулировать вычисление полинома. При применении параллельных алгоритмов, которые активно используются в векторных процессорах или многоядерных архитектурах:

• Параллельная временная сложность (время, затраченное до получения результата, $T_p$): может быть снижена до $O(\log n)$.
• Параллельная работа/стоимость (общее количество операций, $W_p$): остается $O(n)$.

Таким образом, для достижения максимальной скорости на параллельных машинах используются более сложные алгоритмы, основанные на идеях Горнера, но адаптированные для распараллеливания, позволяя вычислять полином чрезвычайно быстро, за время, логарифмически зависящее от его степени.

Оценка Погрешности и Точность Вычислений

В численных методах критически важно понимать, как алгоритм влияет на точность конечного результата. Схема Горнера обладает хорошими свойствами в отношении минимизации накопления погрешности.

Абсолютная и относительная погрешности

При вычислении $P(x_0)$ мы имеем дело с двумя основными типами погрешностей:

1. Погрешности входных данных: Неточности в коэффициентах $a_k$ или в самой точке $x_0$.
2. Машинные погрешности (округления): Возникают при выполнении арифметических операций на ЭВМ из-за ограничения разрядности.

Абсолютная погрешность ($\Delta P$) — это модуль разности между точным значением $P_{\text{точн}}(x_0)$ и вычисленным $P_{\text{выч}}(x_0)$:

$$\Delta P = |P_{\text{точн}}(x_0) — P_{\text{выч}}(x_0)|$$

Относительная погрешность ($\delta P$) — это отношение абсолютной погрешности к точному значению (при условии, что $P_{\text{точн}}(x_0) \ne 0$):

$$\delta P = \frac{\Delta P}{|P_{\text{точн}}(x_0)|}$$

Схема Горнера, за счет минимального количества арифметических операций (всего $2n$), минимизирует количество точек, в которых происходит округление, что напрямую уменьшает накопление машинной погрешности. Это особенно важно при решении систем с плавающей запятой.

Обусловленность задачи и влияние схемы Горнера на точность

Обусловленность задачи — это мера чувствительности решения к малым изменениям во входных данных. Задача вычисления полинома в точке является хорошо обусловленной, если малые изменения $x_0$ или $a_k$ приводят к малым изменениям $P(x_0)$.

Однако, при вычислении полинома в стандартной форме, особенно при больших степенях $n$ и больших значениях $x$, могут возникать проблемы с потерей значащих разрядов при сложении чисел сильно отличающихся порядков (например, при сложении $a_0$ и $a_n x^n$).

Схема Горнера, используя рекуррентное сложение и умножение, структурирует вычисления таким образом, что промежуточные результаты $b_k$ находятся в более контролируемом диапазоне. Это снижает риск потери точности, связанный с прямым вычислением очень больших степеней $x^n$.

Вывод: Использование схемы Горнера является не только вопросом скорости, но и важным фактором повышения точности. Сокращение числа операций — это прямое средство борьбы с накоплением машинных погрешностей округления.

Программная Реализация и Обобщение Метода

Практическая реализация схемы Горнера на компьютере требует выбора оптимальной алгоритмической структуры.

Алгоритмические структуры и псевдокод

Схема Горнера идеально подходит для итеративной реализации, поскольку рекуррентный шаг $b_{k} = a_{k} + b_{k+1}x_{0}$ выполняется последовательно, начиная со старшего коэффициента $a_n$ до свободного члена $a_0$.

Представление данных: Полином $P(x)$ представляется в памяти как одномерный массив коэффициентов coeffs, индексированный от 0 до $n$.

Псевдокод схемы Горнера (итеративный):

ФУНКЦИЯ Horner_Scheme (coeffs, n, x0):
  // coeffs: массив коэффициентов [a_0, a_1, ..., a_n]
  // n: степень полинома
  // x0: точка вычисления

  // 1. Инициализация (b_n = a_n)
  результат = coeffs[n]

  // 2. Итеративный цикл (k от n-1 до 0)
  ДЛЯ i ОТ n-1 ДО 0:
    результат = coeffs[i] + результат * x0
  
  ВОЗВРАТ результат

Пример реализации на C++:

/**
 * Функция для вычисления полинома по схеме Горнера.
 * @param coeffs Массив коэффициентов [a_0, a_1, ..., a_n]
 * @param n Степень полинома
 * @param x0 Точка вычисления
 * @return Значение P(x0)
 */
double horner(const double coeffs[], int n, double x0) {
    // Начало с a_n (коэффициент n-ой степени)
    double result = coeffs[n]; 

    // Цикл от n-1 до 0
    for (int i = n - 1; i >= 0; i--) {
        // b_k = a_k + b_{k+1} * x0
        result = coeffs[i] + result * x0; 
    }
    return result;
}

Такая реализация является чрезвычайно компактной и быстрой, требуя всего один цикл с $n$ итерациями.

Обобщение схемы Горнера для многомерных полиномов

Классическая схема Горнера предназначена для полиномов от одной переменной. Однако принцип вложенного вычисления может быть обобщен и для многомерных полиномов (полиномов от нескольких переменных).

Рассмотрим полином от двух переменных $P(x, y)$. Его можно представить в виде:

$$P(x, y) = \sum_{i=0}^{n} \sum_{j=0}^{m} a_{ij} x^{i} y^{j}$$

Для вычисления такого полинома можно использовать обобщенную схему Горнера, которая применяет последовательное вложение. Полином рассматривается как полином от одной переменной (например, $x$), коэффициентами которого являются полиномы от другой переменной ($y$):

$$P(x, y) = Q_0(y) + x \cdot Q_1(y) + x^2 \cdot Q_2(y) + \dots + x^n \cdot Q_n(y)$$

Сначала применяется схема Горнера по переменной $x$, где в качестве «коэффициентов» $Q_i(y)$ используются полиномы от $y$. Затем каждый из этих внутренних полиномов $Q_i(y)$ также вычисляется с помощью схемы Горнера по переменной $y$.

Роль в высокопроизводительных вычислениях: Обобщенная схема Горнера для многомерных полиномов критически важна в задачах компьютерной графики (полиномиальные поверхности), численного моделирования и высокопроизводительных вычислений. Это позволяет декомпозировать сложную многомерную задачу на серию более простых одномерных задач, которые затем могут быть эффективно распараллелены для выполнения на кластерах или GPU.

Заключение

Схема Горнера, будучи одним из старейших алгоритмов в вычислительной математике, сохраняет свое фундаментальное значение и актуальность. Исследование показало, что ее превосходство обусловлено не только исторической преемственностью, но и объективными алгоритмическими преимуществами. Мы убедились, что в своей области она является, по сути, идеальным инструментом.

В контексте курсовой работы, посвященной численным методам, мы установили:

1. Историческая строгость: Метод, представленный Уильямом Джорджем Горнером в 1819 году, имеет глубокие корни, восходящие к работам Цинь Цзюшао, что подчеркивает универсальность математических принципов.
2. Математическая оптимальность: Схема Горнера преобразует полином в форму вложенных скобок, что позволяет вычислять $P(x_0)$ с минимальным числом операций: $n$ умножений и $n$ сложений.
3. Прикладная эффективность: Алгоритм является основой для синтетического деления полиномов на линейный двучлен и незаменимым инструментом для систематического нахождения рациональных корней.
4. Вычислительное превосходство: В последовательном режиме схема демонстрирует оптимальную линейную сложность $\Theta(n)$. Более того, в параллельных вычислительных средах, благодаря схемам сдваивания, ее временная сложность может быть снижена до $O(\log n)$, что является критически важным фактором для современных высокопроизводительных вычислений.
5. Точность: За счет сокращения общего количества арифметических операций, схема Горнера минимизирует накопление машинных погрешностей, способствуя повышению точности результата.

Таким образом, схема Горнера является образцом алгоритмической элегантности и эффективности. Она не только обеспечивает высокую скорость вычисления, но и является важным эталоном для разработки и анализа более сложных алгоритмов в алгебре и вычислительной математике.

Список использованной литературы

1. Деление полиномов на двучлен. Схема Горнера. [Электронный ресурс] // Инфоурок. URL: https://infourok.ru/prezentaciya-po-algebre-delenie-polinomov-na-dvuchlen-shema-gornera-2826978.html (дата обращения: 22.10.2025).
2. Схема Горнера. [Электронный ресурс] // Math.ru. URL: https://math.ru/dic/scheme (дата обращения: 22.10.2025).
3. Как найти рациональные корни многочлена? Схема Горнера. [Электронный ресурс] // MathProfi.net. URL: https://mathprofi.net/a_korni_mnogochlena.html (дата обращения: 22.10.2025).
4. Схема Горнера. Примеры с пояснениями. [Электронный ресурс] // AMK Book. URL: https://amkbook.net/matematika/mnogochleny/skhema-gornera-primery (дата обращения: 22.10.2025).
5. ВЫЧИСЛЕНИЕ ЗНАЧЕНИЙ ПОЛИНОМА С ПОМОЩЬЮ СХЕМЫ ГОРНЕРА. [Электронный ресурс] // Международный студенческий научный вестник. URL: https://www.eduherald.ru/ru/article/view?id=12595 (дата обращения: 22.10.2025).
6. Вычисление значений полинома. Схема Горнера. [Электронный ресурс] // Сибирская Электронная Библиотека. URL: https://www.siblec.ru/matematika/chislennye-metody/64-vychislenie-znacheniy-polinoma-shema-gornera (дата обращения: 22.10.2025).
7. Схема Горнера Уильям Джордж Горнер (1786-1831). [Электронный ресурс] // URL: https://e.sfu-kras.ru/bitstream/handle/2311/129753/ovsyannikov.pdf (дата обращения: 22.10.2025).
8. Схема Горнера в картинках. Алгоритм и примеры решений. [Электронный ресурс] // MathProfi.net. URL: https://mathprofi.net/a_horner_scheme_pictures.html (дата обращения: 22.10.2025).
9. Девяткин Е. Эффективное вычисление полинома. Схема Горнера. [Электронный ресурс]. URL: https://eugene-devyatkin.ru/blog/horner (дата обращения: 22.10.2025).
10. Определение Схемы Горнера. [Электронный ресурс]. URL: https://uchitelya.com/algebra/139339-opredelenie-shemy-gornera.html (дата обращения: 22.10.2025).
11. Вычисление значений многомерных полиномов. [Электронный ресурс] // КиберЛенинка. URL: https://cyberleninka.ru/article/n/vychislenie-znacheniy-mnogomernyh-polinomov (дата обращения: 22.10.2025).
12. Схема Горнера. [Электронный ресурс] // Словари и энциклопедии на Академике. URL: https://dic.academic.ru/dic.nsf/ruwiki/1690184 (дата обращения: 22.10.2025).
13. ИСТОРИЯ РАЗВИТИЯ И МЕТОД ИСПОЛЬЗОВАНИЯ СХЕМЫ ГОРНЕРА. [Электронный ресурс] // Elibrary. URL: https://www.elibrary.ru/item.asp?id=43936630 (дата обращения: 22.10.2025).
14. Схема Горнера, вещественная версия, последовательный вариант. [Электронный ресурс] // AlgoWiki. URL: https://algowiki-project.org/ru/Схема_Горнера,_вещественная_версия,_последовательный_вариант (дата обращения: 22.10.2025).