Gradientní metody

Lineární rovnici ${\bf A} \vec{x} = \vec{b}$ řešíme například minimalizací funkce
$f(\vec{x}) = \frac{1}{2}\vert{\bf A} \vec{x} - \vec{b}\vert^2$. V každém kroku $\lambda$ takové, aby $f(\vec{x} + \lambda \vec{u})$ bylo minimální. Tedy

$$\lambda = \frac{-\vec{u} \nabla f}{\vert{\bf A} \vec{u}\vert... ...\quad \nabla f(\vec{x}) = {\bf A}^T({\bf A} \vec{x} - \vec{b})$$

Pro řídké matice se složitost násobení vektoru maticí snižuje z počtu operací $\sim N^2$ na počet operací $\sim N$.

Pozn. Existuje řada moderních často používaných gradientních metod.