Русская Википедия:Схема Горнера
Схе́ма Го́рнера (или правило Горнера, метод Горнера, метод Руффини-Горнера) — алгоритм вычисления значения многочлена, записанного в виде суммы мономов (одночленов), при заданном значении переменной. Метод Горнера позволяет найти корни многочлена[1], а также вычислить производные полинома в заданной точке. Схема Горнера также является простым алгоритмом для деления многочлена на бином вида <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>
Также с помощью схемы Горнера можно вычислять значение числа в позиционной системе исчисления.
Примечания
См. также
Литература
Ссылки
- Схема Горнера
- Вычисление многомерных полиномов — обобщение схемы Горнера на случай полинома от нескольких переменных.
- Метод Горнера в комплексном поле
- ↑ Если целочисленный многочлен обладает целыми корнями, то они будут найдены среди делителей свободного члена. Шаблон:Книга Шаблон:Wayback