The Method of Cholesky

Claude Brezinski

Revue d'histoire des mathématiques (2005)

  • Volume: 11, Issue: 2, page 205-238
  • ISSN: 1262-022X

Abstract

top
The purpose of this paper is to present the original manuscript, unknown until now, of Cholesky where he explains his method for solving systems of linear equations. After a brief biography, the historical context is specified. The method of least squares and its application to topography, and the various methods for the solution of linear systems are discussed. Then, the spreading of Cholesky’s method is reported, and a detailed analysis of Cholesky’s manuscript (entirely reproduced) is given. The other works in the fonds A.Cholesky of the École polytechnique are enumerated.

How to cite

top

Brezinski, Claude. "La méthode de Cholesky." Revue d'histoire des mathématiques 11.2 (2005): 205-238. <http://eudml.org/doc/252115>.

@article{Brezinski2005,
abstract = {L’objet de cet article est de présenter le manuscrit original, jusqu’alors inconnu, de Cholesky où il explique sa méthode de résolution des systèmes d’équations linéaires. Le contexte historique est précisé après une brève biographie. La méthode des moindres carrés et son application à la topographie, ainsi que les diverses méthodes directes de résolution des systèmes linéaires sont discutées. Ensuite, la diffusion de la méthode de Cholesky est retracée et l’on donne une analyse détaillée du manuscrit de Cholesky (qui est entièrement reproduit). Les autres travaux du fonds A.Cholesky de l’École polytechnique sont énumérés.},
author = {Brezinski, Claude},
journal = {Revue d'histoire des mathématiques},
keywords = {Cholesky method; linear systems; least squares; topography},
language = {fre},
number = {2},
pages = {205-238},
publisher = {Société mathématique de France},
title = {La méthode de Cholesky},
url = {http://eudml.org/doc/252115},
volume = {11},
year = {2005},
}

TY - JOUR
AU - Brezinski, Claude
TI - La méthode de Cholesky
JO - Revue d'histoire des mathématiques
PY - 2005
PB - Société mathématique de France
VL - 11
IS - 2
SP - 205
EP - 238
AB - L’objet de cet article est de présenter le manuscrit original, jusqu’alors inconnu, de Cholesky où il explique sa méthode de résolution des systèmes d’équations linéaires. Le contexte historique est précisé après une brève biographie. La méthode des moindres carrés et son application à la topographie, ainsi que les diverses méthodes directes de résolution des systèmes linéaires sont discutées. Ensuite, la diffusion de la méthode de Cholesky est retracée et l’on donne une analyse détaillée du manuscrit de Cholesky (qui est entièrement reproduit). Les autres travaux du fonds A.Cholesky de l’École polytechnique sont énumérés.
LA - fre
KW - Cholesky method; linear systems; least squares; topography
UR - http://eudml.org/doc/252115
ER -

References

top
  1. [1] R. Adrain, “Research concerning the probabilities of the errors which happen in making observations”, The Analyst or Mathematical Museum 1 (1808), p. 93-108 
  2. [2] R. Adrain, “Investigation of the figure of the earth and of the gravity in different latitudes”, Transactions of the American Philosophical Society (n.s.) 1 (1818), p. 119-135 
  3. [3] R. Adrain, “Research concerning the mean diameter of the earth”, Transactions of the American Philosophical Society (n.s.) 1 (1818), p. 353-366 
  4. [4] A. C. Aitken, “On the evaluation of determinants, the formation of their adjugates and the practical solution of simultaneous linear equations”, Proceedings of the Edinburgh Mathematical Society (2) 3 (1932), p. 207-219 JFM59.0536.02
  5. [5] T. Banachiewicz, Études d’analyse pratique, Cracow Observatory Reprint 22, University of Cracow, 1938 
  6. [6] T. Banachiewicz, “Principes d’une nouvelle technique de la méthode des moindres carrés. Méthode de résolution numérique des équations linéaires, du calcul des déterminants et des inverses, et de réduction des formes quadratiques”, Bulletin international de l’Académie polonaise des sciences et des lettres, Classe des sciences mathématiques, Série A (1938), p. 134-135, 393-404 Zbl0021.24101JFM65.0529.02
  7. [7] C. Benoît, “Note sur une méthode de résolution des équations normales provenant de l’application de la méthode des moindres carrés à un système d’équations linéaires en nombre inférieur à celui des inconnues (procédé du commandant Cholesky)”, Bulletin géodésique 2 (1924), p. 67-77 
  8. [8] C. Brezinski & M. Gross-Cholesky, “La vie et les travaux d’André-Louis Cholesky”, Bulletin de la Société des amis de la bibliothèque de l’École polytechnique (2005), p. 7-31 
  9. [9] Å. Björck, Numerical Methods for Least Squares Problems, SIAM, 1996 Zbl0847.65023MR1386889
  10. [10] C. Brezinski, “Géodésie, topographie et cartographie”, Bulletin de la Société des amis de la bibliothèque de l’École polytechnique 39 (2005), p. 33-66 
  11. [11] J.-L. Chabert & , Histoires d’algorithmes. Du caillou à la puce, Belin, 1994 Zbl0922.01005MR1413044
  12. [12] A. L. Cholesky, Cours de topographie. 2e partie : Topographie générale, École spéciale des travaux publics, 1937 
  13. [13] B.-I. Clasen, “Sur une nouvelle méthode de résolution des équations linéaires et sur l’application de cette méthode au calcul des déterminants”, Annales de la Société scientifique de Bruxelles (2) 12 (1888), p. 251-281 JFM20.0143.04
  14. [14] P. D. Crout, “A short method for evaluating determinants and solving systems of linear equations with real or complex coefficients”, Transactions of the American Institute of Electrical Engineers 60 (1941), p. 1235-1240 
  15. [15] P. D. Crout, A short method for evaluating determinants and solving systems of linear equations with real or complex coefficients, Marchant Methods MM-182, Sept.1941, Marchant Calculating Machine Co., 1941 
  16. [16] W. De Sitter, “Determination of the mass of Jupiter and elements of the orbits of its satellites from observations made with the Cape heliometer by Sir David Gill, K.C.B., and W.H. Finlay, M.A., part I”, Annals of the Cape Observatory 12 (1915) 
  17. [17] M. H. Doolittle, Method employed in the solution of normal equations and the adjustment of a triangulation, in: U.S. Coast and Geodetic Survey Report, 1878, p. 115-120 
  18. [18] H. Duquenne, Méthode des moindres carrés. Application aux travaux de géodésie, cours polycopié, Institut géographique national, École nationale des sciences géographiques, 1986 
  19. [19] P. S. Dwyer, “The Doolittle technique”, Annals of Mathematical Statistics 12 (1941), p. 449-458 Zbl0061.27201MR6232
  20. [20] P. S. Dwyer, “The solution of simultaneous equations”, Psychometrika 6 (1941), p. 101-129 Zbl0063.01202MR4376
  21. [21] P. S. Dwyer, “A matrix presentation of least squares and correlation theory with matrix justification of improved methods of solution”, Annals of Mathematical Statistics 15 (1944), p. 82-89 Zbl0061.39202MR10062
  22. [22] P. S. Dwyer, Linear Computations, Wiley, 1951 Zbl0044.12804
  23. [23] L. Eyrolles, E. Prévot & É. Quanon, Cours de topographie. Livre I : Topométrie, Eyrolles, 1909 
  24. [24] L. Fox, H. D. Huskey & J. H. Wilkinson, “Notes on the solution of algebraic linear simultaneous equations”, Quarterly Journal of Mechanics and Applied Mathematics 1 (1948), p. 149-173 Zbl0033.28503MR26421
  25. [25] C. F. Gauss, Theoria motus corporum coelestium in sectionibus solem ambientium, Perthes & Besser, 1809, [Gauss, Werke], vol.7 
  26. [26] C. F. Gauss, “Disquisitio de elementis ellipticis Palladis ex oppositionibus annorum 1803, 1804, 1805, 1807, 1808, 1809”, Commentationes societatis regiæ scientiarum Gottingensis recentiores 1 (1811), p. 1-24 
  27. [27] C. F. Gauss, “Theoria combinationis observationum erroribus minimis obnoxiae, deuxième partie”, Commentationes societatis regiæ scientiarum Gottingensis recentiores 5 (1823), p. 313-318 
  28. [28] C. F. Gauss, Werke, hg. von der Königlichen Gesellschaft der Wissenschaften zu Göttingen, 1863-1933 JFM55.0611.02
  29. [29] P. Goix, Topographie, CRDP de l’Académie de Grenoble, 2001 
  30. [30] H. H. Goldstine, A History of Numerical Analysis from the 16th through the 19th Century, Springer, 1977 Zbl0402.01005MR484905
  31. [31] F. R. Helmert, Die Ausgleichungsrechnung nach der Methode der kleinsten Quadrate mit Anwendung auf die Geodäsie, die Physik und die Theorie der Messinstrumente, Teubner, 1872 Zbl38.0276.01JFM38.0276.01
  32. [32] H. Hotelling, “Some new methods in matrix calculations”, Annals of Mathematical Statistics 14 (1943), p. 1-34 Zbl0061.27007MR7851
  33. [33] C. G. J. Jacobi, “Über eine elementare Transformation eines in Bezug jedes von zwei Variablen-Systemen linearen und homogenen Ausdrucks”, Journal für die reine und angewandte Mathematik 53 (1857), p. 265-270 
  34. [34] H. Jensen, An Attempt at a Systematic Classification of some Methods for the Solution of Normal Equations, Geodætisk Institut København, Meddelelse No. 18, 45p., Bianco Lunos Bogtrykkeri A/S, 1944 Zbl0061.39105MR15921
  35. [35] W. Jordan, Handbuch der Vermessungskunde. Bd. 1 : Ausgleichungs-Rechnung nach der Methode der kleinsten Quadrate, Metzler, 1888 Zbl0013.14402JFM26.1075.01
  36. [36] M.-F. Jozeau, “Géodésie au XIXe siècle. De l’hégémonie française à l’hégémonie allemande. Regards belges. Compensation et méthode des moindres carrés”, Ph. D. Thesis, Université Paris 7, 1997 
  37. [37] A. N. Kolmogorov & A.-A. P. Yushkevich (ed.), Mathematics of the 19th Century. Mathematical Logic, Algebra, Number Theory, Probability Theory, Birkhäuser, 1992 Zbl0749.01016MR1174343
  38. [38] J.-L. Lagrange, “Recherches sur la méthode des maximis et minimis”, Miscellanea philosophico-mathematica societatis privatæ Taurinensis 1 (1759), p. 18-32 
  39. [39] C. Lallemand, Compensation d’un réseau de nivellements par la méthode des coefficients indéterminés, Béranger, 1912 
  40. [40] A.-M. Legendre, Nouvelles méthodes pour la détermination des orbites des comètes, Courcier, 1806 
  41. [41] J. Meinguet, “Refined error analysis of Cholesky factorization”, SIAM Journal of Numerical Analysis 20 (1983), p. 1243-1250 Zbl0528.65014MR723842
  42. [42] P. Merlin, La Topographie, Que-Sais-Je ? 744, Presses universitaires de France, 1964 
  43. [43] M. d. Ocagne, Vue d’ensemble sur les machines à calculer, Gauthier-Villars, 1922 Zbl48.0622.02JFM48.0622.02
  44. [44] P. Pizzetti & H. A. Noirel, Géodésie, in: Encyclopédie des sciences mathématiques pures et appliquées, VI.1, Gauthier-Villars, Paris, 1916 JFM42.0126.02
  45. [45] R. Serre, Compensation par moindres carrés, cours polycopié, Institut géographique national, École nationale des sciences géographiques, 2000 
  46. [46] O. B. Sheynin, “C.F. Gauss and the theory of errors”, Archive for History of Exact Sciences 20 (1979), p. 21-72 Zbl0424.01006MR527657
  47. [47] O. B. Sheynin, “C.F. Gauss and geodetic observation”, Archive for History of Exact Sciences 46 (1994), p. 253-283 Zbl0793.01009MR1260317
  48. [48] G. W. Stewart, Gauss, statistics, and Gaussian elimination, in: Computing Science and Statistics (J. Sall & A. Lehman ed.), 26 : Computationally Intensive Statistical Methods, Interface Foundation of North America, Fairfax Station, VA, 1994, p. 1-7 MR1323053
  49. [49] J. Todd, The prehistory and early history of computation at the U.S. National Bureau of Standards, in: A History of Scientific Computing (S. G. Nash ed.), ACM Press, New York, 1990, p. 251-268 MR1203110
  50. [50] O. Toeplitz, “Die Jacobische Transformation der quadratischen Formen von unendlich vielen Veränderlichen”, Nachrichten der Akademie der Wissenschaften in Göttingen. II. Mathematisch-Physikalische Klasse (1907), p. 101-110 Zbl38.0156.01JFM38.0156.01
  51. [51] O. Taussky-Todd & J. Todd, Cholesky, Toeplitz and the triangular factorization of symmetric matrices, Zbl1093.65030
  52. [52] A. M. Turing, “Rounding-off errors in matrix processes”, Quarterly Journal of Mechanics and Applied Mathematics 1 (1948), p. 287-308 Zbl0033.28501MR28100
  53. [53] F. V. Waugh, “A simplified method of determining multiple regression constants”, Journal of the American Statistical Association 30 (1935), p. 694-700 Zbl0015.36202JFM61.1305.06

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.