Gesamtschrittverfahren < Lin. Gleich.-systeme < Numerik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 22:20 Mi 02.02.2005 | | Autor: | Deadblow |
Hi,
ich sitze hier vor einer Aufgabe, wo ich absolut keinen Plan habe, wie ich diese lösen soll.
Ich habe schon in meinem Numerik-Buch geguckt, aber über Gesamtschrittverfahren steht da ne halbe Seite...mhmmm...hilft mir garnicht weiter.
Die Aufgabe ist, dass ich aufzeigen soll, dass das Gesamtschrittverfahren zur lösung des linearen Gleichungssystems Au=b mit
A = [mm] \pmat{ 2 & 0 \\ 1 & 3 }, [/mm] b = [mm] \pmat{ 2 \\ 1 } [/mm]
nach 2 Iterationen die exakte Lösung erreicht.
Wäre vielleicht garnicht schlecht, mir vielleicht nur ne Seite sagen, wo dieses ausführlich behandelt wird und ich dann erst mal versuche das alleine zu lösen. Muss das ja irgendwie lernen.
Auch wäre es nicht schlecht, wenn einer ne Ahnung hätte wie ich mit der Methode der kleinsten Quadrate die Formel für die Parameter a und b herleite:
y = ax² + bx (Zwischen 2 Messwerten erwartet man aufgrund bestimmter Überlegungen einen funktionalen Zusammenhang von diesem Typ)
Bei google habe ich ein paar Seiten über diese Methode der kleinsten Quadrate gefunden, aber wirklich verstanden habe ich da nichts.
Ich weiss, dass es sowas bestimmt nicht gibt, aber kennt jemand ne Quelle über Numerik, wo wirklich ausführlich alle Verfahren beschrieben werden, ohne dass man besonders viele Vorkenntnisse hat (u.a. Ausgleichsrechnung und Approximation)? Bin nämlich da noch recht neu auf diesem Gebiet :)
Oder eine sehr gute Buchempfehlung für "dummies"
Danke schon mal im Voraus
Gruss
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
Hallo Deadblow,
Beim Gesamtschritt oder Jacobiverfahren wird die Diagonale der Matrix als Näherung für die Inverse benutzt.
Verfahrensvorschrift für das Gleichungssystem Ax=b ist:
[mm] x_{k+1}=x_k-D^{-1}Ax_k+D^{-1}b
[/mm]
wobei D eben die Diagonale ist also in deinem Fall.
[mm]\pmat{ 2 & 0 \\ 0 & 3 }[/mm]
Alles klar?
Ach ja ![[]](/images/popup.gif) Buchtipp
Zur Methode der kleinsten Quadrate:
Weißt du denn welche Quadrate hier gemeint sind?
gruß
mathemaduenn
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:53 Do 03.02.2005 | | Autor: | Deadblow |
Danke erst mal für deine Antwort :)
Also... habe aufgrund der Aussage, dass es sich ums Jacobi-Verfahren handelt dann doch noch was in meinen Unterlagen gefunden.
Also A = D * (I - L - R) und man soll B=D wählen.
Jetzt habe ich die Formel, wie du sie schon geschrieben hast, also:
[mm] u^{(m+1)} [/mm] = [mm] D^{-1} [/mm] * (DL+DR) * [mm] u^{(m)} [/mm] + [mm] D^{-1}*b
[/mm]
Hast du vielleicht ein Rechenbeispiel ? Was ist hier m und was mache ich dann mit u, mhmm... sehe hier garnicht durch :( Vorallem wie kommen die Iterationen da ins Spiel ?
Hoffe, du verlierst nicht die Geduld mit mir :)
Danke schon mal im Voraus.
P.S.: Habe hier nur stehen: Mit der Methode der kleinsten Quadrate...mhmm keine Ahnung, da habe ich wirklich nichts in meinen Unterlagen.
|
|
|
| |
|
Hallo,
> Hast du vielleicht ein Rechenbeispiel ?
Das Verfahren:
Sei [m]A \in M\left( {n \times n,\IK} \right)[/m]. Also haben wir es mit einer beliebigen quadratischen Matrix zu tun. [m]\det A \ne 0[/m] bedeutet, daß es in dieser Matrix keine Nullzeile oder Nullspalte gibt, wenn man die Matrix z.B. durch das Gauss-Verfahren auf die Dreiecksform bringt. Mit anderen Worten das Gleichungssystem ist eindeutig bestimmt. $b [mm] \in \IK^n$ [/mm] bedeutet, daß wir es hier mit einem Ergebnisvektor mit n Zeilen zu tun haben. Nun sei $A = [mm] L+D+R\!$. $L\!$ [/mm] enthält unterhalb seiner Diagonale irgendwelche Einträge und oberhalb seiner 0-Diagonale ebenfalls nur Nullen. [mm] $D\!$ [/mm] enthält auf seiner Diagonale irgendwelche Einträge und ansonsten überall nur Nullen. [mm] $R\!$ [/mm] enthält oberhalb seiner 0-Diagonale irgendwelche Einträge und ansonsten nur Nullen.
Nun betrachten wir ein Gleichungssystem mit $x [mm] \in \IK^n: [/mm] Ax = b$. [mm] $b\!$ [/mm] und [mm] $A\!$ [/mm] sind uns bekannt. Wir wollen [mm] $x\!$ [/mm] bestimmen. Wir setzen [mm] $L+D+R\!$ [/mm] ein:
[m]\left( {L + D + R} \right)x = b \Leftrightarrow Lx + Dx + Rx = b \Leftrightarrow Lx + Rx + Dx = b \Leftrightarrow \left( {L + R} \right)x + Dx = b[/m]. Wir multiplizieren auf beiden Seiten mit der Inversen von D:
[m]\left( {L + R} \right)x + Dx = b \Leftrightarrow D^{ - 1} \left( {L + R} \right)x + x = D^{ - 1} b \Leftrightarrow x = D^{ - 1} b - D^{ - 1} \left( {L + R} \right)x = - D^{ - 1} \left( {L + R} \right)x + D^{ - 1} b[/m].
Damit kriegen wir eine Gleichung, anhand der wir ein Iterationsverfahren (nämlich das Gesamtschrittverfahren) aufstellen, indem wir einen anfänglichen beliebigen Wert für [mm] $x\!$ [/mm] in die rechte Seite der Gleichung einsetzen. Den Wert, den wir erhalten, setzen wir wieder in die rechte Seite der Gleichung ein. u.s.w. .
[mm] $x_{i + 1} [/mm] = - [mm] D^{ - 1} \left( {L + R} \right)x_i [/mm] + [mm] D^{ - 1} [/mm] b$
Damit sollten wir irgendwann einen hinreichend guten Näherungswert für [mm] $x\!$ [/mm] erhalten.
Das Konvergenzkriterium für unser Verfahren:
Jedes Näherungsverfahren besitzt Bedingungen unter denen es dir ganz schnell, ganz langsam oder überhaupt keine Näherungslösung liefert. Beim Gesamtschrittverfahren handelt es sich dabei um das starke Spalten- oder Zeilensummenkriterium:
Sei $A = [mm] \left( {a_{ij} } \right)$. [/mm] Dann lautet das starke Zeilensummenkriterium:
[m]\sum\limits_{\begin{subarray}{l}
j = 1 \\
j \ne i
\end{subarray}} ^{n} {\frac{{\left| {a_{ij} } \right|}}
{{\left| {a_{ii} } \right|}}} < 1,\,i = 1,2, \ldots ,n[/m]
und das starke Spaltensummenkriterium:
[m]\sum\limits_{\begin{subarray}{l}
i = 1 \\
i \ne j
\end{subarray}} ^{n} {\frac{{\left| {a_{ij} } \right|}}
{{\left| {a_{jj} } \right|}}} < 1,\,j = 1,2, \ldots ,n[/m]
Ein Beispiel:
Seien
[m]A: = \left( {\begin{array}{*{20}c}
{ - 6} & 3 & { - 2} \\
4 & 9 & 4 \\
2 & 5 & 8 \\
\end{array} } \right)[/m]
und
[m]b: = \left( {\begin{array}{*{20}c}
5 \\
3 \\
2 \\
\end{array} } \right)[/m]
Also insgesamt folgendes System:
[m]\left( {\begin{array}{*{20}c}
{ - 6} & 3 & { - 2} \\
4 & 9 & 4 \\
2 & 5 & 8 \\
\end{array} } \right)\left( {\begin{array}{*{20}c}
{x_1 } \\
{x_2 } \\
{x_3 } \\
\end{array} } \right) = \left( {\begin{array}{*{20}c}
5 \\
3 \\
2 \\
\end{array} } \right)[/m].
Dann lautet das Zeilensummenkriterium für die einzelnen Zeilen:
[m]\begin{gathered}
i = 1:\quad \frac{{\left| {a_{12} } \right|}}
{{\left| {a_{11} } \right|}} + \frac{{\left| {a_{13} } \right|}}
{{\left| {a_{11} } \right|}} = \frac{3}
{6} + \frac{2}
{6} = \frac{5}
{6} < 1 \hfill \\
i = 2:\quad \frac{{\left| {a_{21} } \right|}}
{{\left| {a_{22} } \right|}} + \frac{{\left| {a_{23} } \right|}}
{{\left| {a_{22} } \right|}} = \frac{4}
{9} + \frac{4}
{9} = \frac{8}
{9} < 1 \hfill \\
i = 3:\quad \frac{{\left| {a_{31} } \right|}}
{{\left| {a_{33} } \right|}} + \frac{{\left| {a_{32} } \right|}}
{{\left| {a_{33} } \right|}} = \frac{2}
{8} + \frac{5}
{8} = \frac{7}
{8} < 1 \hfill \\
\end{gathered}[/m]
Wir können das Verfahren demnach verwenden. Die Zerlegung lautet:
[m]A = \overbrace {\pmat{
0 & 0 & 0 \\
4 & 0 & 0 \\
2 & 5 & 0 \\
}}^{L} + \overbrace {\left( {\begin{array}{*{20}c}
{ - 6} & 0 & 0 \\
0 & 9 & 0 \\
0 & 0 & 8 \\
\end{array} } \right)}^{D} + \overbrace {\left( {\begin{array}{*{20}c}
0 & 3 & { - 2} \\
0 & 0 & 4 \\
0 & 0 & 0 \\
\end{array} } \right)}^{R}[/m]
mit
[m]L + R = \left( {\begin{array}{*{20}c}
0 & 0 & 0 \\
4 & 0 & 0 \\
2 & 5 & 0 \\
\end{array} } \right) + \left( {\begin{array}{*{20}c}
0 & 3 & { - 2} \\
0 & 0 & 4 \\
0 & 0 & 0 \\
\end{array} } \right) = \left( {\begin{array}{*{20}c}
0 & 3 & { - 2} \\
4 & 0 & 4 \\
2 & 5 & 0 \\
\end{array} } \right)[/m]
Die Inverse zu [mm] $D\!$ [/mm] ist in diesem Fall sehr einfach zu berechnen, indem wir für alle Einträge entlang der Diagonale den Kehrwert nehmen:
[m]D^{ - 1} = \left( {\begin{array}{*{20}c}
{ - \tfrac{1}
{6}} & 0 & 0 \\
0 & {\tfrac{1}
{9}} & 0 \\
0 & 0 & {\tfrac{1}
{8}} \\
\end{array} } \right)[/m]
Jetzt müssen wir alles ausmultiplizieren. Zum Glück ist das hier wegen der vielen Nullen einfach:
[m] - D^{ - 1} \left( {L + R} \right) = \left( {\begin{array}{*{20}c}
{\tfrac{1}
{6}} & 0 & 0 \\
0 & { - \tfrac{1}
{9}} & 0 \\
0 & 0 & { - \tfrac{1}
{8}} \\
\end{array} } \right)\left( {\begin{array}{*{20}c}
0 & 3 & { - 2} \\
4 & 0 & 4 \\
2 & 5 & 0 \\
\end{array} } \right) = \left( {\begin{array}{*{20}c}
0 & {\tfrac{1}
{2}} & { - \tfrac{1}
{3}} \\
{ - \tfrac{4}
{9}} & 0 & { - \tfrac{4}
{9}} \\
{ - \tfrac{1}
{4}} & { - \tfrac{5}
{8}} & 0 \\
\end{array} } \right)[/m]
Jetzt berechnen wir noch:
[m]D^{ - 1} b = \left( {\begin{array}{*{20}c}
{ - \tfrac{1}
{6}} & 0 & 0 \\
0 & {\tfrac{1}
{9}} & 0 \\
0 & 0 & {\tfrac{1}
{8}} \\
\end{array} } \right)\left( {\begin{array}{*{20}c}
5 \\
3 \\
2 \\
\end{array} } \right) = \left( {\begin{array}{*{20}c}
{ - \tfrac{5}
{6}} \\
{\tfrac{1}
{3}} \\
{\tfrac{1}
{4}} \\
\end{array} } \right)[/m]
Damit hätten wir fast alles. Jetzt noch eine letzte Multiplikation:
[m] - D^{ - 1} \left( {L + R} \right)x_i = \left( {\begin{array}{*{20}c}
0 & {\tfrac{1}
{2}} & { - \tfrac{1}
{3}} \\
{ - \tfrac{4}
{9}} & 0 & { - \tfrac{4}
{9}} \\
{ - \tfrac{1}
{4}} & { - \tfrac{5}
{8}} & 0 \\
\end{array} } \right)\left( {\begin{array}{*{20}c}
{x_{1_i } } \\
{x_{2_i } } \\
{x_{3_i } } \\
\end{array} } \right) = \left( {\begin{array}{*{20}c}
{\tfrac{{x_{2_i } }}
{2} - \tfrac{{x_{3_i } }}
{3}} \\
{ - \tfrac{4}
{9}x_{1_i } - \tfrac{4}
{9}x_{3_i } } \\
{ - \tfrac{{x_{1_i } }}
{4} - \tfrac{5}
{8}x_{2_i } } \\
\end{array} } \right)[/m]
und jetzt addieren wir [mm] $D^{-1}b$ [/mm] hinzu:
[m] - D^{ - 1} \left( {L + R} \right)x_i + D^{ - 1} b = \left( {\begin{array}{*{20}c}
{\tfrac{{x_{2_i } }}
{2} - \tfrac{{x_{3_i } }}
{3} - \tfrac{5}
{6}} \\
{ - \tfrac{4}
{9}\left( {x_{1_i } + x_{3_i } } \right) + \tfrac{1}
{3}} \\
{ - \tfrac{{x_{1_i } }}
{4} - \tfrac{5}
{8}x_{2_i } + \tfrac{1}
{4}} \\
\end{array} } \right)[/m]
Damit kriegen wir unsere Rekursionsformel. Jetzt wollen wir wissen, ob die Formel erwartungsgemäß funktioniert. Wir starten mit:
[m]x_0 : = \left( {\begin{array}{*{20}c}
0 \\
0 \\
0 \\
\end{array} } \right)[/m]
Dann:
[m]x_1 : = \left( {\begin{array}{*{20}c}
{\tfrac{0}
{2} - \tfrac{0}
{3} - \tfrac{5}
{6}} \\
{ - \tfrac{4}
{9}\left( {0 + 0} \right) + \tfrac{1}
{3}} \\
{ - \tfrac{0}
{4} - \tfrac{5}
{8}*0 + \tfrac{1}
{4}} \\
\end{array} } \right) = \left( {\begin{array}{*{20}c}
{ - \tfrac{5}
{6}} \\
{\tfrac{1}
{3}} \\
{\tfrac{1}
{4}} \\
\end{array} } \right)[/m]
und nochmal:
[m] x_2 : = \left( {\begin{array}{*{20}c}
{\tfrac{{\left( {\tfrac{1}
{3}} \right)}}
{2} - \tfrac{{\left( {\tfrac{1}
{4}} \right)}}
{3} - \tfrac{5}
{6}} \\
{ - \tfrac{4}
{9}\left( { - \tfrac{5}
{6} + \tfrac{1}
{4}} \right) + \tfrac{1}
{3}} \\
{ - \tfrac{{\left( { - \tfrac{5}
{6}} \right)}}
{4} - \tfrac{5}
{8}*\tfrac{1}
{3} + \tfrac{1}
{4}} \\
\end{array} } \right) = \left( {\begin{array}{*{20}c}
{\tfrac{2}
{{12}} - \tfrac{1}
{{12}} - \tfrac{{10}}
{{12}}} \\
{\tfrac{4}
{9}*\tfrac{7}
{{12}} + \tfrac{3}
{9}} \\
{\tfrac{5}
{{24}} - \tfrac{5}
{{24}} + \tfrac{1}
{4}} \\
\end{array} } \right) = \left( {\begin{array}{*{20}c}
{ - \tfrac{3}
{4}} \\
{\tfrac{{16}}
{{27}}} \\
{\tfrac{1}
{4}} \\
\end{array} } \right)[/m]
[m] x_3 : = \left( {\begin{array}{*{20}c}
{\tfrac{{\tfrac{{16}}
{{27}}}}
{2} - \tfrac{{\tfrac{1}
{4}}}
{3} - \tfrac{5}
{6}} \\
{ - \tfrac{4}
{9}\left( { - \tfrac{3}
{4} + \tfrac{1}
{4}} \right) + \tfrac{1}
{3}} \\
{ - \tfrac{{ - \tfrac{3}
{4}}}
{4} - \tfrac{5}
{8}*\tfrac{{16}}
{{27}} + \tfrac{1}
{4}} \\
\end{array} } \right) = \left( {\begin{array}{*{20}c}
{\tfrac{{16}}
{{54}} - \tfrac{1}
{{12}} - \tfrac{5}
{6}} \\
{\tfrac{4}
{9}*\tfrac{1}
{2} + \tfrac{1}
{3}} \\
{\tfrac{3}
{{16}} - \tfrac{{10}}
{{27}} + \tfrac{1}
{4}} \\
\end{array} } \right) = \left( {\begin{array}{*{20}c}
{ - \tfrac{{67}}
{{108}}} \\
{\tfrac{5}
{9}} \\
{\tfrac{{29}}
{{432}}} \\
\end{array} } \right)[/m]
[m] x_4 : = \left( {\begin{array}{*{20}c}
{\tfrac{{\tfrac{5}
{9}}}
{2} - \tfrac{{\tfrac{{29}}
{{432}}}}
{3} - \tfrac{5}
{6}} \\
{ - \tfrac{4}
{9}\left( { - \tfrac{{67}}
{{108}} + \tfrac{{29}}
{{432}}} \right) + \tfrac{1}
{3}} \\
{ - \tfrac{{ - \tfrac{{67}}
{{108}}}}
{4} - \tfrac{5}
{8}*\tfrac{5}
{9} + \tfrac{1}
{4}} \\
\end{array} } \right) = \left( {\begin{array}{*{20}c}
{ - \tfrac{{749}}
{{1296}}} \\
{\tfrac{{563}}
{{972}}} \\
{\tfrac{{25}}
{{432}}} \\
\end{array} } \right) \doteq \left( {\begin{array}{*{20}c}
{ - 0.5779320987} \\
{0.5792181069} \\
{0.05787037037} \\
\end{array} } \right)[/m]
[m] x_5 : = \left( {\begin{array}{*{20}c}
{ - \tfrac{{2189}}
{{3888}}} \\
{\tfrac{{823}}
{{1458}}} \\
{\tfrac{{505}}
{{15552}}} \\
\end{array} } \right) \doteq \left( {\begin{array}{*{20}c}
{ - 0.5630144032} \\
{0.5644718792} \\
{0.03247170781} \\
\end{array} } \right) [/m]
[m] x_6 : = \left( {\begin{array}{*{20}c}
{ - \tfrac{{971}}
{{1728}}} \\
{\tfrac{{19915}}
{{34992}}} \\
{\tfrac{{1771}}
{{46656}}} \\
\end{array} } \right) \doteq \left( {\begin{array}{*{20}c}
{ - 0.5619212962} \\
{0.5691300868} \\
{0.03795867626} \\
\end{array} } \right)[/m]
[m] x_7 : = \left( {\begin{array}{*{20}c}
{ - \tfrac{{78581}}
{{139968}}} \\
{\tfrac{{29719}}
{{52488}}} \\
{\tfrac{{19469}}
{{559872}}} \\
\end{array} } \right) \doteq \left( {\begin{array}{*{20}c}
{ - 0.5614211819} \\
{0.5662056089} \\
{0.03477401977} \\
\end{array} } \right) [/m]
[m] x_8 : = \left( {\begin{array}{*{20}c}
{ - \tfrac{{943645}}
{{1679616}}} \\
{\tfrac{{238253}}
{{419904}}} \\
{\tfrac{{61267}}
{{1679616}}} \\
\end{array} } \right) \doteq \left( {\begin{array}{*{20}c}
{ - 0.5618218688} \\
{0.5673987387} \\
{0.03647678993} \\
\end{array} } \right)
[/m]
Der genaue Wert auf 10 Stellen gerundet lautet übrigens:
[m]x_\text{genau} = \left( {\begin{array}{*{20}c}
{ - \tfrac{{109}}
{{194}}} \\
{\tfrac{{55}}
{{97}}} \\
{\tfrac{7}
{{194}}} \\
\end{array} } \right) \approx \left( {\begin{array}{*{20}c}
{ - 0.5618556701} \\
{0.5670103092} \\
{0.03608247422} \\
\end{array} } \right)[/m]
Viele Grüße
Karl
|
|
|
|
