автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Вычисление параметров линейных дискретных динамических систем, описываемых уравнениями свертки

Введение.

1. Постановка задачи идентификации линейных дискретных динамических систем, описываемых уравнениями свертки, и обзор методов ее решения.

1.1. Формулировка задачи.

1.2. Методы вычисления параметров линейных динамических систем с ошибками во входном и выходном сигналах.

2. Метод расширенной системы уравнений в регуляризованной задаче наименьших квадратов.

2.1. Численная обусловленность расширенной системы уравнений, соответствующей регуляризованной задаче наименьших квадратов.

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

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

2.4. Численное исследование разработанного алгоритма решения регуляризованной задачи наименьших квадратов.

3. Расширенная система уравнений в методе инструментальных переменных.

3.1. Численная обусловленность расширенной системы уравнений, соответствующей задаче с применением инструментальных переменных

Задачи идентификации систем находят широкое применение в технике, экономике, медицине и других областях. Большое внимание уделяется идентификации линейных дискретных динамических систем, описываемых уравнениями свертки [27, 42, 59, 75].

К настоящему времени предложено много различных методов идентификации систем такого типа [43, 69, 70, 81]. К методам определения параметров линейных динамических систем с аддитивными ошибками во входном и выходном сигналах относятся метод инструментальных переменных, метод полных наименьших квадратов, регуляризованный метод полных наименьших квадратов. Для определения параметров линейных динамических систем с аддитивными ошибками только в выходном сигнале используют метод наименьших квадратов, максимального правдоподобия, регуляризованный метод наименьших квадратов, метод Байеса.

Если рассматривать системы с аддитивными ошибками в выходном сигнале, то для определения параметров таких систем наиболее широкое распространение на практике находит метод наименьших квадратов. В линейных дискретных динамических системах, описываемых уравнениями свертки, необходимо определять достаточно большое число параметров и использование метода наименьших квадратов приводит к плохо обусловленным задачам большой размерности. Для таких задач обычно используют регуляризованный метод наименьших квадратов.

В теоретической и практической разработке техники решения задач метода наименьших квадратов участвовали многие математики. Этой теме посвящено большое количество работ. Для решения некорректных и плохо обусловленных задач был предложен А.Н. Тихоновым [37] метод регуляризации. Значительный вклад в развитие регуляризованного метода наименьших квадратов внесли В.Я. Ар-сенин, В.А. Морозов, А.Б. Бакушинский [2, 3, 4, 29, 31]. Статистическая регуляризация систем линейных уравнений исследовалась Е.А. Жуковским, А.И. Ждановым, А. В. Кряневым, В.В. Мелешко [13, 20, 24] и другими учеными.

Если рассматривать линейные дискретные динамические системы, описываемые уравнениями свертки, с аддитивными ошибками во входном и выходном сигналах, то для определения параметров таких систем наиболее широкое распространение получил метод инструментальных переменных, в большей степени из-за того, что для его использования требуется наименьшее количество априорной информации о статистических характеристиках возмущений.

Метод инструментальных переменных был введен в статистике и эконометрике О.Рейерсьюлом (О.11е1егз01) [68] и применялся для решения большого числа задач параметрического оценивания. Применение в области управления динамическими системами впервые было осуществлено в работах К.Вонга (К^опд) и Е.Полака (Е.Ро1ак) [86], П.Янга (Р.Уошщ) и Д.Мейна (Б. Маупе) [62, 88]. В дальнейшем значительный вклад в развитие метода инструментальных переменных сделали Т.Седерстрем (Т.Збс^гв^бт), П.Стойка (Р. ЭЫса), Л.Льюнг (Ь.Г^ш^) [73, 27].

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

Цель диссертационной работы заключается в разработке численно устойчивых алгоритмов решения регуляризованных задач наименьших квадратов и задач с применением инструментальных переменных для определения параметров линейных дискретных динамических систем, описываемых уравнениями свертки.

Для достижения поставленной цели были решены следующие задачи:

1. Преобразование регуляризованной задачи наименьших квадратов к эквивалентной задаче решения расширенной системы линейных алгебраических уравнений (СЛАУ).

2. Исследование численной обусловленности расширенной СЛАУ, соответствующей регуляризованной задаче наименьших квадратов.

3. Разработка численных алгоритмов для решения расширенной СЛАУ, соответствующей регуляризованной задаче наименьших квадратов.

