Γκαουσιανή απαλοιφή

Στη γραμμική άλγεβρα, η Γκαουσιανή απαλοιφή ή απαλοιφή Gauss είναι ένας αλγόριθμος για την επίλυση συστημάτων γραμμικών εξισώσεων. Είναι συνήθως αντιληπτή ως ακολουθία από πράξεις που εκτελούνται στις γραμμές του πίνακα των συντελεστών. Ο αλγόριθμος ουσιαστικά μετατρέπει τον επαυξημένο πίνακα του συστήματος σε πίνακα κλιμακωτής μορφής, που χρησιμοποιείται επίσης για την εύρεση της τάξης του πίνακα, για τον υπολογισμό της ορίζουσας ενός πίνακα και για τον υπολογισμό του αντιστρόφου τετραγωνικού πίνακα (όταν υπάρχει). Η μέθοδος πήρε το όνομά της από τον Carl Friedrich Gauss (1777-1855), αν και ήταν ήδη γνωστή από τους Κινέζους μαθηματικούς από το 179 π.Χ.).

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

1. Αντιμετάθεση δύο γραμμών
2. Πολλαπλασιασμός μιας γραμμής με ένα  μη-μηδενικό αριθμό
3. Πρόσθεση ενός πολλαπλάσιου μιας γραμμής σε μία άλλη γραμμή

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

${\displaystyle \left[{\begin{array}{rrr|r}1&3&1&9\\1&1&-1&1\\3&11&5&35\end{array}}\right]\to \left[{\begin{array}{rrr|r}1&3&1&9\\0&-2&-2&-8\\0&2&2&8\end{array}}\right]\to \left[{\begin{array}{rrr|r}1&3&1&9\\0&1&1&4\\0&2&2&8\end{array}}\right]\to \left[{\begin{array}{rrr|r}1&3&1&9\\0&1&1&4\\0&0&0&0\end{array}}\right]\to \left[{\begin{array}{rrr|r}1&0&-2&-3\\0&1&1&4\\0&0&0&0\end{array}}\right]}$

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

Ορισμοί και το παράδειγμα του αλγορίθμου

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

Σειρά ενεργειών

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

Τύπος 1: Αντιμετάθεση δύο γραμμών του πίνακα.

Τύπος 2: Πολλαπλασιασμός μιας γραμμής του πίνακα με ένα μη μηδενικό στοιχείο.

Τύπος 3: Πολλαπλασιασμός μιας γραμμής με ένα μη μηδενικό στοιχείο και πρόσθεση αυτής της γραμμής σε μία άλλη.

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

ΚΛΙΜΑΚΩΤΗ  ΜΟΡΦΗ

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

1. Όλες οι μη μηδενικές γραμμές του πίνακας βρίσκονται πάνω από τις μηδενικές γραμμές του
2. Το πρώτο μη μηδενικό στοιχείο κάθε γραμμής είναι ίσο με 1 και
3. Το πρώτο 1 κάθε γραμμής βρίσκεται δεξιότερα από το αντίστοιχο 1 της αμέσως προηγούμενης γραμμής (προς τα πάνω).

Για παράδειγμα, οι παρακάτω πίνακες είναι σε κλιμακωτή μορφή:

${\displaystyle \left({\begin{array}{cccc}0&1&1&-1\\0&0&1&1\\0&0&0&0\end{array}}\right),\quad \left({\begin{array}{cccc}1&2&-1&4\\0&1&0&0\\0&0&0&0\end{array}}\right),\quad \left({\begin{array}{cccc}1&2&-1&4\\0&1&0&0\\0&0&0&1\end{array}}\right),}$

Ένας πίνακας θα λέμε ότι είναι σε ανηγμένη κλιμακωτή μορφή αν επιπλέον το πρώτο 1 κάθε γραμμής είναι το μοναδικό μη μηδενικό στοιχείο της στήλης στην οποία ανήκει. Για παράδειγμα:

${\displaystyle \left({\begin{array}{cccc}0&1&0&-1\\0&0&1&1\\0&0&0&0\end{array}}\right),\quad \left({\begin{array}{cccc}1&0&-1&4\\0&1&0&0\\0&0&0&0\end{array}}\right),\quad \left({\begin{array}{cccc}1&0&-1&0\\0&1&0&0\\0&0&0&1\end{array}}\right),}$

