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

Из пројекта Википедија

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

Садржај

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

Прве две итерације метода сечице. Црвена крива представља функцију 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+1x_n) = 0.}-

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

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

Низ 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. | xn + 1xn | < 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.

Image:Secantmethod_jaredwf.png

[уреди] Спољне везе