Αριθμητικές μέθοδοι: Newton-Raphson, Euler και Runge-Kutta

Οι αριθμητικές μέθοδοι είναι αλγόριθμοι για προσεγγιστικές απαντήσεις. Η Newton-Raphson χρησιμοποιείται για να βρεθεί μια ρίζα εξίσωσης όπως η $f(x)=0$, ενώ οι Euler και Runge-Kutta χρησιμοποιούνται για την προσέγγιση λύσεων διαφορικών εξισώσεων.

Αν θέλεις μόνο τη γρήγορη διάκριση, είναι η εξής: η Newton-Raphson ενημερώνει μια εκτίμηση για το $x$, ενώ οι Euler και Runge-Kutta προωθούν μια λύση στον χρόνο. Το αν λειτουργούν καλά εξαρτάται από συνθήκες όπως μια λογική αρχική εκτίμηση, μια χρήσιμη παράγωγος ή ένα μέγεθος βήματος $h$ αρκετά μικρό για το πρόβλημα.

Σε τι χρησιμεύει κάθε αριθμητική μέθοδος

Newton-Raphson: εύρεση ρίζας

Αν θέλεις μια τιμή του $x$ ώστε $f(x)=0$, η Newton-Raphson ενημερώνει μια εκτίμηση ακολουθώντας την εφαπτομένη:

$$x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}$$

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

Αυτό συνήθως λειτουργεί καλά όταν η $f$ είναι παραγωγίσιμη, $f'(x_n) \ne 0$, και η αρχική εκτίμηση είναι ήδη κοντά σε μια απλή ρίζα. Αν αυτές οι συνθήκες δεν ισχύουν, η μέθοδος μπορεί να κολλήσει, να απομακρυνθεί από τη ρίζα ή να αποκλίνει.

Για παράδειγμα, με $f(x)=x^2-2$ και $x_0=1.5$,

$$x_1 = 1.5 - \frac{1.5^2 - 2}{2(1.5)} = 1.4167$$

και ένα ακόμη βήμα δίνει περίπου $1.4142$, που είναι ήδη κοντά στο $\sqrt{2}$.

Μέθοδος Euler: μία κλίση, ένα βήμα

Για ένα πρόβλημα αρχικών τιμών

$$y' = f(t,y), \qquad y(t_0)=y_0,$$

η μέθοδος Euler χρησιμοποιεί την τρέχουσα κλίση για να προχωρήσει μπροστά:

$$y_{n+1} = y_n + h f(t_n, y_n)$$

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

Μέθοδος Runge-Kutta: πολλοί έλεγχοι κλίσης σε ένα βήμα

Οι μέθοδοι Runge-Kutta βελτιώνουν την Euler, δειγματοληπτώντας την πληροφορία της κλίσης περισσότερες από μία φορές μέσα στο ίδιο βήμα. Στα εισαγωγικά μαθήματα, το "Runge-Kutta" συχνά σημαίνει την κλασική μέθοδο τέταρτης τάξης RK4:

$$k_1 = f(t_n, y_n), \qquad k_2 = f\left(t_n + \frac{h}{2}, y_n + \frac{h}{2}k_1\right),$$ $$k_3 = f\left(t_n + \frac{h}{2}, y_n + \frac{h}{2}k_2\right), \qquad k_4 = f(t_n + h, y_n + hk_3)$$ $$y_{n+1} = y_n + \frac{h}{6}(k_1 + 2k_2 + 2k_3 + k_4)$$

Η RK4 παίρνει έναν σταθμισμένο μέσο όρο από πολλές εκτιμήσεις της κλίσης, οπότε συνήθως ακολουθεί την καμπύλη πολύ καλύτερα από την Euler για το ίδιο μέγεθος βήματος.

Λυμένο παράδειγμα: Euler vs. Runge-Kutta στην ίδια ΔΕ

Πάρε

$$y' = y, \qquad y(0)=1$$

και χρησιμοποίησε ένα βήμα μεγέθους $h=0.1$ για να εκτιμήσεις το $y(0.1)$.

Βήμα Euler

Στο $t=0$, η τρέχουσα τιμή είναι $y_0=1$, άρα η κλίση είναι

$$f(0,1)=1$$

Η Euler δίνει

$$y_1 = 1 + 0.1(1) = 1.1$$

Βήμα RK4

Τώρα χρησιμοποίησε το ίδιο πρόβλημα με την RK4:

$$k_1 = 1$$ $$k_2 = 1 + \frac{0.1}{2}(1) = 1.05$$ $$k_3 = 1 + \frac{0.1}{2}(1.05) = 1.0525$$ $$k_4 = 1 + 0.1(1.0525) = 1.10525$$

Άρα

$$y_1 = 1 + \frac{0.1}{6}(1 + 2(1.05) + 2(1.0525) + 1.10525)$$ $$y_1 \approx 1.105170833$$

Για αυτή την εξίσωση, η ακριβής τιμή είναι $e^{0.1} \approx 1.105170918$, οπότε το βήμα RK4 είναι πολύ πιο κοντά από το βήμα Euler.

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

Πότε να χρησιμοποιήσεις Newton-Raphson, Euler ή Runge-Kutta

Χρησιμοποίησε τη Newton-Raphson όταν ο στόχος είναι να λύσεις μια μη γραμμική εξίσωση και μπορείς να υπολογίσεις ή να προσεγγίσεις την παράγωγο. Χρησιμοποίησε την Euler όταν θέλεις τη βασική ιδέα της βηματικής επίλυσης μιας ΔΕ ή χρειάζεσαι μια γρήγορη γραμμή βάσης.

Χρησιμοποίησε Runge-Kutta, ειδικά την RK4, όταν θέλεις μια πρακτική αναβάθμιση ακρίβειας χωρίς να αλλάξεις τη διατύπωση του προβλήματος. Αν όμως η ΔΕ είναι δύσκαμπτη, ούτε η Euler ούτε η κλασική RK4 είναι πάντα καλή επιλογή· η μέθοδος πρέπει να ταιριάζει με την εξίσωση.

Συνηθισμένα λάθη στις αριθμητικές μεθόδους

Μπέρδεμα των τύπων προβλημάτων

Η Newton-Raphson είναι για ρίζες εξισώσεων. Οι Euler και Runge-Kutta είναι για διαφορικές εξισώσεις. Αν επιλέξεις τη λάθος οικογένεια μεθόδων, η διατύπωση είναι λάθος πριν καν αρχίσεις τους υπολογισμούς.

Υπόθεση ότι η μέθοδος θα συγκλίνει πάντα

Η Newton-Raphson μπορεί να αποτύχει αν η αρχική εκτίμηση είναι κακή ή αν το $f'(x)$ είναι πολύ μικρό κοντά στην επανάληψη. Οι μέθοδοι Euler και RK μπορεί να συμπεριφερθούν άσχημα αν το μέγεθος βήματος είναι πολύ μεγάλο για το πρόβλημα.

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

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

Ξεχνάς ότι η απάντηση είναι προσεγγιστική

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

Πού χρησιμοποιούνται οι αριθμητικές μέθοδοι

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

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

Δοκίμασε ένα παρόμοιο πρόβλημα

Δοκίμασε το ίδιο παράδειγμα ΔΕ με $h=0.05$ αντί για $0.1$ και σύγκρινε ξανά την απάντηση της Euler με την απάντηση της RK4. Έπειτα δοκίμασε τη Newton-Raphson στη $f(x)=x^2-3$ ξεκινώντας από $x_0=2$ και δες πόσο γρήγορα οι επαναλήψεις κινούνται προς το $\sqrt{3}$.