4. Преобразование вычислительной задачи метода инструментальных переменных к задаче решения расширенной СЛАУ.

5. Исследование численной обусловленности расширенной СЛАУ, соответствующей задаче с применением инструментальных переменных.

6. Разработка численных алгоритмов для решения расширенной СЛАУ, соответствующей задаче с применением инструментальных переменных.

7. Проведение на ЭВМ численных исследований разработанных алгоритмов.

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

Исследования полученных методов и алгоритмов в работе проводились на ЭВМ с помощью пакета Matlab 6.5 и программного обеспечения, написанного на Borland Delphi 5.0.

Научная новизна. Новые научные результаты включают в себя:

- преобразование регуляризованной задачи наименьших квадратов к эквивалентной задаче решения расширенной СЛАУ и модификацию этой системы, которая позволила снизить число обусловленности исходной задачи;

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

- преобразование вычислительной задачи метода инструментальных переменных к эквивалентной задаче решения расширенной СЛАУ и модификацию этой системы, которая позволила снизить число обусловленности исходной задачи;

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

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

Материалы диссертационного исследования используются при проведении лабораторных занятий по курсу "Матрицы и вычисления" на кафедре прикладной математики Самарского государственного аэрокосмического университета.

Апробация работы проводилась на следующих научных конференциях:

- 10-й межвузовской конференции "Математическое моделирование и краевые задачи", Самара, 2000;

- научно-практической конференции "Прикладные математические задачи в машиностроении и экономике", Самара, 2001;

- 8-й российской научной конференции профессорско - преподавательского состава, научных сотрудников и аспирантов, Самара, 2001;

- 9-й международной конференции "Математика. Образование. Экономика", Чебоксары, 2001;

- международной конференции "Математическое моделирование 2001", Самара 2001.

Публикации. По теме диссертации опубликовано семь печатных работ.

Структура и объем работы. Диссертация состоит из введения, трех глав, заключения и списка литературы из 89 наимено

Основные результаты и выводы отражены в следующих публикациях:

1. Жданов А.И., Гоголева С.Ю. Оценивание параметров динамических систем методом инструментальных переменных // Труды десятой межвузовской конференции "Математическое моделирование и краевые задачи". Самара: СамГТУ, 2000. Часть 2. С. 44-46.

2. Жданов А.И., Гоголева С.Ю. Решение плохо обусловленных задач идентификации линейных динамических систем методом инструментальных переменных // Сборник докладов научно-практической конференции " Прикладные математические задачи в машиностроении и экономике". Самара: Самарский госуниверситет, 2001. Часть 1. С. 20-22.

3. Жданов А.И., Гоголева С.Ю. Прямой проекционный метод решения задач идентификации с применением инструментальных переменных // Тезисы докладов VIII российской научной конференции профессорско - преподавательского состава, научных сотрудников и аспирантов. Самара. 2001. Часть 2. С. 20-21.

- 914. Гоголева С.Ю. Метод инструментальных переменных для идентификации линейных динамических систем с использованием расширенной матрицы // Тезисы докладов IX международной конференции "Математика. Образование. Экономика." Чебоксары: Чувашский госуниверситет, 2001. С. 81.

5. Гоголева С.Ю., Жданов А.И. Вычисление решений регуля-ризованных задач наименьших квадратов на основе метода расширенной системы уравнений // Труды международной конференции "Математическое моделирование 2001". Самара: СГАУ, 2001. С. 95-97.

6. Жданов А.И., Гоголева С.Ю. Решение задач идентификации динамических систем на основе метода инструментальных переменных // Сборник научных трудов "Перспективные информационные технологии в научных исследованиях, проектировании и обучении". Самара: СГАУ, 2001. С.212.

7. Жданов А.И., Гоголева С. Ю. Об одном алгоритме вычисления регуляризованных решений задач наименьших квадратов // Труды 3-й Международной конференции молодых ученых и студентов "Актуальные проблемы современной науки". Самара: СамГТУ, 2002. Часть 1. С. 16.

Заключение

На основе выполненного диссертационного исследования автором разработаны методы вычисления параметров линейных дискретных динамических систем, описываемых уравнениями свертки. Основные научные и практические результаты, полученные в диссертационной работе, включают в себя:

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

2. Анализ численной обусловленности расширенной СЛАУ, соответствующей регуляризованной задаче наименьших квадратов.

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

