Η αντίστροφη μέθοδος Cuthill-Mckee [2] στηρίζεται στη θεωρία των γραφημάτων για να μειώσει το εύρος ενός μητρώου. Θεωρώντας ένα συμμετρικό $n\times n$ μητρώο αρχικά δημιουργείται το γράφημα που αντιστοιχεί στο υπόψη μητρώο και στη συνέχεια γίνεται η επαναρίθμηση του γραφήματος ώστε το μητρώο να έχει το ελάχιστο εύρος.

Έστω για παράδειγμα το μητρώο και το γράφημα του Σχήματος 4.5.

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

Εφαρμόζοντας την αντίστροφη μέθοδος Cuthill-Mckee στα παραδείγματα που εξετάστηκαν στην προηγούμενη ενότητα, προκύπτουν τώρα τα τροποποιημένα μητρώα για την περίπτωση της αρίθμησης των κόμβων κατά γραμμές (βλ. Σχήμα 4.7), της αρίθμησης των κόμβων κατά στήλες (βλ. Σχήμα 4.8) και της τυχαίας αρίθμησης των κόμβων (βλ. Σχήμα 4.9).

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

Στην περίπτωση αυτή που φαίνεται στο Σχήμα 4.10, αποθηκεύεται το σύνολο των στοιχείων του μητρώου δυσκαμψίας, ακόμα και στην περίπτωση που αυτά είναι μηδενικά. Ο απαιτούμενος χώρος αποθήκευσης ισούται με $n^{2}$, όπου $n$ το μέγεθος του τετραγωνικού πίνακα $n\times n$.

Για παράδειγμα, για τον $n=4$ και έχουμε:

$$A=\left[\begin{array}[]{cccc}{a}_{11}&{a}_{12}&{a}_{13}&{a}_{14}\\ {a}_{21}&{a}_{22}&{a}_{23}&{a}_{24}\\ {a}_{31}&{a}_{32}&{a}_{33}&{a}_{34}\\ {a}_{41}&{a}_{42}&{a}_{43}&{a}_{44}\\ \end{array}\right]\xrightarrow{\text{αποθήκευση}}\begin{array}[]{cccc}{a}_{11}&{a}_{12}&{a}_{13}&{a}_{14}\\ {a}_{21}&{a}_{22}&{a}_{23}&{a}_{24}\\ {a}_{31}&{a}_{32}&{a}_{33}&{a}_{34}\\ {a}_{41}&{a}_{42}&{a}_{43}&{a}_{44}\\ \end{array}$$

(4.2)

Όταν αποθηκεύονται οι παραπάνω όροι κατά γραμμή, σε συμπαγή μορφή ως μονοδιάστατος πίνακας, τότε προκύπτει:

$$\left[{a}_{11},{a}_{12},{a}_{13},{a}_{14},\ldots{a}_{44}\right]_{(size=16)}$$

(4.3)

Αντίστοιχα κατά στήλη προκύπτει:

$$\left[{a}_{11},{a}_{12},{a}_{22},{a}_{13},\ldots{a}_{44}\right]_{(size=16)}.$$

(4.4)

Στην περίπτωση που το μητρώο των εξισώσεων είναι συμμετρικό (βλ. Σχήμα  4.11), μπορούμε να εκμεταλλευτούμε τη συμμετρία αποθηκεύοντας μόνο το άνω τριγωνικό (U) ή κάτω τριγωνικό (L) τμήμα του πίνακα [1]. Ο απαιτούμενος χώρος αποθήκευσης σε αυτή την περίπτωση ισούται με $\dfrac{n}{2}(n+1)$, όπου $n$ το μέγεθος του τετραγωνικού πίνακα $n\times n$.

Για παράδειγμα, για τον $n=4$ και για το άνω τριγωνικό τμήμα (U) του πίνακα έχουμε:

