Metoda konjugovaných gradientů jako dobrodružství jdoucí přes staletí

Strakoš, Zdeněk

Pokroky matematiky, fyziky a astronomie, Tome 65 (2020) no. 4, pp. 197-222.

Résumé

Metoda konjugovaných gradientů a Lanczosova metoda tvoří historický a metodologický základ tzv. metod krylovovských podprostorů pro numerickou aproximaci řešení lineárních rovnic a částečnou aproximaci spektra lineárních operátorů. Ačkoliv jsou v obecném povědomí spojovány především s numerickým řešením velmi rozsáhlých soustav lineárních algebraických rovnic a aproximací vlastních čísel velkých matic, je přirozené uvažovat jejich formulaci v kontextu operátorů na Hilbertových prostorech (konečné či nekonečné dimenze). Ostatně ani v algebraické formulaci nemusí být matice soustavy vůbec sestavována, neboť výpočet používá pouze aplikaci odpovídajícího operátoru na vektor. Principiální vztah metody konjugovaných gradientů a Lanczosovy metody k problému momentů, k teorii ortogonálních polynomů, Jacobiho matic, řetězových zlomků a Gaussovy kvadratury z nich činí také objekt čistě matematického zájmu. Využití hlubokých matematických souvislostí postupně vedlo k pochopení \emph{adaptivního silně nelineárního chování} obou metod včetně vlivu aritmetiky s konečnou přesností na praktické výpočty. V nejlepším smyslu se zde setkává matematický a informatický pohled. Příležitost, kterou prolnutí obou oborů přináší, však není využita při zúženém chápání metody konjugovaných gradientů a Lanczosovy metody jako pouhých algoritmických výpočetních nástrojů, které je bohužel až na výjimky rozšířeno napříč literaturou. To má zhoubné důsledky. Pro většinu matematiků (a následně i vědců z jiných oborů, inženýrů a praktiků provádějících výpočty v aplikacích) dominuje v pojetí metody konjugovaných gradientů lineární odhad poklesu velikosti chyby \emph{odpovídající Čebyševově metodě}. Mnoho učebnicových popisů metody konjugovaných gradientů a stejně tak článků na ni odkazujících je pak zatíženo řadou mýtů, nedorozumění i nepřiznaných omylů. Matematicky zcela zmatečné je pojetí metody konjugovaných gradientů pro řešení lineárních rovnic, kdy jsou jednotlivé iterace těsně navzájem provázány podmínkou optimality na podprostorech rostoucí dimenze, jako zjednodušení gradientních metod pro řešení nelineárních rovnic. Příklad metody konjugovaných gradientů a Lanczosovy metody ukazuje, jak krásná a zároveň obtížná i úzká může být cesta k porozumění. Vede nás k trpělivosti a houževnatosti, ale hlavně nás učí pokoře.

Détail

Classification : 65F10, 65Fxx