О влиянии возмущений на точность вычисления поправки в подпространстве Крылова

О влиянии возмущений на точность вычисления поправки в подпространстве Крылова

Ильин В. П., Бабенко В. Н.
Сибирский журнал индустриальной математики, 28, 1(101), 5-14 (2025)
Скачать статью

УДК 519.61 
DOI: 10.33048/SIBJIM.2025.28.101

Аннотация:

При осуществлении вычислений на ЭВМ неизбежно возникают погрешности округления. В настоящей работе исследуется вопрос о влиянии указанных погрешностей на точность вычисления поправки в подпространстве Крылова. Получена оценка точности вычисленной поправки, выраженная через возмущения исходных данных.

Литература:
  1. Голуб Дж., Ван Лоун Ч. Матричные вычисления. М.: Мир, 1999.
     
  2. Saad J. Iterative Methods for Sparse Linear Systems. Boston: PWS Publishing Co., 1996.
     
  3. Olshanskii M. A., Tyrtyshnikov E. E. Iterative methods for linear systems: theory and applications. Philadelphia: SIAM, 2014.
     
  4. Ильин В. П. Итерационные предобусловленные методы в подпространствах Крылова: тенденции XXI века // Ж. вычисл. матем. и матем. физ. 2021. Т. 61, № 11. С. 1786–1813; DOI: 10.31857/S0044466921110090
     
  5. Писсанецки С. Технология разреженных матриц. М.: Мир, 1988.
     
  6. Greenbaum A. Iterative Metuloids of Solving Linear Systems. Philadelphia: SIAM, 1997.
     
  7. Greenbaum A., Trefethen L. N. GMRES/CR and Arnoldi/Lanczos as Matrix Approximation Problems // SIAM J. Sci. Comput. 2018. V. 15, N 2. P 359–368.
     
  8. Ильин В. П. О проекционных методах в подпространствах Крылова // Зап. научн. сем. ПОМИ. 2018. Т 472. С. 103–119.
     
  9. Киреев И. В. Ортогональные проекторы и системы линейных алгебраических уравнений // Сиб. журн. вычисл. матем. 2020. Т. 23, № 3. С. 315–324.
     
  10. Arioli M., Fassino C. Roundoff error analysis of algorithms based on Krylov subspace methods // BIT Numer. Math. 1996. V. 36, N 2. P. 189–206.
     
  11. Arioli М. Generalized Golub—Kahan Bidiagonalization and Stopping Criteria // SIAM J. Matrix Anal. Appl. 2013. V. 34, N 2. P. 57–592.
     
  12. Greenbaum A. Estimating the Attainable Accuracy of Recursively Computed Residual Methods // SIAM J. Matrix Anal. Appl. 1997. V. 18, N 3. P.535–551.
     
  13. Capraux J.-F., Godunov S. K., Kuznetsov S. V. Condition number of the Krylov bases and subspaces // Linear Algebra Appl. 1996. V. 248, N 1–3. P. 136–160.
     
  14. Kuznetsov S. V. Perturbation of the Krylov bases and associated Hessenberg Forms // Linear Algebra Appl. 1997. V. 265, N 1–3. P. 1–28.
     
  15. Малышев А. Н., Садкане М. Теория возмущений по первому приближению для симметричного алгоритма Ланцоша // Ж. вычисл. матем. и матем. физ. 2005. Т. 45, № 3. С. 391–399.
     
  16. Babenko V. N. On the Structure of Closeness Estimates for Pseudosolutions of Initial and Perturbed Systems of Linear Algebraic Equations // Comput. Math. Math. Phys. 2019. V. 59, N 9. Р. 1399–1421; DOI: 10.1134/S0965542519090069
     
  17. Бабенко В. Н. Аспекты машинного решения систем линейных уравнений: монография. Краснодар: Экоинвест, 2020.
     
  18. Лоусон Ч., Хенсон Р. Численное решение задач метода наименьших квадратов. М.: Наука, 1986.
     
  19. Годунов С. К. Гарантированная точность решения систем линейных уравнений в евклидовых пространствах: монография. Новосибирск: Наука, 1988. 

Исследование выполнено при финансовой поддержке Российского научного фонда (проект № 24-21-00402). Других источников финансирования проведения или руководства данным конкретным исследованием не было.

В. П. Ильин
  1. Институт вычислительной математики и математической геофизики СО РАН, 
    просп. Акад. Лаврентьева, 6, г. Новосибирск 630090, Россия

E-mail: ilin@sscc.ru

