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

Γράφουμε το σύστημα των εξισώσεων στη μορφή

Στην κύρια διαγώνιο του πίνακα αυτού του συστήματος βρίσκονται τα στοιχεία σι 1, σι 2, …, bn, πάνω από αυτό είναι τα στοιχεία Με1, s2,... , sn-1 κάτω από αυτό βρίσκονται τα στοιχεία ένα 2, ένα 3,... , πάνω(στην περίπτωση αυτή, συνήθως όλοι οι συντελεστές διδεν είναι ίσα με μηδέν). Τα υπόλοιπα στοιχεία του πίνακα είναι ίσα με μηδέν.

Μέθοδος σάρωσηςαποτελείται από δύο στάδια - ευθεία τρέξιμο(ανάλογα με την άμεση κίνηση της μεθόδου Gauss) και αντίστροφη σάρωση(ανάλογη με την αντίστροφη κίνηση της μεθόδου Gauss). Η σάρωση προς τα εμπρός συνίσταται στον υπολογισμό των συντελεστών σάρωσης Όλα συμπεριλαμβάνονται,Bi, με τη βοήθεια του οποίου κάθε άγνωστος x Εγώεκφράζεται μέσω zi+1 :

Από την πρώτη εξίσωση του συστήματος (2.13) βρίσκουμε

Από την άλλη πλευρά, σύμφωνα με τον τύπο (2.14) Εξίσωση των συντελεστών και στις δύο παραστάσεις για Χ 1, παίρνουμε

(2.15)

Ας αντικαταστήσουμε στη δεύτερη εξίσωση του συστήματος (2.13) αντί για Χ 1 η έκφρασή του μέσω Χ 2 με τον τύπο (2.14):

Εξπρές από εδώ Χ 2 έως Χ 3:

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

(2.16)

Η σάρωση προς τα πίσω συνίσταται στον διαδοχικό υπολογισμό των αγνώστων xi. Πρώτα πρέπει να βρείτε xp.Για να γίνει αυτό, χρησιμοποιούμε την έκφραση (2.14) για Εγώ = Π–1 και η τελευταία εξίσωση του συστήματος (2.13). Ας τα γράψουμε:

Ως εκ τούτου, εξαιρώντας Χn-1, βρίσκουμε

Στη συνέχεια, χρησιμοποιώντας τους τύπους (2.14) και τους συντελεστές σάρωσης που υπολογίστηκαν νωρίτερα από τους τύπους (2.15), (2.16), υπολογίζουμε διαδοχικά όλους τους αγνώστους Χn- 1, xn-2 ,....,Χ 1. Αλγόριθμος λύσης συστήματος γραμμικές εξισώσειςτης μορφής (2.13) με τη μέθοδο σάρωσης φαίνεται στο σχ. 2.4.

Ρύζι. 2.4. Αλγόριθμος μεθόδου σάρωσης

Κατά την ανάλυση του αλγόριθμου της μεθόδου σάρωσης, θα πρέπει να ληφθεί υπόψη η δυνατότητα διαίρεσης με το μηδέν στους τύπους (2.15), (2.16). Μπορεί να φανεί ότι υπό την προϋπόθεση της επικράτησης των διαγώνιων στοιχείων, δηλ. εάν , και για τουλάχιστον μία τιμή ΕγώΗ αυστηρή ανισότητα ισχύει, η διαίρεση με το μηδέν δεν συμβαίνει και το σύστημα (2.13) έχει μια μοναδική λύση.

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

Αριθμητικές μέθοδοι γραμμικής άλγεβρας

3. Μέθοδος σάρωσης

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

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

Ας μετατρέψουμε την πρώτη εξίσωση του συστήματος (8) στη μορφή x 1 = 1 x 2 + 1, όπου

1 = -c 1 / b 1 και 1 = -d 1 / b 1 . Αντικαθιστούμε την έκφραση που προκύπτει για x 1 στη δεύτερη εξίσωση του συστήματος (8)

a 2 (1 x 2 + 1) + b 2 x 2 + c 2 x 3 = d 2 .

