Main Content

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

Faktorisierungen

Einführung

Alle drei in diesem Abschnitt erläuterten Matrixfaktorisierungen verwenden Dreiecksmatrizen, bei denen alle Elemente entweder über oder unter der Diagonalen null sind. Systeme linearer Gleichungen, die Dreiecksmatrizen enthalten, werden mithilfe der Vorwärts- oder Rückwärtssubstitution schnell und einfach gelöst.

Cholesky-Faktorisierung

Die Cholesky-Faktorisierung drückt eine symmetrische Matrix als Produkt einer Dreiecksmatrix und ihrer Transponierten aus

A = RR,

wobei R eine obere Dreiecksmatrix ist.

Nicht alle symmetrischen Matrizen können auf diese Weise faktorisiert werden. Die Matrizen mit einer solchen Faktorisierung gelten als positiv definit. Dies impliziert, dass alle Diagonalelemente von A positiv sind und dass die Elemente, die nicht auf der Diagonalen liegen, „nicht zu groß“ sind. Die Pascal-Matrizen sind ein interessantes Beispiel. In diesem Kapitel war die Beispielmatrix A die 3-mal-3-Pascal-Matrix. Stellen Sie vorübergehend auf 6-mal-6 um:

A = pascal(6)

A =
       1     1     1     1     1     1
       1     2     3     4     5     6
       1     3     6    10    15    21
       1     4    10    20    35    56
       1     5    15    35    70   126
       1     6    21    56   126   252

Die Elemente von A sind Binomialkoeffizienten. Jedes Element ist die Summe seiner nördlichen und westlichen Nachbarn. Die Cholesky-Faktorisierung sieht wie folgt aus:

R = chol(A)

R =
     1     1     1     1     1     1
     0     1     2     3     4     5
     0     0     1     3     6    10
     0     0     0     1     4    10
     0     0     0     0     1     5
     0     0     0     0     0     1

Die Elemente sind auch hier Binomialkoeffizienten. Die Tatsache, dass R'*R gleich A ist, weist auf eine Identität hin, die Summen von Produkten der Binomialkoeffizienten umfasst.

Hinweis

Die Cholesky-Faktorisierung gilt auch für komplexe Matrizen. Alle komplexen Matrizen, die eine Cholesky-Faktorisierung aufweisen, erfüllen

A′ = A

und gelten als hermitesch positiv definit.

Die Cholesky-Faktorisierung erlaubt die Ersetzung des linearen Systems

Ax = b

durch

RRx = b.

Da der umgekehrte Schrägstrich als Operator Dreiecksysteme erkennt, kann dies in der MATLAB® Umgebung schnell wie folgt gelöst werden:

