mikrocontroller.net

Forum: Digitale Signalverarbeitung / DSP Lösung lineares Gleichungssystem (Komplexität)


Autor: Informatik (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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)?

Autor: Heinrich von der Ahle (Gast)
Datum:

Bewertung
1 lesenswert
nicht lesenswert
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...

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.