Ας αναπαραστήσουμε αυτήν την εξίσωση με τη μορφή x 2 \u003d 2 x 3 + 2, όπου 2 \u003d -c 2 / (b 2 + a 2 1) και 2 \u003d (d 2 - a 2 1) / (b 2 + α 2 1). Αντικαθιστούμε την έκφραση που προκύπτει για το x 2 στην τρίτη εξίσωση του συστήματος (8) και ούτω καθεξής.

Στο i-ο βήμα (1< i < n) процесса i-η εξίσωσησύστημα παίρνει τη μορφή

x i = i x i+1 + i , (9)

όπου i = -с i / (b i + a i i-1) και i = (d i - a i i-1) / (b i + a i i-1).

Στο τελευταίο ντο βήμααντικατάσταση στην τελευταία εξίσωση του συστήματος (8) της έκφρασης x n -1 = n -1 x n + n -1 δίνει την εξίσωση a n (n -1 x n + n -1) + b n x n = d n, από την οποία μπορείτε να προσδιορίσετε την τιμή x n = n = (d n - a n n-1) / (b n + a n n-1).

Οι τιμές των υπόλοιπων αγνώστων x i (i = n-1, n-2, ..., 1) υπολογίζονται εύκολα χρησιμοποιώντας τον τύπο (9).

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

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

i (i =) και i (i =).

Για i = 1, αυτοί οι συντελεστές υπολογίζονται από τους τύπους:

1 = -c 1 / 1; 1 = -d 1 / 1; 1 = b 1 .

Για i = χρησιμοποιούνται οι ακόλουθοι αναδρομικοί τύποι:

i \u003d -c i / i; i = (d i - a i i-1) / i ; i = b i + a i i -1 .

Η σάρωση προς τα εμπρός τελειώνει όταν i = n:

n \u003d (d n - a n n-1) / n; n = b n + a n n-1.

ΑΝΤΙΣΤΡΟΦΗη μέθοδος σάρωσης σάς επιτρέπει να υπολογίσετε τις τιμές των αγνώστων. Πρώτον, υποτίθεται ότι x n = n. Μετά μέσα αντίστροφη σειράσύμφωνα με τον τύπο (9) προσδιορίστε τις τιμές των αγνώστων x n -1 , x n -2 , ..., x 1 .

Ιδιότητες μεθόδου σάρωσης. Η πολυπλοκότητα της μεθόδου σάρωσης εκτιμάται σε περίπου 8n αριθμητικές πράξεις, κάτι που είναι σημαντικό λιγότερη μέθοδοςΓκάους. Η ύπαρξη λύσης στο σύστημα (8) και η μοναδικότητά του είναι εγγυημένα αν επαρκείς προϋποθέσειςδίνεται από το παρακάτω θεώρημα.

Θεώρημα. Έστω οι συντελεστές του συστήματος (8) ικανοποιούν τις παρακάτω ανισότητες

bk a k + c k ; b k > a k ; k = , όπου a 1 = 0; b n = 0. Τότε i 0 και i

1 για όλα i =

Σημειώστε ότι για όλα τα i 0 οι υπολογισμοί με τους τύπους σάρωσης προς τα εμπρός μπορούν να ολοκληρωθούν (κανένας από τους παρονομαστές δεν θα εξαφανιστεί). Ταυτόχρονα, όλοι οι συντελεστές i , τέτοιοι ώστε i 1, παρέχουν σταθερότητα σε σχέση με τα δεδομένα εισόδου του σταδίου back-sweep σύμφωνα με τον τύπο (9).

Υπολογιστικά Μαθηματικά

Η μέθοδος διαίρεσης ενός τμήματος στο μισό είναι ο απλούστερος και πιο αξιόπιστος τρόπος επίλυσης μιας μη γραμμικής εξίσωσης. Ας γίνει γνωστό από μια προκαταρκτική ανάλυση ότι η ρίζα της εξίσωσης (2.1) βρίσκεται στο διάστημα , δηλ. x*, έτσι ώστε f(x*) = 0...

Υπολογιστικά Μαθηματικά

