О влиянии возмущений в проекционном методе крыловского типа на точность итерационного приближения и формирование критерия останова

О влиянии возмущений в проекционном методе крыловского типа на точность итерационного приближения и формирование критерия останова

Ильин В. П., Бабенко В. Н.
Сибирский журнал индустриальной математики, 29, 1(105), 25-38 (2026)
Скачать статью

УДК 519.61 
DOI: 10.33048/SIBJIM.2026.29.103

Аннотация:

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

Литература:
  1. Писсанецки С. Технология разреженных матриц. М.: Мир, 1988.
     
  2. Greenbaum A. Iterative Metuloids of Solving Linear Systems // Frontiers in Applied Mathematics, 1997; DOI:10.1137/1.9781611970937.
     
  3. Фаддеев Д. К., Фаддеева В. Н. Вычислительные методы линейной алгебры. СПб.: Лань, 2002.
     
  4. Голуб Дж., Ван Лоун Ч. Матричные вычисления. М.: Мир, 1999.
     
  5. Saad J. Iterative Methods for Sparse Linear Systems. Boston: EPS, 1996.
     
  6. Olshanskii M. A., Tyrtyshnikov E. E. Iterative methods for linear systems: theory and ap-plications, SIAM (Philadelphia, PA, United States), 2014.
     
  7. Ильин В. П. Итерационные предобусловленные методы в подпространствах Крылова: тенденции XXI века // Журн. вычисл. математики и матем. физики. 2021. Т. 61, № 11. С. 1786–1813; DOI: 10.31857/S0044466921110090
     
  8. Ильин В. П. О проекционных методах в подпространствах Крылова // Записки научных семинаров ПОМИ. 2018. Т. 472. С. 103–119; https://ftp.pdmi.ras.ru/pub/publicat/znsl/v472/p103.pdf  
     
  9. Киреев И. В. Ортогональные проекторы и системы линейных алгебраических уравнений // Сиб. журн. вычисл. математики. 2020. Т. 23, № 3. С. 315–324.
     
  10. Arioli M., Fassino C. Troundoff error analysis of algorithms based on Krylov subspace methods // BIT. 1996. V. 36, N 2. P. 189–206.
     
  11. Arioli M., Fassino C. 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.
     
  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. Малышев А. Н., Sadkane M. Теория возмущений по первому приближению для симметричного алгоритма Ланцоша // Журн. вычисл. математики и матем. физики. 2005. Т. 45, № 3. С. 391–399.
     
  16. Ильин В. П., Бабенко В. Н. О влиянии возмущений на точность вычисления поправки в подпространстве Крылова // Сиб. журн. индустр. математики. 2025. Т. 28, № 1. С. 5–14; DOI: 10.33048/SIBJIM.2025.28.101
     
  17. Годунов С. К. Решение систем линейных уравнений. Новосибирск: Наука, 1980.
     
  18. Годунов С. К., Антонов А. Г., Кирилюк О. П., Костин В. И. Гарантированная точность решения систем линейных уравнений в евклидовых пространствах. Новосибирск: Наука, 1988.
     
  19. Бабенко В. Н., Ивановский О. Я. Аспекты машинного решения систем линейных уравнений. Краснодар: Экоинвест, 2020.
     
  20. Баландин М. Ю., Шурина Э. П. Методы решения СЛАУ большой размерности. Новосибирск: Изд-во НГТУ, 2000.
     
  21. Икрамов Х. Д. Несимметричная проблема собственных значений. – Москва: Наука, 1991.

Исследования выполнены в рамках государственного задания Института вычислительной математики и математической геофизики СО РАН (проект FWNM-2025-0001). Других источников финансирования проведения или руководства данным конкретным исследованием не было.

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

E-mail: ilin@sscc.ru 

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

E-mail: rnibvd@mail.ru 

Статья поступила 08.12.2025 г.
После доработки — 13.02.2026 г.
Принята к публикации 13.05.2026 г.

Abstract:

Roundoff errors inevitably arise when performing computer calculations. This paper examines the impact of these errors on the accuracy of calculating the next approximation in a projection method for solving linear equations using projection onto Krylov subspaces. An estimate of the accuracy of the calculated approximation is obtained, expressed in terms of perturbations of the initial data. A termination criterion is proposed that guarantees the chosen acceptable accuracy of the desired solution.

