1.6 ΕΠΙΛΥΣΗ ΓΡΑΜΜΙΚΟΥ ΣΥΣΤΗΜΑΤΟΣ ΜΕ ΤΗ ΜΕΘΟΔΟ ΑΠΑΛΟΙΦΗΣ ΤΟΥ GAUSS

Αποδεικνύεται ότι, αν σε ένα γραμμικό σύστημα εφαρμόσουμε μια από τις επόμενες διαδικασίες, τότε προκύπτει ισοδύναμο σύστημα: - Εναλλαγή της θέσης δύο εξισώσεων - Πολλαπλασιασμός των μελών μιας εξίσωσης με ένα μη μηδενικό αριθμό. - Πρόσθεση των μελών μιας εξίσωσης (πολλαπλασιασμένων με έναν αριθμό) στα μέλη μιας άλλης. Έτσι, όταν έχουμε να λύσουμε ένα γραμμικό σύστημα προσπαθούμε, εφαρμόζοντας τις προηγούμενες διαδικασίες, να το μετασχηματίσουμε σε ένα άλλο ισοδύναμο σύστημα του οποίου η λύση να είναι προφανής. Ας δούμε τώρα με ένα παράδειγμα πως εφαρμόζονται και πως συμβολίζονται οι τρεις αυτές διαδικασίες. Έστω το γραμμικό σύστημα [pic] [pic] [pic] - Πολλαπλασιάζουμε τα μέλη της 1ης εξίσωσης [pic] του [pic] με [pic] και τα προσθέτουμε στα αντίστοιχα μέλη της 2ης εξίσωσης [pic] του [pic]. Έτσι, απαλείφεται από την [pic] ο άγνωστος x. [pic] - Πολλαπλασιάζουμε τα μέλη της [pic] του [pic]με [pic] και τα προσθέτουμε στα μέλη της [pic]. ΄Ετσι, απαλείφεται από την [pic] ο άγνωστος x. [pic] - Πολλαπλασιάζουμε τα μέλη της [pic] του [pic]με [pic]. Έτσι, ο συντελεστής του y γίνεται 1. Συνεχίζουμε εφαρμόζοντας τις παραπάνω διαδικασίες που παριστάνουμε πλέον μόνο συμβολικά: [pic] [pic][pic] [pic] [pic] [pic] [pic] [pic] [pic] [pic] [pic] [pic] [pic] [pic] [pic] Επειδή το σύστημα [pic] είναι ισοδύναμο με το αρχικό σύστημα [pic], συμπεραίνουμε ότι η λύση του συστήματος είναι η τριάδα [pic]. Μπορούμε να περιγράψουμε απλούστερα τη διαδικασία επίλυσης ενός [pic] γραμμικού συστήματος, αν σκεφτούμε ως εξής: Αφού κάθε εξίσωση παριστάνεται με μια γραμμή του επαυξημένου πίνακα, αρκεί οι παραπάνω μετατροπές των εξισώσεων να γίνονται στις γραμμές [pic] του επαυξημένου πίνακα. Οι μετατροπές αυτές λέγονται γραμμοπράξεις και είναι οι εξής: Γραμμοπράξη - Συμβολισμός 1. Εναλλαγή της θέσης δύο γραμμών [pic] 2. Πολλαπλασιασμός μιας γραμμής με ένα μη μηδενικό αριθμό [pic], [pic] 3. Πρόσθεση των στοιχείων μιας γραμμής, πολλαπλασιασμένων με έναν αριθμό, στα [pic] αντίστοιχα στοιχεία μιας άλλης γραμμής. Όταν έχουμε δύο πίνακες Α, Β που ο ένας προκύπτει από τον άλλο με γραμμοπράξεις, τότε οι πίνακες αυτοί λέγονται γραμμοϊσοδύναμοι ή απλώς ισοδύναμοι και γράφουμε [pic]. Είναι προφανές ότι, αν οι επαυξημένοι πίνακες δύο συστημάτων είναι ισοδύναμοι, τότε και τα συστήματα είναι ισοδύναμα, αφού καθεμιά γραμμοπράξη ξεχωριστά οδηγεί σε σύστημα ισοδύναμο με το αρχικό. Έτσι, η επίλυση του προηγούμενου συστήματος μπορεί να γίνει ως εξής: [pic][pic][pic][pic] [pic][pic] [pic][pic] [pic][pic] [pic][pic] [pic][pic] [pic][pic] [pic]. Ο τελευταίος πίνακας αντιστοιχεί στο σύστημα [pic]. Επομένως, η λύση του συστήματος είναι η τριάδα [pic]. Παρατηρούμε ότι ο τελευταίος πίνακας των συντελεστών των αγνώστων είναι ο μοναδιαίος [pic] πίνακας. Έτσι μπορούμε να "διαβάσουμε" αμέσως τη λύση του συστήματος. Για να απλοποιήσουμε και να συντομεύσουμε ακόμη περισσότερο τη διαδικασία επίλυσης ενός συστήματος, πολλές φορές στο ίδιο βήμα εφαρμόζουμε περισσότερες από μία γραμμοπράξεις. Ας λύσουμε τώρα και το σύστημα [pic]. Παίρνουμε τον επαυξημένο πίνακα και έχουμε διαδοχικά: [pic][pic] [pic][pic] [pic][pic] [pic][pic] [pic][pic][pic][pic] [pic] Έτσι το αρχικό σύστημα είναι ισοδύναμο με το σύστημα [pic]. Λύνουμε την πρώτη εξίσωση ως προς έναν άγνωστο, π.χ. ως προς [pic] (αυτό μας διευκολύνει, αφού ο συντελεστής του αγνώστου αυτού είναι 1) και έχουμε [pic]. Επειδή ο άγνωστος [pic] εκφράζεται ως συνάρτηση των [pic], αυτό σημαίνει ότι μπορούμε να επιλέξουμε αυθαιρέτως τις τιμές των [pic]. Δηλαδή, το γραμμικό σύστημα έχει άπειρο πλήθος λύσεων, τις διατεταγμένες πεντάδες [pic], όπου οι [pic] μπορούν να πάρουν οποιεσδήποτε πραγματικές τιμές. Π.χ. για [pic], [pic] έχουμε τη λύση [pic] του συστήματος. Ο τελευταίος από τους παραπάνω ισοδύναμους επαυξημένους πίνακες είναι, όπως λέμε, ένας ανηγμένος κλιμακωτός πίνακας. Γενικά, δίνουμε τον επόμενο ορισμό:

