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.