Γραμμικά συστήματα

Επιστροφή στη Γραμμική Άλγεβρα.

Σύστημα γραμμικών εξισώσεων

Έστω μια εξίσωση m αγνώστων x_i με σταθερούς συντελεστές: $a_{1}x_{1}+a_{2}x_{2}+...+a_{k}x_{k}+...+a_{m}x_{m}=b$

Αυτή η εξίσωση ονομάζεται γραμμική γιατί είναι γραμμικός συνδυασμός των αγνώστων. Η εξίσωση μπορεί να γραφτείσε αυτήν τη μορφή:

${\begin{bmatrix}a_{1}&a_{2}&...&a_{k}&...&a_{m}\end{bmatrix}}\times {\begin{bmatrix}x_{1}\\x_{2}\\...\\x_{k}\\...\\x_{m}\end{bmatrix}}=[b]$

Έστω δύο γραμμικές εξισώσεις m μεταβλητών:

$a_{11}x_{1}+a_{12}x_{2}+...+a_{1k}x_{k}+...+a_{1m}x_{m}=b_{1}$
$a_{21}x_{1}+a_{22}x_{2}+...+a_{2k}x_{k}+...+a_{2m}x_{m}=b_{2}$

Αυτές μπορούν να γραφτούν στη μορφή: ${\begin{bmatrix}a_{11}&a_{12}&...&a_{1k}&...&a_{1m}\\a_{21}&a_{22}&...&a_{2k}&...&a_{2m}\end{bmatrix}}\times {\begin{bmatrix}x_{1}\\x_{2}\\...\\x_{k}\\...\\x_{m}\end{bmatrix}}={\begin{bmatrix}b_{1}\\b_{2}\end{bmatrix}}$

Αν μια μεταβλητή εμφανίζεται στη μία εξίσωση αλλά όχι στην άλλη, αρκεί να θεωρηθεί ότι ο συντελεστής της στην άλλη είναι 0.

Αν οι εξισώσεις είναι n, τότε αυτές γράφονται στην εξής μορφή:

${\begin{bmatrix}a_{11}&a_{12}&...&a_{1k}&...&a_{1m}\\a_{21}&a_{22}&...&a_{2k}&...&a_{2m}\\...&...&&...&&...\\a_{l1}&a_{l2}&...&a_{lk}&...&a_{lm}\\...&...&&...&&...\\a_{n1}&a_{n2}&...&a_{nk}&...&a_{nm}\end{bmatrix}}\times {\begin{bmatrix}x_{1}\\x_{2}\\...\\x_{k}\\...\\x_{m}\end{bmatrix}}={\begin{bmatrix}b_{1}\\b_{2}\\...\\b_{l}\\...\\b_{m}\end{bmatrix}}$

Έστω ${\underline {a}}={\begin{bmatrix}a_{11}&a_{12}&...&a_{1k}&...&a_{1m}\\a_{21}&a_{22}&...&a_{2k}&...&a_{2m}\\...&...&&...&&...\\a_{l1}&a_{l2}&...&a_{lk}&...&a_{lm}\\...&...&&...&&...\\a_{n1}&a_{n2}&...&a_{nk}&...&a_{nm}\end{bmatrix}},{\underline {x}}={\begin{bmatrix}x_{1}\\x_{2}\\...\\x_{k}\\...\\x_{m}\end{bmatrix}},{\underline {b}}={\begin{bmatrix}b_{1}\\b_{2}\\...\\b_{l}\\...\\b_{m}\end{bmatrix}}$

Τότε το σύστημα γραμμικών εξισώσεων γράφεται στη μορφή: ${\underline {a}}{\underline {x}}={\underline {b}}$ Η λύση του συστήματος αυτού είναι η:

${\underline {x}}=({\underline {a}})^{-1}{\underline {b}}$

Επίλυση κατά Γκάους

Η μέθοδος Γκάους λύνει το πρόβλημα με γραμμοπράξεις. Οι γραμμοπράξεις αλλάζουν τον ${\underline {a}}$ και τον ${\underline {b}}$, ενώ η λύση ${\underline {x}}$ παραμένει η ίδια. Οι γραμμοπράξεις εφαρμόζονται στον πίνακα $[{\underline {a}}{\underline {b}}]$. Οι γραμμοπράξεις είναι οι εξείς δύο:

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

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

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

Παράδειγμα

Έστω το σύστημα:

${\begin{bmatrix}-5&2&3\\3&-2&0\\4&1&-2\end{bmatrix}}\times {\underline {x}}={\begin{bmatrix}8\\-1\\0\end{bmatrix}}$

Οι γραμμοπράξεις θα εφαρμοστούν στον πίνακα:

${\begin{bmatrix}-5&2&3&8\\3&-2&0&-1\\4&1&-2&0\end{bmatrix}}$