ΟΡΙΣΜΟΣ Ένας [pic] πίνακας λέγεται ανηγμένος κλιμακωτός(1) , αν ισχύουν συγχρόνως τα παρακάτω: α) Οι μη μηδενικές γραμμές βρίσκονται πριν από τις μηδενικές. β) Το πρώτο από αριστερά μη μηδενικό στοιχείο κάθε μη μηδενικής γραμμής είναι το 1 και βρίσκεται δεξιότερα του αντίστοιχου 1 της προηγούμενης γραμμής. γ) Το πρώτο από αριστερά 1 κάθε μη μηδενικής γραμμής είναι και το μόνο μη μηδενικό στοιχείο της στήλης στην οποία ανήκει.

(1) Ένας [pic] πίνακας λέγεται, απλώς, κλιμακωτός, αν α) Οι μη μηδενικές γραμμές βρίσκονται πριν από τις μηδενικές και β) Το πρώτο από τα αριστερά μη μηδενικό στοιχείο κάθε γραμμής βρίσκεται δεξιότερα από το αντίστοιχο στοιχείο της προηγούμενης γραμμής, χωρίς να είναι κατ’ ανάγκη ίσο με 1.

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

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

ΑΛΓΟΡΙΘΜΟΣ ΒΗΜΑ 1ο: Βρίσκουμε την πρώτη στήλη του πίνακα που περιέχει μη μηδενικό στοιχείο. ΒΗΜΑ 2ο: Μεταφέρουμε στον πίνακα πρώτη τη γραμμή που περιέχει μη μηδενικό στοιχείο της στήλης (γραμμοπράξη 1). ΒΗΜΑ 3ο: Κάνουμε το μη μηδενικό στοιχείο της στήλης μονάδα (γραμμοπράξη 2). ΒΗΜΑ 4ο: Κάνουμε όλα τα στοιχεία της στήλης που είναι κάτω από τη μονάδα μηδενικά (γραμμοπράξη 3). ΒΗΜΑ 5ο: Αγνοούμε την πρώτη γραμμή του πίνακα και επαναλαμβάνουμε τα βήματα 1 έως 4 για τις επόμενες γραμμές του πίνακα. Αν όμως οι γραμμές που απέμειναν είναι μηδενικές, πηγαίνουμε στο 6ο βήμα. ΒΗΜΑ 6ο: Από γραμμή σε γραμμή χρησιμοποιώντας το πρώτο από αριστερά 1 κάθε γραμμής και τη γραμμοπράξη 3 κάνουμε μηδέν όλα τα στοιχεία της στήλης στην οποία βρίσκεται η μονάδα αυτή.

Ο παραπάνω αλγόριθμος, που ονομάζεται και αλγόριθμος του Gauss, ολοκληρώνεται όταν σε κάθε μη μηδενική γραμμή του πίνακα το πρώτο από αριστερά 1 είναι και το μόνο μη μηδενικό στοιχείο της στήλης στην οποία ανήκει. Έτσι για να λύσουμε ένα γραμμικό σύστημα με τον αλγόριθμο του Gauss, μετατρέπουμε τον επαυξημένο πίνακά του σε έναν ισοδύναμο ανηγμένο κλιμακωτό πίνακα. Για παράδειγμα, ας λύσουμε το σύστημα [pic]. Σχηματίζουμε τον επαυξημένο πίνακα του συστήματος [pic] και έχουμε διαδοχικά: [pic] (βήμα 2ο) [pic] [pic] (βήμα 4ο) [pic] [pic] [pic] ([pic] βήμα 3ο) [pic] [pic] (βήμα 4ο) [pic] [pic] [pic] [pic] (βήμα 6ο) [pic] [pic] (βήμα 6ο) [pic]. Ο τελευταίος πίνακας είναι ανηγμένος κλιμακωτός και αντιστοιχεί στο σύστημα [pic] που είναι ισοδύναμο με το σύστημα [pic]. Επομένως, το σύστημα έχει άπειρο πλήθος λύσεων της μορφής [pic], [pic]. Ας λύσουμε τώρα και το σύστημα: [pic]. Σχηματίζουμε τον επαυξημένο πίνακα του συστήματος και έχουμε διαδοχικά: [pic] [pic] [pic] [pic] [pic][pic] [pic]. Από την 3η γραμμή του τελευταίου πίνακα έχουμε ότι [pic] ή [pic], που σημαίνει ότι το σύστημα είναι αδύνατο. Γενικά, Αν κατά την επίλυση ενός συστήματος με τη βοήθεια του επαυξημένου πίνακα παρουσιαστεί μια γραμμή της μορφής [pic], με [pic], τότε το σύστημα είναι αδύνατο.

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