Basic properties of an inverse iteration algorithm for solving linear systems with positive definite matrices

Authors

  • V.N. Ivanov Perm State University (PSU)

Keywords:

systems of linear algebraic equations, iteration methods, variable metric methods, mechanical systems, equations of motion, numerical integration

Abstract

The problem of solving positive definite systems of linear equations with slowly varying coefficients is considered. The problem is reduced to solving the equations of motion for mechanical systems with respect to accelerations when performing their numerical integration. A new iteration method of solution is proposed. It is shown that this method is a modification of the variable metric Powell-Broyden’s method. Some conditions of convergence are obtained and the basic properties of the method are considered. It is proved that, in the case of exact arithmetic, the method converges after a finite number of iterations, which does not exceed the rank of the perturbation matrix for the linear system. A comparative efficiency of the method is shown by an example of solving the equation of motion for some particular mechanical systems.

Author Biography

V.N. Ivanov

References

  1. Величенко В.В. Матрично-геометрические методы в механике с приложениями к задачам робототехники. М.: Наука, 1988.
  2. Лилов Л.К. Моделирование систем связанных тел. М.: Наука, 1993.
  3. Голуб Дж., Ван Лоун Ч. Матричные вычисления. М.: Мир, 1999.
  4. Аоки М. Введение в методы оптимизации. М.: Наука, 1977.
  5. Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. М.: Мир, 1985.
  6. Иванов В.Н. Модификация алгоритма Пауэлла-Бройдена для решения систем линейных алгебраических уравнений // Вестник Пермского университета. Информационные системы и технологии. 2005. Вып. 4. 115-119.
  7. Поляк Б.Т. Введение в оптимизацию. М.: Наука, 1983.
  8. Химмельблау Д. Прикладное нелинейное программирование. М.: Мир, 1975.
  9. Дэннис Дж., Шнабель Р. Численные методы безусловной оптимизации и решения нелинейных уравнений. М.: Мир, 1988.
  10. Nocedal J., Wright S.J. Numerical Optimization. Berlin: Springer, 2006.
  11. Мину М. Математическое программирование. Теория и алгоритмы. М.: Наука, 1990.
  12. Фиакко А., Мак-Кормик Г. Нелинейное программирование. Методы последовательной безусловной минимизации. М.: Мир, 1972.
  13. Conn A.R., Gould N.I. M., Toint Ph.L. Convergence of quasi-Newton matrices generated by the symmetric rank-one update // Mathematical Programming. 1991. 50, N 1. 177-195.
  14. Byrd R.H., Khalfan H.F., Schnabel R.B. Analysis of a symmetric rank-one trust region method // SIAM J. on Optimization. 1996. 6. 1025-1039.
  15. Khalfan H.F., Byrd R.H., Schnabel R.B. A theoretical and experimental study of the symmetric rank-one update // SIAM J. on Optimization. 1993. 3. 1-24.
  16. Farzin M., Malik Abu H., Wah J.L. Multi-steps symmetric rank-one update for unconstrained optimization // World Applied Sci. J. 2009. 7, N 5. 610-615.
  17. Farzin M., Malik Abu H., Wah J.L. Memoryless modified symmetric rank-one method for large-scale unconstrained optimization // American J. of Applied Sciences. 2009. 6, N 12. 2054-2059.
  18. Farzin M., Malik Abu H., Wah J.L. Convergence of symmetric rank-one method based on modified quasi-Newton equation // J. of Math. Res. 2010. 2, N 3. 97-102.
  19. Yueting Y., Chengxian X. A switching algorithm based on modified quasi-Newton equation // Numer. Math. A J. of Chinese Universities. 2006. 15, N 3. 257-267.
  20. Wah J.L., Malik Abu H. Convergence of a positive definite symmetric rank-one method with restart // Advanced Modeling and Optimization. 2009. 11, N 4. 423-433.
  21. Бячков А.Б., Иванов В.Н., Шимановский В.А. Классификация форм уравнений динамики систем твердых тел со структурой дерева // Вестник Пермского университета. Математика. Механика. Информатика. 2009. Вып. 4. 109-116.

Published

09-06-2012

How to Cite

Иванов В.Н. Basic Properties of an Inverse Iteration Algorithm for Solving Linear Systems With Positive Definite Matrices // Numerical Methods and Programming (Vychislitel’nye Metody i Programmirovanie). 2012. 13. 366-376

Issue

Section

Section 1. Numerical methods and applications