${\begin{bmatrix}-5&2&3&8\\3&-2&0&-1\\4&1&-2&0\end{bmatrix}}\rightarrow {\begin{bmatrix}-15&6&9&24\\15&-10&0&-5\\4&1&-2&0\end{bmatrix}}\rightarrow {\begin{bmatrix}-5&2&3&8\\0&-4&9&19\\4&1&-2&0\end{bmatrix}}\rightarrow {\begin{bmatrix}-20&8&12&32\\0&-4&9&19\\20&5&-10&0\end{bmatrix}}\rightarrow$

${\begin{bmatrix}-20&8&12&32\\0&-4&9&19\\0&13&2&32\end{bmatrix}}\rightarrow {\begin{bmatrix}-20&8&12&32\\0&-52&117&247\\0&52&8&128\end{bmatrix}}\rightarrow {\begin{bmatrix}-20&8&12&32\\0&-4&9&19\\0&0&125&375\end{bmatrix}}\rightarrow {\begin{bmatrix}-20&8&12&32\\0&-4&9&19\\0&0&1&3\end{bmatrix}}\rightarrow$

${\begin{bmatrix}-20&8&12&32\\0&-4&9&19\\0&0&-9&-27\end{bmatrix}}\rightarrow {\begin{bmatrix}-20&8&12&32\\0&-4&0&-8\\0&0&-12&-36\end{bmatrix}}\rightarrow {\begin{bmatrix}-20&8&0&-4\\0&-8&0&-16\\0&0&1&3\end{bmatrix}}\rightarrow {\begin{bmatrix}-20&0&0&-20\\0&1&0&2\\0&0&1&3\end{bmatrix}}\rightarrow {\begin{bmatrix}1&0&0&1\\0&1&0&2\\0&0&1&3\end{bmatrix}}$

Άρα η λύση του αρχικού συστήματος είναι η ${\underline {x}}={\begin{bmatrix}x\\y\\z\end{bmatrix}}={\begin{bmatrix}1\\2\\3\end{bmatrix}}$, δηλαδή x=1, y=2, z=3.

Μη τετραγωνικός πίνακας ή μηδενικές γραμμές

Σκοπός της μεθόδου είναι η δημιουργία ενός πίνακα σε άνω κλιμακωτή μορφή. Η άνω κλιμακωτή μορφή είναι άνω τριγωνική με πιθανώς περισσότερα μηδενικά στην αρχή των γραμμών. Στην άνω κλιμακωτή μορφή αν η i-στη και η j-στη γραμμή έχουν n και m μηδενικά στην αρχή της γραμμής αντίστοιχα με i<j, τότε n<m. Για παράδειγμα:

${\begin{bmatrix}-5&2&3&8\\0&0&2&-1\\0&0&4&-2\end{bmatrix}}$

Αυτή δεν είναι άνω κλιμακωτή, γιατί για την 2η και 3η γραμμή υπάρχουν 2 μηδενικά στην αρχή και των δύο γραμμών. Είναι 2<3, αλλά 2=2. Η παρακάτω ισοδύναμη μορφή:

${\begin{bmatrix}-5&2&3&8\\0&0&2&-1\\0&0&0&0\end{bmatrix}}$

Αυτή είναι άνω κλιμακωτή μορφή, γιατί 2<3 και 2<4.

Επίλυση με ορίζουσες

Υπολογίζουμε την ορίζουσα D του ${\underline {a}}$. Για κάθε στοιχείο $x_{i}$:

• Αντικαθιστούμε από τον πίνακα Α την αντίστοιχη i-στη γραμμή με την στήλη ${\underline {b}}$.
• Υπολογίζουμε την ορίζουσα $D_{i}$ αυτού του πίνακα.
• Η τιμή του $x_{i}$ είναι $x_{i}=D_{i}/D$

Παράδειγμα

Στο προηγούμενο παράδειγμα:

$D={\begin{vmatrix}-5&2&3\\3&-2&0\\4&1&-2\end{vmatrix}}=-23$
$D_{1}={\begin{vmatrix}8&2&3\\-1&-2&0\\0&1&-2\end{vmatrix}}=-23$
$D_{2}={\begin{vmatrix}-5&8&3\\3&-1&0\\4&0&-2\end{vmatrix}}=-46$
$D_{3}={\begin{vmatrix}-5&2&8\\3&-2&-1\\4&1&0\end{vmatrix}}=-69$

Άρα $x=1,y=2,z=3$

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

Πολλά συστήματα γραμμικών εξισώσεων

Έστω δύο συστήματα γραμμικών εξισώσεων:

• ${\underline {a}}{\underline {x_{1}}}={\underline {b_{1}}}$
• ${\underline {a}}{\underline {x_{2}}}={\underline {b_{2}}}$

