Abstract
When a solution to an abstract inverse linear problem on Hilbert space is approximable by finite linear combinations of vectors from the cyclic subspace associated with the datum and with the linear operator of the problem, the solution is said to be a Krylov solution. Krylov solvability of the inverse problem allows for solution approximations that, in applications, correspond to the very efficient and popular Krylov subspace methods. We study the possible behaviors of persistence, gain, or loss of Krylov solvability under suitable small perturbations of the infinite-dimensional inverse problem – the underlying motivations being the stability or instability of infinite-dimensional Krylov methods under small noise or uncertainties, as well as the possibility to decide a priori whether an infinite-dimensional inverse problem is Krylov solvable by investigating a potentially easier, perturbed problem.
Funding statement: This work is partially supported by the Alexander von Humboldt Foundation, Bonn.
References
[1] N. I. Akhiezer and I. M. Glazman, Theory of Linear Operators in Hilbert Space, Frederick Ungar, New York, 1993. Search in Google Scholar
[2] H. Brezis, Functional Analysis, Sobolev Spaces and Partial Differential Equations, Universitext, Springer, New York, 2011. 10.1007/978-0-387-70914-7Search in Google Scholar
[3] J.-F. Carpraux, S. K. Godunov and S. V. Kuznetsov, Condition number of the Krylov bases and subspaces, Linear Algebra Appl. 248 (1996), 137–160. 10.1016/0024-3795(95)00164-6Search in Google Scholar
[4] N. A. Caruso and A. Michelangeli, Krylov solvability of unbounded inverse linear problems, Integral Equations Operator Theory 93 (2021), no. 1, Paper No. 1. 10.1007/s00020-020-02616-2Search in Google Scholar
[5] N. A. Caruso and A. Michelangeli, Convergence of the conjugate gradient method with unbounded operators, Oper. Matrices 16 (2022), no. 1, 35–68. 10.7153/oam-2022-16-05Search in Google Scholar
[6] N. A. Caruso, A. Michelangeli and P. Novati, On Krylov solutions to infinite-dimensional inverse linear problems, Calcolo 56 (2019), no. 3, Paper No. 32. 10.1007/s10092-019-0330-7Search in Google Scholar
[7] N. A. Caruso, A. Michelangeli and P. Novati, On general convergence behaviours of finite-dimensional approximants for abstract linear inverse problems, Asymptot. Anal. 127 (2022), no. 1–2, 167–189. 10.3233/ASY-211678Search in Google Scholar
[8] J. W. Daniel, The conjugate gradient method for linear and nonlinear operator equations, SIAM J. Numer. Anal. 4 (1967), 10–26. 10.1137/0704002Search in Google Scholar
[9] X. Du, M. Sarkis, C. E. Schaerer and D. B. Szyld, Inexact and truncated parareal-in-time Krylov subspace methods for parabolic optimal control problems, Electron. Trans. Numer. Anal. 40 (2013), 36–57. Search in Google Scholar
[10] A. Ern and J.-L. Guermond, Theory and Practice of Finite Elements, Appl. Math. Sci. 159, Springer, New York, 2004. 10.1007/978-1-4757-4355-5Search in Google Scholar
[11] L. Gehér, Cyclic vectors of a cyclic operator span the space, Proc. Amer. Math. Soc. 33 (1972), 109–110. 10.1090/S0002-9939-1972-0290131-4Search in Google Scholar
[12] M. A. Gilles and A. Townsend, Continuous analogues of Krylov subspace methods for differential operators, SIAM J. Numer. Anal. 57 (2019), no. 2, 899–924. 10.1137/18M1177810Search in Google Scholar
[13] I. C. Gohberg and A. S. Markus, Two theorems on the gap between subspaces of a Banach space, Uspekhi Mat. Nauk 14 (1959), no. 5(89), 135–140. Search in Google Scholar
[14] A. K. Gupta and S. Mukherjee, On Hausdorff metric spaces, preprint (2019), https://arxiv.org/abs/1909.07195v3. Search in Google Scholar
[15] P. R. Halmos, A Hilbert Space Problem Book, 2nd ed., Encyclopedia Math. Appl. 17, Springer, New York, 1982. 10.1007/978-1-4684-9330-6_4Search in Google Scholar
[16] M. Hanke, Conjugate Gradient Type Methods for Ill-Posed Problems, Pitman Res. Notes Math. Ser. 327, Longman Scientific & Technical, Harlow, 1995. Search in Google Scholar
[17] P. C. Hansen, Rank-Deficient and Discrete Ill-Posed Problems, SIAM Monogr. Math. Model. Comput., Society for Industrial and Applied Mathematics, Philadelphia, 1998. 10.1137/1.9780898719697Search in Google Scholar
[18] J. Henrikson, Completeness and total boundedness of the Hausdorff metric, MIT Undergrad J. Math. 1 (1999), 69–80. Search in Google Scholar
[19] D. A. Herrero, Eigenvectors and cyclic vectors for bilateral weighted shifts, Rev. Un. Mat. Argentina 26 (1972/73), 24–41. Search in Google Scholar
[20] R. Herzog and E. Sachs, Superlinear convergence of Krylov subspace methods for self-adjoint problems in Hilbert space, SIAM J. Numer. Anal. 53 (2015), no. 3, 1304–1324. 10.1137/140973050Search in Google Scholar
[21] W. J. Kammerer and M. Z. Nashed, On the convergence of the conjugate gradient method for singular linear operator equations, SIAM J. Numer. Anal. 9 (1972), 165–181. 10.1137/0709016Search in Google Scholar
[22] W. Karush, Convergence of a method of solving linear problems, Proc. Amer. Math. Soc. 3 (1952), 839–851. 10.1090/S0002-9939-1952-0055794-4Search in Google Scholar
[23] T. Kato, Perturbation Theory for Linear Operators, Class. Math., Springer, Berlin, 1995. 10.1007/978-3-642-66282-9Search in Google Scholar
[24] M. G. Kreĭn and M. A. Krasnosel’skiĭ, Fundamental theorems on the extension of Hermitian operators and certain of their applications to the theory of orthogonal polynomials and the problem of moments, Uspehi Matem. Nauk (N. S.) 2 (1947), no. 3(19), 60–106. Search in Google Scholar
[25] M. G. Kreĭ, M. A. Krasnosel’skiĭ and D. Mil’man, Concerning the deficiency numbers of linear operators in Banach space and some geometric questions, Sbornik Trudov Instit. Mat. Akad. Nauk. Ukr. S.S.R. 11 (1948), 97–112. Search in Google Scholar
[26] S. V. Kuznetsov, Perturbation bounds of the Krylov bases and associated Hessenberg forms, Linear Algebra Appl. 265 (1997), 1–28. 10.1016/S0024-3795(96)00299-6Search in Google Scholar
[27] J. Liesen and Z. Strakoš, Krylov Subspace Methods, Numer. Math. Sci. Comput., Oxford University, Oxford, 2013. 10.1093/acprof:oso/9780199655410.001.0001Search in Google Scholar
[28] J. R. Munkres, Topology, Prentice Hall, Upper Saddle River, 2000. Search in Google Scholar
[29] A. S. Nemirovskiy and B. T. Polyak, Iterative methods for solving linear ill-posed problems under precise information. I, Izv. Akad. Nauk SSSR Tekhn. Kibernet. (1984), no. 2, 13–25, 203. Search in Google Scholar
[30] A. S. Nemirovskiy and B. T. Polyak, Iterative methods for solving linear ill-posed problems under precise information. II, Eng. Cybernetics 22 (1984), 50–57. Search in Google Scholar
[31] S. Olver, GMRES for the differentiation operator, SIAM J. Numer. Anal. 47 (2009), no. 5, 3359–3373. 10.1137/080724964Search in Google Scholar
[32] C. C. Paige and P. Van Dooren, Sensitivity analysis of the Lanczos reduction, Numer. Linear Algebra Appl. 6 (1999), 29–50. 10.1002/(SICI)1099-1506(199901/02)6:1<29::AID-NLA144>3.0.CO;2-ISearch in Google Scholar
[33] A. Quarteroni, Numerical Models for Differential Problems, 3rd ed., MS&A. Model. Simul. Appl. 16, Springer, Cham, 2017. 10.1007/978-3-319-49316-9Search in Google Scholar
[34] Y. Saad, Iterative Methods for Sparse Linear Systems, 2nd ed., Society for Industrial and Applied Mathematics, Philadelphia, 2003. 10.1137/1.9780898718003Search in Google Scholar
[35] S. Shkarin, A weighted bilateral shift with cyclic square is supercyclic, Bull. Lond. Math. Soc. 39 (2007), no. 6, 1029–1038. 10.1112/blms/bdm085Search in Google Scholar
[36] J. A. Sifuentes, M. Embree and R. B. Morgan, GMRES convergence for perturbed coefficient matrices, with application to approximate deflation preconditioning, SIAM J. Matrix Anal. Appl. 34 (2013), no. 3, 1066–1088. 10.1137/120884328Search in Google Scholar
[37] V. Simoncini and D. B. Szyld, Theory of inexact Krylov subspace methods and applications to scientific computing, SIAM J. Sci. Comput. 25 (2003), no. 2, 454–477. 10.1137/S1064827502406415Search in Google Scholar
[38] V. Simoncini and D. B. Szyld, On the occurrence of superlinear convergence of exact and inexact Krylov subspace methods, SIAM Rev. 47 (2005), no. 2, 247–272. 10.1137/S0036144503424439Search in Google Scholar
[39] A. A. Tuzhilin, Lectures on Hausdorff and Gromov–Hausdorff distance geometry, arXiv:2012.00756, preprint (2020), https://arxiv.org/abs/2012.00756. Search in Google Scholar
[40] J. van den Eshof, G. L. G. Sleijpen and M. B. van Gijzen, Relaxation strategies for nested Krylov methods, J. Comput. Appl. Math. 177 (2005), no. 2, 347–365. 10.1016/j.cam.2004.09.024Search in Google Scholar
[41] R. Winther, Some superlinear convergence results for the conjugate gradient method, SIAM J. Numer. Anal. 17 (1980), no. 1, 14–17. 10.1137/0717002Search in Google Scholar
[42] F. Xue and H. C. Elman, Fast inexact subspace iteration for generalized eigenvalue problems with spectral transformation, Linear Algebra Appl. 435 (2011), no. 3, 601–622. 10.1016/j.laa.2010.06.021Search in Google Scholar
[43] J.-P. M. Zemke, Abstract perturbed Krylov methods, Linear Algebra Appl. 424 (2007), no. 2–3, 405–434. 10.1016/j.laa.2007.02.011Search in Google Scholar
© 2022 Walter de Gruyter GmbH, Berlin/Boston
