Komplexität < Numerik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 13:49 Mo 03.11.2008 | | Autor: | Frisco |
| Aufgabe | Löst man das lineare Gleichungssystem Ax = b (A eine n x n - Matrix) mit
Hilfe des Gaußchen Eliminationsverfahrens, so beträgt die Komplexität (ohne Berucksichtigung von Zeilenvertauschungen)
[mm] \bruch{1}{3}n³+n²-\bruch{1}{3}n [/mm] Mult./Div.
[mm] \bruch{1}{3}n³+\bruch{1}{2}n²-\bruch{5}{6}n [/mm] Add.(Sub. |
Irgednwie komme ich damit nicht zu recht!
Ich habe es über die LR-Zerlegung versucht.
Dazu sei die LR-Zerlegung wie bekannt erklärt!
Sei A [mm] \in \IR^{nxn}
[/mm]
dann gilt
[mm] A=LR=\pmat{ 1 & & 0 & \\ l_{21}& 1& & \\ & & ...\\ & & & 1} \pmat{ a_{11} & a_{12} & ... & a_{1n} \\ & a^{(2)}_{22} & ... & a^{(2)}_{2n} \\ & & ...\\& & & a^{(n)}_{nn}}
[/mm]
anhand dierZerlegung und der speziellen Gestalt von [mm] A_{k} [/mm] sieht man, dass die Matrx-Matrix Multiplikation [mm] A_{k+1}=L_{k}A_{k} [/mm] genau (n-k)² Mult. kostet Dazu kommen ja dann noch n-k Divisionen aus [mm] (L_{k}=I-l_{k}e^{*}_{k}, l_{k}=[0,....0,l_{k+1,k},....,l_{nk}]^{T}
[/mm]
mit [mm] l_{jk}=x_{j}/x_{k} [/mm] für j = k+1,...,n). Somit ergibt die LR-Zerlegung eine Komplexität von
[mm] \summe_{k=1}^{n-1} [/mm] (n-k+1)(n-k) = [mm] \summe_{j=1}^{n-1} (j+1)j=\bruch{1}{3}n³-\bruch{1}{3}n
[/mm]
aber ich komme nicht auf das oben geforderte Ergebnis
kann mir jamdn sagen was ich da falsch mache, bzw. welcher schritt mir noch fehlt
Danke
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:20 Mi 05.11.2008 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
