Θεωρία προσέγγισης

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

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

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

Ο στόχος είναι να γίνει η προσέγγιση όσο το δυνατόν πιο κοντά στην πραγματική συνάρτηση, συνήθως με ακρίβεια που προσεγγίζει την ακρίβεια της υποκείμενης αριθμητικής κινητής υποδιαστολής του υπολογιστή. Αυτό επιτυγχάνεται με τη χρήση ενός πολυωνύμου υψηλού βαθμού και/ή περιορίζοντας το πεδίο στο οποίο το πολυώνυμο πρέπει να προσεγγίσει τη συνάρτηση. Ο περιορισμός του πεδίου μπορεί συχνά να γίνει με τη χρήση διαφόρων τύπων πρόσθεσης ή κλιμάκωσης για τη συνάρτηση που προσεγγίζεται. Οι σύγχρονες μαθηματικές βιβλιοθήκες συχνά μειώνουν το πεδίο σε πολλά μικροσκοπικά τμήματα και χρησιμοποιούν ένα πολυώνυμο χαμηλού βαθμού για κάθε τμήμα.


Βέλτιστα πολυώνυμα
Αφού επιλεγεί το πεδίο (συνήθως ένα διάστημα) και ο βαθμός του πολυωνύμου, το ίδιο το πολυώνυμο επιλέγεται με τέτοιο τρόπο ώστε να ελαχιστοποιείται το σφάλμα χειρότερης περίπτωσης. Δηλαδή, ο στόχος είναι να ελαχιστοποιηθεί η μέγιστη τιμή της , όπου P(x) είναι το προσεγγιστικό πολυώνυμο, f(x) είναι η πραγματική συνάρτηση και x μεταβάλλεται στο επιλεγμένο διάστημα. Για καλά συμπεριφερόμενες συναρτήσεις, υπάρχει ένα Nth βαθμού πολυώνυμο που θα οδηγήσει σε μια καμπύλη σφάλματος που ταλαντεύεται μπρος-πίσω μεταξύ  και  συνολικά N+2 φορές, δίνοντας ένα σφάλμα χειρότερης περίπτωσης . Βλέπουμε ότι υπάρχει ένα πολυώνυμο Nth βαθμού που μπορεί να παρεμβάλει N+1 σημεία σε μια καμπύλη. Το ότι ένα τέτοιο πολυώνυμο είναι πάντα βέλτιστο υποστηρίζεται από το θεώρημα της ισοταλάντωσης (equioscillation). Είναι δυνατόν να κατασκευαστούν τεχνητές συναρτήσεις f(x) για τις οποίες δεν υπάρχει τέτοιο πολυώνυμο, αλλά αυτές εμφανίζονται σπάνια στην πράξη.

Επί παραδείγματι, οι γραφικές παραστάσεις που παρουσιάζονται στα δεξιά δείχνουν το σφάλμα στην προσέγγιση των log(x) και exp(x) για N = 4. Οι κόκκινες καμπύλες, για το βέλτιστο πολυώνυμο, είναι επίπεδες, δηλαδή ταλαντεύονται μεταξύ  και  ακριβώς. Σε κάθε περίπτωση, ο αριθμός των ακρότατων είναι N+2, δηλαδή 6. Δύο από τα ακρότατα βρίσκονται στα ακραία σημεία του διαστήματος, στο αριστερό και στο δεξί άκρο των γραφημάτων.


Όταν το μέγιστο P−f εμφανίζεται στο xi, τότε

Και όταν ένα ελάχιστο P−f εμφανίζεται στο xi, τότε

Έτσι, όπως φαίνεται στο γράφημα, [P(x) − f(x)] − [Q(x) − f(x)] πρέπει να εναλλάσσονται ως προς το πρόσημο για τις N + 2 τιμές του xi. Αλλά η [P(x) − f(x)] − [Q(x) − f(x)]  ανάγεται στην P(x) − Q(x) που είναι ένα πολυώνυμο βαθμού N. Η συνάρτηση αυτή αλλάζει πρόσημο τουλάχιστον  N+1  φορές, οπότε, σύμφωνα με το θεώρημα των ενδιάμεσων τιμών, έχει N+1 μηδενικά, πράγμα αδύνατο για ένα πολυώνυμο βαθμού N.

Προσέγγιση Τσεμπίσεφ

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

Αν υπολογίσει κανείς τους συντελεστές στο ανάπτυγμα Τσεμπίσεφ για μια συνάρτηση: 

και στη συνέχεια κόβει τη σειρά μετά τον όρο , παίρνει κανείς ένα  Nth-βαθμού πολυώνυμο που προσεγγίζει το f(x).

