In mathematics and computer science, Horner's method (or Horner's scheme) is an algorithm for polynomial evaluation.
Dalam matematika dan ilmu komputer, metode Horner (atau skema Horner) adalah algoritma untuk evaluasi polinomial.
It is named after William George Horner, although it is much older, attributed by Horner to Joseph-Louis Lagrange, and was discovered hundreds of years earlier by Chinese and Persian mathematicians.
Meskipun dinamai William George Horner, metode ini jauh lebih tua, karena telah dikaitkan dengan Joseph-Louis Lagrange oleh Horner sendiri, dan dapat ditelusuri kembali ratusan tahun ke matematikawan Cina dan Persia.
After the introduction of computers, this algorithm became fundamental for computing efficiently with polynomials.
Setelah pengenalan komputer, algoritma ini menjadi dasar untuk komputasi secara efisien dengan polinomial.
The algorithm is based on Horner's rule, in which a polynomial is written in nested form: a 0 + a 1 x + a 2 x 2 + a 3 x 3 + ⋯ + a n x na 0 + x ( a 1 + x ( a 2 + x ( a 3 + ⋯ + x ( a n − 1 + x a n )
Algoritma ini didasarkan pada aturan Horner: a 0 + a 1 x + a 2 x 2 + a 3 x 3 + ⋯ + a n x na 0 + x ( a 1 + x ( a 2 + x ( a 3 + ⋯ + x ( a n − 1 + x a n )
&a_{0}+a_{1}x+a_{2}x^{2}+a_{3}x^{3}+\cdots +a_{n}x^{n}\\={}&a_{0}+x{\bigg (}a_{1}+x{\Big (}a_{2}+x{\big (}a_{3}+\cdots +x(a_{n-1}+x\,a_{n})\cdots {\big )}{\Big )}{\bigg )}.\end{aligned}}} This allows the evaluation of a polynomial of degree n with only n multiplications and n additions.
a_{0}&+a_{1}x+a_{2}x^{2}+a_{3}x^{3}+\cdots +a_{n}x^{n}\\&=a_{0}+x{\bigg (}a_{1}+x{\Big (}a_{2}+x{\big (}a_{3}+\cdots +x(a_{n-1}+x\,a_{n})\cdots {\big )}{\Big )}{\bigg )}.\end{aligned}}} Hal ini memungkinkan evaluasi polinomial derajat n dengan hanya n perkalian dan n tambahan.
This is optimal, since there are polynomials of degree n that cannot be evaluated with fewer arithmetic operations.
Ini optimal, karena ada polinomial berderajat n yang tidak dapat dievaluasi dengan operasi aritmetika yang lebih sedikit.
Horner's method and Horner–Ruffini method also refers to a method for approximating the roots of polynomials, described by Horner in 1819.
Atau, metode Horner juga mengacu pada metode untuk mendekati akar polinomial, dijelaskan oleh Horner pada tahun 1819.
It is a variant of the Newton–Raphson method made more efficient for hand calculation by application of Horner's rule.
Ini adalah varian dari metode Newton-Raphson yang dibuat lebih efisien untuk perhitungan tangan dengan penerapan aturan Horner.
It was widely used until computers came into general use around 1970.
Itu banyak digunakan sampai komputer mulai digunakan secara umum sekitar tahun 1970.
p(x_{0})&=a_{0}+x_{0}{\Big (}a_{1}+x_{0}{\big (}a_{2}+\cdots +x_{0}(a_{n-1}+b_{n}x_{0})\cdots {\big )}{\Big )}\\&=a_{0}+x_{0}{\Big (}a_{1}+x_{0}{\big (}a_{2}+\cdots +x_{0}b_{n-1}{\big )}{\Big )}\\&~~\vdots \\&=a_{0}+x_{0}b_{1}\\&=b_{0}.\end{aligned}}} Similarly, it can be shown that: Suggesting a convenient procedure for determining the result of the polynomial division p ( x ) / ( x − x 0 ) )} with b 0 } (which is equal to p ( x 0 ) )} ) being the division's remainder.
a_{0}&+a_{1}x+a_{2}x^{2}+a_{3}x^{3}+\cdots +a_{n}x^{n}\\&=a_{0}+x{\bigg (}a_{1}+x{\Big (}a_{2}+x{\big (}a_{3}+\cdots +x(a_{n-1}+x\,a_{n})\cdots {\big )}{\Big )}{\bigg )}.\end{aligned}}} Hal ini memungkinkan evaluasi polinomial derajat n dengan hanya n perkalian dan n tambahan.
p(x)&=\sum _{i=0}^{n}a_{i}x^{i}\\[1ex]&=a_{0}+a_{1}x+a_{2}x^{2}+a_{3}x^{3}+\cdots +a_{n}x^{n}\\[1ex]&=\left(a_{0}+a_{2}x^{2}+a_{4}x^{4}+\cdots \right)+\left(a_{1}x+a_{3}x^{3}+a_{5}x^{5}+\cdots \right)\\[1ex]&=\left(a_{0}+a_{2}x^{2}+a_{4}x^{4}+\cdots \right)+x\left(a_{1}+a_{3}x^{2}+a_{5}x^{4}+\cdots \right)\\[1ex]&=\sum _{i=0}^{\lfloor n/2\rfloor }a_{2i}x^{2i}+x\sum _{i=0}^{\lfloor n/2\rfloor }a_{2i+1}x^{2i}\\[1ex]&=p_{0}(x^{2})+xp_{1}(x^{2}).\end{aligned}}} More generally, the summation can be broken into k parts: p ( x )
a_{0}&+a_{1}x+a_{2}x^{2}+a_{3}x^{3}+\cdots +a_{n}x^{n}\\&=a_{0}+x{\bigg (}a_{1}+x{\Big (}a_{2}+x{\big (}a_{3}+\cdots +x(a_{n-1}+x\,a_{n})\cdots {\big )}{\Big )}{\bigg )}.\end{aligned}}} Hal ini memungkinkan evaluasi polinomial derajat n dengan hanya n perkalian dan n tambahan.
More on the root-finding application
For more on the root-finding application see [1]