to be continued
Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Komplexitaeten von den Verfahren ( in O notation)
mach grad paar aufgaben, und schreibe meine loesungen zu den kompl. in o schreibweise hier rein,
lest sie euch durch, ueberprueft sie, korrigiert wenn falsch , added eigene, und am ende haben wir ne schoene sammlung zum auswendig reinknueppeln…
Anfangen ich jetzt ;-):
Komplexitaet LR Zerlegung: O(n^3)
quelle: https://lp.uni-goettingen.de/get/text/1018
Komplexitaet Vor bzw Rueck einsetzen nach LR zerlegung: O(n^2 + (n^2)/2 - n) = O(n^2)
quelle: rechnung wieviel schritte man brauch,umformen zu summenformel, und nutzen von wolframalpha
Komplexitaet von loesen von gleichung it LR und vor,rueckwaertseinsetzun: O ( n^3 + n^2 + n^2) = O(n^3)
QR-Zerlegung (beide Verfahren): O(n^3)
Matrix-Matrix Multiplikation: O(n^3)
Matrix-Vektor Multiplikation: O(n^2)
Polynom-Auswertung mit Horner-Schema: O(n)
cg-Verfahren: O(n^3)
Lösen von Gleichungssystemen mit tridiagonalen Matrizen: O(n)
QR-Zerlegung (beide Verfahren): O(n^3)
Matrix-Matrix Multiplikation: O(n^3)
Matrix-Vektor Multiplikation: O(n^2)
Polynom-Auswertung mit Horner-Schema: O(n)
cg-Verfahren: O(n^3)
Lösen von Gleichungssystemen mit tridiagonalen Matrizen: O(n)
Seid ihr euch bei den Komplexitäten sicher?
Hab hier in ner Zusammenfassung auch a paar gefunden:
Algorithmus von Aitken-Neville O(n²)
Algorithmus von DeCasteljau O(n²)
Algorithmus von Gauss O(n³)
Thomas-Algorithmus O(n)
Ax=b bei vollbesetztem A O(n³)
Rx=b (Dreieck) O(n²)
Vandermonde O(n³)
Cattmull-Rom-Spline O(n³)
Jacobi, Gseidel O(n²)
Householder O(n³)
LR-Zerlegung selber hat O(n³). Das ist ja praktisch das Gauss’sche Eliminationsverfahren bei dem man sich zusätzlich die Koeffizienten „merkt“. Das anschließende Vorwärts- / Rückwärtseinsetzen hat dann O(n²).
Verwendet man das cg-Verfahren zur Optimierung quadratischer Funktionale (und damit als Anwendung dessen Lösen von LGS), so liefert das cg-Verfahren (wenn man exakt d.h. mit unbegrenzter Genauigkeit rechnet) in n Schritten die Lösung. Da ein solcher Schritt allerdings Matrix-Vektor Multiplikationen enthält ( O(n²) ), ergibt sich eine Gesamtkomplexität von O(n³).
Diskrete Faltung zweier Vektoren (periodischer Fall): O(n)
FFT (Fast-Fourier-Transformation) eines Vektors: O(n*log n)
Ein Iterationsschritt des SOR-Verfahrens (vollbesetzte Matrizen): O(??)
Bestimmen der Maximums-Norm eines Vektors: O(n)
Filterung eines m x m Pixel großen Bildes mit einer (nicht separierbaren) Maske der Größe n x n: O(??)
Soweit ich mich erinnern kann, kam das im SS SoSe 2010 gar nicht dran und duerfte somit auch nicht Teil des Klausurstoffs sein.
überragend 
Das SOR Verfahren ist einfach das Gauss-Seidel Verfahren mit Relaxation nach jedem Iterationsschritt. Am Aufwand für einen Iterationsschritt ändert das (in Landau Notation) nichts. Es bleibt also bei O(n²). Bei guter Wahl des Relaxationsparameters lässt sich damit allerdings die Konvergenzgeschwindigkeit beträchtlich steigern. Ich halte das in Hinblick auf die Klausur aber für eher unwichtig.