Η μέθοδος του Νεύτωνα είναι η πιο αποτελεσματική μέθοδοςλύσεις μη γραμμικών εξισώσεων. Έστω η ρίζα x* , έτσι ώστε f(a)f(b)< 0. Предполагаем, что функция f(x) непрерывна на отрезке и дважды непрерывно дифференцируема на интервале (a, b). Положим x0 = b...

Υπολογιστικά Μαθηματικά

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

Η συνολική μέθοδος ελάχιστης αναζήτησης, που ονομάζεται μέθοδος αναζήτησης πλέγματος, είναι αξιόπιστη, αλλά εφαρμόζεται μόνο σε προβλήματα χαμηλών διαστάσεων (n<4). Неправильный выбор начального шага сетки может привести к тому...

Γραμμικός και μη γραμμικός προγραμματισμός

Επανάληψη 1. Αριθμός επαναλήψεων k = 0 Επανάληψη 2. Αριθμός επαναλήψεων k = 1 Η αναζήτηση ολοκληρώθηκε 3.3...

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

Θεωρητικές πληροφορίες. Για να λύσετε τη διαφορική εξίσωση y/=f(x,y) σημαίνει αριθμητικά για μια δεδομένη ακολουθία ορισμάτων x0, x1…, xn και τον αριθμό y0, χωρίς να ορίσετε τη συνάρτηση y=F(x), να βρείτε τέτοιες τιμές y1, y2,…, ун, ότι уi=F(xi)(i=1,2,…, n) και F(x0)=y0...

Μαθηματική μοντελοποίηση με ενεργό πείραμα

Ένα κανονικό απλό στον χώρο En είναι ένα σύνολο n + 1 σημείων σε ίση απόσταση μεταξύ τους (κορυφές του απλού). Ένα τμήμα που συνδέει δύο κορυφές ονομάζεται ακμή ενός απλού...

Μαθηματικός προγραμματισμός

Η μέθοδος του Νεύτωνα, ο αλγόριθμος του Νεύτωνα (γνωστός και ως μέθοδος εφαπτομένης) είναι μια επαναληπτική αριθμητική μέθοδος για την εύρεση της ρίζας (μηδέν) μιας δεδομένης συνάρτησης. Να λύσουμε αριθμητικά την εξίσωση f(x)=0 με απλή επανάληψη...

Μέθοδος περιστροφής για την επίλυση SLAE

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

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

Επίλυση παραβολικών εξισώσεων

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

Σύστημα διαφορικών εξισώσεων με σταθερούς συντελεστές

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

Ανάλυση συστήματος ομάδων μετασχηματισμών καταστάσεων του κύβου του Ρούμπικ

Το CFOP είναι το όνομα των τεσσάρων σταδίων συναρμολόγησης (εικόνα 3.2): Cross, F2L, OLL, PLL: 1) Cross - cross assembly ...

Αριθμητικές Μέθοδοιγραμμική άλγεβρα

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

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

Έστω ότι η εξίσωση (1) έχει μια ρίζα στο τμήμα και τα f (x) και f "(x) είναι συνεχή και διατηρούν σταθερά πρόσημα σε όλο το διάστημα. Η γεωμετρική έννοια της μεθόδου του Νεύτωνα είναι ότι το τόξο της καμπύλης y \u003d Η f (x) αντικαθίσταται από μια εφαπτομένη...

Αυτή η μέθοδος είναι επίσης μια τροποποίηση της μεθόδου Gauss για την ειδική περίπτωση αραιόςσυστήματα - συστήματα με μήτρα τριδιαγώνιου τύπου (οριακό πρόβλημα ΔΕ).

Η κανονική μορφή της σημειογραφίας τους

(1.6)

ή σε διευρυμένη μορφή:

(1.7)

Στην περίπτωση αυτή, κατά κανόνα, όλοι οι συντελεστές σι Εγώ  0.

Η μέθοδος εφαρμόζεται σε δύο στάδια - προς τα εμπρός και προς τα πίσω.

εμπρός εγκεφαλικό επεισόδιο . Κάθε άγνωστο Χ Εγώεκφράζεται μέσω Χ Εγώ +1

(Χ Εγώ = ΕΝΑ Εγώ Χ Εγώ +1 + σι ΕγώΓια Εγώ = 1,2, ..., n– 1) (1.8)

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

