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

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

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

1. Έλεγχος της εκπλήρωσης της συνθήκης σύγκλισης στον αρχικό πίνακα. Θεώρημα σύγκλισης: εάν ο αρχικός πίνακας του συστήματος έχει διαγώνια κυριαρχία (δηλαδή, σε κάθε σειρά, τα στοιχεία της κύριας διαγωνίου πρέπει να είναι μεγαλύτερα σε απόλυτη τιμή από το άθροισμα των στοιχείων των δευτερευόντων διαγωνίων σε απόλυτη τιμή), τότε η μέθοδος απλές επαναλήψεις- συγκλίνουσα.

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

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

3. Μετατροπή του προκύπτοντος συστήματος σε κανονική μορφή:

x - =β - +α*x -

Αυτό μπορεί να γίνει με πολλούς τρόπους, για παράδειγμα, ως εξής: από την πρώτη εξίσωση, εκφράστε x 1 ως προς άλλους αγνώστους, από τη δεύτερη - x 2, από την τρίτη - x 3, κ.λπ. Σε αυτή την περίπτωση χρησιμοποιούμε τους τύπους:

α ij = -(a ij / a ii)

i = b i /a ii
Θα πρέπει και πάλι να βεβαιωθείτε ότι το προκύπτον σύστημα κανονικής μορφής πληροί την συνθήκη σύγκλισης:

∑ (j=1) |α ij |≤ 1, ενώ i= 1,2,...n

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

Το x (0) είναι η αρχική προσέγγιση, θα εκφράσουμε το x (1) μέσω αυτού, μετά θα εκφράσουμε το x (2) έως το x (1). Γενικός τύποςΕΝΑ μορφή μήτραςμοιάζει με αυτό:

x (n) = β - +α*x (n-1)

Υπολογίζουμε μέχρι να επιτύχουμε την απαιτούμενη ακρίβεια:

max |x i (k)-x i (k+1) ≤ ε

Λοιπόν, ας κάνουμε πράξη την απλή μέθοδο επανάληψης. Παράδειγμα:
Επίλυση SLAE:

4,5x1-1,7x2+3,5x3=2
3,1x1+2,3x2-1,1x3=1
1,8x1+2,5x2+4,7x3=4 με ακρίβεια ε=10 -3

Ας δούμε αν τα διαγώνια στοιχεία κυριαρχούν στο συντελεστή.

Βλέπουμε ότι μόνο η τρίτη εξίσωση ικανοποιεί τη συνθήκη σύγκλισης. Ας μετατρέψουμε το πρώτο και το δεύτερο και ας προσθέσουμε το δεύτερο στην πρώτη εξίσωση:

7,6x1+0,6x2+2,4x3=3

Από το τρίτο αφαιρούμε το πρώτο:

2,7x1+4,2x2+1,2x3=2

Μετατρέψαμε το αρχικό σύστημα σε αντίστοιχο:

7,6x1+0,6x2+2,4x3=3
-2,7x1+4,2x2+1,2x3=2
1,8x1+2,5x2+4,7x3=4

Τώρα ας φέρουμε το σύστημα στην κανονική του μορφή:

x1=0,3947-0,0789x2-0,3158x3
x2=0,4762+0,6429x1-0,2857x3
x3= 0,8511-0,383x1-0,5319x2

Ελέγχουμε τη σύγκλιση της επαναληπτικής διαδικασίας:

0.0789+0.3158=0,3947 ≤ 1
0.6429+0.2857=0.9286 ≤ 1
0,383+ 0,5319= 0,9149 ≤ 1, δηλ. πληρούται η προϋπόθεση.

0,3947
Αρχική εικασία x(0) = 0,4762
0,8511

Αντικαθιστώντας αυτές τις τιμές στην εξίσωση κανονικής μορφής, λαμβάνουμε τις ακόλουθες τιμές:

0,08835
x(1) = 0,486793
0,446639

