Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

@@ Zeile 1: / Zeile 1: @@
+===== Komplexitäten =====
+Editierhinweise: Zum Escapen zwei Prozentzeichen am Anfang und am Ende nutzen. Zwei Backslashes und Leerzeichen für eine Newline in der Tabelle.
+^ Problem ^ Aufwand ^ Weitere Anmkerungen ^
+| Matrix-Vektor|O(n²)|
+| Matrix-Matrix|O(n³)|
+| Matrix-Vektor, wenn Matrix Rang 1 hat und %%A = uv^T%% geg.|O(n)|
+| LR-Zerlegung|O(n³)|
+| QR-Zerlegung|O(n³)|
+| QR mit Householder:|~doppelt so viel wie LR|
+| QR mit Givens-Rotation:|~vier mal so viel wie LR|
+| Cholesky: SPD Matrizen|~halb so groß wie LR|
+| Rückwärts- & Vorwärtssubst. bei geg. LR:|O(n²)|
+| Lösen bei geg. LR:|O(n²)||
+| Lösen bei geg. QR:|O(n²)|
+| A = LU, Determinante:|O(n)||
+| A = P L U, Betrag der Determinante|O(n)|
+| A = P L U, Determinante:|O(n³)|vllt. O(n²)\\ Siehe unten.|
+| A = QR, Determinante|O(n³)|
+| A = QR, Betrag der Determinante|O(n³)|
+| LR m-diagonale Matrix:|O(m² * n)|
+| Rückwärts- & Vorwärtssubst. bei geg. LR von m-diagonaler Matrix:|O(n*m)|
+|||
+| Interpolation Nearest Neighbor:|O(h)|
+| Interpolation Linear:|O(h²)|
+| Interpolation Catmull-Rom|O(h³)|
+|||
+| Newton (Aitken-Neville Pyramide):|O(n²)|
+| De Casteljau:|O(n²)|
+| Midpoint Subdivision Fehler:|%%O(1/(levelZahl^4))%%|
+|||
+| Ein Iterationsschritt Jacobi / GS / SOR|O(n²)|
+| Anzahl Iterschritte bei Jacobi|O(n)|(Schätzwert)|
+| Anzahl Iterschritte bei SOR|O(sqrt(n))|(Schätzwert)|
+| Konvergenzordnung Jacobi / GS / SOR|rho = 1|Lineare Konvergenz, d. h. feste Anzahl an Iterationen nimmt der Fehler um einen __Faktor__ ab.|
+|||
+| Filter NxN Bildausschnitt (Rand vernachlässigbar), nicht sep. MxM Filter, insgesamte Anz. arithmetischer Ops:|2 N² M²|
+| Filter NxN Bildausschnitt (Rand vernachlässigbar), sep. MxM Filter, insgesamte Anz. arithmetischer Ops:|4 N² M|
+===== Algorithmen Details =====
+==== A = PLU, det(A) bestimmen. ====
+Beachte, dass nur |det(P)| = 1 gilt (mit Betrag!). Da P reell, kann also det(P) nur + 1 oder -1 sein.
+P ist eine Permutationsmatrix, d. h. die Spalten sind e_1, e_2, e_3, ... nur umsortiert. Finde zuerst die erste 1 in der ersten Zeile (dies ist e_1), dann dies 'gedanklich' vortauschen. Pro Tauschschritt ändert sich die Determinante um den Faktor (-1). Dann finde die erste 1 in der zweiten Zeile usw. Das sind n^2 Schritte. Die finale Determinante ergibt sich zu: %%det(P) = (-1)^#Vertauschungen%%