<jupyter_start><jupyter_text>Horner's MethodWhat is the best way to evaluate \\[ f(x) = x^3 + 4x^2 - 10 \\]at $ x = \dfrac{1}{2} $? The traditional and direct approach is\\[ f(\dfrac{1}{2}) = \dfrac{1}{2} * \dfrac{1}{2} * \dfrac{1}{2} + 4 * \dfrac{1}{2} * \dfrac{1}{2} - 10 \\]This procedure takes 4 multiplications and 2 additions where a subtraction can be interpreted as adding a negative number. All together it takes 6 operations to evaluate the function. Is there a way to reduce the number of operations? Rewrite the polynomial in such a way the variable $x$ is factored out: \begin{align}f(x) & = -10 + 4x^2 + x^3 \\ & = -10 + x * (0 + 4x + x^2 ) \\ & = -10 + x * (0 + x * (4 + x))\end{align}As you can see, it takes a total of 5 operations to evaluate the function; 3 additions and 2 multiplications. This method is called **Horner's Method**.The point of this notebook is to check the absolute error and relative error and to test the efficiency of using Horner's Method for numerical computations. In this case, we explore its application to find the root of the equation using Bisection Method.  Absolute and Relative ErrorTo calculate the error between the two functions we need to find the absolute and the relative error where $x^*$ is the approximate function and $x$ is the true function.**Absolute Error** $= |x^* - x| $**Relative Error** $= \dfrac{|x^* - x|}{|x|} $<jupyter_code>def error_analysis(true_fx, approx_fx):
    absolute_error = abs(approx_fx - true_fx)
    relative_error = absolute_error / abs(true_fx)
    return absolute_error, relative_error<jupyter_output><empty_output><jupyter_text>True Function - Naive Method<jupyter_code>def f(x):
    return (x ** 3) + (4 * (x ** 2)) - 10<jupyter_output><empty_output><jupyter_text>Approximate Function - Horner's Method<jupyter_code>def f_a(x):
    return -10 + 𝑥 * (0 + 𝑥 * (4 + 𝑥))<jupyter_output><empty_output><jupyter_text>Bisection MethodBisection method is a root-finding algorithm based from the intermediate-value theorem from calculus.You need to verify if a root exist by making sure the two endpoints of the interval $ [a,b] $ or $\{f(a),f(b)\}$ have different signs. If function $ f $ is continuous, then there will be a root $r$ between $a$ and $b$ such that $f(r) = 0$ and $a < r < b$.<jupyter_code>import numpy as np
def bisection_method(a,b):
    if f(a) * f(b) < 0: 
        roots = []
        while (b - a) / 2 > 1e-7:
            c = (a + b) / 2          
            if f(a) * f(c) < 0:
                b = c
            else:
                a = c
            roots.append(c)
    return np.array(roots)
%%timeit
roots = bisection_method(1,2)
roots = bisection_method(1,2)
def bisection_method_hm(a,b):
    if f_a(a) * f_a(b) < 0: 
        roots = []
        while (b - a) / 2 > 1e-7:
            c = (a + b) / 2          
            if f_a(a) * f_a(c) < 0:
                b = c
            else:
                a = c
            roots.append(c)
    return np.array(roots)
%%timeit
roots_a = bisection_method_hm(1,2)
roots_a = bisection_method(1,2)<jupyter_output><empty_output><jupyter_text>According to the benchmark an implementation of the Horner's Method perform faster than the naive method. Now let us look at the error analysis to find out whether results are different on a precision level.<jupyter_code>absolute_error, relative_error = error_analysis(roots, roots_a)
absolute_error
relative_error<jupyter_output><empty_output><jupyter_text>Luckily errors were not found in this example, however polynomials should always be expressed in the nested form before performing an evaluation, because this form minimizes the number of arithmetic calculations, as a result, the errors are reduced. The example \begin{align}f(x) & = -10 + 4x^2 + x^3 \\ & = -10 + x * (0 + 4x + x^2 ) \\ & = -10 + x * (0 + x * (4 + x))\end{align}has already placed the coefficients and the variables in the rightful place. Notice we placed an additional coefficient $0$ to fill-in the missing degree.  Evaluation using Horner's MethodAs an engineer we can write an algorithm to evaluate `x` given only the `degree` (or the number of terms in a polynomial) and its `coefficients`. This way we don't have to rewrite a function everytime a new polynomial is introduced.Consider the following polynomial $ P(x) = a_{k}x^{k} + a_{k-1}x^{k-1} + a_{k-2}x^{k-2} + ... + a_{1}x + a_{0} $ we can evaluate `x` using this algorithm below.<jupyter_code>def evaluate(x, k, c, b=None):
    '''
    Evaluate `x` from a polynomial using Horner's Method.

    Parameters
    ----------
    x : int or float
            The value of x
    k : int
            degrees or the number of terms
    c : int or float
            coefficients
    b : int or float
            base points

    Returns
    -------
    y : int or float
            The output of the polynomial
    '''
    y = c[0]
    if b is None:
        for i in range(1, k):
            y = c[i] + (x * y)
    else:
        for i in range(1, k):
            y = (y * (x - b[i])) + c[i]
    return y
%%timeit
evaluate(2, 4, [1, 4, 0, -10])
%%timeit
f_a(2)
%%timeit
f(2)<jupyter_output>581 ns ± 9.06 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
StarcoderdataJupyterStructuredCleanDedup