Szelőmódszer

A 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 analitikus kifejezését, hanem numerikusan közelíti meg azt.

A módszer

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 alkalmazzuk erre a sajátos esetre:

y − f ( x n ) = f ( x n ) − f ( x n − 1 ) x n − x n − 1 ( x − x n ) . {\displaystyle 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 ) + f ( x n ) − f ( x n − 1 ) x n − x n − 1 ( x n + 1 − x n ) = 0. {\displaystyle 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ő rekurzív képlet:

x n + 1 = x n − x n − x n − 1 f ( x n ) − f ( x n − 1 ) f ( x n ) . {\displaystyle 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

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:

α = 1 + 5 2 ≈ 1.618 {\displaystyle \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

A szelőmódszer tulajdonképpen az érintő módszer diszkretizált változata. Az érintő módszer (Newton-módszer) rekurzív összefüggése:

x n + 1 = x n − f ( x n ) f ′ ( x n ) {\displaystyle 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 ) ≈ f ( x n ) − f ( x n − 1 ) x n − x n − 1 . {\displaystyle 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

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 | < ϵ {\displaystyle |x_{n+1}-x_{n}|<\epsilon }
  2. n > m {\displaystyle 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 {\displaystyle x_{0}=0\,\!}
x 1 = 1 {\displaystyle x_{1}=1\,\!}
x 2 = 0.685073357326045 {\displaystyle x_{2}=0.685073357326045\,\!}
x 3 = 0. 8 _ 41355125665652 {\displaystyle x_{3}=0.{\underline {8}}41355125665652\,\!}
x 4 = 0. 8 _ 70353470875526 {\displaystyle x_{4}=0.{\underline {8}}70353470875526\,\!}
x 5 = 0. 865 _ 358300319342 {\displaystyle x_{5}=0.{\underline {865}}358300319342\,\!}
x 6 = 0. 86547 _ 3486654304 {\displaystyle x_{6}=0.{\underline {86547}}3486654304\,\!}
x 7 = 0. 8654740331 _ 63012 {\displaystyle x_{7}=0.{\underline {8654740331}}63012\,\!}
x 8 = 0. 865474033101614 _ {\displaystyle x_{8}=0.{\underline {865474033101614}}\,\!}

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

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

Források

Fordítás

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. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

  • matematika Matematikaportál • összefoglaló, színes tartalomajánló lap