Stabilization of Stochastic Iterative Methods for Singular and Nearly Singular Linear Systems
We consider linear systems of equations, Ax = b, with an emphasis on the case where A is singular. Under certain conditions, necessary as well as sufficient, linear deterministic iterative methods generate sequences {x[subscript k]} that converge to a solution as long as there exists at least one so...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Institute for Operations Research and the Management Sciences (INFORMS)
2015
|
| Online Access: | http://hdl.handle.net/1721.1/99752 https://orcid.org/0000-0001-6909-7208 |
| _version_ | 1826202285256998912 |
|---|---|
| author | Wang, Mengdi Bertsekas, Dimitri P. |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Wang, Mengdi Bertsekas, Dimitri P. |
| author_sort | Wang, Mengdi |
| collection | MIT |
| description | We consider linear systems of equations, Ax = b, with an emphasis on the case where A is singular. Under certain conditions, necessary as well as sufficient, linear deterministic iterative methods generate sequences {x[subscript k]} that converge to a solution as long as there exists at least one solution. This convergence property can be impaired when these methods are implemented with stochastic simulation, as is often done in important classes of large-scale problems. We introduce additional conditions and novel algorithmic stabilization schemes under which {x[subscript k]} converges to a solution when A is singular and may also be used with substantial benefit when A is nearly singular. |
| first_indexed | 2024-09-23T12:05:06Z |
| format | Article |
| id | mit-1721.1/99752 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T12:05:06Z |
| publishDate | 2015 |
| publisher | Institute for Operations Research and the Management Sciences (INFORMS) |
| record_format | dspace |
| spelling | mit-1721.1/997522022-10-01T08:01:35Z Stabilization of Stochastic Iterative Methods for Singular and Nearly Singular Linear Systems Wang, Mengdi Bertsekas, Dimitri P. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology. Laboratory for Information and Decision Systems Wang, Mengdi Bertsekas, Dimitri P. We consider linear systems of equations, Ax = b, with an emphasis on the case where A is singular. Under certain conditions, necessary as well as sufficient, linear deterministic iterative methods generate sequences {x[subscript k]} that converge to a solution as long as there exists at least one solution. This convergence property can be impaired when these methods are implemented with stochastic simulation, as is often done in important classes of large-scale problems. We introduce additional conditions and novel algorithmic stabilization schemes under which {x[subscript k]} converges to a solution when A is singular and may also be used with substantial benefit when A is nearly singular. United States. Air Force (Grant GA9550-10-1-0412) Los Alamos National Laboratory. Information Science and Technology Institute (Grant 67870-001-08) 2015-11-09T14:53:08Z 2015-11-09T14:53:08Z 2013-05 2012-11 Article http://purl.org/eprint/type/JournalArticle 0364-765X 1526-5471 http://hdl.handle.net/1721.1/99752 Wang, Mengdi, and Dimitri P. Bertsekas. “Stabilization of Stochastic Iterative Methods for Singular and Nearly Singular Linear Systems.” Mathematics of OR 39, no. 1 (February 2014): 1–30. https://orcid.org/0000-0001-6909-7208 en_US http://dx.doi.org/10.1287/moor.2013.0596 Mathematics of Operations Research Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Institute for Operations Research and the Management Sciences (INFORMS) MIT web domain |
| spellingShingle | Wang, Mengdi Bertsekas, Dimitri P. Stabilization of Stochastic Iterative Methods for Singular and Nearly Singular Linear Systems |
| title | Stabilization of Stochastic Iterative Methods for Singular and Nearly Singular Linear Systems |
| title_full | Stabilization of Stochastic Iterative Methods for Singular and Nearly Singular Linear Systems |
| title_fullStr | Stabilization of Stochastic Iterative Methods for Singular and Nearly Singular Linear Systems |
| title_full_unstemmed | Stabilization of Stochastic Iterative Methods for Singular and Nearly Singular Linear Systems |
| title_short | Stabilization of Stochastic Iterative Methods for Singular and Nearly Singular Linear Systems |
| title_sort | stabilization of stochastic iterative methods for singular and nearly singular linear systems |
| url | http://hdl.handle.net/1721.1/99752 https://orcid.org/0000-0001-6909-7208 |
| work_keys_str_mv | AT wangmengdi stabilizationofstochasticiterativemethodsforsingularandnearlysingularlinearsystems AT bertsekasdimitrip stabilizationofstochasticiterativemethodsforsingularandnearlysingularlinearsystems |