Aufgaben
Gegeben sei das lineare Gleichungssystem
%%\begin{array}{cccccccc}&-x_1&+&2x_2&=&2\\\ \ &2x_1&-&x_2&=&2\end{array}%%
  1. Löse das System zunächst graphisch.
  2. Eliminiere nun mittels der ersten Gleichung das x1x_1 in der zweiten Gleichung.
  3. Löse das so geänderte System noch einmal graphisch.
  4. Berechne schließlich aus dem geänderten System die Lösung.
Das Lösen eines LGS nach dieser Methode benötigt bei nn Unbekannten etwa n3/3n^3/3 Operationen (Additionen und Multiplikationen). Angenommen, unser Rechner schafft 100100 Millionen Operationen pro Sekunde - wie lange braucht er dann für ein LGS mit 1010, mit 10001000, mit 100 000100\ 000 Unbekannten?

Für diese Aufgabe benötigst Du folgendes Grundwissen: Lineare Gleichungssysteme

Also: Unser Verfahren benötigt
n33op\displaystyle \dfrac{n^3}{3} op
für nn Unbekannte und wir haben einen Rechner, der
100000000ops\displaystyle 100\, 000\, 000 \dfrac{op}{s}
schafft. Also kann die Dauer angegeben werden als:
d(n)=n33op100000000ops=n3300000000s\displaystyle d(n) = \dfrac{\frac{n^3}{3}op}{100\,000\,000 \frac{op}{s}} = \dfrac{n^3}{300\,000\,000}s
Nun setzen wir die angegebenen nn ein:
d(10)=103300000000s=1300000s3,3μs\displaystyle d(10) = \dfrac{10^3}{300\,000\,000}s = \dfrac{1}{300\,000}s \approx 3,3 \mu\text{s}

d(1000)=10003300000000s=103s3,3s\displaystyle d(1\,000) = \dfrac{1000^3}{300\,000\,000}s = \dfrac{10}{3}s \approx 3,3 \text{s}

d(100000)=1000003300000000s3333333,3s39d\displaystyle d(100\,000) = \dfrac{100\,000^3}{300\,000\,000}s \approx 3\,333\,333,3\text{s} \approx 39\text{d}
Während also ein Gleichungssystem mit 1010 Unbekannten im Bruchteil einer Sekunde gelöst werden kann, dauert es für 100000100000 Variablen länger als einen Monat.
Für welche Werte von aa ist folgendes LGS lösbar? Was sind dann die Lösungen?
%%\begin{array}{cccccccc}&x_1&+&2x_2+&x_3&=&2\\\ &x_1&+&4x_2+&3x_3&=&4\\\ &-2x_1&-&3x_2-&x_3&=&a\end{array}%%
Das LGS lässt sich als Matrix aufschreiben und mit dem Gauß-Jordan-Algorithmus vereinfachen.
%%\left(\begin{array}{rrr}1 & 2 & 1 \\1 & 4 & 3 \\-2 & -3 & -1 \\\end{array}\left|\begin{array}{r}2 \\ 4 \\ a\end{array}\right.\right)%%
%%\left(\begin{array}{rrr}1 & 2 & 1 \\0 & 2 & 2 \\0 & 1 & 1 \\\end{array}\left|\begin{array}{r}2 \\ 2 \\ a + 4\end{array}\right.\right)%%
%%\left(\begin{array}{rrr}1 & 2 & 1 \\0 & 1 & 1 \\0 & 0 & 0 \\\end{array}\left|\begin{array}{r}2 \\ a + 4 \\ 2 - 2(a + 4)\end{array}\right.\right)%%
Da die letzte Zeile keine Koeffizienten mehr enthält, gilt 0=22(a+4)0 = 2 - 2(a + 4) bzw. a=3a = -3. Das Gleichungssystem ist also unterdefefiniert und wir können x3x_3 beliebig wählen, z. B. x3=zx_3 = z. Fügen als noch eine neue Zeile ein und setzen a=3a = -3.
%%\left(\begin{array}{rrr}1 & 2 & 1 \\0 & 1 & 1 \\0 & 0 & 1 \\\end{array}\left|\begin{array}{r}2 \\ -3 + 4 \\ z\end{array}\right.\right)%%
%%\left(\begin{array}{rrr}1 & 0 & 0 \\0 & 1 & 0 \\0 & 0 & 1 \\\end{array}\left|\begin{array}{r}z \\ 1 - z \\ z\end{array}\right.\right)%%
Das heißt, es gilt a=3a = -3 sowie x1=zx_1 = z, x2=1zx_2 = 1 - z und x3=zx_3 = z mit zRz \in \mathbb{R}.
Kommentieren Kommentare