Παράδειγμα του αλγορίθμου σε ένα σύστημα

Ας υποθέσουμε ότι θέλουμε να βρούμε σύνολο των λύσεων για το ακόλουθο σύστημα γραμμικών εξισώσεων:

${\displaystyle {\begin{alignedat}{7}2x&&\;+\;&&y&&\;-\;&&z&&\;=\;&&8&\qquad (L_{1})\\-3x&&\;-\;&&y&&\;+\;&&2z&&\;=\;&&-11&\qquad (L_{2})\\-2x&&\;+\;&&y&&\;+\;&&2z&&\;=\;&&-3&\qquad (L_{3})\end{alignedat}}}$

Ο παρακάτω πίνακας είναι περιγράφει ττον αλγόριθμο απαλοιφής του Gauss ταυτόχρονα στο σύστημα των εξισώσεων και στον επαυξημένο πίνακα του συστήματος. Στην πράξη, συνήθως ο αλγόριθμος εφαρμόζεται συνήθως στον επαυξημένο πίνακα και όχι στην αρχική μορφή του συστήματος. Η διαδικασία μπορεί να συνοψιστεί ως εξής: απλοποιήστε το x από όλες τις εξισώσεις κάτω από την ${\displaystyle L_{1}}$, και στη συνέχεια απλοποιήστε το y από όλες τις εξισώσεις κάτω από την ${\displaystyle L_{2}}$. Αυτό θα θέσει το σύστημα σε τριγωνική μορφή. Στη συνέχεια, χρησιμοποιώντας την μέθοδο της προς-τα-πίσω-αντικατάστασης, κάθε άγνωστος μπορεί να βρεθεί.

Το σύστημα των εξισώσεων	Σειρά ενεργειών	Επαυξημένος πίνακας
${\displaystyle {\begin{alignedat}{7}2x&&\;+\;&&y&&\;-\;&&z&&\;=\;&&8&\\-3x&&\;-\;&&y&&\;+\;&&2z&&\;=\;&&-11&\\-2x&&\;+\;&&y&&\;+\;&&2z&&\;=\;&&-3&\end{alignedat}}}$		${\displaystyle \left[{\begin{array}{ccc|c}2&1&-1&8\\-3&-1&2&-11\\-2&1&2&-3\end{array}}\right]}$
${\displaystyle {\begin{alignedat}{7}x&&\;+\;&&{\frac {1}{2}}y&&\;-\;&&{\frac {1}{2}}z&&\;=\;&&4&\\-3x&&\;-\;&&y&&\;+\;&&2z&&\;=\;&&-11&\\-2x&&\;+\;&&y&&\;+\;&&2z&&\;=\;&&-3&\end{alignedat}}}$	${\displaystyle {\frac {1}{2}}L_{1}\rightarrow L_{1}}$	${\displaystyle \left[{\begin{array}{ccc|c}1&{\frac {1}{2}}&-{\frac {1}{2}}&4\\-3&-1&2&-11\\-2&1&2&-3\end{array}}\right]}$
${\displaystyle {\begin{alignedat}{7}x&&\;+\;&&{\frac {1}{2}}y&&\;-\;&&{\frac {1}{2}}z&&\;=\;&&4&\\&&&&{\frac {1}{2}}y&&\;+&&\;{\frac {1}{2}}z&&\;=\;&&1&\\&&&&2y&&\;+&&\;z&&\;=\;&&5&\end{alignedat}}}$	${\displaystyle L_{2}+3L_{1}\rightarrow L_{2}}$  ${\displaystyle L_{3}+2L_{1}\rightarrow L_{3}}$	${\displaystyle \left[{\begin{array}{ccc|c}1&{\frac {1}{2}}&-{\frac {1}{2}}&4\\0&1/2&1/2&1\\0&2&1&5\end{array}}\right]}$
${\displaystyle {\begin{alignedat}{7}x&&\;+\;&&{\frac {1}{2}}y&&\;-\;&&{\frac {1}{2}}z&&\;=\;&&4&\\&&&&y&&\;+&&\;z&&\;=\;&&2&\\&&&&2y&&\;+&&\;z&&\;=\;&&5&\end{alignedat}}}$	${\displaystyle 2L_{2}\rightarrow L_{2}}$	${\displaystyle \left[{\begin{array}{ccc|c}1&{\frac {1}{2}}&-{\frac {1}{2}}&4\\0&1&1&2\\0&2&1&5\end{array}}\right]}$
${\displaystyle {\begin{alignedat}{7}x&&\;+\;&&{\frac {1}{2}}y&&\;-\;&&{\frac {1}{2}}z&&\;=\;&&4&\\&&&&y\;&&+&&\;z\;&&=\;&&2&\\&&&&&&&&\;-z\;&&\;=\;&&1&\end{alignedat}}}$	${\displaystyle L_{3}-2L_{2}\rightarrow L_{3}}$	${\displaystyle \left[{\begin{array}{ccc|c}1&{\frac {1}{2}}&-{\frac {1}{2}}&4\\0&1&1&2\\0&0&-1&1\end{array}}\right]}$
${\displaystyle {\begin{alignedat}{7}x&&\;+\;&&{\frac {1}{2}}y&&\;-\;&&{\frac {1}{2}}z&&\;=\;&&4&\\&&&&y\;&&+&&\;z\;&&=\;&&2&\\&&&&&&&&\;z\;&&\;=\;&&-1&\end{alignedat}}}$	${\displaystyle -L_{3}\rightarrow L_{3}}$	${\displaystyle \left[{\begin{array}{ccc|c}1&{\frac {1}{2}}&-{\frac {1}{2}}&4\\0&1&1&2\\0&0&1&-1\end{array}}\right]}$
Ο πίνακας είναι τώρα τριγωνικός και σε κλιμακωτή μορφή

