Lösung lineares Gleichungssystem (Komplexität)

[Informatik (Gast)]

In einer Vorlesung wurde am Rande die O-Notation eingeführt. Zur Lösung 
von LGS eignet sich die QR-Zerlegung. Dabei wird schrittweise ein 
Element der zu zerlegenden Matrix zu null gesetzt. Demnach müsste die 
Matrix nach
[math] \sum_{i =  1}^{n-1} (n - i) /math]
Durchläufe in Form einer Dreiecksmatrix vorliegen.

Ein Wikipedia-Eintrag hierzu 
https://de.wikipedia.org/wiki/Givens-Rotation schätzt den Aufwand zu 
O(n^2) ab (n*m Matrix-Matrix Produkte seien zu bilden).

Ein weiterer Eintrag hierzu 
https://fsi.cs.fau.de/forum/thread/7466-Komplexitaeten-von-den-Verfahren-in-O-notation 
schätzt den Aufwand zu O(n^3) ab.

Meine Frage:
Was stimmt an meiner Überlegung zur Anzahl an Durchläufen einer QR 
Zerlegung nicht, bzw. wie kommt man zur Angabe O(n^2), bzw. O(n^3)?

[Heinrich von der Ahle (Gast)]

Informatik schrieb:
> In einer Vorlesung wurde am Rande die O-Notation eingeführt. Zur
> Lösung von LGS eignet sich die QR-Zerlegung. Dabei wird schrittweise ein
> Element der zu zerlegenden Matrix zu null gesetzt. Demnach müsste die
> Matrix nach [math] \sum_{i =  1}^{n-1} (n - i) /math] Durchläufe in Form
> einer Dreiecksmatrix vorliegen.
> Ein Wikipedia-Eintrag hierzu
> https://de.wikipedia.org/wiki/Givens-Rotation schätzt den Aufwand zu
> O(n^2) ab (n*m Matrix-Matrix Produkte seien zu bilden).
> Ein weiterer Eintrag hierzu
> https://fsi.cs.fau.de/forum/thread/7466-Komplexita... schätzt den
> Aufwand zu O(n^3) ab.
> Meine Frage:
> Was stimmt an meiner Überlegung zur Anzahl an Durchläufen einer QR
> Zerlegung nicht, bzw. wie kommt man zur Angabe O(n^2), bzw. O(n^3)?

Pack das ganze doch mal in eine, für den Leser, lesbare Form...