Μέθοδος Όιλερ

Στα μαθηματικά και την υπολογιστική επιστήμη , η μέθοδος Όιλερ είναι μια πρώτης τάξης αριθμητική διαδικασία για την επίλυση συνήθων διαφορικών εξισώσεων (Σ.Δ.Ε.), με δεδομένη την αρχική τιμή . Είναι η πιο βασική μέθοδος για την ρητή αριθμητικής ολοκλήρωσης των συνήθων διαφορικών εξισώσεων και είναι η απλούστερη Runge-Kutta μέθοδο . Ονομάζεται μέθοδος Όιλερ απο το όνομα του Leonhard Euler, ο οποίος εμφανίζεται στο βιβλίο Institutionum του calculi Integralis (δημοσιεύθηκε 1768-1770).

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

Άτυπη γεωμετρική περιγραφή 

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

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

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

Διατύπωση της μεθόδου 

Θέλουμε να προσεγγίσουμε την λύση της αρχικής τιμής του προβλήματος

χρησιμοποιώντας τους πρώτους δύο όρους από την  επέκταση της σειράς Taylor του y, η οποία παρουσιάζει τη γραμμική προσέγγιση γύρω από το σημείο (t0,y(t0)) . Ένα βήμα της μεθόδου Όιλερ από το tn στο tn+1 = tn + h είναι

Η αξία της  είναι μια προσέγγιση της λύσης του Σ.Δ.Ε. στο χρόνο : . Η μέθοδος Euler είναι ρητή, δηλαδή η λύση του  είναι μια ρητή συνάρτηση  για .

Ενώ η μέθοδος του Όιλερ ενσωματώνει πρώτου βαθμού Συνήθεις Διαφορικές Εξισώσεις, κάθε Συνήθης Διαφορική Εξίσωση βαθμού N μπορεί να αναπαρασταθεί ως μία πρώτου βαθμού Συνήθης Διαφορική Εξίσωση:

,

Παρουσιάζουμε βοηθητικές μεταβλητές  και παίρνουμε την αντίστοιχη εξίσωση

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

Παράδειγμα 

Δίνεται η διαφορική εξίσωση

θα θέλαμε να χρησιμοποιήσουμε τη μέθοδο Όιλερ για την προσέγγιση .

Χρησιμοποιώντας μέγεθος βήματος ίση προς 1 (h = 1) 
Η μέθοδος Όιλερ είναι

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

Κάνοντας το παραπάνω βήμα, έχουμε βρει την κλίση της γραμμής που είναι εφαπτόμενη στην καμπύλη στο σημείο .
Υπενθυμίζουμε ότι η κλίση ορίζεται ως η μεταβολή  διαιρούμενη με τη μεταβολή , or .

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

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

Τα παραπάνω βήματα θα πρέπει να επαναληφθεί για να βρείτε ,  and .

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

{| class="wikitable"
|-
!  !!  !!  !! !!  !!  !! 
|-
| 0 || 1 || 0 || 1 || 1 || 1 || 2
|-
| 1 || 2 || 1 || 2 || 1 || 2 || 4
|-
| 2 || 4 || 2 || 4 || 1 || 4 || 8
|-
| 3 || 8 || 3 || 8 || 1 || 8 || 16
|}

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

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

{| class="wikitable"
|-
! Το μέγεθος του βήματος !! αποτέλεσμα της μεθόδου του Όιλερ !! σφάλμα
|-
| 1 || 16 || 38.598
|-
| 0.25 || 35.53 || 19.07
|-
| 0.1 || 45.26 || 9.34
|-
| 0.05 || 49.56 || 5.04
|-
| 0.025 || 51.98 || 2.62
|-
| 0.0125 || 53.26 || 1.34
|}

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

Άλλες μέθοδοι, όπως είναι η μέθοδος μέσου σημείου που επίσης, απεικονίζεται στα σχήματα, συμπεριφέρονται πιο ευνοϊκά: το σφάλμα της μεθόδου μέσου σημείου είναι χονδρικά ανάλογη με το τετράγωνο του μεγέθους βήματος. Για το λόγο αυτό, η μέθοδος Όιλερ λέγεται ότι είναι ένα πρώτης τάξης μέθοδος, ενώ η μέθοδος μέσου σημείου είναι δεύτερης τάξης.

