Schreibweise Algorithmus < Numerik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Algorithmus der Rückwärtssubstitution:
Seien [mm] U \in \IR^{nxn} [/mm] eine reguläre obere Dreiecksmatrix und [mm] b \in \IR^n [/mm]. Berechne [mm] x \in \IR^n [/mm] durch:
for i = n : -1 : 1; [mm] x_i=(b_i [/mm] - [mm] \summe_{j=i+1}^n u_{ij} x_j) [/mm] / [mm] u_{ii}; [/mm] end |
Hallo!
Ich arbeite gerade mit einem Numerikbuch, das so den Algorithmus für die Rückwärtssubstitution eingeführt hat. Leider ist die Schreibweise nicht erklärt und ich versuche mir das herzuleiten. Nachdem ich ein paar Beispiele gerechnet habe, bin ich auf folgende "Übersetzung" des Ausdrucks "for i=n: -1 : 1 " gekommen:
für i=n,...,1 in (-1)-Schritten
Das heißt, man fängt mit i=n an und arbeitet sich dann in (-1)-Schritten vor bis zu i=1.
Stimmt das so?
Liebe Grüße,
Lily
|
|
| |
|
> Algorithmus der Rückwärtssubstitution:
> Seien [mm]U \in \IR^{nxn}[/mm] eine reguläre obere Dreiecksmatrix
> und [mm]b \in \IR^n [/mm]. Berechne [mm]x \in \IR^n[/mm] durch:
>
> for i = n : -1 : 1; [mm]x_i=(b_i[/mm] - [mm]\summe_{j=i+1}^n u_{ij} x_j)[/mm]
> / [mm]u_{ii};[/mm] end
> Hallo!
>
> Ich arbeite gerade mit einem Numerikbuch, das so den
> Algorithmus für die Rückwärtssubstitution eingeführt
> hat. Leider ist die Schreibweise nicht erklärt und ich
> versuche mir das herzuleiten. Nachdem ich ein paar
> Beispiele gerechnet habe, bin ich auf folgende
> "Übersetzung" des Ausdrucks "for i=n: -1 : 1 " gekommen:
> für i=n,...,1 in (-1)-Schritten
> Das heißt, man fängt mit i=n an und arbeitet sich dann
> in (-1)-Schritten vor bis zu i=1.
>
> Stimmt das so?
>
> Liebe Grüße,
> Lily
Hallo Lily,
falls das in dem Buch tatsächlich so geschrieben wird und auch
keine Erläuterung der absonderlichen Notation gegeben wird,
finde ich das ziemlich schlimm.
Ich kann mir aber auch keinen anderen Reim als du machen
und denke dabei an die (veraltete) Schreibweise aus alten
Versionen von Programmiersprachen wie etwa:
FOR n := (Startwert) STEP (Schrittweite) TO (Endwert) DO (Anweisung)
Mein Vorschlag: Teste die Vermutung mal an einfachen
konkreten Beispielen z.B. mit n=3 !
LG , Al-Chw.
|
|
|
| |
|
Danke für die schnelle Antwort!! 
> > Algorithmus der Rückwärtssubstitution:
> > Seien [mm]U \in \IR^{nxn}[/mm] eine reguläre obere
> Dreiecksmatrix
> > und [mm]b \in \IR^n [/mm]. Berechne [mm]x \in \IR^n[/mm] durch:
> >
> > for i = n : -1 : 1; [mm]x_i=(b_i[/mm] - [mm]\summe_{j=i+1}^n u_{ij} x_j)[/mm]
> > / [mm]u_{ii};[/mm] end
> Hallo Lily,
>
> falls das in dem Buch tatsächlich so geschrieben wird und
> auch
> keine Erläuterung der absonderlichen Notation gegeben
> wird,
> finde ich das ziemlich schlimm.
Ich habe zumindest nichts gefunden :-/
>
> Ich kann mir aber auch keinen anderen Reim als du machen
> und denke dabei an die (veraltete) Schreibweise aus alten
> Versionen von Programmiersprachen wie etwa:
>
> FOR n := (Startwert) STEP (Schrittweite) TO (Endwert)
> DO (Anweisung)
>
> Mein Vorschlag: Teste die Vermutung mal an einfachen
> konkreten Beispielen z.B. mit n=3 !
>
Vielen Dank! Das habe ich gemacht und es scheint zu stimmen. Ich wollte nur mal anfragen, ob das einfach Zufallstreffer waren, oder ob es jemand besser weiß ^^
Im nächsten Schritt wird behauptet, dass im i-ten Schritt n-i viele Multiplikationen und Subtraktionen sowie eine Division durchgeführt werden, und daher sei der Gesamtaufwand: [mm] \summe_{i=1}^n (1+2(n-i)) [/mm]
Auch das wollte ich mir mal konkreter anschauen:
Gegeben sei das LGS:
[mm] \pmat{ a_{11} & a_{12} & a_{13} & | b_1 \\ 0 & a_{22} & a_{23} & | b_2 \\ 0 & 0 & a_{33} & | b_3 }
[/mm]
Dann wäre der 1. Schritt: [mm] x_3= \bruch{b_3}{a_{33}} [/mm]. Dabei wurde 1 Division, 0 Subtraktionen und 0 Multiplikationen durchgeführt.
Das würde mit dem Muster, wie oben beschrieben, nur übereinstimmen, wenn das der 3. (also n-te) Schritt wäre. Na gut, das könnte man sich ja noch so herleiten, dass es ja um die letzte Zeile geht.
Aber dann beim nächsten Schritt klappt es irgendwie gar nicht mehr:
Wir haben [mm] a_{22}x_2 + a_{23}x_3=b_2 \Rightarrow x_2= \bruch{b_2-a_{23}x_3}{a_{22}} [/mm]. Hier hatten wir 1 Division, 1 Subtraktion, 0 Multiplikationen.
Irgendwas stimmt hier nicht. Wo sind meine Überlegungen falsch? :-/
Liebe Grüße, Lily
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 08:25 Do 30.06.2016 | | Autor: | hippias |
> Danke für die schnelle Antwort!!
>
> > > Algorithmus der Rückwärtssubstitution:
> > > Seien [mm]U \in \IR^{nxn}[/mm] eine reguläre obere
> > Dreiecksmatrix
> > > und [mm]b \in \IR^n [/mm]. Berechne [mm]x \in \IR^n[/mm] durch:
> > >
> > > for i = n : -1 : 1; [mm]x_i=(b_i[/mm] - [mm]\summe_{j=i+1}^n u_{ij} x_j)[/mm]
> > > / [mm]u_{ii};[/mm] end
>
> > Hallo Lily,
> >
> > falls das in dem Buch tatsächlich so geschrieben wird und
> > auch
> > keine Erläuterung der absonderlichen Notation gegeben
> > wird,
> > finde ich das ziemlich schlimm.
>
> Ich habe zumindest nichts gefunden :-/
>
> >
> > Ich kann mir aber auch keinen anderen Reim als du machen
> > und denke dabei an die (veraltete) Schreibweise aus
> alten
> > Versionen von Programmiersprachen wie etwa:
> >
> > FOR n := (Startwert) STEP (Schrittweite) TO (Endwert)
> > DO (Anweisung)
> >
> > Mein Vorschlag: Teste die Vermutung mal an einfachen
> > konkreten Beispielen z.B. mit n=3 !
> >
>
> Vielen Dank! Das habe ich gemacht und es scheint zu
> stimmen. Ich wollte nur mal anfragen, ob das einfach
> Zufallstreffer waren, oder ob es jemand besser weiß ^^
>
> Im nächsten Schritt wird behauptet, dass im i-ten Schritt
> n-i viele Multiplikationen und Subtraktionen sowie eine
> Division durchgeführt werden, und daher sei der
> Gesamtaufwand: [mm]\summe_{i=1}^n (1+2(n-i))[/mm]
>
> Auch das wollte ich mir mal konkreter anschauen:
> Gegeben sei das LGS:
> [mm]\pmat{ a_{11} & a_{12} & a_{13} & | b_1 \\ 0 & a_{22} & a_{23} & | b_2 \\ 0 & 0 & a_{33} & | b_3 }[/mm]
>
> Dann wäre der 1. Schritt: [mm]x_3= \bruch{b_3}{a_{33}} [/mm]. Dabei
> wurde 1 Division, 0 Subtraktionen und 0 Multiplikationen
> durchgeführt.
> Das würde mit dem Muster, wie oben beschrieben, nur
> übereinstimmen, wenn das der 3. (also n-te) Schritt wäre.
> Na gut, das könnte man sich ja noch so herleiten, dass es
> ja um die letzte Zeile geht.
> Aber dann beim nächsten Schritt klappt es irgendwie gar
> nicht mehr:
> Wir haben [mm]a_{22}x_2 + a_{23}x_3=b_2 \Rightarrow x_2= \bruch{b_2-a_{23}x_3}{a_{22}} [/mm].
> Hier hatten wir 1 Division, 1 Subtraktion, 0
> Multiplikationen.
Es ist doch wohl 1 Multiplikation, die hier durchgeführt wird.
Ich vermute, dass es sich um eine etwas missverständliche Notation handelt, in dem Sinne, dass $i$ die Zahlen $n$, $n-1$, ... durchläuft in umgekehrter Reihenfolge.
[mm] $\begin{array}{ccccc} \text{Schritt} & i & \text{Multiplikationen} & \text{Subtraktionen} & \text{Divisionen} \\ \hline 1 & 3 & 0 & 0 & 1\\ 2 & 2 & 1 & 1& 1\\ \end{array}$
[/mm]
in Übereinstimmung mit der Formel $n-i$
> Irgendwas stimmt hier nicht. Wo sind meine Überlegungen
> falsch? :-/
>
> Liebe Grüße, Lily
>
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 10:01 Do 30.06.2016 | | Autor: | Mathe-Lily |
Vielen Dank für deine Antwort!
> > Im nächsten Schritt wird behauptet, dass im i-ten Schritt
> > n-i viele Multiplikationen und Subtraktionen sowie eine
> > Division durchgeführt werden, und daher sei der
> > Gesamtaufwand: [mm]\summe_{i=1}^n (1+2(n-i))[/mm]
> >
> > Auch das wollte ich mir mal konkreter anschauen:
> > Gegeben sei das LGS:
> > [mm]\pmat{ a_{11} & a_{12} & a_{13} & | b_1 \\ 0 & a_{22} & a_{23} & | b_2 \\ 0 & 0 & a_{33} & | b_3 }[/mm]
>
> >
> > Dann wäre der 1. Schritt: [mm]x_3= \bruch{b_3}{a_{33}} [/mm]. Dabei
> > wurde 1 Division, 0 Subtraktionen und 0 Multiplikationen
> > durchgeführt.
> > Das würde mit dem Muster, wie oben beschrieben, nur
> > übereinstimmen, wenn das der 3. (also n-te) Schritt wäre.
> > Na gut, das könnte man sich ja noch so herleiten, dass es
> > ja um die letzte Zeile geht.
> > Aber dann beim nächsten Schritt klappt es irgendwie
> gar
> > nicht mehr:
> > Wir haben [mm]a_{22}x_2 + a_{23}x_3=b_2 \Rightarrow x_2= \bruch{b_2-a_{23}x_3}{a_{22}} [/mm].
> > Hier hatten wir 1 Division, 1 Subtraktion, 0
> > Multiplikationen.
> Es ist doch wohl 1 Multiplikation, die hier durchgeführt
> wird.
Achso, ohje, jetzt ist der Groschen gefallen ^^
Ich dachte irgendwie, dass die Umformungen gemeint sind, also:
[mm]a_{22}x_2 + a_{23}x_3=b_2
\gdw a_{22}x_2=b_2 - a_{23}x_3 [/mm] (1 Subtraktion)
[mm] \gdw x_2= \bruch{b_2 - a_{23}x_3}{a_{22}} [/mm] (1 Division)
Aber klar, es sind die Rechnungen im letzten Ausdruck gemeint, und da sind es eine Subtraktion, eine Multiplikation und eine Division ^^
Danke!
|
|
|
|
