next up previous contents
Next: ΜΕΘΟΔΟΣ ΤΟΥ ΝΕΥΤΟΝΟΣ. Up: ΜΗ ΓΡΑΜΜΙΚΕΣ ΕΞΙΣΩΣΕΙΣ ΣΕ Previous: ΜΕΘΟΔΟΣ ΔΙΧΟΤΟΜΗΣΗΣ   Contents

Επαναλήψεις σταθερού σημείου

Έχοντας μία συνάρτηση 32#32, μία τιμή 33#33 τέτοια ώστε


1085#1085

ονομάζεται 1086#1086 της συνάρτησης 1087#1087, αφού το 33#33 παραμένει αμετάβλητο όταν εφαρμόζεται πάνω του το 1087#1087 (;;;;;;). Προβλήματα 1086#1086 συχνά εμφανίζονται απευθείας στην πράξη, αλλά είναι επίσης σημαντικά, γιατί ένα μη γραμμικό σύστημα μπορεί να διατυπωθεί ξανά ως πρόβλημα 1086#1086 για μία σχετική μη γραμμική συνάρτηση. Πράγματι, αρκετοί επαναληπτικοί αλγόριθμοι για την επίλυση μη γραμμικών συστημάτων στηρίζονται σε επαναληπτικά σχέδια της μορφής


1088#1088

όπου η 1087#1087 είναι μία κατάλληλα επιλεγμένη συνάρτηση της οποίας τα 1089#1089 είναι οι λύσεις για την εξίσωση 1043#1043. Ένα τέτοιο σχέδιο ονομάζεται 1090#1090 ή μερικές φορές 1091#1091, αφού η συνάρτηση 1087#1087 εφαρμόζεται επανελημένα σε μία αρχική τιμή 1092#1092. Για μία συγκεκριμένη εξίσωση 1043#1043 μπορεί να υπάρχουν πολλά ισοδύναμα 1093#1093 προβλήματα 1094#1094 με διαφορετικές επιλογές για την συνάρτηση 1087#1087. Αλλά δεν είναι όλοι οι 1093#1093 τύποι το ίδιο χρήσιμη στην άντληση ενός επαναληπτικού σχεδίου για την επίλυση ενός συγκεκριμένου μη γραμμικού συστήματος. Το τελικό επαναληπτικό σχέδιο μπορεί να διαφέρει όχι μόνο στο ρυθμό σύγκλισης, αλλά και κατά πόσο αν θα συγκλίνει ή όχι.


27#27

Παράδειγμα 5.5   ΠΡΟΒΛΗΜΑΤΑ 1095#1095. Για τις μη γραμμικές εξισώσεις 1096#1096 οποιαδήποτε από τις επιλογές

1097#1097

είναι μία συνάρτηση τις οποίας τα 1098#1098 είναι λύσεις στην εξίσωση 1043#1043. Οι συναρτήσεις αυτές φαίνονται στο Σχ. 5.3, όπου βλέπουμε ότι η διατομή της καμπύλης 1099#1099 με τη γραμμή 1100#1100 είναι αυτό που ζητάμε. Στο σχέδιο, βλέπουμε ότι κάθε συνάρτηση περνάει από το σημείο 1101#1101, και πράγματι 1102#1102. Τα αντίστοιχα επαναληπτικά σχέδια απεικονίζονται γραφικά στο Σχ. 5.4. Ένα κάθετο βέλος αντιστοιχεί στην αποτίμηση της συνάρτησης σε ένα σημείο, και ένα οριζόντιο βέλος που δείχνει τη συνάρτηση 1100#1100 υποδεικνύει ότι το αποτέλεσμα της προηγούμενης αποτίμησης της συνάρτησης χρησιμοποιείται ως όρισμα για την επόμενη. Για την πρώτη αυτών των συναρτήσεων, ακόμα και με αρχικό σημείο πολύ κοντά στην λύση, το επαναληπτικό σχέδιο αποκλίνει. Για τις επόμενες τρεις συναρτήσεις, το επαναληπτικό σχέδιο συγκλίνει στο 1093#1093 ακόμα και αν ξεκινάνε σχετικά μακριά από τη λύση, αν και ο φαινομενικός ρυθμός σύγκλισης είναι διαφέρει σε μεγάλο βαθμό.


27#27

ΣΧΕΔΙΑΓΡΑΜΜΑ 5.3 Ένα 1093#1093 μερικών μη γραμμικών συναρτήσεων.

ΣΧΕΔΙΑΓΡΑΜΜΑ 5.4 1103#1103 επαναλήψεις για μερικές μη γραμμικές συναρτήσεις.

Όπως μπορεί κάποιος να δει στο Σχεδιάγραμμα 5.4, Η συμπεριφορά ενός 1093#1093 επαναληπτικού σχεδίου μπορεί να διαφέρει αρκετά, από απόκλιση, σε αργή σύγκλιση, σε γρήγορη σύγκλιση. Τι είναι αυτό που κάνει τι διαφορά;

Ο πιο απλός (αν και όχι ο πιο κοινός τρόπος να χαρακτηρίσεις τη συμπεριφορά ενός επαναληπτικού σχήματος 1104#1104, για το εντοπισμένο πρόβλημα 1094#1094. Είναι να λάβεις υπόψη το παράγωγό του 1087#1087 στη λύση του 1052#1052 υποθέτοντας ότι το 1087#1087 είναι λείο. Πιο συγκεκριμένα, εάν 1105#1105 και

1106#1106

τότε το επαναληπτικό σχήμα είναι τοπικά μετατρέψιμο. Δηλαδή υπάρχει ένα διάστημα που περιλαμβάνει το 1107#1107 έτσι ώστε το αντίστοιχο επαναληπτικό σχέδιο είναι μετατρέψιμο εάν ξεκινήσει εντός αυτού του διαστήματος. Αν, από την άλλη πλευρά 1108#1108 τότε το αντίστοιχο επαναληπτικό σχήμα αποκλίνει. Η απόδειξη αυτού του αποτελέσματος είναι απλή και εκπαιδευτική έτσι τη σχεδιάζουμε εδώ. Εάν 1107#1107 είναι ένα σταθερό σημείο, τότε για το λάθος στην επανάληψη έχουμε

1109#1109

Με την 1110#1110,υπάρχει ένα σημείο 1111#1111 ανάμεσα στα 1051#1051 και 1052#1052 τέτοιο ώστε

1112#1112

έτσι ώστε . Δεν ξέρουμε την τιμή του 1111#1111 αλλά αν 1108#1108 τότε ξεκινώντας τις επαναλήψεις αρκετά κοντά στο 1052#1052, μπορούμε να είμαστε βέβαιοι ότι υφίσταται μία σταθερά 250#250 τέτοια ώστε 1113#1113 για 1114#1114. Έτσι έχουμε

1115#1115

και εφόσον 1116#1116, τότε 1117#1117 και η ακολουθία μετατρέπεται.

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

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



Manolis Vavalis 2000-03-24