Algorisme de cerca d'arrels

En anàlisi numèrica, un algorisme de cerca d'arrels és un algorisme per trobar zeros, també anomenats "arrels", de funcions contínues. Un zero d'una funció f és un nombre x tal que f(x) = 0 Com que, en general, els zeros d'una funció no es poden calcular exactament ni expressar en forma tancada, els algorismes de cerca d'arrels proporcionen aproximacions als zeros. Per a funcions des dels nombres reals fins als nombres reals o des dels nombres complexos fins als nombres complexos, aquests s'expressen com a nombres de coma flotant sense límits d'error o com a valors de coma flotant juntament amb límits d'error. Aquestes últimes, aproximacions amb límits d'error, són equivalents a petits intervals d'aïllament per a arrels reals o discs per a arrels complexes.

Resoldre una equació f(x) = g(x) és el mateix que trobar les arrels de la funció h(x) = f(x) – g(x) . Per tant, els algorismes de cerca d'arrels es poden utilitzar per resoldre qualsevol equació de funcions contínues. Tanmateix, la majoria d'algorismes de cerca d'arrels no garanteixen que trobin totes les arrels d'una funció, i si aquest algorisme no troba cap arrel, això no vol dir necessàriament que no existeixi cap arrel.

La majoria dels mètodes numèrics per trobar arrels són mètodes iteratius, que produeixen una seqüència de nombres que idealment convergeix cap a una arrel com a límit . Requereixen una o més estimacions inicials de l'arrel com a valors inicials, i després cada iteració de l'algorisme produeix una aproximació successivament més precisa de l'arrel. Com que la iteració s'ha d'aturar en algun punt, aquests mètodes produeixen una aproximació a l'arrel, no una solució exacta. Molts mètodes calculen valors posteriors avaluant una funció auxiliar sobre els valors precedents. El límit és, doncs, un punt fix de la funció auxiliar, que s'escull per tenir les arrels de l'equació original com a punts fixos i per convergir ràpidament a aquests punts fixos.

El comportament dels algorismes generals de cerca d'arrels s'estudia en l'anàlisi numèrica. Tanmateix, per als polinomis específicament, l'estudi dels algorismes de cerca d'arrels pertany a l'àlgebra computacional, ja que les propietats algebraiques dels polinomis són fonamentals per als algorismes més eficients. L'eficiència i l'aplicabilitat d'un algorisme poden dependre sensiblement de les característiques de les funcions donades. Per exemple, molts algorismes utilitzen la derivada de la funció d'entrada, mentre que d'altres treballen en cada funció contínua. En general, els algorismes numèrics no garanteixen trobar totes les arrels d'una funció, de manera que no trobar una arrel no demostra que no hi hagi cap arrel. Tanmateix, per als polinomis, hi ha algorismes específics que utilitzen propietats algebraiques per certificar que no es perd cap arrel i per localitzar les arrels en intervals separats (o discs per a arrels complexes) que són prou petits per garantir la convergència dels mètodes numèrics (normalment el mètode de Newton) a l'arrel única dins de cada interval (o disc).

Mètodes de bracketing

Els mètodes de parèntesis determinen intervals successivament més petits (parèntesis) que contenen una arrel. Quan l'interval és prou petit, es considera que s'ha trobat una arrel. Aquests mètodes generalment utilitzen el teorema del valor intermedi, que afirma que si una funció contínua té valors de signes oposats als punts finals d'un interval, aleshores la funció té almenys una arrel a l'interval. Per tant, requereixen començar amb un interval tal que la funció prengui signes oposats als punts finals de l'interval. Tanmateix, en el cas dels polinomis hi ha altres mètodes com la regla dels signes de Descartes, el teorema de Budan i el teorema de Sturm per acotar o determinar el nombre d'arrels en un interval. Condueixen a algorismes eficients per a l'aïllament d'arrels reals de polinomis, que troben totes les arrels reals amb una precisió garantida.

Mètode de bisecció

L'algorisme de cerca d'arrels més simple és el mètode de bisecció. Sigui f una funció contínua per a la qual es coneix un interval [a, b] tal que f(a) i f(b) tenen signes oposats (un parèntesi). Sigui c = (a + b)/2 el mig de l'interval (el punt mig o el punt que bisecciona l'interval). Aleshores, o bé f(a) i f(c), o bé f(c) i f(b) tenen signes oposats, i s'ha dividit per dos la mida de l'interval. Tot i que el mètode de bisecció és robust, guanya un i només un bit de precisió amb cada iteració. Per tant, el nombre d'avaluacions de funcions necessàries per trobar una arrel ε -aproximada és $\log _{2}{\frac {b-a}{\varepsilon }}$ Altres mètodes, en condicions adequades, poden obtenir precisió més ràpidament.

