Metoda konjugovaných gradientů pro řešení systému lineárních rovnic s pozitivně definitní maticí

Úlohou je řešit , kde A je pozitivně definitní matice, tj. symetrická matice definující pozitivně definitní kvadratickou formu a tedy pro

Nechť je přesné řešení úlohy. Pak funkce má ^{minimum rovné 0 pro}

Poslední člen je konstanta (byť neznámá) a proto ho lze vynechat.

^{Proto i funkce má minimum pro}

Systém lineárních rovnic řešíme nalezením minima metodou konjugovaných gradientů

^{a tedy}

Počáteční odhad je a , při iteracích ^a ,

^{Minimalizací ve směru dostaneme , funkci vyjádříme}

a tedy

a tak k nalezení minima ve směru - násobení vektoru maticí a skal.součin

Pro řídké matice je násobení vektoru maticí velmi rychlé (řádu N a ne N²)