Cholesky-Zerlegung < Lin. Gleich.-systeme < Numerik < Hochschule < Mathe < Vorhilfe
| |
|
Hiho
Das wären dann
[mm] $\sim \bruch{1}{6}n^{3}$ [/mm] Divisionen/Multiplikationen und n Quadratwurzeln.
Gruss
EvenSteven
|
|
|
| |
|
Hallo Bastiane!
> Bist du sicher? Denn das wären doch jetzt auch [mm]O(n^3)[/mm]
> Operationen und demnach nicht wirklich weniger als beim
> Gauß-Algorithmus!? ![[kopfkratz3]](/images/smileys/kopfkratz3.gif "[kopfkratz3]") Oder könnte mir jemand
> sagen, warum es sonst bei spd-Matrizen günstiger ist, das
> Cholesky-Verfahren zu nehmen?
Im Knorrenschild sind die genauen Werte angegeben:
Der Aufwand für das Berechnen der [mm]LR\texttt{-Zerlegung}[/mm] mit dem Gauß-Algorithmus beträgt [mm]\tfrac{1}{3}n^3 - \tfrac{1}{3}n[/mm] Punktoperationen, und der für die Cholesky-Zerlegung benötigt [mm]\tfrac{1}{6}n^3 + \tfrac{1}{2}n^2 - \tfrac{2}{3}n[/mm] Punktoperationen und [mm]n[/mm] Wurzelberechnungen.
Na ja, und jetzt vereinfache folgende Ungleichung soweit wie möglich:
[mm]\frac{n^3}{3} - \frac{n}{3} > \frac{n^3}{6} + \frac{n^2}{2} - \frac{2}{3}n + n[/mm]
Also ich glaube schon, daß die Cholesky-Zerlegung für sym.pos.d._Matrizen schneller zu berechnen ist, oder?
Viele Grüße
Karl
|
|
|
| |
|
Hi Bastiane,
na klar, [mm] 2*1/6*n^{3} [/mm] = [mm] 1/3*n^{3}. [/mm] Das ist die Hälfte.
Schönen Gruß
MM
|
|
|
| |
|
[mm] 1/6*n^{3} [/mm] stimmt. Das habe ich auch bei meinen Unterlagen stehen.
Habe ausserdem notiert, dass der Aufwand im Vergleich zu Gauß halb soviel sein soll.
Begründung: Man nutzt die Symmetrie aus und muss somit nur noch eine Hälfte der Matrix berechnen. Die Cholesky-Zerlegung lautet ja A=L'*L'^{T}, wobei [mm] L':=L*D^{1/2}
[/mm]
Man berechnet also gar nicht mehr R wie bei der LR-Zerlegung, sondern nur noch L. Wie aber genau das funktioniert weiß ich auch nicht und würde mich auch interessieren. Vielleicht weiß da jemand ja mehr drüber.
Ein weiterer Vorteil bei Cholesky ist eben, dass man für s.p.d. Matrizen keine Pivotisierung braucht.
Schönen Gruß
MM
|
|
|
|
)
![[cap]](/images/smileys/cap.gif "[cap]"){kind=small}
![[kopfkratz]](/images/smileys/kopfkratz.gif "[kopfkratz]"){kind=small}
![[gutenacht]](/images/smileys/gutenacht.gif "[gutenacht]"){kind=small}
