Main Content

Die Übersetzung dieser Seite ist veraltet. Klicken Sie hier, um die neueste Version auf Englisch zu sehen.

Systeme linearer Gleichungen

Rechnerische Überlegungen

Eines der wichtigsten Probleme bei der technischen Informatik ist die Lösung von Systemen simultaner linearer Gleichungen.

In der Matrixschreibweise sieht das allgemeine Problem wie folgt aus: Gibt es, wenn zwei Matrizen A und b vorliegen, eine eindeutige Matrix x, damit Ax = b oder xA = b?

Aufschluss gibt dabei ein 1x1-Beispiel. Hat beispielsweise die Gleichung

7x = 21

eine eindeutige Lösung?

Die Antwort lautet natürlich ja. Die Gleichung hat die eindeutige Lösung x = 3. Die Lösung lässt sich leicht durch Division ermitteln:

x = 21/7 = 3.

Die Lösung wird nicht einfach durch Berechnen der Inversen von 7, also 7–1 = 0,142857..., und anschließende Multiplikation von 7–1 mal 21 berechnet. Das würde mehr Aufwand bedeuten und wäre auch weniger genau wenn 7–1 für eine finite Anzahl von Ziffern stünde. Ähnliche Bedingungen gelten für Reihen linearer Gleichungen mit mehr als einer Unbekannten. MATLAB® löst solche Gleichungen ohne Berechnung der Inversen der Matrix.

Auch wenn es sich nicht um eine mathematische Standardschreibweise handelt, verwendet MATLAB die vertraute Divisionsterminologie aus dem Skalarfall, um die Lösung eines allgemeinen Systems simultaner Gleichungen zu beschreiben. Die beiden Divisionssymbole, Schrägstrich, /, und umgekehrter Schrägstrich, \, entsprechen den beiden MATLAB Funktionen mrdivide und mldivide. Diese Operatoren werden für die beiden Situationen verwendet, in denen die unbekannte Matrix auf der linken oder rechten Seite der Koeffizientenmatrix angezeigt wird:

x = b/A

Gibt die Lösung für die Matrixgleichung xA = b an, die mithilfe von mrdivide ermittelt wurde.

x = A\b

Gibt die Lösung für die Matrixgleichung Ax = b an, die mithilfe von mldivide ermittelt wurde.

Stellen Sie sich die „Division“ beider Seiten der Gleichung Ax = b oder xA = b durch A vor. Die Koeffizientenmatrix A ist immer im „Nenner“.

Die Dimensionskompatibilitätsbedingungen für x = A\b erfordern, dass die beiden Matrizen A und b dieselbe Anzahl von Zeilen aufweisen. Anschließend weist die Lösung x dieselbe Anzahl von Spalten auf wie b und ihre Zeilendimension entspricht der Spaltendimension von A. Für x = b/A werden die Rollen der Zeilen und Spalten vertauscht.

In der Praxis treten lineare Gleichungen der Form Ax = b häufiger auf als solche der Form xA = b. Daher wird der umgekehrte Schrägstrich wesentlich häufiger verwendet als der Schrägstrich. Im übrigen Teil dieses Abschnitts geht es um den umgekehrten Schrägstrich als Operator. Die entsprechenden Eigenschaften des Schrägstrichs als Operator können von der Identität abgeleitet werden:

(b/A)' = (A'\b').

Die Koeffizientenmatrix A muss nicht quadriert sein. Wenn A die Größe m-mal-n aufweist, gibt es drei Fälle:

m = n

Quadratisches System. Sucht nach einer exakten Lösung.

m > n

Überbestimmtes System mit mehr Gleichungen als Unbekannten. Findet eine Kleinste-Quadrate-Lösung.

m < n

Unterbestimmtes System mit weniger Gleichungen als Unbekannten. Findet eine Basislösung mit höchstens m Komponenten ungleich null.

Der mldivide-Algorithmus

Der Operator mldivide verwendet unterschiedliche Solver für verschiedene Arten von Koeffizientenmatrizen. Die verschiedenen Fälle werden automatisch durch Untersuchen der Koeffizientenmatrix diagnostiziert. Weitere Informationen finden Sie im Abschnitt „Algorithmen“ auf der Referenzseite zu mldivide.

Allgemeine Lösung