Αντικαθιστώντας νέες τιμές, παίρνουμε:

0,215243
x(2) = 0,405396
0,558336

Συνεχίζουμε τους υπολογισμούς μέχρι να προσεγγίσουμε τιμές που ικανοποιούν τη δεδομένη συνθήκη.

x (7) = 0,441091

Ας ελέγξουμε την ορθότητα των αποτελεσμάτων που ελήφθησαν:

4,5*0,1880 -1.7*0,441+3.5*0,544=2,0003
3,1*0,1880+2,3*0,441-1,1x*0,544=0,9987
1.8*0,1880+2.5*0,441+4.7*0,544=3,9977

Τα αποτελέσματα που λαμβάνονται με την αντικατάσταση των τιμών που βρέθηκαν στις αρχικές εξισώσεις ικανοποιούν πλήρως τις συνθήκες της εξίσωσης.

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

Ας σκεφτούμε σύστημα γραμμικών αλγεβρικές εξισώσεις

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

(2.15)

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

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

(2.16)

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

Υπάρχουν και άλλες μορφές γραφής της μεθόδου επανάληψης, για παράδειγμα

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

Θεώρημα ( επαρκής κατάστασησύγκλιση απλή μέθοδος επανάληψης). Η επαναληπτική διαδικασία (2.16) συγκλίνει στη λύση του SLAE με την ταχύτητα γεωμετρική πρόοδοςόταν πληρούται η προϋπόθεση:

Απόδειξη.

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

Από αυτό προκύπτει ότι όταν

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

Θεώρημα (κριτήριο σύγκλισης απλή μέθοδος επανάληψης (καμία απόδειξη)). Αφήστε το SLAE (2.15) να έχει μια μοναδική λύση. Τότε για τη σύγκλιση της επαναληπτικής διαδικασίας (2.16) είναι απαραίτητο και επαρκές ότι όλα ιδιοτιμέςμήτρες από απόλυτη τιμήήταν λιγότερο από ένα.

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

Αριθμητικές πράξεις; απλή μέθοδος επανάληψης (2.16) , όπου i είναι ο αριθμός των προσεγγίσεων που απαιτούνται για να επιτευχθεί μια δεδομένη ακρίβεια. Αυτό σημαίνει ότι για Ι< n/3 метод итераций становится предпочтительнее. В πραγματικά προβλήματα, βασικά, Επιπλέον, επαναληπτικές μεθόδουςμπορεί να γίνει πιο αποτελεσματικό αλλάζοντας τις παραμέτρους επανάληψης. Σε ορισμένες περιπτώσεις επαναληπτικές μεθόδουςαποδεικνύεται ότι είναι πιο ανθεκτικό στη συσσώρευση σφαλμάτων στρογγυλοποίησης από τις ευθείες γραμμές.

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

Προϋπόθεση για σύγκλιση της επαναληπτικής διαδικασίας Μέθοδος Jacobi Μέθοδος Seidel

Απλή μέθοδος επανάληψης

Εξετάζεται ένα σύστημα γραμμικών αλγεβρικών εξισώσεων

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

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

Για να συγκλίνει η επαναληπτική διαδικασία, αρκεί να ικανοποιηθεί η συνθήκη
(κανονική μήτρα). Το κριτήριο για τον τερματισμό των επαναλήψεων εξαρτάται από την επαναληπτική μέθοδο που χρησιμοποιείται.

Μέθοδος Jacobi .

Ο απλούστερος τρόπος για να φέρετε το σύστημα σε μια μορφή κατάλληλη για επανάληψη είναι ο εξής:

Από την πρώτη εξίσωση του συστήματος εκφράζουμε το άγνωστο Χ 1, από τη δεύτερη εξίσωση του συστήματος που εκφράζουμε Χ 2, κ.λπ.

Ως αποτέλεσμα, λαμβάνουμε ένα σύστημα εξισώσεων με τον πίνακα Β, στον οποίο τα μηδενικά στοιχεία βρίσκονται στην κύρια διαγώνιο και τα υπόλοιπα στοιχεία υπολογίζονται χρησιμοποιώντας τους τύπους:

