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:

${\displaystyle {\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 ${\displaystyle n}$ perkalian dan ${\displaystyle n}$ tambahan. Ini optimal, karena ada polinomial berderajat n yang tidak dapat dievaluasi dengan operasi aritmetika 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.