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

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

Методът на Хорнер се описва чрез приложенията му: изчисляване на многочлени и разлагането им с бином.

Изчисляване на многочлен

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

$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}}$

Пример

Да се пресметне $f(x)=2x^{3}-6x^{2}+2x-1\,$ за $x=3.\;$

Използва се методът на синтезирано деление, базиран на схемата на Хорнер, както следва:

  │ x³  x²  x¹  x⁰          │ x³  x²  x¹  x⁰
x₀│ a0  a1  a2  a3          3│ 2  −6   2  −1
  │ k0  k1  k2  k3           │     6   0   6  
  └───────────────          └───────────────
    b0  b1  b2  b3             2   0   2   5

На първия ред са означени степените на аргумента $x$. Числата от втория ред са стойността на $x$, означена с $x_{0}$, и коефициентите на полинома: $a_{0}=2,a_{1}=-6,a_{2}=2,a_{3}=-1$. Третият и четвърият ред се попълват паралелно, започвайки отляво с празна позиция ($k_{0}=0$) на третия ред. Числата от четвърия ред са сумите съответните числа във втория и третия ред $b_{i}=a_{i}+k_{i}$. Всяко следващо число от третия ред е произведение от числото вляво от него от четвърия ред по стойността на $x$ (в случая 3): $k_{i}=x_{0}.b_{i-1}$ за $i>0$. Така последователно се получава: $b_{0}=a_{0}+k_{0}=2+0=2$, $k_{1}=x_{0}.b_{0}=3.2=6$;
$b_{1}=a_{1}+k_{1}=-6+6=0$, $k_{2}=x_{0}.b_{1}=3.0=0$;
$b_{2}=a_{2}+k_{2}=2+0=2$, $k_{3}=x_{0}.b_{2}=3.2=6$.
$b_{3}=a_{3}+k_{3}=-6+1=5$. Остатъкът на$f(x)$ при деление на $x-3$ е 5.

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

Разлагане на многочлен с бином

Зададеният бином може да участва в разложението като множител или знаменател на остатък.

При делението на многочлена $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. Да се разложи многочленът $x^{3}-6x^{2}+11x-6\,$ на $x-2\,$:

x₀│ x³  x²  x¹  x⁰
2 │ 1  -6  11  -6
  │ 2  -8   6
  └────────────────
    1  -4   3   0

Получава се квадратният тричлен $x^{2}-4x+3\,$. Многочленът се разлага на множители във вида $x^{3}-6x^{2}+11x-6=(x-2)(x^{2}-4x+3)$.

2. Нека $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.