A new iterative refinement for ill-conditioned linear systems based on discrete gradient
- PDF / 1,740,801 Bytes
- 16 Pages / 439.37 x 666.142 pts Page_size
- 34 Downloads / 155 Views
A new iterative refinement for ill‑conditioned linear systems based on discrete gradient Kai Liu1 · Jie Yang1 · Changying Liu2 Received: 26 November 2019 / Revised: 17 March 2020 © The JJIAM Publishing Committee and Springer Japan KK, part of Springer Nature 2020
Abstract In this paper, a new iterative refinement for ill-conditioned linear systems is derived based on discrete gradient methods for gradient systems. It is proved that the new method is convergent for any initial values irrespective of the choice of the stepsize h. Some properties of the new iterative refinement are presented. It is shown that the condition number of the coefficient matrix in the linear system to be solved in every step can be improved significantly compared with Wilkinson’s iterative refinement. The numerical experiments illustrate that the new method is more effective and efficient than Wilkinson’s iterative refinement when dealing with ill-conditioned linear systems. Keywords Wilkinson’s iterative refinement · Ill-conditioned system of linear equations · Discrete gradient method · Gradient system Mathematics Subject Classification 65L05 · 65L06 · 65F10
1 Introduction Consider a linear equation of the form (1)
Ax = b,
The research was supported in part by the Natural Science Foundation of China under Grant 11701271 and by the Natural Science Foundation of the Jiangsu Higher Education Institutions under Grant 16KJB110010. * Jie Yang [email protected] 1
College of Applied Mathematics, Nanjing University of Finance and Economics, Nanjing 210023, People’s Republic of China
2
School of Mathematics and Statistics, Nanjing University of Information Science and Technology, Nanjing 210044, People’s Republic of China
13
Vol.:(0123456789)
K. Liu et al.
where A ∈ ℝn×n is symmetric positive definite and x, b ∈ ℝn . The condition number of a nonsingular square matrix A with respect to a given matrix norm ∥ ⋅ ∥ is defined to be
𝜅(A) = ‖A‖ ⋅ ‖A−1 ‖.
(2)
Linear system (1) is called ill-conditioned if the condition number 𝜅(A) of the coefficient matrix A is very large, in which case, small perturbations in the observation data can have large effects on the computed solutions. One approach to deal with ill-conditioned linear systems is the scaling strategy, but scaling of the equations and unknowns must proceed on a problem-by-problem basis [1, 2]. Another approach is regularization method in which a parameter is introduced in order to modify the ill-conditioned linear systems, such that it can be well-conditioned. For example, the truncated singular value decomposition [3], maximum entropy regularization [4] , and the Tikhonov regularization method [5] are widely used in this field. The regularization method requires the choice of an adequate regularization parameter [6]. An optimal regularization parameter can balance the perturbation error and the regularization error in the regularized solution. Besides the above mentioned approaches, an iterative refinement of the solution obtained by a direct solver is also a widely-used m
Data Loading...