$$A=\left[\begin{array}[]{cccc}{a}_{11}&{a}_{12}&{a}_{13}&{a}_{14}\\ \bar{a}_{21}&{a}_{22}&{a}_{23}&{a}_{24}\\ \bar{a}_{31}&\bar{a}_{32}&\bar{a}_{33}&{a}_{34}\\ \bar{a}_{41}&\bar{a}_{42}&\bar{a}_{43}&\bar{a}_{44}\\ \end{array}\right]\xrightarrow{\text{αποθήκευση}}\begin{array}[]{cccc}{a}_{11}&{a}_{12}&{a}_{13}&{a}_{14}\\ \circ&{a}_{22}&{a}_{23}&{a}_{24}\\ \circ&\circ&{a}_{33}&{a}_{34}\\ \circ&\circ&\circ&{a}_{44}\\ \end{array}$$

(4.5)

Όταν αποθηκεύονται οι παραπάνω όροι κατά γραμμή, σε συμπαγή μορφή ως μονοδιάστατος πίνακας, τότε προκύπτει:

$$\left[{a}_{11},{a}_{12},{a}_{13},{a}_{14},\ldots{a}_{44}\right]_{(size=10)}$$

(4.6)

Αντίστοιχα κατά στήλη προκύπτει:

$$\left[{a}_{11},{a}_{12},{a}_{22},{a}_{13},\ldots{a}_{44}\right]_{(size=10)}.$$

(4.7)

Για το κάτω τριγωνικό τμήμα (L) αντίστοιχα,

$$A=\left[\begin{array}[]{cccc}{a}_{11}&\bar{a}_{12}&\bar{a}_{13}&\bar{a}_{14}\\ {a}_{21}&{a}_{22}&\bar{a}_{23}&\bar{a}_{24}\\ {a}_{31}&{a}_{32}&{a}_{33}&\bar{a}_{34}\\ {a}_{41}&{a}_{42}&{a}_{43}&{a}_{44}\\ \end{array}\right]\xrightarrow{\text{αποθήκευση}}\begin{array}[]{cccc}{a}_{11}&\circ&\circ&\circ\\ {a}_{21}&{a}_{22}&\circ&\circ\\ {a}_{31}&{a}_{32}&{a}_{33}&\circ\\ {a}_{41}&{a}_{42}&{a}_{43}&{a}_{44}\\ \end{array}$$

(4.8)

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

$$\left[{a}_{11},{a}_{21},{a}_{22},{a}_{31},\ldots{a}_{44}\right]_{(size=10)}$$

(4.9)

Αντίστοιχα κατά στήλη προκύπτει:

$$\left[{a}_{11},{a}_{21},{a}_{31},{a}_{41},{a}_{22},\ldots{a}_{44}\right]_{(size=10)}.$$

(4.10)

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

• •

  την κύρια διαγώνιο του μητρώου και

• •

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

Ένα παράδειγμα μητρώου ταινιωτής μορφής δίνεται στο Σχήμα 4.12.

Ο αριθμός των διαγωνίων που βρίσκονται κάτω από την κύρια διαγώνιο ($kl$) και ο αριθμός των διαγωνίων που βρίσκονται πάνω από την κύρια διαγώνιο ($ku$) ορίζουν το εύρος του πίνακα ($bw$) σύμφωνα με τη σχέση:

$$bw=kl+ku+1$$

(4.11)

Η αποθήκευση ενός μη συμμετρικού, τετραγωνικού μητρώου (έστω $n=5$) ταινιωτής μορφής ακολουθεί το παρακάτω πρότυπο [1]:

$$A=\left[\begin{array}[]{ccccc}a_{11}&a_{12}&0&0&0\\ a_{21}&a_{22}&a_{23}&0&0\\ a_{31}&a_{32}&a_{33}&a_{34}&0\\ 0&a_{42}&a_{43}&a_{44}&a_{45}\\ 0&0&a_{53}&a_{54}&a_{55}\\ \end{array}\right]\xrightarrow{\text{αποθήκευση}}\begin{array}[]{ccccc}\circ&a_{12}&a_{23}&a_{34}&a_{45}\\ a_{11}&a_{22}&a_{33}&a_{44}&a_{55}\\ a_{21}&a_{32}&a_{43}&a_{54}&\circ\\ a_{31}&a_{42}&a_{53}&\circ&\circ\\ \end{array}$$

(4.12)

Όταν αποθηκεύονται οι παραπάνω όροι κατά γραμμή, σε συμπαγή μορφή ως μονοδιάστατος πίνακας, τότε προκύπτει:

$$\left[0,{a}_{12},{a}_{23},{a}_{34},\ldots,{a}_{42},{a}_{53},0,0\right]_{(size=16)}$$

