Aufwand des Gauss-Algorithmus

13.04.2017, 16:54

forbin

Aufwand des Gauss-Algorithmus

Hallo,

ich lese mich gerade in den Gauss-Algorithmus ein.
Dort finde ich die Passage:

Zitat:

Der Gesamtaufwand des Algorithmus(nur wesentliche Rechenoperationen, also Multiplikation und Division) für ein LGS mit n Unbekannten beläuft sich auf: $\begin{eqnarray*} Z = \frac{1}{3}n^{3}+n^{2}-\frac{1}{3}n \end{eqnarray*}$ . Dieser steigt mit der dritten Potenz der Zahl der Unbekannte an.

Meine Frage ist:
Wenn ich nun nicht $\begin{eqnarray*} n \end{eqnarray*}$ , sondern $\begin{eqnarray*} (n+l) \end{eqnarray*}$ Unbekannte habe, ist mein Gesamtaufwand doch:
$\begin{eqnarray*} \frac{}{}(n+l)^{3}+(n+l)^{2}-\frac{1}{3}(n+l) = Z + \frac{1}{3}l^{3}+nl^{2}+l^{2}+n^{2}l+2nl-\frac{1}{3}l \end{eqnarray*}$ .

Der Aussage aus dem Buch nach sollte aber doch der "neue" Rechenaufwand $\begin{eqnarray*} Z + (n+l)^{3} \end{eqnarray*}$ sein, oder? verwirrt

13.04.2017, 17:04

mYthos

Auf diesen Beitrag antworten »

Da muss man gar nichts rechnen, diese Information steht schon in der Formel (bei $\begin{eqnarray*} n^3 \end{eqnarray*}$ ).
Aus dieser folgt, dass beispielsweise der Aufwand ungefähr 8 mal so groß wird, wenn sich die Anzahl der Unbekannten verdoppelt.
Die Vergrößerung des Aufwandes erfolgt multiplikativ, nicht additiv.

mY+

13.04.2017, 17:08

forbin

Auf diesen Beitrag antworten »

Super, danke, dass sehe ich ein.
Aber wie kann man das rechnerisch zeigen? Habe es schon über die Ableitung versucht, leider ohne Erfolg...

13.04.2017, 17:39

IfindU

Auf diesen Beitrag antworten »

Du willst zeigen, dass es kubisch anwächst. Bevor du das zeigen kannst, und bevor du sinnvoll überlegen kannst wie du das tun könntest, musst du dir eine Sache bewusst werden: Was bedeutet bei dir "kubisches Wachstum"? Was ist die Definition davon?

13.04.2017, 22:13

forbin

Auf diesen Beitrag antworten »

Zitat:

Original von IfindU
Du willst zeigen, dass es kubisch anwächst. Bevor du das zeigen kannst, und bevor du sinnvoll überlegen kannst wie du das tun könntest, musst du dir eine Sache bewusst werden: Was bedeutet bei dir "kubisches Wachstum"? Was ist die Definition davon?

Sei der Aufwand bei n Unbekannten $\begin{eqnarray*} Z_{n} = z \end{eqnarray*}$ . Dann gilt für $\begin{eqnarray*} a\cdot n \end{eqnarray*}$ Unbekannte: $\begin{eqnarray*} Z_{a\cdot n} = a^{3}\cdot Z_{n} \end{eqnarray*}$

So?

14.04.2017, 08:50

IfindU

Auf diesen Beitrag antworten »

Das ist eine sehr starke Bedingung. Und nicht das was man hier meint. Kubisches Wachstum bedeutet im Allgemeinen das folgende: $\begin{eqnarray*} p_n \end{eqnarray*}$ wächst kubisch in $\begin{eqnarray*} n \end{eqnarray*}$ , falls ein $\begin{eqnarray*} n_0 \end{eqnarray*}$ existiert und $\begin{eqnarray*} c_1, c_2 > 0 \end{eqnarray*}$ so dass $\begin{eqnarray*} c_1 n^3 \leq p_n \leq c_2 n^3 \end{eqnarray*}$ für alle $\begin{eqnarray*} n \geq n_0 \end{eqnarray*}$ .

In Worten: Irgendwann bewegt sich die Funktion $\begin{eqnarray*} n \mapsto p_n \end{eqnarray*}$ zwischen 2 kubischen Funktionen (welche deine Definition erfüllen.)

So ist deine Bedingung äquivalent dazu, dass $\begin{eqnarray*} Z_n = \alpha n^3 \end{eqnarray*}$ gilt. Und das schließt sehr viele Fälle aus, ebenso den der nötigen Operationen des Gauß-Algorithmus. Was einen interessiert ist das Verhalten für $\begin{eqnarray*} n \to \infty \end{eqnarray*}$ , und da interessiert nur der am schnellsten wachsende Summand.

Neue Frage »

Antworten »

Aufwand des Gauss-Algorithmus

Verwandte Themen