4. Преобразование задачи с применением инструментальных переменных для вычисления параметров линейных дискретных динамических систем к эквивалентной задаче решения расширенной СЛАУ.

5. Анализ численной обусловленности расширенной СЛАУ, соответствующей задаче с применением инструментальных переменных.

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

7. Численные исследования, с помощью которых показана эффективность разработанных алгоритмов.

1. Абаффи И., Спедикато Э. Математические методы для линейных и нелинейных уравнений: Проекционные АВв-алгоритмы. М.: Мир, 1996. 268 с.

2. АрсенинВ.Я. О методах решения некорректно постеленных задач. М.: МИФИ, 1973. 236 с.

3. Бакушинский А.Б. Избранные вопросы приближенного решения некорректных задач. М.: МГУ, 1968. 336 с.

4. Бакушинский А.Б. Некоторые вопросы теории регуляризи-рующих алгоритмов //Выч. методы и программирование: Вып. 12.- М.: МГУ, 1969.

5. Беклемишев Д.В. Дополнительные главы линейной алгебры. М.: Наука, 1983. 336 с.

6. Воеводин В.В. Линейная алгебра. М.: Наука, 1974. 400 с.

7. Воеводин В.В. Численные методы алгебры (теория и алгорифмы). М.: Наука, 1966. 248 с.

8. Воеводин В.В., Кузнецов Ю.А. Матрицы и вычисления. М.: Наука, 1984. 320 с.

9. Вычислительные методы /В.И. Крылов, В.В. Бобков, П.И. Монастырный. М.: Наука, 1976. 304 с.

10. Гантмахер Ф.Р. Теория матриц. М.: Наука, 1967. 575 с.

11. Голуб Дж., Ван Лоун Ч. Матричные вычисления. М.: Мир, 1999. 548 с.

12. Деммель Дж. Вычислительная линейная алгебра. Теория и приложения. М.: Мир, 2001. 430 с.

13. Жданов А.И. Вычисление решений некорректных стохастических линейных алгебраических уравнений регуляризован-ным методом наименьших квадратов //ДАН СССР. 1989. т. 306. No 2.

14. Жданов А.И. Вычислительные аспекты метода полных наименьших квадратов и его применения //Труды международной конференции "Математическое моделирование 2001". 2001. Самара. С.95-97.

15. Жданов А.И. Метод полных наименьших квадратов в задачах математического моделирования //Сборник лекций Всеросийской молодежной школы "Современные методы мат. моделирования". Самара. 2001. С. 41-45.

16. Жданов А.И. Прямой последовательный метод решения систем линейных алгебраических уравнений //Докл. РАН. 1997. Т. 356. No 4. С. 442-444.

17. Жданов А.И. Прямые рекуррентные алгоритмы решения линейных задач метода наименьших квадратов // ЖВМиМФ. 1994. Т. 34. No 6. С. 811-814.

18. Жданов А.И., Шамаров П.А. Идентификация параметров дискретной передаточной функции с помощью метода полных наименьших квадратов // Труды восьмой научной межвузовской конференции. 1998. Самара. С. 43.

19. Жданов А.И., Шамаров П.А. Прямой проекционный метод в задаче полных наименьших квадратов // АиТ. 2000. No 4. С. 77-87.

20. Жуковский E.JI. Статистическая регуляризация решений обратных некорректно поставленных задач обработки и интерпретации результатов эксперимента //Методы мат. моделирования, автоматизации обработки наблюдений и их применения. М.: МГУ, 1986. С. 47-72.

21. Закс Ш. Теория статистических выводов. М.: Мир, 1975. 776 с.

22. Икрамов Х.Д. Несимметричная проблема собственных значений. М.: Наука, 1991. 473 с.

23. Кендалл М.Дж., Стьюарт А. Статистические выводы и связи. М.: Наука, 1973. 900 с.

24. Крянев A.B. Статистическая форма регуляриз о ванного метода наименьших квадратов А.Н. Тихонова // Докл. АН СССР. 1986. Т. 291. No 4. С. 780-785.

25. Линник Ю.В. Метод наименьших квадратов и основы математико-статистической обработки наблюдений. М.: Физматгиз, 1962. 349 с.

26. Лоусон Ч., Хенсон Р. Численное решение задач методом наименьших квадратов. М.: Наука. 1986. 230 с.