Από την πρώτη εξίσωση του συστήματος (1.7) βρίσκουμε Χ 1:

.

Από την εξίσωση (1.8) με Εγώ = 1 Χ 1 = ΕΝΑ 1  Χ 2 + σιένας . Συνεπώς,

και σύμφωνα με την εξίσωση (1.8) στο Εγώ = 2 Χ 2 = ΕΝΑ 2 Χ 3 + σι 2, επομένως:

,

όπου μι 2 = ένα 2 ΑΛΛΑ 1 + σι 2 .

Εστιάζοντας στους λόγους των δεικτών στους συντελεστές των εξισώσεων (1,9) και (1,9*), μπορούμε να λάβουμε αυτούς τους λόγους για τη γενική περίπτωση:

,

όπου μι Εγώ = ένα Εγώ  ΑΛΛΑ Εγώ –1 + σι Εγώ (Εγώ= 2,3, ..., n– 1) . (1.10)

Αντίστροφη κίνηση. Από την τελευταία εξίσωση του συστήματος (1.7) χρησιμοποιώντας τα δεδομένα της έκφρασης (1.8) με Εγώ = n – 1

.

Κατά την εφαρμογή της μεθόδου σάρωσης, θα πρέπει να λαμβάνεται υπόψη ότι υπό την προϋπόθεση

(1.12)

ή τουλάχιστον για ένα σι ΕγώΙσχύει η αυστηρή ανισότητα (1.12), η διαίρεση με το "0" αποκλείεται και το σύστημα έχει μια μοναδική λύση.

Σημειώστε ότι η συνθήκη (1.12) είναι επαρκής αλλά όχι απαραίτητη. Σε ορισμένες περιπτώσεις, για καλά κλιματιζόμενα συστήματα (1.7), η μέθοδος σάρωσης μπορεί να είναι σταθερή ακόμη και αν η συνθήκη (1.12) δεν ικανοποιείται.

Το σχήμα αλγορίθμου της μεθόδου σάρωσης μπορεί να μοιάζει με αυτό που φαίνεται στο Σχήμα 1.2.

Εικόνα 1.2 - Μπλοκ διάγραμμα της μεθόδου σάρωσης

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

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

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

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

(1.13)

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

, κ = 0, 1, 2, ... . (1.13*)

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

Για τη σύγκλιση της μεθόδου (1.13*) είναι απαραίτητο και επαρκές ότι | Εγώ (σολ)| < 1, где  Εγώ (σολ) - όλες οι ιδιοτιμές του πίνακα σολ. Θα υπάρξει επίσης σύγκλιση εάν || σολ|| < 1, ибо | Εγώ (σολ)| <  ||σολ|| ( - οποιαδήποτε).

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

||σολ|| =
ή || σολ|| =
, (1.14)

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

. (1.15)

Όταν ικανοποιούνται οι συνθήκες (1.14) ή (1.15), η μέθοδος επανάληψης συγκλίνει για οποιαδήποτε αρχική προσέγγιση
. Τις περισσότερες φορές διάνυσμα
πάρτε είτε το μηδέν, είτε τη μονάδα, είτε το ίδιο το διάνυσμα από το σύστημα (1.13).

Εάν η συνθήκη (1.15) ικανοποιείται, τότε η μετατροπή στην επαναληπτική μορφή (1.13) μπορεί να γίνει απλά λύνοντας κάθε Εγώ-η εξίσωση του συστήματος (1) ως προς Χ Εγώσύμφωνα με τους ακόλουθους αναδρομικούς τύπους:

σολ ij = − ένα ij / ένα ii ; σολ ii = 0; φά Εγώ = σι Εγώ / ένα ii , (1.15*)

δηλ.
.

Αν στο matrix ΑΛΛΑδεν υπάρχει διαγώνια υπεροχή, πρέπει να επιτευχθεί μέσω κάποιων γραμμικών μετασχηματισμών του που δεν παραβιάζουν την ισοδυναμία τους.

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

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

Αριθμός αντικειμένων 2 3 4 5 6 7 8 9 10 Αριθμός επιλογών 2 3 4 5 6 7 8 9 10

