Неявный итерационный алгоритм для решения задачи регуляризированных полных наименьших квадратов

Обложка
  • Авторы: Иванов Д.В.1,2, Жданов А.И.3
  • Учреждения:
    1. Самарский национальный исследовательский университет имени академика С.П. Королева
    2. Самарский государственный университет путей сообщения
    3. Самарский государственный технический университет
  • Выпуск: Том 26, № 2 (2022)
  • Страницы: 311-321
  • Раздел: Математическое моделирование, численные методы и комплексы программ
  • URL: https://bakhtiniada.ru/1991-8615/article/view/107681
  • DOI: https://doi.org/10.14498/vsgtu1930
  • ID: 107681

Цитировать

Полный текст

Аннотация

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

Об авторах

Дмитрий В. Иванов

Самарский национальный исследовательский университет имени академика С.П. Королева; Самарский государственный университет путей сообщения

Email: dvi85@list.ru
ORCID iD: 0000-0002-5021-5259
SPIN-код: 6672-4830
Scopus Author ID: 22937879800
http://www.mathnet.ru/person42123

кандидат физико-математических наук, доцент, доцент каф. безопасности информационных систем, доцент каф. мехатроники

Россия, 443086, Самара, Московское ш., 34; 443066, Самара, ул. Свободы, 2 В

Александр И. Жданов

Самарский государственный технический университет

Автор, ответственный за переписку.
Email: ZhdanovAleksan@yandex.ru
ORCID iD: 0000-0001-6082-9097
SPIN-код: 5056-3555
Scopus Author ID: 7102747969
ResearcherId: E-1433-2014
http://www.mathnet.ru/person41724

доктор физико-математических наук, профессор, профессор каф. прикладная математика и информатика

Россия, 443100, Самара, ул. Молодогвардейская, 244

