3 Πρόβλημα δύο σημείων 3.1 Διακριτοποίηση 3.3 Σύγκλιση της μεθόδου πεπερασμένων διαφορών

3.2 Επίλυση τριδιαγώνιου γραμμικού συστήματος

Έστω ότι θέλουμε να λύσουμε το γραμμικό σύστημα $Ay=z$ , δηλαδή να βρούμε το $y\in\mathbb{R}^{N}$ , όπου $A$ είναι ένας $N\times N$ τριδιαγώνιος πίνακας με στοιχεία

A=\left(\begin{array}[]{ccccc}a_{1}&b_{1}&&0&\\ c_{2}&a_{2}&b_{2}&&\\ &\ddots&\ddots&\ddots&\\ &0&c_{N-1}&a_{N-1}&b_{N-1}\\ &&&c_{N}&a_{N}\\ \end{array}\right),

(3.10)

και $z\in\mathbb{R}^{N}$ ένα δοσμένο διάνυσμα. Για τα στοιχεία του πίνακα $A$ θα κάνουμε τις ακόλουθες υποθέσεις

|a_{1}|>|b_{1}|,\quad|a_{k}|\geq|b_{k}|+|c_{k}|,\ k=2,\dots,N-1,\quad|a_{N}|>|% c_{N}|.

(3.11)

Για να λύσουμε το γραμμικό σύστημα $Ay=z$ μπορούμε να εφαρμόσουμε διάφορους αλγόριθμους όπως είναι η απαλοιφή Gauss. Στην περίπτωση, όμως, του πίνακα $A$ , είναι προτιμότερο να χρησιμοποιήσουμε έναν αλγόριθμο που έχει σχεδιαστεί ειδικά για τριδιαγώνιους πίνακες, όπως ο ακόλουθος:

Ο πίνακας $A$ μπορεί να γραφεί ως γινόμενο $L U$ δύο πινάκων $L$ και $U$ , με $L$ κάτω τριγωνικό και $U$ άνω τριγωνικό, που έχουν τη μορφή

L=\left(\begin{array}[]{cccc}d_{1}&&&\\ c_{2}&d_{2}&0&\\ &\ddots&\ddots&\\ &0&c_{N}&d_{N}\\ \end{array}\right),\ U=\left(\begin{array}[]{ccccc}1&e_{1}&&&\\ &1&e_{2}&0&\\ &&\ddots&\ddots&\\ &&&1&e_{N-1}\\ &&&0&1\\ \end{array}\right),

(3.12)

δηλαδή έχουν μη μηδενικά στοιχεία στη διαγώνιο και ο $L$ στην πρώτη υποδιαγώνιο και ο $U$ στην πρώτη υπερδιαγώνιο. Είναι απλό να δούμε ότι οι αριθμοί $d_{1},\dots,d_{N}$ και $e_{1},\dots,e_{N-1}$ προκύπτουν με τον ακόλουθο αλγόριθμο

\begin{split}&\displaystyle d_{1}=a_{1},e_{1}=b_{1}/d_{1}\\ &\displaystyle\text{για }k=2,3,\dots,N-1\\ &\displaystyle\qquad d_{k}=a_{k}-c_{k}e_{k-1}\\ &\displaystyle\qquad e_{k}=b_{k}/d_{k}\\ &\displaystyle\text{τέλος για}\\ &\displaystyle d_{N}=a_{k}-c_{N}e_{N-1}.\end{split}

(3.13)

Η υπάρξη των πινάκων $L$ και $U$ και η ολοκλήρωση του αλγορίθμου (3.13) αποδεικνύεται στο ακόλουθο λήμμα.

Λήμμα 3.2.

Έστω $A$ ένας τριδιαγώνιος πίνακας της μορφής (3.10), τέτοιος ώστε να ισχύουν οι υποθέσεις (3.11). Τότε υπάρχουν πίνακες $L$ και $U$ της μορφής (3.12), τέτοιοι ώστε $A=LU$ και ο αλγόριθμος (3.13) είναι καλά ορισμένος και ολοκληρώνεται.

Απόδειξη.

Για να είναι ο αλγόριθμος (3.13) καλά ορισμένος και, συνεπώς, να υπάρχει η ανάλυση του $A=LU$ με πίνακες $L$ και $U$ της μορφής (3.12), αρκεί να ισχύει $d_{k}\neq 0$ , $k=1,\dots,N$ . Από τις υποθέσεις (3.11) έχουμε ότι $|a_{1}|>|b_{1}|$ , οπότε $|e_{1}|<1$ . Επαγωγικά μπορούμε να αποδείξουμε ότι

d_{k}\neq 0,k=1,\dots,N,\quad|e_{k}|<1.

Πράγματι, έστω ότι ισχύει $d_{k-1}\neq 0$ , $|e_{k-1}|<1$ για κάποιο $k$ . Τότε $|d_{k}|=|a_{k}-c_{k}e_{k-1}|\geq|a_{k}|-|c_{k}|\,|e_{k-1}|>|a_{k}|-|c_{k}|\geq% |b_{k}|>0$ . Επιπλέον $|e_{k}|=|b_{k}|/|d_{k}|<1$ . ∎

Εφόσον έχουμε αποδείξει ότι $A=LU$ , για να λύσουμε τώρα το γραμμικό σύστημα $LUy=z$ , λύνουμε πρώτα το $Lw=z$ εφαρμόζοντας τον ακόλουθο αλγόριθμο

