Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


37. Gaußsches Eliminationsverfahren



Übungen

  1. Geben Sie die Matrix an, die während der Etappe der Vorwärts-Elimination des Gaußschen Eliminationsverfahrens (eliminate) erzeugt wird, wenn dieses zur Lösung des Gleichungssystems x + y + z = 6, 2x + y + 3z = 12, 3x + y + 3z = 14 angewandt wird.
  2. Geben Sie ein System von drei Gleichungen mit drei Unbekannten an, für das die primitive Implementation der Vorwärts-Elimination mit dreifach verschachtelter for-Schleife nicht zum Ziel führt, obwohl eine Lösung existiert.
  3. Wie groß ist der Speicherbedarf für das Gaußsche Eliminationsverfahren im Falle einer NxN-Matrix, in der nur 3N Elemente von null verschieden sind?
  4. Beschreiben Sie, was geschieht, wenn eliminate im Falle einer Matrix angewandt wird, in der eine Zeile nur aus Nullen besteht.
  5. Beschreiben Sie, was geschieht, wenn eliminate und dann substitute im Falle einer Matrix angewandt werden, in der eine Spalte nur aus Nullen besteht.
  6. Wie viele Rechenoperationen werden beim Gauß-Jordanschen Reduktionsverfahren ungefähr ausgeführt?
  7. Welche Auswirkungen ergeben sich für die entsprechenden Gleichungen, wenn wir Spalten in einer Matrix vertauschen?
  8. Wie würden Sie bei der Anwendung von eliminate prüfen, ob einander widersprechende Gleichungen existieren? Oder identische Gleichungen?
  9. Welchen Nutzen hätte das Gaußsche Eliminationsverfahren im Falle eines Systems von M Gleichungen mit N Unbekannten, wenn M < N gilt? Oder wenn M > N gilt?
  10. Geben Sie ein Beispiel an, das die Notwendigkeit des Pivotierens mit Hilfe des größten zur Verfügung stehenden Elements zeigt, wenn ein imaginärer primitiver Computer benutzt wird, in dem Zahlen nur mit zwei signifikanten Ziffern dargestellt werden können (alle Zahlen müssen die Form x, y * 10z haben, mit aus nur einer Ziffer bestehenden ganzen Zahlen x, y und z).


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]