matheraum.de
Raum für Mathematik
Offene Informations- und Nachhilfegemeinschaft

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Mathe
  Status Schulmathe
    Status Primarstufe
    Status Mathe Klassen 5-7
    Status Mathe Klassen 8-10
    Status Oberstufenmathe
    Status Mathe-Wettbewerbe
    Status Sonstiges
  Status Hochschulmathe
    Status Uni-Analysis
    Status Uni-Lin. Algebra
    Status Algebra+Zahlentheo.
    Status Diskrete Mathematik
    Status Fachdidaktik
    Status Finanz+Versicherung
    Status Logik+Mengenlehre
    Status Numerik
    Status Uni-Stochastik
    Status Topologie+Geometrie
    Status Uni-Sonstiges
  Status Mathe-Vorkurse
    Status Organisatorisches
    Status Schule
    Status Universität
  Status Mathe-Software
    Status Derive
    Status DynaGeo
    Status FunkyPlot
    Status GeoGebra
    Status LaTeX
    Status Maple
    Status MathCad
    Status Mathematica
    Status Matlab
    Status Maxima
    Status MuPad
    Status Taschenrechner

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

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenUni-NumerikSchreibweise Algorithmus
Foren für weitere Schulfächer findest Du auf www.vorhilfe.de z.B. Informatik • Physik • Technik • Biologie • Chemie
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.matheraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]