對算法收斂速度的研究何時開始?


1

我正在讀一本關於計算複雜性理論的書,作者聲稱對算法的時間複雜性的研究始於對euclid算法所需的運算次數的上限的加布里埃爾·拉梅(GabrielLamé)在2000年提出的結果。1800年代初期/中期。由於算法收斂速度的分析也可以看作是一種原始時間的複雜性分析,並且至少可以追溯到拉格朗日,我想知道它們是否早於拉格朗日。

4

Rate of convergence estimates are typically not counted as estimating complexity of algorithms because the relation between number of steps in them and computational complexity is not very straightforward. And the algebraic analysis conceptions of 18th century make comparisons to the modern complexity theory even more remote, see Was 18th century algebra more symbolic/formal than the modern conception? This is likely why its origins are only traced to the work of Reynaud (1811), Finck (1841) and Lame (1844) on the Euclidean algorithm, where both issues are absent.

However, both the rate of convergence and its speed up were commonplace in the investigation of series in the early 18th century, albeit not in the way resembling the modern one. Ferraro has two papers Convergence and Formal Manipulation of Series from the Origins of Calculus to About 1730 and Convergence and formal manipulation in the theory of series from 1730 to 1815, on the subject.

For example, Jacob Bernoulli explicitly introduced and estimated remainders for the geometric series and the Mercator method in Ars Conjectandi (1713). But these sorts of considerations happily coexisted with the formal conception of series and manipulating divergent series, which got him in trouble with the "sum" of inverse square roots. Attempts to improve rates of convergence themselves often involved formal manipulations, and led to the appearance of divergent asymptotic series, as in Stirling's Methodus Differentialis (1730). Even d'Alembert, who criticized the use of divergent series and made detailed rate of convergence estimates for the binomial series in Réflexions sur les Suites et sur les Racines Imaginaires (1768), was no exception.

"Although N. Bernoulli's and d'Alembert's conception might seem close to modern ideas about series, it was in fact rather problematic... I stress that d'Alembert accepted the principle of formal manipulation upon which the early theory was based: this was precisely the principle that had led to asymptotic series, recurrent series, etc. In particular, d'Alembert did not consider series as autonomous objects but the result of transformations of given closed analytical expressions. Although it is true that d'Alembert used the inequality technique, it was only a tool for the numerical evaluation of a function. In no case was this technique used to prove the existence of a limit. D’Alembert had no knowledge of the ratio test, if by this term we refer to a criterion to establish whether a given series has a finite sum or not. For him the condition $a_{n+1}/a_n < 1$ served to establish where the series approximated its known sum: the “ratio test” was not used to prove the existence of the sum but was only a procedure to determine the bounds of errors. In conclusion, criticisms of the use of divergent series were weak because all mathematicians used formal procedures even if some of them, such as Euler, Lagrange, and Laplace, used them in a stronger form."

This said, Lagrange did publish two long papers on the numerical solution of equations in 1769/70, and continued to work on the subject with his work eventually summarized in his book Traite de la Resolution des Equations Numeriques de Tous les Degres (1798, revised 1808). There is also a chapter on them in his Lectures on Elementary Mathematics, translated into English. He paid special attention to the rate of convergence and accelerating it, both for series and continued fractions. In particular, he replaced Newton's method with a continued fractions based one that provided error estimates, and introduced generalized continued fractions to speed up the convergence, see Lagrange and the Solution of Numerical Equations by Laubenbacher and McGrath.