Horner's Method - Description of The Algorithm

Description of The Algorithm

Given the polynomial

where are real numbers, we wish to evaluate the polynomial at a specific value of, say .

To accomplish this, we define a new sequence of constants as follows:

\begin{align}
b_n & := a_n \\
b_{n-1} & := a_{n-1} + b_n x_0 \\
& {}\ \ \vdots \\
b_0 & := a_0 + b_1 x_0.
\end{align}

Then is the value of .

To see why this works, note that the polynomial can be written in the form

Thus, by iteratively substituting the into the expression,


\begin{align}
p(x_0) & = a_0 + x_0(a_1 + x_0(a_2 + \cdots + x_0(a_{n-1} + b_n x_0)\cdots)) \\
& = a_0 + x_0(a_1 + x_0(a_2 + \cdots + x_0(b_{n-1})\cdots)) \\
& {} \ \ \vdots \\
& = a_0 + x_0(b_1) \\
& = b_0.
\end{align}

Read more about this topic:  Horner's Method

Famous quotes containing the words description of the, description of and/or description:

    The next Augustan age will dawn on the other side of the Atlantic. There will, perhaps, be a Thucydides at Boston, a Xenophon at New York, and, in time, a Virgil at Mexico, and a Newton at Peru. At last, some curious traveller from Lima will visit England and give a description of the ruins of St. Paul’s, like the editions of Balbec and Palmyra.
    Horace Walpole (1717–1797)

    Do not require a description of the countries towards which you sail. The description does not describe them to you, and to- morrow you arrive there, and know them by inhabiting them.
    Ralph Waldo Emerson (1803–1882)

    The type of fig leaf which each culture employs to cover its social taboos offers a twofold description of its morality. It reveals that certain unacknowledged behavior exists and it suggests the form that such behavior takes.
    Freda Adler (b. 1934)