Παράδειγμα #1. Λύστε το πρόβλημα χρησιμοποιώντας τη μέθοδο δυναμικού προγραμματισμού σε χρόνο προς τα εμπρός και προς τα πίσω για την αντικειμενική συνάρτηση που δίνεται σε έναν πίνακα.
F(x 1 ,x 2 ,x 3) = f 1 (x 1) + f 2 (x 2) + f 3 (x 3) → max
x 1 + 2x 2 + 2x 3 ≤ 5

Χ	0	1	2	3	4	5
f 1 (x 1)	6	7	11	12	15	16
f 2 (x 2)	9	11	13	15
f 3 (x 3)	8	12	14	16

Λύση.
σκηνώνω. Βελτιστοποίηση υπό όρους. f 1 (L) = max(f 1); 0 ≤ x 1 ≤ 5; x 1 \u003d 0.1.2.3.4.5.
f 1 (0) = max = 6
f 1 (1) = max = 7
f 1 (2) = max = 11
f 1 (3) = max = 12
f 1 (4) = max = 15
f 1 (5) = max = 16
Πίνακας 1 - Υπολογισμός της τιμής της συνάρτησης f 1 (L)

μεγάλο	0	1	2	3	4	5
f 1 (L)	6	7	11	12	15	16
x 1	0	1	2	3	4	5

f 2 (L) = max; 0 ≤ x 2 ≤ 5; x 2 \u003d 0.1.2.3.4.5.
f 2 (0) = max = 15
f 2 (1) = max = 16
f 2 (2) = max = 20
f 2 (3) = max = 21
f 2 (4) = max = 24
f 2 (5) = max = 25
Πίνακας 2 - Υπολογισμός της τιμής της συνάρτησης f 2 (L)

μεγάλο	0	1	2	3	4	5
f 2 (L)	15	16	20	21	24	25
x2	0	0	0	0	0	0

f 3 (L) = max; 0 ≤ x 3 ≤ 5; x 3 \u003d 0.1.2.3.4.5.
f 3 (0) = max = 23
f 3 (1) = max = 24
f 3 (2) = max = 28
f 3 (3) = max = 29
f 3 (4) = max = 32
f 3 (5) = max = 33
Πίνακας 3 - Υπολογισμός της τιμής της συνάρτησης f 3 (L)

μεγάλο	0	1	2	3	4	5
f 3 (L)	23	24	28	29	32	33
x 3	0	0	0	0	0	0

ΙΙ στάδιο. Βελτιστοποίηση χωρίς όρους.
Έτσι, το μέγιστο f 3 (5) = 33
Σε αυτήν την περίπτωση, x 3 \u003d 0, αφού το f 3 (5) \u003d 33 επιτυγχάνεται σε x 3 \u003d 0 (βλ. πίνακα 3).
Τα υπόλοιπα x κατανέμονται ως εξής:
L=5 - 2*0=5
f 2 (5) = 25 επιτυγχάνεται σε x 2 = 0 (βλ. πίνακα 2).
L=5 - 2*0=5
f 1 (5) = 16 επιτυγχάνεται σε x 1 = 5 (βλ. πίνακα 1).
L=5 - 1*5=0
Ως αποτέλεσμα, η καλύτερη επιλογή επιτυγχάνεται με τις τιμές: x 1 = 5, x 2 = 0, x 3 = 0

Παράδειγμα #2. Εξετάστε το πρόβλημα της βέλτιστης κατανομής του κεφαλαίου K = nh σε m διαφορετικά ανεξάρτητα αμοιβαία κεφάλαια (τράπεζες, οργανισμοί, επιχειρήσεις κ.λπ.) για τα οποία το αναμενόμενο κέρδος f i είναι γνωστό για επενδύσεις x i = ih, i = 1..n. Εδώ n είναι ο αριθμός των διακριτών προσαυξήσεων h (διακριτές) στις οποίες διαιρείται το κεφαλαίο K.
Αφήστε τέτοια δεδομένα να είναι διαθέσιμα για τέσσερα (m=4) κεφάλαια για h = 1 εκατομμύριο ρούβλια, n = 6

