ΓΡΑΜΜΙΚΑ ΣΥΣΤΗΜΑΤΑ ΕΞΙΣΩΣΕΩΝ

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

Θεωρήστε τις ευθείες

$$3x-y = 5,$$ (1)

$$2x-2y = 10,$$ (2)

στο επίπεδο. Οι ευθείες αυτές θα έχουν ένα σημείο τομής (αν, όπως συμβαίνει εδώ, δεν είναι παράλληλες ή δεν ταυτίζονται), έστω $(x_0, y_0)$. Το σημείο $(x_0, y_0)$ θα ανήκει και στις δύο ευθείες, άρα θα ικανοποιεί τόσο την (1) όσο και τη (2). Λέμε τότε ότι το $(x_0, y_0)$ είναι λύση του συστήματος των (1) και (2).

Οι (1) και (2) αποτελούν ένα γραμμικό σύστημα εξισώσεων (γιατί λέγεται γραμμικό;) το οποίο μπορεί να γραφεί, ισοδύναμα, χρησιμοποιώντας άλγεβρα πινάκων, ως

$$\left( \begin{array}{cc} 3 & -1 \\ 2 & -2 \end{array}\righ... ...right) = \left( \begin{array}{c} 5 \\ 10 \end{array}\right),$$ (3)

είναι δηλαδή της μορφής

$$(a)\bar{x}=\bar{b},$$ (4)

όπου το $\bar{}$ θα συμβολίζει ένα διάνυσμα ή πίνακα στήλη. Αν το διάνυσμα $\bar{b}$ είναι το μηδενικό διάνυσμα, τότε το γραμμικό σύστημα λέγεται ομογενές.

Το πρόβλημα που θα αντιμετωπίσουμε εδώ είναι η επίλυση γραμμικών συστημάτων, δηλαδή ο προσδιορισμός του άγνωστου διανύσματος $\bar{x}$, δεδομένου του πίνακα $(a)$, ο οποίος λέγεται πίνακας του συστήματος, και του διανύσματος των σταθερών όρων, $\bar{b}$. (Θα περιοριστούμε σε συστήματα στα οποία ο $(a)$ είναι τετραγωνικός πίνακας, δηλαδή συστήματα με ίσο αριθμό εξισώσεων και αγνώστων.)

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

Για να περιγράψουμε τους τρόπους επίλυσης γραμμικών συστημάτων και τις συνθήκες ύπαρξης λύσης θα θεωρήσουμε το πιο γενικό σύστημα $2 \times 2$,

$$a_{11}x_1 + a_{12}x_2 = b_1$$

$$a_{21}x_1+ a_{22}x_2 = b_2 ,$$ (5)

που σε μορφή πινάκων παίρνει τη μορφή

$$(a)\bar{x}=\bar{b} \hspace{3mm} \leftrightarrow \hspace{3mm}... ...ht) = \left( \begin{array}{c} b_1 \\ b_2 \end{array}\right).$$ (6)

1. Απλή αντικατάσταση

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

$$x_1=(b_1-a_{12}x_2)/a_{11},$$

$$a_{21}(b_1-a_{12}x_2)/a_{11} +a_{22}x_2=b_2.$$ (7)

Η δεύτερη από τις παραπάνω εξισώσεις δίνει το $x_2$, το οποίο αντικαθίσταται στην πρώτη εξίσωση για τον υπολογισμό του $x_1$.

2. Μέθοδος ευθείας αντιστροφής

Η μέθοδος αυτή συνίσταται στον πολλαπλασιασμό και των δύο μελών της εξίσωσης $(a)\bar{x}=\bar{b}$ με τον αντίστροφο του πίνακα $(a)$, τον $(a)^{-1}$. Για να μπορεί να γίνει αυτό θα πρέπει ο $(a)$ να είναι αντιστρέψιμος, ή, ισοδύναμα, η ορίζουσά του να είναι διαφορετική από μηδέν ( ${\rm det}(a) \neq 0$). Τότε έχουμε

$$(a)\bar{x}=\bar{b} \Rightarrow (a)^{-1}(a)\bar{x}=(a)^{-1}\bar{b}\Rightarrow \bar{x}=(a)^{-1}\bar{b}.$$ (8)

Αν το διάνυσμα $\bar{b}$ είναι μηδέν τότε η μόνη λύση του συστήματος είναι η μηδενική.

Αν η ορίζουσα του $(a)$ είναι μηδέν, το σύστημα είτε δεν έχει λύση ή έχει άπειρες λύσεις.

Λόγω της εμπλοκής πολλών πράξεων στη διαδικασία εύρεσης του αντιστρόφου, η μέθοδος ευθείας αντιστροφής δεν προσφέρεται για την επίλυση μεγάλων συστημάτων. Τα βασικά της πλεονεκτήματα είναι ότι προσφερεται για την περίπτωση όπου χρειάζεται η επίλυση πολλών συστημάτων με τον ίδιο πίνακα $(a)$ αλλά διαφορετικό δεξιό διάνυσμα $\bar{b}$, καθώς και το ότι βοηθά να εξαχθούν οι συνθήκες επιλυσιμότητας των γραμμικών συστημάτων.

