In der geradlinigen Algebra ist Beseitigung von Gaussian ein Algorithmus, um Systeme von geradlinigen Gleichungen zu lösen. Es kann auch verwendet werden, um die Reihe einer Matrix zu finden, die Determinante einer Matrix zu berechnen, und das Gegenteil einer invertible Quadratmatrix zu berechnen. Die Methode wird nach Carl Friedrich Gauss genannt, aber sie wurde von ihm nicht erfunden.

Elementare Reihe-Operationen werden verwendet, um eine Matrix darauf zu reduzieren, was Dreiecksform (in der numerischen Analyse) oder Reihe-Staffelstellungsform (in der abstrakten Algebra) genannt wird. Beseitigung von Gauss-Jordan, eine Erweiterung dieses Algorithmus, reduziert die Matrix weiter auf die diagonale Form, die auch bekannt als reduzierte Reihe-Staffelstellungsform ist. Beseitigung von Gaussian allein ist für viele Anwendungen genügend, und verlangt weniger Berechnungen als die Version von Gauss-Jordan.

Geschichte

Die Methode der Beseitigung von Gaussian erscheint im Kapitel Acht, Rechteckige Reihe, vom wichtigen chinesischen mathematischen Text Jiuzhang suanshu oder Die Neun Kapitel über die Mathematische Kunst. Sein Gebrauch wird in achtzehn Problemen mit zwei bis fünf Gleichungen illustriert. Auf die erste Verweisung auf das Buch durch diesen Titel wird zu 179 CE datiert, aber Teile davon wurden schon in etwa 150 BCE geschrieben. Darüber wurde von Liu Hui im 3. Jahrhundert geäußert.

Die Methode in Europa stammt von den Zeichen von Isaac Newton. 1670 hat er geschrieben, dass die ganze Algebra bekannt ihm vorbestellt, hat an einer Lehre Mangel gehabt, um gleichzeitige Gleichungen zu lösen, die Newton dann geliefert hat. Universität von Cambridge hat schließlich die Zeichen als Arithmetica Universalis 1707 veröffentlicht, lange nachdem Newton akademisches Leben verlassen hat. Die Zeichen wurden weit imitiert, der gemacht hat (was jetzt genannt wird) Beseitigung von Gaussian eine Standardlehre in Algebra-Lehrbüchern am Ende des 18. Jahrhunderts. Carl Friedrich Gauss 1810 hat eine Notation für die symmetrische Beseitigung ausgedacht, die im 19. Jahrhundert durch Berufshandcomputer angenommen wurde, um die normalen Gleichungen von Am-Wenigsten-Quadratproblemen zu lösen. Der Algorithmus, der in der Höheren Schule unterrichtet wird, wurde für Gauss nur in den 1950er Jahren infolge der Verwirrung über die Geschichte des Themas genannt.

Algorithmus-Übersicht

