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é (VO)

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

Bibliographie

[1] Arioli, M., Pták, V., Strakoš, Z.: Krylov sequences of maximal length and convergence of GMRES. BIT 38 (1998), 636–643. | DOI | MR

[2] Axelsson, O., Barker, V. A.: Finite element solution of boundary value problems, theory and computations. Academic Press, Orlando, FL, 1984. | MR

[3] Benzi, M.: Preconditioning techniques for large linear systems: a survey. J. Comput. Phys. 182 (2002), 418–477. | DOI | MR

[4] Benzi, M., Tůma, M.: A comparative study of sparse approximate inverse preconditioners. Appl. Numer. Math. 30 (1999), 305–340. | DOI | MR

[5] Brandts, J., Křížek, M.: Padesát let metody konjugovaných gradienů aneb zvládnou počítače soustavy miliónů rovnic o miliónech neznámých?. Pokroky Mat. Fyz. Astronom. 47 (2002), 103–113.

[6] Brezinski, C.: History of continued fractions and Padé approximants. Springer Series in Computational Mathematics, vol. 12. Springer-Verlag, Berlin, 1991. | MR

[7] Carson, E., Rozložník, M., Strakoš, Z., Tichý, P., Tůma, M.: The numerical stability analysis of pipelined conjugate gradient methods: historical context and methodology. SIAM J. Sci. Comput. 40 (2018), A3549–A3580. | DOI | MR

[8] Carson, E., Strakoš, Z.: On the cost of iterative computations. Philos. Trans. Roy. Soc. A 378 (2020). | MR

[9] Concus, P., Golub, G. H., O'Leary, D. P.: A generalized conjugate gradient method for the numerical solution of elliptic partial differential equations. In: Bunch, J. R., Rose, D. J.: Sparse Matrix Computations, Academic Press, New York, 2018, 309–332. | MR

[10] Daniel, J. W.: The conjugate gradient method for linear and nonlinear operator equations. SIAM J. Numer. Anal. 4 (1967), 10–26. | DOI | MR | Zbl

[11] Duintjer Tebbens, J., Hnětynková, I., Plešinger, M., Strakoš, Z., Tichý, P.: Analýza metod pro maticové výpočty – základní metody. MatfyzPress, Praha, 2012.

[12] Engeli, M., Ginsburg, T., Rutishauser, H., Stiefel, E.: Refined iterative methods for computation of the solution and the eigenvalues of self-adjoint boundary value problems. Mitt. Inst. Angew. Math. Zürich 8, Birkhäuser, Basel, 1959. | MR

[13] Fischer, B.: Polynomial based iteration methods for symmetric linear systems. Wiley-Teubner Series Advances in Numerical Mathematics, John Wiley and Sons, Chichester, 1996. | MR

[14] Gergelits, T., Mardal, K.-A., Nielsen, B. F., Strakoš, Z.: Laplacian preconditioning of elliptic PDEs: Localization of the eigenvalues of the discretized operator. SIAM J. Numer. Anal. 57 (2019), 1369–1394. | DOI | MR

[15] Gergelits, T., Nielsen, B. F., Strakoš, Z.: Generalized spectrum of second order differential operators. SIAM J. Numer. Anal. 58 (2020), 2193–2211. | DOI | MR

[16] Gergelits, T., Strakoš, Z.: Composite convergence bounds based on Chebyshev polynomials and finite precision conjugate gradient computations. Numer. Algorithms 65 (2014), 759–782. | DOI | MR

[17] Greenbaum, A.: Behavior of slightly perturbed Lanczos and conjugate-gradient recurrences. Linear Algebra Appl. 113 (1989), 7–63. | DOI | MR

[18] Greenbaum, A.: Iterative methods for solving linear systems. Frontiers in Applied Mathematics, vol. 17. SIAM, Philadelphia, PA, 1997. | MR

[19] Greenbaum, A., Pták, V., Strakoš, Z.: Any nonincreasing convergence curve is possible for GMRES. SIAM J. Matrix Anal. Appl. 17 (1996), 465–469. | DOI | MR

[20] Greenbaum, A., Strakoš, Z.: Predicting the behavior of finite precision Lanczos and conjugate gradient computations. SIAM J. Matrix Anal. Appl. 13 (1992), 121–137. | DOI | MR

[21] Greenbaum, A., Strakoš, Z.: Matrices that generate the same Krylov residual spaces. In: Recent advances in iterative methods. IMA Vol. Math. Appl., vol. 60. Springer, New York, 1994, 95–118. | MR

[22] Hayes, R. M.: Iterative methods for solving linear problems in Hilbert space. PhD. Thesis. Univ. of California at Los Angeles, 1954.