References:
  1. S. Pissanetsky, Sparse Matrix Technology. N. Y.: Academic Press, 1984.
     
  2. Greenbaum A. Iterative Metuloids of Solving Linear Systems. Frontiers Appl. Math., 1997; DOI:10.1137/1.9781611970937.
     
  3. Фаддеев Д. К., Фаддеева В. Н. Vychislitel’nye metody linejnoj algebry [Computational methods of linear Algebra]. St. Petersburg: Lan’, 2002 (in Russian).
     
  4. Golub G. H., Van Loan C. F. Matrix Computations Baltimore: J. Hopkins Univ. Publ., 1996
     
  5. Saad J. Iterative Methods for Sparse Linear Systems. Boston: EPS, 1996.
     
  6. Olshanskii M. A., Tyrtyshnikov E. E. Iterative methods for linear systems: theory and ap-plications, SIAM (Philadelphia, PA, United States), 2014.
     
  7. Il’in V. P. Iterative preconditioned methods in Krylov spaces: Trends of the 21st century. Comput. Math. Math. Phys., 2021, Vol. 61, No. 1), pp. 1750–1775; https://doi.org/10.1134/S0965542521110099  
     
  8. Il’in V. P. O proekcionnyh metodah v podprostranstvah Krylova [On projection methods in Krylov subspaces]. Zapiski Nauchnyh Seminarov POMI [Notes of Scientific Seminars in Moscow], 2018, Vol. 472, pp. 103–119 (in Russian); https://ftp.pdmi.ras.ru/pub/publicat/znsl/v472/p103.pdf  
     
  9. Kireev I. V. Orthogonal projectors and systems of linear algebraic equations,. Numer. Anal. Appl., 2020, Vol. 13, No. 3, pp. 262–270.
     
  10. Arioli M., Fassino C. Troundoff error analysis of algorithms based on Krylov subspace methods. BIT, 1996, Vol. 36, No. 2, pp. 189–206.
     
  11. Arioli M., Fassino C. Generalized Golub-Kahan Bidiagonalization and Stopping Criteria. SIAM J. Matrix Anal. Appl., 2013, Vol. 34, No. 2, pp. 57–592.
     
  12. Greenbaum A. Estimating the Attainable Accuracy of Recursively Computed Residual Methods. SIAM J. Matrix Anal. Appl., 1997.
     
  13. Capraux J.-F., Godunov S. K., Kuznetsov S. V. Condition number of the Krylov bases and subspaces. Linear Algebra Appl., 1996, Vol. 248, No. 1–3, pp. 136–160.
     
  14. Kuznetsov S. V. Perturbation of the Krylov bases and associated Hessenberg Forms. Linear Algebra Appl., 1997, Vol. 265, No. 1–3, pp. 1–28.
     
  15. Malyshev A. N., Sadkane M. Teoriya vozmushchenij po pervomu priblizheniyu dlya simmetrichnogo algoritma Lancosha [First approximation perturbation theory for the symmetric Lanczos algorithm]. Zhurn. Vychisl. Mat. Mat. Fiziki[J. Calcul. Math. Math. Phys.], 2005, Vol. 45, No 3, pp. 391–399 (in Russian).
     
  16. Ilyin V. P., Babenko V. N. On the Influence of Disturbances on the Accuracy of Computing Corrections in the Krylov Subspace. JAIM, 2025, Vol. 19, No. 1, pp. 51–58; DOI: 10.1134/S1990478925010053
     
  17. Godunov S. K. Reshenie sistem linejnyh uravnenij [Solving systems of linear equations]. Novosibirsk: Nauka, 1980 (in Russian).
     
  18. Godunov S. K., Antonov A. G., Kirilyuk O. P., Kostin V. I. Garantirovannaya tochnost’ resheniya sistem linejnyh uravnenij v evklidovyh prostranstvah [Guaranteed accuracy of solving systems of linear equations in Euclidean spaces]. Novosibirsk: Nauka, 1988 (in Russian).
     
  19. Babenko V. N., Ivanovskij O. Ya. Aspekty mashinnogo resheniya sistem linejnyh uravnenij [Aspects of solving systems of linear equations by machine]. Krasnodar: Ehkoinvest, 2020 (in Russian).
     
  20. Balandin M. Yu., Shurina E. P. Metody resheniya SLAU bol’shoj razmernosti [Methods for solving large-dimensional SLAUs]. Novosibirsk: NSTU Pub., 2000 (in Russian).
     
  21. Ikramov H. D. Nesimmetrichnaya problema sobstvennyh znachenij [The Asymmetric Eigenvalue Problem]. Moscow: Nauka, 1991 (in Russian).