\begin{split}&\displaystyle w_{1}=z_{1}/d_{1}\\ &\displaystyle\text{για }k=2,3,\dots,N-1\\ &\displaystyle\qquad w_{k}=(z_{k}-c_{k}w_{k-1})/d_{k}\\ &\displaystyle\text{τέλος για}\end{split}

(3.14)

και, στη συνέχεια, το διάνυσμα $y$ προκύπτει ως λύση του γραμμικού συστήματος $Uy=w$

\begin{split}&\displaystyle y_{N}=w_{N}\\ &\displaystyle\text{για }k=N-1,N-2,\dots,1\\ &\displaystyle\qquad y_{k}=w_{k}-e_{k}y_{k+1}\\ &\displaystyle\text{τέλος για}\end{split}

(3.15)

Παρατήρηση 3.1.

Παρατηρούμε, λοιπόν, ότι αν ένας πίνακας $Α$ της μορφής (3.10) δεν έχει αυστηρά κυριαρχική διαγώνιο, αλλά ικανοποιεί τις υποθέσεις (3.11), τότε αντιστρέφεται. Στο πρόβλημα (3.1), υποθέσαμε ότι $q_{\min}\geq 0$ . Αυτό σημαίνει ότι ο πίνακας $A+h^{2}Q$ που θεωρήσαμε στην (3.8), ικανοποιεί τις υποθέσεις (3.11). Συνεπώς, εφαρμόζοντας τους αλγορίθμους (3.14) και (3.15), διαπιστώνουμε ότι το γραμμικό σύστημα (3.8) έχει μοναδική λύση.

Παράδειγμα 3.1.

Θεωρούμε το ακόλουθο πρόβλημα συνοριακών τιμών

-u^{\prime\prime}(x)+u(x)=\sin(2\pi x),\quad 0<x<1,\quad\text{με}\ u(0)=u(1)=0.

(3.16)

Η ακριβής λύση $u$ αυτού του προβλήματος είναι

u(x)=\dfrac{\sin(2\pi x)}{1+4\pi^{2}},

(3.17)

οπότε η (3.6) γίνεται τώρα

-\dfrac{U_{i+1}-2U_{i}+U_{i-1}}{h^{2}}+U_{i}=\sin(2\pi x_{i}),\quad i=1,\dots,N.

(3.18)

Διαμερίζουμε το $[0,1]$ σε $N+2$ ισαπέχοντα σημεία και χρησιμοποιώντας τους παραπάνω αλγορίθμους (3.13), (3.14) και (3.15), μπορούμε να βρούμε $U_{i}$ που προσεγγίζουν την ακριβή λύση στο αντίστοιχο σημείο $x_{i}$ του διαμερισμού. Στο Σχήμα 3.1 εμφανίζονται οι προσεγγίσεις για $N=2,4$ και $6$ και το γράφημα της ακριβούς λύσης $u$ . Σε αυτό το σχήμα, μπορούμε να παρατηρήσουμε ότι καθώς το πλήθος των σημείων της διαμέρισης αυξάνει, και άρα το βήμα $h$ ελαττώνεται, φαίνεται ότι η αντίστοιχη προσέγγιση πλησιάζει καλύτερα την ακριβή λύση. Αυτό εμφανίζεται και στον Πίνακα 3.1, όπου βλέπουμε τα σφάλματα της προσέγγισης της $u(x_{i})$ από την $U_{i}$ στα σημεία $x_{i}$ , με $i=1,3$ και $N=5,7,9,11$ . Το σημείο $x_{1}$ είναι το πρώτο σημείο στο οποίο υπολογίζουμε την προσέγγιση και, καθώς το $N$ αυξάνει, αυτό θα πλησιάζει το σημείο $x_{0}=0$ . Αν και το σημείο $x_{1}$ μεταβάλλεται για κάθε διαμερισμό, το σφάλμα $|U_{1}-u(x_{1})|$ ελαττώνεται, καθώς το $N$ αυξάνει. Αυτό ισχύει για όλα τα σημεία του διαμερισμόυ και πραγματικά η ποσότητα $\max_{1\leq i\leq N}|U_{i}-u(x_{i})|$ φθίνει, καθώς το πλήθος των σημείων αυξάνει. Αυτήν την προσεγγιστική ιδιότητα που έχει η μέθοδος πεπερασμένων διαφορών (3.6)–(3.7) αποδεικνύουμε παρακάτω στο Θεώρημα 3.2.

$N$	$x_{1}$	$\|U_{1}-u(x_{1})\|$	$x_{3}$	$\|U_{3}-u(x_{3})\|$	$\displaystyle\max_{0\leq i\leq N+1}\|U_{i}-u(x_{i})\|$
5	0.2	0.0051	0.6	0.046	0.0080
7	0.1429	0.0021	0.4286	0.0072	0.0072
9	0.1111	0.0010	0.3333	0.0056	0.0070
11	0.0909	0.0005	0.2727	0.0041	0.0069

Πίνακας 3.1: Τα σφάλματα του Παραδείγματος 3.1 στα σημεία

x_{1}

και

x_{3}

και το μέγιστο σφάλμα σε κάθε σημείο του διαμερισμού, για

N=5,7,9,11