Algorithmen: Mathematik: Unterschied zwischen den Versionen

Aus SibiWiki
Zur Navigation springen Zur Suche springen
 
(15 dazwischenliegende Versionen desselben Benutzers werden nicht angezeigt)
Zeile 27: Zeile 27:
Von der Stichprobe (d.h. allen Simulationsergebnissen) ermittelt man folgende Werte:
Von der Stichprobe (d.h. allen Simulationsergebnissen) ermittelt man folgende Werte:
* Den '''Mittelwert''': <math> \overline x = \frac{1}{n} \sum_{i=1}^n{x_i}</math>  
* Den '''Mittelwert''': <math> \overline x = \frac{1}{n} \sum_{i=1}^n{x_i}</math>  
* Die (korrigierte) '''Standardabweichung''': <math>s= \sqrt{\frac{1}{n-1} \sum \limits_{i=1}^n\left(x_i-\overline x\right)^2} </math>
* Die '''Standardabweichung der Stichprobie''': <math>s= \sqrt{\frac{1}{n-1} \sum \limits_{i=1}^n\left(x_i-\overline x\right)^2} </math>


Jetzt gilt (lt. Mathematik...):
Jetzt gilt (lt. Mathematik...):
* Mit 95% Sicherheit liegt das echte Ergebnis im Intervall <math>[\overline x - 1,96 \cdot{s} ~ | ~ \overline x + 1,96 \cdot{s} ] </math>.
* Mit 95% Sicherheit liegt der <u>Mittelwert der Grundgesamtheit</u> im Intervall <math>[\overline x - 1,96 \cdot {\frac{s}{\sqrt{n}}} ~ | ~ \overline x + 1,96 \cdot {\frac{s}{\sqrt{n}}} ] </math>.
* Mit 99% Sicherheit liegt das echte Ergebnis im Intervall <math>[\overline x - 2,58 \cdot{s} ~ | ~ \overline x + 2,58 \cdot{s} ] </math>.
* Mit 99% Sicherheit liegt der <u>Mittelwert der Grundgesamtheit</u> im Intervall <math>[\overline x - 2,58 \cdot {\frac{s}{\sqrt{n}}} ~ | ~ \overline x + 2,58 \cdot {\frac{s}{\sqrt{n}}} ] </math>.
 
==Sonderfall: Bernoulli-Versuche==
Bei Bernoulli-Versuchen (d.h. Versuchen, für die es als Ergebnis nur "0" oder "1" gibt), ist die Ermittlung von Mittelwert und Standardabweichung sehr einfach, denn die Ergebnisse von Bernoulli-Ketten sind "binominalverteilt". Deswegen kann man Mittelwert und Standardabweichung wie folgt berechnen:
 
* '''Mittelwert''': <math> \overline x = p </math>
* (korrigierte) '''Standardabweichung''': <math> s = \sqrt{\frac{p \cdot (1-p)}{n-1}}</math>


=Beispiel: Ermittlung von PI =
=Beispiel: Ermittlung von PI =
Zeile 47: Zeile 41:


* '''Mittelwert''': <math> \overline x = 0,7851 </math>
* '''Mittelwert''': <math> \overline x = 0,7851 </math>
* (korrigierte) '''Standardabweichung''': <math> s = \sqrt{\frac{0,7851 \cdot (1-0,7851)}{n-1}} = 0,0041</math>
* '''Standardabweichung der Stichprobe''': <math> s = \sqrt{\frac{ {{7851}\cdot{(1 - 0,7851)^2}} + {2149} \cdot {(0 - 0,7851)^2}}{9999}} = 0,411</math>


Bestimmung des Konfidenzinterfalls für eine Wahrscheinlichkeit von 99%:
Bestimmung des Konfidenzinterfalls für eine Wahrscheinlichkeit von 99%:


* <math>[\overline x - 2,58 \cdot{s} ~ | ~ \overline x + 2,58 \cdot{s} ] ~ = ~</math><br/><br/><math>[0,7851 - 2,58 \cdot{0,041} ~ | ~ 0,7851 + 2,58 \cdot{0,041} ]~ = ~</math><br/><br/><math>[0,7745 ~ | ~ 0,7957]</math>
* <math>[\overline x - 2,58 \cdot {\frac{s}{\sqrt{n}}} ~ | ~ \overline x + 2,58 \cdot {\frac{s}{\sqrt{n}}} ] ~ = ~</math><br/><br/><math>[0,7851 - 2,58 \cdot{0,00411} ~ | ~ 0,7851 + 2,58 \cdot{0,00411} ]~ = ~</math><br/><br/><math>[0,7745 ~ | ~ 0,7957]</math>