Λύση.
σκηνώνω. Βελτιστοποίηση υπό όρους.
1ο βήμα: k = 4.
Έστω ότι όλα τα κεφάλαια στο ποσό των x 4 = 6 δίνονται στην 4η επιχείρηση. Σε αυτήν την περίπτωση, το μέγιστο εισόδημα, όπως φαίνεται από τον πίνακα 1*, θα είναι 0,56, επομένως:
F 4 (c 4) \u003d g 4 (x 4)
Τραπέζι 1.

0	x 1	0	1	2	3	4	5	6
x4	f 0 (x 0) / F 4 (x 4)	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0	0
1	0.2	0	0	0	0	0	0.2	0
2	0.33	0	0	0	0	0.33	0	0
3	0.42	0	0	0	0.42	0	0	0
4	0.48	0	0	0.48	0	0	0	0
5	0.53	0	0.53	0	0	0	0	0
6	0.56	0.56*	0	0	0	0	0	0

Τραπέζι 1*.

γ 1	0	1	2	3	4	5	6
F 0 (c 1)	0	0.2	0.33	0.42	0.48	0.53	0.56
x 1	0	1	2	3	4	5	6

2ο βήμα: k = 3.

F 3 (c 3) \u003d max [g 3 (x 3) + F 4 (c 3 - x 3)]
Πίνακας 2.

0	x2	0	1	2	3	4	5	6
x 3	f 3 (x 3) / F 3 (x 3)	0	0.2	0.33	0.42	0.48	0.53	0.56
0	0	0	0.2*	0.33	0.42	0.48	0.53	0.56
1	0.15	0.15	0.35*	0.48*	0.57	0.63	0.68	0
2	0.25	0.25	0.45	0.58	0.67	0.73	0	0
3	0.4	0.4	0.6*	0.73*	0.82	0	0	0
4	0.5	0.5	0.7	0.83*	0	0	0	0
5	0.62	0.62	0.82	0	0	0	0	0
6	0.73	0.73	0	0	0	0	0	0

Συμπληρώστε τον πίνακα 2*. Για να γίνει αυτό, σε κάθε βορειοανατολική διαγώνιο βρίσκουμε τον μεγαλύτερο αριθμό, τον οποίο σημειώνουμε με αστερίσκο και υποδεικνύουμε την αντίστοιχη τιμή x 2.
Πίνακας 2*.

γ 2	0	1	2	3	4	5	6
F 3 (c 2)	0	0.2	0.35	0.48	0.6	0.73	0.83
x2	0	0	1	1	3	3	4

3ο βήμα: k = 2.
Καθορίζουμε τη βέλτιστη στρατηγική για τη διανομή κεφαλαίων μεταξύ άλλων επιχειρήσεων. Σε αυτήν την περίπτωση, η σχέση επανάληψης Bellman έχει τη μορφή:
F 2 (c 2) \u003d max [g 2 (x 2) + F 3 (c 2 - x 2)]
Πίνακας 3

0	x 3	0	1	2	3	4	5	6
x2	f 4 (x 4) / F 2 (x 2)	0	0.2	0.35	0.48	0.6	0.73	0.83
0	0	0	0.2	0.35	0.48	0.6	0.73	0.83
1	0.25	0.25*	0.45*	0.6	0.73	0.85	0.98	0
2	0.41	0.41	0.61*	0.76*	0.89	1.01	0	0
3	0.55	0.55	0.75	0.9*	1.03*	0	0	0
4	0.65	0.65	0.85	1	0	0	0	0
5	0.75	0.75	0.95	0	0	0	0	0
6	0.8	0.8	0	0	0	0	0	0

Συμπληρώνουμε τον πίνακα 3 *. Για να γίνει αυτό, σε κάθε βορειοανατολική διαγώνιο βρίσκουμε τον μεγαλύτερο αριθμό, τον οποίο σημειώνουμε με αστερίσκο και υποδεικνύουμε την αντίστοιχη τιμή x 3 .
Πίνακας 3*.

γ 3	0	1	2	3	4	5	6
F 4 (c 3)	0	0.25	0.45	0.61	0.76	0.9	1.03
x 3	0	1	1	2	2	3	3

