Metoda sečice

S Vikipedije, slobodne enciklopedije

U numeričkoj analizi, metoda sečice je algoritam za približno rešavanje jednačina, koji koristi niz sečica kako bi sve bolje aproksimirao koren funkcije f.

Metoda[uredi | uredi izvor]

Prve dve iteracije metoda sečice. Crvena kriva predstavlja funkciju f, a plave linije su sečice.

Metoda sečice je definisana rekurentnom relacijom

Kao što se može videti iz rekurentne relacije, metoda sečice zahteva dve početne vrednosti, x0 i x1, koje bi trebalo da budu što bliže traženoj nuli funkcije.

Izvođenje metode[uredi | uredi izvor]

Ako je dato xn−1 i xn, konstruišemo pravu kroz tačke (xn−1, f(xn−1)) i (xn, f(xn)), kao što se vidi na slici desno. Ova prava predstavlja sečicu krive funkcije f. Možemo je definisati na sledeći način

xn+1 je nula ove prave, tako da je

Rešavanje ove jednačine daje rekurentnu relaciju za metodu sečice.

Konvergencija[uredi | uredi izvor]

Niz xn metode sečice konvergira nuli funkcije f, ako su početne vrednosti x0 i x1 dovoljno blizu nuli. Red konvergencije je φ, gde

je zlatni presek. Specifično, konvergencija je superlinearna.

Ovo važi samo pod određenim tehničkim uslovima, naime, f treba da je dvaput neprekidno diferencijabilno, i dati koren funkcije mora da bude prost (to jest, da ne bude višestruki).

Ako početne vrednosti nisu blizu nuli, ne postoji garancija da će metoda sečice konvergirati.

Poređenje sa drugim približnim metodama[uredi | uredi izvor]

Metoda sečice ne zahteva da nula ostane uokvirena, kao što je slučaj kod metode polovljenja intervala, i stoga ne konvergira uvek. Metoda lažnog pozicioniranja koristi istu formulu kao i metoda sečice. Međutim, ona ne primenjuje formulu na xn−1 i xn, kao metoda sečice, već na xn i na poslednji xk tako da f(xk) i f(xn) imaju suprotne znakove. Ovo znači da metoda lažnog pozicioniranja uvek konvergira.

Rekurentna formula metode sečice može da se izvede iz formule za metodu tangente (Njutnova metoda)

korišćenjem aproksimacije

Ako uporedimo metodu tangente i metod sečice, videćemo da metoda tangente brže konvergira (red 2 u odnosu na φ ≈ 1,6). Međutim, metoda tangente zahteva izračunavanje i vrednosti funkcije, i njenog izvoda u svakom koraku, dok metoda sečice zahteva izračunavanje samo vrednosti funkcije. Stoga metoda sečice može biti brža u praksi. Na primer, ako pretpostavimo da izračunavanje f uzima isto vremena kao i izračunavanje njenog izvoda, i zanemarimo sve druge troškove, možemo da izvedemo dva koraka metode sečice (smanjivši grešku za faktor φ² ≈ 2,6) za isto vreme za koje metoda tangente vrši jedan korak (smanjivši grešku za faktor 2), pa je metoda sečice brža.

Primer koda[uredi | uredi izvor]

Sledi C kod, napisan da bude čitljiv, a ne efikasan. Dizajniran je da nađe pozitivan broj x gde je cos(x) = x3. Ovaj problem se transformiše u problem aproksimacije za formu f(x) = cos(x) − x3 = 0.

Metoda sečice će se u kodu izvršavati sve dok se jedan od sledeća dva uslova ne ispuni:

za neke zadate m i 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;
}

Nakon izvršavanja koda, konačno rešenje je približno 0,865474033101614. Početne, usputne i konačne aproksimacije su izlistane ispod:

Sledeći grafik pokazuje funkciju f u crvenom, i poslednju sečicu u plavom. Na grafiku se vidi da je presek x ose i sečice prilično dobra aproksimacija nule funkcije f.


Vidi još[uredi | uredi izvor]

Spoljašnje veze[uredi | uredi izvor]