[23] Hestenes, M. R., Stiefel, E.: Methods of conjugate gradients for solving linear systems. J. Research Nat. Bur. Standards 49 (1952), 409–436. | DOI | MR | Zbl

[24] Karush, W.: Convergence of a method for solving linear problems. Proc. Amer. Math. Soc. 3 (1952), 839–851. | DOI | MR

[25] Lanczos, C.: An iteration method for the solution of the eigenvalue problem of linear differential and integral operators. J. Research Nat. Bur. Standards 45 (1950), 255–282. | DOI | MR

[26] Lanczos, C.: Solution of systems of linear equations by minimized iterations. J. Research Nat. Bur. Standards 49 (1952), 33–53. | DOI | MR

[27] Lanczos, C.: Chebyshev polynomials in the solution of large-scale linear systems. In: Proceedings of the Association for Computing Machinery, Toronto, 1952, Sauls Lithograph Co., Washington, DC, 1953, 124–133. | MR

[28] Lanczos, C.: Why Mathematics?. Lecture given at the Annual Meeting of the Irish Mathematical Association on October 31, 1966, at Belfield, Dublin.

[29] Liesen, J., Strakoš, Z.: Krylov subspace methods: Principles and analysis. Oxford University Press, Oxford, 2013. | MR

[30] Ljusternik, L. A.: Solution of problems in linear algebra by the method of continued fractions. Trudy Voronezh. Gos. Inst., Voronezh 2 (1956), 85–90. | MR

[31] Málek, J., Strakoš, Z.: Preconditioning and the conjugate gradient method in the context of solving PDEs. SIAM Spotlights, vol. 1. SIAM, Philadelphia, PA, 2015. | MR

[32] Meurant, G., Strakoš, Z.: The Lanczos and conjugate gradient algorithms in finite precision arithmetic. Acta Numer. 15 (2006), 471–542. | DOI | MR

[33] Murphy, M. F., Golub, G. H., Wathen, A. J.: A note on preconditioning for indefinite linear systems. SIAM J. Sci. Comput. 21 (2000), 1969–1972. | DOI | MR

[34] Paige, C. C.: Accuracy and effectiveness of the Lanczos algorithm for the symmetric eigenproblem. Linear Algebra Appl. 34 (1980), 235–258. | DOI | MR

[35] Pearson, J. W., Pestana, J.: Preconditioned iterative methods for scientific applications. GAMM-Mitt., to appear (2020).

[36] Pozza, S., Strakoš, Z.: Algebraic description of the finite Stieltjes moment problem. Linear Algebra Appl. 561 (2019), 207–227. | DOI | MR

[37] Reid, J. K.: On the method of conjugate gradients for the solution of large sparse systems of linear equations. In: Large sparse sets of linear equations, Proc. Conf., St. Catherine’s Coll., Oxford, 1970, Academic Press, London, 1971, 231–254. | MR

[38] Rektorys, K.: Variační metody v inženýrských problémech a v problémech matematické fyziky. SNTL, Praha, 1974. | MR

[39] Saad, Y.: Iterative methods for sparse linear systems. 2nd ed., SIAM, Philadelphia, PA, 2003. | MR

[40] Stieltjes, T. J.: Recherches sur les fractions continues. Ann. Fac. Sci. Toulouse Sci. Math. Sci. Phys. 8 (1894), J. 1–122. Reprinted in Oeuvres II (P. Noordhoff, Groningen, 1918), 402–566. English translation Investigations on continued fractions. in Thomas Jan Stieltjes, Collected Papers, Vol. II, Springer-Verlag, Berlin, 1993, 609–745. | MR

[41] Strakoš, Z., Tichý, P.: On error estimation in the conjugate gradient method and why it works in finite precision computations. Electron. Trans. Numer. Anal. 13 (2002), 56–80. | MR

[42] Thurston, W.: On proof and progress in Mathematics. Bull. Amer. Math. Soc. 30 (1994), 161–177. | DOI | MR

[43] Vorobyev, Yu. V.: Methods of moments in applied mathematics. Translated from the Russian original published in 1958 by Bernard Seckler, Gordon and Breach Science Publishers, New York, 1965. | MR

[44] van der Vorst, H. A.: Preconditioning by incomplete decompositions. PhD Thesis. University of Utrecht, 1982.

[45] Wathen, A.: Preconditioning. Acta Numer. 24 (2015), 329–376. | DOI | MR

[46] Zeidler, E.: Oxford users' guide to mathematics. Oxford University Press, Oxford, 2004. Translated from the 1996 German original by Bruce Hunt. | MR