LGS < Gleichungssysteme < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Zeigen Sie, daß für ein LGS(n, n) (lineares Gleichungssystem mit n Gleichungen und n Variablen) der Gauß-Jordan-Algorithmus (zur Berechnung von [mm] LGS^\sim [/mm] (n, n)
aus LGS(n, n)) höchstens [mm] \bruch{n^3}{2} [/mm] + [mm] \bruch{n^2}{2} [/mm]
Multiplikationen und Divisionen benötigt. Dabei
sollen Divisionen der Form [mm] \bruch{0}{a} [/mm] und [mm] \bruch{a}{a},a \not= [/mm] 0 und Multiplikationen mit 1 nicht mitgezählt werden.
Hinweis: Bestimmen Sie die Zahl z(k) von Multiplikationen und Divisionen in Iteration
k. Dann bilden Sie [mm] \summe_{k=1}^{n} [/mm] z(k). |
Hallo
Bei dieser Aufgabe, bin ich mir nicht ganz sicher, wie ich auf den Wert von [mm] \bruch{n^3}{2} [/mm] + [mm] \bruch{n^2}{2} [/mm] komme. Der einzige Untersied zwischen dem Gaus und den Gaus-Jordan Algorithmus ist, ist der SChritt, zur Umrechnung der Zeilen. Dies sind nur 2 Operationen mehr. Kann mir einer einen Tip geben?
Vielen Dank
|
|
| |
|
Sieht nach vollständiger Induktion aus.
Prüfe mal für eine 2*2-Matrix, überleg Dir dann, was sich bei einer Größenerweiterung von n*n auf (n+1)*(n+1) an den nötigen Schritten ändert, und mach Dich dann an den Induktionsschluss.
|
|
|
|