Список литературы

  1. Markovsky I. Bibliography on total least squares and related methods, Stat. Interface, 2010, vol. 3, no. 3, pp. 329–334. DOI: https://doi.org/10.4310/SII.2010.v3.n3.a6.
  2. Pintelon R., Schoukens J. System Identification: A Frequency Domain Approach. Piscataway, NJ, IEEE Press, 2012, xliv+743 pp. DOI: https://doi.org/10.1002/9781118287422.
  3. Pillonetto G., Chen T., Chiuso A., De Nicolao G., Ljung L. Regularized System Identification. Learning Dynamic Models from Data, Communications and Control Engineering. Cham, Springer, 2022, xxiv+377 pp. DOI: https://doi.org/10.1007/978-3-030-95860-2.
  4. Markovsky I., Willems J. C., Van Huffel S., Bart De Moor, Pintelon R. Application of structured total least squares for system identification and model reduction, IEEE Trans. Autom. Control, 2005, vol. 50, no. 10, pp. 1490–1500. DOI: https://doi.org/10.1109/TAC.2005.856643.
  5. Ivanov D. V. Identification of linear dynamic systems of fractional order with errors in variables based on an augmented system of equations, Vestn. Samar. Gos. Tekhn. Univ., Ser. Fiz.-Mat. Nauki [J. Samara State Tech. Univ., Ser. Phys. Math. Sci.], 2021, vol. 25, no. 3, pp. 508–518. EDN: RCYACI. DOI: https://doi.org/10.14498/vsgtu1854.
  6. Fu H., Barlow J. A regularized structured total least squares algorithm for high-resolution image reconstruction, Linear Algebra Appl., 2004, vol. 391, pp. 75–98. DOI: https://doi.org/10.1016/S0024-3795(03)00660-8.
  7. Mesarovic V. Z., Galatsanos N. P., Katsaggelos A. K. Regularized constrained total least squares image restoration, IEEE Trans. Image Process., 1995, vol. 4, no. 8, pp. 1096–1108. DOI: https://doi.org/10.1109/83.403444.
  8. Zhu W., Wang Y., Yao Y., Chang J., Graber H. L., Barbour R. L. Iterative total least-squares image reconstruction algorithm for optical tomography by the conjugate gradient method, J. Opt. Soc. Am. A, 1997, vol. 14, no. 4, pp. 799–807. DOI: https://doi.org/10.1364/josaa.14.000799.
  9. Zhu W., Wang Y., Zhang J. Total least-squares reconstruction with wavelets for optical tomography, J. Opt. Soc. Am. A, vol. 15, no. 10, pp. 2639–2650. DOI: https://doi.org/10.1364/josaa.15.002639.
  10. Lemmerling P., Mastronardi N., Van Huffel S. Efficient implementation of a structured total least squares based speech compression method, Linear Algebra Appl., 2003, vol. 366, pp. 295–315. DOI: https://doi.org/10.1016/S0024-3795(02)00465-2.
  11. Khassina E. M., Lomov A. A. Audio files compression with the STLS-ESM method, St. Petersburg State Polytechnical University Journal. Computer Science. Telecommunications and Control Systems, 2015, vol. 229, no. 5, pp. 88–96. EDN: VAWFWT. DOI: https://doi.org/10.5862/JCSTCS.229.9.
  12. Golub G. H., Van Loan C. An analysis of the total least squares problem, SIAM J. Matrix Anal. Appl., 1980, vol. 17, no. 6, pp. 883–893. DOI: https://doi.org/10.1137/0717073.
  13. Zhdanov A. I., Shamarov P. A. The direct projection method in the problem of complete least squares, Autom. Remote Control, 2000, vol. 61, no. 4, pp. 610–620. EDN: LGBGAF.
  14. Ivanov D., Zhdanov A. Symmetrical augmented system of equations for the parameter identification of discrete fractional systems by generalized total least squares, Mathematics, 2021, vol. 9, no. 24, 3250. EDN: QFMGJB. DOI: https://doi.org/10.3390/math9243250.
  15. Björk Å. Newton and Rayleigh quotient methods for total least squares problem, In: Recent Advances in Total Least Squares Techniques and Errors in Variables Modeling, Proceedings of the Second Workshop on Total Least Squares and Errors-in-Variables Modeling (Leuven, Belgium, August 21–24, 1996). Philadelphia, PA, USA, SIAM, 1997, pp. 149–160.
  16. Björck Å., Heggernes P., Matstoms P. Methods for large scale total least squares problems, SIAM J. Matrix Anal. Appl., 2000, vol. 22, no. 2, pp. 413–429. DOI: https://doi.org/10.1137/S0895479899355414.
  17. Fasino D., Fazzi A. A Gauss–Newton iteration for total least squares problems, BIT Numer. Math., 2018, vol. 58, no. 2, pp. 281–299. DOI: https://doi.org/10.1007/s10543-017-0678-5.
  18. Mohammedi A. Rational–Lanczos technique for solving total least squares problems, Kuwait J. Sci. Eng., 2001, vol. 28, no. 1, pp. 1–12.
  19. Fierro R. D., Golub G. H., Hansen P. C., O’Leary D. P. Regularization by truncated total least squares, SIAM J. Sci. Comp., 1997, vol. 18, no. 4, pp. 1223–1241. DOI: https://doi.org/10.1137/S1064827594263837.
  20. Golub G. H., Hansen P. C., O’Leary D. P. Tikhonov regularization and total least squares, SIAM J. Matrix Anal. Appl., 1999, vol. 21, no. 1, pp. 185–194. DOI: https://doi.org/10.1137/S0895479897326432.
  21. Lampe J., Voss H. Solving regularized total least squares problems based on eigenproblems, Taiwanese J. Math., 2010, vol. 14, no. 3A, pp. 885–909. DOI: https://doi.org/10.11650/twjm/1500405873.
  22. Sima D. M., Van Huffel S., Golub G. H. Regularized total least squares based on quadratic eigenvalue problem solvers, BIT Numer. Math., 2004, vol. 44, no. 4, pp. 793–812. DOI: https://doi.org/10.1007/s10543-004-6024-8.
  23. Lampe J., Voss H. Efficient determination of the hyperparameter in regularized total least squares problems, Appl. Numer. Math., 2012, vol. 62, no. 9, pp. 1229–1241. DOI: https://doi.org/10.1016/j.apnum.2010.06.005.
  24. Zhdanov A. I. Direct recurrence algorithms for solving the linear equations of the method of least squares, Comput. Math. Math. Phys., 1994, vol. 34, no. 6, pp. 693–701. EDN: VKRSPF.
  25. Vainiko G. M., Veretennikov A. Yu. Iteratsionnye protsedury v nekorrektno postavlennykh zadachakh [Iteration Procedures in Ill-Posed Problems]. Moscow, Nauka, 1986, 177 pp.
  26. Zhdanov A. I. Implicit iterative schemes based on singular decomposition and regularizing algorithms, Vestn. Samar. Gos. Tekhn. Univ., Ser. Fiz.-Mat. Nauki [J. Samara State Tech. Univ., Ser. Phys. Math. Sci.], 2018, vol. 22, no. 3, pp. 549–556. EDN: PJITAX. DOI: https://doi.org/10.14498/vsgtu1592.
  27. Zhdanov A. I. The solution of ill-posed stochastic linear algebraic equations by the maximum likelihood regularization method, USSR Comput. Math. Math. Phys., 1988, vol. 28, no. 5, pp. 93–96. DOI: https://doi.org/10.1016/0041-5553(88)90014-6.
  28. Gfrerer H. An a posteriori parameter choice for ordinary and iterated Tikhonov regularization of ill-posed problems leading to optimal convergence rates, Math. Comp., 1987, vol. 49, no. 180, pp. 507–522. DOI: https://doi.org/10.1090/S0025-5718-1987-0906185-4.
  29. Hämarik U., Tautenhahn U. On the monotone error rule for parameter choice in iterative and continuous regularization methods, BIT Numer. Math., 2001, vol. 41, no. 5, pp. 1029–1038. DOI: https://doi.org/https://doi.org/10.1023/A:1021945429767.
  30. Tautenhahn U., Hämarik U. The use of monotonicity for choosing the regularization parameter in ill-posed problems, Inverse Probl., 1999, vol. 15, no. 6, pp. 1487–1505. DOI: https://doi.org/10.1088/0266-5611/15/6/307.
  31. Hansen P. C. Regularization tools version 4.0 for Matlab 7.3, Numer. Algorithms, 2007, vol. 46, no. 2, pp. 189–194. DOI: https://doi.org/10.1007/s11075-007-9136-9.