(4.13)

Αντίστοιχα κατά στήλη προκύπτει:

$$\left[0,{a}_{11},{a}_{21},{a}_{31},{a}_{12},\ldots,{a}_{45},{a}_{55},0,0\right]_{(size=16)}.$$

(4.14)

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

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

Έστω για παράδειγμα το τετραγωνικό, συμμετρικό μητρώο με $n=6$, το οποίο δίνεται ως:

$$A=\left[\begin{array}[]{cccccc}a_{11}&0&a_{13}&0&0&a_{16}\\ &a_{22}&0&a_{24}&0&0\\ &&a_{33}&a_{34}&0&0\\ &&&&a_{55}&a_{56}\\ &&&&&a_{66}\\ \end{array}\right]$$

(4.15)

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

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

$$A=\left[\begin{array}[]{cccccc}a_{11}&&a_{13}&&&a_{16}\\ &a_{22}&0&a_{24}&&0\\ &&a_{33}&a_{34}&&0\\ &&&&a_{55}&a_{56}\\ &&&&&a_{66}\\ \end{array}\right]$$

(4.16)

Μόνο οι παραπάνω όροι αποθηκεύονται σε αυτή την περίπτωση.

Σποραδικό ή αραιό ονομάζεται ένα μητρώο το οποίο έχει ένα σχετικά μικρό ποσοστό μη μηδενικών στοιχείων (βλ. π.χ. το Σχήμα 4.14). Ο απαιτούμενος αριθμός των μηδενικών στοιχείων ενός μητρώου ώστε αυτό να αποκαλείται αραιό εξαρτάται από το μέγεθος, τη δομή και χρήση του μητρώου [5].

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

• •

  Λίστα από λίστες (list of lists).
  Με αυτήν τη μέθοδο αποθηκεύεται μία λίστα ανά γραμμή. Κάθε στοιχείο αυτής της λίστας περιέχει τη στήλη και την τιμή του μη μηδενικού στοιχείου. Συνήθως τα στοιχεία της κάθε λίστας είναι ταξινομημένα ως προς τη στήλη για γρηγορότερες αναζητήσεις.

• •

  Συντεταγμένη λίστα (coordinate list – COO).
  Με αυτήν τη μέθοδο κάθε μη μηδενικό στοιχείο αποθηκεύεται ως τριάδα (γραμμή, στήλη, τιμή). Και σε αυτή την περίπτωση οι τριάδες είναι συνήθως ταξινομημένες ως προς γραμμή και στήλη για γρηγορότερες αναζητήσεις.

• •

  Πεπιεσμένη αποθήκευση κατά γραμμές (compressed row storage). Με αυτήν τη μέθοδο τα μη μηδενικά στοιχεία του μητρώου τοποθετούνται καταρχήν σε διαδοχικές θέσεις μνήμης (διάνυσμα $a$, από αριστερά προς τα δεξιά και από πάνω προς τα κάτω). Επιπλέον δημιουργούνται δύο διανύσματα στα οποία αποθηκεύονται:

  • –

    ένα διάνυσμα $col\_index$ που αποθηκεύει τους δείκτες των στηλών των στοιχείων του διανύσματος $a$ και

  • –

    ένα διάνυσμα $row\_index$ που αποθηκεύει για κάθε στήλη τη θέση στο διάνυσμα $a$ που αντιστοιχεί στο πρώτο μη μηδενικό στοιχείο του.

• •

  Πεπιεσμένη αποθήκευση κατά στήλες (compressed column storage). Η μέθοδος αυτή είναι παρόμοια με τη μέθοδο της πεπιεσμένης αποθήκευσης κατά γραμμές.

Η επιλογή μίας από τις διαθέσιμες μεθόδους εξαρτάται από πολλούς παράγοντες, όπως:

• •

  Τα χαρακτηριστικά και την αραιότητα του μητρώου.

• •

  Τις διαθέσιμες μεθόδους επίλυσης και την απόδοσή τους.

• •

  Την απαίτηση να υποστηρίζεται η αποτελεσματική τροποποίηση των στοιχείων του πίνακα ή

• •

  την απαίτηση να υποστηρίζεται η αποτελεσματική εισαγωγή νέων στοιχείων ή τέλος