Όταν ο πίνακας γίνει κλιμακωτός, το σύστημα μπορεί να λυθεί με προς τα πίσω αντικατάσταση. Η τελευταία εξίσωση μας δίνει την λύση ${\displaystyle z=-1}$. Αντικαθιστώντας αυτή την τιμή στην εξίσωση ${\displaystyle L_{2}}$ παίρνουμε ${\displaystyle y=3}$. Τέλος, αντικαθιστώντας τις τιμές ${\displaystyle z=-1}$ και ${\displaystyle y=3}$ στην ${\displaystyle L_{1}}$ παίρνουμε ${\displaystyle x=2}$.

Αντί να σταματήσει κανείς όταν ο πίνακας είναι σε κλιμακωτή μορφή, θα μπορούσε να συνεχίσει μέχρι ο πίνακας να είναι σε ανηγμένη κλιμακωτή μορφή. Αυτή η διαδικασία συνήθως αναφέρεται ως απαλοιφή Gauss-Jordan, για να διαχωριστεί από την απλή απαλοιφή Gauss. Παρακάτω δίνουμε τη διαδικασία μετατροπής σε ανηγμένο κλιμακωτό πίνακα.

Το σύστημα των εξισώσεων	Σειρά ενεργειών	Επαυξημένος πίνακας
${\displaystyle {\begin{alignedat}{7}x&&\;+\;&&{\frac {1}{2}}y&&\;-\;&&{\frac {1}{2}}z&&\;=\;&&4&\\&&&&y\;&&+&&\;z\;&&=\;&&2&\\&&&&&&&&\;z\;&&\;=\;&&-1&\end{alignedat}}}$		${\displaystyle \left[{\begin{array}{ccc|c}1&{\frac {1}{2}}&-{\frac {1}{2}}&4\\0&1&1&2\\0&0&1&-1\end{array}}\right]}$
${\displaystyle {\begin{alignedat}{7}x&&\;+\;&&{\frac {1}{2}}y&&\;\;&&&&\;=\;&&{\frac {7}{2}}&\\&&&&y\;&&&&\;\;&&=\;&&3&\\&&&&&&&&\;z\;&&\;=\;&&-1&\end{alignedat}}}$	${\displaystyle L_{2}-L_{3}\rightarrow L_{2}}$${\displaystyle L_{1}+{\frac {1}{2}}L_{3}\rightarrow L_{1}}$	${\displaystyle \left[{\begin{array}{ccc|c}1&{\frac {1}{2}}&0&{\frac {7}{2}}\\0&1&0&3\\0&0&1&-1\end{array}}\right]}$
${\displaystyle {\begin{alignedat}{7}x&&\;\;&&&&\;\;&&&&\;=\;&&2&\\&&&&y\;&&&&\;\;&&=\;&&3&\\&&&&&&&&\;z\;&&\;=\;&&-1&\end{alignedat}}}$	${\displaystyle L_{1}-{\frac {1}{2}}L_{2}\rightarrow L_{1}}$	${\displaystyle \left[{\begin{array}{ccc|c}1&{0}&{0}&{2}\\0&1&0&3\\0&0&1&-1\end{array}}\right]}$
Ο πίνακας είναι τώρα σε ανηγμένη κλιμακωτή μορφή

