vollständige Pivotisierung innerhalb des Gaussschen Eliminationsverfahrens

stekuntze

Hallo!

Ich nutze das Gausssche Eliminationsverfahren mit vollständiger Pivotisierung, um homogene lineare Gleichungssysteme in eine Stufenform zu überführen. Dabei stelle ich den Rang fest und für den Fall unterbestimmtes GS bestimme ich Lösungen, indem ich einzelne Unbekannte vorgebe.

Ich nutze die vollständige Pivotisierung, um Rundungsfehler klein zu halten.
Neben dieser Motivation habe ich mir folgende Frage gestellt:

Wird die vollständige Pivotisierung nur benötigt, um einen vorzeitigen Programmabbruch zu vermeiden, wenn ein oder mehrere Spaltenvektoren der Matrix Vielfache eines anderen Spaltenvektors sind?

Beispiel (mit Pivotsuche nur in der Spalte - z Bsp erstes element ungleich Null)

1 2 3
1 2 6
1 2 -1

erster eliminationsschritt:

1 2 3
0 0 3
0 0 -4

zweiter eliminationsschritt:

kein element ungleich Null - weder a_22 noch a_32

Ist das der einzige Fall, der eine vollständige Pivotisierung im Sinne des Algorithmus unabdingbar macht?

Wie gesagt, lineare Abhängigkeiten in den Zeilen und Spalten kann ich für die Eingangsmatrizen nicht ausschließen und auch nicht den beschriebenen Fall, dass die Spalten Vielfache voneinander sind.

Grüße,
Stefan

krümelkacker

Ein homogenes Gleichungssystem ist von der Gestalt A*x=0.
Eine nichttriviale Lösung kannst Du hier am besten über eine Singulärwertzerlegung bestimmen. Die muss nicht mal vollständig sein. Interessant sind nur die Singulärwerte und die Rechts-Singulärvektoren.

A x = 0    (SVD: A = U S V^T
<=>   U S V^T x = 0    | U^*
<=>     S V^T x = 0

S ist eine Diagonalmatrix mit nightnegativen absteigenden Einträgen. Ist der letzte Singulärwert 0, dann ist hat A keinen vollen Rang und die dazugehörige letzte Spalte von V ist eine nichttriveale Lösung für x. Falls A singulär sein müsste, es aber aufgrund von Messfehlern nicht ist, entspricht die letzte Spalte in V einer Lösung im Sinne der kleinsten Fehlerquadrate unter der Einschränkung, dass die Norm der Lösung 1 sein soll.

Eine SVD zu berechnen ist aufwändiger. Mag sein, dass das mit anderen Mitteln noch einfacher geht. Aber dafür gibt es ja fertige Routinen und so macht man am wenigsten falsch.