Estimating Roots via Bisection Search and Newton-Raphson Method

by Justin Skycak (@justinskycak) on

Bisection search involves repeatedly moving one bound halfway to the other. The Newton-Raphson method involves repeatedly moving our guess to the root of the tangent line.

This post is part of the book Introduction to Algorithms and Machine Learning: from Sorting to Strategic Agents. Suggested citation: Skycak, J. (2021). Estimating Roots via Bisection Search and Newton-Raphson Method. In Introduction to Algorithms and Machine Learning: from Sorting to Strategic Agents. https://justinmath.com/estimating-roots-via-bisection-search-and-newton-raphson-method/

Want to get notified about new posts? Join the mailing list and follow on X/Twitter.

Two of the simplest methods for estimating roots of functions are bisection search and the Newton-Raphson method. We will cover both of these here.

Bisection Search

To estimate the root of a function using bisection search, we start with a lower bound and an upper bound and then repeatedly move one bound halfway to the other.

Let’s use bisection search to approximate the value of $\sqrt[3]{2}$ by approximating the root of the function $f(x) = x^3 - 2.$ We’ll use $x=1$ as the lower bound and $x=3$ as the upper bound since $f(1) < 0 < f(3).$ Note that the function values are positive to the right of the root and negative to the left of the root.

  1. Our bounds are $[1,3]$ and the midpoint $2.$ Since $f(2) = 6 > 0,$ we know that $2$ is bigger than the root. So, we use $2$ as our new upper bound.
  2. Our bounds are $[1,2]$ and the midpoint $1.5.$ Since $f(1.5) = 1.375 > 0,$ we know that $1.5$ is bigger than the root. So, we use $1.5$ as our new upper bound.
  3. Our bounds are $[1,1.5]$ and the midpoint is $1.25.$ Since $f(1.25) = -0.046875 < 0,$ we know that $1.25$ is smaller than the root. So, we use $1.25$ as our new lower bound.
  4. Our bounds are $[1.25,1.5]$ and the midpoint is $1.375.$ Since $f(1.375) \approx 0.599609 > 0,$ we know that $1.375$ is bigger than the root. So, we use $1.375$ as our new upper bound.

Our next bounds are $[1.25,1.375],$ which tells us that $\sqrt[3]{2}$ is between $1.25$ and $1.375.$ Our best guess is the midpoint, $1.3125,$ and the precision of our guess (i.e. the maximum amount we can be off by) is the distance from the midpoint to the bounds. In our case, the precision is $0.0625.$ We can keep on repeating the bisection procedure until our guess is as precise as we want.

Newton-Raphson Method

To estimate the root of a function using the Newton-Raphson method, we start with an initial guess and then repeatedly update our guess to be the root of the tangent line to the function.

To illustrate, let’s again approximate the value of $\sqrt[3]{2}$ by approximating the root of the function $f(x) = x^3 - 2.$ We’ll use $x=2$ as our initial guess. Remember that the slope of the tangent line is given by the derivative, which in this case is $f’(x) = 3x^2.$

  1. Our guess is $x=2.$ The function value is $f(2) = 6$ and the slope of the tangent line is $f'(2) = 12,$ so the tangent line is given by $y - 6 = 12(x - 2).$ The root of this tangent line is obtained by solving the equation $0 - 6 = 12(x - 2),$ which gives us $x=1.5.$
  2. Our guess is $x=1.5.$ The function value is $f(1.5) = 1.375$ and the slope of the tangent line is $f'(1.5) = 6.75,$ so the tangent line is given by $y - 1.375 = 6.75(x - 1.5).$ The root of this tangent line is obtained by solving the equation $0 - 1.375 = 6.75(x - 1.5),$ which gives us $x \approx 1.2963.$

Our next guess would be $x = 1.2963.$ Note that this is rounded to $4$ decimal places, but we wouldn’t actually round this number in our computer program. We can keep on repeating the Newton-Raphson procedure until our guesses converge, i.e. stay the same when rounded to the desired number of decimal places.

Lastly, note that to implement the Newton-Raphson procedure, it’s necessary to come up with a formula for the root of the tangent line. If the tangent line is $y - y_0 = m(x - x_0),$ then the root is the value of $x$ that solves the equation $0 - y_0 = m(x - x_0).$ You can find this value of $x$ in terms of the other variables $x_0,$ $y_0,$ and $m.$

Exercises

As usual, be sure to include a variety of tests.

  1. Write a script that approximates $\sqrt[3]{2}$ to a precision of $6$ decimal places using bisection search. (This should match up against the provided example and continue for more iterations.)
  2. Write a script that approximates $\sqrt[3]{2}$ to a precision of $6$ decimal places using the Newton-Raphson method. (This should match up against the provided example and continue for more iterations.)
  3. Write a function calc_root_bisection(a, n, precision) that approximates $\sqrt[n]{a}$ to the desired level of precision using bisection search.
  4. Write a function calc_root_newton_raphson(a, n, precision) that approximates $\sqrt[n]{a}$ to the desired level of precision using the Newton-Raphson method.

This post is part of the book Introduction to Algorithms and Machine Learning: from Sorting to Strategic Agents. Suggested citation: Skycak, J. (2021). Estimating Roots via Bisection Search and Newton-Raphson Method. In Introduction to Algorithms and Machine Learning: from Sorting to Strategic Agents. https://justinmath.com/estimating-roots-via-bisection-search-and-newton-raphson-method/


Want to get notified about new posts? Join the mailing list and follow on X/Twitter.