what is horner formula
Answers
Answer:
Given the polynomial
{\displaystyle 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},} 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},
where {\displaystyle a_{0},\ldots ,a_{n}} a_{0},\ldots ,a_{n} are constant coefficients, we wish to evaluate the polynomial at a specific value of {\displaystyle x} x that we'll call {\displaystyle x_{0}} x_{0}.
To accomplish this, we define a new sequence of constants as follows:
{\displaystyle {\begin{aligned}b_{n}&:=a_{n}\\b_{n-1}&:=a_{n-1}+b_{n}x_{0}\\b_{n-2}&:=a_{n-2}+b_{n-1}x_{0}\\&~~~\vdots \\b_{0}&:=a_{0}+b_{1}x_{0}.\end{aligned}}} {\displaystyle {\begin{aligned}b_{n}&:=a_{n}\\b_{n-1}&:=a_{n-1}+b_{n}x_{0}\\b_{n-2}&:=a_{n-2}+b_{n-1}x_{0}\\&~~~\vdots \\b_{0}&:=a_{0}+b_{1}x_{0}.\end{aligned}}}
Then {\displaystyle b_{0}} b_{0} is the value of {\displaystyle p(x_{0})} p(x_{0}).
To see why this works, note that the polynomial can be written in the form
{\displaystyle p(x)=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 )}\ .} {\displaystyle p(x)=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 )}\ .}
Thus, by iteratively substituting the {\displaystyle b_{i}} b_{i} into the expression,
{\displaystyle {\begin{aligned}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}}} {\displaystyle {\begin{aligned}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}}}