Ιστορία

Η μέθοδος της απαλοιφής Gauss εμφανίζεται στο Κινέζικο μαθηματικό κείμενο Κεφάλαιο Οκτώ ''Ορθογώνιοι'' ''Πίνακες'' του ''Τα εννέα κεφάλαια της μαθηματικής τέχνης''. Η χρήση του απεικονίζεται σε δεκαοκτώ προβλήματα, με δύο έως πέντε εξισώσεις. Η πρώτη αναφορά στο βιβλίο με αυτόν τον τίτλο κυκλοφόρησε το 179 CE, αλλά τμήματά του ήταν γραμμένα τόσο νωρίς όσο περίπου το 150 Π. χ.^[1][2] Σχολιάστηκε από τον Liu Hui τον 3ο αιώνα.

Η μέθοδος στην Ευρώπη προέρχεται από τις σημειώσεις του Isaac Newton^{[νεκρός σύνδεσμος]}.^[3] [4] Το 1670, έγραψε ότι όλα τα γνωστά σε αυτόν βιβλία άλγεβρας στερούνταν ένα μάθημα για την επίλυση ταυτόχρονων εξισώσεων, το οποίο ο Νεύτωνας στη συνέχεια παρείχε. To πανεπιστήμιο του Cambridge τελικά δημοσίευσε τις σημειώσεις ως Arithmetica Universalis το 1707 πολύ καιρό μετά αφού ο Νεύτωνας άφησε την ακαδημαϊκή του ζωή. Οι σημειώσεις αντιγράφηκαν παντού, οι οποίες δημιούργησαν (που τώρα ονομάζεται) απαλοιφή Gauss ένα πρότυπο μάθημα στα βιβλία άλγεβρας από το τέλος του 18ου αιώνα. Ο Carl Friedrich Gauss,^{[νεκρός σύνδεσμος]} το 1810, επινόησε μια σημείωση για συμμετρική απαλοιφή που εκδόθηκε τον 19ο αιώνα από το επαγγελματικό υπολογιστή χειρός για να λύσει τις κανονικές εξισώσεις του προβλήματος των ελάχιστων τετραγώνων.^[5]  Ο αλγόριθμος που θα διδάσκεται στο γυμνάσιο ονομάστηκε Gauss μόνο στη δεκαετία του 1950, ως αποτέλεσμα της σύγχυσης πάνω στην ιστορία του θέματος^[6]

Μερικοί συγγραφείς χρησιμοποιούν τον όρο απαλοιφή Gauss για να αναφερθούν μόνο στη διαδικασία έως ότου ο πίνακας είναι σε κλιμακωτή μορφή, και χρησιμοποιούν τον όρο Gauss-Jordan απαλοιφή για να αναφερθούν στη διαδικασία που καταλήγει σε μειωμένη κλιμακωτή μορφή. Το όνομα χρησιμοποιείται γιατί είναι μια παραλλαγή της απαλοιφής Gauss, όπως περιγράφεται από τον Wilhelm Jordan το 1888. Ωστόσο, η μέθοδος, επίσης, εμφανίζεται σε ένα άρθρο από τον Clasen που δημοσιεύτηκε το ίδιο έτος.  Ο Jordan και ο Clasen πιθανότατα ανακάλυψαν ανεξάρτητα την Gauss–Jordan απαλοιφή.^[7]

