.. _sphx_glr_api_gallery_numerical_analysis_root_finding:

Root finding
------------

The Babylonian square-root rule and bisection, Newton-Raphson's tangent
iteration, Halley's cubically convergent method, and Aitken/Steffensen
acceleration, each with its empirical convergence order measured.


.. raw:: html

  <div id='sg-tag-list' class='sphx-glr-tag-list'></div>


.. raw:: html

    <div class="sphx-glr-thumbnails">

.. thumbnail-parent-div-open

.. raw:: html

    <div class="sphx-glr-thumbcontainer" tooltip="Old Babylonian tablets give \sqrt{2} to about six decimal places. The rule Heron of Alexandria later wrote down averages a guess with a divided by the guess, x_{n+1} = \tfrac12(x_n + a/x_n). Bisection needs even less: it halves a bracket [a, b] on which f changes sign, relying only on the intermediate value theorem. This script computes \sqrt{2} both ways and shows the bracket shrinking by exactly half per step, against the Babylonian rule&#x27;s doubling of correct digits.">

.. only:: html

  .. image:: /api/gallery/numerical_analysis/root_finding/images/thumb/sphx_glr_plot_01_babylonian_bisection_thumb.png
    :alt:

  :doc:`/api/gallery/numerical_analysis/root_finding/plot_01_babylonian_bisection`

.. raw:: html

      <div class="sphx-glr-thumbnail-title">The Babylonian square root and bisection</div>
    </div>


.. raw:: html

    <div class="sphx-glr-thumbcontainer" tooltip="Newton and Raphson&#x27;s iteration replaces f by its tangent line at the current guess and steps to where that line crosses zero, x_{n+1} = x_n - f(x_n)/f&#x27;(x_n). This script draws the first tangent steps for f(x) = x^3 - 2x - 5 (the cubic Newton himself used as his example) and shows the number of correct digits roughly doubling at every step, i.e. convergence of order 2.">

.. only:: html

  .. image:: /api/gallery/numerical_analysis/root_finding/images/thumb/sphx_glr_plot_02_newton_raphson_thumb.png
    :alt:

  :doc:`/api/gallery/numerical_analysis/root_finding/plot_02_newton_raphson`

.. raw:: html

      <div class="sphx-glr-thumbnail-title">Newton-Raphson's method: tangent lines and quadratic convergence</div>
    </div>


.. raw:: html

    <div class="sphx-glr-thumbcontainer" tooltip="Edmond Halley&#x27;s 1694 iteration uses the second derivative as well as the first, stepping to the root of an osculating hyperbola instead of a tangent line. Near a simple root it triples the number of correct digits per step, against Newton&#x27;s doubling. This script solves x^3 = 2 with both methods from the same starting guess and compares their error histories and empirical convergence orders.">

.. only:: html

  .. image:: /api/gallery/numerical_analysis/root_finding/images/thumb/sphx_glr_plot_03_halley_method_thumb.png
    :alt:

  :doc:`/api/gallery/numerical_analysis/root_finding/plot_03_halley_method`

.. raw:: html

      <div class="sphx-glr-thumbnail-title">Halley's method: cubic convergence</div>
    </div>


.. raw:: html

    <div class="sphx-glr-thumbcontainer" tooltip="Aitken&#x27;s \Delta^2 process (1926) extrapolates a linearly convergent sequence from three consecutive terms. Applied to the slowly converging Leibniz series for \pi, one pass gains several digits. Steffensen&#x27;s method (1933) applies the same extrapolation inside a fixed-point iteration, turning the linear convergence of x_{n+1} = \cos x_n into quadratic convergence without any derivative.">

.. only:: html

  .. image:: /api/gallery/numerical_analysis/root_finding/images/thumb/sphx_glr_plot_04_aitken_steffensen_thumb.png
    :alt:

  :doc:`/api/gallery/numerical_analysis/root_finding/plot_04_aitken_steffensen`

.. raw:: html

      <div class="sphx-glr-thumbnail-title">Aitken's delta-squared process and Steffensen's method</div>
    </div>


.. thumbnail-parent-div-close

.. raw:: html

    </div>


.. toctree::
   :hidden:

   /api/gallery/numerical_analysis/root_finding/plot_01_babylonian_bisection
   /api/gallery/numerical_analysis/root_finding/plot_02_newton_raphson
   /api/gallery/numerical_analysis/root_finding/plot_03_halley_method
   /api/gallery/numerical_analysis/root_finding/plot_04_aitken_steffensen