Editing Runge's phenomenon (section)

==Mitigations==

===Change of interpolation points===
The oscillation can be minimized by using nodes that are distributed more densely towards the edges of the interval, specifically, with asymptotic density (on the interval <math>[-1,1]</math>) given by the formula<ref>{{Citation | last1=Berrut | first1=Jean-Paul | last2=Trefethen | first2=Lloyd N. | author2-link=Lloyd N. Trefethen | title=Barycentric Lagrange interpolation | doi=10.1137/S0036144502417715 | year=2004 | journal=SIAM Review | issn=1095-7200 | volume=46 | pages=501–517 | issue=3| bibcode=2004SIAMR..46..501B | citeseerx=10.1.1.15.5097 }}</ref>
:<math>\frac{1}{\sqrt{1-x^2}}</math>.
A standard example of such a set of nodes is [[Chebyshev nodes]], for which the maximum error in approximating the Runge function is guaranteed to diminish with increasing polynomial order.

===S-Runge algorithm without resampling===
When equidistant samples must be used because resampling on well-behaved sets of nodes is not feasible, the S-Runge algorithm can be considered.<ref name="FakeNodes">
{{citation
|first1 = Stefano
|last1 = De Marchi | author1-link = Stefano De Marchi
|first2 = Francesco
|last2 = Marchetti
|first3 = Emma
|last3 = Perracchione
|first4 = Davide
|last4 = Poggiali
|title = Polynomial interpolation via mapped bases without resampling
|doi = 10.1016/j.cam.2019.112347
|journal = J. Comput. Appl. Math.
|volume = 364
|year = 2020
|issn = 0377-0427
|doi-access = free
}}
</ref> In this approach, the original set of nodes is mapped on the set of [[Chebyshev nodes]], providing a stable polynomial reconstruction. The peculiarity of this method is that there is no need of resampling at the mapped nodes, which are also called ''[[fake nodes]]''. A [[Python (programming language)|Python]] implementation of this procedure can be found [https://github.com/pog87/FakeNodes here].

===Use of piecewise polynomials===
The problem can be avoided by using [[spline curve]]s which are piecewise polynomials. When trying to decrease the interpolation error one can increase the number of polynomial pieces which are used to construct the spline instead of increasing the degree of the polynomials used.

===Constrained minimization===
One can also fit a polynomial of higher degree (for instance, with <math>n</math> points use a polynomial of order <math>N = n^2</math> instead of <math>n + 1</math>), and fit an interpolating polynomial whose first (or second) derivative has minimal [[Lp space|<math>L^2</math> norm]].

A similar approach is to minimize a constrained version of the <math>L^p</math> distance between the polynomial's <math>m</math>-th derivative and the mean value of its <math>m</math>-th derivative. Explicitly, to minimize
:<math>
V_p = \int_a^b \left|\frac{\mathrm{d}^m P_N(x)}{\mathrm{d} x^m} - \frac{1}{b-a} \int_a^b  \frac{\mathrm{d}^m P_N(z)}{\mathrm{d} z^m} \mathrm{d}z\right|^p \mathrm{d} x - \sum_{i=1}^n \lambda_i \, \left(P_N(x_i) - f(x_i)\right),
</math>
where <math> N \ge n - 1</math> and <math> m < N </math>, with respect to the polynomial coefficients and the [[Lagrange multiplier]]s, <math>\lambda_i</math>. When <math>N = n - 1</math>, the constraint equations generated by the Lagrange multipliers reduce <math>P_N(x)</math> to the minimum polynomial that passes through all <math>n</math> points. At the opposite end, <math>\lim_{N \to \infty} P_N(x)</math> will approach a form very similar to a piecewise polynomials approximation. When <math>m=1</math>, in particular, <math>\lim_{N \to \infty} P_N(x)</math> approaches the linear piecewise polynomials, i.e. connecting the interpolation points with straight lines.

The role played by <math>p</math> in the process of minimizing <math>V_p</math> is to control the importance of the size of the fluctuations away from the mean value. The larger <math>p</math> is, the more large fluctuations are penalized compared to small ones. The greatest advantage of the Euclidean norm, <math>p=2</math>, is that it allows for analytic solutions and it guarantees that <math>V_p</math> will only have a single minimum. When <math>p\neq 2</math> there can be multiple minima in <math>V_p</math>, making it difficult to ensure that a particular minimum found will be the [[Maxima and minima|global minimum]] instead of a local one.

===Least squares fitting===
{{main|Polynomial fit}}
Another method is fitting a polynomial of lower degree using the method of [[least squares]]. Generally, when using <math>m</math> equidistant points, if <math>N < 2\sqrt{m}</math> then least squares approximation <math>P_N(x)</math> is well-conditioned.<ref>{{Citation | last1=Dahlquist | first1=Germund | last2=Björk | first2=Åke | author1-link=Germund Dahlquist | title=Numerical Methods | year=1974 | isbn=0-13-627315-7 | chapter=4.3.4. Equidistant Interpolation and the Runge Phenomenon | pages=[https://archive.org/details/numericalmethods00dahl/page/101 101–103] | url-access=registration | url=https://archive.org/details/numericalmethods00dahl/page/101 }}</ref>

===Bernstein polynomial===
Using [[Bernstein polynomial]]s, one can uniformly approximate every continuous function in a closed interval, although this method is rather computationally expensive.{{Citation needed|date=December 2019}}

===External fake constraints interpolation===
This method proposes to optimally stack a dense distribution of constraints of the type {{math|1=''P''&Prime;(''x'') = 0}} on nodes positioned externally near the endpoints of each side of the interpolation interval, where P"(x) is the second derivative of the interpolation polynomial. Those constraints are called External Fake Constraints as they do not belong to the interpolation interval and they do not match the behaviour of the Runge function. The method has demonstrated that it has a better interpolation performance than Piecewise polynomials (splines) to mitigate the Runge phenomenon.<ref>{{citation | last1 = Belanger | first1 = Nicolas | title = External Fake Constraints Interpolation: the end of Runge phenomenon with high degree polynomials relying on equispaced nodes – Application to aerial robotics motion planning    | publisher = Proceedings of the 5th Institute of Mathematics and its Applications Conference on Mathematics in Defence | year = 2017 | url = https://cdn.ima.org.uk/wp/wp-content/uploads/2017/03/Belanger-paper.pdf}}</ref>