www.vorhilfe.de
Vorhilfe

Kostenlose Kommunikationsplattform für gegenseitige Hilfestellungen.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Englisch
  Status Grammatik
  Status Lektüre
  Status Korrekturlesen
  Status Übersetzung
  Status Sonstiges (Englisch)

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
Weitere Fächer:

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

Schreibweise Algorithmus: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 18:38 Mi 29.06.2016
Autor: Mathe-Lily

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

        
Bezug
Schreibweise Algorithmus: Antwort
Status: (Antwort) fertig Status 
Datum: 19:22 Mi 29.06.2016
Autor: Al-Chwarizmi


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



Bezug
                
Bezug
Schreibweise Algorithmus: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 19:46 Mi 29.06.2016
Autor: Mathe-Lily

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


Bezug
                        
Bezug
Schreibweise Algorithmus: Antwort
Status: (Antwort) fertig Status 
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
>  


Bezug
                                
Bezug
Schreibweise Algorithmus: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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! :-)

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Uni-Numerik"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.englischraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]