Root Finding Algorithms

• Every algebraic equation of the form
  Can be translated to the problem of finding the zeros of a function. Namely find all such that

Bisection Method §

• One approach to root finding is the Bisection Method. ¹ Suppose the solution to exists in the interval .
  • Assume: is continuous in the interval.
  • Check if and have opposite signs and use the Intermediate Value Theorem
    • If , then the root is somewhere in the interval.
    • Otherwise , the root might be in the interval, we must sample the interval until we find an interval where (or until we reach the maximum number of iterations).
  • With the check done, We assume that . We do the following per iteration (up until we reach the maximum iteration)
    • Calculate the midpoint
    • If or if is close enough to .
    • Update with the following rule

• This method works because we cut down the interval search space while ensuring that the endpoints of the interval satisfy the Intermediate Value Theorem (i.e., they contain the root).

• The bisection method only works if .

• The bisection method is not guaranteed to find the root of any arbitrary function. For example take any such that while also containing the root in the interval.

• (Sullivan 2.2) Convergence Rate of the Bisection Method. If is a continuous function with a root in the interval and the bisection method is used for root finding, then:

  • The error between the actual root and the approximate root will decrease by a factor of at every iteration. That is for iterations the approximation error turns out to be.

    The convergence rate is therefore

    In fact, it is a first order approximation. That is. Specifically

  • If we want the approximate root to be within tolerance , then we should do at most

    Iterations

Regula-Falsi Method §

• The Regula Falsi Method [^regula_false] involves trial and error. We test potential roots and then adjust the test value according to the outcome

• In particular, suppose we have the interval . Assume like in the Bisection Method that

  • Consider is the secant line passing through and .
    Choose to be the -intercept of this line calculated as
  • The calculation above has a computational advantage since the numerator and denominator are effectively “additions” which do not lose significant digits unlike subtraction.
  • The algorithm proceeds like the Bisection method except with the choice of above.

• This method works for the same reasons as the Bisection Method. It is simply that we choose a better point than the middle of the interval since, if is approximately linear, the root need not be at the midpoint of this interval.

• The main pitfall of Regula Falsi is mainly that the interval being considered does not tend to zero unless the function is nearly linear at the zero. As a result, it may converge slowly or stagnate.

• For close-to-linear functions, Regula Falsi performs faster than bisection. In particular, it is a first order approximation method

• The number of iterations to converge is dependent on the function. As such, there is no number of iterations that guarantee convergence.

Newton’s Method §

• Newton’s Method involves using derivatives and in particular tangent lines to find the root.

• We begin with an initial guess for the root . We assume the function is differentiable.

• The algorithm proceeds as follows. Let be the approximate root at the -th iteration.

  • Calculate the slope at the -th guess using .
  • Calculate the intercept of the tangent line. This becomes

• Convergence is guaranteed as long as the initial guess is close to the zero.

• However, this method fails when:

  • is not differentiable at the interval specified (or it is not differentiable at the root itself)
  • The initial guess is too far from the actual zero.
  • or its derivative are too computationally expensive (this is more of a concern for time complexity.)
  • is significantly large or small ² or equals zero.

• Newton’s Method is a second order approximation method.
  • Proof: We have the following relation between and from the formula of Newton’s Method
    We use the Taylor Series about the root to compute and . It is easy to show that this gives us
    Also note that
    Now substituting we get
    Note the rightmost term is a geometric form which converges provided . We can substitute this form to obtain the desired bounds as
    Taking absolute values gives us

Secant Method §

• The Secant Method aims to relax Newton’s Method. In particular, we avoid using the derivative which could be cumbersome to compute (if not impossible).

• Rather than use tangent lines to approximate the curve, we use secant lines (approximately tangent).

• We assume that is continuous. Start with guesses that are near the root and respectively.

  • Like the bisection method, we can apply the Intermediate Value Theorem to get a heuristic, that .

• We use the following approximation for the derivative

• We use the approximation as we would in Newton’s Method

• The secant method has a super-linear order of convergence. In fact the order of convergence is the golden ratio.

  • Proof: The proof proceeds similarly to that of Newton’s Method. Let be the root. From the recurrent form of the Secant Method we can observe the following
    And using the Taylor Series centered around the root, we can get
    By substitution and using the Taylor series for the geometric sum we get
    The terms after the first term are smaller. Taking absolute values means we get the recurrence relation
    We can solve the above using the Ansatz method. In particular using the Ansatz . It can be shown that this gives us
    Importantly, if we equate coefficients and powers we have the following

Topics §

• Numerical Methods — An Inquiry Based Approach with Python by Sullivan
• Root Finding Order of Convergence - fills in the proofs for Newton’s Method and the Secant Method

Footnotes §

1. Note the similarities with this and Binary Search ↩

2. Similar to Vanishing and Exploding Gradients. ↩