Continuing our series on root-finding algorithms, this article delves deeper into the Bisection (linear convergence), Newton-Raphson (quadratic convergence), and Secant (super linear convergence) methods. Each of these algorithms has unique strengths, making them suitable for different scenarios. To illustrate their application, we will use the example of calculating the square root of a number—a simple yet insightful problem.

Using an approximation algorithm to calculate a square root might seem excessive, but please bear with me throughout this article. I chose the square root because the function is straightforward, and its derivative is relatively simple to calculate, allowing us to work through the exercises more easily.

$$ \begin{align} x&=\sqrt{m} &\text{define x as the square root of m} \\ x^2&=m &\text{squaring both sides to remove the square root} \\ x^2-m&=0 &\text{rearrange to express the equation in standard form} \\ f(x)&=x^2-m &\text{define f(x) as the function whose root we seek} \\ \end{align} $$

Check the Code Examples at the end of the article for the link to the repo with the code.

1. Bisection

The bisection algorithm is a simple and reliable numerical method for finding roots of continuous functions. It is particularly well-suited for situations where the function is continuous and the root lies within a known interval. Unlike some other methods, the bisection algorithm guarantees convergence to a root, provided the conditions are met, making it a popular choice for solving equations of the form \(f(x) = 0\).

How It Works:

The method starts with an interval \([a,b]\) where the function \(f(x)\) changes sign. This means \(f(a) \cdot f(b) < 0\), indicating that a root lies somewhere in the interval (due to the Intermediate Value Theorem). The algorithm then repeatedly bisects the interval, narrowing it down until the root is approximated to a desired level of accuracy.

The steps are:

  1. $$ r = \frac{a + b}{2} $$

  2. Evaluate \(f(r)\):

    • If \(f(r) = 0\), \(c\) is the exact root, and the algorithm stops.
    • If \(f(a) \cdot f(r) < 0\), the root lies in the subinterval \([a,r]\), so \(b\) is updated to \(r\).
    • Otherwise, the root lies in the subinterval \([r, b]\), so \(a\) is updated to \(r\)

  3. Repeat this process until the interval is sufficiently small, such that \(∣b−a∣\) is within a predefined tolerance.

Use case: Square root

For \(m=2\)

Means we want to get the result for this equation: \(x=\sqrt{m}\).

