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.

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.

Das Bisektionsverfahren (oder auch Intervallschachtelung) beruht auf dem Zwischenwertsatz der Analysis:

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

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.

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.

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

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.

Das Heron-Verfahren ist ein Verfahren zur näherungsweisen Berechnung der Quadratwurzel einer reellen Zahl. Es wird dem griechischen Mathematiker Heron von Alexandria zugeschrieben, aber wahrscheinlich war es bereits den alten Babyloniern bekannt. Man kann es deshalb auch babylonisches Wurzelziehen nennen.

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.

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:

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

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

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.

Das vorgestellte Verfahren kann man als Algorithmus formulieren:

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.

Beim Buffonschen Nadelproblem, welches nach 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 hier beschrieben.

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.

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.

Aufgabe 25

Führe den Versuch mit einer Schachtel Streichhölzer mindestens zehnmal durch. Erfasse deine Messwerte in einem Tabellenkalkulationsprogramm!

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:

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$:

montecarlo.py

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