Theoretische Grundlagen

Problem

Untersucht werden soll ein lineares Gleichungssystem mit mehr Gleichungen als Unbekannten, das in folgender Form vorliegt (gegeben sind die Koeffizienten aij auf der linken Seite und die bi auf der rechten Seite, gesucht sind die Unbekannten xj):

Überbestimmtes lineares Gleichungssystem
Rechts ist das System in Matrixschreibweise formuliert mit der gegebenen Koeffizientenmatrix A und dem gegebenen "Vektor der rechten Seite" b. Weil im Regelfall kein Lösungsvektor x existiert, mit dem alle Gleichungen erfüllt werden können, wurde an Stelle des Gleichheitszeichens jeweils das "Ungefähr"-Symbol ≈ verwendet. Es werden bei einer beliebigen Lösung beim Einsetzen in das System im Allgemeinen bei jeder Gleichung ein "Rest" (Fehler) verbleiben:
Nach Einsetzen einer beliebigen Lösung verbleiben Reste
Nach einem Vorschlag von Gauß soll nun diejenige Lösung bestimmt werden, bei der die "Summe der Quadrate der Fehler" minimal wird. Diese vom Lösungsvektor x abhängige Summe wird nachfolgend mit F bezeichnet:
Summe der Quadrate der Fehler soll minimal werden
Dieses Minimum kann nur erreicht werden, wenn alle partiellen Ableitungen von F nach den Komponenten des Lösungsvektors x verschwinden (zur Definition der partiellen Ableitung einer Funktion nach einem Vektor siehe "Transponieren, Invertieren, Differenzieren, ..."):
Notwendige Bedingungen für das Minimum
Zur Vereinfachung der Schreibarbeit wird ab hier nur noch die Vektor-/Matrix-Schreibweise verwendet. Zunächst wird das Skalarprodukt, das die Funktion F definiert, ausmultipliziert (hier findet man die Regel für das Transponieren eines Matrix-Produkts)
Ausmultiplizieren des Vektorprodukts
Nun kann die partielle Ableitung von F nach x gebildet werden (hier findet man die Formeln für die partielle Ableitung eines Vektorprodukts bzw. einer quadratischen Form nach einem Vektor):
Minimalbedingung
Damit ist ein System bekannt, mit dem für das ursprüngliche Gleichungssystem eine Lösung im Sinne der Forderung nach dem Minimum der Fehler-Quadrate gefunden werden kann:
Gaußsche Normalgleichungen
Diese Gleichungen heißen ...

Gaußsche Normalgleichungen:

Für ein überbestimmtes lineares Gleichungssystem mit einer Koeffizientenmatrix A mit m Zeilen und n Spalten (m ≥ n) findet man die Gaußschen Normalgleichungen durch Linksmultiplikation auf beiden Seiten mit der transponierten Koeffizientenmatrix:

Überbestimmtes Gleichungssystem   Gaußsche Normalgleichungen
A x ≈ b AT A x = AT b

Dieses Gleichungssystem hat eine symmetrische Koeffizientenmatrix. Seine Lösung ist die Näherungslösung für das Ausgangssystem im Sinne der Forderung nach dem Minimum der Fehlerquadratsumme.

Beispiel

Für das folgende Gleichungssystem mit 3 Gleichungen und 2 Unbekannten sollen die Gaußschen Normalgleichungen aufgeschrieben und gelöst werden:

Nebenstehend sieht man das Falksche Schema Beispiel für Matrixmultiplikation

, mit dem die Koeffizientenmatrix ATA und die rechte Seite ATb für die Normalgleichungen berechnet werden. Das kleine Gleichungssystem

Gaußsche Normalgleichungen
ist in diesem Fall durchaus noch "von Hand" lösbar (bequemer natürlich interaktiv mit dem Programm "Lineares Gleichungssystem, Matrix-Inversion"). Das Ergebnis

x1 = 0,9505495   ;   x2 = −2,054945

erfüllt keine der drei Gleichungen des überbestimmten Systems exakt, aber alle Gleichungen "bestmöglich". Zu dem Ergebnis kann man allerdings viel einfacher kommen, wenn man das nachfolgend beschriebene Angebot nutzt.

Programm "Überbestimmtes lineares Gleichungssystem" unter TM-interaktiv.de

Das Programm "Überbestimmtes lineares Gleichungssystem" unter TM-interaktiv.de realisiert die Berechnung exakt nach dem oben beschriebenen Algorithmus. Dem Programm kann das überbestimmte Gleichungssystem direkt eingegeben werden, für das gerade behandelte kleine Beispiel sehen Eingabe und Ergebnis so aus:

Lösung mit dem interaktiven Angebot