next up previous contents
Next: ΜΗ ΓΡΑΜΜΙΚΕΣ ΕΞΙΣΩΣΕΙΣ ΣΕ Up: ΜΗ ΓΡΑΜΜΙΚΕΣ ΕΞΙΣΩΣΕΙΣ Previous: Λύσεις Μη Γραμμικών Εξισώσεων   Contents

ΡΥΘΜΟΣ ΣΥΓΚΛΙΣΗΣ ΕΠΑΝΑΛΗΠΤΙΚΩΝ ΜΕΘΟΔΩΝ

Αντίθετα με τις γραμμικές εξισώσεις, οι περισσότερες μη γραμμικές εξισώσεις δεν μπορούν να λυθούν με περιορισμένο αριθμό βημάτων. Γι' αυτό, καταφεύγουμε συνήθως σε κάποια επαναληπτική μέθοδο που παράγει όλο και μεγαλύτερης ακρίβειας προσέγγιση της λύσης, και τερματίζουμε την επανάληψη όταν το αποτέλεσμα είναι ικανοποιητικά ακριβές. Το συνολικό κόστος της επίλυσης του προβλήματος εξαρτάται από το κόστος κάθε επανάληψης αλλά και από τον αριθμό των επαναλήψεων που απαιτούνται για τη σύγκλιση, και συχνά υπάρχει μία ισορροπία ανάμεσα στους δύο αυτούς παράγοντες. Για να συγκρίνουμε την αποτελεσματικότητα των επαναληπτικών μεθόδων, χρειάζεται να χαρακτηρίσουμε το ρυθμό σύγκλισης. Συμβολίζουμε το λάθος των επαναληπτικών μεθόδων 432#432 από 1050#1050, και συνήθως δίνεται από τον τύπο , όπου 1051#1051 είναι η προσεγγιστική λύση με 432#432 και το 1052#1052 είναι η πραγματική λύση. Ωστόσο, κάποιες μέθοδοι για προβλήματα μίας διάστασης, δεν παράγουν μία συγκεκριμένη προσεγγιστική λύση 1051#1051, αλλά παράγουν μερικώς ένα διάστημα, στο οποίο γνωρίζουμε ότι περιέχεται η λύση, με το μήκος του διαστήματος να μειώνεται σταδιακά όσο συνεχίζονται οι επαναλήψεις. Για αυτές τις μεθόδους, παίρνουμε το 1050#1050 ώστε να είναι το μήκος του διαστήματος κατά την 432#432 επανάληψη. Σε κάθε περίπτωση η μέθοδος θεωρείται ότι συγκλίνει με ρυθμό 29#29 αν

1053#1053

για κάποιες μετρήσιμες μη μηδενικές σταθερές 250#250. Μερικές ενδιαφέρουσες περιπτώσεις είναι οι εξής:

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



Manolis Vavalis 2000-03-24