Παρατηρείται ότι: ${\underline {a}}{\begin{bmatrix}{\underline {x_{1}}}{\underline {x_{2}}}\end{bmatrix}}={\begin{bmatrix}{\underline {a}}{\underline {x_{1}}}&{\underline {a}}{\underline {x_{2}}}\end{bmatrix}}={\begin{bmatrix}{\underline {b_{1}}}&{\underline {b_{2}}}\end{bmatrix}}$

Έστω:

• ${\underline {x}}={\begin{bmatrix}{\underline {x_{1}}}{\underline {x_{2}}}\end{bmatrix}}$
• ${\underline {b}}={\begin{bmatrix}{\underline {b_{1}}}{\underline {b_{2}}}\end{bmatrix}}$

Τότε: ${\underline {a}}{\underline {x}}={\underline {b}}$

Με αυτόν τον τρόπο μπορούμε να λύσουμε ταυτόχρονα τα δύο αρχικά συστήματα. Οι μέθοδοι με τις οποία λύνεται το νέο γραμμικό σύστημα είναι ακριβώς οι ίδιες με πριν. Μόνη διαφορά ότι ο πίνακας ${\underline {b}}$ δεν είναι μια στήλη, αλλά ένα πίνακας με περισσότερες στήλες.

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

${\underline {a}}{\underline {x}}={\underline {I}}$

Συστήματα χωρίς μοναδική λύση

Παρατηρείται ότι η μέθοδος των οριζουσών δε δίνει λύση, αν ο πίνακας ${\underline {a}}$ δεν είναι τετραγωνικός ή αν η ορίζουσα του είναι 0.

Αν η ορίζουσα είναι 0, τουλάχιστον μια γραμμή του πίνακα ${\underline {a}}$ είναι γραμμικός συνδυασμός δύο άλλων στηλών. Ισοδύναμα τουλάχιστον μία στήλη του ${\underline {a}}$ είναι γραμμικός συνδυασμός δύο άλλων στηλών. Αυτό σημαίνει ότι μια εξίσωση του συστήματος γραμμικών εξισώσεων είναι γραμμικών συνδυασμός δύο άλλων εξισώσεων, άρα μπορεί να αφαιρεθεί από το σύστημα χωρίς να αλλάξει η λύση του. Με τη μέθοδο Γκάους θα προκύψει τουλάχιστον ένα μηδενικό στην κύρια διαγώνια, όταν είναι σε άνω τριγωνική μορφή. Αυτές οι περιπτώσεις αντιμετοπίζονται με τη μέθοδο Γκάους.

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

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

Οι μεταβλητές των οποίων οι αντίστοιχες στήλες δεν έχουν οδηγό είναι ελεύθερες, ενώ οι υπόλοιπες βασικές. Υπολογίζονται οι βασικές συναρτήσει των ελεύθερων. Η λύση του συστήματος είναι το διάνυσμα ${\underline {x}}$ Στο οποίο οι βασικές μεταβλητές έχουν αντικατασταθεί από την παράσταση συναρτήσει των ελευθέρων. Για παράδειγμα:

${\begin{bmatrix}1&0&1\\-2&0&-2\\0&1&1\end{bmatrix}}{\begin{bmatrix}x\\y\\z\end{bmatrix}}={\begin{bmatrix}-1\\2\\0\end{bmatrix}}$

Με γραμμοπράξεις γίνεται:

${\begin{bmatrix}1&0&1&-1\\-2&0&-2&2\\0&1&1&0\end{bmatrix}}\rightarrow {\begin{bmatrix}2&0&2&-2\\-2&0&-2&2\\0&1&1&0\end{bmatrix}}\rightarrow {\begin{bmatrix}1&0&1&-1\\0&0&0&0\\0&1&1&0\end{bmatrix}}\rightarrow {\begin{bmatrix}1&0&1&-1\\0&1&1&0\\0&0&0&0\end{bmatrix}}$

Είναι y+z=0, άρα y=-z, x+z=-1, άρα x=-1-z. Άρα η λύση του συστήματος είναι:

${\begin{bmatrix}x\\y\\z\end{bmatrix}}={\begin{bmatrix}-1-z\\-z\\z\end{bmatrix}}=z{\begin{bmatrix}-1\\-1\\1\end{bmatrix}}+{\begin{bmatrix}-1\\0\\0\end{bmatrix}}$

Παρατηρείται ότι η λύση του συστήματος γραμμικών εξισώσεων είναι ένας γραμμικός συνδυασμός δύο διανυσμάτων, ενός σταθερού και ενός ελεύθερου. Επιπλέον, ο διάνυσμα ${\underline {x}}-{\underline {b}}=z{\begin{bmatrix}-1\\-1\\1\end{bmatrix}}$ ανήκει σε έναν διανυσματικό χώρο με βάση το διάνυσμα ${\begin{bmatrix}-1\\-1\\1\end{bmatrix}}$