ru.wikipedia.org

Схема Горнера — Википедия

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

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

{\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_{0},}
…
{\displaystyle b_{i}=a_{i}+b_{i+1}x_{0},}
…
{\displaystyle b_{0}=a_{0}+b_{1}x_{0}.}

Искомое значение {\displaystyle P(x_{0})} есть {\displaystyle 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},\quad b_{k}=a_{k}+cb_{k-1}.}

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

{\displaystyle P(x)=b_{n}+b_{n-1}(x-c)+b_{n-2}(x-c)^{2}+\cdots +b_{0}(x-c)^{n}.}

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

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

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

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

Здесь в первой строке записаны значение {\displaystyle x_{0}} и коэффициенты многочлена.

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

Например, если {\displaystyle a_{3}=2,a_{2}=-6,a_{1}=2,a_{0}=-1} мы видим, что {\displaystyle b_{3}=2,b_{2}=0,b_{1}=2,b_{0}=5} — значения в третьей строке. Так синтетическое деление базируется на методе Горнера.

Разделим {\displaystyle x^{3}-6x^{2}+11x-6} на {\displaystyle x-2}: 

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

Новый многочлен {\displaystyle x^{2}-4x+3}.

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

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

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

{\displaystyle {\frac {f_{1}(x)}{f_{2}(x)}}=2x^{3}-2x^{2}-x+1-{\frac {4}{2x-1}}.}


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

  1. ↑ Если целочисленный многочлен обладает целыми корнями, то они будут найдены среди делителей свободного члена. Курош А. Г. § 57. Рациональные корни целочисленных многочленов // Курс высшей алгебры. — Наука. — Москва, 1968. Архивировано 18 октября 2013 года.