Dieser Artikel wurde maschinell übersetzt.
C#
Matrixuntergliederung
Matrix-Zerlegung, ein Verfahren, das eine quadratische numerische Matrix in zwei verschiedenen quadratische Matrizen, bricht ist die Basis für ein System von Gleichungen, effizient zu lösen, die wiederum ist die Basis für eine Matrix invertieren. Und eine Matrix invertieren ist ein Teil vieler wichtiger Algorithmen. Dieser Artikel präsentiert und c#-Code, die Zerlegung der Matrix, Matrix-Inversion, ein System von Gleichungen Lösung und damit zusammenhängenden Vorgängen erklärt.
Zugegeben, Matrix-Zerlegung ist ein ausgefallenes Thema nicht, aber eine Sammlung von Matrix-Methoden kann eine wichtige Ergänzung zu Ihrer persönlichen Code-Bibliothek. Die Methoden werden erläutert, damit Sie den Quellcode für Ihre eigenen Bedürfnisse ändern können. Darüber hinaus können einige der Techniken verwendet in den Matrix-Methoden in anderen Codierung Szenarien wiederverwendet werden.
Der beste Weg für Sie, um ein Gefühl für die Art der Informationen in diesem Artikel vorgestellten ist sich einen Blick auf den Screenshot in Abbildung 1. Das Demoprogramm beginnt durch Erstellen einer 4 x 4-Quadrat-Matrix und seine Werte anzeigen. Als nächstes ist die Matrix zerlegt, was eine Matrix LUP genannt hat. L steht für niedrigere und U für obere. Der P-Teil (P steht für Permutation) ist ein Array mit den Werten {3.120} und angibt, dass Zeilen 0 und 3 bei der Zersetzung ausgetauscht wurden. Die Zersetzung generiert auch Umschalten der Wert-1, darauf hinweist, dass eine ungerade Anzahl von Zeilenvertauschungen aufgetreten ist. Das Demoprogramm zeigt die Zersetzung auf zwei Arten: zunächst als eine kombinierte LU-Matrix und dann als separate L- und U-Matrizen. Als nächstes wird das Programm berechnet und zeigt die Umkehrung der ursprünglichen Matrix, mit der Matrix LUP hinter den Kulissen. Das Demoprogramm berechnet die Determinante der ursprünglichen Matrix, erneut mit die Zersetzung. Anschließend wird die Inverse der Matrix verwendet, um ein System von linearen Gleichungen zu lösen und durch die Kombination der L- und U-Matrizen wieder in die ursprüngliche Matrix schließt.
.png)
Abbildung 1 Matrix Zersetzung Demo
Aber warum gehen auf die Probleme der Erstellen eines benutzerdefinierten Matrix Dekompositionsverfahren und eine Bibliothek verwandter Methoden? Obwohl viele Standalone-Matrix-Tools verfügbar sind, können sie manchmal schwierig in eine Anwendung oder ein System zu integrieren sein. Und trotz der grundlegenden Bedeutung der Matrix-Zerlegung, es gibt einige kostenlose, nicht urheberrechtlich geschützt .NET Code Implementierungen zur Verfügung; diejenigen, die existieren, sind oft nicht detailliert genug, um Ihre Codierung Szenarien entsprechen den Quellcode ändern erklärt.
Dieser Artikel setzt voraus, dass du fortgeschrittene c# Programmierkenntnisse und zumindest ein grundlegendes Verständnis von Matrix-Operationen und Terminologie. Alle wichtigen c#-Code wird in diesem Artikel vorgestellt. Der Code ist auch von der MSDN Code Download-Website auf archve.msdn.microsoft.com/mag201212matrix.
Matrix-Definition
Es gibt mehrere Möglichkeiten, eine Matrix in c# zu implementieren. Der traditionelle Ansatz und verwendet in diesem Artikel ist ein Array von Arrays, manchmal genannt ein verzweigtes Array verwenden. Dieser Code definiert z. B. eine Matrix mit drei Zeilen und zwei Spalten:
double[][] m = new double[3][];
m[0] = new double[2];
m[1] = new double[2];
m[2] = new double[2];
m[2][1] = 5.0; // set row 2, col 1
Im Gegensatz zu den meisten Programmiersprachen hat c# einen integrierten mehrdimensionales Array-Typ, der einen alternativen Ansatz bietet. wie zum Beispiel:
double[,] m = new double[3,2];
m[2,1] = 5.0;
Ein dritter Ansatz zur Implementierung von Matrizen in c# ist ein einzelnes Array kombiniert mit Array-Index-Manipulation, wie folgt verwenden:
int rows = 3;
int cols = 2;
double[] m = new double[rows * cols];
int i = 2;
int j = 1;
m[i * cols + j] = 5.0;
Unabhängig von der Speicher-Schema verwendet können entweder ein OOP oder eine statische Methode Ansatz Matrizen implementiert werden. Beispielsweise könnte ein OOP Ansatz ähneln:
public class MyMatrix
{
int m; // number rows
int n; // number columns
data[][]; // the values
...
}
Es gibt keine einzelne beste Wahl für Matrix-Design; das beste Design hängt von der bestimmten Codierung Szenario, das Sie in Betrieb sind und Ihre persönlichen Vorlieben, Codierung. Dieser Artikel verwendet ein Static-Methode vorgehen, weil es am einfachsten ist zu verstehen und zu gestalten.
Wenn Sie eine Array von Arrays Design für Matrizen verwenden, weil jede Zeile separat reserviert werden muss, ist es oft praktisch eine Hilfsmethode zum Durchführen der Speicherreservierung definieren. wie zum Beispiel:
static double[][] MatrixCreate(int rows, int cols)
{
// creates a matrix initialized to all 0.0s
// do error checking here?
double[][] result = new double[rows][];
for (int i = 0; i < rows; ++i)
result[i] = new double[cols]; // auto init to 0.0
return result;
}
Die Methode kann aufgerufen werden wie folgt:
double[][] m = MatrixCreate(3,2);
m[2][1] = 5.0;
Diese Methode zeigt einen Vorteil schaffen Sie Ihre eigene Bibliothek von Matrix-Methoden: Wenn Sie die Leistung verbessern möchten, können Sie weglassen, die Eingabeparameter Fehlerüberprüfung — auf Kosten erhöhen das Risiko der aufrufende Code eine Ausnahme verursacht. (Dieser Artikel kurz zu halten, wurde die meisten Fehlerüberprüfung entfernt.) Ein weiterer Vorteil ist, dass Sie Ihre Bibliothek optimieren für Ihre genaue Szenario anpassen können. Erstellen Ihre eigene Bibliothek Hauptnachteil ist, dass als die Verwendung einer vorhandenen Bibliothek länger dauern kann.
Eine weitere bequeme Methode Ihre Matrix-Bibliothek hinzu zählt, die verwendet werden können, um eine Matrix als Zeichenfolge anzuzeigen. Hier ist eine Möglichkeit:
static string MatrixAsString(double[][] matrix)
{
string s = "";
for (int i = 0; i < matrix.Length; ++i)
{
for (int j = 0; j < matrix[i].Length; ++j)
s += matrix[i][j].ToString("F3").PadLeft(8) + " ";
s += Environment.NewLine;
}
return s;
}
Vielleicht möchten die Anzahl von Dezimalstellen angezeigt werden soll, oder die Spalte-Breite Polsterung parametrisieren.
Matrix-Multiplikation
Das Microsoft .NET Framework 4 und höher bieten eine nette Möglichkeit, die Leistung einer Matrix-Multiplikation-Methode wesentlich verbessern. Matrix-Multiplikation ist dargestellt Abbildung 2.
.png)
Abbildung 2-Matrix-Multiplikation
Beachten Sie, dass die Berechnung von jedem Zellwert des Ergebnisses nicht auf andere Zellenwerte im Ergebnis abhängig ist, so dass jede Berechnung unabhängig ist und potenziell parallel auf einem Computer mit mehreren Prozessoren ausgeführt werden können. Hier ist eine Standardmethode zur Matrix-Multiplikation:
static double[][] MatrixProduct(double[][] matrixA,
double[][] matrixB)
{
int aRows = matrixA.Length; int aCols = matrixA[0].Length;
int bRows = matrixB.Length; int bCols = matrixB[0].Length;
if (aCols != bRows)
throw new Exception("Non-conformable matrices in MatrixProduct");
double[][] result = MatrixCreate(aRows, bCols);
for (int i = 0; i < aRows; ++i) // each row of A
for (int j = 0; j < bCols; ++j) // each col of B
for (int k = 0; k < aCols; ++k)
result[i][j] += matrixA[i][k] * matrixB[k][j];
return result;
}
Da Matrix-Multiplikation ein O(n^3) Vorgang ist, kann die Leistung ein Problem sein. Beispielsweise wenn die Matrix A hat Größe 300 x 200 und Matrix B hat Größe 200 x 400, Datenverarbeitung das Produkt von A und B benötigt 300 * 200 * 400 = 24.000.000 Multiplikationen. Die Task Parallel Library (TPL) im System.Threading.Tasks-Namespace in das .NET Framework 4 und höher erleichtert, eine einfache parallelisierte Version des Matrix-Multiplikation zu codieren. Eine Möglichkeit ist:
static double[][] MatrixProduct(double[][] matrixA,
double[][] matrixB)
{
// error check, compute aRows, aCols, bCols
double[][] result = MatrixCreate(aRows, bCols);
Parallel.For(0, aRows, i =>
{
for (int j = 0; j < bCols; ++j)
for (int k = 0; k < aCols; ++k)
result[i][j] += matrixA[i][k] * matrixB[k][j];
}
);
return result;
}
Diese Version zerkleinert, bis die Berechnungen von Zeilen. Hinter den Kulissen erzeugt die TPL ganzen komplexen Synchronisation Sanitär Code um die Berechnungen auf mehreren Prozessoren ausgeführt.
Konsistenz testen
Ein interessanter Aspekt einer Bibliothek von Methoden, die miteinander verwandt sind ist, dass es oft möglich, testen sie überprüfen, um festzustellen, ob sie konsistente Ergebnisse. Z. B. angenommen, Sie haben eine Methode erstellt, die eine zufällige Matrix:
static double[][] MatrixRandom(int rows, int cols,
double minVal, double maxVal, int seed)
{
// return matrix with values between minVal and maxVal
Random ran = new Random(seed);
double[][] result = MatrixCreate(rows, cols);
for (int i = 0; i < rows; ++i)
for (int j = 0; j < cols; ++j)
result[i][j] = (maxVal - minVal) * ran.NextDouble() + minVal;
return result;
}
Darüber hinaus angenommen, Sie haben eine Matrix, die die Identität Matrix erstellt — d. h., eine quadratische Matrix mit 1.0s auf der Hauptdiagonale, 0.0s an anderer Stelle:
static double[][] MatrixIdentity(int n)
{
double[][] result = MatrixCreate(n, n);
for (int i = 0; i < n; ++i)
result[i][i] = 1.0;
return result;
}
Und angenommen, Sie haben eine Methode, die auf Gleichheit zweier Matrizen vergleicht:
static bool MatrixAreEqual(double[][] matrixA,
double[][] matrixB, double epsilon)
{
// true if all values in A == corresponding values in B
int aRows = matrixA.Length;
int bCols = matrixB[0].Length;
for (int i = 0; i < aRows; ++i) // each row of A and B
for (int j = 0; j < aCols; ++j) // each col of A and B
if (Math.Abs(matrixA[i][j] - matrixB[i][j]) > epsilon)
return false;
return true;
}
Bekanntmachung der MatrixAreEqual-Methode vergleicht nicht Zellwerte genaue Gleichheit, da die Werte doppelt sind. Stattdessen überprüft die Methode, um festzustellen, ob alle Werte für die Zellen sind sehr (max. Epsilon) miteinander schließen.
Da das Produkt quadratische Matrix m und die Einheitsmatrix gleicher Dimension der ursprünglichen Matrix m entspricht, können Sie die Matrix Produkt-Methode nach dem Vorbild dieses Codes testen:
double[][] m = MatrixRandom(4, 4, -9.0, 9.0, 0);
double[][] i = MatrixIdentity(4);
double[][] mi = MatrixProduct(m, i);
if (MatrixAreEqual(m, mi, 0.00000001) == true)
Console.WriteLine("Consistent result");
else
Console.WriteLine("Something is wrong");
Consistency checking lends itself well to random input testing.
Matrixuntergliederung
Matrix-Zerlegung wird eine quadratische Matrix M und berechnet zwei neue quadratische Matrizen, die gemeinsam multipliziert, wenn die ursprüngliche Matrix M geben. Die Idee ist ähnlich wie gewöhnliche Anzahl factoring: die Zahl 6 kann in 2 und 3 berücksichtigt werden, da 2 * 3 = 6. Zuerst war es scheinen mag, als gäbe es herausbringt zerlegen einer Matrix, aber es wenig Sinn, das Matrix-Zerlegung der Matrix-Inversion die sehr schwierige Aufgabe ganz ein bisschen einfacher macht. Es gibt viele verschiedene Arten von Matrix-Zerlegung, und jede Art kann mit mehreren verschiedene Algorithmen berechnet werden. Die in diesem Artikel vorgestellten Technik heißt LUP Zersetzung und Doolittles Methode mit partieller Pivotierung verwendet.
Um LUP Zersetzung zu verstehen, ist es hilfreich, zuerst die einfachere LR-Zerlegung, verstehen, die von dem berühmten Mathematiker Alan Turing eingeführt wurde. Genommen Sie an, Sie haben diese 4 x 4-Matrix M:
9.000 5.000 3.000 4.000
4.000 8.000 2.000 5.000
3.000 5.000 7.000 1.000
2.000 6.000 0.000 8.000
Eine mögliche LR-Zerlegung von M ist L =
1.000 0.000 0.000 0.000
0.444 1.000 0.000 0.000
0.333 0.577 1.000 0.000
0.222 0.846 -0.219 1.000
Und U =
9.000 5.000 3.000 4.000
0.000 5.778 0.667 3.222
0.000 0.000 5.615 -2.192
0.000 0.000 0.000 3.904
Dies funktioniert, da L * U = M. Beachten Sie, dass die untere L Matrix 1.0s auf der diagonalen und 0.0s oben rechts hat. Mit anderen Worten, sind die erheblichen Zellwerte der unteren Matrix unten links. Ebenso sind die bedeutenden Zellwerte der oberen Matrix auf der Hauptdiagonale und oben rechts.
Beachten Sie auch, dass es keine Überlappungen der Standorte der die bedeutenden Zellwerte in L und U. Also, statt zwei Ergebnisse Matrizen, L und U, Matrix-Zerlegung speichert in der Regel die unteren und oberen Ergebnisse in eine einzelne Matrix, die enthält sowohl L und U, um Speicherplatz zu sparen.
LUP-Matrix-Zerlegung ist eine leichte, aber wichtige Abwandlung LR Zerlegung. LUP Zersetzung nimmt eine Matrix M und L und U-Matrizen, sondern auch ein P-Array erzeugt. Das Produkt von L und U in LUP ist nicht gerade die ursprüngliche Matrix M, sondern ist eine Version des M wo haben einige Zeilen neu geordnet worden. Die Art und Weise, in der die Zeilen neu geordnet worden haben, wird in der P-Array gespeichert; Diese Informationen können verwendet werden, die ursprüngliche Matrix M rekonstruieren.
Ein enger Verwandter für die Zersetzung des Doolittle in diesem Artikel vorgestellten heißt Crout der Zersetzung. Der Hauptunterschied zwischen Doolittle und Crout ist, dass Doolittle 1.0s auf der Hauptdiagonale der Matrix L platziert und Crout 1.0s auf der Hauptdiagonalen der Matrix U stellt.
Der Grund LUP Zersetzung wird öfter als LR Zerlegung subtil ist verwendet. Wie Sie bald sehen werden, wird zur Zerlegung der Matrix die Inverse einer Matrix berechnen. Allerdings wird als Helfer für die Invertierung der Matrix Matrix-Zerlegung verwendet, stellt sich heraus, dass die Inversion fehl, wenn auf der Hauptdiagonale der Matrix LU wird der Wert 0,0. Also tauscht in LUP Aufspaltung, wenn eine 0.0, die Wert auf der Hauptdiagonale, endet der Algorithmus zwei Zeilen zum Verschieben der Wert 0,0 die Diagonale aus und verfolgt die Spuren der welche Zeilen im Array P ausgetauscht wurden.
Abbildung 3 listet eine Matrix Dekompositionsverfahren.
Abbildung 3 Matrix Dekompositionsverfahren
static double[][] MatrixDecompose(double[][] matrix,
out int[] perm, out int toggle)
{
// Doolittle LUP decomposition
// assumes matrix is square.
int n = matrix.Length; // convenience
double[][] result = MatrixDuplicate(matrix);
perm = new int[n];
for (int i = 0; i < n; ++i) { perm[i] = i; }
toggle = 1;
for (int j = 0; j < n - 1; ++j) // each column
{
double colMax = Math.Abs(result[j][j]); // largest val in col j
int pRow = j;
for (int i = j + 1; i < n; ++i)
{
if (result[i][j] > colMax)
{
colMax = result[i][j];
pRow = i;
}
}
if (pRow != j) // swap rows
{
double[] rowPtr = result[pRow];
result[pRow] = result[j];
result[j] = rowPtr;
int tmp = perm[pRow]; // and swap perm info
perm[pRow] = perm[j];
perm[j] = tmp;
toggle = -toggle; // row-swap toggle
}
if (Math.Abs(result[j][j]) < 1.0E-20)
return null; // consider a throw
for (int i = j + 1; i < n; ++i)
{
result[i][j] /= result[j][j];
for (int k = j + 1; k < n; ++k)
result[i][k] -= result[i][j] * result[j][k];
}
} // main j column loop
return result;
}
Die Methode kann wie folgt aufgerufen werden:
double[][] m = MatrixRandom(4, 4, -9.0, 9.0, 0);
int[] perm;
int toggle;
double luMatrix = MatrixDecompose(m, out perm, out toggle);
Die MatrixDecompose-Methode akzeptiert als Eingabe eine quadratische Matrix. Die Methode hat drei Rückgabewerte. Die explizite Rückkehr ist eine permutierten LU-Matrix. Die Methode gibt zwei Werte als out-Parameter. Eine ist eine Permutation-Array, das enthält die Informationen über die Zeilen wie permutierte waren. Die zweite Parameter ist ein Knebel Wert + 1 oder-1 je nachdem, ob die Anzahl der Zeilenvertauschungen sogar (+ 1) oder ungerade (-1 war). Der Knebel-Wert nicht zur Invertierung der Matrix verwendet aber ist erforderlich, wenn die Matrix-Zerlegung verwendet wird, um die Determinante einer Matrix zu berechnen.
Die MatrixDecompose-Methode ist ziemlich schwierig, aber realistisch, es gibt nur ein paar Details, die Sie verstehen, um den Code zu ändern müssen. Die hier vorgestellte Version wird neuen Speicher für die Rückkehr LU-Matrix mit einer Hilfsmethode MatrixDuplicate:
static double[][] MatrixDuplicate(double[][] matrix)
{
// assumes matrix is not null.
double[][] result = MatrixCreate(matrix.Length, matrix[0].Length);
for (int i = 0; i < matrix.Length; ++i) // copy the values
for (int j = 0; j < matrix[i].Length; ++j)
result[i][j] = matrix[i][j];
return result;
}
Ein alternativer Ansatz ist es, das Ergebnis in die Eingabematrix zu berechnen, um Speicher zu sparen. Mit c# Semantik würde dies dem Matrix-Parameter einen Ref-Parameter machen da es für Eingabe und Ausgabe verwendet wird. Mit diesem Ansatz wäre die Signatur die Methode:
static void MatrixDecompose(ref double[][] matrix, out int[] perm,
out int toggle)
Oder, da die explizite, dass Wert entfernt wurde zurückgeben, Sie könnten es für Variation Array verwenden oder Umschalten der Börsen. wie zum Beispiel:
static int[] MatrixDecompose(ref double[][] matrix, out int toggle)
Vielleicht möchten beseitigen den Knebel-Parameter, um die Signatur die Methode zu vereinfachen, wenn Sie nicht beabsichtigen, Matrix-Zerlegung zu verwenden, um einen bestimmenden Faktor zu berechnen.
Ein weiterer Bereich der MatrixDecompose, die Sie ändern möchten, ist diese Aussage:
if (Math.Abs(result[j][j]) < 1.0E-20)
return null;
In Worten bedeutet dieser Code: "Wenn auch nach dem Austausch von zwei Zeilen, da gab es einen Wert 0,0 auf der Hauptdiagonale, es noch eine 0.0 gibt gibt, dann null zurück." Vielleicht möchten Sie ändern den Wert der willkürlichen Epsilon für die Chancengleichheit von NULL Check von 1. 0E-20 mit einem anderen Wert anhand der Präzision-Merkmale Ihres Systems. Und anstatt Null, vielleicht möchten Sie eine Ausnahme auslösen; wäre die Methode aufgerufen werden, als Teil der Matrix-Inversion, würde die Inversion fehlschlagen. Schließlich, wenn Sie zu einem bestimmten Zweck als Umkehrung der Matrix Matrix-Zerlegung verwenden, sollten Sie diese Aussage ganz zu beseitigen.
Matrix-Inversion
Der Schlüssel zum mit Matrix-Zerlegung eine Matrix invertieren ist eine Hilfsmethode schreiben, die ein System von Gleichungen löst. Diese wichtige Hilfsmethode präsentiert sich in Abbildung 4.
Abbildung 4 die HelperSolve-Methode
static double[] HelperSolve(double[][] luMatrix,
double[] b)
{
// solve luMatrix * x = b
int n = luMatrix.Length;
double[] x = new double[n];
b.CopyTo(x, 0);
for (int i = 1; i < n; ++i)
{
double sum = x[i];
for (int j = 0; j < i; ++j)
sum -= luMatrix[i][j] * x[j];
x[i] = sum;
}
x[n - 1] /= luMatrix[n - 1][n - 1];
for (int i = n - 2; i >= 0; --i)
{
double sum = x[i];
for (int j = i + 1; j < n; ++j)
sum -= luMatrix[i][j] * x[j];
x[i] = sum / luMatrix[i][i];
}
return x;
}
Die HelperSolve-Methode findet ein Array X, dass beim multipliziert eine Matrix LU Array b gibt. Die Methode ist sehr clever und können Sie nur vollständig verstehen von Verfolgung durch ein paar Beispiele. Es gibt zwei Schleifen. Die erste Schleife verwendet forward Ersetzung im unteren Teil der Matrix LU. Die zweite Schleife verwendet rückwärts Ersetzung im oberen Teil der Matrix LU. Einige andere Matrix Zersetzung Implementierungen rufen ihre analoge-Methode so etwas wie LuBackSub.
Obwohl der Code kurz ist, es ist schwierig, aber es sollte keine Szenarien, wo Sie den Code ändern müssten. Hinweis, dass Helferlösen eine LU-Matrix aus MatrixDecompose akzeptiert aber keine Dauerwelle-Out-Parameter verwendet. Dies bedeutet, dass HelperSolve ist in der Tat ein Helfer-Methode und Bedürfnissen zusätzliche Wrappercode, ein System von Gleichungen zu lösen. Wenn Sie den Code in diesem Artikel ein OOP-Entwurf umgestalten, sollten Sie eine private Methode HelperSolve zu machen.
Mit der HelperSolve-Methode an Stelle die Matrix-Inversion-Methode kann implementiert werden, wie in Abbildung 5.
Abbildung 5 die MatrixInverse-Methode
static double[][] MatrixInverse(double[][] matrix)
{
int n = matrix.Length;
double[][] result = MatrixDuplicate(matrix);
int[] perm;
int toggle;
double[][] lum = MatrixDecompose(matrix, out perm, out toggle);
if (lum == null)
throw new Exception("Unable to compute inverse");
double[] b = new double[n];
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < n; ++j)
{
if (i == perm[j])
b[j] = 1.0;
else
b[j] = 0.0;
}
double[] x = HelperSolve(lum, b);
for (int j = 0; j < n; ++j)
result[j][i] = x[j];
}
return result;
}
Auch hier ist der Code schwierig. Der Umkehrung-Algorithmus basiert auf der Idee, dass das Produkt einer Matrix M und ihre Umkehrung die Einheitsmatrix ist. MatrixInverse-Methode löst im wesentlichen eines Gleichungssystems Ax = b, wobei A eine LR-Zerlegung Matrix und b Konstanten sind entweder 1.0 oder 0.0 und auf die Identitätsmatrix entsprechen. Beachten Sie, dass MatrixInverse Perm Array den Aufruf von MatrixDecompose verwendet.
Aufrufen der MatrixInverse-Methode könnte wie folgt aussehen:
double[][] m = MatrixRandom(4, 4, -9.0, 9.0, 0);
double[][] inverse = MatrixInverse(m);
Console.WriteLine(MatrixAsString(inverse));
Um zusammenzufassen, ist eine wichtige Matrix-Operation Matrix Inversion, die ziemlich schwierig ist. Ein Ansatz besteht darin, die ursprüngliche Matrix zersetzen, schreiben ein Helfer lösen, Methode, die vorwärts und rückwärts Substitution ausführt und dann lösen Verwendung der Zersetzung zusammen mit LU Permutation Array und der Helfer Methode um die Inverse zu finden. Dieser Ansatz mag kompliziert erscheinen, aber es ist in der Regel effizienter und einfacher als eine Inverse Matrix direkt Datenverarbeitung.
Matrixdeterminante
Mit einer Matrix-Zerlegung-Methode in der Hand ist es einfach, eine Methode zur Berechnung der Determinante einer Matrix code:
static double MatrixDeterminant(double[][] matrix)
{
int[] perm;
int toggle;
double[][] lum = MatrixDecompose(matrix, out perm, out toggle);
if (lum == null)
throw new Exception("Unable to compute MatrixDeterminant");
double result = toggle;
for (int i = 0; i < lum.Length; ++i)
result *= lum[i][i];
return result;
}
Wie es sich ein wenig überraschend herausstellt, ist die Determinante einer Matrix plus oder minus (je nach Wert ein/aus) nur das Produkt der Werte auf der Hauptdiagonale der Matrix LUP Zersetzung. Beachten Sie, dass eine implizite Typkonvertierung des Wertes der Knebel von Int zu verdoppeln. Zusätzlich zu den Fehlerüberprüfung zu MatrixDeterminant sollten Sie hinzufügen einen Kurzschluss Rückkehr in Situationen, wo die Eingabematrix Größe 1 (dann Rückkehr der Einzelwert) oder Größe 2 x 2 hat (dann zurück ein * d - b * c). Aufrufen der bestimmenden Methode könnte so aussehen:
double[][] m = MatrixRandom(4, 4, -9.0, 9.0, 0);
double det = MatrixDeterminant(m);
Console.WriteLine("Determinant = " + det.ToString("F2"));
Lösung von Gleichungen
Die HelperSolve-Methode kann leicht angepasst werden, um ein System von linearen Gleichungen zu lösen sein:
static double[] SystemSolve(double[][] A, double[] b)
{
// Solve Ax = b
int n = A.Length;
int[] perm;
int toggle;
double[][] luMatrix = MatrixDecompose(A,
out perm, out toggle);
if (luMatrix == null)
return null; // or throw
double[] bp = new double[b.Length];
for (int i = 0; i < n; ++i)
bp[i] = b[perm[i]];
double[] x = HelperSolve(luMatrix, bp);
return x;
}
Hier ist der Code, der das Bildschirmfoto in produziert Abbildung 1 zur Lösung des folgenden Systems:
3x0 + 7x1 + 2x2 + 5x3 = 49
x0 + 8x1 + 4x2 + 2x3 = 30
2x0 + x1 + 9x2 + 3x3 = 43
5x0 + 4x1 + 7x2 + x3 = 52
double[][] m = MatrixCreate(4, 4);
m[0][0] = 3.0; m[0][1] = 7.0; m[0][2] = 2.0; m[0][3] = 5.0;
m[1][0] = 1.0; m[1][1] = 8.0; m[1][2] = 4.0; m[1][3] = 2.0;
m[2][0] = 2.0; m[2][1] = 1.0; m[2][2] = 9.0; m[2][3] = 3.0;
m[3][0] = 5.0; m[3][1] = 4.0; m[3][2] = 7.0; m[3][3] = 1.0;
double[] b = new double[] { 49.0, 30.0, 43.0, 52.0 };
double[] x = SystemSolve(m, b);
Console.WriteLine("\nSolution is x = \n" + VectorAsString(x));
Beachten Sie, dass die SystemSolve der b-Eingabeparameter mit dem Perm-Array aus MatrixDecompose vor dem Aufruf von HelperSolve ordnet.
Verständnis des Permutation Arrays
Die letzten Zeilen der Ausgabe im Screenshot unter Abbildung 1 darauf hinweisen, dass es möglich ist, die L und U Matrizen in einer Weise erhalten die ursprüngliche Matrix multipliziert. Zu wissen, wie Sie dies tun nicht können Sie die Matrix praktische Probleme zu lösen, aber es hilft Ihnen zu verstehen, den P-Teil des LUP Zersetzung. Regenerierende eine ursprüngliche Matrix aus seiner L- und U-Komponenten kann auch für Ihre Matrix Bibliothek Testmethoden für Konsistenz nützlich sein.
Eine Möglichkeit, eine ursprüngliche Matrix regenerieren nach dem LUP Zersetzung ist die L und U multiplizieren und dann Vertausche die Zeilen des Produkts mit dem P-Array:
// create matrix m
// call MatrixDecompose, returning lu and perm
// extract the lower part of lu as matrix 'lower'
// extract the upper part of lu as matrix 'upper'
double[][] lu = MatrixProduct(lower, upper);
double[][] orig = UnPermute(lu, perm);
if (MatrixAreEqual(orig, m, 0.000000001) == true)
Console.WriteLine("L and U unpermuted using perm array");
Die UnPermute-Methode kann wie folgt kodiert werden:
static double[][] UnPermute(double[][] luProduct, int[] perm)
{
double[][] result = MatrixDuplicate(luProduct);
int[] unperm = new int[perm.Length];
for (int i = 0; i < perm.Length; ++i)
unperm[perm[i]] = i; // create un-perm array
for (int r = 0; r < luProduct.Length; ++r) // each row
result[r] = luProduct[unperm[r]];
return result;
}
Ein zweiter Ansatz zum Regenerieren von einer ursprünglichen Matrix aus seiner Zersetzung LUP ist das Perm-Array in eine Matrix Perm konvertieren und dann multiplizieren die Perm-Matrix und die kombinierten LU-Matrix:
// create matrix m
// call MatrixDecompose, returning lu and perm
// extract the lower part of lu as matrix 'lower'
// extract the upper part of lu as matrix 'upper'
double[][] permMatrix = PermArrayToMatrix(perm);
double[][] orig = MatrixProduct(permMatrix, lu);
if (MatrixAreEqual(orig, m, 0.000000001) == true)
Console.WriteLine("L and U unpermuted using perm matrix");
Eine Dauerwelle-Matrix ist eine quadratische Matrix mit einem 1.0 Wert in jeder Zeile und jeder Spalte. Die Methode, die eine Dauerwelle-Matrix aus einem Array von Perm erzeugt codiert werden wie folgt:
static double[][] PermArrayToMatrix(int[] perm)
{
// Doolittle perm array to corresponding matrix
int n = perm.Length;
double[][] result = MatrixCreate(n, n);
for (int i = 0; i < n; ++i)
result[i][perm[i]] = 1.0;
return result;
}
Zusammenfassung
Es gibt viele Algorithmen, die erfordern ein System von linearen Gleichungen zu lösen, suchen, die Inverse einer Matrix oder die Determinante einer Matrix zu finden. Mit Matrix-Zerlegung ist eine effektive Technik für alle diese Operationen ausführen. Der hier vorgestellte Code kann in Situationen verwendet, wo Sie keine externen Abhängigkeiten in Ihrem Code-Basis wollen oder Sie benötigen die Fähigkeit, die Vorgänge um die Leistung verbessern oder Ändern von Funktionen anpassen. Nehmen Sie die rote Pille!
Dr.James McCaffrey arbeitet für Volt Information Sciences Inc., wo er technische Schulungen für Softwareentwickler bei der Microsoft in Redmond, Washington Campus. Er hat an verschiedenen Microsoft-Produkten mitgearbeitet, unter anderem an Internet Explorer und MSN Search. McCaffrey ist Autor von .NET Test Automation Recipes (Apress, 2006). Er kann erreicht werden unter jammc@microsoft.com.
Unser Dank gilt den folgenden technischen Experten für die Durchsicht dieses Artikels: Paul Koch und Dan Liebling