Iterationsverfahren < Nichtlineare Gleich. < Numerik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:56 Do 06.01.2005 | | Autor: | Bastiane |
Hallo!
Ich habe mal eine etwas allgemeinere Frage zu Iterationsverfahren. Und zwar ist mir da nicht ganz klar, wie das Prinzip davon funktioniert. Und somit tue ich mich dann auch mit den einzelnen Verfahren etwas schwer...
Also, allgemein möchte ich doch eine Gleichung des Typs Ax=b lösen. Dafür gibt es dann iterative Verfahren, mit denen man das machen kann. Ist das alles, was diese Verfahren gemeinsam haben? Ich schätze, da gibt's noch mehr, was man allgemein darüber sagen kann. Ob mir das vielleicht jemand kurz erklären könnte?
Viele Grüße
Bastiane
![[breakdance]](/images/smileys/breakdance.gif "[breakdance]")
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 17:59 Do 06.01.2005 | | Autor: | Loddar |
Hallo Bastiane !!
Mir ist irgendwie nicht so ganz klar, worauf du hinaus willst ![[verwirrt]](/images/smileys/verwirrt.gif "[verwirrt]") ...
Möchtest Du zu diesem Thema etwas von der mathematischen Seite wissen oder von der Informatiker-Front (aber da weißt Du ja mehr bescheid als ich!)
In der Mathematik benutzt man Iterationsverfahren, wenn man für gewisse Aufgaben (seien es z.B. Gleichungen oder Integrale) keine explizite Lösung ermitteln kann.
(Dein gewähltes Beispiel mit Ax = B gehört da ja nicht ganz dazu  ).
Dabei ist nähert man sich eine Lösung iterativ, d.h. schrittweise (kommt, wie kann es auch anders sein, aus dem lat.) an. Zusätzlich sollte man sich der gewünschten Lösung auch gezielt nähern.
In den mir bekannten Verfahren (z.B. ![[]](/images/popup.gif) Regula Falsi,  Newton-Verfahren) ist diese Näherung auch rekursiv, d.h. von einem geschätzten Anfangswert [mm] $x_0$ [/mm] wird ein genauerer Wert [mm] $x_1$ [/mm] ermittelt. Nun wird dieses [mm] $x_1$ [/mm] verwendet, um einen weiteren, noch genaueren Wert [mm] $x_2$ [/mm] zu berechnen.
Dies wird dann solange fortgeführt, bis man eine gewünschte Genauigkeit erreicht hat oder tatsächlich den exakten Wert.
Die einzelnen Verfahren unterscheiden sich vom Ansatz bzw. dem Modell her (Regula Falsi = Sekantenverfahren, Newton = Tangentenverfahren).
Ob jetzt für spezielle Aufgaben das eine oder andere Verfahren günstiger ist, entzieht sich meiner Kenntnis.
In der Informatik werden auch Schleifen, sprich: Wiederholungsvorgänge als Iteration bezeichnet.
Etwas Allgemeines zum Thema Iteration findest Du z.B. auch hier oder hier.
Ich hoffe, ich konnte Dir etwas weiterhelfen ....
Für weiter Ergänzungen belasse ich die Frage mal auf "teilweise beantwortet".
Liebe Grüße
Loddar
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 19:13 Do 06.01.2005 | | Autor: | Bastiane |
Hallo Loddar!
> Mir ist irgendwie nicht so ganz klar, worauf du hinaus
> willst ...
Sorry, ich dachte, das wäre klar, weil ich da, kurz nach der Vorlesung, noch irgendwie halbwegs drin war, aber anscheinend habe ich mich nicht verständlich genug ausgedrückt. Aber vielleicht gibt es so etwas auch gar nicht, was ich wissen wollte...
> Möchtest Du zu diesem Thema etwas von der mathematischen
> Seite wissen oder von der Informatiker-Front (aber da weißt
> Du ja mehr bescheid als ich!)
Nein, nur von der mathematischen! 
> In der Mathematik benutzt man Iterationsverfahren, wenn man
> für gewisse Aufgaben (seien es z.B. Gleichungen oder
> Integrale) keine explizite Lösung ermitteln kann.
> (Dein gewähltes Beispiel mit Ax = B gehört da ja nicht
> ganz dazu ).
Also wir hatten jetzt das Gauß-Seidel-Verfahren, das Jacobi-Verfahren, SOR-Verfahren und cg-Verfahren. Sind die nicht ausschließlich zum Lösen von Ax=B da? ![[kopfkratz3]](/images/smileys/kopfkratz3.gif "[kopfkratz3]")
> Dabei ist nähert man sich eine Lösung iterativ, d.h.
> schrittweise (kommt, wie kann es auch anders sein, aus dem
> lat.) an. Zusätzlich sollte man sich der gewünschten Lösung
> auch gezielt nähern.
Danke. Soviel Latein kann ich auch noch!
> In den mir bekannten Verfahren (z.B.
> Regula Falsi,
> Newton-Verfahren) ist diese Näherung auch rekursiv,
> d.h. von einem geschätzten Anfangswert [mm]x_0[/mm] wird ein
> genauerer Wert [mm]x_1[/mm] ermittelt. Nun wird dieses [mm]x_1[/mm]
> verwendet, um einen weiteren, noch genaueren Wert [mm]x_2[/mm] zu
> berechnen.
Heißen die dann auch Iterationsverfahren? ![[haee]](/images/smileys/haee.gif "[haee]")
> Ich hoffe, ich konnte Dir etwas weiterhelfen ....
> Für weiter Ergänzungen belasse ich die Frage mal auf
> "teilweise beantwortet".
Ja, danke Loddar, für den Anfang war das schon mal was. Und da die Frage ja unbefristet ist, kommt bestimmt noch irgendwann mal was dazu.
Viele Grüße
Bastiane
![[hand]](/images/smileys/hand.gif "[hand]")
|
|
|
| |
|
Hallo,
erstmal vielleicht wozu es iterative Verfahren gibt.
In der Mathematik gibt es Aufgabenstellungen, die im Allgemeinen nicht exakt gelöst werden können. Dazu gehören z.B. Fragen nach Nullstellen mit einem Grad höher als vier.
Die Verfahren, die du erwähnt hast, sind doch Verfahren zur Bestimmung von Eigenwerten ?!
Eigenwerte kann man über die Nullstellen des charakteristische Problem lösen, was ja wieder zum Nullstellenproblem führt. Daher versucht man nun also Schritt für Schritt eine bessere Näherung zu erhalten.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 16:14 Fr 07.01.2005 | | Autor: | Bastiane |
Lieber Stefan!
Ja, genau so hatte ich mir das vorgestellt. Das meiste hatte ich zwar doch schon mehrmals gelesen, aber irgendwie habe ich da zu engstirnig reingeguckt, da habe ich mich mehr auf die Umformungen konzentriert als das Prinzip dahinter zu durchschauen!
Vielen Dank, ich denke das müsste helfen!
Viele Grüße
Christiane
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:54 Fr 07.01.2005 | | Autor: | DaMenge |
hi,
denke, dass das zeilensummenkriterium nur eine hinreichende Bedingung für das Konvergieren des Jacobi-Verfahrens ist.
[z.B : unzerlegbare Matrix und schwaches Zeilensummenkriterium oder sassenfels-kriterium]
btw: sorry für das "falsch-stellen" des threads...
(bin neu hier)
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:40 Fr 07.01.2005 | | Autor: | Bastiane |
Hallo DaMenge!
Also, erstmal ![[willkommenmr]](/images/smileys/willkommenmr.png "[willkommenmr]") .
Dann gleich eine Frage: dein Artikel hier war keine Frage, oder? Habe es mal als Mitteilung umgestellt. Und soll ich die Antwort von Stefan wieder auf richtig stellen?
> denke, dass das zeilensummenkriterium nur eine hinreichende
> Bedingung für das Konvergieren des Jacobi-Verfahrens ist.
> [z.B : unzerlegbare Matrix und schwaches
> Zeilensummenkriterium oder sassenfels-kriterium]
>
> btw: sorry für das "falsch-stellen" des threads...
> (bin neu hier)
Außerdem habe ich dann gleich nochmal eine Frage...
1. Ich finde in einem Skript:
Das Iterationsverfahren [mm] x^{k+1}=\Phi(x^k,b) [/mm] mit k=0,1,2,... konvergiert genau dann gegen die Lösung des linearen Gleichungssystems (1) für jeden Startwert [mm] x^0\in\IR^n, [/mm] wenn gilt: [mm] \rho(B)<1.
[/mm]
Ist das jetzt was anderes? Das Jacobi-Verfahren ist doch ein Iterationsverfahren, also müsste dieser Satz doch auch dort gelten, oder?
2. So, wie Stefan mir das Jacobi-Verfahren nochmal erklärt hat, habe ich es auch in meinem Skript stehen und dachte, ich hätte es verstanden. Allerdings finde ich dann hier eine sogenannte Iterationsmatrix [mm] Q=E-D^{-1}A. [/mm] Ich habe dieses Beispiel auf der Seite da mal durchgerechnet, und irgendwie finde ich nicht heraus, wo diese Iterationsmatrix herkommt. Kann mir das jemand sagen?
Viele Grüße
Bastiane
![[cap]](/images/smileys/cap.gif "[cap]")
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 22:12 Fr 07.01.2005 | | Autor: | Paulus |
Liebe Christiane
> Außerdem habe ich dann gleich nochmal eine Frage...
> 1. Ich finde in einem Skript:
> Das Iterationsverfahren [mm]x^{k+1}=\Phi(x^k,b)[/mm] mit
> k=0,1,2,... konvergiert genau dann gegen die Lösung des
> linearen Gleichungssystems (1) für jeden Startwert
> [mm]x^0\in\IR^n,[/mm] wenn gilt: [mm]\rho(B)<1.
[/mm]
>
> Ist das jetzt was anderes? Das Jacobi-Verfahren ist doch
> ein Iterationsverfahren, also müsste dieser Satz doch auch
> dort gelten, oder?
>
Ich denke nicht, dass das etwas anderes ist. Ich weiss allerdings nicht, was denn das B in deinem Skript ist (also wie die Gleichung (1) aussieht).
Hier müsste man einfach beachten, aber das weisst du ja sicher auch, dass die Indizes hochgestellt sind, anstelle des eher gewohnten Tiefstellens.
[mm] $x^k$ [/mm] ist also nicht "x hoch k" im Sinne von Potenzieren, sondern einfach [mm] $x_k$, [/mm] Entsprechendes für k+1.
> 2. So, wie Stefan mir das Jacobi-Verfahren nochmal erklärt
> hat, habe ich es auch in meinem Skript stehen und dachte,
> ich hätte es verstanden. Allerdings finde ich dann
> hier
> eine sogenannte Iterationsmatrix [mm]Q=E-D^{-1}A.[/mm] Ich habe
> dieses Beispiel auf der Seite da mal durchgerechnet, und
> irgendwie finde ich nicht heraus, wo diese Iterationsmatrix
> herkommt. Kann mir das jemand sagen?
Diese Iterationsmatrix ist die Gleiche, wie sie Stefan hergeleitet hat, einfach etwas anders dargestellt.
Man sehe: Stefan hat das so definiert:
$Q = [mm] D^{-1}(L+R)$
[/mm]
Beim Online-Mathelexikon ist es aber so gegeben:
$Q = [mm] E-D^{-1}A$
[/mm]
Ich behaupte also: dass das das Gleiche sei!
Man sehe:
[mm] $D^{-1}(L+R)=E-D^{-1}A$
[/mm]
[mm] $\Leftrightarrow$
[/mm]
[mm] $D^{-1}L+D^{-1}R=E-D^{-1}A$
[/mm]
[mm] $\Leftrightarrow$
[/mm]
[mm] $D^{-1}L+D^{-1}R+D^{-1}A=E$
[/mm]
[mm] $\Leftrightarrow$
[/mm]
[mm] $D^{-1}(L+R+A)=E$
[/mm]
[mm] $\Leftrightarrow$
[/mm]
[mm] $DD^{-1}(L+R+A)=DE$
[/mm]
[mm] $\Leftrightarrow$
[/mm]
$L+R+A=D$
[mm] $\Leftrightarrow$
[/mm]
$A=-L+D-R$
... und Stefan hat ja so begonnen:
$Ax=b [mm] \quad \Leftrightarrow \quad [/mm] (-L+D-R)x=b$
Mit lieben Grüssen
Paul
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 23:01 Fr 07.01.2005 | | Autor: | Bastiane |
Lieber Paul!
> > Außerdem habe ich dann gleich nochmal eine Frage...
> > 1. Ich finde in einem Skript:
> > Das Iterationsverfahren [mm]x^{k+1}=\Phi(x^k,b)[/mm] mit
> > k=0,1,2,... konvergiert genau dann gegen die Lösung des
>
> > linearen Gleichungssystems (1) für jeden Startwert
> > [mm]x^0\in\IR^n,[/mm] wenn gilt: [mm]\rho(B)<1.
[/mm]
> >
> > Ist das jetzt was anderes? Das Jacobi-Verfahren ist doch
>
> > ein Iterationsverfahren, also müsste dieser Satz doch
> auch
> > dort gelten, oder?
> >
>
> Ich denke nicht, dass das etwas anderes ist. Ich weiss
> allerdings nicht, was denn das B in deinem Skript ist (also
> wie die Gleichung (1) aussieht).
Also, ich hab' da jetzt nochmal so einiges gelesen. Aber irgendwie komme ich mit den ganzen unterschiedlichen Formulierungen ganz durcheinander. Machen wir es mal etwas anders:
Das Jacobi-Verfahren konvergiert, falls A strikt diagonaldominant ist - das steht in meinem Skript.
Ist das eine [mm] \gdw [/mm] -Aussage?
Und gibt es dazu noch andere äquivalente Aussagen?
Für das Gauß-Seidel-Verfahren (hier mal gerade noch ne Frage: schreibt sich Gauß mit "ss" oder mit "ß"?) steht im Skript:
... konvergiert, falls die Matrix A symmetrisch positiv definit ist.
Hier die gleichen Fragen:
Ist das eine [mm] \gdw [/mm] -Aussage?
Und gibt es dazu noch andere äquivalente Aussagen?
> > 2. So, wie Stefan mir das Jacobi-Verfahren nochmal
> erklärt
> > hat, habe ich es auch in meinem Skript stehen und dachte,
>
> > ich hätte es verstanden. Allerdings finde ich dann
> >
> hier
>
> > eine sogenannte Iterationsmatrix [mm]Q=E-D^{-1}A.[/mm] Ich habe
>
> > dieses Beispiel auf der Seite da mal durchgerechnet, und
>
> > irgendwie finde ich nicht heraus, wo diese
> Iterationsmatrix
> > herkommt. Kann mir das jemand sagen?
>
> Diese Iterationsmatrix ist die Gleiche, wie sie Stefan
> hergeleitet hat, einfach etwas anders dargestellt.
>
> Man sehe: Stefan hat das so definiert:
>
> [mm]Q = D^{-1}(L+R)[/mm]
>
> Beim Online-Mathelexikon ist es aber so gegeben:
>
> [mm]Q = E-D^{-1}A[/mm]
>
> Ich behaupte also: dass das das Gleiche sei!
>
> Man sehe:
>
> [mm]D^{-1}(L+R)=E-D^{-1}A[/mm]
> [mm]\Leftrightarrow[/mm]
> [mm]D^{-1}L+D^{-1}R=E-D^{-1}A[/mm]
> [mm]\Leftrightarrow[/mm]
> [mm]D^{-1}L+D^{-1}R+D^{-1}A=E[/mm]
> [mm]\Leftrightarrow[/mm]
> [mm]D^{-1}(L+R+A)=E[/mm]
> [mm]\Leftrightarrow[/mm]
> [mm]DD^{-1}(L+R+A)=DE[/mm]
> [mm]\Leftrightarrow[/mm]
> [mm]L+R+A=D[/mm]
> [mm]\Leftrightarrow[/mm]
> [mm]A=-L+D-R[/mm]
>
> ... und Stefan hat ja so begonnen:
>
> [mm]Ax=b \quad \Leftrightarrow \quad (-L+D-R)x=b[/mm]
Danke, genau so etwas hat mir gefehlt!
Viele Grüße
Christiane
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 23:44 Fr 07.01.2005 | | Autor: | DaMenge |
also erstmal:
danke für die begrüßung!
mein Einwand war auf die Antwort von Stefan gedacht, denn er behauptet:
strikt diagonaldominat [mm] \gdw [/mm] $ [mm] \rho(C)<1 [/mm] $
Ich denke hier hat er sich vertan, denn IMHO ist dies nur hinreichend, nicht notwendig (man denke nur an andere quadratische summenkriterien, oder die von mir bereits genannten).
Richtig ist allerdings: Konvergenz [mm] \gdw [/mm] $ [mm] \rho(C)<1 [/mm] $
Dies ist aber tatsächlich etwas anderes !
nun noch zur letzten Frage Gauß-seidel ist doch das Einzelschritt-verfahren, richtig?
Dann folgt aus dem Sassenfeld-Kriterium als hinreichende Bedingung die Konvergenz ! Es ist also nicht notwendig eine spd Matrix zu haben, aber im Deufelhardt (z.B) oder in vielen Vorlesungen wird einfach davon ausgegangen, weil man es dort nur so braucht und obige Äquivalenz wesentlich einfacher zu beweisen ist.
genaueres Sassenfeld-Kriterium:
$ [mm] |a_{ii}|*s_{i} [/mm] := [mm] \summe_{j=1}^{i-1}(|a_{ij}|*s_{j})+ \summe_{j=i+1}^{n}(|a_{ij}|)$
[/mm]
$ 1>s:= max [mm] \{ s_{i} \} [/mm] $
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 00:48 So 09.01.2005 | | Autor: | Stefan |
Hallo DaMenge!
Vielen Dank für den Hinweis, du hast vollkommen recht. Ich habe es verbessert.
Viele Grüße
Stefan
|
|
|
|