Εφαρμογές

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

Υπολογιστικοί Παράγοντες

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

• Με την εναλλαγή δύο γραμμών, πολλαπλασιάζεται η ορίζουσα με -1
• Πολλαπλασιάζοντας μια γραμμή με ένα μη μηδενικό βαθμωτό, πολλαπλασιάζεται η ορίζουσα με το ίδιο βαθμωτό
• Προσθέτοντας σε μία γραμμή με μία άλλη βαθμωτά πολλαπλασιασμένη γραμμή, η ορίζουσα δεν αλλάζει.

Αν η απαλοιφή Gauss εφαρμόζεται σε ένα τετραγωνικό πίνακα A παράγει έναν κλιμακωτό πίνακα Β, ας είναι το d το γινόμενο του βαθμωτού, με το οποίο η ορίζουσα έχει πολλαπλασιαστεί, χρησιμοποιώντας τους παραπάνω κανόνες. Τότε η ορίζουσα του A είναι το πηλίκο του d από το γινόμενο των στοιχείων της διαγωνίου του Β: det(A) = ∏diag(B) / d.

Υπολογιστικά, για ένα n×n πίνακα, αυτή η μέθοδος χρειάζεται μόνο [[O(n³)]] αριθμητικές πράξεις, ενώ η επίλυση με στοιχειώδεις μεθόδους απαιτεί O(2ⁿ) ή O(n!) πράξεις. Ακόμη και στους πιο γρήγορους υπολογιστές, οι στοιχειώδεις μέθοδοι είναι ανέφικτες για n πάνω από 20.

Εύρεση του αντιστρόφου ενός πίνακα

Μια παραλλαγή της απαλοιφής Gauss που ονομάζεται Gauss–Jordan απαλοιφή μπορεί να χρησιμοποιηθεί για την εύρεση του αντιστρόφου ενός πίνακα, αν υπάρχει. Εάν A είναι ένας n x n τετραγωνικός πίνακας, τότε μπορεί κανείς να χρησιμοποιήσει τη διαδικασία μείωσης της σειράς για τον υπολογισμό του αντιστρόφου πίνακα, αν υπάρχει. Πρώτον, ο n x n ταυτοτικός πίνακας αυξάνεται δεξιά από τον A , σχηματίζοντας ένα n x 2n επαυξημένο πίνακα [A | I]. Τώρα, με την εφαρμογή των στοιχειωδών πράξεων στις γραμμές, βρείτε την μειωμένη κλιμακωτή μορφή του n x 2n πίνακα. Ο πίνακας Α είναι αντιστρέψιμος αν και μόνο αν το αριστερό κομμάτι μπορεί να μειωθεί στον ταυτοτικό πίνακα I: στην περίπτωση αυτή το δεξιό κομμάτι του τελικού πίνακα είναι ο A^-1. Αν ο αλγόριθμος δεν είναι σε θέση να μειώσει το αριστερό κομμάτι στον I, τότε ο A δεν είναι αντιστρέψιμος.

Για παράδειγμα, θεωρήστε τον ακόλουθο πίνακα

${\displaystyle A={\begin{bmatrix}2&-1&0\\-1&2&-1\\0&-1&2\end{bmatrix}}.}$

Για να βρεθεί ο αντίστροφος αυτού του πίνακα, παίρνει κανείς τον ακόλουθο πίνακα αυξανόμενο με την ταυτοτικό, και τον μειώνει ως έναν 3 x 6 πίνακα:

${\displaystyle [A|I]=\left[{\begin{array}{rrr|rrr}2&-1&0&1&0&0\\-1&2&-1&0&1&0\\0&-1&2&0&0&1\end{array}}\right].}$

Εκτελώντας μια σειρά ενεργειών, μπορεί κανείς να ελέγξει ότι η μειωμένη κλιμακωτή μορφή από αυτόν τον επαυξημένο πίνακα είναι:

${\displaystyle [I|B]=\left[{\begin{array}{rrr|rrr}1&0&0&{\frac {3}{4}}&{\frac {1}{2}}&{\frac {1}{4}}\\[3pt]0&1&0&{\frac {1}{2}}&1&{\frac {1}{2}}\\[3pt]0&0&1&{\frac {1}{4}}&{\frac {1}{2}}&{\frac {3}{4}}\end{array}}\right].}$

Μπορεί κανείς να σκεφτεί κάθε σειρά πράξεων ως το αριστερό γινόμενο από έναν στοιχειώδη πίνακα. Συμβολίζοντας με Β , το γινόμενο αυτών των στοιχειωδών πινάκων, είδαμε, στα αριστερά, ότι BA = I και, επομένως, B = A^-1. Στα δεξιά, παρατηρούμε ότι BI = B, το οποίο γνωρίζουμε ότι είναι το αντίθετο από το επιθυμητό. Η διαδικασία αυτή για την εύρεση του αντιστρόφου λειτουργεί για τετραγωνικούς πίνακες οποιουδήποτε μεγέθους.

Υπολογίζοντας βαθμίδες και βάσεις

Ο αλγόριθμος απαλοιφής Gauss μπορεί να εφαρμοστεί σε κάθε ${\displaystyle m\times n}$ πίνακα ${\displaystyle A}$. Με αυτό τον τρόπο, για παράδειγμα, κάποιοι ${\displaystyle 6\times 9}$ πίνακες μπορούν να μετατραπούν σε ένα πίνακα που έχει έρθει σε κλιμακωτή μορφή σαν αυτή 

${\displaystyle T={\begin{bmatrix}a&*&*&*&*&*&*&*&*\\0&0&b&*&*&*&*&*&*\\0&0&0&c&*&*&*&*&*\\0&0&0&0&0&0&d&*&*\\0&0&0&0&0&0&0&0&e\\0&0&0&0&0&0&0&0&0\end{bmatrix}}}$

όπου τα * είναι αυθαίρετες καταχωρήσεις και τα a, b, c, d, e είναι μη μηδενικές καταχωρήσεις. Αυτός ο πίνακας ${\displaystyle T}$ που έχει έρθει σε κλιμακωτή μορφή περιέχει έναν πλούτο πληροφοριών σχετικά με τον ${\displaystyle A}$: η βαθμίδα του ${\displaystyle A}$ είναι 5 εφόσον υπάρχουν 5 μη-μηδενικές γραμμές στον πίνακα ${\displaystyle T}$· ο διανυσματικός χώρος που παράγεται από τις στήλες του ${\displaystyle A}$ έχει μια βάση που αποτελείται από την πρώτη, την τρίτη, την τέταρτη, την έβδομη και ένατη στήλη του ${\displaystyle A}$ (τις στήλες a, b, c, d, e στον ${\displaystyle T}$), και τα * υποδεικνύουν πως οι άλλες στήλες του ${\displaystyle A}$ μπορούν να γραφούν ως γραμμικός συνδυασμός των στηλών της βάσης. Αυτό είναι συνέπεια της επιμεριστικότητας του εσωτερικού γινομένου στην αναπαράσταση της γραμμικής απεικόνισης ως πίνακα.

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

Υπολογιστική αποδοτικότητα