Falsa posició (regula falsi)

El mètode de posició falsa, també anomenat mètode de la regula falsi, és similar al mètode de bisecció, però en comptes d'utilitzar el mig de l'interval de cerca de bisecció, utilitza la intersecció amb l'eix x de la línia que connecta els valors de la funció representats als extrems de l'interval, és a dir,

$c={\frac {af(b)-bf(a)}{f(b)-f(a)}}.$

La posició falsa és similar al mètode de la secant, excepte que, en comptes de retenir els dos últims punts, s'assegura de mantenir un punt a cada costat de l'arrel. El mètode de posició falsa pot ser més ràpid que el mètode de bisecció i mai divergirà com el mètode de la secant. Tanmateix, pot fallar en la convergència en algunes implementacions ingènues a causa d'errors d'arrodoniment que poden conduir a un signe incorrecte per a f(c) . Normalment, això pot passar si la derivada de f és gran al voltant de l'arrel.

Interpolació

Molts processos de cerca d'arrels funcionen per interpolació. Això consisteix a utilitzar els últims valors aproximats calculats de l'arrel per aproximar la funció mitjançant un polinomi de baix grau, que pren els mateixos valors en aquestes arrels aproximades. Aleshores, es calcula l'arrel del polinomi i s'utilitza com a nou valor aproximat de l'arrel de la funció, i el procés s'itereix.

La interpolació de dos valors produeix una recta: un polinomi de grau u. Aquesta és la base del mètode de la secant. La regula falsi també és un mètode d'interpolació que interpola dos punts alhora, però es diferencia del mètode de la secant en utilitzar dos punts que no són necessàriament els dos últims punts calculats. Tres valors defineixen una corba parabòlica: una funció quadràtica. Aquesta és la base del mètode de Muller.

Mètodes iteratius

Tot i que tots els algorismes de cerca d'arrels procedeixen per iteració, un mètode iteratiu de cerca d'arrels generalment utilitza un tipus específic d'iteració, que consisteix en definir una funció auxiliar, que s'aplica a les últimes aproximacions calculades d'una arrel per obtenir una nova aproximació. La iteració s'atura quan s'assoleix un punt fix de la funció auxiliar amb la precisió desitjada, és a dir, quan un nou valor calculat és prou proper als precedents.

Mètode de Newton (i mètodes similars basats en derivades)

El mètode de Newton assumeix que la funció f té una derivada contínua. El mètode de Newton pot no convergir si s'inicia massa lluny d'una arrel. Tanmateix, quan convergeix, és més ràpid que el mètode de bisecció; el seu ordre de convergència sol ser quadràtic, mentre que el del mètode de bisecció és lineal. El mètode de Newton també és important perquè es generalitza fàcilment a problemes de dimensions superiors. Els mètodes de Householder són una classe de mètodes semblants a Newton amb ordres de convergència superiors. El primer després del mètode de Newton és el mètode de Halley amb ordre de convergència cúbic.

Mètode de la secant

Si substituïm la derivada del mètode de Newton per una diferència finita, obtenim el mètode de la secant . Aquest mètode no requereix el càlcul (ni l'existència) d'una derivada, però el preu és una convergència més lenta (l'ordre de convergència és la proporció àuria, aproximadament 1,62). Una generalització del mètode de la secant en dimensions superiors és el mètode de Broyden.

Mètode de Steffensen

Si fem servir un ajust polinòmic per eliminar la part quadràtica de la diferència finita utilitzada en el mètode secant, de manera que aproximi millor la derivada, obtenim el mètode de Steffensen, que té convergència quadràtica, i el comportament del qual (tant bo com dolent) és essencialment el mateix que el mètode de Newton, però no requereix una derivada.

Mètode d'iteració de punt fix

Podem utilitzar la iteració de punt fix per trobar l'arrel d'una funció. Donada una funció $f(x)$ que hem posat a zero per trobar l'arrel ( $f(x)=0$ ), reescrivim l'equació en termes de $x$ de manera que $f(x)=0$ esdevé $x=g(x)$ (nota, sovint n'hi ha molts $g(x)$ funcions per a cadascuna $f(x)=0$ funció). A continuació, reetiquetem cada costat de l'equació com a $x_{n+1}=g(x_{n})$ per tal que puguem realitzar la iteració. A continuació, escollim un valor per a $x_{1}$ i realitzeu la iteració fins que convergeixi cap a una arrel de la funció. Si la iteració convergeix, convergirà a una arrel. La iteració només convergirà si $|g'(root)|<1$ .