======Numerische Verfahren als Hilfsmittel in der Mathematik====== Die **numerische Mathematik** beschäftigt sich vorwiegend mit der näherungsweisen Lösung von Problemen, die analytisch/algorithmisch nicht oder nur schwer lösbar sind. Im folgenden sollen einige Verfahren der numerischen Mathematik vorgestellt werden. =====Numerisches Lösen von Gleichungen===== In der Mathematik bezeichnet als eine **Gleichung** zwei Terme die durch ein "=" verbunden sind. Bei einer Gleichung mit einer unbekannten Variable "x" könnte das so aussehen: $$T_1(x)=T_2(x)$$ Bringt man nun beide Terme auf eine Seite der Gleichung, so kann man die Lösungen der Gleichung als Nullstellen einer Funktion auffassen. $$0=T_1(x)-T_2(x)$$ $$0=f(x)$$ Die im folgenden vorgestellten numerischen Verfahren können näherungsweise die Nullstellen beliebiger Funktionen berechnen, wenn bestimmte Anfangsbedingungen erfüllt sind. ====Bisektionsverfahren==== Das **Bisektionsverfahren** (oder auch **Intervallschachtelung**) beruht auf dem Zwischenwertsatz der Analysis: **Satz:** Zwischen zwei Punkten $P_1(x_1,f(x_1))$ und $P_2(x_2,f(x_2))$ einer stetigen Funktion $f(x)$ nimmt $f$ jeden Funktionswert zwischen $f(x_1)$ und $f(x_2)$ mindestens einmal an. Wenn also $f(x_1)$ negativ und $f(x_2)$ positiv ist oder umgekehrt, so muss sich zwischen $x_1$ und $x_2$ eine Nullstelle befinden. Um die Nullstelle zu finden halbiert man nun das Intervall immer weiter und nimmt das Teilintervall, bei dem die Funktionswerte an den Intervallgrenzen unterschiedliche Vorzeichen haben. Das Verfahren hat auch einige Nachteile: * Es funktioniert nur, wenn sich im Intervall genau eine Nullstelle befindet. * Es ist nicht einfach günstige Startwerte zu finden. **Algorithmis als Wortvorschrift:** In der Wortvorschrift setzen wir für $x_1$ $a$ und für $x_2$ $b$. * Eingabe Intervallgrenzen $a$ und $b$ mit $f(a) \cdot f(b) < 0$ * Eingabe minimale Intervalllänge $l$ * Solange $\vert a-b \vert > l$ ist: * $m = \dfrac{a+b}{2}$ * Wenn $f(a) \cdot f(m) < 0$ * $b = m$ * sonst * $a = m$ * Wenn $f(m) == 0$ * Abbruch der Schleife * Ausgabe Nullstelle: m Leider ist es in Python nur schwer möglich, den Funktionsterm bei der Programmausführung einzugeben. Deshalb wird $f(x)$ im Quelltext definiert. def f(x): return 4-x*x def bisektion(a,b,l): while abs(a-b) > l: m =(a+b)/2 if f(a) * f(m) < 0: b = m else: a = m if f(m) == 0.0: break return m **Aufgabe 14** Schreibe ein Programm (bisektion1.py) , welches nach Eingabe von $a$, $b$ und $l$ die Nullstelle der Funktion $f(x)$ ausgibt. Teste das Programm mit $f(x)=4-x^2$, $a=0$, $b=3$ und $l=1e-10$. Finde mit dem GTR weitere Funktionen und geeignete Werten für a und b. Teste das Programm damit. **Aufgabe 15** Erweitere dein Programm (bisektion2.py) so, dass der Iterationsprozess als Wertetabelle dargestellt wird und die Anzahl der Iterationsschritte gezählt wird. **Aufgabe 16** Erweitere dein Programm (bisektion3.py) so, dass man in einem Menü wählen kann, zwischen der Ausgabe einer Wertetabelle und der Berechnung der Nullstelle. Mit Hilfe der Wertetabelle soll es möglich sein, günstige Werte für $a$ und $b$ zu finden. **Aufgabe 17** Berechne mit dem Programm aus Aufgabe 16 die Nullstellen der folgenden Funktionen: * $f(x)=e^{\frac{1}{x-3}}-2$ (eine Nullstelle) * $f(x)=1+\ln \vert x^2-1 \vert$ (vier Nullstellen) * $f(x)=8e^{-2x}-16$ (eine Nullstelle) * $f(x)=4e^{3x}-e^{2x}$ //**Hinweise:**// Die Funktion $f(x)=e^x$ nennt man natürliche Expnentialfunktion, die Funktion $f(x)=\ln x$ natürliche Logarithmusfunktion. In Python kann man die Funktion auf folgende Weise erzeugen: import numpy def f(x): return numpy.exp(x) #e^x natürliche Exponentialfunktion def f(x): return numpy.log(x) #ln x natürliche Logarithmusfunktion Schreibe alle Funktionen in die Lösungsdatei der Aufgabe 16 und lasse die unbenutzten Funktionen auskommentiert. ====Regula Falsi==== Man könnte nun annehmen das beim Bisektionsverfahren die Nullstelle näher bei der Intervallgrenze liegt, deren Absolutbetrag kleiner ist. Diese Idee macht man sich beim Verfahren **Regula Falsi** zu nutze. Man legt eine Gerade durch Randpunkte des Intervalls. Die Stelle $x_f$, an der die Gerade die x-Achse schneidet ist die neue obere bzw. untere Intervallgrenze. **Berechnung von $x_f$:** **Gerade $g: y = mx + n$ durch** \\ ** $P_1(x_1,f(x_1))$ und $P_2(x_2,f(x_2))$:** \\ * $m = \dfrac{f(x_2)-f(x_1)}{x_2 - x_1}$ \\ * Einsetzen von $P_1$: \\ * $f(x_1) = \dfrac{f(x_2)-f(x_1)}{x_2 - x_1} \cdot x_1 + n$ \\ * $n = f(x_1) - \dfrac{f(x_2)-f(x_1)}{x_2 - x_1} \cdot x_1$ {{:profil:klasse10:regulafalsi.png?300|}} * $g: y = \dfrac{f(x_2)-f(x_1)}{x_2 - x_1} \cdot x + f(x_1) - \dfrac{f(x_2)-f(x_1)}{x_2 - x_1} \cdot x_1$ * $g: y = \dfrac{f(x_2)-f(x_1)}{x_2 - x_1} \cdot (x-x_1)$ **Berechnung der Nullstelle $x_f$:** * $0 = \dfrac{f(x_2)-f(x_1)}{x_2 - x_1} \cdot x_f + f(x_1) - \dfrac{f(x_2)-f(x_1)}{x_2 - x_1} \cdot x_1$$ * $\dfrac{f(x_2)-f(x_1)}{x_2 - x_1} \cdot x_f = \dfrac{f(x_2)-f(x_1)}{x_2 - x_1} - f(x_1)$ * $x_f=\left( \dfrac{f(x_2)-f(x_1)}{x_2 - x_1} - f(x_1) \right) \cdot \dfrac{x_2 - x_1}{f(x_2)-f(x_1)}$ * $x_f = x_1 - \dfrac{f(x_1) \cdot (x_2-x_1) }{f(x_2)-f(x_1)}$ **Algorithmis als Wortvorschrift:** In der Wortvorschrift setzen wir für $x_1$ $a$ und für $x_2$ $b$. * Eingabe Intervallgrenzen $a$ und $b$ mit $f(a) \cdot f(b) < 0$ * Eingabe minimale Intervalllänge $l$ * Solange $\vert a-b \vert > l$ ist: * $x_f = a - \dfrac{f(a) \cdot (b-a) }{f(b)-f(a)}$ * Wenn $f(a) \cdot f(x_f) < 0$ * $b = x_f$ * sonst * $a = x_f$ * Wenn $f(x_f) == 0$ * Abbruch der Schleife * Ausgabe Nullstelle: $x_f$ **Aufgabe 18** Löse die Aufgaben 14 bis 16 entsprechend für Regula Falsi. **Aufgabe 19** Vergleiche mit Hilfe der Programme bisektion02.py und regulafalsi02.py die Anzahl der Iterationschritte für entsprechende Funktionsbeispiele. **Aufgabe 20** Löse die Aufgabe 17 entsprechend mit Regula Falsi. =====Näherungsweise Bestimmung der Quadratwurzel - Heron-Verfahren===== Das **Heron-Verfahren** ist ein Verfahren zur näherungsweisen Berechnung der Quadratwurzel einer reellen Zahl. Es wird dem griechischen Mathematiker [[https://de.wikipedia.org/wiki/Heron_von_Alexandria|Heron von Alexandria]] zugeschrieben, aber wahrscheinlich war es bereits den alten Babyloniern bekannt. Man kann es deshalb auch **babylonisches Wurzelziehen** nennen. ====Idee des Verfahrens==== Angenommen, wir wollen die Quadratwurzel der Zahl 5 berechnen, können wir uns diese Wurzel als Kantenlänge eines Quadrats mit der Fläche $A=5$ vorstellen. Auch ein Rechteck mit den Kantenlängen $x_0=1$ und $y_0=5$ hat den Flächeninhalt 5. {{ :profil:klasse10:heron1.png?200 |}} Wir wollen nun die Kantenlängen des Rechtecks immer weiter anpassen, bis ein Quadrat mit dem Flächeninhalt 5 entsteht. **1. Schritt:** Zunächst berechnen wir eine neue Kantenlänge als arithmetisches Mittel der beiden anderen Kantenlängen: $$x_1=\dfrac{x_0+y_0}{2}=\dfrac{1+5}{2}=3$$ Dann berechnen wir die zweite Kantenlänge, indem wir den Flächeninhalt (die Zahl von der wir die Wurzel ermitteln wollen durch die neue Kantenlänge dividieren: $$y_1=\dfrac{A}{x_1}=\dfrac{5}{3}=1,667$$ Es entsteht das folgende Rechteck: {{ :profil:klasse10:heron2.png?200 |}} Dieses Vorgehen setzen wir jetzt immer weiter fort, bis die Seitenlängen des Rechtecks nahezu gleich sind: **2. Schritt:** $$x_2=\dfrac{x_1+y_1}{2}=\dfrac{3+1,667}{2}=2,333$$ $$y_2=\dfrac{A}{x_2}=\dfrac{5}{2,333}=2,143$$ {{ :profil:klasse10:heron3.png?200 |}} **3. Schritt:** $$x_3=\dfrac{x_2+y_2}{2}=\dfrac{2,333+2,143}{2}=2,238$$ $$y_3=\dfrac{A}{x_3}=\dfrac{5}{2,238}=2,234$$ {{ :profil:klasse10:heron4.png?200 |}} **4. Schritt:** $$x_4=\dfrac{x_3+y_3}{2}=\dfrac{2,238+2,234}{2}=2,236$$ $$y_4=\dfrac{A}{x_4}=\dfrac{5}{2,236}=2,236$$ Wie man sieht, hat man bereits nach vier Schritten einen guten Näherungswert für die Quadratwurzel von 5. $$\sqrt{5} \approx 2,236$$ \\ **Aufgabe 21** Berechne mit dem vorgestellten Verfahren die Wurzel von 7 auf drei Nachkommastellen genau! **Aufgabe 22** Erstelle mit einem Tabellenkalkulationsprogramm eine Tabelle, die die Wurzel einer Zahl mit dem Heron-Verfahren berechnet. {{ :profil:klasse10:heron_tabelle.png?300 |}} ====Algorithmus des Heron-Verfahrens==== Das vorgestellte Verfahren kann man als Algorithmus formulieren: * Gib die Zahl und die Genauigkeit ein! * Weise x den Wert 1 und y den Wert der Zahl zu! * Wiederhole, bis der Unterschied von x und y kleiner als die Genauigkeit ist: * x ergibt sich als arithmetisches Mittel von x und y * y ergibt sich als Quotient aus der Zahl und x * Gib x aus! **Aufgabe 23** Erstelle das Struktogramm für den Algorithmus uns setze ihn in einem Pythonprogramm um! **Aufgabe 24** Erweitere dein Pythonprogramm so, dass die Zwischenschritte und die Anzahl der Zwischenschritte mit ausgegeben werden. =====Näherungsweise Bestimmung von π mit Mitteln der Wahrscheinlichkeitsrechnung===== ====Buffonsches Nadelproblem==== Beim Buffonschen Nadelproblem, welches nach [[https://de.wikipedia.org/wiki/Georges-Louis_Leclerc_de_Buffon|Comte de Buffon]] benannt ist, wird erklärt wie man einen Näherungswert für die Zahl π durch werfen von Nadeln (oder Streichhölzern) auf eine Fläche mit waagerechten Linien ermitteln kann. Der mathematische Hintergrund des Verfahrens wird [[https://de.wikipedia.org/wiki/Buffonsches_Nadelproblem|hier]] beschrieben. ===Der Versuch=== Für den Versuch benötigt man viele Stäbchen (Nadeln, Steichhölzer) der Länge d. Zunächst zeichnet man auf ein Blatt Papier parallele Linien, die den Abstand 2d haben. Danach wirft man die Streichhölzer zufällig auf das Blatt Papier. {{ :profil:klasse10:versuch.png?600 |}} Nun zählt man die Stäbchen, die die Linie kreuzen. Der Quotient aus der Anzahl aller Stäbchen $N_A$ und der Anzahl der Stäbchen, die die Linie kreuzen $N_C$ ergibt einen Näherungswert für π. $$\pi \approx \dfrac{N_A}{N_C}$$ Dieser Näherungswert wird umso besser, je häufiger der Versuch durchgeführt wird. {{youtube>1mSarIP_Uhk}} \\ **Aufgabe 25** Führe den Versuch mit einer Schachtel Streichhölzer mindestens zehnmal durch. Erfasse deine Messwerte in einem Tabellenkalkulationsprogramm! ====Monte-Carlo-Methode==== Leider lässt sich das Verfahren von Buffon nicht mit dem Computer simulieren, deshalb wollen wir noch ein weiteres Verfahren zu Bestimmung von π kennenlernen. Wir betrachten ein Quadrat mit der Kantenlänge 2 und einen Kreis mit dem Radius 1 um den Koordinatenursprung: {{ :profil:klasse10:montecarlo.png?400 |}} Für den Flächeninhalt des Quadrats gilt: $$A_Q = a^2 = 2^2 = 4$$ Für den Flächeninhalt des Kreises gilt: $$A_K = \pi \cdot r^2 = \pi \cdot 1^1 = \pi$$ Setzt man die beiden Flächeninhalte ins Verhältnis, so ergibt sich: $$\dfrac{A_K}{A_Q} = \dfrac{\pi}{4}$$ Um nun einen Näherungswert für π zu ermitteln erzeugt man Punkte mit zufälligen Koordinaten, die im Bereich von -1 bis 1 liegen. Danach zählt man die Punkte die innerhalb des Kreises liegen und dividiert sie durch die Gesamtzahl der Punkte. So erhält man einen Näherungswert für $\frac{\pi}{4}$, den man nur noch mit 4 multiplizieren muss. Das folgende Pythonprogramm ermittelt nach Eingabe der Anzahl der Punkte einen Näherungswert für $\pi$: # Modul random importieren import random # Zufallszahlengenerator initialisieren random.seed() # erzeugt eine Koordinate im Bereich von -1 bis 1 def koordinate(): # random.random() erzeugt Zufallszahl im Bereich von 0 bis 1 test = random.random() if test > 0.5: return random.random() else: return -random.random() while True: print() print("Monte Carlo") print("***********") print() p = int(input("Anzahl Punkte: ")) t = 0 for i in range(p): x = koordinate() y = koordinate() if (x**2+y**2)**(1/2) < 1: t += 1 print("Näherungswert für pi:",4*t/p) print() if input("Nochmal? (J/N) ") == "N": break **Aufgabe 26** Teste das Programm. Versuche es zu verstehen und setze die entsprechenden Kommentare im Quelltext. **Aufgabe 27** Ermittle π für 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000 Punkte und berechne die Abweichung vom tatsächlichen Wert von π. Nutze dazu ein Tabellenkalkulationsprogramm.