Aufwand für Housholder Transformation und LGS lösen berechnen

Question

Aufgabe:

Gegeben ist ein lineares Gleichungssystem Ax = b mit Koeffizientenmatrix A ∈ R^{n x n}, n ∈ ℕ. Ermitteln Sie, wie sich der Aufwand der folgenden Schritte zur Lösung des LGS R * x = Q^T * b nach erfolgter Zerlegung A = Q * R verhält:

1. Berechnung von Q^T * b (Anw. der Householder Transformationen H₁, ..., H_n-1 auf b).

2. Lösung des Gleichungssystems R * x = c mit c = Q^T * b.

3. Gesamtaufwand zur Lösung des LGS R * x = Q^T * b (wenn Q und R bereits vorliegen).

Problem/Ansatz:

Ich hadere etwas mit obiger Aufgabe.

Ist der Gesamtaufwand aus 3. die Summe der Aufwände aus 1. und 2. ? So würde ich es jedenfalls sehen.

Zu 1. würde ich wie folgt rechnen:

c = Q^T * b = H_n-1 * H_n-2 * ... * H₂ * H₁ * b

Für die erste Matrix-Vektor-Multiplikation H₁ * b ergeben sich aus meiner Sicht pro "Zeile" des Vektors n Multiplikationen und n-1 Additionen. Da wir n Zeilen haben wird das ganze nochmals mit n multipliziert.

Ergibt: n * (n + (n - 1)) = 2n² - n   Rechenoperationen

Da wir n-1 Matrix-Vektor-Multiplikationen haben ergibt sich insgesamt für 1. ein Aufwand von (n - 1) * 2n² - n = 2n³ - 3n² + n    Rechenoperationen.

Zu 2.

Das ist ja im Grunde nur Rückwärtsrechnen. Zählt man hier "Einsetzen" als Rechenoperation?

Würde mich freuen, wenn Ihr mir hier helfen könntet.

Grüße
Fehlerteufel