Der Prozess der Beseitigung von Gaussian hat zwei Teile. Der erste Teil (Vorwärtsbeseitigung) reduziert ein gegebenes System entweder auf die Dreiecksform oder auf Staffelstellungsform, oder läuft auf eine degenerierte Gleichung hinaus, anzeigend, dass das System keine einzigartige Lösung hat, aber vielfache Lösungen haben kann (Reihe

2x && \; + \;&& y && \; - \;&& z && \; = \;&& 8 & \qquad (L_1) \\

- 3x && \; - \;&& y && \; + \;&& 2z && \; = \;&&-11 & \qquad (L_2) \\

- 2x && \; + \;&& y && \; + \;&& 2z && \; = \;&&-3 & \qquad (L_3)

\end {alignat} </Mathematik>

Der Algorithmus ist wie folgt: Beseitigen Sie x von allen Gleichungen unten, und dann beseitigen Sie y von allen Gleichungen unten. Das wird das System in die Dreiecksform stellen. Dann, mit dem Rückwartseinsetzen, kann jeder unbekannt dafür gelöst werden.

Im Beispiel wird x von durch das Hinzufügen dazu beseitigt. x wird dann von durch das Hinzufügen dazu beseitigt. Formell:

::

Das Ergebnis ist:

:

2x && \; + && y && \; - && \; z && \; = \;&& 8 & \\

&& && \frac {1} {2} y && \; + && \; \frac {1} {2} z && \; = \;&& 1 & \\

&& && 2y && \; + && \; z && \; = \;&& 5 &

\end {alignat} </Mathematik>

Jetzt wird y von durch das Hinzufügen beseitigt zu:

:Das Ergebnis ist::

2x && \; + && y \;&& - && \; z \;&& = \;&& 8 & \\

&& && \frac {1} {2} y \;&& + && \; \frac {1} {2} z \;&& = \;&& 1 & \\

&& && && && \;-z \;&& \; = \;&& 1 &

\end {alignat} </Mathematik>

Dieses Ergebnis ist ein System von geradlinigen Gleichungen in der Dreiecksform, und so ist der erste Teil des Algorithmus abgeschlossen.

Der letzte Teil, Rückwartseinsetzen, besteht aus dem Lösen für den knowns in umgekehrter Reihenfolge. Es kann so das gesehen werden

:

Dann, kann darin eingesetzt werden, der dann gelöst werden kann, um zu erhalten

:

Dann kann z und y darin eingesetzt werden, der gelöst werden kann, um zu erhalten

:

Das System wird gelöst.

Einige Systeme können auf die Dreiecksform nicht reduziert werden, doch mindestens eine gültige Lösung haben: Zum Beispiel, wenn y in nicht vorgekommen war, und nachdem der erste Schritt oben, der Algorithmus unfähig gewesen wäre, das System auf die Dreiecksform zu reduzieren. Jedoch hätte es noch das System auf die Staffelstellungsform reduziert. In diesem Fall hat das System keine einzigartige Lösung, weil es mindestens eine freie Variable enthält. Der Lösungssatz kann dann parametrisch ausgedrückt werden (d. h. in Bezug auf die freien Variablen, so dass, wenn Werte für die freien Variablen gewählt werden, eine Lösung erzeugt wird).

In der Praxis befasst man sich mit den Systemen in Bezug auf Gleichungen nicht gewöhnlich, aber macht stattdessen von der vermehrten Matrix Gebrauch (der auch für Computermanipulationen passend ist). Zum Beispiel:

:2x && \; + \;&& y && \; - \;&& z && \; = \;&& 8 & \qquad (L_1) \\- 3x && \; - \;&& y && \; + \;&& 2z && \; = \;&&-11 & \qquad (L_2) \\- 2x && \; + \;&& y && \; + \;&& 2z && \; = \;&&-3 & \qquad (L_3)\end {alignat} </Mathematik>

Deshalb beginnt der Gaussian auf die vermehrte Matrix angewandte Beseitigungsalgorithmus mit:

:

\left [\begin {Reihe} {ccc|c }\

2 & 1 &-1 & 8 \\

- 3 &-1 & 2 &-11 \\

- 2 & 1 & 2 &-3

\end {Reihe} \right]

</Mathematik>

der, am Ende des ersten Teils (Beseitigung von Gaussian, Nullen nur unter der Führung 1) des Algorithmus, sieht wie das aus:

:\left [\begin {Reihe} {ccc|c }\

1 & \frac {1} {3} & \frac {-2} {3} & \frac {11} {3} \\

0 & 1 & \frac {2} {5} & \frac {13} {5} \\

0 & 0 & 1 &-1

\end {Reihe} \right]</Mathematik>

D. h. es ist in der Reihe-Staffelstellungsform.

Am Ende des Algorithmus, wenn die Beseitigung von Gauss-Jordan (Nullen unter und über der Führung 1) angewandt wird:

:\left [\begin {Reihe} {ccc|c }\

1 & 0 & 0 & 2 \\

0 & 1 & 0 & 3 \\

0 & 0 & 1 &-1\end {Reihe} \right]</Mathematik>

D. h. es ist in der reduzierten Reihe-Staffelstellungsform oder Reihe kanonische Form.

Andere Anwendungen

Die Entdeckung des Gegenteils einer Matrix

Nehmen Sie an, dass A ein n durch die n Matrix von Invertible ist. Dann kann das Gegenteil von A wie folgt gefunden werden. Der n durch die n Identitätsmatrix wird rechts von A vermehrt, einen n durch 2n Matrix (die Block-Matrix B = [A, ich]) bildend. Durch die Anwendung elementarer Reihe-Operationen und des Beseitigungsalgorithmus von Gaussian kann der linke Block von B auf die Identitätsmatrix I reduziert werden, der im richtigen Block von B abreist. Bemerken Sie, dass das die Beseitigung von Gauss-Jordan ist, um Gegenteile zu finden.

Wenn der Algorithmus unfähig ist, zur Dreiecksform abzunehmen, dann ist A nicht invertible.

Allgemeiner Algorithmus, um Reihen und Basen zu schätzen

Der Gaussian Beseitigungsalgorithmus kann auf jede Matrix angewandt werden. Wenn wir in einer gegebenen Säule "durchstochen" werden, bewegen wir uns zur folgenden Säule. Auf diese Weise, zum Beispiel, kann ein matrices in eine Matrix umgestaltet werden, die eine reduzierte Reihe-Staffelstellungsform wie hat

:

\begin {bmatrix }\

1 & * & 0 & 0 & * & * & 0 & * & 0 \\

0 & 0 & 1 & 0 & * & * & 0 & * & 0 \\

0 & 0 & 0 & 1 & * & * & 0 & * & 0 \\

0 & 0 & 0 & 0 & 0 & 0 & 1 & * & 0 \\

0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\

0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0

\end {bmatrix }\

</Mathematik>

(die *'s sind willkürliche Einträge). Diese Staffelstellungsmatrix enthält einen Reichtum der Information über: Die Reihe dessen ist 5, da es 5 Nichtnullreihen darin gibt; der Vektorraum, der durch die Säulen dessen abgemessen ist, hat eine Basis, die aus der ersten, dritten, vierten, siebenten und neunten Säule (die Säulen von denjenigen in) besteht, und die *'s erzählen Ihnen, wie die anderen Säulen dessen als geradlinige Kombinationen der Basissäulen geschrieben werden können.

Analyse

Beseitigung von Gaussian, um ein System von n Gleichungen für n unknowns zu lösen, verlangt n (n+1) / 2 Abteilungen, (2n + 3n  5n)/6 Multiplikationen, und (2n + 3n  5n)/6 Subtraktionen, für insgesamt ungefähr 2n / 3 Operationen. So hat es arithmetische Kompliziertheit von O (n). Jedoch können die Zwischeneinträge exponential groß wachsen, so hat es Exponentialbit-Kompliziertheit.

Dieser Algorithmus kann auf einem Computer für Systeme mit Tausenden von Gleichungen und unknowns verwendet werden. Jedoch werden die Kosten untersagend für Systeme mit Millionen von Gleichungen. Diese großen Systeme werden allgemein mit wiederholenden Methoden gelöst. Spezifische Methoden bestehen für Systeme, deren Koeffizienten einem regelmäßigen Muster folgen (sieh System von geradlinigen Gleichungen).

Die Gaussian Beseitigung kann über jedes Feld durchgeführt werden.

Beseitigung von Gaussian ist für diagonal dominierenden oder positiv-bestimmten matrices numerisch stabil. Für allgemeinen matrices, wie man gewöhnlich betrachtet, ist Beseitigung von Gaussian in der Praxis stabil, wenn Sie das teilweise Drehen, wie beschrieben, unten verwenden, wenn auch es Beispiele gibt, für die es nicht stabil ist.

Höherer Ordnungstensor

Beseitigung von Gaussian verallgemeinert auf keine einfache Weise zum höheren Ordnungstensor (matrices sind Tensor des Auftrags 2); sogar die Computerwissenschaft der Reihe eines Tensor der Ordnung, die größer ist als 2, ist ein schwieriges Problem.

Pseudocode

Wie erklärt, oben schreibt Beseitigung von Gaussian eine gegebene M &times; n Matrix einzigartig als ein Produkt einer invertible M &times; M Matrix S und eine Matrix der Reihe-Staffelstellung T. Hier ist S das Produkt des matrices entsprechend den durchgeführten Reihe-Operationen.

Der formelle Algorithmus, um davon zu rechnen, folgt. Wir schreiben für den Zugang in der Reihe, die Säule in der Matrix mit 1, der erste Index seiend. Die Transformation wird "im Platz" durchgeführt, bedeutend, dass die ursprüngliche Matrix verloren und nacheinander dadurch ersetzt wird.

für k = 1... M:

Finden Sie Türangel für die Spalte k:

i_max: = argmax (ich = k... M, abs ([ich, k]))

wenn [i_max, k] = 0

Fehler "Matrix ist einzigartig!"

Tausch-Reihen (k, i_max)

Tun Sie für alle Reihen unter der Türangel:

weil ich = k + 1... M:

Tun Sie für alle restlichen Elemente in der aktuellen Reihe:

für j = k + 1... n:

[Ich, j]: = [ich, j] - [k, j] * ([ich, k] / [k, k])

Füllen Sie niedrigere Dreiecksmatrix mit Nullen:

[Ich, k]: = 0

</Code>

Dieser Algorithmus unterscheidet sich ein bisschen von demjenigen besprochen früher, weil vor dem Beseitigen einer Variable es zuerst Reihen austauscht, um den Zugang mit dem größten absoluten Wert zur "Türangel-Position" zu bewegen. Solches "teilweises Drehen" verbessert die numerische Stabilität des Algorithmus; einige Varianten sind auch im Gebrauch.

Nach der Vollziehung dieses Verfahrens wird die vermehrte Matrix in der Form der Reihe-Staffelstellung sein und kann durch das Rückwartseinsetzen gelöst werden.

Mit der zunehmenden Beliebtheit von Mehrkernverarbeitern nutzen Programmierer jetzt Parallele-Beseitigungsalgorithmen von Gaussian des Faden-Niveaus aus, um die Geschwindigkeit der Computerwissenschaft zu vergrößern. Das Programmiermodell des geteilten Gedächtnisses (im Vergleich mit dem Nachrichtenaustauschmodell) Pseudocode wird unten verzeichnet.

//Bemerken Sie, dass diese Codeprobe zerfleischt worden ist (attr init/scope fehlend? schlechter gauss Einrückung?)...

//Was ist ursprüngliche Quelle? Können wir gültigen C oder vereinfachter Pseudocode statt dieser Hybride bekommen?

leere Parallele (interne Nummer num_threads, interne Nummer matrix_dimension)

{\

interne Nummer i;

für (i=0; ich

mybarrier-> cur_count ++;

wenn (mybarrier-> cur_count! =num_thread)

pthread_cond_wait (& (mybarrier-> barrier_cond) ,& (mybarrier-> barrier_mutex));

sonst

{\

mybarrier-> cur_count=0;

pthread_cond_broadcast (& (mybarrier-> barrier_cond));

}\

pthread_mutex_unlock (& (mybarrier-> barrier_mutex));

}\

</syntaxhighlight>

Siehe auch

• LU Zergliederung kann als eine Matrixform der Beseitigung von Gaussian angesehen werden
• Frontaler solver, eine Verbesserung der Beseitigung von Gaussian für den Fall von spärlichen Systemen
• Beseitigung von Gauss-Jordan, ein Verfahren, das weiter die mitwirkende Matrix auf den Punkt reduziert, wo Rückwartseinsetzen nicht mehr notwendiger ist
• Der Algorithmus von Grassmann ist eine numerisch stabile Variante der Beseitigung von Gaussian für Systeme über die reellen Zahlen oder komplexen Zahlen. Der Algorithmus vermeidet, dass Subtraktionen so zu durch die Subtraktion von zwei grob gleichen Anzahlen verursachten Fehlern weniger empfindlich sind.

Zeichen

. . . . . . .

• Kapitel 5 befasst sich mit Beseitigung von Gaussian.

.

Links

• WebApp, beschreibend Systeme von geradlinigen Gleichungen mit der Gaussian Beseitigung lösend
• Ein Programm, das Beseitigung von Gaussian ähnlich für einen Menschen durchführt, der an Papier Genaue Lösungen von Systemen mit vernünftigen Koeffizienten arbeitet.
• Beseitigung von Gaussian www.math-linux.com.
• Beseitigung von Gaussian als Java applet an einer lokalen Seite. Nur nimmt natürliche Koeffizienten.
• Beseitigung von Gaussian am Holistischen Numerischen Methode-Institut
• LinearEquations.c Gaussian Beseitigung hat das Verwenden der c Sprache durchgeführt
• Beseitigung von Gauss-Jordan Nach und nach Lösung von 3 Gleichungen mit 3 unknowns das Verwenden der Staffelstellungsmethode der Vollganzen Zahl

• stellt eine sehr klare, elementare Präsentation der Methode der Reihe-Verminderung zur Verfügung.