Mètode de la secant

De Viquipèdia
Dreceres ràpides: navegació, cerca

En anàlisi numèrica, el mètode de secant és un algorisme de resolució numèrica d'equacions que fa servir una successió de solucions d'equacions lineals que corresponen a rectes secants a l'equació original per tal de trobar una solució aproximada d'una funció f. Es pot pensar en el mètode de la secant com una aproximació en diferència finita del Mètode de Newton. Tanmateix, el mètode de la secant es va desenvolupar idependentment del mètode de Newton i el precedeix en més de 3000 anys.[1]

El mètode[modifica | modifica el codi]

Les primeres dues iteracions del mètode de la secant. La corba vermella mostra la funció f i les línies blaves són les secants.

El mètode de secant es defineix per l'expressió recursiva:

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

Com es pot veure a partir de l'expressió recursiva, el mètode de la secant requereix dos valors inicials, x0 i x1, que idealment s'haurien d'escollir de forma que estiguin a la vora de l'arrel.

Obtenció del mètode[modifica | modifica el codi]

Començant amb valors els inicials x0 i x1, es construeix una recta que passa pels punts (x0,f(x0)) i (x1,f(x1)), com es mostra a la figura de la dreta. Aquesta recta té l'equació

y=\frac{f(x_1)-f(x_0)}{x_1-x_0}(x-x_1) + f(x_1)

Es troba l'arrel d'aquesta funció -- el valor de x tal que y=0 -- resolent x en l'equació següent:

0=\frac{f(x_1)-f(x_0)}{x_1-x_0}(x-x_1) + f(x_1)

La solució és

x=x_1-f(x_1)\frac{x_1-x_0}{f(x_1)-f(x_0)}

Llavors es fa servir aquest valor de x com x2 i es repeteix el procés fent servir x1 i x2 en comptes de x0 i x1. Es continua aquest procés, resolent per a x3, x4, etc., fins que s'àrriba a un nivell prou alt de precisió (una diferència prou petita entre xn i xn-1).

x_2=x_1-f(x_1)\frac{x_1-x_0}{f(x_1)-f(x_0)}
x_3=x_2-f(x_2)\frac{x_2-x_1}{f(x_2)-f(x_1)}
...
x_n=x_{n-1}-f(x_{n-1})\frac{x_{n-1}-x_{n-2}}{f(x_{n-1})-f(x_{n-2})}

Convergència[modifica | modifica el codi]

Les iteracions x n del mètode de la secant convergeixen a una arrel de f, si els valors inicials x0 i x1 són prou a la vora de l'arrel. L'ordre de convergència és α, on

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

és la secció àuria. En particular, la convergència és superlineal.

Aquest resultat només es compleix sota algunes condicions tècniques, és a dir que f sigui contínuament diferenciable dues vegades i l'arrel en qüestió sigui simple (és a dir, amb la multiplicitat 1).

Si els valors inicials no són a la vora de l'arrel, llavors no hi ha cap garantia que el mètode de secant convergeix.

Comparació amb altres mètodes de solució d'equacions[modifica | modifica el codi]

El mètode de secant no exigeix que l'arrel romangui encaixada dins del parell de punts com ho fa el mètode de la bisecció, i per això no sempre convergeix. El mètode de regula falsi fa servir la mateixa fórmula que el mètode de la secant. Tanmateix, no aplica la fórmula sobre x n−1 i x n, com el mètode de secant, sinó sobre xn i el punt de l'última iteració xk tal que f(xk) i f(x n) siguin de diferent signe. Això fa que el mètode de regula falsi sempre convergeixi.

La fórmula de recurrència del mètode de la secant es pot obtenir a partir de la fórmula del mètode de Newton

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

fent servir l'aproximació de diferència finita

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