Die allgemeine Lösung für ein System linearer Gleichungen, Axb, beschreibt alle möglichen Lösungen. Sie können die allgemeine Lösung wie folgt finden:

  1. Lösen Sie das entsprechende homogene System Ax = 0. Verwenden Sie hierfür den Befehl null, indem Sie null(A) eingeben. Dadurch wird eine Basis für den Lösungsraum an Ax = 0 zurückgegeben. Alle Lösungen sind lineare Kombinationen von Basisvektoren.

  2. Suchen Sie eine bestimmte Lösung für das nicht homogene System Ax = b.

Anschließend können Sie eine beliebige Lösung für Axb als Summe der jeweiligen Lösung für Ax = b, aus Schritt 2, plus eine lineare Kombination der Basisvektoren aus Schritt 1 schreiben.

Im übrigen Teil dieses Abschnitts wird beschrieben, wie Sie MATLAB zum Suchen einer bestimmten Lösung für Ax = b wie in Schritt 2 verwenden.

Quadratische Systeme

Die gängigste Situation umfasst eine quadratische Koeffizientenmatrix A und einen einzelnen Spaltenvektor b auf der rechten Seite.

Nichtsinguläre Koeffizientenmatrix

Wenn die Matrix A nichtsingulär ist, hat die Lösung x = A\b dieselbe Größe wie b. Beispiel:

A = pascal(3);
u = [3; 1; 4];
x = A\u

x =
      10
     -12
       5

Es kann bestätigt werden, dass A*x exakt mit u übereinstimmt.

Wenn A und b quadratisch sind und die gleiche Größe aufweisen, hat x= A\b ebenfalls diese Größe:

b = magic(3);
X = A\b

X =
      19    -3    -1
     -17     4    13
       6     0    -6

Es kann bestätigt werden, dass A*x exakt mit b übereinstimmt.

Beide Beispiele weisen exakte, ganzzahlige Lösungen auf. Dies liegt daran, dass die Koeffizientenmatrix als pascal(3) ausgewählt wurde, was einer Matrix entspricht, die vollen Rang hat (nicht singulär).

Singuläre Koeffizientenmatrix

Eine quadratische Matrix A ist singulär, wenn sie keine linear unabhängigen Spalten aufweist. Wenn A singulär ist, ist die Lösung für Ax = b entweder nicht vorhanden oder nicht eindeutig. Der umgekehrte Schrägstrich als Operator, A\b, gibt eine Warnung aus, wenn A nahezu singulär ist oder wenn eine exakte Singularität erkannt wird.

Wenn A singulär ist und Ax = b eine Lösung hat, können Sie eine bestimmte, nicht eindeutige Lösung finden, indem Sie Folgendes eingeben:

P = pinv(A)*b

pinv(A) ist eine Pseudoinverse von A. Wenn Ax = b keine exakte Lösung aufweist, gibt pinv(A) eine Kleinste-Quadrate-Lösung zurück.

Beispiel:

A = [ 1     3     7
     -1     4     4
      1    10    18 ]

ist singulär, da eine Verifizierung möglich ist durch Eingabe von

rank(A)

ans =

     2

Da A keinen vollen Rang hat, weist sie einige singuläre Werte gleich null auf.

Exakte Lösungen. Für b =[5;2;12] weist die Gleichung Ax = b eine exakte Lösung auf, die wie folgt angegeben wird:

pinv(A)*b

ans =
    0.3850
   -0.1103
    0.7066

Verifizieren Sie, dass pinv(A)*b eine exakte Lösung ist, indem Sie Folgendes eingeben:

A*pinv(A)*b

ans =
    5.0000
    2.0000
   12.0000

Kleinste-Quadrate-Lösungen. Wenn jedoch b = [3;6;0], hat Ax = b keine exakte Lösung. In diesem Fall gibt pinv(A)*b eine Kleinste-Quadrate-Lösung zurück. Wenn Sie

A*pinv(A)*b

ans =
   -1.0000
    4.0000
    2.0000

eingeben, wird nicht der ursprüngliche Vektor b zurückgegeben.

Sie können bestimmen, ob Ax = b eine exakte Lösung aufweist, indem Sie nach der zeilenreduzierten Treppenform der erweiterten Matrix [A b] suchen. Geben Sie dazu für dieses Beispiel Folgendes ein:

rref([A b])
ans =
    1.0000         0    2.2857         0
         0    1.0000    1.5714         0
         0         0         0    1.0000

Da die unterste Zeile ausschließlich Nullen enthält, mit Ausnahme des letzten Eintrags, gibt es für die Gleichung keine Lösung. In diesem Fall gibt pinv(A) eine Kleinste-Quadrate-Lösung zurück.

Überbestimmte Systeme

Dieses Beispiel veranschaulicht, wie überbestimmte Systeme oft in den unterschiedlichsten Arten der Kurvenanpassung für experimentelle Daten vorkommen.

Eine Größe y wird an vielen verschiedenen Werten der Zeit t gemessen und führt zu den folgenden Beobachtungen. Sie können die Daten mithilfe der folgenden Anweisungen eingeben und in einer Tabelle anzeigen.

t = [0 .3 .8 1.1 1.6 2.3]';
y = [.82 .72 .63 .60 .55 .50]';
B = table(t,y)
B=6×2 table
     t      y  
    ___    ____

      0    0.82
    0.3    0.72
    0.8    0.63
    1.1     0.6
    1.6    0.55
    2.3     0.5

Versuchen Sie, die Daten mit einer abklingenden Exponentialfunktion zu modellieren

y(t)=c1+c2e-t.

Die vorherige Gleichung zeigt, dass der Vektor y durch eine lineare Kombination zweier anderer Vektoren approximiert werden sollte. Einer der Vektoren ist ein konstanter Vektor, der nur Einsen enthält, und der andere ist der Vektor mit den Komponenten exp(-t). Die unbekannten Koeffizienten, c1 und c2, können mit der Kleinste-Quadrate-Methode berechnet werden, bei der die Summe der Abweichungsquadrate der Daten aus dem Modell minimiert wird. Es gibt sechs Gleichungen in zwei Unbekannten, die durch eine 6x2-Matrix dargestellt werden.

E = [ones(size(t)) exp(-t)]
E = 6×2

    1.0000    1.0000
    1.0000    0.7408
    1.0000    0.4493
    1.0000    0.3329
    1.0000    0.2019
    1.0000    0.1003

Verwenden Sie den umgekehrten Schrägstrich als Operator, um die Kleinste-Quadrate-Lösung zu erhalten.

c = E\y
c = 2×1

    0.4760
    0.3413

Anders ausgedrückt, lautet die Kleinste-Quadrate-Methode für die Daten wie folgt:

y(t)=0.4760+0.3413e-t.

Die folgenden Anweisungen werten das Modell in Inkrementen mit regelmäßigen Abständen in t aus und plotten anschließend das Ergebnis zusammen mit den ursprünglichen Daten:

T = (0:0.1:2.5)';
Y = [ones(size(T)) exp(-T)]*c;
plot(T,Y,'-',t,y,'o')

Figure contains an axes object. The axes object contains 2 objects of type line. One or more of the lines displays its values using only markers

E*c ist nicht exakt gleich y, doch die Differenz kann durchaus kleiner sein als Messfehler in den ursprünglichen Daten.

Eine rechteckige Matrix A hat einen unzureichenden Rang, wenn sie keine linear unabhängigen Spalten aufweist. Wenn A einen unzureichenden Rang hat, ist die Kleinste-Quadrate-Lösung für AX = B nicht eindeutig. A\B gibt eine Warnung aus, wenn A einen unzureichenden Rang hat, und erstellt eine Kleinste-Quadrate-Lösung. Sie können mithilfe von lsqminnorm die Lösung X finden, die die minimale Norm unter allen Lösungen aufweist.

Unterbestimmte Systeme

Dieses Beispiel veranschaulicht, wie die Lösung für unterbestimmte Systeme nicht eindeutig ist. Unterbestimmte lineare Systeme beinhalten weitaus mehr Unbekannte als Gleichungen. Die linke Divisionsoperation der Matrix in MATLAB findet eine grundlegende Kleinste-Quadrate-Lösung, die höchstens m Komponenten, die nicht null sind, für eine m-mal-n-Koeffizientenmatrix besitzt.

Im Folgenden ist ein kleines, willkürliches Beispiel abgebildet:

R = [6 8 7 3; 3 5 4 1]
rng(0);
b = randi(8,2,1)
R =

       6              8              7              3       
       3              5              4              1       


