WikiSort.ru - Не сортированное

Схе́ма Го́рнера (или правило Горнера, метод Горнера, метод Руффини-Горнера) — алгоритм вычисления значения многочлена, записанного в виде суммы мономов (одночленов), при заданном значении переменной. Метод Горнера позволяет найти корни многочлена^[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)=A_{0}+A_{1}(x-c)+A_{2}(x-c)^{2}+\cdots +A_{n}(x-c)^{n}.}$

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

Рассчитать ${\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

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

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

Например, если ${\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

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

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

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

Примечания

См. также

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

Литература

• Левитин А. В. Глава 6. Метод преобразования: Схема Горнера и возведение в степень // Алгоритмы. Введение в разработку и анализ — М.: Вильямс, 2006. — С. 284–291. — 576 с. — ISBN 978-5-8459-0987-9
  <a href='https://wikidata.org/wiki/Track:Q21694518'></a><a href='https://wikidata.org/wiki/Track:Q21694521'></a><a href='https://wikidata.org/wiki/Track:Q21694522'></a>
• Волков Е. А. § 2. Вычисление значений многочлена. Схема Горнера // Численные методы. — Учеб. пособие для вузов. — 2-е изд., испр. — М.: Наука, 1987. — 248 с.
• С. Б. Гашков. § 14. Схема Горнера и перевод из одной позиционной системы в другую // Системы счисления и их применение. — М.: МЦНМО, 2004. — С. 37—39. — (Библиотека «Математическое просвещение»). — ISBN 5-94057-146-8.

Ссылки

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