{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T17:42:18Z","timestamp":1776793338018,"version":"3.51.2"},"reference-count":55,"publisher":"American Mathematical Society (AMS)","issue":"275","license":[{"start":{"date-parts":[[2011,11,30]],"date-time":"2011-11-30T00:00:00Z","timestamp":1322611200000},"content-version":"am","delay-in-days":365,"URL":"https:\/\/www.ams.org\/publications\/copyright-and-permissions"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Comp."],"abstract":"<p>\n                    We present a new implementation of the almost optimal Circumscribed Ellipsoid (CE) Algorithm for approximating fixed points of nonexpanding functions, as well as of functions that may be globally expanding, however, are nonexpanding\/contracting in the direction of fixed points. Our algorithm is based only on function values, i.e., it does not require computing derivatives of any order. We utilize the absolute and residual termination criteria with respect to the second norm. The numerical results confirm that the CE algorithm is much more efficient than the simple iteration algorithm whenever the Lipschitz constant is close to 1. We also compare it with the Newton-Raphson method. In some tests the Newton-Raphson method is more efficient than the CE method, especially when the problem size is large. However, the CE algorithm is an excellent method for low dimensional functions with discontinuities and\/or low regularity. Our implementation can be downloaded from http:\/\/www.cs.utah.edu\/\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"tilde\">\n                        <mml:semantics>\n                          <mml:mo>\n                            \u223c\n                            \n                          <\/mml:mo>\n                          <mml:annotation encoding=\"application\/x-tex\">\\sim<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    sikorski\/cea.\n                  <\/p>","DOI":"10.1090\/s0025-5718-2010-02443-3","type":"journal-article","created":{"date-parts":[[2010,12,29]],"date-time":"2010-12-29T14:39:54Z","timestamp":1293633594000},"page":"1703-1723","source":"Crossref","is-referenced-by-count":0,"title":["Circumscribed ellipsoid algorithm for fixed-point problems"],"prefix":"10.1090","volume":"80","author":[{"given":"C.","family":"Boonyasiriwat","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"K.","family":"Sikorski","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"C.","family":"Tsay","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"14","published-online":{"date-parts":[[2010,11,30]]},"reference":[{"key":"1","unstructured":"A. Ageev, V. Vassin, E.N. Bessonova, and V.M. Markusevich, Radiosounding ionosphere on two frequencies. Algorithmic analysis of fredholm-stiltjes integral equation, in: Theoretical problems in geophysics (in Russian), (1997), 100\u2013118."},{"key":"2","first-page":"87","article-title":"Application of a fixed point search algorithm to nonlinear boundary value problems having several solutions","author":"Allgower, E. L.","year":"1977"},{"key":"3","series-title":"Springer Series in Computational Mathematics","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-61257-2","volume-title":"Numerical continuation methods","volume":"13","author":"Allgower, Eugene L.","year":"1990","ISBN":"https:\/\/id.crossref.org\/isbn\/3540127607"},{"key":"4","series-title":"Topological Fixed Point Theory and Its Applications","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-94-017-0407-6","volume-title":"Topological fixed point principles for boundary value problems","volume":"1","author":"Andres, Jan","year":"2003","ISBN":"https:\/\/id.crossref.org\/isbn\/1402013809"},{"key":"5","doi-asserted-by":"crossref","unstructured":"S. Banach, Sur les op\u00e9rations dans les ensembles abstraits et leur application aux \u00e9quations integrales, Fund. Math. 3 (1922), 133\u2013181.","DOI":"10.4064\/fm-3-1-133-181"},{"issue":"6","key":"6","doi-asserted-by":"publisher","first-page":"1039","DOI":"10.1287\/opre.29.6.1039","article-title":"The ellipsoid method: a survey","volume":"29","author":"Bland, Robert G.","year":"1981","journal-title":"Oper. Res.","ISSN":"https:\/\/id.crossref.org\/issn\/0030-364X","issn-type":"print"},{"key":"7","unstructured":"C. Boonyasiriwat, Circumscribed ellipsoid algorithm for fixed point problems, Master\u2019s thesis, University of Utah, Salt Lake City, UT, 2004."},{"issue":"4-6","key":"8","doi-asserted-by":"publisher","first-page":"952","DOI":"10.1016\/j.jco.2007.04.004","article-title":"A note on two fixed point problems","volume":"23","author":"Boonyasiriwat, Ch.","year":"2007","journal-title":"J. Complexity","ISSN":"https:\/\/id.crossref.org\/issn\/0885-064X","issn-type":"print"},{"key":"9","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511625756","volume-title":"Fixed point theorems with applications to economics and game theory","author":"Border, Kim C.","year":"1985","ISBN":"https:\/\/id.crossref.org\/isbn\/0521265649"},{"issue":"2","key":"10","doi-asserted-by":"publisher","first-page":"174","DOI":"10.1145\/264029.264032","article-title":"Algorithm 768: TENSOLVE: a software package for solving systems of nonlinear equations and nonlinear least-squares problems using tensor methods","volume":"23","author":"Bouaricha, Ali","year":"1997","journal-title":"ACM Trans. Math. Software","ISSN":"https:\/\/id.crossref.org\/issn\/0098-3500","issn-type":"print"},{"key":"11","doi-asserted-by":"crossref","unstructured":"L. E. Brouwer, \u00dcber abbildungen von mannigfaltigkeiten, Mathematische Annalen (1912), no. 71, 97\u2013115.","DOI":"10.1007\/BF01456931"},{"issue":"1","key":"12","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1007\/BF01396012","article-title":"Rank-one modification of the symmetric eigenproblem","volume":"31","author":"Bunch, James R.","year":"1978","journal-title":"Numer. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0029-599X","issn-type":"print"},{"issue":"2","key":"13","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1016\/0167-2789(90)90038-Q","article-title":"Chaos and continued fractions","volume":"46","author":"Corless, R. M.","year":"1990","journal-title":"Phys. D","ISSN":"https:\/\/id.crossref.org\/issn\/0167-2789","issn-type":"print"},{"key":"14","isbn-type":"print","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1145\/1060590.1060638","article-title":"On algorithms for discrete and approximate Brouwer fixed points [extended abstract]","author":"Chen, Xi","year":"2005","ISBN":"https:\/\/id.crossref.org\/isbn\/1581139608"},{"issue":"2","key":"15","doi-asserted-by":"publisher","first-page":"S139--S154","DOI":"10.1137\/0908018","article-title":"A fully parallel algorithm for the symmetric eigenvalue problem","volume":"8","author":"Dongarra, J. J.","year":"1987","journal-title":"SIAM J. Sci. Statist. Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0196-5204","issn-type":"print"},{"key":"16","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF01584975","article-title":"Homotopies for computation of fixed points","volume":"3","author":"Eaves, B. Curtis","year":"1972","journal-title":"Math. Programming","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5610","issn-type":"print"},{"key":"17","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1007\/BF01584991","article-title":"Homotopies for computation of fixed points on unbounded regions","volume":"3","author":"Eaves, B. Curtis","year":"1972","journal-title":"Math. Programming","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5610","issn-type":"print"},{"key":"18","first-page":"227","article-title":"Simplicial approximation of an equilibrium point for non-cooperative \ud835\udc41-person games","author":"Garc\u00eda, C. B.","year":"1973"},{"key":"19","doi-asserted-by":"publisher","first-page":"318","DOI":"10.1137\/1015032","article-title":"Some modified matrix eigenvalue problems","volume":"15","author":"Golub, Gene H.","year":"1973","journal-title":"SIAM Rev.","ISSN":"https:\/\/id.crossref.org\/issn\/1095-7200","issn-type":"print"},{"issue":"4","key":"20","doi-asserted-by":"publisher","first-page":"1266","DOI":"10.1137\/S089547989223924X","article-title":"A stable and efficient algorithm for the rank-one modification of the symmetric eigenproblem","volume":"15","author":"Gu, Ming","year":"1994","journal-title":"SIAM J. Matrix Anal. Appl.","ISSN":"https:\/\/id.crossref.org\/issn\/0895-4798","issn-type":"print"},{"issue":"4","key":"21","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1016\/0885-064X(89)90017-4","article-title":"Exponential lower bounds for finding Brouwer fixed points","volume":"5","author":"Hirsch, Michael D.","year":"1989","journal-title":"J. Complexity","ISSN":"https:\/\/id.crossref.org\/issn\/0885-064X","issn-type":"print"},{"issue":"3","key":"22","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1007\/BF01389489","article-title":"Attractive cycles in the iteration of meromorphic functions","volume":"46","author":"Howland, James Lucien","year":"1985","journal-title":"Numer. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0029-599X","issn-type":"print"},{"issue":"2","key":"23","doi-asserted-by":"publisher","first-page":"200","DOI":"10.1006\/jcom.1999.0504","article-title":"Approximating fixed points of weakly contracting mappings","volume":"15","author":"Huang, Z.","year":"1999","journal-title":"J. Complexity","ISSN":"https:\/\/id.crossref.org\/issn\/0885-064X","issn-type":"print"},{"key":"24","first-page":"122","article-title":"A search for the fixed points of a continuous mapping","author":"Jeppson, Mark","year":"1972"},{"issue":"2","key":"25","first-page":"1","article-title":"A polynomial algorithm in linear programming","author":"Khachiyan, L. G.","year":"1980","journal-title":"Yingyong Shuxue yu Jisuan Shuxue"},{"issue":"1","key":"26","first-page":"51","article-title":"Polynomial algorithms in linear programming","volume":"20","author":"Ha\u010dijan, L. G.","year":"1980","journal-title":"Zh. Vychisl. Mat. i Mat. Fiz.","ISSN":"https:\/\/id.crossref.org\/issn\/0044-4669","issn-type":"print"},{"key":"27","unstructured":"O. H. Merril, Application and extensions of an algorithm that computes fixed points of a certain upper semi-continuous point of set mapping, Ph.D. thesis, University of Michigan, Ann Arbor, MI, 1972."},{"key":"28","first-page":"130","article-title":"A summary of techniques for computing fixed points of continuous mappings","author":"Merrill, Orin H.","year":"1972"},{"key":"29","doi-asserted-by":"crossref","unstructured":"J. J. More, B. S. Garbow, and K. E. Hillstrom, User guide for minpack-1, Argonne National Laboratory Report ANL-80-74, Argonne, 1980.","DOI":"10.2172\/6997568"},{"issue":"11","key":"30","doi-asserted-by":"publisher","first-page":"627","DOI":"10.1002\/zamm.19820621108","article-title":"A better estimate for fixed points of contractions","volume":"62","author":"Neumaier, A.","year":"1982","journal-title":"Z. Angew. Math. Mech.","ISSN":"https:\/\/id.crossref.org\/issn\/0044-2267","issn-type":"print"},{"key":"31","unstructured":"G. Perestonina, I.L. Prutkin, L.Ya. Timerkhanova, and V. Vassin, Solving three-dimensional inverse problems of gravimetry and magnetometry for three layer medium (in Russian), Math. Modeling 15 (2003), no. 2, 69\u201376."},{"key":"32","unstructured":"J. Rutter, A serial implementation of cuppen\u2019s divide and conquer algorithm for the symmetric eigenvalue problem, Technical Report CS-94-225, Department of Computer Science, University of Tennessee, Knoxville, TN, USA, March 1994. LAPACK Working Note 69, 1994."},{"key":"33","doi-asserted-by":"publisher","first-page":"1328","DOI":"10.1137\/0115116","article-title":"The approximation of fixed points of a continuous mapping","volume":"15","author":"Scarf, Herbert","year":"1967","journal-title":"SIAM J. Appl. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0036-1399","issn-type":"print"},{"key":"34","doi-asserted-by":"publisher","first-page":"50","DOI":"10.2307\/1909383","article-title":"The core of an \ud835\udc41 person game","volume":"35","author":"Scarf, Herbert E.","year":"1967","journal-title":"Econometrica","ISSN":"https:\/\/id.crossref.org\/issn\/0012-9682","issn-type":"print"},{"key":"35","series-title":"Cowles Foundation Monographs, No. 24","volume-title":"The computation of economic equilibria","author":"Scarf, Herbert","year":"1973"},{"issue":"2","key":"36","doi-asserted-by":"publisher","first-page":"641","DOI":"10.1006\/jcom.2001.0625","article-title":"A two-dimensional bisection envelope algorithm for fixed points","volume":"18","author":"Shellman, Spencer","year":"2002","journal-title":"J. Complexity","ISSN":"https:\/\/id.crossref.org\/issn\/0885-064X","issn-type":"print"},{"issue":"3","key":"37","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1145\/838250.838255","article-title":"Algorithm 825: a deep-cut bisection envelope algorithm for fixed points","volume":"29","author":"Shellman, Spencer","year":"2003","journal-title":"ACM Trans. Math. Software","ISSN":"https:\/\/id.crossref.org\/issn\/0098-3500","issn-type":"print"},{"issue":"6","key":"38","doi-asserted-by":"publisher","first-page":"799","DOI":"10.1016\/j.jco.2003.06.001","article-title":"A recursive algorithm for the infinity-norm fixed point problem","volume":"19","author":"Shellman, Spencer","year":"2003","journal-title":"J. Complexity","ISSN":"https:\/\/id.crossref.org\/issn\/0885-064X","issn-type":"print"},{"issue":"4","key":"39","doi-asserted-by":"publisher","first-page":"580","DOI":"10.1145\/1114268.1114276","article-title":"Algorithm 848: a recursive fixed-point algorithm for the infinity-norm case","volume":"31","author":"Shellman, Spencer","year":"2005","journal-title":"ACM Trans. Math. Software","ISSN":"https:\/\/id.crossref.org\/issn\/0098-3500","issn-type":"print"},{"key":"40","isbn-type":"print","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1007\/978-1-4615-9552-6_4","article-title":"Fast algorithms for the computation of fixed points","author":"Sikorski, K.","year":"1989","ISBN":"https:\/\/id.crossref.org\/isbn\/030643251X"},{"key":"41","isbn-type":"print","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780195106909.001.0001","volume-title":"Optimal solution of nonlinear equations","author":"Sikorski, Krzysztof A.","year":"2001","ISBN":"https:\/\/id.crossref.org\/isbn\/0195106903"},{"issue":"1","key":"42","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1006\/jcom.1993.1013","article-title":"An ellipsoid algorithm for the computation of fixed points","volume":"9","author":"Sikorski, K.","year":"1993","journal-title":"J. Complexity","ISSN":"https:\/\/id.crossref.org\/issn\/0885-064X","issn-type":"print"},{"issue":"4","key":"43","doi-asserted-by":"publisher","first-page":"388","DOI":"10.1016\/0885-064X(87)90008-2","article-title":"Complexity of fixed points. I","volume":"3","author":"Sikorski, K.","year":"1987","journal-title":"J. Complexity","ISSN":"https:\/\/id.crossref.org\/issn\/0885-064X","issn-type":"print"},{"issue":"6","key":"44","doi-asserted-by":"publisher","first-page":"1752","DOI":"10.1137\/0728087","article-title":"On the orthogonality of eigenvectors computed by divide-and-conquer techniques","volume":"28","author":"Sorensen, D. C.","year":"1991","journal-title":"SIAM J. Numer. Anal.","ISSN":"https:\/\/id.crossref.org\/issn\/0036-1429","issn-type":"print"},{"issue":"4","key":"45","doi-asserted-by":"publisher","first-page":"1231","DOI":"10.1090\/S0002-9939-99-05467-2","article-title":"A generalization of the Lefschetz fixed point theorem and detection of chaos","volume":"128","author":"Srzednicki, Roman","year":"2000","journal-title":"Proc. Amer. Math. Soc.","ISSN":"https:\/\/id.crossref.org\/issn\/0002-9939","issn-type":"print"},{"issue":"6","key":"46","doi-asserted-by":"publisher","first-page":"2223","DOI":"10.1137\/S1064827598336951","article-title":"A parallel divide and conquer algorithm for the symmetric eigenvalue problem on distributed memory architectures","volume":"20","author":"Tisseur, Fran\u00e7oise","year":"1999","journal-title":"SIAM J. Sci. Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/1064-8275","issn-type":"print"},{"key":"47","unstructured":"C. W. Tsay, Fixed point computation and parallel algorithms for solving wave equations, Ph.D. thesis, University of Utah, Salt Lake City, UT, 1994."},{"key":"48","unstructured":"V. Vassin, Ill-posed problems with a priori information: Methods and applications, Institute of Mathematics and Mechanics, Russian Academy of Sciences, Ural Subdivision, 2005."},{"key":"49","series-title":"Inverse and Ill-posed Problems Series","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1515\/9783110900118","volume-title":"Ill-posed problems with a priori information","author":"Vasin, V. V.","year":"1995","ISBN":"https:\/\/id.crossref.org\/isbn\/906764191X"},{"key":"50","unstructured":"V. Vassin and E. Eremin, Feyer type operators and iterative processes (in Russian), Russian Academy of Sciences, Ural Subdivision, Ekaterinburg, 2005."},{"key":"51","doi-asserted-by":"crossref","unstructured":"V. Vassin and T.I. Sereznikova, Two stage method for approximation of nonsmooth solutions and reconstruction of noisy images (in Russian), Automatica and Telemechanica (2004), no. 2.","DOI":"10.1023\/B:AURC.0000014724.72772.aa"},{"issue":"4","key":"52","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1016\/0096-3003(79)90020-1","article-title":"A globally convergent algorithm for computing fixed points of \ud835\udc36\u00b2 maps","volume":"5","author":"Watson, Layne T.","year":"1979","journal-title":"Appl. Math. Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0096-3003","issn-type":"print"},{"issue":"1","key":"53","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1007\/BF02238651","article-title":"A comparison of point and ball iterations in the contractive mapping case","volume":"49","author":"Xu, Zong Ben","year":"1992","journal-title":"Computing","ISSN":"https:\/\/id.crossref.org\/issn\/0010-485X","issn-type":"print"},{"issue":"5","key":"54","doi-asserted-by":"publisher","first-page":"2004","DOI":"10.1137\/S0036142996304498","article-title":"A numerical verification method for solutions of boundary value problems with local uniqueness by Banach\u2019s fixed-point theorem","volume":"35","author":"Yamamoto, Nobito","year":"1998","journal-title":"SIAM J. Numer. Anal.","ISSN":"https:\/\/id.crossref.org\/issn\/0036-1429","issn-type":"print"},{"key":"55","series-title":"Theory and Decision Library. Series C: Game Theory, Mathematical Programming and Operations Research","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-4839-0","volume-title":"Computing equilibria and fixed points","volume":"21","author":"Yang, Zaifu","year":"1999","ISBN":"https:\/\/id.crossref.org\/isbn\/0792383958"}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.ams.org\/mcom\/2011-80-275\/S0025-5718-2010-02443-3\/S0025-5718-2010-02443-3.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/2011-80-275\/S0025-5718-2010-02443-3\/S0025-5718-2010-02443-3.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T16:53:03Z","timestamp":1776790383000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2011-80-275\/S0025-5718-2010-02443-3\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,11,30]]},"references-count":55,"journal-issue":{"issue":"275","published-print":{"date-parts":[[2011,7]]}},"alternative-id":["S0025-5718-2010-02443-3"],"URL":"https:\/\/doi.org\/10.1090\/s0025-5718-2010-02443-3","archive":["CLOCKSS","Portico"],"relation":{},"ISSN":["1088-6842","0025-5718"],"issn-type":[{"value":"1088-6842","type":"electronic"},{"value":"0025-5718","type":"print"}],"subject":[],"published":{"date-parts":[[2010,11,30]]}}}