www.vorhilfe.de
Vorhilfe

Kostenlose Kommunikationsplattform für gegenseitige Hilfestellungen.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Vorhilfe
  Status Geisteswiss.
    Status Erdkunde
    Status Geschichte
    Status Jura
    Status Musik/Kunst
    Status Pädagogik
    Status Philosophie
    Status Politik/Wirtschaft
    Status Psychologie
    Status Religion
    Status Sozialwissenschaften
  Status Informatik
    Status Schule
    Status Hochschule
    Status Info-Training
    Status Wettbewerbe
    Status Praxis
    Status Internes IR
  Status Ingenieurwiss.
    Status Bauingenieurwesen
    Status Elektrotechnik
    Status Maschinenbau
    Status Materialwissenschaft
    Status Regelungstechnik
    Status Signaltheorie
    Status Sonstiges
    Status Technik
  Status Mathe
    Status Schulmathe
    Status Hochschulmathe
    Status Mathe-Vorkurse
    Status Mathe-Software
  Status Naturwiss.
    Status Astronomie
    Status Biologie
    Status Chemie
    Status Geowissenschaften
    Status Medizin
    Status Physik
    Status Sport
  Status Sonstiges / Diverses
  Status Sprachen
    Status Deutsch
    Status Englisch
    Status Französisch
    Status Griechisch
    Status Latein
    Status Russisch
    Status Spanisch
    Status Vorkurse
    Status Sonstiges (Sprachen)
  Status Neuerdings
  Status Internes VH
    Status Café VH
    Status Verbesserungen
    Status Benutzerbetreuung
    Status Plenum
    Status Datenbank-Forum
    Status Test-Forum
    Status Fragwürdige Inhalte
    Status VH e.V.

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Dt. Schulen im Ausland: Mathe-Seiten:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Nichtlineare Gleichungen" - Iterationsverfahren
Iterationsverfahren < Nichtlineare Gleich. < Numerik < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Nichtlineare Gleichungen"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Iterationsverfahren: allgemeine Erklärung
Status: (Frage) beantwortet Status 
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]


        
Bezug
Iterationsverfahren: Erklärungsversuch
Status: (Antwort) fertig Status 
Datum: 17:59 Do 06.01.2005
Autor: Loddar

Hallo Bastiane !!

Mir ist irgendwie nicht so ganz klar, worauf du hinaus willst [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. []Regula Falsi, MBNewton-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


Bezug
                
Bezug
Iterationsverfahren: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 19:13 Do 06.01.2005
Autor: Bastiane

Hallo Loddar!
> Mir ist irgendwie nicht so ganz klar, worauf du hinaus
> willst [verwirrt] ...

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]
  

> 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,
> MBNewton-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]

> 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]


Bezug
        
Bezug
Iterationsverfahren: teilweise Erklärungsversuch
Status: (Antwort) fertig Status 
Datum: 20:30 Do 06.01.2005
Autor: marthasmith

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.


Bezug
        
Bezug
Iterationsverfahren: Antwort
Status: (Antwort) fertig Status 
Datum: 21:08 Do 06.01.2005
Autor: Stefan

Liebe Christiane!

Man will also lineare Gleichungssysteme der Form

$Ax=b$

iterativ lösen. Dazu muss man sie zunächst in ein Fixpunktproblem umwandeln.

Die einfachste Möglichkeit das zu tun, ist die folgende:

$Ax=b [mm] \quad \Leftrightarrow \quad [/mm] x = (I-A)x+b$.

Dann kann man eine Iteration mit $C:=I-A$ durchführen (nach dem Vorbild des Banachschen Fixpunktsatzes), falls für den Spektralradius [mm] $\rho(C)$ [/mm] der Iterationsmatrix $C$ gilt: [mm] $\rho(C)<1$. [/mm]

Nun gibt es aber mehrere Möglichkeiten aus dem LGS ein Fixpunktproblem zu machen, und darin unterscheiden sich die Verfahren.

Beispiel Gesamtschrittverfahren:

Schreibe

$Ax=b [mm] \quad \Leftrightarrow \quad [/mm]  (-L+D-R)x=b [mm] \quad \Leftrightarrow \quad [/mm] Dx = Lx+Rx+b [mm] \quad \Leftrightarrow \quad x=D^{-1}(L+R)x [/mm] + [mm] D^{-1}b$. [/mm]

Wir haben also ein Iterationsverfahren

[mm] $x_{k+1} [/mm] = [mm] Cx_{k} [/mm] + c$

mit

[mm] $C:=D^{-1}(L+R)$ [/mm]

und

[mm] $c=D^{-1}b$. [/mm]

Wiederum muss man überprüfen, dass [mm] $\rho(C)<1$ [/mm] gilt. Dies ist, wie mal leicht sieht, genau dann der Fall, wenn das Zeilensummenkriterium erfüllt ist (schau mal in deine Vorlesungsunterlagen). :-)

Beim Einzelschrittverfahren etwa setzt man die bereits berechneten Komponenten in die rechte Seite ein, so dass eine etwas unhandliche Iterationsvorschrift entsteht.

Ich hoffe das Prinzip ist etwas klarer geworden... :-)

Liebe Grüße
Stefan



Bezug
                
Bezug
Iterationsverfahren: Danke.
Status: (Mitteilung) Reaktion unnötig Status 
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
[hand]




Bezug
                
Bezug
Iterationsverfahren: zeilensummenkriterium
Status: (Mitteilung) Reaktion unnötig Status 
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)

Bezug
                        
Bezug
Iterationsverfahren: noch ne Frage
Status: (Frage) beantwortet Status 
Datum: 20:40 Fr 07.01.2005
Autor: Bastiane

Hallo DaMenge!
Also, erstmal [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]



Bezug
                                
Bezug
Iterationsverfahren: Zu 2 und kleine Rückfrage
Status: (Antwort) fertig Status 
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



Bezug
                                        
Bezug
Iterationsverfahren: andere Formulierung und danke
Status: (Mitteilung) Reaktion unnötig Status 
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
[hand]


Bezug
                                                
Bezug
Iterationsverfahren: erläuterungen..
Status: (Antwort) fertig Status 
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] $

Bezug
                        
Bezug
Iterationsverfahren: Richtig
Status: (Mitteilung) Reaktion unnötig Status 
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

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Nichtlineare Gleichungen"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.vorhilfe.de