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

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

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

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

$P(x)=a_0+a_{1}x+a_2{x}^2+a_3{x}^3+\dots +a_n{x}^n,a_i\in ℝ.$

Пусть требуется вычислить значение данного многочлена при фиксированном значении $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}_0,$

…

$b_i=a_i+b_{i+1}{x}_0,$

…

$b_0=a_0+b_1{x}_0.$

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

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

$\begin{array}{cc}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 ))=\\ & ⋮\\ & =a_0+x_0{b}_1=\\ & =b_0.\end{array}$

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

При делении многочлена $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)=b_n+b_{n-1}(x-c)+b_{n-2}(x-c{)}^2+\cdots +b_0(x-c{)}^n.$

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

$P^{(k)}(c)=k!b_{n-k}.$

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

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

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

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

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

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

Разделим $x^3-6x^2+11x-6$ на $x-2$:

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

Новый многочлен $x^2-4x+3$.

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

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

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

$\frac{f_1(x)}{f_2(x)}=2x^3-2x^2-x+1-\frac{4}{2x-1}.$

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

См. также

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

Литература

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

Ссылки

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