4ο βήμα: k = 1.
Καθορίζουμε τη βέλτιστη στρατηγική για τη διανομή κεφαλαίων μεταξύ άλλων επιχειρήσεων. Σε αυτήν την περίπτωση, η σχέση επανάληψης Bellman έχει τη μορφή:
F 1 (c 1) \u003d max [ g 1 (x 1) + F 2 (c 1 - x 1)]
Πίνακας 4

0	x4	0	1	2	3	4	5	6
x 1	f 5 (x 5) / F 1 (x 1)	0	0.25	0.45	0.61	0.76	0.9	1.03
0	0	0	0.25	0.45	0.61	0.76	0.9	1.03
1	0.28	0.28*	0.53*	0.73*	0.89	1.04	1.18	0
2	0.45	0.45	0.7	0.9	1.06	1.21	0	0
3	0.65	0.65	0.9*	1.1*	1.26*	0	0	0
4	0.78	0.78	1.03	1.23	0	0	0	0
5	0.9	0.9	1.15	0	0	0	0	0
6	1.02	1.02	0	0	0	0	0	0

Συμπληρώνουμε τον πίνακα 4 *. Για να γίνει αυτό, σε κάθε βορειοανατολική διαγώνιο βρίσκουμε τον μεγαλύτερο αριθμό, τον οποίο σημειώνουμε με αστερίσκο και υποδεικνύουμε την αντίστοιχη τιμή x 4 .
Πίνακας 4*.

γ 4	0	1	2	3	4	5	6
F 5 (c 4)	0	0.28	0.53	0.73	0.9	1.1	1.26
x4	0	1	1	1	3	3	3

ΙΙ στάδιο. Βελτιστοποίηση χωρίς όρους.
1ο βήμα: k = 1.
Σύμφωνα με τον Πίνακα 4*, το μέγιστο εισόδημα όταν το 6 κατανέμεται μεταξύ των επιχειρήσεων είναι c 1 = 6, F 1 (6) = 1,26. Σε αυτήν την περίπτωση, η 1η επιχείρηση πρέπει να διαθέσει x 1 = 3.
2ο βήμα: k = 2.

c 2 \u003d c 1 - x 1 \u003d 6 - 3 \u003d 3.
Σύμφωνα με τον Πίνακα 3*, το μέγιστο εισόδημα όταν το 3 κατανέμεται μεταξύ των επιχειρήσεων είναι c 2 = 3, F 2 (3) = 0,61. Σε αυτήν την περίπτωση, η 2η επιχείρηση πρέπει να διαθέσει x 2 = 2.
3ο βήμα: k = 3.
Ας προσδιορίσουμε το ποσό των υπόλοιπων κεφαλαίων που αποδίδονται στο μερίδιο άλλων επιχειρήσεων.
c 3 \u003d c 2 - x 2 \u003d 3 - 2 \u003d 1.
Σύμφωνα με τον Πίνακα 2*, το μέγιστο εισόδημα όταν το 1 κατανέμεται μεταξύ των επιχειρήσεων είναι c 3 = 1, F 3 (1) = 0,2. Σε αυτήν την περίπτωση, η 3η επιχείρηση πρέπει να διαθέσει x 3 \u003d 0.
4ο βήμα: k = 4.
Ας προσδιορίσουμε το ποσό των υπόλοιπων κεφαλαίων που αποδίδονται στο μερίδιο άλλων επιχειρήσεων.
c 4 \u003d c 3 - x 3 \u003d 1 - 0 \u003d 1.
Σύμφωνα με τον Πίνακα 1*, το μέγιστο εισόδημα όταν το 1 κατανέμεται μεταξύ των επιχειρήσεων είναι c 4 = 1, F 4 (1) = 0,20. Σε αυτήν την περίπτωση, η 4η επιχείρηση πρέπει να διαθέσει x 4 \u003d 1.
Έτσι, το βέλτιστο επενδυτικό σχέδιο για την επιχείρηση:
x 1 = 3
x2 = 2
x 3 = 0
x4 = 1
που θα παρέχει το μέγιστο εισόδημα ίσο με: F(6) = g 1 (3) + g 2 (2) + g 3 (0) + g 4 (1) = 0,65 + 0,41 + 0 + 0,20 = 1,26.

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

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

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

