Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Fragen in der Klausurvorbereitung
Hi,
ich mach mal einen Thread auf für Fragen die beim Lernen auftauchen…
Und ich fang an 
Übung 7, Aufgabe 3: Thomas-Algorithmus:
Also, das was wir da machen ist ja - so wie ich das verstehe - ein Spezialfall, normalerweise ist Thomas-Algorithmus ja für tridiagonale Matrizen wo sich die Werte auf die drei Einträge pro Zeile um die Diagonale beschränken und der Rest 0 ist. Wo der Zusammenhang unserer Übungs-Lösung und dem allgemeinen T-Alg. ist versteh ich nicht wirklich, für mich haben die beiden nicht so richtig viel miteinander zu tun… 
Die Lösung die ich aus einer Übung für diese Aufgabe hab ist erstens ziemlich kurz (und ich frag mich warum das dann 8 Punkte gab) und zweitens versteh ich sie nicht so richtig… Ich hab nämlich als Lösung einfach nur eine Ergebnis-Matrix und drei Zeilen die jeweils angeben wie sich s(i), r(i) und l(i) berechnen.
Ist diese Aufgabe für die Klausur relevant? Wenn ja, dann dieser Spezialfall aus der Übung? Oder das allgemeine Verfahren Thomas-Algorithmus?
Hab auch ne Frage:
Angenommen wir müssen Jacobi oder Gauss-Seidel implementieren.
Was wäre die Abbruchbedingung? Müssten wir den Code für die Berechnung des Residuums mit aufschreiben? Oder reicht es, maxIter mal zu iterieren? Aber dann wissen wir nichts über die Konvergenz. Vielleicht reicht ja auch einfach der “eigentliche” Code, also nur, was das jeweilige Verfahren macht… ?!
Danke,
domoson
Der Thomas Algorithmus ist ziemlich praktisch. In der Uebungsaufgabe waren die Nebendiagonalen versetzt - das geht aber nach dem gleichen Schema auch für Tridiagonale Matrizen (afaik der „eigentliche“ Thomas Algorithmus).
Wenn man mal hinschaut sieht man, dass die LR-Zerlegung mit dem Thomas-Algo (bzw. einer Variante davon) in O(n) läuft und nicht in O(n^3). Auch das Vorwärts- und Rückwärts-Einsetzen dürfte sich sehr ähnlich verhalten. => Spezielle LGS (Ax = b, wobei A tridiagonal) in O(n) lösbar und nicht in O(n^3).
vielleicht kann das noch schnell jemand klären:
Im Lösungszusammentragsthread zur Algo3 Klausur vom 18.09.06 wurde zur Frage welcher Aufwand bei der diskreten Faltung zweier n-elementiger Verktoren zu veranschlagen ist, ein O(n^3) vorgeschlagen und es hat auch keiner widersprochen. Stimmt das? Ich hätte eigentlich an O(n^2) gedacht.
Yup, würd ich auch sagen. Die Leute in dem Thread waren zum Teil eh ein bisschen planlos, hatte ich den Eindruck 
Danke. Dann macht die Welt doch noch Sinn. 