• •

  την απαίτηση να υποστηρίζονται αποτελεσματικά τελεστές και πράξεις επί των μητρώων.

Έστω το σύστημα γραμμικών εξισώσεων $n\times n$

$$\mathbf{A}\boldsymbol{x}=\boldsymbol{b}$$

(4.17)

ή σε πλήρη μορφή:

$$\left[\begin{array}[]{cccc}a_{11}&a_{12}&\ldots&a_{1n}\\ a_{21}&a_{22}&\ldots&a_{2n}\\ \vdots&\vdots&\ddots&\vdots\\ a_{n1}&a_{n2}&\ldots&a_{kn}\\ \end{array}\right]\left[\begin{array}[]{c}x_{1}\\ x_{2}\\ \vdots\\ x_{n}\\ \end{array}\right]=\left[\begin{array}[]{c}b_{1}\\ b_{2}\\ \vdots\\ b_{n}\\ \end{array}\right]$$

(4.18)

Κατασκευάζουμε τώρα τον επαυξημένο πίνακα του συστήματος, προσαρτώντας στο μητρώο $\mathbf{A}$ το διάνυσμα $\boldsymbol{b}$, ως:

$$\left[\begin{array}[]{cccc|c}a_{11}&a_{12}&\ldots&a_{1n}&b_{1}\\ a_{21}&a_{22}&\ldots&a_{2n}&b_{2}\\ \vdots&\vdots&\ddots&\vdots&\vdots\\ a_{n1}&a_{n2}&\ldots&a_{nn}&b_{n}\\ \end{array}\right]$$

(4.19)

Στη συνέχεια με στοιχειώδεις διαδικασίες γραμμών προσπαθούμε να φέρουμε το σύστημα στην ακόλουθη μορφή, άνω τριγωνικού μητρώου [7]:

$$\left[\begin{array}[]{cccc|c}a^{\prime}_{11}&a^{\prime}_{12}&\ldots&a^{\prime}_{1n}&b^{\prime}_{1}\\ 0&a^{\prime}_{22}&\ldots&a^{\prime}_{2n}&b^{\prime}_{2}\\ \vdots&\vdots&\ddots&\vdots&\vdots\\ 0&0&\ldots&a^{\prime}_{nn}&b^{\prime}_{n}\\ \end{array}\right]$$

(4.20)

Οι στοιχειώδεις διαδικασίες γραμμών αφορούν τις ακόλουθες διαδικασίες:

1. 1.

   Εναλλαγή δύο γραμμών.

2. 2.

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

3. 3.

   Πρόσθεση σε μία γραμμή το πολλαπλάσιο μίας άλλης γραμμής.

Από το άνω τριγωνικό μητρώο (4.20) εύκολα μπορεί πλέον να βρεθεί η λύση του συστήματος. Πιο συγκεκριμένα, επιλύεται η $n$-ιοστή γραμμή ως προς προς $x_{n}$, το αποτέλεσμά της αντικαθίσταται στην $n-1$, η οποία επιλύεται ως προς $x_{n-1}$ κ.ο.κ. Η παραπάνω διαδικασία περιγράφεται από τον τύπο:

$$x_{i}=\dfrac{1}{a^{\prime}_{11}}\left(b^{\prime}_{i}-\sum_{j=i+1}^{n}a^{\prime}_{ij}x_{j}\right)$$

(4.21)

Η μέθοδος παραγοντοποίησης Cholesky αποτελεί μια παραλλαγή της μεθόδου απαλοιφής Gauss. Είναι μια μέθοδος με την οποία παραγοντοποιείται ένα συμμετρικό, θετικά ορισμένο μητρώο σε ένα κάτω τριγωνικό μητρώο και το ανάστροφό του σύμφωνα με τη σχέση [4]:

$$\mathbf{A}=\mathbf{L}\mathbf{L}^{T}.$$

(4.22)

Η μέθοδος αυτή αναπτύσσεται στη συνέχεια. Έστω λοιπόν το μητρώο $3\times 3$,

$$\mathbf{A}=\left[\begin{array}[]{ccc}a_{11}&a_{21}&a_{31}\\ a_{21}&a_{22}&a_{32}\\ a_{31}&a_{32}&a_{33}\\ \end{array}\right]$$