Ο αριθμός των αριθμητικών πράξεων που απαιτούνται για την υλοποίηση της κλιμακωτής μορφής είναι ένας τρόπος μέτρησης της υπολογιστικής αποδοτικότητας του αλγόριθμου. Για παράδειγμα, για την επίλυση ενός συστήματος n εξισώσεων με n αγνώστους, εκτελώντας μια σειρά από πράξεις στον πίνακα μέχρι να έρθει στην κλιμακωτή μορφή, και στη συνέχεια επιλύοντας ως προς κάθε άγνωστο με αντίστροφη διαδικασία, απαιτούνται n(n+1) / 2 διαιρέσεις, (2n³ + 3n² − 5n)/6 πολλαπλασιασμοί, και (2n³ + 3n² − 5n)/6 αφαιρέσεις, για ένα σύνολο από, περίπου, 2n³ / 3 πράξεις.^[8] Έτσι, έχει την αριθμητική πολυπλοκότητα της O(n³). βλέπε τον ορισμό του Big O. Αυτή η αριθμητική πολυπλοκότητα είναι ένας καλός τρόπος μέτρησης του χρόνου που απαιτείται για το συνολικό υπολογισμό, όταν ο χρόνος για κάθε αριθμητική πράξη είναι περίπου σταθερός. Αυτή είναι η περίπτωση, όταν οι συντελεστές εκπροσωπούνται από αριθμούς κινητής υποδιαστολής ή όταν ανήκουν σε ένα πεπερασμένο πεδίο. Αν οι συντελεστές είναι ακέραιοι ή ρητοί αριθμοί με ακριβή αναπαράσταση, οι ενδιάμεσες καταχωρήσεις μπορεί να αυξάνονται εκθετικά, έτσι η πολυπλοκότητα Bit είναι εκθετική.^[9] Ωστόσο, υπάρχει μια παραλλαγή της απαλοιφής Gauss, που ονομάζεται αλγόριθμος Bareiss που αποφεύγεται αυτή η εκθετική αύξηση των ενδιάμεσων καταχωρήσεων, και, με την ίδια αριθμητική πολυπλοκότητα της O(n³), έχει την πολυπλοκότητα bit της O(n⁵).

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

Για να έρθει ένας n x n πίνακας σε μειωμένη κλιμακωτή μορφή εφαρμόζοντας πράξεις στις γραμμές του , χρειάζονται ${\displaystyle n^{3}}$ αριθμητικές πράξεις· που είναι περίπου 50% περισσότερα υπολογιστικά βήματα.^[10]

Ένα πιθανό πρόβλημα είναι η αριθμητική αστάθεια, που προκαλείται από την πιθανότητα διαίρεσης με πολύ μικρούς αριθμούς. Αν, για παράδειγμα, ο κύριος συντελεστής μίας από τις σειρές είναι πολύ κοντά στο μηδέν, τότε για να έρθει ο πίνακας σε μειωμένη κλιμακωτή μορφή θα πρέπει να γίνει διαίρεση με τον αριθμό αυτόν προκειμένου ο κύριος συντελεστής να είναι 1. Αυτό σημαίνει ότι οποιοδήποτε σφάλμα που υπήρχε για τον αριθμό που ήταν κοντά στο μηδέν θα αυξηθεί. Απαλοιφή Gauss είναι αριθμητικά σταθερή για διαγώνια κυρίαρχους ή θετικά-ορισμένους πίνακες. Για γενικούς πίνακες, η απαλοιφή Gauss συνήθως θεωρείται ότι είναι σταθερή, όταν χρησιμοποιείται μερική περιστροφή, αν και υπάρχουν παραδείγματα από σταθερούς πίνακες, για τους οποίους είναι ασταθής.^[11]

Γενικεύσεις

Η απαλοιφή Gauss μπορεί να εκτελεστεί από οποιοδήποτε τομέα, όχι μόνο των πραγματικών αριθμών.

Η απαλοιφή Gauss δεν γενικεύεται με κάποιο απλό τρόπο για υψηλότερης τάξης τανυστές (οι πίνακες είναι σειρές αναπαράστασης της τάξης 2 τανυστών)· ακόμη και ο υπολογισμός της βαθμίδας ενός τανυστή τάξης μεγαλύτερης από 2 είναι ένα δύσκολο πρόβλημα.

Ψευδοκώδικας

Όπως εξηγήθηκε παραπάνω, απαλοιφή Gauss γράφει ένα δοσμένο ${\displaystyle m}$ × ${\displaystyle n}$ πίνακα ${\displaystyle A}$ ως μοναδικό γινόμενο ενός αντιστρέψιμου ${\displaystyle m}$ × ${\displaystyle m}$ πίνακα ${\displaystyle S}$ και ενός πίνακα σε μειωμένη κλιμακωτή μορφή ${\displaystyle T}$. Εδώ, το ${\displaystyle S}$ είναι το γινόμενο των πινάκων που αντιστοιχούν πράξεις που εκτελούνται στις σειρές.

