Γκαουσιανή απαλοιφή: Διαφορά μεταξύ των αναθεωρήσεων
Περιεχόμενο που διαγράφηκε Περιεχόμενο που προστέθηκε
Χωρίς σύνοψη επεξεργασίας |
Αλλαγή της έννοιας του κλιμακωτού πίνακα για να ταιριάζει με την ελληνική βιβλιογραφία. Το κείμενο είχε πολλές ασάφειες. Διόρθωση. |
||
Γραμμή 1:
{{μετάφραση}}Στη [[γραμμική άλγεβρα]], η '''Γκαουσιανή απαλοιφή''' ή '''απαλοιφή Gauss'''
Η βασική ιδέα του αλγορίθμου είναι ότι οι γραμμές του πίνακα μπορούν να τροποποιηθούν χρησιμοποιώντας κάποιους στοιχειώδεις μετασχηματισμούς, χωρίς όμως να αλλάξει ο χώρος των στηλών του και επομένως και η λύσεις του συστήματος. Ο αλγόριθμος τροποποιεί τον πίνακα μέχρι την κάτω αριστερή γωνία του συμπληρώνοντάς τον με όσο το δυνατόν περισσότερα μηδενικά. Υπάρχουν τρεις τύποι επιτρεπόμενων στοιχειωδών ενεργειών:
# Αντιμετάθεση δύο γραμμών
# Πολλαπλασιασμός μιας γραμμής με ένα μη-μηδενικό αριθμό
# Πρόσθεση ενός πολλαπλάσιου μιας γραμμής σε μία άλλη σειρά
Χρησιμοποιώντας αυτές τις ενέργειες, κάθε πίνακας μπορεί να μετατραπεί σε έναν άνω τριγωνικού πίνακα σε κλιμακωτή μορφή (ή ακόμη και σε ανηγμένη κλιμακωτή μορφή). Αυτή η τελική μορφή του πίνακα είναι μοναδική, με άλλα λόγια, είναι ανεξάρτητη από την ακολουθία των ενεργειών που χρησιμοποιούνται. Για παράδειγμα, στην παρακάτω ακολουθία εργασιών σε κάθε γραμμή (όπου πολλαπλές στοιχειώδεις λειτουργίες μπορεί να γίνουν σε κάθε βήμα), ο τέταρτος πίνακας είναι σε κλιμακωτή μορφή και ο πέμπτος πίνακας είναι σε ανηγμένη κλιμακωτή μορφή (και οι δύο μορφές είναι μοναδικές).
: <math>\left[\begin{array}{rrr|r}
1 & 3 & 1 & 9 \\
Γραμμή 14 ⟶ 18 :
\left[\begin{array}{rrr|r}
1 & 3 & 1 & 9 \\
0 &
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
Γραμμή 22 ⟶ 31 :
0 & 0 & 0 & 0
\end{array}\right] </math>
Η χρήση των παραπάνω ενεργειών με σκοπό ο πίνακας να πάρει την
== Ορισμοί και το παράδειγμα του αλγορίθμου ==
Η διαδικασία μετατροπής ενός πίνακα σε κλιμακωτή μορφή γίνεται με την χρήση αποκλειστικά μιας σειράς στοιχειωδών πράξεων. Για την επίλυση ενός συστήματος ακολουθούμε μια διαδικασία δύο βημάτων. Πρώτα μετατρέπουμε τον επαυξημένο πίανκα του συστήματος σε κλιμακωτή μορφή, από την οποία μπορεί κάποιος να διαπιστώσει αν δεν υπάρχουν λύσεις, αν υπάρχει μία μοναδική λύση, ή αν υπάρχουν άπειρες λύσεις. Στο δεύτερο βήμα (μερικές φορές ονομάζεται προς τα [[πίσω αντικατάσταση]]) χρησιμοποιούνται οι στοιχειώδεις πράξεις, μέχρι να βρεθεί η λύση του συστήματος, με άλλα λόγια, μέχρι ο πίνακας να μετατραπεί σε ανηγμένη κλιμακωτή μορφή.
=== Σειρά ενεργειών ===
Υπάρχουν τρεις τύποι '''στοιχειωδών πράξεων''' που μπορούν να εκτελούνται στις γραμμές ενός πίνακα:
'''Τύπος 1''':
'''Τύπος 3''': Πολλαπλασιασμός μιας γραμμής με ένα μη μηδενικό στοιχείο και πρόσθεση αυτής της γραμμής σε μία άλλη.
Αν σε έναν αρχικό πίνακα Α εφαρμόσουμε μια πεπερασμένη σειρά στοιχειωδών πράξεων, τότε ο πίνακας Β που προκύπτει ονομάζεται (γραμμο)ισοδύναμος με τον Α. Αν ο πίνακας σχετίζεται με ένα σύστημα γραμμικών εξισώσεων, τότε οι πράξεις αυτές δεν μεταβάλλουν το σύνολο λύσεων. Συνεπώς, αν στόχος είναι να λύσουμε ένα σύστημα γραμμικών εξισώσεων, χρησιμοποιώντας αυτές τις πράξεις το πρόβλημα γίνεται πιο εύκολο.
'''ΚΛΙΜΑΚΩΤΗ ΜΟΡΦΗ'''
Σε κάθε γραμμή σε έναν πίνακα, εάν η γραμμή δεν αποτελείται μόνο από μηδενικά, το πρώτο μη μηδενικό στοιχείο της ονομάζεται κύριος συντελεστής. Έτσι, αν δύο κύριοι συντελεστές είναι στην ίδια στήλη θα μπορούσαμε να χρησιμοποιήσουμε την στοιχειώδη πράξη τύπου 3, ώστε ένας από τους κύριους συντελεστές να γίνει μηδέν. Στη συνέχεια,εναλλάσσοντας τις γραμμές του πίνακα μπορούμε να τις διατάξουμε έτσι ώστε ο κύριος συντελεστής της κάθε γραμμής να βρίσκεται στα δεξιά του κύριου συντελεστή της προηγούμενης γραμμής. Αν έχουμε αυτή την περίπτωση, τότε ο πίνακας είναι σε κλιμακωτή (ή ανηγμένη) μορφή. Έτσι, το κάτω αριστερά μέρος του πίνακα περιέχει μόνο μηδενικά, και όλα τα μηδενικά στοιχεία των γραμμών του πίνακα βρίσκονται κάτω από τα μη μηδενικά στοιχεία των γραμμών του πίνακα. Η λέξη "κλιμακωτή" χρησιμοποιείται εδώ γιατί το μεγαλύτερο στοιχείο βρίσκεται στο πάνω μέρος του πίνακα (πρώτη σειρά) και το μικρότερο στοιχείο βρίσκεται στο κάτω μέρος του πίνακα (τελευταία σειρά). Γενικά, ένας πίνακας θα λέμε ότι είναι σε κλιμακωτή μορφή, αν:
# Όλες οι μη μηδενικές γραμμές του πίνακας βρίσκονται πάνω από τις μηδενικές γραμμές του
# Το πρώτο μη μηδενικό στοιχείο κάθε γραμμής είναι ίσο με 1 και
# Το πρώτο 1 κάθε γραμμής βρίσκεται δεξιότερα από το αντίσοτοιχο 1 της αμέσως προηγούμενης γραμμής (προς τα πάνω).
Για παράδειγμα, οι παρακάτω πίνακες είναι σε κλιμακωτή μορφή:
<math>\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),</math>
Ένας πίνακας θα λέμε ότι είναι σε ανηγμένη κλιμακωτή μορφή αν επιπλέον το πρώτο 1 κάθε γραμμής είναι το μοναδικό μη μηδενικό στοιχείο της στήλης στην οποία ανήκει. Για παράδειγμα:
<math>\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),</math>
=== Παράδειγμα
Ας υποθέσουμε ότι
<math>\begin{alignat}{7}
Γραμμή 54 ⟶ 78 :
\end{alignat}</math>
Ο παρακάτω πίνακας είναι
{| class="wikitable"
Γραμμή 76 ⟶ 100 :
|-
|<math>\begin{alignat}{7}
-3x &&\; - \;&& y &&\; + \;&& 2z &&\; = \;&& -11 & \\
-2x &&\; + \;&& y &&\; +\;&& 2z &&\; = \;&& -3 &
\end{alignat}</math>
|<math>\frac{1}{2}L_1\rightarrow L_1</math>
|<math>
\left[ \begin{array}{ccc|c}
1 & \frac{1}{2} & -\frac{1}{2} & 4 \\
-3 & -1 & 2 & -11 \\
-2 & 1 & 2 & -3
\end{array} \right]
</math>
|-
|<math>\begin{alignat}{7}
x &&\; + \;&& \frac{1}{2}y &&\; - \;&&\frac{1}{2}z &&\; = \;&& 4 & \\
&& && \frac{1}{2}y &&\; + &&\; \frac{1}{2}z &&\; = \;&& 1 & \\
&& && 2y &&\; + &&\; z &&\; = \;&& 5 &
\end{alignat}</math>
|<math>L_2 +
<math>L_3 +
|<math>\left[ \begin{array}{ccc|c}
0 & 1/2 & 1/2 & 1 \\
0 & 2 & 1 & 5
Γραμμή 89 ⟶ 127 :
|-
|<math>\begin{alignat}{7}
&& &&
&& && 2y &&\; + &&\; z &&\; = \;&& 5 &
\end{alignat}</math>
|<math>2L_2\rightarrow L_2</math>
|<math>\left[ \begin{array}{ccc|c}
1 & \frac{1}{2]} & -\frac{1}{2} & 4 \\
0 & 1 & 1 & 2 \\
0 & 2 & 1 & 5
\end{array} \right]</math>
|-
|<math>\begin{alignat}{7}
x &&\; + \;&& \frac{1}{2}y &&\; - \;&&\frac{1}{2}z &&\; = \;&& 4 & \\
&& && y \;&& + &&\; z \;&& = \;&& 2 & \\
&& && && &&\; -z \;&&\; = \;&& 1 &
\end{alignat}</math>
|<math>L_3
|<math>\left[ \begin{array}{ccc|c}
0 & 1
0 & 0 & -1 & 1
\end{array} \right]
|-
|<math>\begin{alignat}{7}
x &&\; + \;&& \frac{1}{2}y &&\; - \;&&\frac{1}{2}z &&\; = \;&& 4 & \\
&& && y \;&& + &&\; z \;&& = \;&& 2 & \\
&& && && &&\; z \;&&\; = \;&& -1 &
\end{alignat}</math>
|<math>-L_3\rightarrow L_3</math>
|<math>\left[ \begin{array}{ccc|c}
1 & \frac{1}{2]} & -\frac{1}{2} & 4 \\
0 & 1 & 1 & 2 \\
0 & 0 & 1 & -1
\end{array} \right]</math>
|-
| colspan="3" |Ο πίνακας είναι τώρα τριγωνικός και σε κλιμακωτή μορφή
|}
Όταν ο πίνακας γίνει κλιμακωτός, το σύστημα μπορεί να λυθεί με προς τα πίσω αντικατάσταση. Η τελευταία εξίσωση μας δίνει την λύση <math>z=-1</math>. Αντικαθιστώντας αυτή την τιμή στην εξίσωση <math>L_2</math> παίρνουμε <math>y=3</math>. Τέλος, αντικαθιστώντας τις τιμές <math>z=-1</math> και <math>y=3</math> στην <math>L_1</math> παίρνουμε <math>x=2</math>.
Αντί να σταματήσει κανείς όταν ο πίνακας είναι σε κλιμακωτή μορφή, θα μπορούσε να συνεχίσει μέχρι ο πίνακας να είναι σε ανηγμένη κλιμακωτή μορφή. Αυτή η διαδικασία συνήθως αναφέρεται ως '''απαλοιφή''' '''Gauss-Jordan''', για να διαχωριστεί από την απλή απαλοιφή Gauss. Παρακάτω δίνουμε τη διαδικασία μετατροπής σε ανηγμένο κλιμακωτό πίνακα.
{| class="wikitable"
!Το σύστημα των εξισώσεων
!Σειρά ενεργειών
!Επαυξημένος πίνακας
|-
|<math>\begin{alignat}{7}
&& &&
&& && && &&\;
\end{alignat}</math>
|
|<math>\left[ \begin{array}{ccc|c}
0 & 1
0 & 0 &
\end{array} \right]
|-
|<math>\begin{alignat}{7}
&& && y \;&& &&\; \;&& = \;&& 3 & \\
&& && && &&\; z \;&&\; = \;&& -1 &
\end{alignat}</math>
|<math>
|<math>\left[ \begin{array}{ccc|c}
0 & 1 & 0 & 3 \\
0 & 0 & 1 & -1
\end{array} \right]
|-
|<math>\begin{alignat}{7}
x &&\;
&& && y \;&& &&\; \;&& = \;&& 3 & \\
&& && && &&\; z \;&&\; = \;&& -1 &
\end{alignat}</math>
|<math>L_1 - \frac{1}{2} L_2 \rightarrow L_1</math>
|<math>\left[ \begin{array}{ccc|c}
1 &
0 & 1 & 0 & 3 \\
0 & 0 & 1 & -1
\end{array} \right]
|-
| colspan="3" |Ο πίνακας είναι τώρα σε ανηγμένη κλιμακωτή μορφή
|}
== Ιστορία ==
Η μέθοδος της απαλοιφής Gauss εμφανίζεται στο Κινέζικο μαθηματικό κείμενο [[Κεφάλαιο Οκτώ ''Ορθογώνιοι'' ''Πίνακες'']] του [[''Τα εννέα κεφάλαια της μαθηματικής τέχνης'']]. Η χρήση του απεικονίζεται σε δεκαοκτώ προβλήματα, με δύο έως πέντε εξισώσεις. Η πρώτη αναφορά στο βιβλίο με αυτόν τον τίτλο κυκλοφόρησε το 179 CE, αλλά τμήματά του ήταν γραμμένα τόσο νωρίς όσο περίπου το 150 Π. χ.<ref>Calinger, Ronald (1999), ''A Contextual History of Mathematics,''[[Prentice Hall]], [[International Standard Book Number|ISBN]] [[Ειδικό:BookSources/978-0-02-318285-3|978-0-02-318285-3]], σελ. 234–236</ref><ref>Timothy Gowers; June Barrow-Green; Imre Leader (8 Σεπτεμβρίου 2008). ''The Princeton Companion to Mathematics''. Princeton University Press. σελ. 607. [[International Standard Book Number|ISBN]] [[Ειδικό:BookSources/978-0-691-11880-2|978-0-691-11880-2]].</ref> Σχολιάστηκε από τον [[Liu Hui]] τον 3ο αιώνα.
Γραμμή 262 ⟶ 325 :
{{Portal bar|Μαθηματικά}}
[[Κατηγορία:Αριθμητική γραμμική άλγεβρα]]
== Εξωτερικοί σύνδεσμοι ==
# [https://www.mathstudies.eu/single-post/2017/10/02/Gauss-elimination Ο αλγόριθμος απαλοιφής του Gauss υλοποιημένος σε γλώσσα python και Matlab].
|