The Runge Phenomenon: Polynomial Interpolation and Approximation Error

Το Φαινόμενο του Ρούνγκε: Πολυωνυμική Παρεμβολή και Σφάλματα Προσέγγισης

Πηγή έμπνευσης: Big Internet Math-Off 2018 (The Aperiodical)

Τα πολυώνυμα είναι από τις πιο «φιλικές» συναρτήσεις των μαθηματικών: παραγωγίζονται και ολοκληρώνονται εύκολα, υπολογίζονται γρήγορα σε έναν υπολογιστή και συμπεριφέρονται γενικά «καλά». Γι’ αυτό, όταν έχουμε μια πιο περίπλοκη συνάρτηση, είναι φυσικό να προσπαθούμε να τη προσεγγίσουμε με ένα πολυώνυμο.

Πολυωνυμική παρεμβολή: η βασική ιδέα

Έστω ότι έχουμε μια συνάρτηση f(x) ορισμένη στο διάστημα [-1, 1]. Διαλέγουμε n+1 σημεία στο διάστημα αυτό και υπολογίζουμε τις τιμές της f(x) εκεί. Υπάρχει τότε ένα και μοναδικό πολυώνυμο βαθμού το πολύ n που περνάει από όλα αυτά τα σημεία: αυτό λέγεται παρεμβαλλόμενο πολυώνυμο.

Διαισθητικά, θα περίμενε κανείς ότι αν πάρουμε πολλά σημεία (μεγαλύτερο n), η προσέγγιση θα γίνεται όλο και καλύτερη. Το φαινόμενο του Ρούνγκε μας δείχνει ότι αυτό δεν είναι πάντα αλήθεια.

Τι είναι το φαινόμενο του Ρούνγκε;

Αν επιλέξουμε τα σημεία μας ισαπέχοντα στο διάστημα [-1, 1] και πάρουμε αρκετά πολλά, τότε σε ορισμένες συναρτήσεις το πολυώνυμο παρεμβολής αρχίζει να κάνει μεγάλες ταλαντώσεις κοντά στα άκρα του διαστήματος, δηλαδή κοντά στο -1 και στο 1. Το σφάλμα γίνεται πολύ μεγάλο ακριβώς εκεί που θα θέλαμε να έχουμε καλή προσέγγιση.

Αυτό το «φούσκωμα» του σφάλματος κοντά στα άκρα ονομάζεται φαινόμενο του Ρούνγκε (Runge phenomenon), από τον Carl David Tolmé Runge, ο οποίος το περιέγραψε στις αρχές του 20ού αιώνα.

Το εκπληκτικό είναι ότι, όσο περισσότερα ισαπέχοντα σημεία παίρνουμε, τόσο χειρότερη μπορεί να γίνεται η προσέγγιση στα άκρα!

Πώς μπορούμε να το αποφύγουμε; Τα σημεία Chebyshev

Ευτυχώς, δεν είναι καταδικασμένη κάθε πολυωνυμική προσέγγιση. Το πρόβλημα δεν είναι τα πολυώνυμα, αλλά η επιλογή των σημείων.

Αντί να διαλέξουμε τα σημεία μας ισαπέχοντα, μπορούμε να τα τοποθετήσουμε πιο πυκνά κοντά στα άκρα, χρησιμοποιώντας τα λεγόμενα σημεία Chebyshev (από τον Pafnuty Chebyshev). Μια γεωμετρική περιγραφή είναι η εξής:

• παίρνουμε ισαπέχοντα σημεία πάνω σε έναν κύκλο,
• προβάλλουμε αυτά τα σημεία στον οριζόντιο άξονα,
• οι προβολές αυτές δίνουν τις x-συντεταγμένες των σημείων Chebyshev στο [-1, 1].

Με αυτά τα σημεία, το πολυώνυμο παρεμβολής γίνεται πολύ πιο σταθερό στα άκρα και το φαινόμενο του Ρούνγκε ουσιαστικά εξαφανίζεται για πολλές κλασικές συναρτήσεις.

Από τις συναρτήσεις… στα δεδομένα: ένα παράδειγμα με ψηφοφορίες

Για να δούμε πόσο χρήσιμη είναι αυτή η ιδέα, μπορούμε να κοιτάξουμε όχι μόνο «ωραίες» συναρτήσεις, αλλά και δεδομένα. Σε μια διαδικτυακή ψηφοφορία (όπως στον πρώτο γύρο του Big Internet Math-Off 2018), οι ψήφοι εξελίσσονται με την πάροδο του χρόνου: για κάθε χρονική στιγμή έχουμε έναν αριθμό ψήφων.

Αν προσπαθήσουμε να προσεγγίσουμε την καμπύλη των ψήφων:

• με 16 ισαπέχοντα σημεία στον χρόνο, η πολυωνυμική παρεμβολή μπορεί να «τρέμει» και να δίνει παράξενες καμπύλες,
• με 16 σημεία Chebyshev, η καμπύλη παρεμβολής είναι πολύ πιο κοντά στα πραγματικά δεδομένα.

Το ίδιο φαινόμενο: τα ισαπέχοντα σημεία επιτρέπουν στο πολυώνυμο να «ξεφύγει» στα άκρα, ενώ τα σημεία Chebyshev συγκρατούν αυτές τις ταλαντώσεις.

Το RungeBot: παίζοντας με το φαινόμενο

