Diskussion:QR-Algorithmus
Letzter Kommentar: vor 13 Jahren von LutzL
Was ist denn die Laufzeit in O-Notation? O(n^3)? (nicht signierter Beitrag von Trailblazerger (Diskussion | Beiträge) )
- Das hängt ab. O(n^3) ist eine untere Schranke, da die Herstellung der Hessenbergform soviel kostet. Multishift-Verfahren mit Bulge-Verbänden der Länge m kosten laut angegebener Literatur O(mn^2) in jedem Durchlauf, wobei praktisch quadratische bis kubische Konvergenz in den unteren m Eigenwerten beobachtet wird. Pro Eigenwert also O(n^2) Operationen, zusammen O(n^3).--LutzL 19:29, 12. Jun. 2007 (CEST)
Guter Artikel! Ich habe gerade eine Eigenwertzerlegung damit implementiert und teste sie an einer symmetrischen 3x3-Matrix. Als Polynom verwende ich p(a)=a-k. Nach wenigen Iterationsschritten ist alles klar. Allerdings wundert mich folgendes: Der Wilkinson-Shift liefert nach meiner bisherigen Erfahrung keine Verbesserung gegenueber dem a[n][n]-Shift. Verwende ich stattdessen den betragskleinsten Eigenwert der rechten unteren 2x2-Matrix (a[n-1][n-1]...a[n][n]), funzt's super (das entspricht dem Multishift fuer den Fall s=2,m=1). Hat noch jemand Erfahrung damit gemacht? --Deprecated 18:23, 14. Jul. 2010 (CEST)
- 3x3 ist evtl. zu klein, um diese Effekte richtig zu beobachten. Ich könnte mich täuschen, aber mir ist so als ob Wilkinson besonders dann gut funktioniert, wenn die Matrix zuerst in Hessenbergform, d.h. bei symmetrischen Matrizen in Tridiagonalform gebracht wird.--LutzL 10:33, 15. Jul. 2010 (CEST)