Pronzato, L., Zhigljavsky, Anatoly and Bukina, A. 2012. Estimation of spectral bounds in gradient algorithms. Acta Applicandae Mathematicae 127 (1) , pp. 117-136. 10.1007/s10440-012-9794-z |
Abstract
We consider the solution of linear systems of equations Ax=b, with A a symmetric positive-definite matrix in ℝ n×n , through Richardson-type iterations or, equivalently, the minimization of convex quadratic functions(1/2)(Ax,x)−(b,x) with a gradient algorithm. The use of step-sizes asymptotically distributed with the arcsine distribution on the spectrum of A then yields an asymptotic rate of convergence after k<n iterations, k→∞, that coincides with that of the conjugate-gradient algorithm in the worst case. However, the spectral bounds m and M are generally unknown and thus need to be estimated to allow the construction of simple and cost-effective gradient algorithms with fast convergence. It is the purpose of this paper to analyse the properties of estimators of m and M based on moments of probability measures ν k defined on the spectrum of A and generated by the algorithm on its way towards the optimal solution. A precise analysis of the behavior of the rate of convergence of the algorithm is also given. Two situations are considered: (i) the sequence of step-sizes corresponds to i.i.d. random variables, (ii) they are generated through a dynamical system (fractional parts of the golden ratio) producing a low-discrepancy sequence. In the first case, properties of random walk can be used to prove the convergence of simple spectral bound estimators based on the first moment of ν k . The second option requires a more careful choice of spectral bounds estimators but is shown to produce much less fluctuations for the rate of convergence of the algorithm.
Item Type: | Article |
---|---|
Status: | Published |
Schools: | Mathematics |
Subjects: | Q Science > QA Mathematics |
Uncontrolled Keywords: | Estimation of leading eigenvalues, Arcsine distribution, Gradient algorithms, Conjugate gradient, Fibonacci numbers |
Publisher: | Springer Netherlands |
ISSN: | 0167-8019 |
Last Modified: | 04 Jun 2017 09:02 |
URI: | http://orca.cf.ac.uk/id/eprint/89666 |
Citation Data
Cited 1 time in Scopus. View in Scopus. Powered By Scopus® Data
Actions (repository staff only)
Edit Item |