Implicit iterative schemes based on singular decomposition and regularizing algorithms

Abstract


A new version of the simple iterations implicit method based on the singular value decomposition is proposed. It is shown that this variant of the simple iterations implicit method can significantly improve the computational stability of the algorithm and at the same time provides a high rate of its convergence. The application of the simple iterations implicit method based on the singular value decomposition for the development of iterative regularization algorithms is considered. The proposed algorithms can be effectively used to solve a wide class of ill-posed and ill-conditioned computational problems.

Full Text

Introduction. Iterative methods of regularization play an exceptionally important role in solving a large class of ill-posed and discrete ill-conditioned problems [1-6]. They can be used to solve problems encountered in dynamics and kinetics, mathematical economics, geophysics, potential theory, antenna synthesis, acoustics, automatic processing of physical experiment results, determination of the shape of a radio pulse emitted by a source, plasma diagnostics, in ground or air geological prospecting (mathematical processing of measurements), in solving the inverse kinematic task of seismic, space research (spectroscopy), medicine Iterative regularizing algorithms are obtained from classical iterative- schemes using special stopping criteria that provide them with regularizing properties. The regularization effect in these algorithms is achieved due to matching the number of iterations with initial errors-as a regularization parameter is the number of iterations of the iterative algorithm (iterative residual principle of Tikhonov). Such a choice of the regularization parameter is easily realized, especially in iterative methods, and in most practical problems leads to results on accuracy close to optimal. Most of the practically used iterative regularizing algorithms apply explicit or implicit iterative schemes (methods) of simple iterations [1-3]. In terms of the convergence rate, implicit iterative schemes have significant advantage over explicit schemes. In this connection, implicit iterative schemes play a more important role for the methods of iterative regularization. The computational stability of implicit iterative schemes is important. This stability strongly depends on the method of solving systems of linear algebraic equations (SLAE) at each iteration. It is known that the methods of solving SLAE on the basis of singular decomposition (SVD-methods) have the largest computational stability [7,8]. These methods allow to solve effectively even SLAE with ill-determined rank [9, 10]. A disadvantage (when solving problems large dimension) is the fact that the SVD method is poorly implemented on parallel high-performance platforms. However, in recent years some researches eliminating this lack have recently appeared [11-15]. In this paper, we propose a variant of the implicit method of simple iterations based on the use of singular decomposition (SVD-method). The speed and the numeric stability of this iteration algorithm are studied. The application of the proposed method for constructing iterative regularization algorithms is considered here. 1. Problem formulation and implicit method of simple iterations. We consider the problem of solving systems of linear equations of the form:

About the authors

Alexander I Zhdanov

Samara State Technical University

Email: zhdanovaleksan@yandex.ru
244, Molodogvardeyskaya st., Samara, 443100, Russian Federation
Dr. Phys. & Math. Sci., Professor; Head of Department; Dept. of Higher Mathematics & Applied Computer Science

References

  1. Vainikko G. M., Veretennikov A. Yu. Iteration Procedures in Ill-Posed Problems. Moscow, Nauka, 1986, 186 pp. (In Russian)
  2. Bakushinsky A. B., Goncharsky A. V. Iterative methods for solving ill-posed problems. Moscow, Nauka, 1986, 186 pp. (In Russian)
  3. Matysik O. V. Explicit and implicit iteration procedures of solving ill-posed problems. Brest, Brest State Univ., 1986, 186 pp. (In Russian)
  4. Donatelli M. On nondecreasing sequences of regularization parameters for nonstationary iterated Tikhonov, Numer. Algor., 2012, vol. 60, no. 4, pp. 651-668. doi: 10.1007/s11075-012-9593-7.
  5. Landi G., Loli Picolomini E., Tomba I. A stopping criterion for iterative regularization methods, Appl. Numer. Math., 2016, vol. 106, pp. 53-68. doi: 10.1016/j.apnum.2016.03.006.
  6. Buccini A., Donatelli M., Reichel L. Iterated Tikhonov regularization with a general penalty term, Numer Linear Algebra Appl., 2017, vol. 24, no. 4, e2089. doi: 10.1002/nla.2089.
  7. Golub G. H., Van Loan C. F. Matrix computations, Johns Hopkins Series in the Mathematical Sciences, vol. 3. Baltimore, etc., The Johns Hopkins University Press., 1989, xix+642 pp.
  8. Björk Å. Numerical Methods in Matrix Computations, Texts in Applied Mathematics, vol. 59. Cham, Springer, 2015, xvi+800 pp. doi: 10.1007/978-3-319-05089-8.
  9. Malyshev A. N. Introduction to numerical linear algebra (with an application of algorithms on FORTRAN). Novosibirsk, Nauka, 1991, 229 pp. (In Russian)
  10. Hansen P. C. Rank-deficient and discrete ill-posed problems. Numerical aspects of linear inversion, SIAM Monographs on Mathematical Modeling and Computation, vol. 4. Philadelphia, PA, SIAM, Society for Industrial and Applied Mathematics, 1997, 247 pp.
  11. Yamazaki I., Tomov S., Dongarra J. Sampling Algorithms to Update Truncated SVD, In: IEEE International Conference on Big Data (Big Data), 2017. doi: 10.1109/BigData.2017.8257997.
  12. Gates M., Tomov S., Dongarra J. Accelerating the SVD Two StageBidiagonal Reduction and Divide and Conquer Using GPUs, Parallel Computing, 2018, vol. 74, pp. 3-18. doi: 10.1016/j.parco.2017.10.004.
  13. Kabir K., Haidar A., Tomov S., Bouteiller A., Dongarra J. A Framework for Out of Memory SVD Algorithms, In: High Performance Computing, ISC 2017. Lecture Notes in Computer Science, vol. 10266; eds. J. Kunkel, R. Yokota, P. Balaji, D. Keyes. Cham, Springer, pp. 158-178. doi: 10.1007/978-3-319-58667-0_9.
  14. Dong T., Haidar A., Tomov S., Dongarra J. Optimizing the SVD Bidiagonalization Process for a Batch of Small Matrices, Procedia Computer Science, 2017, vol. 108, pp. 1008-1018. doi: 10.1016/j.procs.2017.05.237.
  15. Haidar A., Kabir K., Fayad D., Tomov S., Dongarra J. Out Of Memory SVD Solver for Big Data, In: 2017 IEEE High Performance Extreme Computing Conference (HPEC), 2017. doi: 10.1109/HPEC.2017.8091029.
  16. Verzhbitskij V. M. Numerical Methods (Linear Algebra and Nonlinear Equations). Moscow, Oniks 21 Century Publishing House, 2005, 432 pp. (In Russian)

Statistics

Views

Abstract - 29

PDF (Russian) - 7

Cited-By


Article Metrics

Metrics Loading ...

PlumX

Dimensions

Refbacks

  • There are currently no refbacks.

Copyright (c) 2018 Samara State Technical University

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

This website uses cookies

You consent to our cookies if you continue to use our website.

About Cookies