(4.23)

Μπορούμε να υπολογίσουμε το μητρώο $\mathbf{L}$, όπως αυτό ορίζεται από τη σχέση (4.22), ως:

	$\displaystyle\mathbf{A}\equiv LL^{T}$	$\displaystyle:=\left[\begin{array}[]{ccc}a_{11}&a_{21}&a_{31}\\ a_{21}&a_{22}&a_{32}\\ a_{31}&a_{32}&a_{33}\\ \end{array}\right]$		(4.24)
		$\displaystyle=\left[\begin{array}[]{ccc}l_{11}&0&0\\ l_{21}&l_{22}&0\\ l_{31}&l_{32}&l_{33}\\ \end{array}\right]\left[\begin{array}[]{ccc}l_{11}&l_{21}&l_{31}\\ 0&l_{22}&l_{32}\\ 0&0&l_{33}\end{array}\right]$		(4.25)
		$\displaystyle=\left[\begin{array}[]{ccc}l_{11}^{2}&l_{21}l_{11}&l_{31}l_{11}\\ l_{21}l_{11}&l_{21}^{2}+l_{22}^{2}&l_{31}l_{21}+l_{32}l_{22}\\ l_{31}l_{11}&l_{31}l_{21}+l_{32}l_{22}&l_{31}^{2}+l_{32}^{2}+l_{33}^{2}\end{array}\right]$		(4.26)

Παρατηρούμε ότι τα διαγώνια στοιχεία $l_{kk}$ του μητρώου $\mathbf{L}$ μπορούν να υπολογιστούν από τις σχέσεις:

	$\displaystyle l_{11}$	$\displaystyle=\sqrt{a_{11}}$		(4.27)
	$\displaystyle l_{22}$	$\displaystyle=\sqrt{a_{22}-l_{21}^{2}}$		(4.28)
	$\displaystyle l_{33}$	$\displaystyle=\sqrt{a_{33}-(l_{31}^{2}+l_{32}^{2})}$		(4.29)

Στη γενική περίπτωση για τα διαγώνια στοιχεία του μητρώου $\mathbf{L}$ της παραγοντοποίησης $\mathbf{A}=\mathbf{L}\mathbf{L}^{T}$ ισχύει:

$$l_{kk}=\sqrt{a_{kk}-\sum_{j=1}^{k-1}l_{kj}^{2}}$$

(4.30)

Για τα στοιχεία που βρίσκονται κάτω από την κύρια διαγώνιο, δηλαδή τα στοιχεία

$$l_{ιk}\,\text{όπου}\,i>k$$

(4.31)

παρατηρούμε ότι

	$\displaystyle l_{21}$	$\displaystyle=\dfrac{1}{l_{11}}a_{21}$		(4.32)
	$\displaystyle l_{31}$	$\displaystyle=\dfrac{1}{l_{11}}a_{31}$		(4.33)
	$\displaystyle l_{32}$	$\displaystyle=\dfrac{1}{l_{22}}(a_{32}-l_{31}l_{21})$		(4.34)

το οποίο οδηγεί στη γενική σχέση:

$$l_{ik}=\dfrac{1}{l_{kk}}\left(a_{ik}-\sum_{j=1}^{k-1}l_{ij}l_{kj}\right)$$

(4.35)

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

$$\mathbf{A}=\mathbf{L}\mathbf{U}$$

(4.36)

όπου $\mathbf{L}$ ένα κάτω τριγωνικό και $\mathbf{U}$ ένα άνω τριγωνικό μητρώο αντίστοιχα. Από τα μητρώα $\mathbf{L}$ και $\mathbf{U}$ η μέθοδος αυτή ονομάζεται LU παραγοντοποίηση.

Μια πιο ευρέως χρησιμοποιούμενη παραλλαγή της μεθόδου Chοlesky είναι η παραγοντοποίηση κατά Crout, στην οποία το μητρώο $\mathbf{A}$ παραγοντοποιείται ως:

$$\mathbf{A}=(\mathbf{L}\mathbf{D})\mathbf{U}$$

(4.37)

