Szelőmódszer

A Wikipédiából, a szabad enciklopédiából

Numerikus analízisben a szelőmódszer egy gyökkereső algoritmus, mely kiküszöböli az érintő-módszer (Newton-módszer) fő fogyatékosságát: nem használja fel a függvény deriváltjának analítikus kifejezését, hanem numerikusan közelíti meg azt.

A módszer[szerkesztés | forrásszöveg szerkesztése]

Legyen két kezdeti pont xn‒1 és xn, megkeressük a nekik megfelelő függvényértékeket majd az (xn‒1, f(xn‒1)) , (xn, f(xn)) pontokon keresztül megszerkesztünk egy egyenest. Ez lesz tulajdonképpen a szelő (lásd a grafikont jobbra).

A szelőmódszer első két lépése. A piros vonal az f függvény képe, a kék vonalak pedig a szelők.

Felírjuk az egyenes egyenletét, és alkalmazzük erre a sajátos esetre:

 y - f(x_n) = \frac{f(x_n)-f(x_{n-1})}{x_n-x_{n-1}} (x-x_n).

Most legyen xn+1 a fenti egyenes egy gyöke. Behelyettesítve a képletbe, mivel y=0:

 f(x_n) + \frac{f(x_n)-f(x_{n-1})}{x_n-x_{n-1}} (x_{n+1}-x_n) = 0.

Ezt átrendezve megkapjuk a keresett összefüggést. A módszer alapja tehát a következő rekurrenciás-képlet:

x_{n+1} = x_n - \frac{x_n-x_{n-1}}{f(x_n)-f(x_{n-1})} f(x_n).

A fenti összefüggésből jól látható, hogy szükséges két kezdeti pont: x0 és x1, melyek megfelelően kell legyenek kiválasztva, lehetőleg minél közelebb a keresett gyökhöz.

A módszer konvergenciája[szerkesztés | forrásszöveg szerkesztése]

A szelőmódszer akkor konvergens, tehát xn akkor tart az f függvény gyökéhez, ha a kezdeti x0 és x1 értékek megfelelően vannak választva. Ebben az esetben, a módszer konvergenciája:

 \alpha = \frac{1+\sqrt{5}}{2} \approx 1.618

ez tulajdonképpen az aranymetszés. A módszer szupralineáris.

Összehasonlítás más gyökkereső módszerrel[szerkesztés | forrásszöveg szerkesztése]

A szelőmódszer tulajdonképpen az érintő módszer diszkrétizált változata. Az érintő módszer rekurrenciás összefüggése:

 x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}

ahol ha használjuk a derivált következő közelítését:

 f'(x_n) \approx \frac{f(x_n)-f(x_{n-1})}{x_n-x_{n-1}}.

visszakaphatjuk a szelőmódszer alapképletét. Ha megfigyeljük a Newton-módszer gyorsabban konvergál (másodrendű), mint a szelőmódszer, de annak szüksége van a függvény kiértékelésére és annak deriváltjára is, minden lépésnél. Így a gyakorlatban a szelőmódszer gyorsabb, mint a Newton-módszer. Például ha figyelembe vesszük, hogy a függvény deriváltját egy adott pontban meg kell határozni, a program két lépést tudna elvégezni a szelőmódszerrel az idő alatt, míg a Newton módszer egy lépést.

Program C-ben[szerkesztés | forrásszöveg szerkesztése]

A következő program meghatározza azt a pozitív x-et, ahol cos(x) = x³, tehát ez a szelőmódszer alkalmazésa a következő függvényre:

f(x) = cos(x) ‒ x³

A kilépési feltételek legyenek a következőek:

  1.  |x_{n+1} - x_n| < \epsilon
  2.  n > m

ahol m egy előre megadott lépésszám, és ε a maximális hiba.

#include <stdio.h>
#include <math.h>
 
double f(double x)
{
    return cos(x) - x*x*x;
}
 
double Szelomodszer(double xn_1, double xn, double e, int m)
{
    int n;
    double d;
    for (n = 1; n <= m; n++)
    {
        d = (xn - xn_1) / (f(xn) - f(xn_1)) * f(xn);
        if (fabs(d) < e)
            return xn;
        xn_1 = xn;
        xn = xn - d;
    }
    return xn;
}
 
int main(void)
{
    printf("%0.15f\n", Szelomodszer(0, 1, 5E-11, 100));
    return 0;
}

A program futása után a következő eredményt kapjuk: 0.865474033101614. Alatta pedig láthatjuk, hogy lépésenként hogyan konvergál a program:

 x_0 = 0  \,\!
 x_1 = 1  \,\!
 x_2 = 0.685073357326045  \,\!
 x_3 = 0.\underline{8}41355125665652  \,\!
 x_4 = 0.\underline{8}70353470875526  \,\!
 x_5 = 0.\underline{865}358300319342  \,\!
 x_6 = 0.\underline{86547}3486654304  \,\!
 x_7 = 0.\underline{8654740331}63012  \,\!
 x_8 = 0.\underline{865474033101614}  \,\!

ahol az aláhúzott számjegyek a helyes értékek.

Secant method example code result.svg

Az ábrán megfigyelhető piros színnel az f függvény, az utolsó szelő pedig kékkel.

Források[szerkesztés | forrásszöveg szerkesztése]

Fordítás[szerkesztés | forrásszöveg szerkesztése]

Ez a szócikk részben vagy egészben a Secant method című angol Wikipédia-szócikk fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel.