Mètode iteratiu
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 trobant la inversa de la matriu A, per exemple amb l'algorisme QMR). 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
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 convergirà cap a la solució x.
Sistemes lineals modifica
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 anomenats mètodes del subespai de Krylov.[1]
Mètodes iteratius estacionaris modifica
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
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
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 se 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
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.
Referències modifica
- ↑ Liesen, Jörg; Strakos, Zdenek. Krylov Subspace Methods. Oxford University Press, 2012-10-18, p. 12–70.
| A Wikimedia Commons hi ha contingut multimèdia relatiu a: Mètode iteratiu |