# Estimating Roots via Bisection Search and Newton-Raphson Method

*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 a chapter in 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. *Introduction to Algorithms and Machine Learning: from Sorting to Strategic Agents.* https://justinmath.com/estimating-roots-via-bisection-search-and-newton-raphson-method/

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.

- 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.
- 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.
- 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.
- 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.$

- 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.$
- 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.

- 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.)
- 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.)
- Write a function
`calc_root_bisection(a, n, precision)`

that approximates $\sqrt[n]{a}$ to the desired level of precision using bisection search. - 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 a chapter in 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. *Introduction to Algorithms and Machine Learning: from Sorting to Strategic Agents.* https://justinmath.com/estimating-roots-via-bisection-search-and-newton-raphson-method/