Метода сечице

Из Википедије, слободне енциклопедије

У нумеричкој анализи, метода сечице је алгоритам за приближно решавање једначина, који користи низ сечица како би све боље апроксимирао корен функције f.

Метода[уреди]

Прве две итерације метода сечице. Црвена крива представља функцију f, а плаве линије су сечице.

Метода сечице је дефинисана рекурентном релацијом

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

Као што се може видети из рекурентне релације, метода сечице захтева две почетне вредности, x0 и x1, које би требало да буду што ближе траженој нули функције.

Извођење методе[уреди]

Ако је дато xn−1 и xn, конструишемо праву кроз тачке (xn−1, f(xn−1)) и (xn, f(xn)), као што се види на слици десно. Ова права представља сечицу криве функције f. Можемо је дефинисати на следећи начин

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

xn+1 је нула ове праве, тако да је

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

Решавање ове једначине даје рекурентну релацију за методу сечице.

Конвергенција[уреди]

Sekantenverfahren Ani2.gif

Низ xn методе сечице конвергира нули функције f, ако су почетне вредности x0 и x1 довољно близу нули. Ред конвергенције је φ, где

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

је златни пресек. Специфично, конвергенција је суперлинеарна.

Ово важи само под одређеним техничким условима, наиме, f треба да је двапут непрекидно диференцијабилно, и дати корен функције мора да буде прост (то јест, да не буде вишеструки).

Ако почетне вредности нису близу нули, не постоји гаранција да ће метода сечице конвергирати.

Поређење са другим приближним методама[уреди]

Метода сечице не захтева да нула остане уоквирена, као што је случај код методе половљења интервала, и стога не конвергира увек. Метода лажног позиционирања користи исту формулу као и метода сечице. Међутим, она не примењује формулу на xn−1 и xn, као метода сечице, већ на xn и на последњи xk тако да f(xk) и f(xn) имају супротне знакове. Ово значи да метода лажног позиционирања увек конвергира.

Рекурентна формула методе сечице може да се изведе из формуле за методу тангенте (Њутнова метода)

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

коришћењем апроксимације

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

Ако упоредимо методу тангенте и метод сечице, видећемо да метода тангенте брже конвергира (ред 2 у односу на φ ≈ 1,6). Међутим, метода тангенте захтева израчунавање и вредности функције, и њеног извода у сваком кораку, док метода сечице захтева израчунавање само вредности функције. Стога метода сечице може бити бржа у пракси. На пример, ако претпоставимо да израчунавање f узима исто времена као и израчунавање њеног извода, и занемаримо све друге трошкове, можемо да изведемо два корака методе сечице (смањивши грешку за фактор φ² ≈ 2,6) за исто време за које метода тангенте врши један корак (смањивши грешку за фактор 2), па је метода сечице бржа.

Пример кода[уреди]

Следи C код, написан да буде читљив, а не ефикасан. Дизајниран је да нађе позитиван број x где је cos(x) = x3. Овај проблем се трансформише у проблем апроксимације за форму f(x) = cos(x) − x3 = 0.

Метода сечице ће се у коду извршавати све док се један од следећа два услова не испуни:

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

за неке задате m и e.

#include <stdio.h>
#include <math.h>
 
double f(double x)
{
    return cos(x) - x*x*x;
}
 
double SecantMethod(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", SecantMethod(0, 1, 5E-11, 100));
    return 0;
}

Након извршавања кода, коначно решење је приближно 0,865474033101614. Почетне, успутне и коначне апроксимације су излистане испод:

 x_0 = 0  \,\!
 x_1 = 1  \,\!
 x_2 = 0.685073357326045  \,\!
 x_3 = 0.841355125665652  \,\!
 x_4 = 0.870353470875526  \,\!
 x_5 = 0.865358300319342  \,\!
 x_6 = 0.865473486654304  \,\!
 x_7 = 0.865474033163012  \,\!
 x_8 = 0.865474033101614  \,\!

Следећи график показује функцију f у црвеном, и последњу сечицу у плавом. На графику се види да је пресек x осе и сечице прилично добра апроксимација нуле функције f.

Secantmethod jaredwf.png


Види још[уреди]

Спољашње везе[уреди]