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:

    “Everything to which we concede existence is a posit from the standpoint of a description of the theory-building process, and simultaneously real from the standpoint of the theory that is being built. Nor let us look down on the standpoint of the theory as make-believe; for we can never do better than occupy the standpoint of some theory or other, the best we can muster at the time.”
    —Willard Van Orman Quine (b. 1908)

    “Once a child has demonstrated his capacity for independent functioning in any area, his lapses into dependent behavior, even though temporary, make the mother feel that she is being taken advantage of....What only yesterday was a description of the child’s stage in life has become an indictment, a judgment.”
    —Elaine Heffner (20th century)

    “Why does philosophy use concepts and why does faith use symbols if both try to express the same ultimate? The answer, of course, is that the relation to the ultimate is not the same in each case. The philosophical relation is in principle a detached description of the basic structure in which the ultimate manifests itself. The relation of faith is in principle an involved expression of concern about the meaning of the ultimate for the faithful.”
    —Paul Tillich (1886–1965)