Da man diese Simulation nur für einen Viertelkreis gemacht hat, muss man das Intervall noch mit 4 multiplizieren, um ein Konfidenzintervall für Pi zu erhalten:
Da man diese Simulation nur für einen Viertelkreis gemacht hat, muss man das Intervall noch mit 4 multiplizieren, um ein Konfidenzintervall für Pi zu erhalten:
Zeile 57: Zeile 51:
Mit 99% Wahrscheinlichkeit liegt Pi im Intervall
Mit 99% Wahrscheinlichkeit liegt Pi im Intervall


<math>[4 \cdot 0,7745 ~|~ 4 \cdot 0,7957]~=</math> <br/><math>[3,098 ~|~ 3,1828]</math>
<math>[4 \cdot 0,7745 ~|~ 4 \cdot 0,7957]~=</math> <br/><math>[3,0980 ~|~ 3,1828]</math>
 
=Excel: Mittelwert und Standardabweichung berechnen=
* Die Daten in Spalte A packen.
** Wichtig: Zahlen mit Kommas!
* Folgende Formeln z.B. in die Felder <code>C1</code> bis <code>C5</code> eintragen:
** '''C1: '''<code>=ANZAHL(A:A)</code>
** '''C2: '''<code>=MITTELWERT(A:A)</code>
** '''C3: '''<code>=STABW.S(A:A)</code>
** '''C4: '''<code>=C2-2,58*C3/WURZEL(C1)</code>&nbsp;&nbsp;''Berechnet die untere Grenze des 99%-Konfidenzintervalls.''
** '''C5: '''<code>=C2+2,58*C3/WURZEL(C1)</code>&nbsp;&nbsp;''Berechnet die obere Grenze des 99%-Konfidenzintervalls.'
 
=Java: Mittelwert und Standardabweichung berechnen=
Hier ist eine Klasse <code>Statistik</code>, mit der man Mittelwert und Standardabweichung einer Stichprobe berechnen kann.
 
<code>
'''public class Statistik''' {
   
  '''public double mittelwert(double[] werte)''' {
      double anzahl = werte.length;
      double summe = 0;
      for (int i = 0; i < werte.length; i++) {
        summe += werte[i];
      }
      return 1.0*summe / anzahl;
  }
 
  '''public double standardAbweichungStichprobe(double[] werte)''' {
      int anzahl = werte.length;
      double mittelwert = mittelwert(werte);
        double summeAbweichungZumQuadrat = 0.0;
        for(int i=0; i<werte.length; i++) {
            double wert = werte[i];
            summeAbweichungZumQuadrat += Math.pow(wert - mittelwert, 2);
        }
        double standardAbweichung = Math.sqrt(summeAbweichungZumQuadrat/(anzahl-1));
        return standardAbweichung;
  }
   
  // zu Testzwecken
  '''public static void main(String[] args)''' {
      Statistik st = new Statistik();
      double[] stichprobe = { 35, 48, 60, 71, 80, 95, 130};
      double mittelwert = st.mittelwert(stichprobe);
      double standardAbweichungStichprobe = st.standardAbweichungStichprobe(stichprobe);
      System.out.println("Mittelwert: "+ mittelwert);
      System.out.println("Standardabweichung: "+standardAbweichungStichprobe);
  }
}
</code>
 
 
=Python: Mittelwert und Standardabweichung berechnen=
Um in Python den Mittelwert und die Standardabweichung zu berechnen, greift man am besten auf Funktionen der Bibliothek '''numpy''' zurück. (Natürlich könnte man das auch von Hand implementieren, aber das ist fehleranfälliger.)
 
Das folgende Beispielprogramm zeigt, wie man das macht.<br/>Das Beispielprogramm kann man Copy&Paste in IDLE übernehmen.
 
<code>
'''import numpy as np'''
 
'''def mittelwert(x):'''
    return np.mean(x)