Οι συνιστώσες του διανύσματος d υπολογίζονται χρησιμοποιώντας τους τύπους:

Ο τύπος υπολογισμού για την απλή μέθοδο επανάληψης είναι:

ή σε συντεταγμένη σημειογραφία μοιάζει με αυτό:

Το κριτήριο για την ολοκλήρωση των επαναλήψεων στη μέθοδο Jacobi έχει τη μορφή:

Αν
, τότε μπορούμε να εφαρμόσουμε ένα απλούστερο κριτήριο για τον τερματισμό των επαναλήψεων

Παράδειγμα 1.Επίλυση συστήματος γραμμικών εξισώσεων με τη μέθοδο Jacobi.

Ας δοθεί το σύστημα των εξισώσεων:

Απαιτείται να βρεθεί μια λύση στο σύστημα με ακρίβεια

Ας μειώσουμε το σύστημα σε μια μορφή κατάλληλη για επανάληψη:

Ας επιλέξουμε μια αρχική προσέγγιση, για παράδειγμα,

- διάνυσμα της δεξιάς πλευράς.

Τότε η πρώτη επανάληψη μοιάζει με αυτό:

Οι ακόλουθες προσεγγίσεις στο διάλυμα λαμβάνονται με παρόμοιο τρόπο.

Ας βρούμε τον κανόνα του πίνακα Β.

Θα χρησιμοποιήσουμε τον κανόνα

Αφού το άθροισμα των μονάδων των στοιχείων σε κάθε σειρά είναι 0,2, τότε
, οπότε το κριτήριο για τον τερματισμό των επαναλήψεων σε αυτό το πρόβλημα είναι

Ας υπολογίσουμε τους κανόνες των διανυσματικών διαφορών:

Επειδή
η καθορισμένη ακρίβεια επιτεύχθηκε στην τέταρτη επανάληψη.

Απάντηση: Χ 1 = 1.102, Χ 2 = 0.991, Χ 3 = 1.0 1 1

Μέθοδος Seidel .

Η μέθοδος μπορεί να θεωρηθεί ως τροποποίηση της μεθόδου Jacobi. Η κύρια ιδέα είναι ότι κατά τον υπολογισμό του επόμενου (n+1)-η προσέγγιση στο άγνωστο Χ Εγώστο i >1χρήση που έχει ήδη βρεθεί (n+1)-ε πλησιάζει το άγνωστο Χ 1 ,Χ 2 , ...,Χ i - 1 και όχι nη προσέγγιση, όπως στη μέθοδο Jacobi.

Ο τύπος υπολογισμού της μεθόδου σε συμβολισμό συντεταγμένων μοιάζει με αυτό:

Οι συνθήκες σύγκλισης και το κριτήριο για το τέλος των επαναλήψεων μπορούν να ληφθούν με τον ίδιο τρόπο όπως στη μέθοδο Jacobi.

Παράδειγμα 2.Επίλυση συστημάτων γραμμικών εξισώσεων με τη μέθοδο Seidel.

Ας εξετάσουμε παράλληλα τη λύση 3 συστημάτων εξισώσεων:

Ας μειώσουμε τα συστήματα σε μια μορφή κατάλληλη για επαναλήψεις:

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

1ο σύστημα:

Η ακριβής λύση θα είναι οι ακόλουθες τιμές: Χ 1 = 1.4, Χ 2 = 0.2 . Η επαναληπτική διαδικασία συγκλίνει.

2ο σύστημα:

Μπορεί να φανεί ότι η διαδικασία επανάληψης αποκλίνει.

Ακριβής λύση Χ 1 = 1, Χ 2 = 0.2 .

3ο σύστημα:

Μπορεί να φανεί ότι η διαδικασία επανάληψης έχει προχωρήσει σε κύκλους.

