Augmented Subspaces in the LSQR Krylov Method
- PDF / 452,567 Bytes
- 5 Pages / 595.276 x 790.866 pts Page_size
- 100 Downloads / 266 Views
(0123456789().,-volV)(0123456789(). ,- volV)
RESEARCH PAPER
Augmented Subspaces in the LSQR Krylov Method Zahra Asgari1 • Faezeh Toutounian2
•
Esmail Babolian1
Received: 28 October 2019 / Accepted: 2 October 2020 Ó Shiraz University 2020
Abstract The LSQR iterative method is a Krylov subspace method for solving least-squares problems. Early termination is rare, and it is common for LSQR to require many iterations before an approximation of the solution with desired accuracy has been determined. In this paper, we present a restarted LSQR method and we use a new technique for accelerating the convergence of restated by adding some approximate error vectors to the Krylov subspace. The effectiveness of the new method is illustrated by several examples. Keywords Iterative method Least-squares approximation Krylov subspaces methods LSQR
1 Introduction In this paper, we consider the problem of finding a solution of least-squares problems min kAx bk2 ; x2Rl
ð1Þ
where A 2 Rnl is a large sparse matrix with n l and b 2 Rn : For solving systems of linear equation (1), Krylov subspace methods have become one of the popular choices for solving (1); see (Hayami et al. 2010; Piage and Saunders 1982) and references therein. The LSQR method is a famous approach that is proposed by Piage and Saunders (1982). In this method, the matrix A is used only to compute products of the form Av and AT u for various vectors v and u. Hence, A will normally be large and sparse or will be expressible as a product of matrices that are sparse or have special structure. A typical application is to the large least-squares problems & Faezeh Toutounian [email protected] Zahra Asgari [email protected] Esmail Babolian [email protected] 1
Department of Mathematics, Faculty of Mathematical Science and Computer, Kharazmi University, Tehran, Iran
2
Department of Applied Mathematics, Faculty of Mathematical Sciences, Ferdowsi University of Mashhad, Mashhad, Iran
arising from the solution of the diffusion–convection equation with variable velocity field through the use of the dual reciprocity method in multidomains (Popov et al. 2007). Also, LSQR has been shown to be numerically more reliable in various circumstances than the other methods considered for solving some inverse problems (Jiang et al. 2007). In LSQR method, the Golub–Kahan bidiagonalization process is applied, with initial vectors u1 ¼ krr00 k and v1 ¼ AT u1 kAT u1 k
to construct orthonormal bases fu1 ; u2 ; . . .; um g and
fv1 ; v2 ; . . .; vm g for the Krylov subspaces Km ðAAT ; u1 Þ ¼ spanfu1 ; ðAAT Þu1 ; . . .; ðAAT Þm1 u1 g; Km ðAT A; v1 Þ ¼ spanfv1 ; ðAT AÞv1 ; . . .; ðAT AÞm1 v1 g: ð2Þ The LSQR method finds an approximate solution xm by minimizing kAx bk2 over the subspace x0 þ Km ðAT A; v1 Þ: The associated residual vector rm ¼ b Axm lies in Km ðAAT ; u1 Þ: The LSQR method will in exact arithmetic terminate before m steps have been carried out if the Krylov subspace Km ðAT A; v1 Þ is of dimension less than m. LSQR delivers, in this situation, the sol
Data Loading...