Osnovni problem.

Želimo riješiti sustav linearnih algebarskih jednadžbi

$$a_{1\,1}\,x_1+a_{1\,2}\,x_2+\cdots+a_{1\,n}\,x_n = b_1$$

$$a_{2\,1}\,x_1+a_{2\,2}\,x_2+\cdots +a_{2\,n}\,x_n = b_2$$

$$\cdots$$

$$a_{n\,1}\,x_1+a_{n\,2}\,x_2+\cdots +a_{n\,n}\,x_n = b_n.$$

Primijetite da je broj jednadžbi jednak broju nepoznanica.

Matrično zapisan on glasi

$$A\,\boldsymbol{x} = \boldsymbol{b},$$

gdje je

$$% latex2html id marker 38553 A = \left[ \begin{array}{cccc}... ...ray}{c} x_1 \\ x_2 \\ \vdots \\ x_n \end{array} \right].$$

To je matrična jednadžba, i mi ćemo često o sustavu jednadžbi govoriti kao o jednadžbi, misleći na ovu matričnu jednadžbu. Pretpostavimo da je $A$ regularna matrica. Tada jednadžba ima rješenje, i označimo to rješenje sa $\boldsymbol{s}.$

Osnovna ideja iterativnih metoda se sastoji u sljedećem. Stavimo

$$A = B - C,$$

gdje su $B$ i $C$ također kvadratne matrice $n$-tog reda. Jednadžbu tada možemo prepisati kao

$$B\,\boldsymbol{x} = C\,\boldsymbol{x} + \boldsymbol{b}.$$

Ako s $\boldsymbol{x}^{(k)}$ označimo $k$-tu aproksimaciju rješenja, onda pomoću formule

$$B\,\boldsymbol{x}^{(k+1)} = C\,\boldsymbol{x}^{(k)} + \boldsymbol{b},$$

$$\boldsymbol{x}^{(k+1)} = B^{-1}\,C\,\boldsymbol{x}^{(k)} + B^{-1}\,\boldsymbol{b},$$

možemo naći $k+1$-vu aproksimaciju rješenja.

Naravno, da bi postupak uopće krenuo, treba biti zadana početna aproksimacija $\boldsymbol{x}_0.$ Nadalje, matrica $B$ mora biti regularna i relativno jednostavna, da bismo $\boldsymbol{x}^{(k+1)}$ mogli relativno jednostavno izračunati. Također postupak nas mora približavati k rješenju, tj. postupak mora biti takav da

$$\lim_{k\rightarrow{}\infty}\boldsymbol{x}^{(k)} = \boldsymbol{s}.$$

Opišimo sada neke od iterativnih metoda.