.. DO NOT EDIT.
.. THIS FILE WAS AUTOMATICALLY GENERATED BY SPHINX-GALLERY.
.. TO MAKE CHANGES, EDIT THE SOURCE PYTHON FILE:
.. "api/gallery/numerical_analysis/chebyshev/plot_01_runge_phenomenon.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_chebyshev_plot_01_runge_phenomenon.py>`
        to download the full example code.

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

.. _sphx_glr_api_gallery_numerical_analysis_chebyshev_plot_01_runge_phenomenon.py:


Runge's phenomenon: equally spaced interpolation diverges
=========================================================

Carl Runge's 1901 example :math:`f(x) = 1/(1+25x^2)` is smooth on
:math:`[-1, 1]`, yet interpolating it at *more* equally spaced nodes
makes the fit *worse*: oscillations near the endpoints grow without
bound as the degree increases. This script shows the overshoot for
growing degree, the maximum error blowing up, and the exponentially
growing Lebesgue constant of equally spaced nodes that causes it.

.. GENERATED FROM PYTHON SOURCE LINES 14-21

.. code-block:: Python

    import matplotlib.pyplot as plt
    import numpy as np

    from mathematicskit.numerical_analysis import LagrangeInterpolant, runge_function
    from mathematicskit.numerical_analysis.systems.chebyshev import runge_phenomenon_errors
    from mathematicskit.numerical_analysis.utils.error_analysis import lebesgue_constant








.. GENERATED FROM PYTHON SOURCE LINES 22-24

More equally spaced nodes, bigger wiggles
-----------------------------------------

.. GENERATED FROM PYTHON SOURCE LINES 24-39

.. code-block:: Python


    x_fine = np.linspace(-1.0, 1.0, 600)
    fig1, ax1 = plt.subplots(figsize=(7, 4.5))
    ax1.plot(x_fine, runge_function(x_fine), color="black", lw=2, label=r"$f(x) = 1/(1+25x^2)$")
    for n, color in ((6, "goldenrod"), (11, "darkorange"), (16, "firebrick")):
        nodes = np.linspace(-1.0, 1.0, n)
        p = LagrangeInterpolant(nodes, runge_function(nodes))
        ax1.plot(x_fine, p.evaluate(x_fine), color=color, label=f"degree {n - 1}, equally spaced")
        ax1.plot(nodes, runge_function(nodes), "o", ms=3, color=color)
    ax1.set_ylim(-2.5, 2.5)
    ax1.set_xlabel("$x$")
    ax1.set_title("Runge's phenomenon: oscillations grow near the endpoints")
    ax1.legend(fontsize=8)
    fig1.tight_layout()




.. image-sg:: /api/gallery/numerical_analysis/chebyshev/images/sphx_glr_plot_01_runge_phenomenon_001.png
   :alt: Runge's phenomenon: oscillations grow near the endpoints
   :srcset: /api/gallery/numerical_analysis/chebyshev/images/sphx_glr_plot_01_runge_phenomenon_001.png
   :class: sphx-glr-single-img





.. GENERATED FROM PYTHON SOURCE LINES 40-42

The maximum error diverges with degree
--------------------------------------

.. GENERATED FROM PYTHON SOURCE LINES 42-55

.. code-block:: Python


    degrees = [5, 10, 15, 20, 25, 30]
    equal_errors, _ = runge_phenomenon_errors(degrees)
    for d, e in zip(degrees, equal_errors):
        print(f"degree={d:2d}  equally spaced max |error| = {e:.3e}")

    fig2, ax2 = plt.subplots(figsize=(6, 4))
    ax2.semilogy(degrees, equal_errors, "o-", color="firebrick")
    ax2.set_xlabel("polynomial degree")
    ax2.set_ylabel(r"$\max |f - p_n|$")
    ax2.set_title("Equally spaced interpolation error grows without bound")
    fig2.tight_layout()




.. image-sg:: /api/gallery/numerical_analysis/chebyshev/images/sphx_glr_plot_01_runge_phenomenon_002.png
   :alt: Equally spaced interpolation error grows without bound
   :srcset: /api/gallery/numerical_analysis/chebyshev/images/sphx_glr_plot_01_runge_phenomenon_002.png
   :class: sphx-glr-single-img


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

 .. code-block:: none

    degree= 5  equally spaced max |error| = 4.327e-01
    degree=10  equally spaced max |error| = 1.916e+00
    degree=15  equally spaced max |error| = 2.107e+00
    degree=20  equally spaced max |error| = 5.977e+01
    degree=25  equally spaced max |error| = 7.576e+01
    degree=30  equally spaced max |error| = 2.385e+03




.. GENERATED FROM PYTHON SOURCE LINES 56-58

The cause: an exponentially growing Lebesgue constant
-----------------------------------------------------

.. GENERATED FROM PYTHON SOURCE LINES 58-63

.. code-block:: Python


    for n in (5, 10, 20, 30):
        print(f"n={n:2d} nodes  Lebesgue constant = {lebesgue_constant(np.linspace(-1.0, 1.0, n)):.2e}")

    plt.show()




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

 .. code-block:: none

    n= 5 nodes  Lebesgue constant = 2.21e+00
    n=10 nodes  Lebesgue constant = 1.78e+01
    n=20 nodes  Lebesgue constant = 5.89e+03
    n=30 nodes  Lebesgue constant = 3.45e+06





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

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


.. _sphx_glr_download_api_gallery_numerical_analysis_chebyshev_plot_01_runge_phenomenon.py:

.. only:: html

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

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

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

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

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

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

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


.. only:: html

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

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