όπου $\mathbf{D}$ ένα διαγώνιο μητρώο.

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

		$\displaystyle\boldsymbol{r}_{0}:=\boldsymbol{b}-\mathbf{A}\boldsymbol{x}_{0}$		(4.38)
		$\displaystyle\boldsymbol{p}_{0}:=\boldsymbol{r}_{0}$		(4.39)
		$\displaystyle k:=0$		(4.40)
		επανάληψη		(4.41)
		$\displaystyle\qquad\alpha_{k}:=\frac{\boldsymbol{r}_{k}^{\mathsf{T}}\boldsymbol{r}_{k}}{\boldsymbol{p}_{k}^{\mathsf{T}}\mathbf{Ap}_{k}}$		(4.42)
		$\displaystyle\qquad\boldsymbol{x}_{k+1}:=\boldsymbol{x}_{k}+\alpha_{k}\boldsymbol{p}_{k}$		(4.43)
		$\displaystyle\qquad\boldsymbol{r}_{k+1}:=\boldsymbol{r}_{k}-\alpha_{k}\mathbf{Ap}_{k}$		(4.44)
		$\displaystyle\qquad\hbox{αν}\;r_{k+1}\hbox{ είναι σχετικά μικρό τότε {ΕΞΟΔΟΣ}}$		(4.45)
		$\displaystyle\qquad\beta_{k}:=\frac{\mathbf{r}_{k+1}^{\mathsf{T}}\boldsymbol{r}_{k+1}}{\boldsymbol{r}_{k}^{\mathsf{T}}\mathbf{r}_{k}}$		(4.46)
		$\displaystyle\qquad\boldsymbol{p}_{k+1}:=\boldsymbol{r}_{k+1}+\beta_{k}\boldsymbol{p}_{k}$		(4.47)
		$\displaystyle\qquad k:=k+1$		(4.48)

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

$$\mathbf{A}\boldsymbol{x}=\boldsymbol{b}$$

(4.49)

και ξεκινάει με μια αρχική θεώρηση $\boldsymbol{x}_{0}$ της λύσης $\boldsymbol{x}$.

Σε περιβάλλον ιδεατής αριθμητικής ακρίβειας, για την ακριβή λύση απαιτούνται το πολύ $n$ επαναλήψεις, όπου $n$ ο αριθμός των αγνώστων [6]. Στην πραγματικότητα, όμως, τα αριθμητικά σφάλματα στρογγύλευσης επηρεάζουν την ταχύτητα σύγκλισης.

Για τα προβλήματα που εξετάζονται στο παρόν βιβλίο, οι άγνωστοι στους κόμβους είναι οι μετακινήσεις. Κατ’ επέκταση, τα αντίστοιχα αποτελέσματα της επίλυσης αφορούν πρωτίστως τις μετακινήσεις των κόμβων. Μια τυπική απεικόνιση αποτελεσμάτων, όπου οι μετακινήσεις στους κόμβους σχεδιάζονται ως διανύσματα, δίνεται στο Σχήμα 4.17, που αφορά τα αποτελέσματα προσομοίωσης μίας σήραγγας και της επένδυσής της.

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

Αν το υλικό που χαρακτηρίζει το πρόβλημα θεωρηθεί ελαστικό, οι τάσεις $\boldsymbol{\sigma}$ σχετίζονται άμεσα με τις παραμορφώσεις $\boldsymbol{\varepsilon}$ σε κάθε σημείο μέσω των γνωστών σχέσεων τάσεων-παραμορφώσεων:

$$\boldsymbol{\sigma}=\mathbf{C}\boldsymbol{\varepsilon}.$$

(4.50)

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

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

Έστω ότι έχει επιλυθεί το σύστημα των εξισώσεων των πεπερασμένων στοιχείων

$$\mathbf{K}\boldsymbol{u}=\mathbf{F}$$

(4.51)

για τις επικόμβιες μετακινήσεις $\boldsymbol{u}$.

Για τον υπολογισμό των τάσεων και των παραμορφώσεων υπολογίζεται καταρχήν σε κάθε στοιχείο του προσομοιώματος, έστω $e$, το διάνυσμα των επικόμβιων μετακινήσεων του στοιχείου $\boldsymbol{u}^{(e)}$. Για τη συγκεκριμένη περίπτωση του τετράκομβου τετράπλευρου στοιχείου, αυτό θα είναι ένα διάνυσμα της μορφής:

