Mètode iteratiu

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

El mètode iteratiu en matemàtica computacional tracta de resoldre un problema (com una equació o un sistema d'equacions) mitjançant aproximacions successives a la solució, tot començant des d'una estimació inicial. Aquesta aproximació contrasta amb els mètodes directes, que tracten de resoldre el problema d'una sola vegada (com resoldre un sistema d'equacions Ax=b trobrant la inversa de la matriu A). Els mètodes iteratius són útils per resoldre problemes que involucren un nombre gran de variables (de vegades de l'ordre de milions), on els mètodes directes tindrien una despesa prohibitiva fins i tot amb la potència del millor computador disponible.

Punts fixos atractius[modifica | modifica el codi]

Si una equació pot posar-se en la forma f(x) = x, i una solució x és un punt fix atractiu de la funció f, aleshores pot començar amb un punt x1 a la base d'atracció de x, i sigui xn+1 = f(xn per a n ≥ 1, i la seqüència {xn}n ≥ 1 convergerà la solució x.

Sistemes lineals[modifica | modifica el codi]

En el cas d'un sistema d'equacions lineals, les dues classes principals de mètodes iteratius són els mètodes iteratius estacionaris i els més generals mètodes del subespai de Krylov.

Mètodes iteratius estacionaris[modifica | modifica el codi]

Els mètodes iteratius estacionaris resolen un sistema lineal amb un operador que s'apropa a l'original, i basant-se en la mitjana d'error (el residu), des d'una equació de correcció per a la qual es repeteix aquest procés. Mentre que aquests mètodes són senzills de derivar, implementar i analitzar, la convergència normalment només es garanteix per a una classe limitada de matrius.

Mètodes del subespai de Krylov[modifica | modifica el codi]

Els mètodes del subespai de Krylov formen una base ortogonal de la seqüència de potències de la matriu pel residu inicial (la seqüència de Krylov). Les aproximacions a la solució es formen minimitzant el residu en el subespai format. El mètode prototípic d'aquesta classe és el mètode de gradent conjugat. Altres mètodes són el mètode del residu mínim generalitzat i el mètode del gradent biconjugat.

Convergència[modifica | modifica el codi]

Ja que aquests mètodes formen una base, el mètode convergeix en N iteraccions, on N és la mida del sistema. Tanmateix, en la presència d'errors d'arrodoniment aquesta afirmació no es sosté. A més a més, a la pràctica N pot ser molt gran, i el procés iteratiu arriba a una precisió suficient molt abans. L'anàlisi d'aquests mètodes és difícil, depenent de com sigui de complicada la funció de l'espectre de l'operador.

Precondicionants[modifica | modifica el codi]

L'operador aproximatiu que apareix en els mètodes iteratius estacionaris pot incorporar-se també en els mètodes del subespai de Krylov, on es passen de ser transformacions de l'operador original a un operador millor acondicionat. La construcció de precondicionadors és una àrea d'investigació molt extensa.