Схема Горнера

Возьмем произвольно полином [math]\displaystyle{ f(x)=a_{0} x^{n} +a_{1} x^{n-1} +...+a_{n-1} x+a_{n} }[/math]. Пусть $f(x)=(x-c)q(x)+r$, где $r=const$. Ясно, что $q(x)=b_{0} x^{n-1} +b_{1} x^{n-2} +...+b_{n-2} x+b_{n-1} $. Тогда для определения остатка $r$ и коэффициентов $b_{k},$ $k=\overline{0,n-1}$ имеем очевидное соотношение \begin{equation} a_{0} x^{n} +a_{1} x^{n-1} +...+a_{n-1} x+a_{n} = (x-c)(b_{0} x^{n-1} +b_{1} x^{n-2} +...+b_{n-2} x+b_{n-1} )+r. \end{equation}

Сравнивая коэффициенты полиномов при одинаковых степенях $x$, имеем \begin{equation} a_{0} = b_{0}, a_{k} =b_{k} - b_{k-1} c, k=\overline{1,n-1}, a_{n} = r-b_{n-1} c, \end{equation} поэтому окончательно получаем схему Горнера \begin{equation} b_{0} = a_{0}, b_{k} = a_{k} +b_{k-1} c, k=\overline{1,n-1}, r=a_{n} +b_{n-1} c. \end{equation}