arithmetische Operationen < Lin. Gleich.-systeme < Numerik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 10:36 So 19.02.2006 | | Autor: | Britta82 |
| Aufgabe | Numerischer Aufwand des Gaußschen Eliminationsverfahrens
Gegeben sei eine reguläre Matrix A aus [mm] \IC^{nxn} [/mm] für die eine LR-Zerlegung existiert. Zeigen Sie:
a) Das Gaußschen Eliminationsverfahren zur Lösung von Ax=b erfordert [mm] \bruch{2}{3}n^{3}+O(n^{2}) [/mm] Operationen.
b) Die Inverse [mm] A^{-1} [/mm] kann unter Ausnutzung der Beziehung [mm] A^{-1}=(x^{(1)}....x^{(n)}) [/mm] mit maximal [mm] \bruch{8}{3}n^{3}+O(n^{2}) [/mm] Operationen berechnet werden, wobei [mm] x^{(1)}..x^{(n)} [/mm] die Lösungen von [mm] Ax^{(i)}=e^{(i)} [/mm] sind |
Hi,
also ich weiß nicht genau wie ich die Operationen abzählen kann,
zu a) hab ich mir überlegt, daß man ja n Zeilenmultiplikationen mit einem Faktor qi brauch mal n Zeilenadditionen mal n Schritte zum Ausrechnen, also [mm] n^{3}, [/mm] aber woher kommt die [mm] \bruch{2}{3}?
[/mm]
Bei der Inversenberechnung gilt dasselbe, ich weiß nicht wie ich auf den Vorfaktor komme.
Vielen dank für die Hilfe
Freundliche Grüße
Britta
|
|
| |
|
Hallo Britta,
> zu a) hab ich mir überlegt, daß man ja n
> Zeilenmultiplikationen mit einem Faktor qi brauch mal n
> Zeilenadditionen mal n Schritte zum Ausrechnen, also [mm]n^{3},[/mm]
> aber woher kommt die [mm]\bruch{2}{3}?[/mm]
Vom Ansatz her solltest Du beachten das die "Matrix" auf der gerechnet wird immer kleiner wird und dann einen "Gaußschritt" genauer anschauen.
Eine "Zeilenmultiplikation" bedeutet ja n einzelne Multiplikationen.
zu b)
Für die Lösung von LRx=e sind zwei Dreieckssysteme zu lösen.
Lc=e
Rx=c
Also müßtest Du Dir anschauen wieviele Operationen man zum Lösen eines Dreieckssystems benötigt.
viele Grüße
mathemaduenn
|
|
|
|
