Формула на Хорнер

Формула на Хорнер, още известна като Схема на Хорнер или Правило на Хорнер е алгоритъм за изчисляване на полиноми, който се състои от трансформирането на полинома с цел залагането му на множители. Този метод е кръстен на британския математик Уилям Джордж Хорнър, въпреки че е бил известен преди него на Паоло Руфини, както и шестстотин години по-рано, на китайския математик Чин Жиушао.

Същност

Имайки полинома:

$p(x)=\sum _{i=0}^{n}a_{i}x^{i}=a_{0}+a_{1}x+a_{2}x^{2}+a_{3}x^{3}+\cdots +a_{n}x^{n},$

където $a_{0},\ldots ,a_{n}$ са реални числа, искаме да изчислим полинома за специална стойност на $x$, нека е $x_{0}$.

За да го направим, полагаме:

${\begin{aligned}b_{n}&:=a_{n}\\b_{n-1}&:=a_{n-1}+b_{n}x_{0}\\&{}\ \ \vdots \\b_{0}&:=a_{0}+b_{1}x_{0}.\end{aligned}}$

Тогава $b_{0}$ е стойността на $p(x_{0})$.

Това се получава, като запишем полинома в такъв вид:

$p(x)=a_{0}+x(a_{1}+x(a_{2}+\cdots +x(a_{n-1}+a_{n}x))).\,$

След това, замествайки с $b_{i}$ се получава,

${\begin{aligned}p(x_{0})&=a_{0}+x_{0}(a_{1}+x_{0}(a_{2}+\cdots +x_{0}(a_{n-1}+b_{n}x_{0})))\\&=a_{0}+x_{0}(a_{1}+x_{0}(a_{2}+\cdots +x_{0}(b_{n-1})))\\&{}\ \ \vdots \\&=a_{0}+x_{0}(b_{1})\\&=b_{0}.\end{aligned}}$

Използване на схема на Хорнер за разлагане на многочлен на бином

При делението на многочлена $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}+cb_{k-1}$.

По същия начин, може да се определи кратността на корените (използва се схема на Хорнер за нов полином). Можете също да използвате схемата за намиране на коефициентите чрез разлагането на полинома с $(x-c)$:

$P(x)=A_{0}+A_{1}(x-c)+A_{2}(x-c)^{2}+\cdots +A_{n}(x-c)^{n}$

Пример 1

Пресметнете $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

Числата от третия ред да сумите от тези в първите два. Всяко число от втория ред е произведението от стойността на х (в случая 3) с числата от ляво от третия ред. Числата от първия ред са коефициентите на полинома. Остатъкът на$f(x)$ при деление на $x-3$ е 5.

По теорема знаем, че остатъка е равен на $f(3)$. Следователно $f(3)=5$

В този пример, ако $a_{3}=2,a_{2}=-6,a_{1}=2,a_{0}=-1$ виждаме, че $b_{3}=2,b_{2}=0,b_{1}=2,b_{0}=5$, числата от третия ред.

Пример 2

Разложете $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

Третият ред е сумата от другите два реда, разделена на 2. Всяко число от втория ред е произведението на 1 с числото от ляво на третия ред. Отговорът е:

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

Източници

• Berggren, J. L. Innovation and Tradition in Sharaf al-Din al-Tusi's Muadalat. // Journal of the American Oriental Society 110 (2). 1990. DOI:10.2307/604533.
• Cajori, Florian. Horner's method of approximation anticipated by Ruffini. // Bulletin of the American Mathematical Society 17. 1911. с. 409–414. Read before the Southwestern Section of the American Mathematical Society on November 26, 1910.
• Cormen, Thomas H., Leiserson, Charles E., Rivest, Ronald L. Introduction to Algorithms. 3rd. MIT Press, 2009.
• Fuller, A. T. Horner versus Holdred: An Episode in the History of Root Computation. // Historia Mathematica 26. 1999.
• Higham, Nicholas. Accuracy and Stability of Numerical Algorithms. SIAM, 2002. ISBN 0-89871-521-0.
• Holdred, T. A New Method of Solving Equations with Ease and Expedition; by which the True Value of the Unknown Quantity is Found Without Previous Reduction. With a Supplement, Containing Two Other Methods of Solving Equations, Derived from the Same Principle. Richard Watts, 1820. Архив на оригинала от 2014-01-06 в Wayback Machine.

  Holdred's method is in the supplement following page numbered 45 (which is the 52nd page of the pdf version).

• Horner, William George. A new method of solving numerical equations of all orders, by continuous approximation. // Philosophical Transactions. Royal Society of London, July 1819. с. pp. 308–335. Архивиран от оригинала на 2014-02-22. Посетен на 2017-03-22.

  Directly available online via the link, but also reprinted with appraisal in D.E. Smith: A Source Book in Mathematics, McGraw-Hill, 1929; Dover reprint, 2 vols, 1959.

• Knuth, Donald. The Art of Computer Programming. 3rd. Т. Vol. 2: Seminumerical Algorithms. Addison-Wesley, 1997. ISBN 0-201-89684-2. с. 486–488 in section 4.6.4.
• Kress, Rainer. Numerical Analysis. Springer, 1991.
• Kripasagar, Venkat. Efficient Micro Mathematics – Multiplication and Division Techniques for MCUs. // Circuit Cellar magazine (212). March 2008.
• Libbrecht, Ulrich. Chapter 13. // Chinese Mathematics in the Thirteenth Century. 2nd. Dover, 2005. ISBN 0-486-44619-0. Архив на оригинала от 2017-06-06 в Wayback Machine.
• Mikami, Yoshio. Chapter 11. Ch'in Chiu-Shao. // The Development of Mathematics in China and Japan. 1st. Chelsea Publishing Co reprint, 1913. с. 74 – 77.
• Ostrowski, Alexander M. On two problems in abstract algebra connected with Horner's rule. // Studies in Mathematics and Mechanics presented to Richard von Mises. Academic Press, 1954. ISBN 978-1-4832-3272-0. с. 40 – 48.
• Pan, Y. Ja. On means of calculating values of polynomials. // Russian Math. Surveys 21. 1966. DOI:10.1070/rm1966v021n01abeh004147. с. 105 – 136.
• Pankiewicz, W. Algorithm 337: calculation of a polynomial and its derivative values by Horner scheme. // Communications of the ACM 11 (9). ACM, 1968. с. 633.
• Spiegel, Murray R. Schaum's Outline of Theory and Problems of College Algebra. McGraw-Hill, 1956.
• Temple, Robert. The Genius of China: 3,000 Years of Science, Discovery, and Invention. Simon and Schuster, 1986. ISBN 0-671-62028-2.
• Whittaker, E.T., Robinson, G. The Calculus of Observations. London, Blackie, 1924.
• Wylie, Alexander. Jottings on the Science of Chinese Arithmetic. // Chinese Researches. Shanghai, 1897. с. 159 – 194.