Дополнительные файлы

Доп. файлы
Действие
1. JATS XML
Скачать
2. Figure 1. RMSE of the solution (8) at the \(k\)-th iteration for various values of the parameter \(\mu ^{-1}\): 1 – \(\mu ^{-1}=10^{-5}\sigma \), 2 – \(\mu ^{-1}=10^{-1}\sigma \); 3 – \(\mu ^{-1}=10^{-2}\sigma\)

Скачать (85KB)
Метаданные
3. Figure 2. RMSE of the solution (13) for various values of the parameter \(\alpha _i=10^{-4}\sigma ^{2} i\)

Скачать (160KB)
Метаданные

© Авторский коллектив; Самарский государственный технический университет (составление, дизайн, макет), 2022

Creative Commons License
Эта статья доступна по лицензии Creative Commons Attribution 4.0 International License.

Согласие на обработку персональных данных с помощью сервиса «Яндекс.Метрика»

1. Я (далее – «Пользователь» или «Субъект персональных данных»), осуществляя использование сайта https://journals.rcsi.science/ (далее – «Сайт»), подтверждая свою полную дееспособность даю согласие на обработку персональных данных с использованием средств автоматизации Оператору - федеральному государственному бюджетному учреждению «Российский центр научной информации» (РЦНИ), далее – «Оператор», расположенному по адресу: 119991, г. Москва, Ленинский просп., д.32А, со следующими условиями.

2. Категории обрабатываемых данных: файлы «cookies» (куки-файлы). Файлы «cookie» – это небольшой текстовый файл, который веб-сервер может хранить в браузере Пользователя. Данные файлы веб-сервер загружает на устройство Пользователя при посещении им Сайта. При каждом следующем посещении Пользователем Сайта «cookie» файлы отправляются на Сайт Оператора. Данные файлы позволяют Сайту распознавать устройство Пользователя. Содержимое такого файла может как относиться, так и не относиться к персональным данным, в зависимости от того, содержит ли такой файл персональные данные или содержит обезличенные технические данные.

3. Цель обработки персональных данных: анализ пользовательской активности с помощью сервиса «Яндекс.Метрика».

4. Категории субъектов персональных данных: все Пользователи Сайта, которые дали согласие на обработку файлов «cookie».

5. Способы обработки: сбор, запись, систематизация, накопление, хранение, уточнение (обновление, изменение), извлечение, использование, передача (доступ, предоставление), блокирование, удаление, уничтожение персональных данных.

6. Срок обработки и хранения: до получения от Субъекта персональных данных требования о прекращении обработки/отзыва согласия.

7. Способ отзыва: заявление об отзыве в письменном виде путём его направления на адрес электронной почты Оператора: info@rcsi.science или путем письменного обращения по юридическому адресу: 119991, г. Москва, Ленинский просп., д.32А

8. Субъект персональных данных вправе запретить своему оборудованию прием этих данных или ограничить прием этих данных. При отказе от получения таких данных или при ограничении приема данных некоторые функции Сайта могут работать некорректно. Субъект персональных данных обязуется сам настроить свое оборудование таким способом, чтобы оно обеспечивало адекватный его желаниям режим работы и уровень защиты данных файлов «cookie», Оператор не предоставляет технологических и правовых консультаций на темы подобного характера.

9. Порядок уничтожения персональных данных при достижении цели их обработки или при наступлении иных законных оснований определяется Оператором в соответствии с законодательством Российской Федерации.

10. Я согласен/согласна квалифицировать в качестве своей простой электронной подписи под настоящим Согласием и под Политикой обработки персональных данных выполнение мною следующего действия на сайте: https://journals.rcsi.science/ нажатие мною на интерфейсе с текстом: «Сайт использует сервис «Яндекс.Метрика» (который использует файлы «cookie») на элемент с текстом «Принять и продолжить».