27. Льюнг Л. Идентификация систем. Теория для пользователя. М.: Наука, 1991. 432 с.

28. Маслов Е. П. Применение теории статиститических решений к задачам оценки параметров объекта // Автоматика и телемеханика. 1963. Т. 28. No 10. С. 1338-1350.

29. Морозов В.А. Некоторые аспекты восстановления сигналов методом регуляризации // Вычислительная математика и программирование. 2001. Т. 2. С. 27-33.

30. Морозов В.А. О псевдорешениях // ЖВМ и МФ. 1969. No 6. С. 9.

31. Морозов В.А. Регулярные методы решения некорректно поставленных задач. М.: Наука, 1987. 240 с.

32. Ортега Дж. Введение в параллельные и векторные методы решения линейных систем. М.: Мир, 1991. 367 с.

33. Парлетт Б. Симметричная проблема собственных значений. М.: Мир, 1983. 382 с.

34. Райе Д. Матричные вычисления и математическое обеспечение. М.: Мир, 1984. 264 с.

35. Регуляризирующие алгоритмы и априорная информация/ А.Н. Тихонов, A.B. Гончарский, В.В. Степанов, А.Г. Ягола. М.: Наука, 1983. 200 с.

36. Сейдж А., Мелза Д. Идентификация систем управления. М. Наука, 1974. 368 с.

37. Тихонов А.H. О некорректных задачах линейной алгебры и устойчивом методе их решения // ДАН СССР. 1965. No 6. С. 163.

38. Тихонов А.Н., Арсенин В.Я. Методы решения некорректных задач. М.: Наука, 1986. 288 с.

39. Тьюарсон Р. Разреженные матрицы. М.: Мир, 1977. -210 с.

40. Уилкинсон Дж. X. Алгебраическая проблема собственных значений. М.: Наука, 1970. 564 с.

41. Хорн Р., Джонсон Ч. Матричный анализ. М.: Мир, 1989. -655 с.

42. Цыпкин Я.З. Основы информационной теории идентификации. М.: Наука, 1984. 320 с.

43. Эйкхофф П. Основы идентификации систем управления. М.: Мир, 1975. 685 с.

44. Эстербю О., Златев 3. Прямые методы для разреженных матриц. М.: Мир, 1987. 120 с.

45. Astrom J.K.J., Eykhoff P. System identification A survey // Automática. 1971. Vol. 7. No. 2. P. 123-162.

46. Barnett V.D. Evaluation of the maximum likelihood estimator where the likelihood équation has multiple roots //Biometrika. 1966. No 53. P. 151-165.

47. Benzi M., Meyer C.D. A direct projection method for sparse linear systems // SIAM J. Sci. Comput., 1995. V. 16. No. 5. P. 11591176.

48. Bjork A. Component-wise perturbation analysis and errors bounds for linear least squares solutions // BIT. 1991. Vol. 31. P. 238-244.

49. Bjork A. Handbook of numerical analysis. V. 1. North-Holland: Elsevier. 1990.

50. Bjork A. Iterative refinement of linear least squares solutions // BIT. 1967. Vol. 7. P. 257-278.

51. Bjork A. Numerical Stability of Methods for Solving Augment Systems // Contemp. Math. 1997. Vol 204. P. 51-59.

52. Bjork A. Pivoting and Stability in the Augment System Method// Numerical Analysis. Proceedings of the 14th Dundee Conference. Griffiths D.F. and Watson G.A. eds. 1991. P. 1-16.

53. Bunch J.R., Nielsen C.P., Sorensen D.C. Rank-one modification of the symmetric eigenproblem // Numer. Math. 1978. No. 31. P. 31-48.

54. Calvetti D., Reichel L. Tikhonov regularization of large linear problems //BIT. 2003. To appear.

55. Givens W. Computation of plane unitary rotations transforming a general matrix to triangular form j/SIAM J. Appl. Math. 1958. No 6. P. 26-50.

56. Golub G.H. Numerical methods for solving linear least squares problems //Numer. Math. 1965. No 7. P. 206-216.

57. Householder A.S. Unitary triangularization of nonsymmetric matrix //J.ACM 1958. No 5. P. 339-342.

58. Johansson R. System modeling and identification. Prentice-Hall. Englewood Cliffs. NJ. 1993.

59. Kale R.K. On the solution of the likelihood equation by iteration processes //Biometrika. 1961. No 48. P. 452-456.

