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)

“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)

“A sound mind in a sound body, is a short, but full description of a happy state in this World: he that has these two, has little more to wish for; and he that wants either of them, will be little the better for anything else.”
—John Locke (1632–1704)