Ο επίσημος αλγόριθμος για να υπολογίσει ο  ${\displaystyle T}$ από το ${\displaystyle A}$ είναι ο εξής. Γράφουμε ${\displaystyle A[i,j]}$ για την είσοδο στη σειρά ${\displaystyle i}$, στη στήλη ${\displaystyle j}$ στον πίνακα ${\displaystyle A}$ με το 1 να είναι ο πρώτος δείκτης. Η μετατροπή γίνεται σε θέση, με την έννοια ότι ο αρχικός πίνακας ${\displaystyle A}$ χάθηκε και αντικαταστάθηκε διαδοχικά από τον ${\displaystyle T}$.

 για κ = 1 ... min(m,n): 
Βρείτε την k-οστή περιστροφή: 
i_max  := argmax (i = k, ... m, abs(A[i, k])) 
αν A[i_max, k] = 0 
  σφάλμα "ο Πίνακας είναι μοναδικός!" 
swap rows(k, i_max) 
Εκτέλεσε για όλες τις γραμμές κάτω από την περιστροφή: 
για i = k + 1 ... m: 
f := A[i, k] / A[k, k] 
Εκτέλεσε για όλα τα υπόλοιπα στοιχεία, στην τρέχουσα σειρά: 
για j = k + 1 ... n: 
A[i, j]  := A[i, j] - Α[k, j] * f 
Γέμισε τον κάτω τριγωνικό πίνακα με μηδενικά: 
A[i, k]  := 0

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

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

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

Παραπομπές

1. Calinger, Ronald (1999), A Contextual History of Mathematics,Prentice Hall, ISBN 978-0-02-318285-3,  σελ. 234–236
2. Timothy Gowers; June Barrow-Green; Imre Leader (8 Σεπτεμβρίου 2008). The Princeton Companion to Mathematics. Princeton University Press. σελ. 607. ISBN 978-0-691-11880-2.
3. Grcar, Joseph F. (2011α), "How ordinary elimination became Gaussian elimination" σελ.169-172, Historia Mathematica 38 (2): 163–218, arXiv:0907.2397, doi:10.1016/j.hm.2010.06.003
4. Grcar, Joseph F. (2011β), "Mathematicians of Gaussian elimination" σελ.783-785, Notices of the American Mathematical Society 58 (6): 782–792
5. Lauritzen P.3, Niels, Undergraduate Convexity: From Fourier and Motzkin to Kuhn and Tucker.
6. Grcar, Joseph F. (2011b), "Mathematicians of Gaussian elimination" σελ.79, Notices of the American Mathematical Society 58 (6): 782–792
7. Althoen, Steven C.; McLaughlin, Renate (1987), "Gauss–Jordan reduction: a brief history", The American Mathematical Monthly (Mathematical Association of America) 94 (2): 130–142,doi:10.2307/2322413, ISSN 0002-9890, JSTOR 2322413
8. Farebrother, R.W. (1988), Linear Least Squares Computations, STATISTICS: Textbooks and Monographs, Marcel Dekker, σελ.12,ISBN 978-0-8247-7661-9 .
9. Fang, Xin Gui; Havas, George (1997). "On the worst-case complexity of integer Gaussian elimination"^{[νεκρός σύνδεσμος]} (PDF). Proceedings of the 1997 international symposium on Symbolic and algebraic computation. ISSAC '97. Kihei, Maui, Hawaii, United States: ACM. σελ. 28–31. doi:10.1145/258726.258740. ISBN 0-89791-875-4.
10. J. B. Fraleigh and R. A. Beauregard, Linear Algebra. Addison-Wesley Publishing Company, 1995, κεφάλαιο 10
11. Golub, Gene H.; Van Loan, Charles F. (1996), Matrix Computations (3rd ed.), Johns Hopkins, ISBN 978-0-8018-5414-9 .

Εξωτερικοί σύνδεσμοι

1. Ο αλγόριθμος απαλοιφής του Gauss υλοποιημένος σε γλώσσα python και Matlab.
2. Εφαρμογή (app) για την εφαρμογή της μεθόδου απαλοιφής του Gauss.
3. Εφαρμογή (app) για android που εφαρμόζει την απαλοιφή Gauss.