60. Matstoms P. Sparse QR factorization in MATLAB // Trans. Math. Software. 1994. No. 20. P. 136-159.

61. Mayne D.Q. A method for estimating discrete time transfer functions //In Advances in Computer Control. Second UKAC Control Convention. University of Bristol. 1967.

62. Mzyk G. Application of instrumental variable method to identification of systems //Proceeding of the XIII Krajowa Konferencja Automatyky. Opole. 1999.

63. Mzyk G. Application of instrumental variable method to the identification of Hammerstein Wiener systems //Report.

64. Wroclaw University of Technology. Poland. 2000.

65. Northan H.W. One likelihood adjustment may be inadequate //Biometrics. 1956. No 12. P. 79-81.

66. Peterka V. Bayesian approach to system identification. In trends and Progress in system identification. Pergamon Press. Elmsford, N.Y. 1981.

67. Peterka V. Bayesian system identification //Automatica. 1981. No 17. P. 41-53.

68. Reiersol O. Confluence analysis by means of lag moments and other methods of confluence analysis // Econometrica. 1941. Vol. 9. P. 1-23.

69. Rugh W. Linear system theory, second edition. Prentice Hall. New Jersey. 1996.

70. Schoukens J., Pintelon R. Identification of linear systems: a practical guideline to accurate modeling. Pergamon Press. Oxford. 1991.

71. Shinamura T., Arima Y. Input estimation and instrumental variable method for noisy speech analysys // Proc. Int. Technical Conf. Circuits systems, computers and communications. 1999. P. 17-20.

72. Soderstrom T., Stoica P. Comparison of some instrumental variable methods consistency and accuracy aspects // Automatica. 1981. Vol. 17. No. 1. P. 101-115.

73. Soderstrom T., Stoica P. Instrumental variable methods for system identification. Lecture notes in control and information sciences. Springer-Verlag. New York. 1983.

74. Soderstrom T., Stoica P. On the stability of dynamic models obtained by least squares identification // IEEE Trans. Automat. Contr. 1981. Vol. AC-26. No. 2. P. 575-577.

75. Soderstrom T., Stoica P. System identification. Prentice-Hall. London. U.K. 1989.

76. Steiglitz K., McBride L.E. A technique for the identification of linear systems // IEEE Trans. Automat. Contr. 1965. Vol. AC-10. No. 5. P. 461-464.

77. Stoica P., Friedlander B., Soderstrom T. Instrumental variable methods for ARMA models // Control and Dinamic Systems. 1986. Vol. XXIV.

78. Stoica P., Soderstrom T. Bias correction in least-squares identification // Int. J. Control, 1982. V. 35. No. 3. P. 449-457.

79. Stoica P., Soderstrom T. Optimal Instrumental-variable Methods for Identification of Multivariable Linear Systems // Automatica. 1983. Vol. 19. No. 4. P. 425-429.

80. Stoica P., Soderstrom T. The Steiglitz-McBride identification algorithm revised convergence analysis and accuracy aspects // IEEE Trans. Automat. Contr. 1981. Vol. AC-26. No. 3. P. 712-717.

81. Strejc V. Trends in identification // Automatica. 1981. Vol. 17. No. 1. P. 7-21.

82. Trefethen L.N., Bau D. Numerical Linear Algebra. SIAM, 1997. 373 p.

83. Van Huffel S., Vandewalle J. Algebraic connection between the least squares and total least squares problems // Numer. Math. Vol. 55. P. 431-449.

84. Van Huffel S., Vandewalle J. Comparison of total least squares and instrumental variable methods for parameter estimation of transfer function models // Internat. J. Control. 1989. Vol. 50. P. 1039-1056.

85. Van Huffel S., Vandewalle J. On the accuracy of total least squares technicues in the presence of errors on all data // Automatica. 1989. Vol. 25. P. 765-769.

86. Wong K.Y., Polak E. Identification of linear discrete time systems using the instrumental variable approach // IEEE Trans. Automat. Contr. 1967. Vol. AC-12. P. 707-718.

87. Young P.C. Coments on on-line identification of linear dynamic systems with applications to Kalman filtering // IEEE Trans. Automat. Contr. 1972. Vol. AC-17. P. 269-270.

88. Young P.C. On a weighted steepest descent method of process parameter estimation. Report. Cambridge University. Engineering Laboratory. 1965.