'''def standardabweichung(x):'''
    return np.std(x,ddof=1)
    # damit man die Standardabweichung der ''Stichprobe''
    # und nicht der ''Gesamtheit'' berechnet,
    # muss man als zusätzliches Argument ''ddof=1'' übergeben.
#main
x = [3.4,3.2,3.5,4.1,3.2]
mi = mittelwert(x)
std = standardabweichung(x)
print(x)
print("Mittelwert", mi)
print("Standardabweichung",std)
</code>

Aktuelle Version vom 1. Dezember 2022, 18:19 Uhr

Im Wesentlichen werden bei Algorithmen zwei Aspekte mathematisch geprüft:

  1. Laufzeit: siehe Laufzeit_von_Algorithmen
  2. Genauigkeit (oder Zuverlässigkeit)

Auf dieser Seite wird die Prüfung der Genauigkeit (oder Zuverlässigkeit) für sogenannte Monte-Carlo-Algorithmen dargestellt. Monte-Carlo-Algorithmen braucht man zur Simulation; sie beruhen auf Zufall.


Prüfung der Zuverlässigkeit: Konfidenzintervall und Wahrscheinlichkeit

Bei Simulationen lässt man einen Prozess 1000mal (oder öfter) laufen, und erhält entsprechend viele Ergebnisse.

Aus den Ergebnissen der Simulation kann man den Mittelwert bilden und erhält so eine Voraussage auf das tatsächliche Verhalten.

Daran schließt sich die Frage an: Wie genau ist diese Voraussage?

Eine 100prozentig genaue Voraussage wird man mit einer Simulation nie erreichen; stattdessen gibt man ein Konfidenzintervall und eine Wahrscheinlichkeit an, z.B.:

Mit einer Wahrscheinlichkeit von 99% ist das tatsächliche Ergebnis im Intervall [0,7745 | 0,7957].

Ermittlung des Konfidenzintervalls mithilfe von Mittelwert und Standardabweichung

Ergebnisse von Simulationen sind in der Regel normalverteilt, weil die einzelnen Durchläufe der Simulationen voneinander unabhängig sind.

D.h. die Ergebnisse der Simulation können als Stichprobe angesehen werden, von der man auf die Gesamtheit schließt.

Von der Stichprobe (d.h. allen Simulationsergebnissen) ermittelt man folgende Werte:

  • Den Mittelwert: [math]\displaystyle{ \overline x = \frac{1}{n} \sum_{i=1}^n{x_i} }[/math]
  • Die Standardabweichung der Stichprobie: [math]\displaystyle{ s= \sqrt{\frac{1}{n-1} \sum \limits_{i=1}^n\left(x_i-\overline x\right)^2} }[/math]

Jetzt gilt (lt. Mathematik...):

  • Mit 95% Sicherheit liegt der Mittelwert der Grundgesamtheit im Intervall [math]\displaystyle{ [\overline x - 1,96 \cdot {\frac{s}{\sqrt{n}}} ~ | ~ \overline x + 1,96 \cdot {\frac{s}{\sqrt{n}}} ] }[/math].
  • Mit 99% Sicherheit liegt der Mittelwert der Grundgesamtheit im Intervall [math]\displaystyle{ [\overline x - 2,58 \cdot {\frac{s}{\sqrt{n}}} ~ | ~ \overline x + 2,58 \cdot {\frac{s}{\sqrt{n}}} ] }[/math].

Beispiel: Ermittlung von PI

Es wird 10.000mal zufällig auf das Einheitsquadrat "geschossen": Als "Treffer" zählt es, wenn der Punkt im Einheitskreis liegt.
Von den 10.000 Schüssen sind 7851 Treffer, d.h. man hat eine Trefferwahrscheinlichkeit p=0,7851 .

Das ist eindeutig eine Bernoulli-Kette, denn

  • die "Schüsse" haben das Ergebnis 1 (=im Einheitskreis) oder 0 (daneben),
  • die "Schüsse" sind voneinander unabhängig.
  • Mittelwert: [math]\displaystyle{ \overline x = 0,7851 }[/math]
  • Standardabweichung der Stichprobe: [math]\displaystyle{ s = \sqrt{\frac{ {{7851}\cdot{(1 - 0,7851)^2}} + {2149} \cdot {(0 - 0,7851)^2}}{9999}} = 0,411 }[/math]

