.. DO NOT EDIT.
.. THIS FILE WAS AUTOMATICALLY GENERATED BY SPHINX-GALLERY.
.. TO MAKE CHANGES, EDIT THE SOURCE PYTHON FILE:
.. "api/gallery/numerical_analysis/root_finding/plot_04_aitken_steffensen.py"
.. LINE NUMBERS ARE GIVEN BELOW.

.. only:: html

    .. note::
        :class: sphx-glr-download-link-note

        :ref:`Go to the end <sphx_glr_download_api_gallery_numerical_analysis_root_finding_plot_04_aitken_steffensen.py>`
        to download the full example code.

.. rst-class:: sphx-glr-example-title

.. _sphx_glr_api_gallery_numerical_analysis_root_finding_plot_04_aitken_steffensen.py:


Aitken's delta-squared process and Steffensen's method
=========================================================

Aitken's :math:`\Delta^2` process (1926) extrapolates a linearly
convergent sequence from three consecutive terms. Applied to the slowly
converging Leibniz series for :math:`\pi`, one pass gains several digits.
Steffensen's method (1933) applies the same extrapolation *inside* a
fixed-point iteration, turning the linear convergence of
:math:`x_{n+1} = \cos x_n` into quadratic convergence without any
derivative.

.. GENERATED FROM PYTHON SOURCE LINES 15-20

.. code-block:: Python

    import matplotlib.pyplot as plt
    import numpy as np

    from mathematicskit.numerical_analysis import FixedPointIteration, Steffensen, aitken_delta_squared








.. GENERATED FROM PYTHON SOURCE LINES 21-23

Accelerating the Leibniz series
---------------------------------

.. GENERATED FROM PYTHON SOURCE LINES 23-38

.. code-block:: Python


    k = np.arange(30)
    partial = 4.0 * np.cumsum((-1.0) ** k / (2 * k + 1))
    once = aitken_delta_squared(partial)
    twice = aitken_delta_squared(once)

    fig, (ax1, ax2) = plt.subplots(1, 2, figsize=(10, 4.2))
    ax1.semilogy(k, np.abs(partial - np.pi), "o-", ms=3, label="partial sums")
    ax1.semilogy(k[2:], np.abs(once - np.pi), "s-", ms=3, label="Aitken once")
    ax1.semilogy(k[4:], np.abs(twice - np.pi), "^-", ms=3, label="Aitken twice")
    ax1.set_xlabel("$n$")
    ax1.set_ylabel(r"error in $\pi$")
    ax1.set_title("Leibniz series for $\\pi$")
    ax1.legend(fontsize=8)




.. image-sg:: /api/gallery/numerical_analysis/root_finding/images/sphx_glr_plot_04_aitken_steffensen_001.png
   :alt: Leibniz series for $\pi$
   :srcset: /api/gallery/numerical_analysis/root_finding/images/sphx_glr_plot_04_aitken_steffensen_001.png
   :class: sphx-glr-single-img


.. rst-class:: sphx-glr-script-out

 .. code-block:: none


    <matplotlib.legend.Legend object at 0x1196e3770>



.. GENERATED FROM PYTHON SOURCE LINES 39-41

Steffensen vs. plain fixed-point iteration for :math:`x = \cos x`
--------------------------------------------------------------------

.. GENERATED FROM PYTHON SOURCE LINES 41-59

.. code-block:: Python


    plain = FixedPointIteration(np.cos, x0=1.0, tol=1e-14).solve()
    steff = Steffensen(np.cos, x0=1.0, tol=1e-14).solve()
    x_star = steff.root

    for result, label in ((plain, "fixed-point (linear)"), (steff, "Steffensen (quadratic)")):
        err = np.maximum(np.abs(result.history - x_star), 1e-17)
        ax2.semilogy(err, "o-", ms=3, label=label)
    ax2.set_xlabel("iteration $n$")
    ax2.set_ylabel(r"$|x_n - x^*|$")
    ax2.set_title(r"Fixed point of $\cos x$")
    ax2.legend(fontsize=8)
    fig.tight_layout()

    print(f"30 Leibniz terms: error {abs(partial[-1] - np.pi):.1e}; Aitken twice: {abs(twice[-1] - np.pi):.1e}")
    print(f"fixed-point iterations: {plain.iterations}, Steffensen iterations: {steff.iterations}")

    plt.show()




.. rst-class:: sphx-glr-script-out

 .. code-block:: none

    30 Leibniz terms: error 3.3e-02; Aitken twice: 1.1e-08
    fixed-point iterations: 81, Steffensen iterations: 5





.. rst-class:: sphx-glr-timing

   **Total running time of the script:** (0 minutes 0.114 seconds)


.. _sphx_glr_download_api_gallery_numerical_analysis_root_finding_plot_04_aitken_steffensen.py:

.. only:: html

  .. container:: sphx-glr-footer sphx-glr-footer-example

    .. container:: sphx-glr-download sphx-glr-download-jupyter

      :download:`Download Jupyter notebook: plot_04_aitken_steffensen.ipynb <plot_04_aitken_steffensen.ipynb>`

    .. container:: sphx-glr-download sphx-glr-download-python

      :download:`Download Python source code: plot_04_aitken_steffensen.py <plot_04_aitken_steffensen.py>`

    .. container:: sphx-glr-download sphx-glr-download-zip

      :download:`Download zipped: plot_04_aitken_steffensen.zip <plot_04_aitken_steffensen.zip>`


.. only:: html

 .. rst-class:: sphx-glr-signature

    `Gallery generated by Sphinx-Gallery <https://sphinx-gallery.github.io>`_