εξετάστε το σχήμα σιωπηρής διαφοράς

Εδώ Ai = Ci = 1, Bi = 1 + /?. 2 /(2at), D = li 2 (-u"- g / ") / (2at). Στην περίπτωσή μας ΕΝΑΤα j, D και C* δεν εξαρτώνται από τον δείκτη Εγώ, ωστόσο, εάν το βήμα του πλέγματος είναι μεταβλητό, τότε όλοι οι συντελεστές θα εξαρτώνται από τον αριθμό του κόμβου. Είναι σημαντικό να σημειωθεί ότι А(, Bj, Ci, g n+l , / n+1 - γνωστές ποσότητες. Η σχέση (7.2) είναι ένα σύστημα γραμμικών εξισώσεων για τους αγνώστους Uq + , Mg + .

Η διευρυμένη μήτρα αυτού του συστήματος έχει τη μορφή

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

Η παρουσία της αριστερής συνοριακής συνθήκης (mq +1 = n+1) καθιστά δυνατή την αναζήτηση μιας λύσης στη μορφή (για απλότητα σημειογραφίας, παραλείπεται ο ανώτερος δείκτης του αγνώστου) όπως

Λέγεται αναλογία σάρωσης, και οι συντελεστές A"*_i που περιλαμβάνονται σε αυτό και Li- - συντελεστές σάρωσης.Για i = 1 (7.1) ικανοποιείται αν δεχθούμε

Έτσι, ορίζονται οι αρχικές τιμές των συντελεστών αγώνων.

Χρησιμοποιώντας τη σχέση προαγωγής (7.3), εξαλείφουμε το άγνωστο sch-1 από (7.2):

Έχοντας πραγματοποιήσει τους απλούστερους μαθηματικούς μετασχηματισμούς, λαμβάνουμε

σε μορφή που συμπίπτει με την αναλογία σάρωσης. Η σύγκριση των (7.5) και (7.3) δίνει τις σχέσεις επανάληψης για τους συντελεστές σάρωσης:

Χρησιμοποιώντας τις αρχικές τιμές Co. = 0, Lq = , μπορούμε να υπολογίσουμε διαδοχικά Κ, Λ], Προς την2 , ^2, ..., Ln- εξαρτήματα διανύσματα των συντελεστών σάρωσης. Αυτή η υπολογιστική διαδικασία ονομάζεται ευθεία τρέξιμο. Είναι εύκολο να διαπιστωθεί ότι μια άμεση σάρωση χρησιμοποιώντας στοιχειώδεις μετασχηματισμούς μετατρέπει τον τριδιαγώνιο πίνακα του αρχικού γραμμικού συστήματος στον άνω δύο διαγώνιο και ο αριθμός των αριθμητικών πράξεων (λόγω της ειδικής μορφής του αρχικού πίνακα) είναι ανάλογος του αριθμός αγνώστων 1 .

Η μορφή δύο διαγώνιων του προκύπτοντος πίνακα καθιστά εύκολη την κατασκευή της διαδικασίας υπολογισμού των αγνώστων. Σαρωτική σχέση για τον τελευταίο κόμβο wjv-i = Kn-Un + L^~ 1, μαζί με τη σωστή οριακή συνθήκη = εγώ,μας επιτρέπει να υπολογίσουμε το idr_ 1 και στη συνέχεια, χρησιμοποιώντας τον αναδρομικό τύπο (7.3), να προσδιορίσουμε διαδοχικά όλους τους αγνώστους un-2, un-3, ..., schπρόβλημα διαφοράς. Ο διαδοχικός υπολογισμός των αγνώστων με τη χρήση της σχέσης σάρωσης (7.3) ονομάζεται αντίστροφη διαδρομή. Στον πυρήνα της, η μέθοδος σάρωσης είναι μια παραλλαγή του Gaussian elimination, η οποία λαμβάνει υπόψη τις ιδιαιτερότητες της δομής ενός τριδιαγώνιου πίνακα και εξαλείφει τις πράξεις στα μηδενικά στοιχεία του.

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

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

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

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