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

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

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

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

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

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

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

 Για να αποδείξουμε ότι αυτό ισχύει γενικά, ας υποθέσουμε ότι το *P* είναι ένα πολυώνυμο βαθμού *N* που έχει την περιγραφόμενη ιδιότητα, δηλαδή ότι δίνει μια συνάρτηση σφάλματος που έχει *N*&nbsp;+&nbsp;2 ακρότατα, με εναλλασσόμενα πρόσημα και ίσα μεγέθη. Το κόκκινο γράφημα στα δεξιά δείχνει πώς μπορεί να μοιάζει αυτή η συνάρτηση σφάλματος για *N*&nbsp;=&nbsp;4. Ας υποθέσουμε ότι το *Q*(*x*) (του οποίου η συνάρτηση σφάλματος φαίνεται με μπλε χρώμα στα δεξιά) είναι ένα άλλο πολυώνυμο *Ν* βαθμού που αποτελεί καλύτερη προσέγγιση του *f* από το *P*. Συγκεκριμένα, το *Q* είναι πιο κοντά στο *f* από το *P* για κάθε τιμή *x<sub>i</sub>* όπου εμφανίζεται ένα ακρότατο των *P*-*f*, οπότε

:|Q(x_i)-f(x_i)|
Όταν το μέγιστο *P*−*f* εμφανίζεται στο *x<sub>i</sub>*, τότε
:Q(x_i)-f(x_i)\le|Q(x_i)-f(x_i)|
Και όταν ένα ελάχιστο *P*−*f* εμφανίζεται στο *x<sub>i</sub>*, τότε
:f(x_i)-Q(x_i)\le|Q(x_i)-f(x_i)|

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

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

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

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

:f(x) \sim \sum_{i=0}^\infty c_i T_i(x)

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

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

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

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

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

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

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

:\begin{align}
          P(x_1) - f(x_1) &= +\varepsilon \\
          P(x_2) - f(x_2) &= -\varepsilon \\
          P(x_3) - f(x_3) &= +\varepsilon \\
                          &\ \ \vdots \\
  P(x_{N+2}) - f(x_{N+2}) &= \pm\varepsilon.
\end{align}

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

Δηλαδή,

:\begin{align}
  P_0 + P_1 x_1 + P_2 x_1^2 + P_3 x_1^3 + \dots + P_N x_1^N - f(x_1) &= +\varepsilon \\
  P_0 + P_1 x_2 + P_2 x_2^2 + P_3 x_2^3 + \dots + P_N x_2^N - f(x_2) &= -\varepsilon \\
                                                                     &\ \ \vdots
\end{align}

Εφόσον δόθηκαν οι x_1, ..., x_{N+2}, όλες οι δυνάμεις τους είναι γνωστές και οι f(x_1), ..., f(x_{N+2}) είναι επίσης γνωστές. Αυτό σημαίνει ότι οι παραπάνω εξισώσεις είναι απλά *N*+2 γραμμικές εξισώσεις στις *N*+2 μεταβλητές P_0, P_1, ..., P_N, και \varepsilon. Δεδομένων των δοκιμαστικών σημείων x_1, ..., x_{N+2}, μπορεί κανείς να λύσει αυτό το σύστημα για να πάρει το πολυώνυμο *P* και τον αριθμό \varepsilon.

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

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

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

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

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

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

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

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

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

## Παραπομπές

*
*
*
*
*
*
*
*
*
*
*
* Ch. 1–6 of 2013 edition

## Πηγές
* 
* 
* 
* 
* 
* 
* 

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