Μπορούμε να προεκτείνουμε από τον παραπάνω πίνακα το μέγεθος του βήματος που απαιτείται για να πάρουμε μια απάντηση που είναι σωστή για τα τρία δεκαδικά ψηφία είναι περίπου 0,00001 , πράγμα που σημαίνει ότι χρειαζόμαστε 400.000 βήματα. Αυτός ο μεγάλος αριθμός των βημάτων συνεπάγεται υψηλό υπολογιστικό κόστος. Για το λόγο αυτό, οι άνθρωποι συνήθως χρησιμοποιούν εναλλακτικά , ανώτερης τάξης μεθόδους όπως μεθόδους Runge-Kuttas or γραμμικές μέθοδοι πολλαπλού βήματος, ειδικά αν μια υψηλή ακρίβεια είναι επιθυμητή.

Παραγωγή 

Η μέθοδος Όιλερ μπορεί να προκύψει έναν αριθμό τρόπων. Πρώτον, υπάρχει η γεωμετρική περιγραφή που αναφέρονται ανωτέρω.

Μια άλλη δυνατότητα είναι να εξετάσει την επέκταση της συνάρτησης Taylor  around :

Η διαφορική εξίσωση δηλώνει ότι. Αν αυτό υποκαθίσταται από την επέκταση Taylor και αν αγνοούνται η τετραγωνική και υψηλότερης τάξης οροι, προκυπτει η μέθοδος Όιλερ . Η επέκταση Taylor χρησιμοποιείται παρακάτω για να αναλύσει το σφάλμα της μεθόδου Όιλερ, και μπορεί να επεκταθεί για να παραχθεί η μέθοδος Runge–Kutta.

Μια στενά συνδεδεμένη παραγωγή είναι να αντικαταστήσει προς τα εμπρός διαφορά πεπερασμένων τον τύπο για την παράγωγο,

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

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

Τώρα κατά προσέγγιση το ολοκλήρωμα από την αριστερή ορθογώνια μέθοδο (με μόνο ένα ορθογώνιο):

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

Τοπικό σφάλμα αποκοπής 

Το Τοπικό σφάλμα αποκοπής της μεθόδου Euler είναι σφάλμα σε ένα μόνο βήμα. Είναι η διαφορά μεταξύ της αριθμητικής λυσης μετά από ένα βήμα, , και η ακριβής λύση κατά το χρόνο . Η αριθμητική λύση δίνεται από

Για την ακριβή λύση, χρησιμοποιούμε την επέκταση Taylor που αναφέρονται στην ενότητα παραγωγή πάνω από:

Η τοπική αποκοπή σφαλμάτων (ΤΑΣ) παρουσιάζεται με τη μέθοδο Euler και δίνεται από τη διαφορά μεταξύ αυτών των εξισώσεων:

Αυτό το αποτέλεσμα είναι έγκυρο εάν  έχει φραγμένη τρίτη παράγωγο.

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

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

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

Παγκόσμιο σφάλμα αποκοπής 

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

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

όπου  είναι ένα άνω όριο για τη δεύτερη παράγωγο  για το δεδομένο χρονικό διάστημα και είναι η σταθερά Lipschitz της .

Η ακριβής μορφή αυτή δεσμεύεται από μικρή πρακτική σημασία, καθώς στις περισσότερες περιπτώσεις η δεσμευμένη είναι πολύ μεγαλύτερη από το πραγματικό σφάλμα στο οποίο υπέπεσε με τη μέθοδο Όιλερ. είναι σημαντικό ότι δείχνει ότι το παγκόσμιο σφάλμα αποκοπής είναι περίπου ανάλογο με το . Για το λόγο αυτό, η μέθοδος Όιλερ λέγεται ότι είναι πρώτης τάξης.

Αριθμητική σταθερότητα 

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

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