Ακριβής λύση Χ 1 = 1, Χ 2 = 2 .

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

Απλή μέθοδος επανάληψης.

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

Χ=Χ-τ (Α Χ- β), τ – παράμετρος επανάληψης.

Ο τύπος υπολογισμού της μεθόδου απλής επανάληψης σε αυτή την περίπτωση έχει τη μορφή:

Χ (n+1) =Χ n- τ (Α Χ (n) - β).

και η παράμετρος τ > 0 επιλέγεται έτσι ώστε να ελαχιστοποιείται, αν είναι δυνατόν, η τιμή

Έστω λ min και λ max οι ελάχιστες και μέγιστες ιδιοτιμές του πίνακα A. Η βέλτιστη επιλογή της παραμέτρου είναι

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

Παράδειγμα 3. Επίλυση συστημάτων γραμμικών εξισώσεων με τη μέθοδο της απλής επανάληψης. (στο MathCAD)

Έστω το σύστημα των εξισώσεων Ax = b

Για να οικοδομήσουμε μια επαναληπτική διαδικασία ας βρούμε το δικό μαςαριθμοί του πίνακα Α:

- χρησιμοποιεί μια ενσωματωμένη συνάρτηση για την εύρεση ιδιοτιμών.

Ας υπολογίσουμε την παράμετρο επανάληψης και ας ελέγξουμε τη συνθήκη σύγκλισης

Η συνθήκη σύγκλισης ικανοποιείται.

Ας πάρουμε την αρχική προσέγγιση - διάνυσμα x0, ορίζουμε την ακρίβεια στο 0,001 και βρίσκουμε τις αρχικές προσεγγίσεις χρησιμοποιώντας το παρακάτω πρόγραμμα:

Ακριβής λύση

Σχόλιο. Εάν το πρόγραμμα επιστρέψει τον πίνακα rez, τότε μπορείτε να δείτε όλες τις επαναλήψεις που βρέθηκαν.

1. Έστω γνωστό ένα τμήμα που περιέχει μια ρίζα της εξίσωσης f(x) = 0. Η συνάρτηση f είναι μια συνεχώς διαφοροποιήσιμη συνάρτηση σε αυτό το τμήμα (f(x)ОC 1 ). Εάν πληρούνται αυτές οι προϋποθέσεις, μπορεί να χρησιμοποιηθεί η μέθοδος της απλής επανάληψης.

2. Χρησιμοποιώντας τη συνάρτηση f(x), κατασκευάζεται μια συνάρτηση j(x) που ικανοποιεί τρεις προϋποθέσεις: πρέπει να είναι συνεχώς διαφορίσιμη (j(x)ОC 1 ), έτσι ώστε η εξίσωση x = Το j(x) είναι ισοδύναμο με την εξίσωση f(x)=0. θα πρέπει επίσης μεταφράστε ένα τμήμα στον εαυτό σου.

Θα πούμε ότι η συνάρτηση j (Χ ) μεταφράζει το τμήμα [ένα , σι ] στον εαυτό σου, αν για κανένανΧ Î [ ένα , σι ], y = ι (Χ ) ανήκει επίσης[ ένα , σι ] ( y Î [ ένα , σι ]).

Η τρίτη συνθήκη επιβάλλεται στη συνάρτηση j(x):

Τύπος μεθόδου: x n +1 = j(xn).

3. Εάν πληρούνται αυτές οι τρεις προϋποθέσεις για οποιαδήποτε αρχική προσέγγιση x 0 О ακολουθία επαναλήψεων x n +1 = Το j(x n) συγκλίνει στη ρίζα της εξίσωσης: x = j(x) στο τμήμα ().

Κατά κανόνα, ως x 0 επιλέγεται ένα από τα άκρα.

,

όπου e είναι η καθορισμένη ακρίβεια

