Horner scheme
A method for obtaining the incomplete fraction and the remainder in the division of a polynomial \begin\label f(x) = a_n x^n + a_ x^ + \cdots + a_1 x + a_0 \end by a binomial $x-a$, where all the coefficients $a,a_0,\ldots,a_n$ lie in a certain field, e.g. in the field of complex numbers. Any polynomial $f(x)$ can be uniquely represented in the form $ f(x) = g(x)(x-a) + r $ where $g(x) = b_x^ + b_x^ + \cdots + b_0$ is the incomplete fraction, while $r$ is the remainder which, according to the Bezout theorem, equals $f(a)$. The coefficients of $g(x)$ and $r$ are calculated by the recurrence formulas \begin\label \left.< \begin b_ = a_n,\ \ b_ = a_ + a b_,\ \ldots\,,\ b_0 = a_1 + a b_1 \ ; \\ r = a_0 + a b_0 \end >\right\rbrace\ \ . \end
Схема Горнера
на бином $x-a$. Работать придётся с таблицей, первая строка которой содержит коэффициенты заданного многочлена (они выделены для наглядности синим цветом). Первым элементом второй строки будет число $a$, взятое из бинома $x-a$:
$$ P_n(x)=\normblue>x^+\normblue>x^+\normblue>x^+\ldots+\normblue
Вторая строка таблицы заполняется постепенно. Второй элемент этой строки (обозначим его $b_0$) равен $a_0$, т.е., по сути, мы просто переносим вниз число $a_0$:
$$ \begin
Следующий элемент второй строки, который мы обозначим как $b_1$, получается по такой формуле: $b_1=a\cdot+a_1$:
$$ \begin
Далее находим элемент $b_2$ по формуле $b_2=a\cdot+a_2$:
$$ \begin
Аналогично вычисляем и элемент $b_3=a\cdot+a_3$:
$$ \begin
Далее находим $b_4$, $b_5$ и так далее. В целом, общая формула для вычисления $b_i$, где $i\ge$, будет такой:
В конечном итоге, мы вычислим последний элемент $b_n = a\cdot>+a_n$, и на этом работа будет закончена. Заполненная таблица будет иметь такой вид:
$$ \begin
После деления исходного многочлена n-ой степени $P_n(x)$ на бином $x-a$, получим многочлен, степень которого на единицу меньше исходного, т.е. равна $n-1$. Последнее число второй строки, т.е. $b_n$, есть остаток от деления $P_n(x)$ на $x-a$:
Если вспомнить теорему Безу, то можно сформулировать и так: число $b_n$ равно значению многочлена $P_n(x)$ при $x=a$, т.е. $b_n = P_n (a)$.
Если $b_n=0$, то исходный многочлен делится на бином $x-a$ нацело, т.е. число $a$ является корнем этого многочлена. Непосредственное применение схемы Горнера проще всего показать на примерах.
Разделить $5x^4+5x^3+x^2-11$ на $x-1$, используя схему Горнера.
Для сокращения записи обозначим заданный многочлен как $P(x)$, т.е. $P(x)=5x^4+5x^3+x^2-11$. Для начала составим таблицу из двух строк. В первой строке запишем коэффициенты многочлена $P(x)$, расположенные по убыванию степеней переменной $x$. Заметьте, что данный многочлен не содержит $x$ в первой степени, т.е. коэффициент перед $x$ в первой степени равен 0:
Так как мы делим на $x-\normred$, то в первой ячейке второй строки запишем число $\normred$. Таблица, с которой мы будем работать, имеет такой вид:
$$ \begin
Начнём заполнять пустые ячейки во второй строке. Во вторую ячейку второй строки запишем число $5$, просто перенеся его вниз из второй ячейки первой строки:
$$ \begin
Следующую ячейку заполним по такому принципу: $\normred\cdot\normgreen+\normpurple=\normblue$:
$$ \begin
Аналогично заполним и четвертую ячейку второй строки: $\normred\cdot\normgreen+\normpurple=\normblue$:
$$ \begin
Для пятой ячейки получим: $\normred\cdot\normgreen+\normpurple=\normblue$:
$$ \begin
И, наконец, для последней, шестой ячейки, имеем: $\normred\cdot\normgreen+\normpurple=\normblue$:
$$ \begin
Числа, расположенные во второй строке (между единицей и нулём), есть коэффициенты многочлена, полученного после деления $P(x)$ на $x-1$. Последнее число во второй строке (ноль) равно остатку от деления многочлена $P(x)$ на $x-1$. Остаток равен нулю, т.е. многочлен $P(x)$ делится на $x-1$ нацело. Для наглядности я запишу полученный результат, выделив коэффициенты разными цветами:
$$ \begin
Естественно, что так как степень исходного многочлена $P(x)$ равнялась четырём, то степень многочлена $5x^3+10x^2+11x+11$ на единицу меньше, т.е. равна трём.
Полученный нами результат можно ещё охарактеризовать так: значение многочлена $P(x)$ при $x=1$ равно нулю. Так как значение многочлена $P(x)$ при $x=1$ равно нулю, то единица является корнем многочлена $P(x)$.
Ответ: $5x^4+5x^3+x^2-11 = (x-1)\left(5x^3+10x^2+11x+11\right)$.
Разделить многочлен $x^4+3x^3+4x^2-5x-47$ на $x+3$ по схеме Горнера.
Для сокращения записи обозначим заданный многочлен как $P(x)$, т.е. $P(x)=x^4+3x^3+4x^2-5x-47$. Сразу оговорим, что выражение $x+3$ нужно представить в форме $x-(-3)$. В схеме Горнера будет учавствовать именно $-3$. Выполняем преобразования, аналогичные сделанным в примере №1:
$$ \begin
Так как степень исходного многочлена $P(x)$ равна четырём, то в результате деления получим многочлен третьей степени.
$$P(x)=(x+3)\left(x^3+0\cdot x^2 +4x-17\right)+4=(x+3)\left(x^3+4x-17\right)+4$$
Полученный результат означает, что многочлен $P(x)$ делится на бином $x+3$ не нацело. Остаток от деления $P(x)$ на $x+3$ равен $4$. Этот же результат означает, что значение многочлена $P(x)$ при $x=-3$ равно $4$, т.е. $P(-3)=4$. Кстати, это несложно перепроверить непосредственной подстановкой $x=-3$ в заданный многочлен:
$$ x^4+3x^3+4x^2-5x-47=(-3)^4+3 \cdot (-3)^3-5 \cdot (-3)-47=4. $$
Т.е. схему Горнера можно также использовать, если необходимо найти значение многочлена при заданном значении переменной.
Ответ: $x^4+3x^3+4x^2-5x-47=(x+3)\left(x^3+4x-17\right)+4$.
Если наша цель – найти все корни многочлена, то схему Горнера можно применять несколько раз подряд, – до тех пор, пока мы не исчерпаем все корни, как рассмотрено в примере №3.
Найти все целочисленные корни многочлена $x^6+2x^5-21x^4-20x^3+71x^2+114x+45$, используя схему Горнера.
Для сокращения записи обозначим заданный многочлен как $P(x)$, т.е.
Коэффициенты рассматриваемого многочлена есть целые числа, а коэффициент перед старшей степенью переменной (т.е. перед $x^6$) равен единице. В этом случае целочисленные корни многочлена нужно искать среди делителей свободного члена, т.е. среди делителей числа 45. Для заданного многочлена такими корнями могут быть числа $45; \; 15; \; 9; \; 5; \; 3; \; 1$ и $-45; \; -15; \; -9; \; -5; \; -3; \; -1$. Проверим, к примеру, число $1$:
$$ \begin
Как видите, значение многочлена $P(x)$ при $x=1$ равно $192$ (последнее число в второй строке), а не $0$, посему единица не является корнем данного многочлена. Так как проверка для единицы окончилась неудачей, проверим значение $x=-1$. Новую таблицу составлять не будем, а продолжим использование табл. №1, дописав в нее новую (третью) строку. Вторую строку, в которой проверялось значение $1$, выделим красным цветом и в дальнейших рассуждениях использовать её не будем.
Можно, конечно, просто переписать таблицу заново, но при заполнении вручную это займет немало времени. Тем более, что чисел, проверка которых окончится неудачей, может быть несколько, и каждый раз записывать новую таблицу затруднительно. При вычислении «на бумаге» красные строки можно просто вычёркивать.
$$ \begin
Итак, значение многочлена $P(x)$ при $x=-1$ равно нулю, т.е. $P(-1)=0$. Это значит, что число $-1$ есть корень многочлена $P(x)$. После деления многочлена $P(x)$ на бином $x-(-1)=x+1$ получим многочлен $x^5+x^4-22x^3+2x^2+69x+45$, коэффициенты которого взяты из третьей строки табл. №2. Результат вычислений можно также представить в такой форме:
Продолжим поиск целочисленных корней. Теперь уже нужно искать корни многочлена $x^5+x^4-22x^3+2x^2+69x+45$. Опять-таки, целочисленные корни этого многочлена ищут среди делителей его свободного члена, – числа $45$. Попробуем ещё раз проверить число $-1$. Новую таблицу составлять не будем, а продолжим использование предыдущей табл. №2, т.е. допишем в нее еще одну строку:
$$ \begin
Итак, число $-1$ является корнем многочлена $x^5+x^4-22x^3+2x^2+69x+45$. Этот результат можно записать так:
Учитывая равенство (2), равенство (1) можно переписать в такой форме:
$$ \begin P(x)=(x+1)\left(x^5+x^4-22x^2+2x^2+69x+45\right)=\\ =(x+1)(x+1)\left(x^4-22x^2+24x+45\right) =(x+1)^2\left(x^4-22x^2+24x+45\right) \end $$
Теперь уже нужно искать корни многочлена $x^4-22x^2+24x+45$, – естественно, среди делителей его свободного члена (числа $45$). Проверим еще раз число $-1$:
$$ \begin
Число $-1$ является корнем многочлена $x^4-22x^2+24x+45$. Этот результат можно записать так:
С учетом равенства (4), равенство (3) перепишем в такой форме:
$$ \begin P(x)=(x+1)^2\left(x^4-22x^3+24x+45\right)=\\ =(x+1)^2(x+1)\left(x^3-x^2-21x+45\right) =(x+1)^3\left(x^3-x^2-21x+45\right) \end $$
Теперь ищем корни многочлена $x^3-x^2-21x+45$. Проверим еще раз число $-1$:
$$ \begin
Проверка окончилась неудачей. Выделим шестую строку красным цветом и попробуем проверить иное число, например, число $3$:
$$ \begin
В остатке ноль, посему число $3$ – корень рассматриваемого многочлена. Итак,
Теперь равенство (5) можно переписать так:
Проверим ещё раз число $3$:
$$ \begin
Полученный результат можно записать так (это продолжение равенства (6)):
Из последней скобки видно, что число $-5$ также является корнем данного многочлена. Можно, конечно, формально продолжить схему Горнера, проверив значение $x=-5$, но необходимости в этом нет. Итак,
Числа $-1$, $3$, $-5$ – корни данного многочлена. Причем, так как скобка $(x+1)$ в третьей степени, то $-1$ – корень третьего порядка; так как скобка $(x-3)$ во второй степени, то $3$ – корень второго порядка; так как скобка $(x+5)$ в первой степени, то $x=-5$ – корень первого порядка (простой корень).
Вообще, обычно оформление таких примеров состоит из таблицы, в которой перебираются возможные варианты корней, и ответа:
$$ \begin
Из таблицы следует вывод, полученный нами ранее с подробным решением:
Убедиться, что числа $2$ и $-5$ являются корнями многочлена $3x^6+9x^5-28x^4+6x^3-30x^2-30x+100$. Разделить заданный многочлен на биномы $x-2$ и $x+5$.
Как и ранее, для сокращения записи обозначим заданный многочлен как $P(x)$, т.е.
Степень многочлена $P(x)$ равна $6$. После деления на два заданных бинома степень заданного многочлена уменьшится на $2$, т.е. станет равна $4$.
$$ \begin
Конечно, данный метод подбора малоэффективен в общем случае, когда корни не являются целыми числами, но для целочисленных корней метод довольно-таки неплох.
Вернуться к списку тем
Задать вопрос на форуме
Записаться на занятия
Заметили ошибку, опечатку, или некорректно отобразилась формула? Отпишите, пожалуйста, об этом в данной теме на форуме (регистрация не требуется).
Horner scheme
A method for obtaining the incomplete fraction and the remainder in the division of a polynomial \begin\label f(x) = a_n x^n + a_ x^ + \cdots + a_1 x + a_0 \end by a binomial $x-a$, where all the coefficients $a,a_0,\ldots,a_n$ lie in a certain field, e.g. in the field of complex numbers. Any polynomial $f(x)$ can be uniquely represented in the form $$ f(x) = g(x)(x-a) + r $$ where $g(x) = b_x^ + b_x^ + \cdots + b_0$ is the incomplete fraction, while $r$ is the remainder which, according to the Bezout theorem, equals $f(a)$. The coefficients of $g(x)$ and $r$ are calculated by the recurrence formulas \begin\label \left.< \begin b_ = a_n,\ \ b_ = a_ + a b_,\ \ldots\,,\ b_0 = a_1 + a b_1 \ ; \\ r = a_0 + a b_0 \end >\right\rbrace\ \ . \end
The following table $$ \begin <|c|c|c|c|c|c|>\hline \\ a_n & a_ & \ldots & a_1 & a_0 \\ \hline \\ a & b_ & b_ & \ldots & b_0 \\ \hline \end $$ whose upper line is given, while the lower line is filled in accordance with the formulas \eqref), is used in the computations. In fact, this method is identical with the method of Ch’in Chiu-Shao employed in medieval China. At the beginning of the 19th century it was rediscovered, almost simultaneously, by W.G. Horner [1] and P. Ruffini [1].
References
| [1] | W.G. Horner, Philos. Transact. Roy. Soc. London Ser. A , 1 (1819) pp. 308–335 |
| [2] | P. Ruffini, Mem. Coronata Soc. Ital. Sci. , 9 (1802) pp. 44–526 |
Comments
Horner’s scheme is used for the efficient evaluation of polynomials. The straightforward evaluation of $f(x)$ for a given value $x=a$ by computing the powers $a^2,a^3,\ldots,a^n$ and forming the linear combination according to \eqref would require $2n-1$ multiplications. However, by writing $f(x)$ in the “nested” form $$ f(x) = x(\cdots(x(xa_n + a_) + a_) \cdots)+a_0\,, $$ only $n$ (sequential) multiplications are involved. It is easily verified that using this nested representation the work consists of the computation steps given by \eqref. Since $r=f(a)$, the evaluation of $f(a)$ requires $n$ instead of $2n-1$ multiplications.
References
| [a1] | F.B. Hildebrand, “Introduction to numerical analysis” , McGraw-Hill (1974) |
| [a2] | F. Cajori, “A history of mathematics” , Chelsea, reprint (1980) |
How to Cite This Entry:
Horner scheme. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Horner_scheme&oldid=41987
This article was adapted from an original article by V.N. Remeslennikov (originator), which appeared in Encyclopedia of Mathematics – ISBN 1402006098. See original article
Mühazirə mətnləri. Tərtib edən: b/m S. S. Haxıyev
Bu qiymətləri f (x) =(x – c) q (x) + r bərabərliyində yerinə yazsaq alarıq:
Sol və sağ tərəflərdə uyğun dərəcəli hədlərin əmsallarını bərabərləşdirməklə aşağıdakı bərabərlikləri
Bunu Horner sxemi adlanan aşağıdakı cədvəl vasitəsilə göstərmək olar:
çoxhədlisinin x-3-ə bölünməsindən alınan qisməti və qalığı tapaq:
3. Çoxhədlinin köklərinin maksimal sayı
Teorem. K- tamlıq oblastı üzərində n dərəcəli çoxhədlinin köklərinin sayı n-dən çoz ola bilməz.
İsbatı. İsbatı n-ə görə induksiya ilə aparaq. Əgər deg f = 0 olarsa, f ( ) = olar ki, onun köklərinin
sayı sıfırdır. Teoremin doğruluğunu n üçün qəbul edək, yəni n dərəcəli çoxhədlinin köklərinin sayının
n-dən çox olmadığını qəbul edək. n + 1 dərəcəli f (x) çoxhədlisi götürək. Əgər
köküdürsə, onda Bezu teoreminə əsasən f (x) = (x –
)q (x), belə ki, q (x) –in dərəcəsi n-dir.
Fərziyyəmizə görə, q (x) –in köklərinin sayı n-dən çox ola bilməz. Deməli, n + 1 dərəcəli
çoxhədlisinin köklərinin sayı n + 1-dən çox ola bilməz.
Nəticə. Tamlıq oblastı üzərində n dərəcəli çoxhədlinin köklərinin sayı n-dən çox olarsa, bu çoxhədli
Comments are closed, but trackbacks and pingbacks are open.