Εάν η μέθοδος Όιλερ εφαρμόζεται στην γραμμική εξίσωση , τότε η αριθμητική λύση είναι ασταθής εάν το προϊόν  είναι εκτός της περιοχής

απεικονίζεται στα δεξιά.Η περιοχή αυτή ονομάζεται (γραμμική) περιοχή αστάθειας. Για παραδειγμα,  ισούται με −2.3, ωστόσο αν  τότε  η οποία είναι έξω από την περιοχή σταθερότητας, και έτσι η αριθμητική λύση είναι ασταθής.

Ο περιορισμός αυτός-μαζί με την αργή σύγκλιση του σφάλματος μεh—σημαίνει ότι η μέθοδος Όιλερ δεν χρησιμοποιείται συχνά, εκτός από ένα απλό παράδειγμα της αριθμητικής ολοκλήρωσης.

Σφάλματα Στρογγυλοποίησης 
Η συζήτηση μέχρι τώρα αγνοεί τις συνέπειες των Σφαλμάτων Στρογγυλοποίησης. Στο βήμα n της μεθόδου Όιλερ, το σφάλμα στρογγυλοποίησης είναι περίπου το μέγεθος εyn όπου ε είναι η μηχανή έψιλον. Υποθέτοντας ότι τα σφάλματα στρογγυλοποίησης είναι όλα περίπου το ίδιο μέγεθος, το συνολικό σφάλμα στρογγυλοποίησης στα N βήματα είναι περίπου Nεy0 εάν όλα τα σφάλματα σημεία της είναι στην ίδια κατεύθυνση. Δεδομένου ότι ο αριθμός των βημάτων είναι αντιστρόφως ανάλογος με το μέγεθος του βήματος h, Το συνολικό σφάλμα στρογγυλοποίησης είναι ανάλογο με ε / h. Στην πραγματικότητα, ωστόσο, είναι εξαιρετικά απίθανο όλα τα σφάλματα στρογγυλοποίησης να συγκεντρώνονται  προς την ίδια κατεύθυνση. Αν, αντίθετα, υποτίθεται ότι τα σφάλματα στρογγυλοποίησης είναι ανεξάρτητες μεταβλητές στρογγυλοποίησης, τότε το συνολικό σφάλμα στρογγυλοποίησης είναι ανάλογο με .

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

Τροποποιήσεις και επεκτάσεις 

Μια απλή τροποποίηση της μεθόδου Όιλερ το οποίο εξαλείφει τα προβλήματα σταθερότητας που εχει σημειωθεί στην προηγούμενη ενότητα είναι η προς τα πίσω μέθοδο Euler:

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

Άλλες τροποποιήσεις της μεθόδου Όιλερ που βοηθα με τη σταθερότητα να δώσει την εκθετική μέθοδο Όιλερ ή ημι-έμμεση μέθοδο Όιλερ.

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

Αυτό οδηγεί στην οικογένεια των Runge–Kutta methods.

Η άλλη δυνατότητα είναι να χρησιμοποιήσετε περισσότερες αξίες του παρελθόντος, όπως φαίνεται και από την Adams-Bashforth μέθοδο:

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

Όριο Σφάλματος 

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

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

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

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

Το οποίο σημαίνει ότι το h πρέπει να είναι μικρότερο από το παραπάνω ώστε να έχουμε το επιθυμητό σφάλμα ή μικρότερο , και 4/h, ή θα χρειαστούν περίπου 1072 επαναλήψεις για να γίνει αυτό.  Ο τεράστιος αριθμός των βημάτων, και συνεπώς το υψηλό υπολογιστικό κόστος,  ενισχύουν την χρήση εναλλακτικών, μεγαλύτερου βαθμού μεθόδων όπως η μέθοδος Runge–Kutta ή γραμμικές μέθοδοι πολλαπλών βημάτων.

Σημειώσεις

Πηγές 
 Ascher, Uri M.; Petzold, Linda Ruth. Computer methods for ordinary differential equations and differential-algebraic equations. 1998. SIAM. ISBN 0898714125

Εξωτερικοί Σύνδεσμοι 

 Euler's Method for O.D.E.'s

Αριθμητική ανάλυση
Μηχανική ρευστών