Estimating Roots via Bisection Search and Newton-Rhapson Method

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

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.

To estimate the root of a function using the Newton-Rhapson 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-Rhapson 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-Rhapson 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.$


Practice Problems


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-Rhapson method. (This should match up against the provided example and continue for more iterations.)
  3. Write a function calc_root_via_bisection(a, n, precision) that approximates $\sqrt[n]{a}$ to the desired level of precision using bisection search.
  4. Write a function calc_root_via_newton_rhapson(a, n, precision) that approximates $\sqrt[n]{a}$ to the desired level of precision using the Newton-Rhapson method.

Leave a Comment