b =

       7       
       8      

Das lineare System Rp = b besitzt zwei Gleichungen in vier Unbekannten. Da die Koeffizientenmatrix kleine Ganzzahlen enthält, sollte der Befehl format die Lösung im rationalen Format anzeigen. Die jeweilige Lösung wird wie folgt ermittelt:

format rat
p = R\b
p =

       0       
      17/7     
       0       
     -29/7    

Eine der Komponenten, die nicht null sind, ist p(2), da R(:,2) die Spalte von R mit der größten Norm ist. Die andere Komponente, die nicht gleich null ist, ist p(4), da R(:,4) dominiert, nachdem R(:,2) eliminiert wurde.

Die vollständige allgemeine Lösung für das unterbestimmte System kann durch Hinzufügen von p zu einer beliebigen linearen Kombination der Nullraumvektoren charakterisiert werden, die mithilfe der Funktion null und einer Option zum Anfordern einer rationalen Basis gefunden werden kann.

Z = null(R,'r')
Z =

      -1/2           -7/6     
      -1/2            1/2     
       1              0       
       0              1       

Es kann bestätigt werden, dass R*Z null ist und dass das Residuum R*x - b für einen beliebigen Vektor x klein ist, wobei Folgendes gilt:

x = p + Z*q

Da die Spalten von Z die Nullraumvektoren sind, ist das Produkt Z*q eine lineare Kombination aus den folgenden Vektoren:

Zq=(x1x2)(uw)=ux1+wx2.

Wählen Sie zur Veranschaulichung eine beliebige Komponente q aus und konstruieren Sie x.

q = [-2; 1];
x = p + Z*q;

Berechnen Sie die Norm des Residuums.

format short
norm(R*x - b)
ans =

   2.6645e-15

Wenn unendlich viele Lösungen verfügbar sind, ist die Lösung mit der minimalen Norm von besonderem Interesse. Sie können lsqminnorm zum Berechnen der Kleinste-Quadrate-Lösung mit der minimalen Norm verwenden. Diese Lösung weist den kleinstmöglichen Wert für norm(p) auf.

p = lsqminnorm(R,b)
p =

    -207/137   
     365/137   
      79/137   
    -424/137  

Lösungen für verschiedene rechte Seiten

Einige Probleme betreffen die Lösung linearer Systeme, die dieselbe Koeffizientenmatrix A, doch unterschiedliche rechte Seiten b aufweisen. Wenn die verschiedenen Werte von b gleichzeitig verfügbar sind, können Sie b als Matrix mit mehreren Spalten konstruieren und alle Gleichungssysteme gleichzeitig mithilfe eines einzelnen Befehls mit umgekehrtem Schrägstrich lösen: X = A\[b1 b2 b3 …].

Manchmal sind jedoch die verschiedenen Werte von b nicht alle gleichzeitig verfügbar, sodass Sie verschiedene Gleichungssysteme nacheinander lösen müssen. Wenn Sie eines dieser Gleichungssysteme mit Schrägstrich (/) oder umgekehrtem Schrägstrich (\) lösen, faktorisiert der Operator die Koeffizientenmatrix A und verwendet diese Matrixzerlegung, um die Lösung zu berechnen. Allerdings berechnet der Operator jedes Mal, wenn Sie ein ähnliches Gleichungssystem mit einem anderen Wert von b lösen, dieselbe Zerlegung von A, bei der es sich um eine redundante Berechnung handelt.

Dieses Problem kann behoben werden, indem die Zerlegung von A vorab berechnet wird und anschließend die zu lösenden Faktoren für die verschiedenen Werte von b wiederverwendet werden. In der Praxis kann jedoch die Vorabberechnung der Zerlegung auf diese Weise schwierig sein, da Sie wissen müssen, welche Zerlegung zu berechnen ist (LU, LDL, Cholesky usw.) und wie Sie die Faktoren zum Lösen des Problems multiplizieren. Mit der LU-Zerlegung müssen Sie zwei lineare Systeme lösen, um das ursprüngliche System Ax = b zu lösen:

[L,U] = lu(A);
x = U \ (L \ b);

