Summary
We present an accelerated version of Cimmino's algorithm for solving the convex feasibility problem in finite dimension. The algorithm is similar to that given by Censor and Elfving for linear inequalities. We show that the nonlinear version converges locally to a weighted least squares solution in the general case and globally to a feasible solution in the consistent case. Applications to the linear problem are suggested.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Censor, Y.: Row-action methods for huge and sparse systems and their applications. SIAM Rev.23, 444–466 (1981)
Censor, Y., Elfving, T.: New methods for linear inequalities. Linear Algebra Appl.42, 199–211 (1982)
Censor, Y., Elfving, T.: A nonlinear Cimmino algorithm. Report 33, Department of Mathematics, University of Haifa 1981
Cimmino, G.: Calcolo approssimato per le soluzioni dei sistemi di equazioni lineari. Ric. Sci.1, 326–333 (1938)
De Pierro, A., Iusem, A.: A Simultaneous Projection Method for Linear Inequalities. Linear Algebra Appl.64, 243–253 (1985)
Elfving, T.: Block iterative methods for consistent and inconsistent linear equations. Numer. Math.33, 1–12 (1980)
Gastinel, N.: Analise Numérique Linéaire. Paris: Hermann 1970
Householder, A.S.: The Theory of Matrices in Numerical Analysis. New York: Dover Publications 1964
Kammerer, W.J., Nashed, M.Z.: A generalization of a matrix iterative method of G. Cimmino to best approximate solution of linear integral equation of the first kind. Rend. Accad. Naz. dei Lincei51, 20–25 (1971)
Luenberger, D.G.: Optimization by Vector Space Methods. New York: John Wiley 1969
Mangasarian, O.L.: Nonlinear Programming. New York: McGraw-Hill 1969
Nashed, M.Z.: Continuous and semicontinuous analogues of iterative methods of Cimmino and Kaczmarz with applications to the inverse Radon Transform. In. Mathematical Aspects of Computerized Tomography (G.T. Herman and F. Notherer, Eds.). Lect. Notes Med. Inf.8, 160–178 (1981)
Rockafeller, R.T.: Convex Analysis. Cambridge: University Press 1970
Tewarson, R.P.: Projection method for solving sparse linear systems. Comput. J.12, 77–80 (1969)
De Pierro, A., Iusem, A.: A Parallel Projection Method of Finding a Common Point of a Family of Convex Sets. Pesquisa Operacional, 1–20 (1985)
Censor, Y., Elfving, T., Herman, G.T.: Regularized least squares solution of linear inequalities. Technical Report No. MIPG97. Department of Radiology, University of Pennsylvania 1985
Gubin, L.G., Polyak, B.T., and Raik, E.V.: The method of projections for finding the common point of convex sets. USSR Comput. Math. Math. Phys.7, 1–24 (1967)
Herman, G.T., Lent, A., Hurwitz, H.: A storage-efficient algorithm for finding the regularized solution of a large inconsistent system of equations. J. Inst. Math. Appl.25, 361–366 (1980)
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Iusem, A.N., De Pierro, A.R. Convergence results for an accelerated nonlinear cimmino algorithm. Numer. Math. 49, 367–378 (1986). https://doi.org/10.1007/BF01389537
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF01389537