Αριθμός x n +1 όταν πληρούται η προϋπόθεση για τη διακοπή της επαναληπτικής διαδικασίας, είναι κατά προσέγγιση τιμή της ρίζας της εξίσωσης f(x) = 0 στο τμήμα , βρέθηκαν με απλή μέθοδο επανάληψης με ακρίβειαμι .

Κατασκευάστε έναν αλγόριθμο για να διευκρινίσετε τη ρίζα της εξίσωσης: x 3 + 5x – 1 = 0 σε ένα τμήμα χρησιμοποιώντας τη μέθοδο της απλής επανάληψης με ακρίβεια e .

1. Συνάρτηση f(x) = x 3 +5x-1 είναι συνεχώς διαφορίσιμο στο διάστημα που περιέχει μια ρίζα της εξίσωσης.

2. Η μεγαλύτερη δυσκολία στη μέθοδο της απλής επανάληψης είναι η κατασκευή μιας συνάρτησης j(x) που ικανοποιεί όλες τις προϋποθέσεις:

Σκεφτείτε: .

Εξίσωση x = j 1 (x) είναι ισοδύναμη με την εξίσωση f(x) = 0, αλλά η συνάρτηση j 1 (x) δεν είναι συνεχώς διαφορίσιμη στο διάστημα.

Ρύζι. 2.4. Γράφημα της συνάρτησης j 2 (x)

Από την άλλη, λοιπόν, . Επομένως: είναι μια συνεχώς διαφοροποιήσιμη συνάρτηση. Σημειώστε ότι η εξίσωση: x = j 2 (x) είναι ισοδύναμη με την εξίσωση f(x) = 0 . Από τη γραφική παράσταση (Εικ. 2.4) είναι σαφές ότι η συνάρτηση j 2 (x) μετατρέπει το τμήμα στον εαυτό της.

Η συνθήκη ότι η συνάρτηση j(x) παίρνει το τμήμα μέσα της μπορεί να αναδιατυπωθεί ως εξής: έστω το πεδίο ορισμού της συνάρτησης j(x) και έστω το πεδίο της παραλλαγής της j(x).

Αν το τμήμα ανήκει στο τμήμα , τότε η συνάρτηση j(x) παίρνει το τμήμα στον εαυτό της.

, .

Όλες οι προϋποθέσεις για τη συνάρτηση j(x) ικανοποιούνται.

Τύπος επαναληπτικής διαδικασίας: x n +1 = ι 2 (xn).

3. Αρχική προσέγγιση: x 0 = 0.

4. Προϋπόθεση για τη διακοπή της επαναληπτικής διαδικασίας:

Ρύζι. 2.5. Γεωμετρική σημασίααπλή μέθοδος επανάληψης

.

Εάν πληρούται αυτή η συνθήκη x n +1 – κατά προσέγγιση τιμή της ρίζας στο τμήμα, βρέθηκαν με απλή επανάληψη με ακρίβεια μι. Στο Σχ. 2.5. Εικονογραφείται η εφαρμογή της μεθόδου της απλής επανάληψης.

Θεώρημα σύγκλισης και εκτίμηση σφάλματος

Αφήστε το τμήμα περιέχει μια ρίζα της εξίσωσης x = j(x), λειτουργία j(x ) είναι συνεχώς διαφοροποιήσιμο στο διάστημα , μεταφράζει το τμήμα στον εαυτό του και η προϋπόθεση πληρούται:

.

Στη συνέχεια για οποιαδήποτε αρχική προσέγγιση x 0 О ακολουθία συγκλίνει στη ρίζα της εξίσωσης y = j(x ) στο τμήμα και η εκτίμηση του σφάλματος είναι δίκαιη:

.

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

Πολυπλοκότητα της απλής μεθόδου επανάληψης. Η ποσότητα της μνήμης του υπολογιστή που απαιτείται για την εφαρμογή της μεθόδου απλής επανάληψης είναι ασήμαντη. Σε κάθε βήμα πρέπει να αποθηκεύσετε το x n , x n +1 , q Και μι.