Si es compara el mètode de Newton amb el mètode de la secant, es veu que el mètode de Newton convergeix més ràpid (ordre 2 enfront de α ≈ 1.6). Tanmateix, el mètode de Newton exigeix l'avaluació tant de f com de la seva derivada en tots els passos, mentre el mètode de la secant només exigeix l'avaluació de f. Per això, el mètode de la secant pot molt ben ser més ràpid a la pràctica. Per exemple, si se suposa que avaluar f pren tant temps com avaluar la seva derivada i es negligeixen tots els altres costos, es poden fer dos passos del mètode de la secant (disminuint el logaritme de l'error en un factor α² ≈ 2.6) pel mateix cost d'un pas en e mètode de Newton (disminuint el logaritme de l'error en un factor 2), així el mètode de la secant és més ràpid. Si tanmateix es considera el processament paral·lel per a l'avaluació de la derivada, el mètode de Newton presenta la seva vàlua, en ser més ràpid en temps, encara que continua condumint més passos.

Generalitzacions[modifica | modifica el codi]

El mètode de Broyden és una generalització del mètode de la secant a més d'una dimensió.

Codi exemple[modifica | modifica el codi]

El següent programa escrit en C s'ha escrit per claredat en comptes d'eficiència. Es va dissenyar per resoldre el mateix problema com el resol el mètode de Newton i el mètode de la falsa posició: per trobar el nombre positiu x tal que cos(x) = x 3. Aquest problema es transforma en un problema de càlcul de l'arrel de la forma f (x) = cos(x) − x 3 = 0.

En el codi següent, el mètode de la secant segueix fins que es doni una de dues condicions:

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

per a alguns valors de m i ε donats.

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

Després d'executar aquest codi, la resposta final és aproximadament 0.865474033101614. Les aproximacions inicials, intermèdies, i finals es llisten sota, els dígits correctes s'han subratllat.

 x_0 = 0  \,\!
 x_1 = 1  \,\!
 x_2 = 0.685073357326045  \,\!
 x_3 = 0.\underline{8}41355125665652  \,\!
 x_4 = 0.\underline{8}70353470875526  \,\!
 x_5 = 0.\underline{865}358300319342  \,\!
 x_6 = 0.\underline{86547}3486654304  \,\!
 x_7 = 0.\underline{8654740331}63012  \,\!
 x_8 = 0.\underline{865474033101614}  \,\!

El gràfic següent mostra la funció f en vermell i l'última recta secant en blau gruixut. Al gràfic, el punt x trobat per la recta secant sembla ser una bona aproximació de l'arrel de f.

Exemple

Codi de Matlab:

 function Xs = ArrelSecant(Fun,Xa,Xb,Err,imax) &nbsp;
 % ArrelSecant troba l'arrel de Fun = 0 fent servir el mètode de la secant. &nbsp;
 % Variables d'entrada: &nbsp;
 % Fun    Nom (cadena) d'un fitxer amb el programa que calcula Fun per a un x donat. &nbsp;
 % a, b   Dos punts propers a l'arrel (un a cada cantó, o tots dos &nbsp;
 %        al mateix cantó de l'arrel). &nbsp;
 % Err    Error màxim. &nbsp;
 % imax   Nombre màxim d'iteracions &nbsp;
 % Variable de sortida: &nbsp;
 % Xs     Solució &nbsp;
 for i = 1:imax &nbsp;
 FunXb = feval(Fun,Xb); &nbsp;
 Xi = Xb - FunXb*(Xa-Xb)/(feval(Fun,Xa)-FunXb); &nbsp;
 if abs((Xi - Xb)/Xb) < Err &nbsp;
 Xs = Xi; &nbsp;
 break &nbsp;
 end &nbsp;
 Xa = Xb; &nbsp;
 Xb = Xi; &nbsp;
 end &nbsp;
 if i == imax &nbsp;
 fprintf('La solució no s'ha trobat després de fer %i iteracions.\n',imax) &nbsp;
 Xs = ('Cap resposta'); &nbsp;
 end

Referències[modifica | modifica el codi]

  1. «www.allacademic.com». [Enllaç no actiu]

Enllaços externs[modifica | modifica el codi]