Русская Википедия:Схема Горнера

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Схе́ма Го́рнера (или правило Горнера, метод Горнера, метод Руффини-Горнера) — алгоритм вычисления значения многочлена, записанного в виде суммы мономов (одночленов), при заданном значении переменной. Метод Горнера позволяет найти корни многочлена, а также вычислить производные полинома в заданной точке. Схема Горнера также является простым алгоритмом для деления многочлена на бином вида <math>x - c</math>. Метод назван в честь Уильяма Джорджа Горнера, однако Паоло Руффини опередил Горнера на 15 лет, а китайцам этот способ был известен еще в XIII веке.

Описание алгоритма

Задан многочлен

<math>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}.</math>

Пусть требуется вычислить значение данного многочлена при фиксированном значении <math>x = x_0</math>. Представим многочлен <math>P(x)</math> в следующем виде:

<math>P(x) = a_0 + x(a_1 + x(a_2 + \cdots x(a_{n-1} + a_n x) \dots)).</math>

Определим следующую последовательность:

<math>b_n = a_n,</math>

<math>b_{n-1} = a_{n-1} + b_n x_0,</math>

…

<math>b_i = a_i + b_{i+1} x_0,</math>

…

<math>b_0 = a_0 + b_1 x_0.</math>

Искомое значение <math>P(x_0)</math> есть <math>b_0</math>. Покажем, что это так.

В полученную форму записи <math>P(x)</math> подставим <math>x = x_0</math> и будем вычислять значение выражения, начиная с внутренних скобок. Для этого будем заменять подвыражения через <math>b_i</math>:

<math>

\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} </math>

Использование схемы Горнера для деления многочлена на бином

При делении многочлена <math>a_0 x^n + a_1 x^{n-1} + \cdots + a_{n-1} x + a_n</math> на <math>x - c</math> получается многочлен <math>b_0 x^{n-1} + b_1 x^{n-2} + \cdots + b_{n-2} x + b_{n-1}</math> с остатком <math>b_n</math> (см. теорема Безу).

При этом коэффициенты результирующего многочлена удовлетворяют рекуррентным соотношениям

<math>b_0 = a_0, \quad b_k = a_k + c b_{k-1}.</math>

Таким же образом можно определить кратность корней (использовать схему Горнера для нового полинома). Также схему можно использовать для нахождения коэффициентов при разложении полинома по степеням <math>(x - c)</math>:

<math>P(x) = b_n + b_{n-1} (x - c) + b_{n-2} (x - c)^2 + \cdots + b_0 (x - c)^n.</math>

Схема Горнера может использоваться для нахождения производных многочлена:

<math>P^{(k)}(c) = k!b_{n-k}.</math>

Примеры использования

Рассчитать <math>f(x)=2x^3-6x^2+2x-1</math> для <math>x=3.</math> Используем синтетическое деление:

 x₀│   x³    x²    x¹    x⁰
 3 │   2    −6     2    −1
   │         6     0     6
   └────────────────────────
       2     0     2     5

Здесь в первой строке записаны значение <math>x_0</math> и коэффициенты многочлена.

Значения (по столбцам) в третьей строке соответствуют сумме значений первой и второй строки (<math>b_{n-1} = a_{n-1} + b_n x_0</math>), а значения второй строки произведению x на значение в третьей строке предыдущего столбца (<math>b_n x_0</math>).

Например, если <math>a_3 = 2, a_2 = -6, a_1 = 2, a_0 = -1</math> мы видим, что <math>b_3 = 2, b_2 = 0, b_1 = 2, b_0 = 5 </math> — значения в третьей строке. Так синтетическое деление базируется на методе Горнера.

Разделим <math>x^3-6x^2+11x-6</math> на <math>x-2</math>:

 2 │   1    −6    11    −6
   │         2    −8     6
   └────────────────────────
       1    −4     3     0

Новый многочлен <math>x^2-4x+3</math>.

Пусть <math>f_1(x)=4x^4-6x^3+3x-5</math> и <math>f_2(x)=2x-1</math>. Разделим <math>f_1(x)</math> на <math>f_2\,(x)</math>, используя метод Горнера.

  2 │  4    −6    0    3   │   −5
────┼──────────────────────┼───────
  1 │        2   −2   −1   │    1
    └──────────────────────┼───────
       2    −2   −1    1   │   −4

Tретья строка — сумма первых двух, деленная на два. Каждое значение второй строки совпадает с значением третьей строки в предыдущем столбце. Ответ на деление:

<math>\frac{f_1(x)}{f_2(x)}=2x^3-2x^2-x+1-\frac{4}{2x-1}.</math>

Также с помощью схемы Горнера можно вычислять значение числа в позиционной системе исчисления.

См. также

• Деление многочленов столбиком
• Деление столбиком
• Метод Лиля

Литература

• Шаблон:Source
• Шаблон:Книга
• Шаблон:Книга

Ссылки

• Схема Горнера
• Вычисление многомерных полиномов — обобщение схемы Горнера на случай полинома от нескольких переменных.
• Метод Горнера в комплексном поле