Metoda Riddersa

Cztery pierwsze iteracje algorytmu, niebieska pozioma linia oznacza funkcję $x=x_d$

Metoda Riddersa – iteracyjna metoda numeryczna, służąca do rozwiązywania równań nieliniowych z jedną niewiadomą.

Metoda Riddersa jest to jedna z odmian metody fałszywych przybliżeń (łac. regula falsi). Opiera się ona na aproksymacji równania za pomocą funkcji eksponencjalnej. Algorytm ten gwarantuje, że punkt wyznaczony w kolejnej iteracji, będzie zawierał się w założonym przedziale. Wykorzystanie funkcji eksponenty do aproksymacji powoduje osłabienie niekorzystnego wpływu wypukłości funkcji aproksymowanej. Metoda ta jest prostsza w implementacji niż podobnie działające metody Brenta i Mullera, a jej zbieżność w porównaniu z analogicznymi metodami jest duża. Dokładność wartości rozwiązania metody zwiększa się dwukrotnie po dwóch iteracjach. Konieczność wyznaczenia dwóch wartości w każdej iteracji powoduje, że rząd zbieżności metody wynosi $\sqrt{2}.$

Z racji tego, że jest to rodzaj reguly falsi spełnione muszą być następujące założenia: w przedziale $(x_a;x_b)$ istnieje jedno miejsce zerowe (pierwiastek), oraz że funkcja $f(x)$ jest ciągła w przedziale $<x_a;x_b>.$

Przebieg algorytmu

• Wyznaczamy środek przedziału:

$x_c=\frac{(x_a+x_b)}{2}$

• Szukamy $e^Q$ spełniającego równanie:

$f(x_a)-2f(x_c)e^Q+f(x_b)e^{2Q}=0$

• Otrzymujemy:

$e^Q=\frac{f(x_c)+sign[f(x_b)]\sqrt{(f(x_c{)}^2-f(x_a)f(x_b)}}{f(x_b)}$

• Stosujemy regule falsi, lecz nie do wartości $f(x_a),$ $f(x_b)$ i $f(x_c),$ ale dla: $f(x_a),$$f(x_c)e^Q$ i $f(x_b)e^{2Q}$ znajdując przy ich pomocy nowe $x_d.$

$x_d=x_c+(x_c-x_a)\frac{sign[f(x_a)-f(x_b)]f(x_c)}{\sqrt{(f(x_c{)}^2-f(x_a)f(x_b)}}$

• Sprawdzamy wartość $f(x_d)$ jeżeli jest ona wystarczająco bliska 0 to algorytm kończy pracę, w innym wypadku koniec przedziału zostaje zastąpiony przez $x_d,$ następuje ponowne przejście do punktu pierwszego. Iteracje powtarzamy, aż do uzyskania wartości satysfakcjonującej.

Przykładowe rozwiązanie

Pierwsze 4 iteracje na przykładzie funkcji:$f(x)=x^3-11x^2+14x+80$

Animacja przedstawia cztery pierwsze iteracje algorytmu

Iteracja nr 1

$x_a=-6,$ $f(x_a)=-616,$
$x_b=10,$ $f(x_b)=120,$
$x_c=8,$ $f(x_c)=72,$
$e^Q=2,9438,$
$x_d=-0,048,$ $f(x_d)=79,303.$

Iteracja nr 2

$x_a=-6,$ $f(x_a)=-616,$
$x_b=-0,048,$ $f(x_b)=79,303,$
$x_c=-3,024,$ $f(x_c)=-90,577,$
$e^Q=1,8698,$
$x_d=-1,8955,$ $f(x_d)=7,1331.$

Iteracja nr 3

$x_a=-6,$ $f(x_a)=-616,$
$x_b=-1,8955,$ $f(x_b)=7,1331,$
$x_c=-3,9477,$ $f(x_c)=-208,223,$
$e^Q=1,4435,$
$x_d=-1,922,$ $f(x_d)=0,5475.$

Iteracja nr 4

$x_a=-6,$ $f(x_a)=-616,$
$x_b=-1,922,$ $f(x_b)=0,5475,$
$x_c=-3,9961,$ $f(x_c)=-215,4126,$
$e^Q=1,4272,$
$x_d=-1,9994,$ $f(x_d)=0,0415.$

Jeżeli uznamy, że wynik 0,0415 jest wystarczającym przybliżeniem wartości 0 to algorytm kończy działanie, w przeciwnym wypadku kontynuujemy iteracje do uzyskania wartości satysfakcjonującej.

Bibliografia

• Ridders, C. (1979). „A new algorithm for computing a single root of a real continuous function”. IEEE Transactions on Circuits and Systems 26: 979–980.
• Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). „Section 9.2.1. Ridders’ Method”. Numerical Recipes: The Art of Scientific Computing (3rd ed.). New York: Cambridge University Press.