В. Н. Бабенко
  1. Кубанский государственный технологический университет, 
    ул. Московская, 2, г. Краснодар 350072, Россия

E-mail: rnibvd@mail.ru

Статья поступила 26.10.2024 г.
После доработки — 12.04.2025 г.
Принята к публикации 21.04.2025 г.

Abstract:

Rounding errors inevitably occur when performing calculations on a computer. In this paper, we study the impact of these errors on the accuracy of calculating the correction in the Krylov subspace. An estimate of the accuracy of the calculated correction, expressed via perturbations of the original data, is obtained.

References:
  1. G. H. Golub and C. F. Van Loan, Matrix Computations (Johns Hopkins Univ., Baltimore, 1996; Moscow, Mir, 1999).
     
  2. J. Saad, Iterative Methods for Sparse Linear Systems (PWS, Boston, 1996).
     
  3. M. A. Olshanskii and E. E. Tyrtyshnikov, Iterative Methods for Linear Systems: Theory and Applications (SIAM, Philadelphia, 2014).
     
  4. V. P. Il’in, “Iterative preconditioned methods in Krylov spaces: Trends of the 21st century,” Zh. Vychisl. Mat. Mat. Fiz. 61 (11), pp. 1786–1813 (2021) [Comput. Math. Math. Phys. 61 (11), pp. 1750–1775 (2021) https://doi.org/10.1134/S0965542521110099].
     
  5. S. Pissanetsky, Sparse Matrix Technology (Academic Press, New York, 1984; Mir, Moscow, 1988).
     
  6. A. Greenbaum, Iterative Methods for Solving Linear Systems (SIAM, Philadelphia, 1997).
     
  7. A. Greenbaum and L. N. Trefethen, “GMRES/CR and Arnoldi/Lanczos as matrix approximation problems,” SIAM J. Sci. Comput. 15 (2), pp. 359–368 (2018).
     
  8. V. P. Ilyin, “On projection methods in Krylov subspaces,” Zap. Nauchn. Semin. POMI. 472, pp. 103–119 (2018) [in Russian].
     
  9. I. V. Kireev, “Orthogonal projectors and systems of linear algebraic equations,” Sib. Zh. Vychisl. Mat. 23 (3), pp. 315–324 (2020) [Numer. Anal. Appl. 13 (3), pp. 262–270 (2020)].
     
  10. M. Arioli and C. Fassino, “Roundoff error analysis of algorithms based on Krylov subspace methods,” BIT Numer. Math. 36 (2), pp. 189–206 (1996).
     
  11. М. Arioli, “Generalized Golub–Kahan bidiagonalization and stopping criteria,” SIAM J. Matrix Anal. Appl. 34 (2), pp. 57–592 (2013).
     
  12. A. Greenbaum, “Estimating the attainable accuracy of recursively computed residual methods,” SIAM J. Matrix Anal. Appl. 18 (3), pp. 535–551 (1997).
     
  13. J.-F. Capraux, S. K. Godunov, and S. V. Kuznetsov, “Condition number of the Krylov bases and subspaces,” Linear Algebra Appl. 248 (1–3), pp. 136–160 (1996).
     
  14. S. V. Kuznetsov, “Perturbation of the Krylov bases and associated Hessenberg Forms,” Linear Algebra Appl. 265 (1–3), pp. 1–28 (1997).
     
  15. A. N. Malyshev and M. Sadkane, “Perturbation theory to the first approximation for the symmetric Lanczos algorithm,” Zh. Vychisl. Mat. Mat. Fiz. 45 (3), pp. 391–399 (2005) [Comput. Math. Math. Phys. 45 (3), pp. 374–382 ((2005))].
     
  16. V. N. Babenko, “On the structure of closeness estimates for pseudosolutions of initial and perturbed systems of linear algebraic equations,” Comput. Math. Math. Phys. 59 (9), pp. 1399–1421 (2019). https://doi.org/10.1134/S0965542519090069
     
  17. V. N. Babenko, Aspects of Machine Solution of Systems of Linear Equations: A Monograph (Ekoinvest, Krasnodar, 2020) [in Russian].
     
  18. C. L. Lawson and R. J. Hanson, Solving Least Sqyares Problems (Prentice-Hall, Englewood Cliffs, 1974; Nauka, Moscow, 1988).
     
  19. S. K. Godunov, Guaranteed Accuracy of Solutions of Systems of Linear Equations in Euclidean Spaces: A Monograph (Nauka, Novosibirsk, 1988) [in Russian].