Ο λόγος που αυτό το πολυώνυμο είναι σχεδόν βέλτιστο είναι ότι, για συναρτήσεις με ταχέως συγκλίνουσες δυναμοσειρές, εάν η σειρά αποκοπεί μετά από κάποιο όρο, το συνολικό σφάλμα που προκύπτει από την αποκοπή είναι κοντά στον πρώτο όρο μετά την αποκοπή. Με άλλα λόγια, ο πρώτος όρος μετά την αποκοπή κυριαρχεί σε όλους τους μεταγενέστερους όρους. Το ίδιο ισχύει και αν το ανάπτυγμα είναι σε όρους bucking πολυωνύμων. Εάν ένα ανάπτυγμα Τσεμπίσεφ αποκοπεί μετά το , το σφάλμα θα πάρει μια μορφή κοντά σε ένα πολλαπλάσιο του . Τα πολυώνυμα Τσεμπίσεφ έχουν την ιδιότητα ότι είναι επίπεδα - ταλαντώνονται μεταξύ +1 και -1 στο διάστημα [-1, 1].  έχει N+2 ακρότατα επιπέδων. Αυτό σημαίνει ότι το σφάλμα μεταξύ της f(x) και του αναπτύγματος Τσεμπίσεφ μέχρι το  είναι κοντά σε μια συνάρτηση επιπέδου με N+2 ακρότατα, οπότε είναι κοντά στο βέλτιστο N πολυώνυμο Nth βαθμού.

Στα παραπάνω γραφήματα, η μπλε συνάρτηση σφάλματος είναι μερικές φορές καλύτερη από την κόκκινη συνάρτηση (εντός αυτής), αλλά μερικές φορές χειρότερη, πράγμα που σημαίνει ότι δεν είναι ακριβώς το βέλτιστο πολυώνυμο. Η απόκλιση είναι λιγότερο σοβαρή για τη συνάρτηση exp, η οποία έχει μια εξαιρετικά γρήγορα συγκλίνουσα δυναμοσειρά, απ' ό,τι για τη συνάρτηση log.

Η προσέγγιση Τσεμπίσεφ είναι η βάση για την τετραγωνική εξίσωση Κλένσοου-Κέρτις, μια τεχνική αριθμητικής ολοκλήρωσης.

 Αλγόριθμος του Ρεμέζ
Ο αλγόριθμος Ρεμέζ (μερικές φορές γράφεται Ρεμές) χρησιμοποιείται για την παραγωγή ενός βέλτιστου πολυωνύμου P(x) που προσεγγίζει μια δεδομένη συνάρτηση f(x) σε ένα δεδομένο διάστημα. Είναι ένας επαναληπτικός αλγόριθμος που συγκλίνει σε ένα πολυώνυμο που έχει συνάρτηση σφάλματος με ακρότατα N+2 επιπέδων. Σύμφωνα με το παραπάνω θεώρημα, αυτό το πολυώνυμο είναι βέλτιστο.

Ο αλγόριθμος του Ρέμεζ χρησιμοποιεί το γεγονός ότι μπορεί κανείς να κατασκευάσει ένα πολυώνυμο 'Nth-βαθμού που οδηγεί σε τιμές σφάλματος επιπέδου και εναλλασσόμενες, δεδομένων N+2 σημείων δοκιμής.

Δίνονται N+2 σημεία δοκιμής , , ...  (όπου  και  είναι πιθανώς τα τελικά σημεία του διαστήματος προσέγγισης), οι εξισώσεις αυτές πρέπει να επιλυθούν:

Οι δεξιές πλευρές εναλλάσσονται ως προς το πρόσημο.

Δηλαδή,

Εφόσον δόθηκαν οι , ..., , όλες οι δυνάμεις τους είναι γνωστές και οι , ...,  είναι επίσης γνωστές. Αυτό σημαίνει ότι οι παραπάνω εξισώσεις είναι απλά N+2 γραμμικές εξισώσεις στις N+2 μεταβλητές , , ..., , και . Δεδομένων των δοκιμαστικών σημείων , ..., , μπορεί κανείς να λύσει αυτό το σύστημα για να πάρει το πολυώνυμο P και τον αριθμό .

Το παρακάτω γράφημα δείχνει ένα παράδειγμα αυτού, που παράγει ένα πολυώνυμο τέταρτου βαθμού που προσεγγίζει το  στο [-1, 1]. Τα δοκιμαστικά σημεία ορίστηκαν στο
−1, −0.7, −0.1, +0.4, +0.9, και 1.Οι τιμές αυτές εμφανίζονται με πράσινο χρώμα. Η προκύπτουσα τιμή της  is 4.43 × 10−4


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