x = R\(R'\b)

Wenn A gleich n-mal-n ist, ist die rechnerische Komplexität von chol(A) gleich O(n3), doch die Komplexität der nachfolgenden Lösungen mit umgekehrtem Schrägstrich ist nur O(n2).

LU-Faktorisierung

Die LU-Faktorisierung, oder das Gaußsche Eliminationsverfahren, drückt eine beliebige quadratische Matrix A als Produkt der Permutation einer unteren Dreiecksmatrix und einer oberen Dreiecksmatrix aus,

A = LU,

wobei L eine Permutation der unteren Dreiecksmatrix mit Einsen entlang der Diagonalen und U eine obere Dreiecksmatrix ist.

Die Permutationen sind aus theoretischen und rechnerischen Gründen erforderlich. Die Matrix

[0110]

kann nicht als Produkt von Dreiecksmatrizen ausgedrückt werden, wenn nicht die beiden Zeilen vertauscht werden. Auch wenn die Matrix

[ε110]

als Produkt der Dreiecksmatrizen ausgedrückt werden kann, wenn ε klein ist, sind die Elemente in den Faktoren groß und vergrößern Fehler, sodass die Permutationen zwar nicht unbedingt erforderlich, doch wünschenswert sind. Durch teilweise Pivotisierung kann sichergestellt werden, dass die Größe der Elemente von L durch 1 begrenzt ist und dass die Elemente von U nicht wesentlich größer sind als die von A.

Beispiel:

[L,U] = lu(B)

L =
    1.0000         0         0
    0.3750    0.5441    1.0000
    0.5000    1.0000         0

U =
    8.0000    1.0000    6.0000
         0    8.5000   -1.0000
         0         0    5.2941

Durch die LU-Faktorisierung von A kann das lineare System

A*x = b

wie folgt schnell gelöst werden:

x = U\(L\b)

Determinanten und Inverse lassen sich mit der LU-Faktorisierung wie folgt berechnen:

det(A) = det(L)*det(U)

und

inv(A) = inv(U)*inv(L)

Sie können die Determinanten auch mithilfe von det(A) = prod(diag(U)) berechnen, wobei jedoch die Vorzeichen der Determinanten umgekehrt sein können.

QR-Faktorisierungen

Eine orthogonale Matrix, oder eine Matrix mit orthonormalen Spalten, ist eine reelle Matrix, deren Spalten alle eine Einheitenlänge aufweisen und senkrecht zueinander sind. Wenn Q orthogonal ist, dann gilt Folgendes:

QTQ = I,

wobei I die Identitätsmatrix ist.

Die einfachsten orthogonalen Matrizen sind zweidimensionale Koordinatendrehungen:

[cos(θ)sin(θ)sin(θ)cos(θ)].

Für komplexe Matrizen lautet der entsprechende Begriff unitär. Orthogonale und unitäre Matrizen sind für die numerische Berechnung wünschenswert, da sie Länge und Winkel beibehalten und Fehler nicht vergrößern.

Die orthogonale Faktorisierung, oder QR-Faktorisierung, drückt eine beliebige rechteckige Matrix als Produkt einer orthogonalen oder unitären Matrix und einer oberen Dreiecksmatrix aus. Eine Spaltenpermutation kann ebenfalls beteiligt sein:

A = QR

oder

AP = QR,

wobei Q die orthogonale oder unitäre Matrix, R die obere Dreiecksmatrix und P eine Permutation ist.

Es gibt vier Varianten der QR-Faktorisierung – vollständig oder reduziert sowie mit und ohne Spaltenpermutation.

Überbestimmte lineare Systeme umfassen eine rechteckige Matrix mit mehr Zeilen als Spalten, also m-mal-n mit m > n. Bei der vollständigen QR-Faktorisierung ergibt sich eine quadratische, orthogonale m-mal-m-Q-Matrix und eine rechteckige, obere m-mal-n-R-Dreiecksmatrix:

C=gallery('uniformdata',[5 4], 0);
[Q,R] = qr(C)

Q =

    0.6191    0.1406   -0.1899   -0.5058    0.5522
    0.1506    0.4084    0.5034    0.5974    0.4475
    0.3954   -0.5564    0.6869   -0.1478   -0.2008
    0.3167    0.6676    0.1351   -0.1729   -0.6370
    0.5808   -0.2410   -0.4695    0.5792   -0.2207


R =

    1.5346    1.0663    1.2010    1.4036
         0    0.7245    0.3474   -0.0126
         0         0    0.9320    0.6596
         0         0         0    0.6648
         0         0         0         0

In vielen Fällen sind die letzten m – n-Spalten von Q nicht erforderlich, da sie mit den Nullen im unteren Teil von R multipliziert werden. Bei der reduzierten QR-Faktorisierung entsteht eine rechteckige m-mal-n-Q-Matrix mit orthonormalen Spalten und eine quadratische, obere n-mal-n-R-Dreiecksmatrix. Für das 5x4-Beispiel stellt dies keine besondere Einsparung dar, doch für größere, stark rechteckige Matrizen können die Einsparungen hinsichtlich Zeit und Speicher tatsächlich von Bedeutung sein:

[Q,R] = qr(C,0)	
Q =

    0.6191    0.1406   -0.1899   -0.5058
    0.1506    0.4084    0.5034    0.5974
    0.3954   -0.5564    0.6869   -0.1478
    0.3167    0.6676    0.1351   -0.1729
    0.5808   -0.2410   -0.4695    0.5792


R =

    1.5346    1.0663    1.2010    1.4036
         0    0.7245    0.3474   -0.0126
         0         0    0.9320    0.6596
         0         0         0    0.6648

Im Gegensatz zur LU-Faktorisierung sind für die QR-Faktorisierung weder Pivotisierung noch Permutationen erforderlich. Doch eine optionale Spaltenpermutation, die durch die Präsenz eines dritten Ausgabearguments ausgelöst wird, ist hilfreich, um Singularität oder einen nicht ausreichenden Rang zu erkennen. Bei jedem Schritt der Faktorisierung wird die Spalte der verbleibenden, nicht faktorisierten Matrix mit der größten Norm als Basis für den jeweiligen Schritt verwendet. So ist sichergestellt, dass die Diagonalelemente von R in absteigender Reihenfolge auftreten und eine lineare Abhängigkeit entlang der Spalten nahezu sicher bei der Überprüfung dieser Elemente erkannt wird. Im folgenden kleinen Beispiel weist die zweite Spalte von C eine größere Norm auf als die erste, sodass die beiden Spalten vertauscht werden:

[Q,R,P] = qr(C)

Q =
   -0.3522    0.8398   -0.4131
   -0.7044   -0.5285   -0.4739
   -0.6163    0.1241    0.7777

R =
  -11.3578   -8.2762
         0    7.2460
         0         0

P =
     0     1
     1     0

Wenn die reduzierte und die Spaltenpermutationen kombiniert werden, ist das dritte Ausgabeargument ein Permutationsvektor und keine Permutationsmatrix:

[Q,R,p] = qr(C,0)

Q =
   -0.3522    0.8398
   -0.7044   -0.5285
   -0.6163    0.1241

R =
  -11.3578   -8.2762
         0    7.2460


p =
     2     1

Die QR-Faktorisierung transformiert ein überbestimmtes lineares System in ein äquivalentes Dreieckssystem. Der Ausdruck

norm(A*x - b)

ist gleich

norm(Q*R*x - b)

Durch Multiplikation mit orthogonalen Matrizen bleibt die euklidische Norm beibehalten, sodass dieser Ausdruck gleich

norm(R*x - y)

ist, wobei y = Q'*b. Da die letzten m-n-Zeilen von R gleich null sind, besteht dieser Ausdruck aus zwei Teilen:

norm(R(1:n,1:n)*x - y(1:n))

und

norm(y(n+1:m))

Wenn A den vollen Rang aufweist, können Sie nach x auflösen, sodass der erste dieser Ausdrücke null ist. Dann gibt der zweite Ausdruck die Norm des Residuums an. Wenn A nicht den vollen Rang aufweist, kann mit der Dreiecksstruktur von R eine Basislösung für das Kleinste-Quadrate-Problem gefunden werden.

Verwenden der Multithread-Berechnung für die Faktorisierung

Die MATLAB Software 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.

lu und qr sind bei großen Arrays mit doppelter Präzision (in der Größenordnung von 10.000 Elementen) erheblich schneller.

Siehe auch

| |

Verwandte Themen