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 Sage of Toronto ... spent several decades marveling at the numerous freedoms created by a “global village” instantly and effortlessly accessible to all. Villages, unlike towns, have always been ruled by conformism, isolation, petty surveillance, boredom and repetitive malicious gossip about the same families. Which is a precise enough description of the global spectacle’s present vulgarity.”
—Guy Debord (b. 1931)

“Whose are the truly labored sentences? From the weak and flimsy periods of the politician and literary man, we are glad to turn even to the description of work, the simple record of the month’s labor in the farmer’s almanac, to restore our tone and spirits.”
—Henry David Thoreau (1817–1862)