Ας υπολογίσουμε τον αριθμό των αριθμητικών πράξεων που απαιτούνται για την εφαρμογή της μεθόδου απλής επανάληψης. Ας γράψουμε μια εκτίμηση για τον αριθμό n 0 = n 0 (e) έτσι ώστε για όλα τα n ³ n 0 να ισχύει η ανισότητα:

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

Σχόλιο. Δεν υπάρχει γενικός κανόναςκατασκευάζοντας την j(x) από την f(x) έτσι ώστε να πληρούνται όλες οι προϋποθέσεις του θεωρήματος σύγκλισης. Συχνά χρησιμοποιείται η ακόλουθη προσέγγιση: η συνάρτηση j(x) = x + k× f(x) επιλέγεται ως συνάρτηση j, όπου k – συνεχής.

Κατά τον προγραμματισμό της απλής μεθόδου επανάληψης, η διακοπή της επαναληπτικής διαδικασίας συχνά απαιτεί την ταυτόχρονη εκπλήρωση δύο προϋποθέσεων:

Και .

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

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

Το θεώρημα του Samarsky

Αφήνω - αυτοσυνημμένος θετικός οριστικός πίνακας:

,
,

- θετικός καθορισμένος πίνακας, - θετικός αριθμός:

,
.

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

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

,
,
.

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

.

Μετά από αυτές τις παρατηρήσεις, προχωράμε στην απόδειξη του θεωρήματος. Ας εκφράσουμε από τη σχέση διά μέσου :

και αντικαταστήστε το στον επαναλαμβανόμενο τύπο για την ακολουθία επαναλήψεων. Ως αποτέλεσμα παίρνουμε:

.

Η διαφορά μεταξύ του επαναληπτικού τύπου και είναι ότι είναι ομοιογενής.

Μήτρα - θετική οριστική. Επομένως είναι μη εκφυλισμένο και έχει αντίστροφο
. Με τη βοήθειά της σχέση υποτροπήςμπορεί να επιλυθεί σχετικά
:

, Ετσι
.

Πολλαπλασιάζοντας και τις δύο πλευρές της ισότητας στα αριστερά με τον πίνακα , παίρνουμε μια άλλη σχέση επανάληψης

.

Εξετάστε την ακολουθία των θετικών συναρτήσεων:

.

Ας δημιουργήσουμε μια παρόμοια έκφραση για
και να το μετατρέψετε χρησιμοποιώντας επαναλαμβανόμενους τύπους και:

Από την αυτοσύνδεση της μήτρας και ακολουθεί ο τύπος

Ως αποτέλεσμα, ο τύπος παίρνει τη μορφή:

Έτσι, η ακολουθία των λειτουργιών υπό προϋποθέσεις
σχηματίζει μια μονοτονικά μη αυξανόμενη ακολουθία που οριοθετείται κάτω από το μηδέν

.

,

Οπου
είναι μια αυστηρά θετική σταθερά. Ως αποτέλεσμα, σύμφωνα με και θα έχουμε

Από αυτή την ανισότητα και τη σύγκλιση της ακολουθίας των συναρτήσεων ακολουθεί ότι
στο
. Με τη σειρά του
, Ετσι

Το θεώρημα έχει αποδειχθεί.

1. Απλή μέθοδος επανάληψης.

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

Θα υποθέσουμε ότι ο πίνακας ικανοποιεί τις προϋποθέσεις του θεωρήματος του Samarsky,
, τότε ο τύπος που καθορίζει το όριο του διαστήματος σύγκλισης σε σχέση με την επαναληπτική παράμετρο , παίρνει τη μορφή

.

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

Ας επεκτείνουμε το διάνυσμα
βασίζονται σε ιδιοδιανύσματα

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

.

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

,

και ξαναγράψτε τον τύπο στη φόρμα

.

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

.

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

Λήμμα 1

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

.

Η απόδειξη είναι στοιχειώδης. Διενεργείται με άμεση επαλήθευση