Bestimmung des Konfidenzinterfalls für eine Wahrscheinlichkeit von 99%:

  • [math]\displaystyle{ [\overline x - 2,58 \cdot {\frac{s}{\sqrt{n}}} ~ | ~ \overline x + 2,58 \cdot {\frac{s}{\sqrt{n}}} ] ~ = ~ }[/math]

    [math]\displaystyle{ [0,7851 - 2,58 \cdot{0,00411} ~ | ~ 0,7851 + 2,58 \cdot{0,00411} ]~ = ~ }[/math]

    [math]\displaystyle{ [0,7745 ~ | ~ 0,7957] }[/math]

Da man diese Simulation nur für einen Viertelkreis gemacht hat, muss man das Intervall noch mit 4 multiplizieren, um ein Konfidenzintervall für Pi zu erhalten:

Mit 99% Wahrscheinlichkeit liegt Pi im Intervall

[math]\displaystyle{ [4 \cdot 0,7745 ~|~ 4 \cdot 0,7957]~= }[/math]
[math]\displaystyle{ [3,0980 ~|~ 3,1828] }[/math]

Excel: Mittelwert und Standardabweichung berechnen

  • Die Daten in Spalte A packen.
    • Wichtig: Zahlen mit Kommas!
  • Folgende Formeln z.B. in die Felder C1 bis C5 eintragen:
    • C1: =ANZAHL(A:A)
    • C2: =MITTELWERT(A:A)
    • C3: =STABW.S(A:A)
    • C4: =C2-2,58*C3/WURZEL(C1)  Berechnet die untere Grenze des 99%-Konfidenzintervalls.
    • C5: =C2+2,58*C3/WURZEL(C1)  Berechnet die obere Grenze des 99%-Konfidenzintervalls.'

Java: Mittelwert und Standardabweichung berechnen

Hier ist eine Klasse Statistik, mit der man Mittelwert und Standardabweichung einer Stichprobe berechnen kann.


public class Statistik {
   
  public double mittelwert(double[] werte) {
     double anzahl = werte.length;
     double summe = 0;
     for (int i = 0; i < werte.length; i++) {
        summe += werte[i];
     }
     return 1.0*summe / anzahl;
  }
  
  public double standardAbweichungStichprobe(double[] werte) {
     int anzahl = werte.length;
     double mittelwert = mittelwert(werte);
        double summeAbweichungZumQuadrat = 0.0;
        for(int i=0; i<werte.length; i++) {
           double wert = werte[i];
           summeAbweichungZumQuadrat += Math.pow(wert - mittelwert, 2);
        }
        double standardAbweichung = Math.sqrt(summeAbweichungZumQuadrat/(anzahl-1));
        return standardAbweichung;
  }
   
  // zu Testzwecken
  public static void main(String[] args) {
     Statistik st = new Statistik();
     double[] stichprobe = { 35, 48, 60, 71, 80, 95, 130};
     double mittelwert = st.mittelwert(stichprobe);
     double standardAbweichungStichprobe = st.standardAbweichungStichprobe(stichprobe);
     System.out.println("Mittelwert: "+ mittelwert);
     System.out.println("Standardabweichung: "+standardAbweichungStichprobe);
  }
}


Python: Mittelwert und Standardabweichung berechnen

Um in Python den Mittelwert und die Standardabweichung zu berechnen, greift man am besten auf Funktionen der Bibliothek numpy zurück. (Natürlich könnte man das auch von Hand implementieren, aber das ist fehleranfälliger.)

Das folgende Beispielprogramm zeigt, wie man das macht.
Das Beispielprogramm kann man Copy&Paste in IDLE übernehmen.


import numpy as np
 
def mittelwert(x):
   return np.mean(x)

def standardabweichung(x):
   return np.std(x,ddof=1)
   # damit man die Standardabweichung der Stichprobe
   # und nicht der Gesamtheit berechnet,
   # muss man als zusätzliches Argument ddof=1 übergeben.

#main
x = [3.4,3.2,3.5,4.1,3.2]

mi = mittelwert(x)
std = standardabweichung(x)

print(x)
print("Mittelwert", mi)
print("Standardabweichung",std)