Stattdessen wird zum Lösen linearer Systeme mit verschiedenen aufeinanderfolgenden rechten Seiten die Verwendung von Zerlegungsobjekten (decomposition) empfohlen. Mit diesen Objekten können die Leistungsvorteile einer Vorabberechnung der Matrixzerlegung genutzt werden, doch es ist kein Wissen über die Verwendung der Matrixfaktoren erforderlich. Sie können die vorherige LU-Zerlegung wie folgt ersetzen:

dA = decomposition(A,'lu');
x = dA\b;

Wenn Sie nicht sicher sind, welche Zerlegung verwendet werden soll, wählt decomposition(A) den richtigen Typ basierend auf den Eigenschaften von A aus, ähnlich wie der umgekehrte Schrägstrich.

Hier ist ein einfacher Test der möglichen Leistungsvorteile dieses Ansatzes. Der Test löst dasselbe dünn besetzte lineare System 100 Mal mithilfe des umgekehrten Schrägstrichs (\) und decomposition.

n = 1e3;
A = sprand(n,n,0.2) + speye(n);
b = ones(n,1);

% Backslash solution
tic
for k = 1:100
    x = A\b;
end
toc
Elapsed time is 9.006156 seconds.
% decomposition solution
tic
dA = decomposition(A);
for k = 1:100
    x = dA\b;
end
toc
Elapsed time is 0.374347 seconds.

Bei diesem Problem ist die decomposition-Lösung wesentlich schneller als die alleinige Verwendung des umgekehrten Schrägstrichs – und doch bleibt die Syntax einfach.

Iterative Methoden

Wenn die Koeffizientenmatrix A groß und dünn besetzt ist, sind Faktorisierungsmethoden im Allgemeinen nicht effizient. Iterative Methoden generieren eine Reihe von Approximationslösungen. MATLAB stellt verschiedene iterative Methoden zur Handhabung großer, dünn besetzter Eingabematrizen zur Verfügung.

FunktionBeschreibung
pcg

Methode der vorausgesetzten konjugierten Gradienten. Diese Methode eignet sich für die hermitesche positiv definite Koeffizientenmatrix A.

bicg

Methode bikonjugierter Gradienten

bicgstab

Stabilisierte Methode bikonjugierter Gradienten

bicgstabl

BiCGStab(l)-Methode

cgs

Quadrierte Methode konjugierter Gradienten

gmres

Methode generalisierter minimaler Residuen

lsqr

LSQR-Methode

minres

Methode minimaler Residuen. Diese Methode eignet sich für die hermitesche Koeffizientenmatrix A.

qmr

Methode quasi-minimaler Residuen

symmlq

Symmetrische LQ-Methode

tfqmr

Transponiertenfreie QMR-Methode

Multithread-Berechnung

MATLAB unterstützt Multithread-Berechnung für zahlreiche numerische Funktionen der linearen Algebra und elementweiser numerischer Funktionen. Diese Funktionen werden automatisch für mehrere Threads ausgeführt. Damit eine Funktion oder ein Ausdruck schneller auf mehreren CPUs ausgeführt wird, müssen verschiedene Bedingungen erfüllt sein:

  1. Die Funktion führt Operationen aus, die sich leicht in gleichzeitig ausführbare Abschnitte unterteilen lassen. Diese Abschnitte müssen in der Lage sein, mit möglichst wenig Kommunikation zwischen Prozessen ausgeführt zu werden. Sie sollten nur wenige aufeinanderfolgende Operationen erfordern.

  2. Die Datengröße muss so bemessen sein, dass alle Vorteile einer gleichzeitigen Ausführung die Zeit aufwiegen, die zum Unterteilen der Daten und zum Verwalten separater Ausführungsthreads erforderlich ist. So ist eine Beschleunigung der meisten Funktionen beispielsweise nur erforderlich, wenn das Array mehrere tausend Elemente oder mehr enthält.

  3. Die Rechenoperation ist nicht speichergebunden und die Verarbeitungszeit wird nicht von der Speicherzugriffszeit beeinträchtigt. Im Allgemeinen gilt, dass komplizierte Funktionen eher beschleunigt werden als einfache Funktionen.

inv, lscov, linsolve und mldivide sind bei großen Arrays mit doppelter Präzision (in der Größenordnung von 10.000 Elementen oder mehr) erheblich schneller, wenn Multithreading aktiviert ist.

Siehe auch

| | | |

Verwandte Themen

Externe Websites