Το δεύτερο βήμα του αλγορίθμου του Ρεμέζ συνίσταται στη μετακίνηση των σημείων δοκιμής στις προσεγγιστικές θέσεις όπου η συνάρτηση σφάλματος είχε τα πραγματικά τοπικά μέγιστα ή ελάχιστα. Παραδείγματος χάριν, μπορεί κανείς να καταλάβει κοιτάζοντας το γράφημα ότι το σημείο στο -0,1 θα έπρεπε να βρίσκεται περίπου στο -0,28. Ο τρόπος για να γίνει αυτό στον αλγόριθμο είναι να χρησιμοποιηθεί ένας μόνο γύρος της μεθόδου του Νεύτωνα. Εφόσον γνωρίζει κανείς την πρώτη και τη δεύτερη παράγωγο της , μπορεί να υπολογίσει κατά προσέγγιση πόσο μακριά πρέπει να μετακινηθεί ένα σημείο δοκιμής ώστε η παράγωγος να είναι μηδέν.

Ο υπολογισμός των παραγώγων ενός πολυωνύμου είναι απλός. Πρέπει επίσης να είναι κανείς σε θέση να υπολογίζει την πρώτη και τη δεύτερη παράγωγο της f(x). Ο αλγόριθμος του Ρεμέζ απαιτεί την ικανότητα υπολογισμού των ,  και  με εξαιρετικά υψηλή ακρίβεια. Ολόκληρος ο αλγόριθμος πρέπει να εκτελείται με μεγαλύτερη ακρίβεια από την επιθυμητή ακρίβεια του αποτελέσματος.

Μετά τη μετακίνηση των δοκιμαστικών σημείων, επαναλαμβάνεται το μέρος της γραμμικής εξίσωσης, παίρνοντας ένα νέο πολυώνυμο, και χρησιμοποιείται ξανά η μέθοδος του Νεύτωνα για να μετακινηθούν και πάλι τα δοκιμαστικά σημεία. Αυτή η ακολουθία συνεχίζεται μέχρι το αποτέλεσμα να συγκλίνει στην επιθυμητή ακρίβεια. Ο αλγόριθμος συγκλίνει πολύ γρήγορα. Η σύγκλιση είναι τετραγωνική για καλά συμπεριφερόμενες συναρτήσεις - αν τα σημεία δοκιμής βρίσκονται εντός  από το σωστό αποτέλεσμα, θα βρίσκονται περίπου εντός  από το σωστό αποτέλεσμα μετά τον επόμενο γύρο.

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

 Εξωτερικοί σύνδεσμοι 
English - Greek Dictionary of Pure and Applied Mathematics Εθνικό Μετσόβιο Πολυτεχνείο
Αγγλοελληνικό Λεξικό Μαθηματικής Ορολογίας - Πανεπιστήμιο Κύπρου
 Ευκλείδεια Γεωμετρία - Πανελλήνιο Σχολικό Δίκτυο
 Θεωρία ομάδων και Λι αλγεβρών -Εθνικό Αρχείο Διδακτορικών Διατριβών
 Θεωρία Αριθμών και Εφαρμογές
 Υπολογιστική Θεωρία Αριθμών
 Καμπυλότητες και γεωμετρία του Riemann σε διαφορίσιμες πολλαπλότητες Εθνικό Αρχείο Διδακτορικών Διατριβών

 Δείτε επίσης 
 Απαγορευτική αρχή του Πάουλι
 Ταχύτητα του φωτός
 Κινητική ενέργεια
 Αλγεβρική θεωρία αριθμών
 Διαφορική γεωμετρία
 Άρθουρ Στάνλεϋ Έντινγκτον
 Φυσικές επιστήμες
 Σουμπραμανιάν Τσαντρασεκάρ
 Ευκλείδειος χώρος
 Ντάνιελ Γκόρενσταϊν
 Σουμπραμανιάν Τσαντρασεκάρ
 Εφαρμοσμένα μαθηματικά
 Ειδική σχετικότητα
 Διακριτός μετασχηματισμός Φουριέ
 Θεμελιώδες θεώρημα αριθμητικής
 Αλγεβρική γεωμετρία
 Μιγαδικός αριθμός
 Άρθουρ Στάνλεϋ Έντινγκτον
 Μαξ Πλανκ

 Βιβλιογραφία












 Παραπομπές 

 Ch. 1–6 of 2013 edition

 Πηγές 








Κατηγορία:Αριθμητική ανάλυση 
Κατηγορία:Αλγόριθμοι 
Κατηγορία:Συναρτησιακή ανάλυση 
Κατηγορία:Εφαρμοσμένα μαθηματικά 
Κατηγορία:Μαθηματική ανάλυση 
Κατηγορία:Περιοχές των μαθηματικών 
Κατηγορία:Θεωρία αριθμών