$$\boldsymbol{u}^{(e)})=\left[\begin{array}[]{c}u_{1x}\\ u_{1y}\\ u_{2x}\\ u_{2y}\\ u_{3x}\\ u_{3y}\\ u_{4x}\\ u_{4y}\\ \end{array}\right]$$

(4.52)

Με γνωστό το διάνυσμα $\boldsymbol{u}^{(e)}$, μπορούν πλέον να υπολογιστούν οι παραμορφώσεις μέσω των κινηματικών εξισώσεων του στοιχείου, δηλαδή,

$$\boldsymbol{\varepsilon}=\mathbf{B}\boldsymbol{u}^{(e)}$$

(4.53)

όπου $\mathbf{B}$ το γνωστό μητρώο μετακινήσεων-παραμορφώσεων.

Επομένως, οι τάσεις υπολογίζονται εντός του στοιχείου $e$ ως:

$$\boldsymbol{\sigma}^{(e)}=\mathbf{C}\boldsymbol{\varepsilon}^{(e)}=\mathbf{C}\mathbf{B}\boldsymbol{u}^{(e)}$$

(4.54)

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

Για τον υπολογισμό τώρα των τάσεων στους κόμβους του στοιχείου υπάρχουν γενικά δύο προσεγγίσεις:

1. 1.

   Υπολογισμός των τάσεων απευθείας από την (4.54) χρησιμοποιώντας τις συναρτήσεις μορφής και τις αντίστοιχες συντεταγμένες των κόμβων.

2. 2.

   Υπολογισμός των τάσεων στα σημεία ολοκλήρωσης Gauss και στη συνέχεια η παρεκβολή τους στους κόμβους του στοιχείου.

H μέθοδος που ακολουθείται συχνότερα είναι η δεύτερη, καθώς θεωρείται ότι δίνει καλύτερα αποτελέσματα από τον απευθείας υπολογισμό των τάσεων στους κόμβους, και αναλύεται στη συνέχεια [3].

Έστω το τετράκομβο/τετράπλευρο στοιχείο του Σχήματος 4.18 στο οποίο έχει γίνει ολοκλήρωση των εξισώσεων του στοιχείου με τη μέθοδο Gauss και κανόνα $2\times 2$. Οι τάσεις υπολογίζονται στα σημεία Gauss, τα οποία δίνονται ως $1^{\prime}$, $2^{\prime}$, $3^{\prime}$ και $4^{\prime}$ στο Σχήμα 4.18. Τα σημεία Gauss ακολουθούν την αρίθμηση των κόμβων του στοιχείου, με το σημείο $1^{\prime}$ π.χ. να είναι το πλησιέστερο στον κόμβο 1 του στοιχείου. Οι συντεταγμένες των σημείων Gauss στο σύστημα του στοιχείου δίνονται στον Πίνακα 4.1.

Έστω τώρα ένα στοιχείο που έχει ως συντεταγμένες κόμβων τις συντεταγμένες των σημείων Gauss $1^{\prime}$, $2^{\prime}$, $3^{\prime}$ και $4^{\prime}$, όπως δίνεται από τη γραμμοσκιασμένη περιοχή του Σχήματος 4.18. Εφόσον γνωρίσουμε ένα μέγεθος στα σημεία αυτά, μπορούμε να το παρεκβάλουμε στα σημεία $1$, $2$, $3$ και $4$ που μας ενδιαφέρουν.

Η παρεκβολή αυτή γίνεται υπολογίζοντας τις συντεταγμένες στα σημεία $1$, $2$, $3$ και $4$ στο σύστημα $\xi^{\prime}$ και $\eta^{\prime}$ που ορίζεται από το καινούργιο στοιχείο. Τα δύο συστήματα συνδέονται με τις παρακάτω σχέσεις:

	$\displaystyle\xi$	$\displaystyle=\dfrac{\xi^{\prime}}{\sqrt{3}}$		(4.55)
	$\displaystyle\eta$	$\displaystyle=\dfrac{\eta^{\prime}}{\sqrt{3}}$		(4.56)
	$\displaystyle\xi^{\prime}$	$\displaystyle=\xi^{\prime}\sqrt{3}$		(4.57)
	$\displaystyle\eta^{\prime}$	$\displaystyle=\eta^{\prime}\sqrt{3}$		(4.58)

