La méthode de Cholesky

Brezinski, Claude

Revue d'histoire des mathématiques, Tome 11 (2005) no. 2, pp. 205-238.

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.

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.

Mot clés : méthode de Cholesky, systèmes linéaires, moindres carrés, topographie
Keywords: Cholesky method, linear systems, least squares, topography

[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] 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] R. Adrain, “Research concerning the mean diameter of the earth”, Transactions of the American Philosophical Society (n.s.) 1 (1818), p. 353-366

[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 | JFM

[5] T. Banachiewicz, Études d'analyse pratique, Cracow Observatory Reprint 22, University of Cracow, 1938

[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 | JFM | Zbl

[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] 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] Å. Björck, Numerical Methods for Least Squares Problems, SIAM, 1996 | MR | Zbl

[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] J.-L. Chabert & , Histoires d'algorithmes. Du caillou à la puce, Belin, 1994 | MR | Zbl

[12] A. L. Cholesky, Cours de topographie. 2e partie : Topographie générale, École spéciale des travaux publics, 1937

[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 | JFM

[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] 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] 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] 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] 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] P. S. Dwyer, “The Doolittle technique”, Annals of Mathematical Statistics 12 (1941), p. 449-458 | MR | Zbl

[20] P. S. Dwyer, “The solution of simultaneous equations”, Psychometrika 6 (1941), p. 101-129 | MR | Zbl

[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 | MR | Zbl

[22] P. S. Dwyer, Linear Computations, Wiley, 1951 | Zbl

[23] L. Eyrolles, E. Prévot & É. Quanon, Cours de topographie. Livre I : Topométrie, Eyrolles, 1909

[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 | MR | Zbl

[25] C. F. Gauss, Theoria motus corporum coelestium in sectionibus solem ambientium, Perthes & Besser, 1809, [Gauss, Werke], vol.7

[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] C. F. Gauss, “Theoria combinationis observationum erroribus minimis obnoxiae, deuxième partie”, Commentationes societatis regiæ scientiarum Gottingensis recentiores 5 (1823), p. 313-318

[28] C. F. Gauss, Werke, hg. von der Königlichen Gesellschaft der Wissenschaften zu Göttingen, 1863-1933 | JFM

[29] P. Goix, Topographie, CRDP de l'Académie de Grenoble, 2001

[30] H. H. Goldstine, A History of Numerical Analysis from the 16th through the 19th Century, Springer, 1977 | MR | Zbl

[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 | JFM

[32] H. Hotelling, “Some new methods in matrix calculations”, Annals of Mathematical Statistics 14 (1943), p. 1-34 | MR | Zbl

[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 | Zbl

[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 | MR | Zbl

[35] W. Jordan, Handbuch der Vermessungskunde. Bd. 1 : Ausgleichungs-Rechnung nach der Methode der kleinsten Quadrate, Metzler, 1888 | JFM | Zbl

[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] A. N. Kolmogorov & A.-A. P. Yushkevich (ed.), Mathematics of the 19th Century. Mathematical Logic, Algebra, Number Theory, Probability Theory, Birkhäuser, 1992 | MR | Zbl

[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] C. Lallemand, Compensation d'un réseau de nivellements par la méthode des coefficients indéterminés, Béranger, 1912

[40] A.-M. Legendre, Nouvelles méthodes pour la détermination des orbites des comètes, Courcier, 1806

[41] J. Meinguet, “Refined error analysis of Cholesky factorization”, SIAM Journal of Numerical Analysis 20 (1983), p. 1243-1250 | MR | Zbl

[42] P. Merlin, La Topographie, Que-Sais-Je ? 744, Presses universitaires de France, 1964

[43] M. D. Ocagne, Vue d'ensemble sur les machines à calculer, Gauthier-Villars, 1922 | JFM

[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 | JFM

[45] R. Serre, Compensation par moindres carrés, cours polycopié, Institut géographique national, École nationale des sciences géographiques, 2000

[46] O. B. Sheynin, “C.F. Gauss and the theory of errors”, Archive for History of Exact Sciences 20 (1979), p. 21-72 | MR | Zbl

[47] O. B. Sheynin, “C.F. Gauss and geodetic observation”, Archive for History of Exact Sciences 46 (1994), p. 253-283 | MR | Zbl

[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 | MR

[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 | MR

[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 | JFM

[51] O. Taussky-Todd & J. Todd, Cholesky, Toeplitz and the triangular factorization of symmetric matrices, | Zbl

[52] A. M. Turing, “Rounding-off errors in matrix processes”, Quarterly Journal of Mechanics and Applied Mathematics 1 (1948), p. 287-308 | MR | Zbl

[53] F. V. Waugh, “A simplified method of determining multiple regression constants”, Journal of the American Statistical Association 30 (1935), p. 694-700 | JFM | Zbl