Let´s take \([a.b]=[0,2]\) as the values bracket. We know the square root of a number \(m\) satisfies \(0 \leq \sqrt{m} \leq m\) only if \(m \geq 1\), for \(0 \leq m < 1\), \(\sqrt{m} \geq m\). So, it’s safe to use this numbers for this exercise.

  • On each iteration we will evaluate only \(f_{n}(a) \cdot f_{n}(r)\) as they are exclusive with \(f_{n}(b) \cdot f_{n}(r)\). if one is positive the other is negative.
  • If \(f(r)=0\) then we stop.
  • If we don’t need an exact result and we are happy with certain amount of precision we ca use the error to check if we achieved the precision we need. ex: if we need 4 digits precision we can check for \(err \leq 0.00001\), which the example below this is satisfied at \(r_{18}\). $$ \begin{align} m &= 2 \\ [a.b] &= [0,2] \\ r_{0} &= \frac{0 + 2}{2} = 1 & \text{initial result}\\ \\ x &= r_{n} & \text{if } f_{n}(r)=0 \text{, stop iterating} \\ \\ v_{n+1} &= f_{n}(a) \cdot f_{n}(r) & \text{evaluate} \\ \\ a_{n+1} &= \begin{cases} a_{n} & \text{if } v_{n+1} < 0 \\ r_{n} & \text{otherwise} \end{cases} \\ \\ b_{n+1} &= \begin{cases} r_{n} & \text{if } v_{n+1} < 0 \\ b_{n} & \text{otherwise} \end{cases} \\ \\ e_{n} &= b_{n}-a_{n} & \text{error} \\ \end{align} $$ $$ \begin{align*} a_{1}&=1,0 &r_{1}&=1,5 &b_{1}&=2,0 &f_{1}(a)&=-1,0 &f_{1}(r)&=2,0 &f_{1}(b)&=0,25 &v_{1}&=-0,25 &v_{0} > 0 &\dots r_{0} \to a_{1} &e&=1,0 \\ a_{2}&=1,0 &r_{2}&=1,25 &b_{2}&=1,5 &f_{2}(a)&=-1,0 &f_{2}(r)&=0,25 &f_{2}(b)&=-0,4375 &v_{2}&=0,4375 &v_{1} < 0 &\dots r_{1} \to b_{2} &e&=0,5 \\ a_{3}&=1,25 &r_{3}&=1,375 &b_{3}&=1,5 &f_{3}(a)&=-0,4375 &f_{3}(r)&=0,25 &f_{3}(b)&=-0,109375 &v_{3}&=0,0478515625 &v_{2} > 0 &\dots r_{2} \to a_{3} &e&=0,25 \\ a_{4}&=1,375 &r_{4}&=1,4375 &b_{4}&=1,5 &f_{4}(a)&=-0,109375 &f_{4}(r)&=0,25 &f_{4}(b)&=0,06640625 &v_{4}&=-0,00726318359375 &v_{3} > 0 &\dots r_{3} \to a_{4} &e&=0,125 \\ a_{5}&=1,375 &r_{5}&=1,40625 &b_{5}&=1,4375 &f_{5}(a)&=-0,109375 &f_{5}(r)&=0,06640625 &f_{5}(b)&=-0,02246094 &v_{5}&=0,0024566650390625 &v_{4} < 0 &\dots r_{4} \to b_{5} &e&=0,0625 \\ a_{6}&=1,40625 &r_{6}&=1,421875 &b_{6}&=1,4375 &f_{6}(a)&=-0,02246094 &f_{6}(r)&=0,06640625 &f_{6}(b)&=0,02172852 &v_{6}&=-0,0004880428314209 &v_{5} > 0 &\dots r_{5} \to a_{6} &e&=0,03125 \\ a_{7}&=1,40625 &r_{7}&=1,4140625 &b_{7}&=1,421875 &f_{7}(a)&=-0,02246094 &f_{7}(r)&=0,02172852 &f_{7}(b)&=-0,00042725 &v_{7}&=0,00000959634780884 &v_{6} < 0 &\dots r_{6} \to b_{7} &e&=0,015625 \\ a_{8}&=1,4140625 &r_{8}&=1,41796875 &b_{8}&=1,421875 &f_{8}(a)&=-0,00042725 &f_{8}(r)&=0,02172852 &f_{8}(b)&=0,01063538 &v_{8}&=-0,00000454392284155 &v_{7} > 0 &\dots r_{7} \to a_{8} &e&=0,0078125 \\ a_{9}&=1,4140625 &r_{9}&=1,41601563 &b_{9}&=1,41796875 &f_{9}(a)&=-0,00042725 &f_{9}(r)&=0,01063538 &f_{9}(b)&=0,00510025 &v_{9}&=-0,00000217906199396 &v_{8} < 0 &\dots r_{8} \to b_{9} &e&=0,00390625 \\ a_{10}&=1,4140625 &r_{10}&=1,41503906 &b_{10}&=1,41601563 &f_{10}(a)&=-0,00042725 &f_{10}(r)&=0,00510025 &f_{10}(b)&=0,00233555 &v_{10}&=-0,00000099785393104 &v_{9} < 0 &\dots r_{9} \to b_{10} &e&=0,00195313 \\ a_{11}&=1,4140625 &r_{11}&=1,41455078 &b_{11}&=1,41503906 &f_{11}(a)&=-0,00042725 &f_{11}(r)&=0,00233555 &f_{11}(b)&=0,00095391 &v_{11}&=-0,0000004075554898 &v_{10} < 0 &\dots r_{10} \to b_{11} &e&=0,00097656 \\ a_{12}&=1,4140625 &r_{12}&=1,41430664 &b_{12}&=1,41455078 &f_{12}(a)&=-0,00042725 &f_{12}(r)&=0,00095391 &f_{12}(b)&=0,00026327 &v_{12}&=-0,00000011248266674 &v_{11} < 0 &\dots r_{11} \to b_{12} &e&=0,00048828 \\ a_{13}&=1,4140625 &r_{13}&=1,41418457 &b_{13}&=1,41430664 &f_{13}(a)&=-0,00042725 &f_{13}(r)&=0,00026327 &f_{13}(b)&=-0,000082 &v_{13}&=0,00000003503464541 &v_{12} < 0 &\dots r_{12} \to b_{13} &e&=0,00024414 \\ a_{14}&=1,41418457 &r_{14}&=1,41424561 &b_{14}&=1,41430664 &f_{14}(a)&=-0,000082 &f_{14}(r)&=0,00026327 &f_{14}(b)&=0,00009063 &v_{14}&=-0,00000000743197098 &v_{13} > 0 &\dots r_{13} \to a_{14} &e&=0,00012207 \\ a_{15}&=1,41418457 &r_{15}&=1,41421509 &b_{15}&=1,41424561 &f_{15}(a)&=-0,000082 &f_{15}(r)&=0,00009063 &f_{15}(b)&=0,00000431 &v_{15}&=-0,00000000035381974 &v_{14} < 0 &\dots r_{14} \to b_{15} &e&=0,00006104 \\ a_{16}&=1,41418457 &r_{16}&=1,41419983 &b_{16}&=1,41421509 &f_{16}(a)&=-0,000082 &f_{16}(r)&=0,00000431 &f_{16}(b)&=-0,00003884 &v_{16}&=0,00000000318519861 &v_{15} < 0 &\dots r_{15} \to b_{16} &e&=0,00003052 \\ a_{17}&=1,41419983 &r_{17}&=1,41420746 &b_{17}&=1,41421509 &f_{17}(a)&=-0,00003884 &f_{17}(r)&=0,00000431 &f_{17}(b)&=-0,00001726 &v_{17}&=0,0000000006706049 &v_{16} > 0 &\dots r_{16} \to a_{17} &e&=0,00001526 \\ a_{18}&=1,41420746 &r_{18}&=1,41421127 &b_{18}&=1,41421509 &f_{18}(a)&=-0,00001726 &f_{18}(r)&=0,00000431 &f_{18}(b)&=-0,00000647 &v_{18}&=0,00000000011178264 &v_{17} > 0 &\dots r_{17} \to a_{18} &e&=0,00000763 \\ a_{19}&=1,41421127 &r_{19}&=1,41421318 &b_{19}&=1,41421509 &f_{19}(a)&=-0,00000647 &f_{19}(r)&=0,00000431 &f_{19}(b)&=-0,00000108 &v_{19}&=0,00000000000699263 &v_{18} > 0 &\dots r_{18} \to a_{19} &e&=0,00000381 \\ a_{20}&=1,41421318 &r_{20}&=1,41421413 &b_{20}&=1,41421509 &f_{20}(a)&=-0,00000108 &f_{20}(r)&=0,00000431 &f_{20}(b)&=0,00000162 &v_{20}&=-0,00000000000174678 &v_{19} > 0 &\dots r_{19} \to a_{20} &e&=0,00000191 \\ a_{21}&=1,41421318 &r_{21}&=1,41421366 &b_{21}&=1,41421413 &f_{21}(a)&=-0,00000108 &f_{21}(r)&=0,00000162 &f_{21}(b)&=0,00000027 &v_{21}&=-0,00000000000029021 &v_{20} < 0 &\dots r_{20} \to b_{21} &e&=0,00000095 \\ a_{22}&=1,41421318 &r_{22}&=1,41421342 &b_{22}&=1,41421366 &f_{22}(a)&=-0,00000108 &f_{22}(r)&=0,00000027 &f_{22}(b)&=-0,00000041 &v_{22}&=0,00000000000043807 &v_{21} < 0 &\dots r_{21} \to b_{22} &e&=0,00000048 \\ a_{23}&=1,41421342 &r_{23}&=1,41421354 &b_{23}&=1,41421366 &f_{23}(a)&=-0,00000041 &f_{23}(r)&=0,00000027 &f_{23}(b)&=-0,00000007 &v_{23}&=0,00000000000002777 &v_{22} > 0 &\dots r_{22} \to a_{23} &e&=0,00000024 \\ a_{24}&=1,41421354 &r_{24}&=1,4142136 &b_{24}&=1,41421366 &f_{24}(a)&=-0,00000007 &f_{24}(r)&=0,00000027 &f_{24}(b)&=0,0000001 &v_{24}&=-0,00000000000000685 &v_{23} > 0 &\dots r_{23} \to a_{24} &e&=0,00000012 \\ a_{25}&=1,41421354 &r_{25}&=1,41421357 &b_{25}&=1,4142136 &f_{25}(a)&=-0,00000007 &f_{25}(r)&=0,0000001 &f_{25}(b)&=0,00000002 &v_{25}&=-0,00000000000000108 &v_{24} < 0 &\dots r_{24} \to b_{25} &e&=0,00000006 \\ a_{26}&=1,41421354 &r_{26}&=1,41421355 &b_{26}&=1,41421357 &f_{26}(a)&=-0,00000007 &f_{26}(r)&=0,00000002 &f_{26}(b)&=-0,00000003 &v_{26}&=0,0000000000000018 &v_{25} < 0 &\dots r_{25} \to b_{26} &e&=0,00000003 \\ a_{27}&=1,41421355 &r_{27}&=1,41421356 &b_{27}&=1,41421357 &f_{27}(a)&=-0,00000003 &f_{27}(r)&=0,00000002 &f_{27}(b)&=-0,00000001 &v_{27}&=0,00000000000000014 &v_{26} > 0 &\dots r_{26} \to a_{27} &e&=0,00000001 \\ a_{28}&=1,41421356 &r_{28}&=1,41421356 &b_{28}&=1,41421357 &f_{28}(a)&=-0,00000001 &f_{28}(r)&=0,00000002 &f_{28}(b)&=0,00000001 &v_{28}&=-0,00000000000000003 &v_{27} > 0 &\dots r_{27} \to a_{28} &e&=0,00000001 \\ a_{29}&=1,41421356 &r_{29}&=1,41421356 &b_{29}&=1,41421356 &f_{29}(a)&=-0,00000001 &f_{29}(r)&=0,00000001 &f_{29}(b)&=0,0 &v_{29}&=0,0 &v_{28} < 0 &\dots r_{28} \to b_{29} &e&=0,0 \\ \\ &&\sqrt{2} &= 1,4142135624 \end{align*} $$

For \(m=13\)

