Научные статьи \ Математика. Естественные науки \ Математика \ Вычислительная математика. Численный анализ

О современных ортогонализованных алгоритмах оптимальной дискретной фильтрации

О современных ортогонализованных алгоритмах оптимальной дискретной фильтрации

Автор: Цыганова Юлия Владимировна, Куликова Мария Вячеславовна

Журнал: Вестник Южно-Уральского государственного университета. Серия: Математическое моделирование и программирование @vestnik-susu-mmp

Рубрика: Обзорные статьи

Статья в выпуске: 4 т.11, 2018 года.

Бесплатный доступ

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

Еще

Дискретная фильтрация, линейные стохастические системы, фильтр калмана, матричные ортогональные преобразования, ортогонализованные алгоритмы

Короткий адрес: https://sciup.org/147232912

IDR: 147232912   |   УДК: 519.61+519.711:681.5   |   DOI: 10.14529/mmp180401

On modern array algorithms for optimal discrete filtering

Nowadays, computational methods for optimal estimation have become an independent field of research and have received a great progress. Modern numerically efficient array algorithms are attractive not only because of their robustness to machine round-off errors, but additionally because of utilization various types of matrix orthogonal transformations. Thus, their design pattern is well suited for parallel implementations on modern computing systems. These properties allow to develop new efficient information technologies, in particular, the techniques that are applicable for solving real-time problems as well as for processing big data arrays. This paper gives a brief survey of modern array algorithms for optimal linear discrete-time filtering. Four large classes of array algorithms are considered: square-root array algorithms, array algorithms based on weighted orthogonalization, J-orthogonal array algorithms and methods based on singular value decomposition. We suggest a classification of array algorithms according to the type of the utilized matrix orthogonal transformation on the basis of which these algorithms are designed. Such classification suggests a more simple way for understanding the array filtering methods' design and gives a choice for finding their most effective implementation for estimating multivariable discrete-time linear stochastic systems. The computational aspects of array algorithms are investigated. It includes the numerical stability to machine round-off errors, and discussion of efficient software implementation for the array algorithms under examination. Finally, the array algorithms investigated in this paper are algebraically equivalent to the conventional implementation of the discrete-time Kalman filter, but they possess the significantly improved computational properties. The results of the presented comparative study allow to conclude that the use of array algorithms in solving practical problems helps to obtain numerically efficient and reliable solutions.

Еще

