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

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

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

Ιστορία

Η μέθοδος της απαλοιφής Gauss εμφανίζεται στο Κινέζικο μαθηματικό κείμενο Κεφάλαιο Οκτώ ''Ορθογώνιοι'' ''Πίνακες'' του ''Τα εννέα κεφάλαια της μαθηματικής τέχνης''. Η χρήση του απεικονίζεται σε δεκαοκτώ προβλήματα, με δύο έως πέντε εξισώσεις. Η πρώτη αναφορά στο βιβλίο με αυτόν τον τίτλο κυκλοφόρησε το 179 CE, αλλά τμήματά του ήταν γραμμένα τόσο νωρίς όσο περίπου το 150 Π. χ. Σχολιάστηκε από τον Liu Hui τον 3ο αιώνα.
Η μέθοδος στην Ευρώπη προέρχεται από τις σημειώσεις του Isaac Newton. Το 1670, έγραψε ότι όλα τα γνωστά σε αυτόν βιβλία άλγεβρας στερούνταν ένα μάθημα για την επίλυση ταυτόχρονων εξισώσεων, το οποίο ο Νεύτωνας στη συνέχεια παρείχε. To πανεπιστήμιο του Cambridge τελικά δημοσίευσε τις σημειώσεις ως Arithmetica Universalis το 1707 πολύ καιρό μετά αφού ο Νεύτωνας άφησε την ακαδημαϊκή του ζωή. Οι σημειώσεις αντιγράφηκαν παντού, οι οποίες δημιούργησαν (που τώρα ονομάζεται) απαλοιφή Gauss ένα πρότυπο μάθημα στα βιβλία άλγεβρας από το τέλος του 18ου αιώνα. Ο Carl Friedrich Gauss, το 1810, επινόησε μια σημείωση για συμμετρική απαλοιφή που εκδόθηκε τον 19ο αιώνα από το επαγγελματικό υπολογιστή χειρός για να λύσει τις κανονικές εξισώσεις του προβλήματος των ελάχιστων τετραγώνων.  Ο αλγόριθμος που θα διδάσκεται στο γυμνάσιο ονομάστηκε Gauss μόνο στη δεκαετία του 1950, ως αποτέλεσμα της σύγχυσης πάνω στην ιστορία του θέματος
Μερικοί συγγραφείς χρησιμοποιούν τον όρο απαλοιφή Gauss για να αναφερθούν μόνο στη διαδικασία έως ότου ο πίνακας είναι σε κλιμακωτή μορφή, και χρησιμοποιούν τον όρο Gauss-Jordan απαλοιφή για να αναφερθούν στη διαδικασία που καταλήγει σε μειωμένη κλιμακωτή μορφή. Το όνομα χρησιμοποιείται γιατί είναι μια παραλλαγή της απαλοιφής Gauss, όπως περιγράφεται από τον Wilhelm Jordan το 1888. Ωστόσο, η μέθοδος, επίσης, εμφανίζεται σε ένα άρθρο από τον Clasen που δημοσιεύτηκε το ίδιο έτος.  Ο Jordan και ο Clasen πιθανότατα ανακάλυψαν ανεξάρτητα την Gauss–Jordan απαλοιφή.

Εφαρμογές

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

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

Μια παραλλαγή της απαλοιφής Gauss που ονομάζεται Gauss–Jordan απαλοιφή μπορεί να χρησιμοποιηθεί για την εύρεση του αντιστρόφου ενός πίνακα, αν υπάρχει. Εάν A είναι ένας n x n τετραγωνικός πίνακας, τότε μπορεί κανείς να χρησιμοποιήσει τη διαδικασία μείωσης της σειράς για τον υπολογισμό του αντιστρόφου πίνακα, αν υπάρχει. Πρώτον, ο n x n ταυτοτικός πίνακας αυξάνεται δεξιά από τον A , σχηματίζοντας ένα n x 2n επαυξημένο πίνακα [A | I]. Τώρα, με την εφαρμογή των στοιχειωδών πράξεων της σειράς, βρείτε την μειωμένη κλιμακωτή μορφή του n x 2n πίνακα. Ο πίνακας Α είναι αντιστρέψιμος αν και μόνο αν το αριστερό κομμάτι μπορεί να μειωθεί στον ταυτοτικό πίνακα I: στην περίπτωση αυτή το δεξιό κομμάτι του τελικού πίνακα είναι ο A⁻¹. Αν ο αλγόριθμος δεν είναι σε θέση να μειώσει το αριστερό κομμάτι στον I, τότε ο A δεν είναι αντιστρέψιμος.
Για παράδειγμα, θεωρήστε τον ακόλουθο πίνακα
Για να βρεθεί ο αντίστροφος αυτού του πίνακα, παίρνει κανείς τον ακόλουθο πίνακα αυξανόμενο με την ταυτοτικό, και τον μειώνει ως έναν 3 x 6 πίνακα:
Εκτελώντας μια σειρά ενεργειών, μπορεί κανείς να ελέγξει ότι η μειωμένη κλιμακωτή μορφή από αυτόν τον επαυξημένο πίνακα είναι:
Μπορεί κανείς να σκεφτεί κάθε σειρά πράξεων ως το αριστερό γινόμενο από έναν στοιχειώδη πίνακα. Συμβολίζοντας με Β , το γινόμενο αυτών των στοιχειωδών πινάκων, είδαμε, στα αριστερά, ότι BA = I και, επομένως, B = A⁻¹. Στα δεξιά, παρατηρούμε ότι BI = B, το οποίο γνωρίζουμε ότι είναι το αντίθετο από το επιθυμητό. Η διαδικασία αυτή για την εύρεση του αντιστρόφου λειτουργεί για τετραγωνικούς πίνακες οποιουδήποτε μεγέθους.

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

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

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

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

Γενικεύσεις

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

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

Όπως εξηγήθηκε παραπάνω, απαλοιφή Gauss γράφει ένα δοσμένο  ×  πίνακα  ως μοναδικό γινόμενο ενός αντιστρέψιμου  ×  πίνακα  και ενός πίνακα σε μειωμένη κλιμακωτή μορφή . Εδώ, το  είναι το γινόμενο των πινάκων που αντιστοιχούν πράξεις που εκτελούνται στις σειρές.
Ο επίσημος αλγόριθμος για να υπολογίσει ο   από το  είναι ο εξής. Γράφουμε  για την είσοδο στη σειρά , στη στήλη  στον πίνακα  με το 1 να είναι ο πρώτος δείκτης. Η μετατροπή γίνεται σε θέση, με την έννοια ότι ο αρχικός πίνακας  χάθηκε και αντικαταστάθηκε διαδοχικά από τον .
 για κ = 1 ... min(m,n): 
Βρείτε την k-οστή περιστροφή: 
i_max  := argmax (i = k, ... m, abs(A[i, k])) 
αν A[i_max, k] = 0 
  σφάλμα "o Πίνακας είναι μοναδικός!" 
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, που εκμεταλλεύονται τις λεπτομέρειες του υλικού του υπολογιστή και τη δομή του πίνακα για να επιλεχθεί αυτόματα ο καλύτερος αλγόριθμος.