$$ \begin{align} m &= 13 \\ [a.b] &= [0,13] \\ r_{0} &= \frac{0 + 13}{2} = 6.5 & \text{initial result}\\ \end{align} $$$$ \begin{align*} a_{0}&=0,0 &r_{0}&=6,5 &b_{0}&=13,0 &f_{0}(a)&=-13,0 &f_{0}(r)&=156,0 &f_{0}(b)&=29,25 &v_{0}&=-380,25 & &e&=0,0 \\ a_{1}&=0,0 &r_{1}&=3,25 &b_{1}&=6,5 &f_{1}(a)&=-13,0 &f_{1}(r)&=29,25 &f_{1}(b)&=-2,4375 &v_{1}&=31,6875 &v_{0} < 0 &\dots r_{0} \to b_{1} &e&=6,5 \\ a_{2}&=3,25 &r_{2}&=4,875 &b_{2}&=6,5 &f_{2}(a)&=-2,4375 &f_{2}(r)&=29,25 &f_{2}(b)&=10,765625 &v_{2}&=-26,2412109375 &v_{1} > 0 &\dots r_{1} \to a_{2} &e&=3,25 \\ a_{3}&=3,25 &r_{3}&=4,0625 &b_{3}&=4,875 &f_{3}(a)&=-2,4375 &f_{3}(r)&=10,765625 &f_{3}(b)&=3,50390625 &v_{3}&=-8,540771484375 &v_{2} < 0 &\dots r_{2} \to b_{3} &e&=1,625 \\ a_{4}&=3,25 &r_{4}&=3,65625 &b_{4}&=4,0625 &f_{4}(a)&=-2,4375 &f_{4}(r)&=3,50390625 &f_{4}(b)&=0,36816406 &v_{4}&=-0,89739990234375 &v_{3} < 0 &\dots r_{3} \to b_{4} &e&=0,8125 \\ a_{5}&=3,25 &r_{5}&=3,453125 &b_{5}&=3,65625 &f_{5}(a)&=-2,4375 &f_{5}(r)&=0,36816406 &f_{5}(b)&=-1,07592773 &v_{5}&=2,62257385253906 &v_{4} < 0 &\dots r_{4} \to b_{5} &e&=0,40625 \\ a_{6}&=3,453125 &r_{6}&=3,5546875 &b_{6}&=3,65625 &f_{6}(a)&=-1,07592773 &f_{6}(r)&=0,36816406 &f_{6}(b)&=-0,36419678 &v_{6}&=0,391849413514137 &v_{5} > 0 &\dots r_{5} \to a_{6} &e&=0,203125 \\ a_{7}&=3,5546875 &r_{7}&=3,60546875 &b_{7}&=3,65625 &f_{7}(a)&=-0,36419678 &f_{7}(r)&=0,36816406 &f_{7}(b)&=-0,00059509 &v_{7}&=0,00021673087030649 &v_{6} > 0 &\dots r_{6} \to a_{7} &e&=0,1015625 \\ a_{8}&=3,60546875 &r_{8}&=3,63085938 &b_{8}&=3,65625 &f_{8}(a)&=-0,00059509 &f_{8}(r)&=0,36816406 &f_{8}(b)&=0,1831398 &v_{8}&=-0,00010898517211899 &v_{7} > 0 &\dots r_{7} \to a_{8} &e&=0,05078125 \\ a_{9}&=3,60546875 &r_{9}&=3,61816406 &b_{9}&=3,63085938 &f_{9}(a)&=-0,00059509 &f_{9}(r)&=0,1831398 &f_{9}(b)&=0,09111118 &v_{9}&=-0,00005421960668173 &v_{8} < 0 &\dots r_{8} \to b_{9} &e&=0,02539063 \\ a_{10}&=3,60546875 &r_{10}&=3,61181641 &b_{10}&=3,61816406 &f_{10}(a)&=-0,00059509 &f_{10}(r)&=0,09111118 &f_{10}(b)&=0,04521775 &v_{10}&=-0,00002690875771805 &v_{9} < 0 &\dots r_{9} \to b_{10} &e&=0,01269531 \\ a_{11}&=3,60546875 &r_{11}&=3,60864258 &b_{11}&=3,61181641 &f_{11}(a)&=-0,00059509 &f_{11}(r)&=0,04521775 &f_{11}(b)&=0,02230126 &v_{11}&=-0,00001327131667495 &v_{10} < 0 &\dots r_{10} \to b_{11} &e&=0,00634766 \\ a_{12}&=3,60546875 &r_{12}&=3,60705566 &b_{12}&=3,60864258 &f_{12}(a)&=-0,00059509 &f_{12}(r)&=0,02230126 &f_{12}(b)&=0,01085056 &v_{12}&=-0,00000645709201308 &v_{11} < 0 &\dots r_{11} \to b_{12} &e&=0,00317383 \\ a_{13}&=3,60546875 &r_{13}&=3,60626221 &b_{13}&=3,60705566 &f_{13}(a)&=-0,00059509 &f_{13}(r)&=0,01085056 &f_{13}(b)&=0,00512711 &v_{13}&=-0,00000305110364707 &v_{12} < 0 &\dots r_{12} \to b_{13} &e&=0,00158691 \\ a_{14}&=3,60546875 &r_{14}&=3,60586548 &b_{14}&=3,60626221 &f_{14}(a)&=-0,00059509 &f_{14}(r)&=0,00512711 &f_{14}(b)&=0,00226585 &v_{14}&=-0,00000134839045529 &v_{13} < 0 &\dots r_{13} \to b_{14} &e&=0,00079346 \\ a_{15}&=3,60546875 &r_{15}&=3,60566711 &b_{15}&=3,60586548 &f_{15}(a)&=-0,00059509 &f_{15}(r)&=0,00226585 &f_{15}(b)&=0,00083534 &v_{15}&=-0,00000049710410721 &v_{14} < 0 &\dots r_{14} \to b_{15} &e&=0,00039673 \\ a_{16}&=3,60546875 &r_{16}&=3,60556793 &b_{16}&=3,60566711 &f_{16}(a)&=-0,00059509 &f_{16}(r)&=0,00083534 &f_{16}(b)&=0,00012011 &v_{16}&=-0,00000007147849512 &v_{15} < 0 &\dots r_{15} \to b_{16} &e&=0,00019836 \\ a_{17}&=3,60546875 &r_{17}&=3,60551834 &b_{17}&=3,60556793 &f_{17}(a)&=-0,00059509 &f_{17}(r)&=0,00012011 &f_{17}(b)&=-0,00023749 &v_{17}&=0,00000014132992043 &v_{16} < 0 &\dots r_{16} \to b_{17} &e&=0,00009918 \\ a_{18}&=3,60551834 &r_{18}&=3,60554314 &b_{18}&=3,60556793 &f_{18}(a)&=-0,00023749 &f_{18}(r)&=0,00012011 &f_{18}(b)&=-0,00005869 &v_{18}&=0,00000001393845341 &v_{17} > 0 &\dots r_{17} \to a_{18} &e&=0,00004959 \\ a_{19}&=3,60554314 &r_{19}&=3,60555553 &b_{19}&=3,60556793 &f_{19}(a)&=-0,00005869 &f_{19}(r)&=0,00012011 &f_{19}(b)&=0,00003071 &v_{19}&=-0,00000000180245487 &v_{18} > 0 &\dots r_{18} \to a_{19} &e&=0,0000248 \\ a_{20}&=3,60554314 &r_{20}&=3,60554934 &b_{20}&=3,60555553 &f_{20}(a)&=-0,00005869 &f_{20}(r)&=0,00003071 &f_{20}(b)&=-0,00001399 &v_{20}&=0,00000000082104112 &v_{19} < 0 &\dots r_{19} \to b_{20} &e&=0,0000124 \\ a_{21}&=3,60554934 &r_{21}&=3,60555243 &b_{21}&=3,60555553 &f_{21}(a)&=-0,00001399 &f_{21}(r)&=0,00003071 &f_{21}(b)&=0,00000836 &v_{21}&=-0,00000000011696509 &v_{20} > 0 &\dots r_{20} \to a_{21} &e&=0,0000062 \\ a_{22}&=3,60554934 &r_{22}&=3,60555089 &b_{22}&=3,60555243 &f_{22}(a)&=-0,00001399 &f_{22}(r)&=0,00000836 &f_{22}(b)&=-0,00000281 &v_{22}&=0,00000000003936945 &v_{21} < 0 &\dots r_{21} \to b_{22} &e&=0,0000031 \\ a_{23}&=3,60555089 &r_{23}&=3,60555166 &b_{23}&=3,60555243 &f_{23}(a)&=-0,00000281 &f_{23}(r)&=0,00000836 &f_{23}(b)&=0,00000277 &v_{23}&=-0,00000000000780489 &v_{22} > 0 &\dots r_{22} \to a_{23} &e&=0,00000155 \\ a_{24}&=3,60555089 &r_{24}&=3,60555127 &b_{24}&=3,60555166 &f_{24}(a)&=-0,00000281 &f_{24}(r)&=0,00000277 &f_{24}(b)&=-0,00000002 &v_{24}&=0,0000000000000575 &v_{23} < 0 &\dots r_{23} \to b_{24} &e&=0,00000077 \\ a_{25}&=3,60555127 &r_{25}&=3,60555147 &b_{25}&=3,60555166 &f_{25}(a)&=-0,00000002 &f_{25}(r)&=0,00000277 &f_{25}(b)&=0,00000138 &v_{25}&=-0,00000000000002812 &v_{24} > 0 &\dots r_{24} \to a_{25} &e&=0,00000039 \\ a_{26}&=3,60555127 &r_{26}&=3,60555137 &b_{26}&=3,60555147 &f_{26}(a)&=-0,00000002 &f_{26}(r)&=0,00000138 &f_{26}(b)&=0,00000068 &v_{26}&=-0,00000000000001385 &v_{25} < 0 &\dots r_{25} \to b_{26} &e&=0,00000019 \\ a_{27}&=3,60555127 &r_{27}&=3,60555132 &b_{27}&=3,60555137 &f_{27}(a)&=-0,00000002 &f_{27}(r)&=0,00000068 &f_{27}(b)&=0,00000033 &v_{27}&=-0,00000000000000672 &v_{26} < 0 &\dots r_{26} \to b_{27} &e&=0,0000001 \\ a_{28}&=3,60555127 &r_{28}&=3,6055513 &b_{28}&=3,60555132 &f_{28}(a)&=-0,00000002 &f_{28}(r)&=0,00000033 &f_{28}(b)&=0,00000015 &v_{28}&=-0,00000000000000315 &v_{27} < 0 &\dots r_{27} \to b_{28} &e&=0,00000005 \\ a_{29}&=3,60555127 &r_{29}&=3,60555128 &b_{29}&=3,6055513 &f_{29}(a)&=-0,00000002 &f_{29}(r)&=0,00000015 &f_{29}(b)&=0,00000007 &v_{29}&=-0,00000000000000137 &v_{28} < 0 &\dots r_{28} \to b_{29} &e&=0,00000002 \\ a_{30}&=3,60555127 &r_{30}&=3,60555128 &b_{30}&=3,60555128 &f_{30}(a)&=-0,00000002 &f_{30}(r)&=0,00000007 &f_{30}(b)&=0,00000002 &v_{30}&=-0,00000000000000047 &v_{29} < 0 &\dots r_{29} \to b_{30} &e&=0,00000001 \\ a_{31}&=3,60555127 &r_{31}&=3,60555128 &b_{31}&=3,60555128 &f_{31}(a)&=-0,00000002 &f_{31}(r)&=0,00000002 &f_{31}(b)&=0,0 &v_{31}&=-0,00000000000000003 &v_{30} < 0 &\dots r_{30} \to b_{31} &e&=0,00000001 \\ a_{32}&=3,60555127 &r_{32}&=3,60555127 &b_{32}&=3,60555128 &f_{32}(a)&=-0,00000002 &f_{32}(r)&=0,0 &f_{32}(b)&=-0,00000001 &v_{32}&=0,00000000000000019 &v_{31} < 0 &\dots r_{31} \to b_{32} &e&=0,0 \\ a_{33}&=3,60555127 &r_{33}&=3,60555127 &b_{33}&=3,60555128 &f_{33}(a)&=-0,00000001 &f_{33}(r)&=0,0 &f_{33}(b)&=0,0 &v_{33}&=0,00000000000000004 &v_{32} > 0 &\dots r_{32} \to a_{33} &e&=0,0 \\ a_{34}&=3,60555127 &r_{34}&=3,60555128 &b_{34}&=3,60555128 &f_{34}(a)&=0,0 &f_{34}(r)&=0,0 &f_{34}(b)&=0,0 &v_{34}&=0,00000000000000001 &v_{33} > 0 &\dots r_{33} \to a_{34} &e&=0,0 \\ a_{35}&=3,60555128 &r_{35}&=3,60555128 &b_{35}&=3,60555128 &f_{35}(a)&=0,0 &f_{35}(r)&=0,0 &f_{35}(b)&=0,0 &v_{35}&=0,0 &v_{34} > 0 &\dots r_{34} \to a_{35} &e&=0,0 \\ \\ &&\sqrt{13} &= 3,60555128 \end{align*} $$

