Accelerated Bidirectional Modifications of the Steepest Descent Method for Ill-posed Linear Algebraic Systems with Dynamics-theoretical and Optimization Interpretation

  •  Li-Wei Liu    
  •  Hong-Ki Hong    
  •  Chein-Shan Liu    


It is well known that the classical numerical algorithm of the steepest descent method (SDM) is effective for well-posed linear systems, but performs poorly for ill-posed ones. In this paper we propose accelerated and/or bidirectional modifications of SDM, namely the accelerated steepest descent method (ASDM), the bidirectional method (2DM), and the accelerated bidirectional method (A2DM). The starting point is a manifold defined in terms of a minimum functional and a fictitious time variable; nevertheless, in the end the fictitious time variable disappears so that we arrive at purely iterative algorithms. The proposed algorithms are justified by dynamics-theoretical and optimization interpretation. The accelerator plays a prominent role of switching from the situation of slow convergence to a new situation that the functional tends to decrease stepwise in an intermittent and ceaseless manner. Three examples of solving ill-posed systems are examined and comparisons are made with exact solutions and with the existing algorithms of the SDM, the Barzilai-Borwein method, and the random SDM, revealing that the new algorithms of ASDM and A2DM have better computational efficiency and accuracy even for the highly ill-posed systems.

This work is licensed under a Creative Commons Attribution 4.0 License.