a.Op bei Gauß Elimination < Lin. Gleich.-systeme < Numerik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Lemma: Die zur Lösung eines nxn Gleichungssystmes Ax=b mit Hilfe des Gaußschen Eliminationsverfahrens erforderliche Anzahl von arithmetischen Operationen (a.Op) ist [mm] N_{Gauß}(n)=\bruch{n^3}{3}+O(n^2)
[/mm]
Dasselbe gilt für die Bestimmung der Dreieckszerlegung PA=LR
Beweis:
Der k-te Eliminationsschritt [mm] a_{ij}^{(k)}=a_{ij}^{(k-1)}-\bruch{a_{ik}^{(k-1)}}{a_{kk}^{(k-1)}}*a_{kj}^{(k-1)} [/mm] , [mm] b_{i}^{(k)}=b_{i}^{(k-1)}-\bruch{a_{ik}^{(k-1)}}{a_{kk}^{(k-1)}}*b_{k}^{(k-1)}
[/mm]
erfordert n-k Divisionen sowie [mm] (n-k)+(n-k)^{2} [/mm] Multiplikationen und Additionen; also zusammen
[mm] \summe_{k=1}^{n-1}(2(n-k)+(n-k)^{2})=\summe_{k=1}^{n-1}(2l+l^{2})=(n-1)*n+\bruch{(n-1)n(2n-1)}{6}=\bruch{n^{3}}{3}+O(n^{2}) [/mm] a.Op. für die n-1 Schritte der Vorwärtselimination. Damit werden alle Elemente der Zerlegungsmatizen L und R bestimmt. |
Mir ist der Beweis nicht ganz klar, vor allem die Berechnung der Summe. Wie könne da Brüche entstehen?
Folgendes habe ich mir überlegt:
[mm] \summe_{k=1}^{n-1}(2(n-k)+(n-k)^{2})=\summe_{k=1}^{n-1}(2n-2k)+\summe_{k=1}^{n-1}(n^{2}-2nk+k^{2})= (n-1)*2n-2*\summe_{k=1}^{n-1}k+(n-1)*n^{2}-2n*\summe_{k=1}^{n-1}k+\summe_{k=1}^{n-1}k^{2}
[/mm]
[mm] =2*n^{2}-2n+n^{3}-n^{2}-(2+2n)*\summe_{k=1}^{n-1}k+\summe_{k=1}^{n-1}k^{2}
[/mm]
[mm] =n^{3}+n^{2}-2n-(2+2n)*\summe_{k=1}^{n-1}k+\summe_{k=1}^{n-1}k^{2}
[/mm]
Und da komme ich dann endgültig nicht weiter.
Ich habe noch einen anderen Beweis gesehen, wo nur [mm] \summe_{k=1}^{n-1}k^{2}+O(n^{2})=1/3*n^{3}+O(n^{2}) [/mm] stand,
dh. [mm] \summe_{k=1}^{n-1}k^{2}=1/3*n^{3}+O(n^{2}) [/mm]
Mir ist aber auch hier nicht klar wie ich das zeigen kann. Ich habe mir mal ein Zahlenbeispiel überlegt, aber das hat auch nicht richtig geholfen:
(n=5 --> 1+4+9+16=30 und [mm] n^{3}=125 [/mm] und 125/3 [mm] \approx [/mm] 30 aber eben nur sehr ungefähr).
Wie kann ich den mathematisch zeigen, dass das ungefähr stimmen kann. Ich sehe eben auch nicht, wie ich die quadrate rausziehen kann, die ich dann in dem [mm] O(n^{2}) [/mm] verstecken kann.
Über Tipps wäre ich sehr dankbar.
|
|
| |
|
Hallo little-miss-moody,
> Lemma: Die zur Lösung eines nxn Gleichungssystmes Ax=b mit
> Hilfe des Gaußschen Eliminationsverfahrens erforderliche
> Anzahl von arithmetischen Operationen (a.Op) ist
> [mm]N_{Gauß}(n)=\bruch{n^3}{3}+O(n^2)[/mm]
> Dasselbe gilt für die Bestimmung der Dreieckszerlegung
> PA=LR
>
> Beweis:
> Der k-te Eliminationsschritt
> [mm]a_{ij}^{(k)}=a_{ij}^{(k-1)}-\bruch{a_{ik}^{(k-1)}}{a_{kk}^{(k-1)}}*a_{kj}^{(k-1)}[/mm]
> ,
> [mm]b_{i}^{(k)}=b_{i}^{(k-1)}-\bruch{a_{ik}^{(k-1)}}{a_{kk}^{(k-1)}}*b_{k}^{(k-1)}[/mm]
> erfordert n-k Divisionen sowie [mm](n-k)+(n-k)^{2}[/mm]
> Multiplikationen und Additionen; also zusammen
>
> [mm]\summe_{k=1}^{n-1}(2(n-k)+(n-k)^{2})=\summe_{k=1}^{n-1}(2l+l^{2})[/mm] ![[notok]](/images/smileys/notok.gif "[notok]")
Das kann doch nicht sein, du hast an der Summe den Laufindex k, unter der Summe steht was ohne k ...
Hier wird offenbar [mm] $\ell:=n-k$ [/mm] substituiert.
Berechne damit die Grenzen $k=1$ und $k=n-1$ mal in [mm] $\ell$ [/mm] ...
Es sollte dann lauten [mm] $\sum\limits_{\ell=1}^{n-1}2\ell+\ell^2$
[/mm]
Das kannst du auseinander ziehen:
[mm] $=2\sum\limits_{\ell=1}^{n-1}\ell [/mm] \ + \ [mm] \sum\limits_{\ell=1}^{n-1}\ell^2$
[/mm]
Nun suche dir mal die Formel für die Summe der ersten n natürlichen Zahlen und für die Summe der ersten n Quadratzahlen heraus.
Die hattet ihr ganz sicher:
Die erste: [mm] $\sum\limits_{k=1}^{n}k=\frac{n(n+1)}{2}$
[/mm]
Die andere suche selber heraus.
Bedenke, dass du hier nicht über die ersten n (Quadrat-)Zahlen, sondern die ersten n-1 (Quadrat-)Zahlen summierst, passe also die Formeln entsprechend an.
Dann sollte die weitere Rechnung klar werden ..
Schreib's dir einfach mal hin ...
[mm] =(n-1)*n+\bruch{(n-1)n(2n-1)}{6}=\bruch{n^{3}}{3}+O(n^{2})[/mm]
> a.Op. für die n-1 Schritte der Vorwärtselimination. Damit
> werden alle Elemente der Zerlegungsmatizen L und R
> bestimmt.
> Mir ist der Beweis nicht ganz klar, vor allem die
> Berechnung der Summe. Wie könne da Brüche entstehen?
> Folgendes habe ich mir überlegt:
>
> [mm]\summe_{k=1}^{n-1}(2(n-k)+(n-k)^{2})=\summe_{k=1}^{n-1}(2n-2k)+\summe_{k=1}^{n-1}(n^{2}-2nk+k^{2})= (n-1)*2n-2*\summe_{k=1}^{n-1}k+(n-1)*n^{2}-2n*\summe_{k=1}^{n-1}k+\summe_{k=1}^{n-1}k^{2}[/mm]
>
> [mm]=2*n^{2}-2n+n^{3}-n^{2}-(2+2n)*\summe_{k=1}^{n-1}k+\summe_{k=1}^{n-1}k^{2}[/mm]
>
> [mm]=n^{3}+n^{2}-2n-(2+2n)*\summe_{k=1}^{n-1}k+\summe_{k=1}^{n-1}k^{2}[/mm]
>
> Und da komme ich dann endgültig nicht weiter.
> Ich habe noch einen anderen Beweis gesehen, wo nur
> [mm]\summe_{k=1}^{n-1}k^{2}+O(n^{2})=1/3*n^{3}+O(n^{2})[/mm] stand,
> dh. [mm]\summe_{k=1}^{n-1}k^{2}=1/3*n^{3}+O(n^{2})[/mm]
> Mir ist aber auch hier nicht klar wie ich das zeigen kann.
> Ich habe mir mal ein Zahlenbeispiel überlegt, aber das hat
> auch nicht richtig geholfen:
> (n=5 --> 1+4+9+16=30 und [mm]n^{3}=125[/mm] und 125/3 [mm]\approx[/mm] 30
> aber eben nur sehr ungefähr).
> Wie kann ich den mathematisch zeigen, dass das ungefähr
> stimmen kann. Ich sehe eben auch nicht, wie ich die
> quadrate rausziehen kann, die ich dann in dem [mm]O(n^{2})[/mm]
> verstecken kann.
> Über Tipps wäre ich sehr dankbar.
>
>
Gruß
schachuzipus
|
|
|
| |
|
Hi schachuzipus,
das die Summe weiter über k (anstatt über l geht) kam mir auch schon komisch vor. (Da muss unser Dozent wohl einen kleinen Fehler gemacht). Die Formel die du mir aufgeschrieben hast, war mir irgendwie nicht mehr bewusst, aber genau das was ich brauchte. Ich habe nun auch die zweite Formel gefunden:
[mm] \summe_{k=1}^{n}k^{2}=\bruch{n(n+1)(2n+1)}{6}
[/mm]
Damit klärt sich die Aufgabe natürlich.
Vielen Dank nochmal!
|
|
|
|