Список литературы О современных ортогонализованных алгоритмах оптимальной дискретной фильтрации

  • Kalman, R.E. A New Approach to Linear Filtering and Prediction Problems / R.E. Kalman // Journal of Basic Engineering. - 1960. - V. 82, № 1. - P. 35-45.
  • Potter, J.E. Statistical Filtering of Space Navigation Measurements / J.E. Potter, R.G. Stern // Proceedings 1963 AIAA Guidance and Control Conference. - 1963. - 13 p.
  • Rauch, H.E. Maximum Likelihood Estimates of Linear Dynamic Systems / H.E. Rauch, C.T. Striebel, F. Tung // AIAA journal. - 1965. - V. 3, № 8. - P. 1445-1450.
  • Dyer, P. Extension of Square-Root Filtering to Include Process Noise / P. Dyer, S. McReynolds // Journal of Optimization Theory and Applications. - 1969. - № 3. - P. 444-459.
  • Schmidt, S.F. Computational Techniques in Kalman Filtering / S.F. Schmidt // Theory and Applications of Kalman Filtering. NATO Advisory Group for Aerospace Research and Development, AGARDograph 139. - 1970.
  • Kaminski, P.G. Discrete Square-Root Filtering: A Survey of Current Techniques / P.G. Kaminski, A.E. Bryson, S.F. Schmidt // IEEE Transactions on Automatic Control. - 1971. - V. 16, № 6. - P. 727-735.
  • Kaminski, P.G. Square Root Filtering and Smoothing for Discrete Processes. Ph.D. Thesis / P.G. Kaminski. - Stanford University, 1971.
  • Kailath, T. Some New Algorithms for Recursive Estimation in Constant Linear System / T. Kailath // IEEE Transactions on Information Theory. - 1973. - V. 19, № 11. - P. 750-760.
  • Morf, M. Some New Algorithms for Recursive Estimation in Constant, Linear Discrete-Time Systems / M. Morf, G.S. Sidhu, T. Kailath // IEEE Transactions on Automatic Control. - 1974. - V. 19, № 4. - P. 315-323.
  • Morf, M. Square-Root Algorithms for Least-Squares Estimation /M. Morf, T. Kailath // IEEE Transactions on Automatic Control. - 1975. - V. 20, № 4. - P. 487-497.
  • Thornton, C.L. Numerical Comparison of Discrete Kalman Filtering Algorithms: an Orbit Determination Case Study / C.L. Thornton, G.J. Bierman // JPL Technical Memorandum 33-771. - Pasadena, 1976. - 48 p.
  • Thornton, C.L. Triangular Covariance Factorizations for Kalman Filtering. Ph.D. Thesis / C.L. Thornton. - University of California at Los Angeles, 1976.
  • Bierman, G.J. Factorization Methods For Discrete Sequential Estimation / G.J. Bierman. - New York: Academic Press, 1977.
  • Фомин, В.Н. Рекуррентное оценивание и адаптивная фильтрация / В.Н. Фомин. - М.: Наука, 1984.
  • Verhaegen, M. Numerical Aspects of Different Kalman Filter Implementations / M. Verhaegen, P. Van Dooren // IEEE Transactions on Automatic Control. - 1986. - V. 31, № 10. - P. 907-917.
  • Jover, J.M. A Parallel Architecture for Kalman Filter Measurement Update and Parameter Estimation / J.M. Jover, T. Kailath // Automatica. - 1986. - V. 22, № 1. - P. 43-57.
  • Огарков, М.А. Методы статистического оценивания параметров случайных процессов / М.А. Огарков. - М.: Энергоатомиздат, 1990.
  • Wang, L. Kalman Filter Algorithm Based on Singular Value Decomposition / L. Wang, G. Libert, P. Manneback // Proceedings of the IEEE Conference on Decision and Control, Tuczon, 1992. - P. 1224-1229.
  • Sayed, A.H. Extended Chandrasekhar Recursions / A.H. Sayed, T. Kailath // IEEE Transactions on Automatic Control. - 1994. - V. 9, № 3. - P. 619-622.
  • Park, P. New Square-Root Algorithms for Kalman Filtering / P. Park, T. Kailath // IEEE Transactions on Automatic Control - 1995. - V. 40, № 5. - P. 895-899.
  • Голуб, Дж. Матричные вычисления / Дж. Голуб, Ч. Ван Лоун. - М.: Мир, 1999.
  • Kailath, T. Linear Estimation / T. Kailath, A.H. Sayed, B. Hassibi. - New Jersey: Prentice Hall, 2000.
  • Grewal, M.S. Kalman Filtering: Theory and Practice Using MATLAB / M.S. Grewal, A.P. Andrews. - New Jersey: Prentice Hall, 2001.
  • Higham, N.J. Accuracy and Stability of Numerical Algorithms / N.J. Higham. - Philadelphia: SIAM, 2002.
  • Higham, N.J. J-Orthogonal Matrices: Properties and Generalization / N.J. Higham // SIAM Review. - 2003. - V. 45, № 3. - P. 504-519.
  • Zhou, B.A. UD Factorization-Based Nonlinear Adaptive Set-Membership Filter for Ellipsoidal Estimation / B. Zhou, J. Han, G. Liu // International Journal of Robust and Nonlinear Control. - 2008. - V. 18. - P. 1513-1531.
  • Daowang, F. Square-Root Second-Order Extended Kalman Filter and its Application in Target Motion Analysis / F. Daowang, L. Teng, H.Z. Tao // Radar, Sonar and Navigation. - 2010. - V. 4, № 3. - P. 329-335.
  • Gibbs, B.P. Advanced Kalman Filtering, Least-Squares and Modeling: A Practical Handbook / B.P. Gibbs. - Hoboken, New Jersey: John Wiley and Sons, 2011.
  • Семушин, И.В. Адаптивные системы фильтрации, управления и обнаружения: коллективная монография / И.В. Семушин, Ю.В. Цыганова, М.В. Куликова и др. - Ульяновск: УлГУ, 2011.
  • Семушин, И.В. Вычислительные методы алгебры и оценивания / И.В. Семушин. - Ульяновск: УлГТУ, 2011.
  • Семушин, И.В. Устойчивые алгоритмы фильтрации - обзор и новые результаты для систем судовождения / И.В. Семушин, Ю.В. Цыганова, К.В. Захаров // Информационные технологии и вычислительные системы. - 2013. - № 4. - С. 90-112.
  • Kulikova, M.V. Stochastic Volatility Models for Exchange Rates and Their Estimation Using Quasi-Maximum-Likelihood Methods: an Application to the South African Rand / M.V. Kulikova, D.R. Taylor // Journal of Applied Statistics. - 2013. - V. 40, № 3. - P. 495-507.
  • Kulikova, M.V. Adaptive Wave Filtering for Marine Vessels within UD-Based Algorithms / M.V. Kulikova, J.V. Tsyganova, I.V. Semushin // Proceedings of the ECC2016, European Control Conference. - Aalborg, 2016. - P. 807-812.
  • Цыганова, Ю.В. О методах реализации UD-фильтра / Ю.В. Цыганова // Известия высших учебных заведений. Поволжский регион. Физико-математические науки. - 2013. - № 3. - P. 84-104.
  • Semushin, I.V. Numerically Efficient UD Filter Based Channel Estimation for OFDM Wireless Communication Technology / I.V. Semushin, Yu.V. Tsyganova, A.V. Tsyganov, E.F. Prokhorova // Procedia Engineering. - 2017. - V. 201. - P. 726-735.
  • Kulikova, M.V. Improved Discrete-Time Kalman Filtering within Singular Value Decomposition / M.V. Kulikova, J.V. Tsyganova // IET Control Theory and Applications. - 2017. - V. 11, № 5. - P. 2412-2418.
  • Цыганова, Ю.В. Ортогонализованные блочные методы для параметрической идентификации дискретных линейных стохастических систем: дис.. д-ра физ.-мат. наук / Ю.В. Цыганова. - Ульяновск, 2017.
  • Semushin, I.V. Numerically Efficient LD-computations for the Auxiliary Performance Index Based Control Optimization under Uncertainties / I.V. Semushin, J.V. Tsyganova, A.V. Tsyganov // Proceedings of the 17th IFAC Workshop on Control Applications of Optimization, Yekaterinburg, Russia, October 15-19, 2018. - Yekaterinburg, 2018. - V. 51. - P. 568-573.
  • D'Souza, Ch. Information Formulation of the UDU Kalman Filter / Ch. D'Souza, R. Zanetti // IEEE Transactions on Aerospace and Electronic Systems. - 2018.
Еще
QR-код для установки приложения SciUp Наведите камеру и скачайте бесплатное приложение SciUp