3. Μέθοδος του Cramer ή των οριζουσών

Μια άλλη μέθοδος χρήσιμη για την επίλυση σχετικά μικρών συστημάτων καθώς και γαι τη διερεύνηση τέτοιων συστημάτων είναι η μέθοδος του Cramer ή των οριζουσών, η οποία δίνει τους αγνώστους του συστήματος ως πηλίκα δύο οριζουσών. Στη συνέχεια παρουσιάζουμε και επεξηγούμε τη μέθοδο αυτή, χρησιμοποιώντας το σύστημα (6).

Έστω ο πίνακας $(a)$ του συστήματος (6), με ${\rm det}(a) \neq 0$. Πολλαπλασιάζοντας επί $x_1$ την ορίζουσα του πίνακα αυτού παίρνουμε

$$x_1\left\vert(a)\right\vert= x_1\left\vert \begin{array}{cc}... ...{11} & a_{12} \\ x_1 a_{21} & a_{22} \end{array}\right\vert.$$ (9)

Σύμφωνα με τις ιδιότητες των οριζουσών, η ορίζουσα (8) δεν αλλαζει αν στην πρώτη στήλη προσθέσουμε ένα πολλαπλάσιο της δεύτερης στήλης. Προσθέτοντας το $x_2 \times$2η στήλη και χρησιμοποιώντας τις εξισώσεις (5), παίρνουμε

$$x_1\left\vert(a)\right\vert = \left\vert \begin{array}{cc} x... ...1={\left\vert(a_1)\right\vert \over \left\vert(a)\right\vert},$$ (10)

όπου $(a_1)$ είναι ο πίνακας που προκύπτει από τον $(a)$ με αντικατάσταση της στήλης των συντελεστών του $x_1$ ($a_{11}$ και $a_{21}$) από τη στήλη των σταθερών όρων ($b_{1}$ και $b_{2}$). Ακολουθώντας την ανάλογη διαδικασία για το $x_2$, βρίσκουμε $x_2=\left\vert(a_2)\right\vert/ \left\vert(a)\right\vert.$

Γενικά, για σύστημα $n$ εξισώσεων με $n$ αγνώστους

$$x_i={\left\vert(a_i)\right\vert \over \left\vert(a)\right\vert}, \hspace{5mm} i=1, 2, ..., n,$$ (11)

όπου $(a_i)$ είναι ο πίνακας που προκύπτει από τον $(a)$ αν αντικαταστήσουμε τη στήλη που περιέχει τους συντελεστές του $x_i$ από τη στήλη των σταθερών όρων. Η ορίζουσες των πινάκων $(a_i)$ λέγονται ορίζουσες Cramer και η εξίσωση (11) δίνει τις λύσεις γραμμικού συστήματος με τη μέθοδο του Cramer.

Συνθήκες επιλυσιμότητας γραμμικών συστημάτων: Mε οδηγό την Εξ. (8), το γεωμετρικό παράδειγμα (3) και τις εξισώσεις (11) συμπεραίνουμε τα εξής:

• H μόνη περίπτωση το γραμμικό σύστημα
  
  $$(a)\bar{x}=\bar{b}$$
  
  
  να έχει μοναδική λύση είναι ${\rm det}(a) \neq 0$. Τότε υπάρχει ο $(a)^{-1}$, και η μοναδική λύση του συστήματος είναι $\bar{x}=(a)^{-1}\bar{b}$.

• Αν ${\rm det}(a)=0$, π.χ.
  
  $$(a)=\left( \begin{array}{cc} 3 & -1 \\ 6 & -2 \end{array}\right),$$
  
  
  τότε το σύστημα είτε

  -

  δεν έχει καμία λύση (η συνήθης περίπτωση) ή

  -

  έχει άπειρες λύσεις,

  ανάλογα με το τι είναι το διάνυσμα $\bar{b}$.

  Άπειρες λύσεις έχουμε στην περίπτωση που το διάνυσμα $\bar{b}$: (i) είτε είναι μηδέν, (ii) είτε παίρνει κάποιες άλλες συγκεκριμμένες τιμές, π.χ., εδώ, $\bar{b}^{Τ}=(5, 10)$. Η περίπτωση (i) για τον πιο πάνω πίνακα $(a)$ θα σήμαινε σύστημα της μορφής $3x-y=0$ και $6x-2y=0$. Λύση τότε θα είναι όλα τα $x$ και $y$ που ικανοποιούν την $y=3x$, δηλαδή κάθε διάνυσμα
  

  $$\bar{x}=\left( \begin{array}{c} x \\ 3x \end{array}\right).$$
  
  
  Η περίπτωση (ii) ( $\bar{b}^{Τ}=(5, 10)$) θα οδηγούσε στις άπειρες λύσεις $\bar{x}^{Τ}=(x, 3x-5)$.

  Σε αυτές τις περιπτώσεις, (i) και (ii), οι ορίζουσες Cramer του συστήματος είναι όλες ίσες με μηδέν. Δηλαδή, ένα γραμμικό σύστημα με ${\rm det}(a)=0$ έχει άπειρες λύσεις στην περίπτωση που οι ορίζουσες Cramer του είναι όλες ίσες με μηδέν.

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

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

