Regula falsi
Wie das Newton-Verfahren ist die Regula falsi eine Methode zum Auffinden von Nullstellen von Funktionen. Im Unterschied zu diesem startet es mit einem Intervall [x1, x2], in dem sich die gesuchte Nullstelle befindet. Außerdem benötigt es nicht die Ableitung der Funktion, sondern arbeitet anhand von Sekanten anstelle von Tangenten.
Ein Schritt des Verfahrens in seiner Grundform berechnet aus den Intervallgrenzen x1 und x2 einen weiteren Wert z mit
z = x1 - (x2 - x1) / (f(x2) - f(x1)) f(x1)
und setzt für den nächsten Schritt x1 = z wenn f(x1) und f(z) das gleiche Vorzeichen haben und x2 = z, wenn f(x2) und f(z) das gleiche Vorzeichen haben.
Wenn die zweite Ableitung der Funktion im Intervall [x1, x2] keinen Vorzeichenwechsel hat, dann bleibt eine Intervallgrenze bei allen Interationsschritten gleich. Das Verfahren konvergiert dann nur linear. Diesen Nachteil vermeidet die Verbesserung der Regula Falsi nach Andersen und Björck.
Die Realisierung des Andersen-Björck-Verfahrens verwendet einige Hilfsfunktionen. Die Funktion opposite-sign? prüft, ob ihre beiden Argumente ein unterschiedliches Vorzeichen haben.
(defproc opposite-sign? (a b)
(or
(and (> a 0) (< b 0))
(and (< a 0) (> b 0))))
Die Funktion andersen-björk dient der Berechnung eines Faktors, der beim Verändern der Intervallgrenzen benötigt wird.
(defproc andersen-björck (fz f2)
(let
((m (- 1 (/ fz f2))))
(if (> m 0) m 0.5)))
Die Funktion regula-falsi-iteration verbessert eine Näherung so lange, bis die Länge des Intervalls kleiner als das Argument delta ist.
(defproc regula-falsi-iteration (f x1 f1 x2 f2 delta)
(let
((i (- x2 x1))
(fi (- f2 f1)))
(if
(< (abs i) delta)
(/ (+ x1 x2) 2)
(let
((z (- x1 (* f1 (/ i fi)))))
(let
((fz (f z)))
(if
(= fz 0)
z
(if
(opposite-sign? fz f2)
(regula-falsi-iteration f x2 f2 z fz delta)
(regula-falsi-iteration f x1 (* f1 (andersen-björck fz f2)) z fz delta))))))))
Die Hilfsfunktionen werden so kombiniert, dass für die Funktion (Parameter f) und das Startintervall (Parameter x1 und x2) eine Näherung einer Nullstelle im Intervall in einer gegebene Genauigkeit (Parameter delta) bestimmt wird.
(defproc regula-falsi (f x1 x2 delta)
(let
((f1 (f x1))
(f2 (f x2)))
(if
(opposite-sign? f1 f2)
(approximate (regula-falsi-iteration f x1 f1 x2 f2 delta) delta)
(throw (quote error) "zero not within interval in regula-falsi"))))
Mit der Funktion (lambda (x) (- (* x x) 2)) und ausgehend von den initialen Intervallgrenzen 1.4 und 1.5 kann man die Quadratwurzel von 2 auf z.B. 50 Stellen genau bestimmen:
1.41421356237309504880168872420969807856967187537694
Quelle
https://de.wikipedia.org/wiki/Regula_Falsi
Ein Schritt des Verfahrens in seiner Grundform berechnet aus den Intervallgrenzen x1 und x2 einen weiteren Wert z mit
z = x1 - (x2 - x1) / (f(x2) - f(x1)) f(x1)
und setzt für den nächsten Schritt x1 = z wenn f(x1) und f(z) das gleiche Vorzeichen haben und x2 = z, wenn f(x2) und f(z) das gleiche Vorzeichen haben.
Wenn die zweite Ableitung der Funktion im Intervall [x1, x2] keinen Vorzeichenwechsel hat, dann bleibt eine Intervallgrenze bei allen Interationsschritten gleich. Das Verfahren konvergiert dann nur linear. Diesen Nachteil vermeidet die Verbesserung der Regula Falsi nach Andersen und Björck.
Die Realisierung des Andersen-Björck-Verfahrens verwendet einige Hilfsfunktionen. Die Funktion opposite-sign? prüft, ob ihre beiden Argumente ein unterschiedliches Vorzeichen haben.
(defproc opposite-sign? (a b)
(or
(and (> a 0) (< b 0))
(and (< a 0) (> b 0))))
Die Funktion andersen-björk dient der Berechnung eines Faktors, der beim Verändern der Intervallgrenzen benötigt wird.
(defproc andersen-björck (fz f2)
(let
((m (- 1 (/ fz f2))))
(if (> m 0) m 0.5)))
Die Funktion regula-falsi-iteration verbessert eine Näherung so lange, bis die Länge des Intervalls kleiner als das Argument delta ist.
(defproc regula-falsi-iteration (f x1 f1 x2 f2 delta)
(let
((i (- x2 x1))
(fi (- f2 f1)))
(if
(< (abs i) delta)
(/ (+ x1 x2) 2)
(let
((z (- x1 (* f1 (/ i fi)))))
(let
((fz (f z)))
(if
(= fz 0)
z
(if
(opposite-sign? fz f2)
(regula-falsi-iteration f x2 f2 z fz delta)
(regula-falsi-iteration f x1 (* f1 (andersen-björck fz f2)) z fz delta))))))))
Die Hilfsfunktionen werden so kombiniert, dass für die Funktion (Parameter f) und das Startintervall (Parameter x1 und x2) eine Näherung einer Nullstelle im Intervall in einer gegebene Genauigkeit (Parameter delta) bestimmt wird.
(defproc regula-falsi (f x1 x2 delta)
(let
((f1 (f x1))
(f2 (f x2)))
(if
(opposite-sign? f1 f2)
(approximate (regula-falsi-iteration f x1 f1 x2 f2 delta) delta)
(throw (quote error) "zero not within interval in regula-falsi"))))
Mit der Funktion (lambda (x) (- (* x x) 2)) und ausgehend von den initialen Intervallgrenzen 1.4 und 1.5 kann man die Quadratwurzel von 2 auf z.B. 50 Stellen genau bestimmen:
1.41421356237309504880168872420969807856967187537694
Quelle
https://de.wikipedia.org/wiki/Regula_Falsi