The Conjugate Gradient Method as a Journey Through Centuries

Zdeněk Strakoš

Pokroky matematiky, fyziky a astronomie (2020)

  • Volume: 65, Issue: 4, page 197-222
  • ISSN: 0032-2423

Abstract

top
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í 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 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.

How to cite

top

Strakoš, Zdeněk. "Metoda konjugovaných gradientů jako dobrodružství jdoucí přes staletí." Pokroky matematiky, fyziky a astronomie 65.4 (2020): 197-222. <http://eudml.org/doc/297138>.

@article{Strakoš2020,
abstract = {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í 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 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.},
author = {Strakoš, Zdeněk},
journal = {Pokroky matematiky, fyziky a astronomie},
language = {cze},
number = {4},
pages = {197-222},
publisher = {Jednota českých matematiků a fyziků},
title = {Metoda konjugovaných gradientů jako dobrodružství jdoucí přes staletí},
url = {http://eudml.org/doc/297138},
volume = {65},
year = {2020},
}

TY - JOUR
AU - Strakoš, Zdeněk
TI - Metoda konjugovaných gradientů jako dobrodružství jdoucí přes staletí
JO - Pokroky matematiky, fyziky a astronomie
PY - 2020
PB - Jednota českých matematiků a fyziků
VL - 65
IS - 4
SP - 197
EP - 222
AB - 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í 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 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.
LA - cze
UR - http://eudml.org/doc/297138
ER -

References

top
  1. Arioli, M., Pták, V., Strakoš, Z., 10.1007/BF02510405, . BIT 38 (1998), 636–643. (1998) MR1670196DOI10.1007/BF02510405
  2. Axelsson, O., Barker, V. A., Finite element solution of boundary value problems, theory and computations, . Academic Press, Orlando, FL, 1984. (1984) MR0758437
  3. Benzi, M., 10.1006/jcph.2002.7176, . J. Comput. Phys. 182 (2002), 418–477. (2002) MR1941848DOI10.1006/jcph.2002.7176
  4. Benzi, M., Tůma, M., 10.1016/S0168-9274(98)00118-4, . Appl. Numer. Math. 30 (1999), 305–340. (1999) MR1688632DOI10.1016/S0168-9274(98)00118-4
  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. (2002) 
  6. Brezinski, C., History of continued fractions and Padé approximants, . Springer Series in Computational Mathematics, vol. 12. Springer-Verlag, Berlin, 1991. (1991) MR1083352
  7. Carson, E., Rozložník, M., Strakoš, Z., Tichý, P., Tůma, M., 10.1137/16M1103361, . SIAM J. Sci. Comput. 40 (2018), A3549–A3580. (2018) MR3866570DOI10.1137/16M1103361
  8. Carson, E., Strakoš, Z., On the cost of iterative computations, . Philos. Trans. Roy. Soc. A 378 (2020). (2020) 
  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. (2018) MR0501821
  10. Daniel, J. W., 10.1137/0704002, . SIAM J. Numer. Anal. 4 (1967), 10–26. (1967) Zbl0154.40302MR0217987DOI10.1137/0704002
  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. (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. (1959) MR0145689
  13. Fischer, B., Polynomial based iteration methods for symmetric linear systems, . Wiley-Teubner Series Advances in Numerical Mathematics, John Wiley and Sons, Chichester, 1996. (1996) MR1449136
  14. Gergelits, T., Mardal, K.-A., Nielsen, B. F., Strakoš, Z., 10.1137/18M1212458, . SIAM J. Numer. Anal. 57 (2019), 1369–1394. (2019) MR3961990DOI10.1137/18M1212458
  15. Gergelits, T., Nielsen, B. F., Strakoš, Z., 10.1137/20M1316159, . SIAM J. Numer. Anal. 58 (2020), 2193–2211. (2020) MR4128499DOI10.1137/20M1316159
  16. Gergelits, T., Strakoš, Z., 10.1007/s11075-013-9713-z, . Numer. Algorithms 65 (2014), 759–782. (2014) MR3187962DOI10.1007/s11075-013-9713-z
  17. Greenbaum, A., 10.1016/0024-3795(89)90285-1, . Linear Algebra Appl. 113 (1989), 7–63. (1989) MR0978581DOI10.1016/0024-3795(89)90285-1
  18. Greenbaum, A., Iterative methods for solving linear systems, . Frontiers in Applied Mathematics, vol. 17. SIAM, Philadelphia, PA, 1997. (1997) MR1474725
  19. Greenbaum, A., Pták, V., Strakoš, Z., 10.1137/S0895479894275030, . SIAM J. Matrix Anal. Appl. 17 (1996), 465–469. (1996) MR1397238DOI10.1137/S0895479894275030
  20. Greenbaum, A., Strakoš, Z., 10.1137/0613011, . SIAM J. Matrix Anal. Appl. 13 (1992), 121–137. (1992) MR1146656DOI10.1137/0613011
  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. (1994) MR1332745
  22. Hayes, R. M., Iterative methods for solving linear problems in Hilbert space, . PhD. Thesis. Univ. of California at Los Angeles, 1954. (1954) 
  23. Hestenes, M. R., Stiefel, E., 10.6028/jres.049.044, . J. Research Nat. Bur. Standards 49 (1952), 409–436. (1952) Zbl0048.09901MR0060307DOI10.6028/jres.049.044
  24. Karush, W., 10.1090/S0002-9939-1952-0055794-4, . Proc. Amer. Math. Soc. 3 (1952), 839–851. (1952) MR0055794DOI10.1090/S0002-9939-1952-0055794-4
  25. Lanczos, C., 10.6028/jres.045.026, . J. Research Nat. Bur. Standards 45 (1950), 255–282. (1950) MR0042791DOI10.6028/jres.045.026
  26. Lanczos, C., 10.6028/jres.049.006, . J. Research Nat. Bur. Standards 49 (1952), 33–53. (1952) MR0051583DOI10.6028/jres.049.006
  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. (1953) MR0067580
  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. (2013) MR3024841
  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. (1956) MR0084856
  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. (2015) MR3307335
  32. Meurant, G., Strakoš, Z., 10.1017/S096249290626001X, . Acta Numer. 15 (2006), 471–542. (2006) MR2269746DOI10.1017/S096249290626001X
  33. Murphy, M. F., Golub, G. H., Wathen, A. J., 10.1137/S1064827599355153, . SIAM J. Sci. Comput. 21 (2000), 1969–1972. (2000) MR1762024DOI10.1137/S1064827599355153
  34. Paige, C. C., 10.1016/0024-3795(80)90167-6, . Linear Algebra Appl. 34 (1980), 235–258. (1980) MR0591433DOI10.1016/0024-3795(80)90167-6
  35. Pearson, J. W., Pestana, J., Preconditioned iterative methods for scientific applications, . GAMM-Mitt., to appear (2020). (2020) 
  36. Pozza, S., Strakoš, Z., 10.1016/j.laa.2018.09.026, . Linear Algebra Appl. 561 (2019), 207–227. (2019) MR3868647DOI10.1016/j.laa.2018.09.026
  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. (1971) MR0341836
  38. Rektorys, K., Variační metody v inženýrských problémech a v problémech matematické fyziky, . SNTL, Praha, 1974. (1974) MR0487652
  39. Saad, Y., Iterative methods for sparse linear systems, . 2nd ed., SIAM, Philadelphia, PA, 2003. (2003) MR1990645
  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. (1894) MR1508159
  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. (2002) MR1943611
  42. Thurston, W., 10.1090/S0273-0979-1994-00502-6, . Bull. Amer. Math. Soc. 30 (1994), 161–177. (1994) MR1249357DOI10.1090/S0273-0979-1994-00502-6
  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. (1965) MR0184400
  44. van der Vorst, H. A., Preconditioning by incomplete decompositions, . PhD Thesis. University of Utrecht, 1982. (1982) 
  45. Wathen, A., 10.1017/S0962492915000021, . Acta Numer. 24 (2015), 329–376. (2015) MR3349311DOI10.1017/S0962492915000021
  46. Zeidler, E., Oxford users' guide to mathematics, . Oxford University Press, Oxford, 2004. Translated from the 1996 German original by Bruce Hunt. (2004) MR3157455

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.