και οι συντεταγμένες των κόμβων του στοιχείου δίνονται στο σύστημα του στοιχείου που ορίζεται από τα σημεία Gauss, σύμφωνα με τα όσα αναφέρονται στον Πίνακα 4.2.

Έστω τώρα ένα βαθμωτό πεδίο $w$ του οποίου οι τιμές $w^{\prime}$ είναι γνωστές στα σημεία Gauss. Αυτές μπορούν να παρεμβληθούν με τις τυπικές διγραμμικές εξισώσεις παρεμβολής, οι οποίες όμως τώρα δίνονται σε όρους $\xi^{\prime}$ και $\eta^{\prime}$ ως:

$$w(\xi^{\prime},\eta^{\prime})=\left[\begin{array}[]{cccc}w^{\prime}_{1}&w^{\prime}_{2}&w^{\prime}_{3}&w^{\prime}_{4}\end{array}\right]\left[\begin{array}[]{c}{N^{\prime}}_{1}^{(e^{\prime})}\\ {N^{\prime}}_{2}^{(e^{\prime})}\\ {N^{\prime}}_{3}^{(e^{\prime})}\\ {N^{\prime}}_{4}^{(e^{\prime})}\\ \end{array}\right]$$

(4.59)

όπου

	$\displaystyle{N^{\prime}}_{1}^{(e^{\prime})}$	$\displaystyle=\dfrac{1}{4}(1-\xi^{\prime})(1-\eta^{\prime})$		(4.60)
	$\displaystyle{N^{\prime}}_{2}^{(e^{\prime})}$	$\displaystyle=\dfrac{1}{4}(1+\xi^{\prime})(1-\eta^{\prime})$		(4.61)
	$\displaystyle{N^{\prime}}_{3}^{(e^{\prime})}$	$\displaystyle=\dfrac{1}{4}(1+\xi^{\prime})(1+\eta^{\prime})$		(4.62)
	$\displaystyle{N^{\prime}}_{4}^{(e^{\prime})}$	$\displaystyle=\dfrac{1}{4}(1-\xi^{\prime})(1+\eta^{\prime})$		(4.63)

Για την παρεκβολή του μεγέθους $w$ αντικαθιστούμε στις παραπάνω εξισώσεις τις αντίστοιχες συντεταγμένες. Π.χ. για τον κόμβο 1 προκύπτει:

	$\displaystyle{N^{\prime}}_{1}^{(e^{\prime})}$	$\displaystyle=\dfrac{1}{4}(1-\xi^{\prime})(1-\eta^{\prime})$
		$\displaystyle=\dfrac{1}{4}(1+\sqrt{3})(1+\sqrt{3})$
		$\displaystyle=1+\dfrac{1}{2}\sqrt{3}$

Εφαρμόζοντας την παραπάνω διαδικασία για όλους τους κόμβους, προκύπτει:

$$\left[\begin{array}[]{c}w_{1}\\ w_{2}\\ w_{3}\\ w_{4}\\ \end{array}\right]=\left[\begin{array}[]{cccc}1+\dfrac{1}{2}\sqrt{3}&-\dfrac{1}{2}&1-\dfrac{1}{2}\sqrt{3}&-\dfrac{1}{2}\\ -\dfrac{1}{2}&1+\dfrac{1}{2}\sqrt{3}&-\dfrac{1}{2}&1-\dfrac{1}{2}\sqrt{3}\\ 1-\dfrac{1}{2}\sqrt{3}&-\dfrac{1}{2}&1+\dfrac{1}{2}\sqrt{3}&-\dfrac{1}{2}\\ -\dfrac{1}{2}&1-\dfrac{1}{2}\sqrt{3}&-\dfrac{1}{2}&1+\dfrac{1}{2}\sqrt{3}\\ \end{array}\right]\left[\begin{array}[]{c}w^{\prime}_{1}\\ w^{\prime}_{2}\\ w^{\prime}_{3}\\ w^{\prime}_{4}\\ \end{array}\right]$$

(4.64)

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

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

Στην πράξη ακολουθείται τις περισσότερες φορές ο πρώτος και πιο απλός τρόπος.