Για να πειραματιστεί κανείς με το φαινόμενο του Ρούνγκε και τα σημεία Chebyshev, δημιουργήθηκε ένα bot, το @RungeBot, που αρχικά λειτουργούσε στο Twitter και πλέον υπάρχει στο Mathstodon ως @RungeBot@mathstodon.xyz.

Η ιδέα είναι απλή: γράφετε μια συνάρτηση, για παράδειγμα f(x)=abs(x), και το bot επιστρέφει ένα διάγραμμα με:

• την παρεμβολή με ισαπέχοντα σημεία (που συνήθως εμφανίζει έντονο φαινόμενο Ρούνγκε),
• την παρεμβολή με σημεία Chebyshev (που τείνει να είναι πολύ πιο ομαλή).

Έτσι, το φαινόμενο του Ρούνγκε παύει να είναι απλώς ένα θεωρητικό παράδοξο και γίνεται ένα εργαλείο κατανόησης για το πώς να προσεγγίζουμε σωστά συναρτήσεις και δεδομένα με πολυώνυμα.

Συμπέρασμα

Το φαινόμενο του Ρούνγκε μας υπενθυμίζει ότι:

• περισσότερα δεδομένα δεν σημαίνουν αυτόματα καλύτερη προσέγγιση,
• η γεωμετρία της επιλογής των σημείων είναι κρίσιμη,
• τα πολυώνυμα είναι ισχυρά εργαλεία, αλλά χρειάζονται προσοχή.

Από τη θεωρία των συναρτήσεων μέχρι την ανάλυση πραγματικών δεδομένων, η σωστή επιλογή σημείων – όπως τα σημεία Chebyshev – μπορεί να κάνει τη διαφορά ανάμεσα σε μια ασταθή, ανακριβή προσέγγιση και σε μια σταθερή, αξιόπιστη μαθηματική μοντελοποίηση.

The Runge Phenomenon: Polynomial Interpolation and Approximation Errors

Inspired by a post for the Big Internet Math-Off 2018 (The Aperiodical)

Polynomials are among the most convenient functions in mathematics: they are easy to differentiate and integrate, they are fast to evaluate, and they behave nicely in numerical computations. For this reason, when we are given a more complicated function, it is natural to try to approximate it with a polynomial.

Polynomial interpolation: the basic idea

Suppose we have a function f(x) defined on the interval [-1, 1]. We choose n+1 points in this interval and sample the values of f(x) there. There is a unique polynomial of degree at most n that passes through all these points: this is called the interpolating polynomial.

Intuitively, one might expect that using more and more points (larger n) should always improve the approximation. The Runge phenomenon shows that this intuition can be very wrong.

What is the Runge phenomenon?

If we choose our sample points to be equally spaced on [-1, 1] and take a sufficiently large number of them, then for certain functions the interpolating polynomial starts to exhibit large oscillations near the endpoints -1 and 1. The error grows dramatically right where we would like the approximation to be good.

This blow-up of the error near the endpoints is called the Runge phenomenon, named after Carl David Tolmé Runge, who first described it in the early 20th century.

Surprisingly, as we increase the number of equally spaced points, the approximation near the endpoints can actually become worse.

A way out: Chebyshev nodes

Fortunately, not all polynomial approximations are doomed. The issue is not with polynomials themselves but with how we choose the interpolation points.

Instead of choosing equally spaced points, we can place them more densely near the endpoints, using what are known as Chebyshev nodes (named after Pafnuty Chebyshev). One geometric way to describe them is:

• take equally spaced points on a circle,
• project these points onto the horizontal axis,
• the projections give the x-coordinates of the Chebyshev nodes in [-1, 1].

With Chebyshev nodes, the interpolating polynomial becomes much more stable near the endpoints, and the Runge phenomenon essentially disappears for many classical functions.

From functions to data: an example with voting curves

To see how useful this idea is, we can look not only at “nice” functions, but also at real data. In an online poll (such as a round of the Big Internet Math-Off 2018), the number of votes for each candidate changes over time.

If we try to approximate the voting curve:

• using 16 equally spaced time points, the interpolating polynomial may oscillate wildly,
• using 16 Chebyshev nodes in time, the interpolation typically stays much closer to the actual data.

Again, equally spaced points allow the polynomial to “misbehave” near the edges of the interval, while Chebyshev nodes keep these oscillations under control.

RungeBot: playing with the phenomenon

To experiment with the Runge phenomenon and Chebyshev interpolation, a bot called @RungeBot was created. Originally built for Twitter, it now lives on Mathstodon as @RungeBot@mathstodon.xyz.

The idea is simple: you post a function, for example f(x)=abs(x), and the bot replies with a plot showing:

• interpolation using equally spaced points (often with a strong Runge effect),
• interpolation using Chebyshev nodes (usually much smoother and more accurate).

In this way, the Runge phenomenon stops being an abstract curiosity and becomes a practical lesson in how we should approximate functions and data using polynomials.

Conclusion

The Runge phenomenon reminds us that:

• more data points do not automatically mean a better approximation,
• the geometry of point placement is crucial,
• polynomials are powerful tools, but they must be used wisely.

From function approximation to real-world data modelling, choosing the right nodes – such as Chebyshev nodes – can make the difference between a highly oscillatory, unreliable approximation and a stable, trustworthy one.