Metode Horner

Dalam matematika dan ilmu komputer, metode Horner (atau skema Horner) adalah algoritma untuk evaluasi polinomial. 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. Setelah pengenalan komputer, algoritma ini menjadi dasar untuk komputasi secara efisien dengan polinomial.

Algoritma ini didasarkan pada aturan Horner:

{\begin{aligned}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. Ini optimal, karena ada polinomial berderajat n yang tidak dapat dievaluasi dengan operasi aritmatika yang lebih sedikit.^[1]

Atau, metode Horner juga mengacu pada metode untuk mendekati akar polinomial, dijelaskan oleh Horner pada tahun 1819. Ini adalah varian dari metode Newton-Raphson yang dibuat lebih efisien untuk perhitungan tangan dengan penerapan aturan Horner. Itu banyak digunakan sampai komputer mulai digunakan secara umum sekitar tahun 1970.

Referensi

^ Pan 1966.

Pranala luar

Wikibooks Algorithm Implementation memiliki halaman di:

Polynomial evaluation

Hazewinkel, Michiel, ed. (2001) [1994], "Horner scheme", Encyclopedia of Mathematics, Springer Science+Business Media B.V. / Kluwer Academic Publishers, ISBN 978-1-55608-010-4
Qiu Jin-Shao, Shu Shu Jiu Zhang (Cong Shu Ji Cheng ed.)
For more on the root-finding application see [1]