Για αυτοσυνημμένο πίνακα μήτρα είναι επίσης αυτοσυνημμένο. Κατά συνέπεια, ο κανόνας του καθορίζεται από τη μεγαλύτερη απόλυτη ιδιοτιμή
:

.

Λήμμα 2

Προκειμένου η απλή μέθοδος επανάληψης να συγκλίνει σε μια λύση του συστήματος για οποιαδήποτε επιλογή αρχικής προσέγγισης, είναι απαραίτητο και επαρκές όλες οι ιδιοτιμές του τελεστή μετάβασης ήταν λιγότερο από ένα σε απόλυτη τιμή:

,

Επάρκεια. Η συνθήκη σημαίνει ότι ο κανόνας του πίνακα , σύμφωνα με, θα είναι μικρότερο από ένα:
. Ως αποτέλεσμα παίρνουμε

Στο
.

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

.

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

,
.

δηλ.
. Η ανάγκη να ικανοποιηθεί η ανισότητα για όλες τις ιδιοτιμές για τη σύγκλιση της μεθόδου της απλής επανάληψης έχει αποδειχθεί.

Το Λήμμα 2 ορίζει το πρόγραμμα για περαιτέρω μελέτη της σύγκλισης της μεθόδου της απλής επανάληψης: είναι απαραίτητο να οριστεί το εύρος διακύμανσης παραμέτρων για την οποία όλες οι ιδιοτιμές ικανοποιούν την ανισότητα. Είναι εύκολο να γίνει. Στο Σχ. 1 δείχνει γραφήματα μείωσης γραμμικές συναρτήσεις
. Όλα προέρχονται από το ίδιο σημείο
,
και κατεβαίνουν λόγω αρνητικών συντελεστών στο , και η συνάρτηση με την ταχύτερη μείωση είναι
. Πότε έχει σημασία
, παύει να πληρούται η προϋπόθεση:

, στο
.

Βρέθηκε τιμή είναι το όριο του διαστήματος σύγκλισης της μεθόδου της απλής επανάληψης

.

Γνωρίζουμε ήδη αυτήν την ανισότητα. Λήφθηκε νωρίτερα από το θεώρημα του Samarsky ως επαρκής συνθήκη για σύγκλιση. Η πρόσθετη ανάλυση που βασίζεται στο Λήμμα 2 μας επιτρέπει να διευκρινίσουμε το αποτέλεσμα. Τώρα έχουμε διαπιστώσει ότι η ιδιότητα μέλους της επαναληπτικής παραμέτρου Το διάστημα είναι απαραίτητη και επαρκής προϋπόθεση για τη σύγκλιση της μεθόδου της απλής επανάληψης.

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

.

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

Ας βρούμε στο τμήμα
σημείο , στην οποία η φθίνουσα συνάρτηση
σε σύγκριση με μια αυξανόμενη συνάρτηση
. Καθορίζεται από την εξίσωση

που δίνει

.

Ως αποτέλεσμα παίρνουμε:

Η μικρότερη τιμή του είναι ο κανόνας του πίνακα φτάνει στο
:

.

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

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

Εργασία 2.

Θεωρήστε ένα σύστημα δύο εξισώσεων με δύο αγνώστους

και κατασκευάστε μια κατά προσέγγιση λύση για αυτό χρησιμοποιώντας την απλή μέθοδο επανάληψης.

Ας γράψουμε αμέσως τη λύση στο σύστημα

,
,

ώστε να μπορείτε στη συνέχεια να το συγκρίνετε με τα μέλη της ακολουθίας επανάληψης.

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

.

Είναι αυτοσυνημμένο και θετικό οριστικό, αφού

Ας δημιουργήσουμε μια χαρακτηριστική εξίσωση για τον πίνακα και βρείτε τις ρίζες του:

,

,

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

,
.

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

, Οπου

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

,
,
,

,
,
,

,
,
,

,
,
.

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

.