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 N2)