-

${\rm det}(a)\ne 0$ $\Rightarrow$ υπάρχει μοναδική λύση.

-

${\rm det}(a)=0$ και ορίζουσες Cramer όχι όλες μηδέν $\Rightarrow$ καμία λύση.

-

${\rm det}(a)=0$ και ορίζουσες Cramer όλες μηδέν $\Rightarrow$ άπειρες λύσεις.

Για την ειδική περίπτωση των ομογενών γραμμικών συστημάτων, δηλαδή των συστημάτων της μορφής $(a)\bar{x}=0$, η οποία συναντάται πολύ συχνά σε εφαρμογές, οι συνθήκες επιλυσιμότητας, οι οποίες αναφέρθηκαν στην προηγούμενη παράγραφο, μεταφράζονται ως εξής:

-

Αν ${\rm det}(a)\ne 0$ $\Rightarrow$ υπάρχει μοναδική λύση, η οποία είναι η μηδενική, δηλ. $\bar{x}=0$.

-

Αν ${\rm det}(a)=0$ υπάρχουν άπειρες λύσεις.

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

4. Απαλοιφή Gauss

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

Θα παρουσιάσουμε αναλυτικότερα την παραπάνω διαδικασία, χρησιμοποιώντας ένα συγκεκριμμένο σύστημα $3\times 3$. Έστω το σύστημα

$$x-2y+z = 4$$

$$x-y-z = 2$$ (12)

$$2x+4y-z = -21.$$

Πολλαπλασιάζουμε την πρώτη γραμμή επί (-1) και την προσθέτουμε στη 2η και επί (-2) και την προσθέτουμε στην 3η (ώστε να μηδενιστεί ο συντελεστής του $x$ στη 2η και 3η εξίσωση). Παίρνουμε το ισοδύναμο σύστημα¹

$$x-2y+z = 4$$

$$+y-2z = -2$$ (13)

$$+8y-3z = -29.$$

Τώρα πολλαπλασιάζουμε τη 2η γραμμή επί (-8) και την προσθέτουμε στην 3η. Παίρνουμε

$$x-2y+z = 4$$

$$+y-2z = -2$$ (14)

$$13z = -13.$$

Το παραπάνω σύστημα μπορεί να λυθεί πολύ εύκολα, πηγαινοντας προς τα πίσω και αντικαθιστώντας το αποτέλεσμα της κάθε εξίσωσης στην αμέσως προηγούμενη (η διαδικασία αυτή είναι γνωστή ως ``ανάδρομη αντικατάσταση''). Δηλ. $z=-1$, $y-2(-1)=-2 \Rightarrow y=-4$, $x-2(-4)+(-1)=4 \Rightarrow x=-3$.

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

$$\left( \begin{array}{rrrr} 1 & -2 & 1 & 4 \\ 1 & -1 & -1 & ... ... \\ 0 & 1 & -2 & -2 \\ 0 & 0 & 13 & -13 \end{array}\right).$$ (15)

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

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

5. Τριγωνική παραγοντοποίηση ή παραγοντοποίηση LU

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

Κατά τη μέθοδο αυτή ο πίνακας του συστήματος γράφεται ως γινόμενο ενός κάτω τριγωνικού πίνακα, ($l$) (από το lower triangular), και ενός άνω τριγωνικού πίνακα, ($u$) (από το upper triangular):

$$(a)=(l)(u).$$ (16)

Π.χ., για το σύστημα (6),

$$\left( \begin{array}{cc} a_{11} & a_{12} \\ a_{21} & a_{22}... ...array}{cc} u_{11} & u_{12} \\ 0 & u_{22} \end{array}\right).$$ (17)

(κατά σύμβαση παίρνουμε τα στοιχεία της κύριας διαγωνίου του $(l)$ ως μονάδα). Οι πίνακες $(l)$ και $(u)$ υπολογίζονται εκτελώντας τον πολλαπλασιασμό στη σχέση (17) και εξισώνοντας τα στοιχεία του πίνακα που προκύπτει με τα αντίστοιχα στοιχεία του $(a)$.

Το γραμμικό σύστημα $(a)\bar{x}=\bar{b}$, τότε, παίρνει τη μορφή $(l)(u)\bar{x}=\bar{b}$. Θέτοντας $\bar{y}=(u)\bar{x}$ η επίλυση του αρχικού συστήματος ανάγεται στην επίλυση των δύο συστημάτων

$$(l)\bar{y}=\bar{b}, \hspace{5mm} (u)\bar{x}=\bar{y},$$ (18)

η οποία μπορεί να γίνει εύκολα, με αντικατάσταση, μια και πρόκειται για τριγωνικά συστήματα.