For \(m=354\)

$$ \begin{align} m &= 354 \\ [a.b] &= [0,354] \\ r_{0} &= \frac{0 + 354}{2} = 177 & \text{initial result}\\ \end{align} $$ $$ \begin{align*} a_{0}&=0,0 &r_{0}&=177,0 &b_{0}&=354,0 &f_{0}(a)&=-354,0 &f_{0}(r)&=124962,0 &f_{0}(b)&=30975,0 &v_{0}&=-10965150,0 & &e&=0,0 \\ a_{1}&=0,0 &r_{1}&=88,5 &b_{1}&=177,0 &f_{1}(a)&=-354,0 &f_{1}(r)&=30975,0 &f_{1}(b)&=7478,25 &v_{1}&=-2647300,5 &v_{0} < 0 &\dots r_{0} \to b_{1} &e&=177,0 \\ a_{2}&=0,0 &r_{2}&=44,25 &b_{2}&=88,5 &f_{2}(a)&=-354,0 &f_{2}(r)&=7478,25 &f_{2}(b)&=1604,0625 &v_{2}&=-567838,125 &v_{1} < 0 &\dots r_{1} \to b_{2} &e&=88,5 \\ a_{3}&=0,0 &r_{3}&=22,125 &b_{3}&=44,25 &f_{3}(a)&=-354,0 &f_{3}(r)&=1604,0625 &f_{3}(b)&=135,515625 &v_{3}&=-47972,53125 &v_{2} < 0 &\dots r_{2} \to b_{3} &e&=44,25 \\ a_{4}&=0,0 &r_{4}&=11,0625 &b_{4}&=22,125 &f_{4}(a)&=-354,0 &f_{4}(r)&=135,515625 &f_{4}(b)&=-231,62109375 &v_{4}&=81993,8671875 &v_{3} < 0 &\dots r_{3} \to b_{4} &e&=22,125 \\ a_{5}&=11,0625 &r_{5}&=16,59375 &b_{5}&=22,125 &f_{5}(a)&=-231,62109375 &f_{5}(r)&=135,515625 &f_{5}(b)&=-78,64746094 &v_{5}&=18216,4109230042 &v_{4} > 0 &\dots r_{4} \to a_{5} &e&=11,0625 \\ a_{6}&=16,59375 &r_{6}&=19,359375 &b_{6}&=22,125 &f_{6}(a)&=-78,64746094 &f_{6}(r)&=135,515625 &f_{6}(b)&=20,78540039 &v_{6}&=-1634,71896529198 &v_{5} > 0 &\dots r_{5} \to a_{6} &e&=5,53125 \\ a_{7}&=16,59375 &r_{7}&=17,9765625 &b_{7}&=19,359375 &f_{7}(a)&=-78,64746094 &f_{7}(r)&=20,78540039 &f_{7}(b)&=-30,84320068 &v_{7}&=2425,73942095041 &v_{6} < 0 &\dots r_{6} \to b_{7} &e&=2,765625 \\ a_{8}&=17,9765625 &r_{8}&=18,66796875 &b_{8}&=19,359375 &f_{8}(a)&=-30,84320068 &f_{8}(r)&=20,78540039 &f_{8}(b)&=-5,50694275 &v_{8}&=169,851740361191 &v_{7} > 0 &\dots r_{7} \to a_{8} &e&=1,3828125 \\ a_{9}&=18,66796875 &r_{9}&=19,01367188 &b_{9}&=19,359375 &f_{9}(a)&=-5,50694275 &f_{9}(r)&=20,78540039 &f_{9}(b)&=7,51971817 &v_{9}&=-41,4106574518955 &v_{8} > 0 &\dots r_{8} \to a_{9} &e&=0,69140625 \\ a_{10}&=18,66796875 &r_{10}&=18,84082031 &b_{10}&=19,01367188 &f_{10}(a)&=-5,50694275 &f_{10}(r)&=7,51971817 &f_{10}(b)&=0,97651005 &v_{10}&=-5,37758492770081 &v_{9} < 0 &\dots r_{9} \to b_{10} &e&=0,34570313 \\ a_{11}&=18,66796875 &r_{11}&=18,75439453 &b_{11}&=18,84082031 &f_{11}(a)&=-5,50694275 &f_{11}(r)&=0,97651005 &f_{11}(b)&=-2,27268577 &v_{11}&=12,5155504010945 &v_{10} < 0 &\dots r_{10} \to b_{11} &e&=0,17285156 \\ a_{12}&=18,75439453 &r_{12}&=18,79760742 &b_{12}&=18,84082031 &f_{12}(a)&=-2,27268577 &f_{12}(r)&=0,97651005 &f_{12}(b)&=-0,64995521 &v_{12}&=1,47714396142455 &v_{11} > 0 &\dots r_{11} \to a_{12} &e&=0,08642578 \\ a_{13}&=18,79760742 &r_{13}&=18,81921387 &b_{13}&=18,84082031 &f_{13}(a)&=-0,64995521 &f_{13}(r)&=0,97651005 &f_{13}(b)&=0,16281058 &v_{13}&=-0,105819584526478 &v_{12} > 0 &\dots r_{12} \to a_{13} &e&=0,04321289 \\ a_{14}&=18,79760742 &r_{14}&=18,80841064 &b_{14}&=18,81921387 &f_{14}(a)&=-0,64995521 &f_{14}(r)&=0,16281058 &f_{14}(b)&=-0,24368903 &v_{14}&=0,158386953260919 &v_{13} < 0 &\dots r_{13} \to b_{14} &e&=0,02160645 \\ a_{15}&=18,80841064 &r_{15}&=18,81381226 &b_{15}&=18,81921387 &f_{15}(a)&=-0,24368903 &f_{15}(r)&=0,16281058 &f_{15}(b)&=-0,0404684 &v_{15}&=0,00986170531828501 &v_{14} > 0 &\dots r_{14} \to a_{15} &e&=0,01080322 \\ a_{16}&=18,81381226 &r_{16}&=18,81651306 &b_{16}&=18,81921387 &f_{16}(a)&=-0,0404684 &f_{16}(r)&=0,16281058 &f_{16}(b)&=0,06116379 &v_{16}&=-0,00247520097863952 &v_{15} > 0 &\dots r_{15} \to a_{16} &e&=0,00540161 \\ a_{17}&=18,81381226 &r_{17}&=18,81516266 &b_{17}&=18,81651306 &f_{17}(a)&=-0,0404684 &f_{17}(r)&=0,06116379 &f_{17}(b)&=0,01034587 &v_{17}&=-0,00041868094073607 &v_{16} < 0 &\dots r_{16} \to b_{17} &e&=0,00270081 \\ a_{18}&=18,81381226 &r_{18}&=18,81448746 &b_{18}&=18,81516266 &f_{18}(a)&=-0,0404684 &f_{18}(r)&=0,01034587 &f_{18}(b)&=-0,01506172 &v_{18}&=0,00060952372995326 &v_{17} < 0 &\dots r_{17} \to b_{18} &e&=0,0013504 \\ a_{19}&=18,81448746 &r_{19}&=18,81482506 &b_{19}&=18,81516266 &f_{19}(a)&=-0,01506172 &f_{19}(r)&=0,01034587 &f_{19}(b)&=-0,00235804 &v_{19}&=0,00003551610033706 &v_{18} > 0 &\dots r_{18} \to a_{19} &e&=0,0006752 \\ a_{20}&=18,81482506 &r_{20}&=18,81499386 &b_{20}&=18,81516266 &f_{20}(a)&=-0,00235804 &f_{20}(r)&=0,01034587 &f_{20}(b)&=0,00399389 &v_{20}&=-0,00000941774059949 &v_{19} > 0 &\dots r_{19} \to a_{20} &e&=0,0003376 \\ a_{21}&=18,81482506 &r_{21}&=18,81490946 &b_{21}&=18,81499386 &f_{21}(a)&=-0,00235804 &f_{21}(r)&=0,00399389 &f_{21}(b)&=0,00081792 &v_{21}&=-0,00000192868312397 &v_{20} < 0 &\dots r_{20} \to b_{21} &e&=0,0001688 \\ a_{22}&=18,81482506 &r_{22}&=18,81486726 &b_{22}&=18,81490946 &f_{22}(a)&=-0,00235804 &f_{22}(r)&=0,00081792 &f_{22}(b)&=-0,00077006 &v_{22}&=0,00000181583301588 &v_{21} < 0 &\dots r_{21} \to b_{22} &e&=0,0000844 \\ a_{23}&=18,81486726 &r_{23}&=18,81488836 &b_{23}&=18,81490946 &f_{23}(a)&=-0,00077006 &f_{23}(r)&=0,00081792 &f_{23}(b)&=0,00002393 &v_{23}&=-0,00000001842631129 &v_{22} > 0 &\dots r_{22} \to a_{23} &e&=0,0000422 \\ a_{24}&=18,81486726 &r_{24}&=18,81487781 &b_{24}&=18,81488836 &f_{24}(a)&=-0,00077006 &f_{24}(r)&=0,00002393 &f_{24}(b)&=-0,00037307 &v_{24}&=0,00000028728400509 &v_{23} < 0 &\dots r_{23} \to b_{24} &e&=0,0000211 \\ a_{25}&=18,81487781 &r_{25}&=18,81488308 &b_{25}&=18,81488836 &f_{25}(a)&=-0,00037307 &f_{25}(r)&=0,00002393 &f_{25}(b)&=-0,00017457 &v_{25}&=0,00000006512587636 &v_{24} > 0 &\dots r_{24} \to a_{25} &e&=0,00001055 \\ a_{26}&=18,81488308 &r_{26}&=18,81488572 &b_{26}&=18,81488836 &f_{26}(a)&=-0,00017457 &f_{26}(r)&=0,00002393 &f_{26}(b)&=-0,00007532 &v_{26}&=0,00000001314860687 &v_{25} > 0 &\dots r_{25} \to a_{26} &e&=0,00000528 \\ a_{27}&=18,81488572 &r_{27}&=18,81488704 &b_{27}&=18,81488836 &f_{27}(a)&=-0,00007532 &f_{27}(r)&=0,00002393 &f_{27}(b)&=-0,0000257 &v_{27}&=0,00000000193543172 &v_{26} > 0 &\dots r_{26} \to a_{27} &e&=0,00000264 \\ a_{28}&=18,81488704 &r_{28}&=18,8148877 &b_{28}&=18,81488836 &f_{28}(a)&=-0,0000257 &f_{28}(r)&=0,00002393 &f_{28}(b)&=-0,00000088 &v_{28}&=0,0000000000227104 &v_{27} > 0 &\dots r_{27} \to a_{28} &e&=0,00000132 \\ a_{29}&=18,8148877 &r_{29}&=18,81488803 &b_{29}&=18,81488836 &f_{29}(a)&=-0,00000088 &f_{29}(r)&=0,00002393 &f_{29}(b)&=0,00001152 &v_{29}&=-0,00000000001018352 &v_{28} > 0 &\dots r_{28} \to a_{29} &e&=0,00000066 \\ a_{30}&=18,8148877 &r_{30}&=18,81488786 &b_{30}&=18,81488803 &f_{30}(a)&=-0,00000088 &f_{30}(r)&=0,00001152 &f_{30}(b)&=0,00000532 &v_{30}&=-0,0000000000047012 &v_{29} < 0 &\dots r_{29} \to b_{30} &e&=0,00000033 \\ a_{31}&=18,8148877 &r_{31}&=18,81488778 &b_{31}&=18,81488786 &f_{31}(a)&=-0,00000088 &f_{31}(r)&=0,00000532 &f_{31}(b)&=0,00000222 &v_{31}&=-0,00000000000196004 &v_{30} < 0 &\dots r_{30} \to b_{31} &e&=0,00000016 \\ a_{32}&=18,8148877 &r_{32}&=18,81488774 &b_{32}&=18,81488778 &f_{32}(a)&=-0,00000088 &f_{32}(r)&=0,00000222 &f_{32}(b)&=0,00000067 &v_{32}&=-0,00000000000058946 &v_{31} < 0 &\dots r_{31} \to b_{32} &e&=0,00000008 \\ a_{33}&=18,8148877 &r_{33}&=18,81488772 &b_{33}&=18,81488774 &f_{33}(a)&=-0,00000088 &f_{33}(r)&=0,00000067 &f_{33}(b)&=-0,00000011 &v_{33}&=0,00000000000009583 &v_{32} < 0 &\dots r_{32} \to b_{33} &e&=0,00000004 \\ a_{34}&=18,81488772 &r_{34}&=18,81488773 &b_{34}&=18,81488774 &f_{34}(a)&=-0,00000011 &f_{34}(r)&=0,00000067 &f_{34}(b)&=0,00000028 &v_{34}&=-0,00000000000003028 &v_{33} > 0 &\dots r_{33} \to a_{34} &e&=0,00000002 \\ a_{35}&=18,81488772 &r_{35}&=18,81488772 &b_{35}&=18,81488773 &f_{35}(a)&=-0,00000011 &f_{35}(r)&=0,00000028 &f_{35}(b)&=0,00000009 &v_{35}&=-0,00000000000000926 &v_{34} < 0 &\dots r_{34} \to b_{35} &e&=0,00000001 \\ a_{36}&=18,81488772 &r_{36}&=18,81488772 &b_{36}&=18,81488772 &f_{36}(a)&=-0,00000011 &f_{36}(r)&=0,00000009 &f_{36}(b)&=-0,00000001 &v_{36}&=0,00000000000000125 &v_{35} < 0 &\dots r_{35} \to b_{36} &e&=0,00000001 \\ a_{37}&=18,81488772 &r_{37}&=18,81488772 &b_{37}&=18,81488772 &f_{37}(a)&=-0,00000001 &f_{37}(r)&=0,00000009 &f_{37}(b)&=0,00000004 &v_{37}&=-0,00000000000000043 &v_{36} > 0 &\dots r_{36} \to a_{37} &e&=0,0 \\ \\ &&\sqrt{354}&=18,81488772 \end{align*} $$

