fbpx

Horner’s Method

0

Introduction

If you love polynomials, you will love this article. We all know how to evaluate a polynomial at a given point i.e. say you got a polynomial p(x), and you would like to compute p(x_0). Well, it’s a plug-and-play. Just substitute x=x_0 and evaluate. Simple right ? Right. The problem is for a polynomial of degree n, we need \frac{n^2+n}{2} multiplications and n additions. This article introduces you to Horner’s Method, named after William George Horner, which evaluates a polynomial in a fast way. It is economic as Horner’s method requires only n additions and Floor(\frac{n}{2})+2 mutiplications.

Horner’s Method

Let p(x) be a polynomial of degree n as follows

(1)   \begin{equation*}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,\end{equation*}


where a_0, \ldots, a_n are the coefficients of the polynomial p(x). The objective is simple and straightforward: Let us evaluate x at x = x_0.
Horner defines the following sequence:

(2)   \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*}


Therefore b_0 = p(x_0) because note that

(3)   \begin{equation*}p(x) = a_0 + x(a_1 + x(a_2 + \cdots + x(a_{n-1} + a_n x)))\end{equation*}


and hence

(4)   \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))) \\& = a_0 + x_0(a_1 + x_0(a_2 + \cdots + x_0(b_{n-1}))) \\& {} \ \ \vdots \\& = a_0 + x_0(b_1) \\& = b_0.\end{align*}



MATLAB implementation

Next, we present the function HornersMethod.m implements this idea, where input n is the degree of the polynomial p(x), the vector x is an (n+1) \times 1 vector containing coefficients \lbrace a_k \rbrace_{k=0}^n, and t = x_0, the point which we which to find p(x_0) which is the output “out”.

function [out] = HornersMethod(n,x,t)
% initialize first elements=
out = x(1);
% apply Horners at point t for coefficients x of a 
% polynomial of degree n
for j = 2:n
    out = out*t + x(j);
end

Summary

This article demonstrates Horner’s method, as well as its MATLAB implementation. Indeed, Horner’s method is provides efficiency as \mathcal{O}(n) operations is required vs the naive implementation, which needs \mathcal{O}(n^2).

Finally, Subscribe to my channel to support us ! We are very close to 100K subscribers <3 w/ love. The algorithmic chef – Ahmad Bazzi. Click here to subscribe. Check my other articles here.

[paypal_donation_block email=’myprivateotherstuff@gmail.com’ amount=’3.00′ currency=’USD’ size=’large’ purpose=’Buy me coffee ^^’ mode=’live’]

PS: I’m on twitter. I retweet stuff around algorithms, python, MATLAB and mathematical optimization, mostly convex.


matlab code of horner
matlab code of horner