Metoda tangentei#

Motivul pentru care această metodă poartă o asmenea denumire onorifică ține de modalitatea prin care poate fi interpretată geometric. Vom elucida împreună misterele pe care le ascunde metoda în cadrul acestui subcapitol.

Metoda este cunoscută și sub denumirea de Newton-Raphson.

Descoperirea algoritmului#

Fie \(f:[a,b]\subseteq\mathbb{R}\rightarrow\mathbb{R}\) o funcție continuă și derivabilă pe intervalul \([a,b]\). Vom dezvolta această serie sub forma unui polinom Taylor de grad \(2\) în jurul unui punct \(x_0\in[a,b]\):

Fie \(p\in[a,b]\) ales astfel încât \(f(p)=0\). Dacă pornim de la o aproximare \(x_0\in[a,b]\) bună a lui \(p\) (cât mai aproape de \(x_0\), adică \(|p-x_0|\approx0\)), atunci \((p-x_0)^2\rightarrow0\).

Deci, înlocuind în polinomul de mai sus, obținem următoarea relație:

Cunoaștem însă \(f(p)=0\), așadar:

Metoda Newton-Raphson#

Folosind aceeași idee ca în cadrul metodei aproximațiilor succesive, anume de a converge către rezultatul dorit, se va defini următorul șir:

Atunci când \(k\to\infty\), se obține chiar \(p=x_k\). Așadar, metoda presupune calcularea unui număr cât mai mare de termeni, apropiindu-se astfel de valoarea \(p\).

Interpretarea geometrică#

Algoritmul este foarte ușor de vizualizat. Pentru a exemplifica algoritmul, să considerăm funcția:

Să considerăm punctul \(x_0=7\) - chiar dacă aceasta este o aproximație proastă, rezultatul produs va fi favorabil.

Vom desena acum funcția \(f\) cu portocaliu și tangenta acesteia în punctul \(x_0\) cu mov. Obținem deci:

Graficul funcției \(f(x)\)

Tangenta în \(x_0=7\) la graficul lui \(f(x)\)

Algoritmul continuă, ducând o paralelă punctată față de axa \(Oy\) din punctul de intersecție al tangentei cu axa \(Ox\). Se va trasa acum o altă tangentă, din punctul de intersecție al abscisei cu graficul funcției \(f(x)\) (adică punctul de abscisă \(x_1\)) - e mai ușor de vizualizat decât de explicat:

Paralela cu \(Oy\) care trece prin \(x_1\)

Tangenta în \(x_1\approx1.179245\) la graficul lui \(f(x)\)

Observăm că, în urma acestor iterații, ducând o ultimă paralelă cu \(Oy\) care trece prin \(x_1\), ne-am apropiat foarte mult de punctul în care \(f(x)\) se anulează:

Paralela cu \(Oy\) care trece prin \(x_2\approx2.331315\)

Am calculat așadar \(\begin{cases} f(x_0)=f(7)&\approx5.141666\\ f(x_1)\approx f(1.179245)&\approx-8.145335\\ f(x_2)\approx f(2.331315)&\approx-1.711315 \end{cases}\)

Ne-am apropiat, într-adevăr, de \(p\approx2.785\) - am fi și mai apropiați dacă am lăsa algoritmul să meargă în continuare.

Convergența#

Această metodă converge în aproximativ \(3-5\) pași, având ordinul de convergență egal cu \(q=2\) (vezi metoda bisecției). Se poate dovedi matematic că eroarea la iterația curentă este direct proporțională cu pătratul erorii de la iterația precedentă, ceea ce înseamnă că, la fiecare iterație, aproximativ, numărul de zecimale corect calculate se dublează.

Cu toate acestea, metoda poate să nu conveargă în situația în care:

• La un anumit pas \(k\in\mathbb{N}\), derivata este zero (numeric), adică \(f'(x_k)\approx0\);

  Motivul este evident - se împarte la \(0\) (sau \(0\) numeric) în calcularea elementului \(x_{k+1}\), ceea ce conduce la o valoare foarte mare a lui \(x_{k+1}\) care tinde către infinit: \(x_{k+1}\rightarrow\pm\infty\).

• \(x_0\) nu este ales suficient de aproape de \(p\).

  În această situație, se încalcă \((p-p_0)^2\to0\). Este posibil ca algoritmul să funcționeze oricum, așa cum am exemplificat anterior, însă nu avem această garanție.

Cod ilustrativ#

Vom implementa metoda secantei în Matlab (funcția metoda_secantei). Aceasta primește:

• x_0 - echivalentul elementului \(x_0\);

• P - un polinom pe postul funcției \(f\), posibil obținut prin interpolare;

• err - eroarea maximă acceptată pentru evaluarea lui \(f\) față de \(0\);

• max_iter - numărul maxim de pași pe care îi poate executa algoritmul până se renunțe.

Codul de mai jos returnează x, echivalentul punctului în care \(f(x)\approx0\).

function x = metoda_tangentei(x_0, P, err, max_iter)
    dP = polyder(P);
    x = x_0;
    for k = [1 : max_iter]
        y0 = polyval(P, x);
        if abs(y0) < err
            return
        end
        dy0 = polyval(dP, x);
        x -= y0 / dy0;
    end
end

Licență#

The book "Metode Numerice", written by Valentin-Ioan Vintilă, is licensed under CC BY-NC-SA 4.0