2. Newton-Raphson

The Newton-Raphson method is an efficient and widely used numerical technique for finding approximate solutions to equations of the form \(f(x) = 0\). It is particularly effective for equations that are difficult or impossible to solve algebraically. The method uses an iterative approach, starting with an initial guess for the root and refining this estimate with each step.

How it works

$$ x_{n+1}=x_{n}-\frac{f(x_{n})}{f'(x_{n})} $$

Here:

  • \(x_n\)​ is the current approximation of the root.
  • \(f(x_n)\) is the value of the function at \(x_n\)​.
  • \(f'(x_n)\) is the derivative of the function at \(x_n\)​, which represents the slope of the tangent.

The process is repeated until the successive approximations converge to a value within a desired level of accuracy.

Use case: Square root

$$ \begin{align*} x&=\sqrt{m} &\text{define x as the square root of m} \\ x^2&=m &\text{squaring both sides to remove the square root} \\ x^2-m&=0 &\text{rearrange to express the equation in standard form} \\ f(x)&=x^2-m &\text{define f(x) as the fucntion whose root we seek} \\ f'(x)&=2x &\text{the derivative, which we will need in this exercise} \end{align*} $$$$ \begin{align*} x_{n+1}&=x_{n}-\frac{x_{n}^2-m}{2x_{n}} \\ \end{align*} $$$$ \begin{align*} &=x_{n}-\frac{x_{n}^2-m}{2x_{n}} \\ &&\text{apply the fraction property: } a-\frac{b}{c}=\frac{ac-b}{c} \\ &=\frac{x_{n}.2x_{n}-(x_{n}^2-m)}{2x_{n}} \\ &&\text{simplify the numerator }x_{n}.2x_{n} \to 2x_{n}^2 \\ &=\frac{2x_{n}^2-(x_{n}^2-m)}{2x_{n}} \\ &&\text{distribute negative sign and combine like terms} \\ &&2x_{n}^2-(x_{n}^2-m) \to 2x_{n}^2-x_{n}^2+m \to x_{n}^2+m \\ &=\frac{x_{n}^2+m}{2x_{n}} &\text{final simplified form}\\ \end{align*} $$$$ x_{n+1}=\frac{x_{n}^2+m}{2x_{n}} $$

Let’s find some roots

For \(m=2\)

$$ \begin{align*} m &= 2 \\ x_0 &= m \to 2 \\ \\ &\text{Iteration} &\text{Result} & &\text{Error} \\ x_1 &= \frac{x_{0}^2+m}{2x_{0}} &\to \frac{2,0^2+2}{2\times2,0} &= 1,5 & x_0-x_1 &= 0,5\\ x_2 &= \frac{x_{1}^2+m}{2x_{1}} &\to \frac{1,5^2+2}{2\times1,5} &= 1,4166666667 & x_1-x_2 &= 0,0833333333 \\ x_3 &= \frac{x_{2}^2+m}{2x_{2}} &\to \frac{1,4166666667^2+2}{2\times1,4166666667} &= 1,4142156863 & x_2-x_3 &= 0,0024509804 \\ x_4&=\frac{x_{3}^2+m}{2x_{3}} &\to \frac{1,4142156863^2+2}{2\times1,4142156863} &= 1,4142135624 & x_3-x_4&=0,0000021239\\ x_5&=\frac{x_{4}^2+m}{2x_{4}}&\to \frac{1,4142135624^2+2}{2\times1,4142135624} &= 1,4142135624 & x_4-x_5&=0,0 \\ \\ &&\sqrt{2} &= 1,4142135624 \end{align*} $$

For \(m=13\)

$$ \begin{align*} m &= 13 \\ x_0 &= m \to 13 \\ \\ &\text{Iteration} &\text{Result} & &\text{Error} \\ x_1 &= \frac{x_{0}^2+m}{2x_{0}} \to &\frac{13,0^2+13}{2\times13,0} &= 7,0 & x_0-x_1 &=6,0\\ x_2 &= \frac{x_{1}^2+m}{2x_{1}} \to &\frac{7,0^2+13}{2\times7,0} &= 4,4285714286 & x_1-x_2&=2,5714285714\\ x_3 &= \frac{x_{2}^2+m}{2x_{2}} \to &\frac{4,4285714286^2+13}{2\times4,4285714286} &= 3,6820276498 & x_2-x_3&=0,7465437788\\ x_4 &= \frac{x_{3}^2+m}{2x_{3}} \to &\frac{3,6820276498^2+13}{2\times3,6820276498} &= 3,6063454895 & x_3-x_4&=0,0756821603\\ x_5 &= \frac{x_{4}^2+m}{2x_{4}} \to &\frac{3,6063454895^2+13}{2\times3,6063454895} &= 3,6055513629 & x_4-x_5&=0,0007941265\\ x_6 &= \frac{x_{5}^2+m}{2x_{5}} \to &\frac{3,6055513629^2+13}{2\times3,6055513629} &= 3,6055512755 & x_5-x_6&=0,0000000875\\ x_7 &= \frac{x_{6}^2+m}{2x_{6}} \to &\frac{3,6055512755^2+13}{2\times3,6055512755} &= 3,6055512755 & x_6-x_7&=0,0\\ \\ &&\sqrt{13}&=3,6055512755 \end{align*} $$

For \(m=354\)

$$ \begin{align*} m &= 354 \\ x_0 &= m \to 354 \\ \\ &\text{Iteration} &\text{Result} & &\text{Error} \\ x_1 &= \frac{x_{0}^2+m}{2x_{0}} &\to \frac{354,0^2+354}{2\times354,0} &= 177,5 & x_0-x_1&=176,5\\ x_2 &= \frac{x_{1}^2+m}{2x_{1}} &\to \frac{177,5^2+354}{2\times177,5} &= 89,7471830986 & x_1-x_2&=87,7528169014\\ x_3 &= \frac{x_{2}^2+m}{2x_{2}} &\to \frac{89,7471830986^2+354}{2\times89,7471830986} &= 46,8457982959 & x_2-x_3 &= 42,9013848026\\ x_4 &= \frac{x_{3}^2+m}{2x_{3}} &\to \frac{46,8457982959^2+354}{2\times46,8457982959} &= 27,2012529479 & x_3-x_4 &= 19,6445453481\\ x_5 &= \frac{x_{4}^2+m}{2x_{4}} &\to \frac{27,2012529479^2+354}{2\times27,2012529479} &= 20,1076796725 & x_4-x_5 &= 7,0935732753\\ x_6 &= \frac{x_{5}^2+m}{2x_{5}} &\to \frac{20,1076796725^2+354}{2\times20,1076796725} &= 18,8564467448 & x_5-x_6 &= 1,2512329277\\ x_7 &= \frac{x_{6}^2+m}{2x_{6}} &\to \frac{18,8564467448^2+354}{2\times18,8564467448} &= 18,8149335196 & x_6-x_7 &= 0,0415132252\\ x_8 &= \frac{x_{7}^2+m}{2x_{7}} &\to \frac{18,8149335196^2+354}{2\times18,8149335196} &= 18,8148877223 & x_7-x_8 &= 0,0000457973\\ x_9 &= \frac{x_{8}^2+m}{2x_{8}} &\to \frac{18,8148877223^2+354}{2\times18,8148877223} &= 18,8148877222 & x_8-x_9 &= 0,0000000001\\ x_{10} &= \frac{x_{9}^2+m}{2x_{9}} &\to \frac{18,8148877222^2+354}{2\times18,8148877222} &= 18,8148877222 & x_9-x_{10} &= 0,0\\ \\ &&\sqrt{354} &= 18,8148877222 \end{align*} $$

3. Secant

The secant method is a numerical algorithm used to approximate solutions to equations of the form \(f(x) = 0\). It is similar to the Newton-Raphson method but does not require the explicit computation of the derivative of \(f(x)\). Instead, the secant method uses a finite difference approximation of the derivative, making it a practical choice when the derivative is difficult or costly to calculate.

How It Works:

$$ x_{n+1} = x_n - \frac{f(x_n)(x_n - x_{n-1})}{f(x_n) - f(x_{n-1})} $$

Here:

  • \(x_n\) and \(x_{n-1}\)​ are the two most recent estimates of the root.
  • \(f(x_n)\) and \(f(x_{n-1})\) are the function values at these points.

This process is repeated until the difference between successive approximations is smaller than a predefined tolerance or until the function value at the current estimate is sufficiently close to zero.

Use case: Square root

For \(m=2\)

$$ \begin{align} m &= 2 \\ f(x) &= x^2 - m \\ x0_{0} &= m \\ x1_{0} &= m-1 \\ x2_{n} &= x1_{n} - \frac{f(x1_{n})(x1_{n} - x0_{n})}{f(x1_{n}) - f(x0_{n})} \\ x0_{n+1} &= x1_{n} \\ x1_{n+1} &= x2_{n} \\ \end{align} $$$$ \begin{align} x0_{0}&=2,0 &x1_{0}&=1,0 &x2_{0}&=1,33333333 &fx0_{0}&=2,0 &fx1_{0}&=-1,0 &e_{0}&=0,33333333\\ x0_{1}&=1,0 &x1_{1}&=1,33333333 &x2_{1}&=1,42857143 &fx0_{1}&=-1,0 &fx1_{1}&=-0,22222222 &e_{1}&=0,0952381\\ x0_{2}&=1,33333333 &x1_{2}&=1,42857143 &x2_{2}&=1,4137931 &fx0_{2}&=-0,22222222 &fx1_{2}&=0,04081633 &e_{2}&=0,01477833\\ x0_{3}&=1,42857143 &x1_{3}&=1,4137931 &x2_{3}&=1,41421144 &fx0_{3}&=0,04081633 &fx1_{3}&=-0,00118906 &e_{3}&=0,00041834\\ x0_{4}&=1,4137931 &x1_{4}&=1,41421144 &x2_{4}&=1,41421356 &fx0_{4}&=-0,00118906 &fx1_{4}&=-0,00000601 &e_{4}&=0,00000212\\ x0_{5}&=1,41421144 &x1_{5}&=1,41421356 &x2_{5}&=1,41421356 &fx0_{5}&=-0,00000601 &fx1_{5}&=0,0 &e_{5}&=0,0\\ x0_{6}&=1,41421356 &x1_{6}&=1,41421356 &x2_{6}&=1,41421356 &fx0_{6}&=0,0 &fx1_{6}&=0,0 &e_{6}&=0,0\\ \\ &&\sqrt{2}&=1,41421356 \end{align} $$

For \(m=13\)

$$ \begin{align} x0_{0}&=13,0 &x1_{0}&=12,0 &x2_{0}&=12,0 &fx0_{0}&=156,0 &fx1_{0}&=131,0 &e_{0}&=5,24\\ x0_{1}&=12,0 &x1_{1}&=6,76 &x2_{1}&=6,76 &fx0_{1}&=131,0 &fx1_{1}&=32,6976 &e_{1}&=1,74294243\\ x0_{2}&=6,76 &x1_{2}&=5,01705757 &x2_{2}&=5,01705757 &fx0_{2}&=32,6976 &fx1_{2}&=12,17086665 &e_{2}&=1,03343867\\ x0_{3}&=5,01705757 &x1_{3}&=3,9836189 &x2_{3}&=3,9836189 &fx0_{3}&=12,17086665 &fx1_{3}&=2,86921957 &e_{3}&=0,31877821\\ x0_{4}&=3,9836189 &x1_{4}&=3,66484069 &x2_{4}&=3,66484069 &fx0_{4}&=2,86921957 &fx1_{4}&=0,43105728 &e_{4}&=0,05635871\\ x0_{5}&=3,66484069 &x1_{5}&=3,60848198 &x2_{5}&=3,60848198 &fx0_{5}&=0,43105728 &fx1_{5}&=0,02114223 &e_{5}&=0,00290682\\ x0_{6}&=3,60848198 &x1_{6}&=3,60557517 &x2_{6}&=3,60557517 &fx0_{6}&=0,02114223 &fx1_{6}&=0,00017227 &e_{6}&=0,00002388\\ x0_{7}&=3,60557517 &x1_{7}&=3,60555129 &x2_{7}&=3,60555129 &fx0_{7}&=0,00017227 &fx1_{7}&=0,00000007 &e_{7}&=0,00000001\\ x0_{8}&=3,60555129 &x1_{8}&=3,60555128 &x2_{8}&=3,60555128 &fx0_{8}&=0,00000007 &fx1_{8}&=0,0 &e_{8}&=0,0\\ x0_{9}&=3,60555128 &x1_{9}&=3,60555128 &x2_{9}&=3,60555128 &fx0_{9}&=0,0 &fx1_{9}&=0,0 &e_{9}&=0,0\\ \\ &&\sqrt{13}&=3,60555128 \end{align} $$

For \(m=354\)

$$ \begin{align} x0_{0}&=354,0 &x1_{0}&=353,0 &x2_{0}&=353,0 &fx0_{0}&=124962,0 &fx1_{0}&=124255,0 &e_{0}&=175,74964639\\ x0_{1}&=353,0 &x1_{1}&=177,25035361 &x2_{1}&=177,25035361 &fx0_{1}&=124255,0 &fx1_{1}&=31063,68785373 &e_{1}&=58,5830592\\ x0_{2}&=177,25035361 &x1_{2}&=118,66729441 &x2_{2}&=118,66729441 &fx0_{2}&=31063,68785373 &fx1_{2}&=13727,92676292 &e_{2}&=46,39103769\\ x0_{3}&=118,66729441 &x1_{3}&=72,27625672 &x2_{3}&=72,27625672 &fx0_{3}&=13727,92676292 &fx1_{3}&=4869,85728538 &e_{3}&=25,5041726\\ x0_{4}&=72,27625672 &x1_{4}&=46,77208412 &x2_{4}&=46,77208412 &fx0_{4}&=4869,85728538 &fx1_{4}&=1833,62785264 &e_{4}&=15,40238058\\ x0_{5}&=46,77208412 &x1_{5}&=31,36970354 &x2_{5}&=31,36970354 &fx0_{5}&=1833,62785264 &fx1_{5}&=630,05830017 &e_{5}&=8,06301365\\ x0_{6}&=31,36970354 &x1_{6}&=23,30668989 &x2_{6}&=23,30668989 &fx0_{6}&=630,05830017 &fx1_{6}&=189,20179382 &e_{6}&=3,46039272\\ x0_{7}&=23,30668989 &x1_{7}&=19,84629717 &x2_{7}&=19,84629717 &fx0_{7}&=189,20179382 &fx1_{7}&=39,8755115 &e_{7}&=0,92404986\\ x0_{8}&=19,84629717 &x1_{8}&=18,92224732 &x2_{8}&=18,92224732 &fx0_{8}&=39,8755115 &fx1_{8}&=4,05144353 &e_{8}&=0,10450337\\ x0_{9}&=18,92224732 &x1_{9}&=18,81774395 &x2_{9}&=18,81774395 &fx0_{9}&=4,05144353 &fx1_{9}&=0,10748728 &e_{9}&=0,0028481\\ x0_{10}&=18,81774395 &x1_{10}&=18,81489585 &x2_{10}&=18,81489585 &fx0_{10}&=0,10748728 &fx1_{10}&=0,00030575 &e_{10}&=0,00000812\\ x0_{11}&=18,81489585 &x1_{11}&=18,81488772 &x2_{11}&=18,81488772 &fx0_{11}&=0,00030575 &fx1_{11}&=0,00000002 &e_{11}&=0,0\\ x0_{12}&=18,81488772 &x1_{12}&=18,81488772 &x2_{12}&=18,81488772 &fx0_{12}&=0,00000002 &fx1_{12}&=0,0 &e_{12}&=0,0\\ \\ &&\sqrt{354}&=18,81488772 \end{align} $$

Code examples

The repo with examples for these algorithms is here. I won’t dive deep into the code in this article, but feel free to contact me directly if you have any doubts or suggestions, but I want you try to run the code and the benchmarks so we can take a look at the results in the next section.

Follow these steps:

# clone the repo
git clone https://github.com/padiazg/root-finding-algorithms-examples.git

# move into the folder
cd root-finding-algorithms-examples/part-2

# run the examples
go run main.go bisection.go newton-raphson.go secant.go --show-summary --values 2,13,354

# run the benchmarks
go test -bench=.

Benchmarks

Once you have cloned and run the examples, let’s take a look at the results

$ go run main.go bisection.go newton-raphson.go secant.go --show-summary --values 2,13,354
threshold: 0.0000001 | max-iter: 64
+-------+----------------+--------------------------+------------+
| VALUE |    ALGORITHM   |          RESULT          | ITERATIONS |
+-------+----------------+--------------------------+------------+
|     2 | Bisection      |                1.4142136 |         24 |
|       +----------------+--------------------------+------------+
|       | Newton-Raphson |                1.4142136 |          4 |
|       +----------------+--------------------------+------------+
|       | Secant         |                1.4142136 |          5 |
+-------+----------------+--------------------------+------------+
|    13 | Bisection      |                3.6055514 |         26 |
|       +----------------+--------------------------+------------+
|       | Newton-Raphson |                3.6055513 |          5 |
|       +----------------+--------------------------+------------+
|       | Secant         |                3.6055513 |          7 |
+-------+----------------+--------------------------+------------+
|   354 | Bisection      |               18.8148878 |         31 |
|       +----------------+--------------------------+------------+
|       | Newton-Raphson |               18.8148877 |          8 |
|       +----------------+--------------------------+------------+
|       | Secant         |               18.8148877 |         11 |
+-------+----------------+--------------------------+------------+

$ go test -bench=.
goos: darwin
goarch: amd64
pkg: github.com/padiazg/go-aproximation-demo
cpu: Intel(R) Core(TM) i9-9980HK CPU @ 2.40GHz
BenchmarkSqrtBisection2-16                 	 1561058	       733.2 ns/op
BenchmarkSqrtBisection16-16                	 1397647	       859.2 ns/op
BenchmarkSqrtBisection32-16                	 1418907	       849.9 ns/op
BenchmarkSqrtBisection79543-16             	  949737	      1286 ns/op
BenchmarkSqrtBisection6632888162-16        	  632889	      1679 ns/op
BenchmarkSqrtNewtonRaphson2-16             	80412462	        14.47 ns/op
BenchmarkSqrtNewtonRaphson16-16            	58465778	        20.13 ns/op
BenchmarkSqrtNewtonRaphson32-16            	47134106	        24.45 ns/op
BenchmarkSqrtNewtonRaphson79543-16         	23997736	        48.41 ns/op
BenchmarkSqrtNewtonRaphson6632888162-16    	11614274	        99.88 ns/op
BenchmarkSqrtSecant2-16                    	39359683	        27.15 ns/op
BenchmarkSqrtSecant16-16                   	28226810	        39.72 ns/op
BenchmarkSqrtSecant32-16                   	25197651	        48.48 ns/op
BenchmarkSqrtSecant79543-16                	10315800	       113.1 ns/op
BenchmarkSqrtSecant6632888162-16           	 6023776	       196.7 ns/op
PASS
ok  	github.com/padiazg/go-aproximation-demo	21.194s

As we predicted in theory, Newton-Raphson outperforms Bisection and Secant, but Secant falls behind it for just small margin.

Here are some key observations:

  1. Accuracy:
    • All three algorithms converge to highly accurate approximations of the square root (e.g., \(\sqrt{2} \approx 1.4142136\)).
    • Small differences in the last decimal place result from algorithm-specific behavior or computational precision.
  2. Iterations:
    • Bisection: Requires the most iterations (24 for \(\sqrt{2}\)​, 26 for \(\sqrt{13}\)​, and 31 for \(\sqrt{354}\)​). This is due to its linear convergence rate, which makes it less efficient compared to the other methods.
    • Newton-Raphson: Achieves the same level of accuracy in significantly fewer iterations (4 for \(\sqrt{2}\)​, 5 for \(\sqrt{13}\) ​, and 8 for \(\sqrt{354}\)​) because of its quadratic convergence rate.
    • Secant: Falls between Bisection and Newton -Raphson in terms of iterations (5 for \(\sqrt{2}\)​, 7 for \(\sqrt{13}\)​, and 11 for \(\sqrt{354}\)​), benefiting from superlinear convergence without requiring derivative calculations.
  3. Benchmarks
    • Bisection: The computational cost grows moderately with larger values (e.g., 733 ns/op for \(\sqrt{2}\)​ vs. 1679 ns/op for )\sqrt{6632888162}$).
    • Newton-Raphson: Outperforms both Bisection and Secant, with the lowest execution times across all values (e.g., 14.47 ns/op for \(\sqrt{2}\), 99.88 ns/op for \(\sqrt{6632888162}\)).
    • Secant: Faster than Bisection but slower than Newton-Raphson (e.g., 27.15 ns/op for \(\sqrt{2}\), 196.7 ns/op for \(\sqrt{6632888162}\)).

Given this data, which one you should pick depends on the theory we mentioned in the previous article:

  • If you have access to the derivative of function you definitely should pick Newton-Raphson
  • If the derivative is not available, or too hard to get, a good candidate is Secant as it performs very close to Newton-Rapson
  • If none of above is possible, then you fall back to BIsection, shich is safer and has an assured convergence if you can guess correctly the brackets for the function.

Conclusion

In this article we explored the Bisection, Newton-Raphson, and Secant methods. Each algorithm offers unique advantages:

  • Bisection ensures convergence but converges linearly, making it a robust yet slower option.
  • Newton-Raphson demonstrates quadratic convergence, achieving results swiftly if a good initial guess is available and the function’s derivative is well-behaved.
  • Secant offers a balance between computational cost and convergence rate, requiring no derivative calculation while converging super-linearly.

Through the practical example of calculating square roots, we illustrated the strengths and limitations of these methods in numerical problem-solving. As we progress in this series, we will delve into some more specific examples and how they can be used in real world use cases.