Алгоритмы метода полных наименьших квадратов и их применение в задачах идентификации динамических систем тема диссертации и автореферата по ВАК РФ 05.13.16, кандидат физико-математических наук Шамаров, Павел Александрович

• Шамаров, Павел Александрович
• кандидат физико-математических наук
• 2000

Оглавление диссертации кандидат физико-математических наук Шамаров, Павел Александрович

Введение

Глава 1. Постановка задачи полных наименьших квадратов и обзор численных методов ее решения

1.1. Формулировка задачи полных наименьших квадратов

1.2. Применение метода полных наименьших квадратов в прикладных задачах

1.3. Обзор численных алгоритмов метода полных наименьших квадратов

1.3.1. Численные методы и подходы решения задачи ПНК

1.3.2. Методы решения плохо обусловленных СЛАУ

1.4. Выводы по главе

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

2.1. Преобразование задачи ПНК к решению расширенной системы уравнений

2.2. Применение прямого рекуррентного метода для решения задачи ПНК

2.3. Численная обусловленность расширенной системы уравнений

2.3.1. Исследование обусловленности расширенной системы уравнений в линейных задачах МНК

- 32.3.2. Исследование обусловленности расширенной системы уравнений в задачах ПНК 2.3.3. Обратный анализ ошибок в задачах ПНК

2.4. Методы поиска коэффициента смещения нормальной СЛАУ

2.5. Численное исследование разработанного алгоритма

2.6. Выводы по главе

Глава 3. Идентификация параметров дискретной передаточной функции на основе МПНК

3.1. Модели динамических линейных стационарных систем

3.2. Анализ методов идентификации параметров дискретных передаточных функций стохастических динамических систем

3.3. Применение разработанного алгоритма для задачи идентификации

3.4. Численные исследования идентификации параметров дискретной передаточной функции

3.5. Выводы по главе 3 94 Заключение

Введение диссертации (часть автореферата) на тему «Алгоритмы метода полных наименьших квадратов и их применение в задачах идентификации динамических систем»

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

Проблема нахождения решений приближенных (как детерминированных, так и стохастических) СЛАУ возникает в огромном числе задач математического моделирования. К их числу принадлежат задачи регрессионного анализа с ошибками в независимых переменных [83], идентификации стохастических дискретных динамических систем, описываемых линейными разностными уравнениями [8], восстановления сигналов [82] и т. д. В настоящее время наиболее разработанной ч; является задача решения приближенных СЛАХ в которой неточно задан лишь вектор правой части, а матрица системы задана точно. Одним из наиболее эффективных и универсальных методов решения этой задачи является классический линейный метод наименьших квадратов (МНК). Это связано с тем фактом, что в настоящее время имеется достаточное число высокоэффективных (в вычислительном отношении) алгоритмов для МНК, а также, что многие статистические свойства оценок решений,полученных на основе МНК для приближенных стохастических СЛАУ (задач регрессионного анализа); не зависят от функций распределений возмущений.

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

Постановка задачи полных наименьших квадратов впервые была рассмотрена академиком Ю.В. Линником (под названием " метод ортогональных проекций") применительно к задачам регрессионного анализа [17]. В дальнейшем, значительный вклад в развитие МПНК и его анализ внесли А.И. Жданов [9], A.B. Крянев [16], а также зарубежные ученые Д. Голуб (G. Golub), С. Ван Лоан (С. Van Loan) [49], [50], С. Ван Хаффел (S. Van Huffel), Д. Вандевейл (J. Vandewalle) [76], [79], А. Вьорк (А. Björk) [36].

Для стохастических задач МПНК сохраняет большинство свойств классического линейного МНК, таких, например, как независимость от конкретного вида функций распределения ошибок. Но вычислительная задача полных наименьших квадратов (ПНК) значительно сложнее, чем задача линейных наименьших квадратов. Задача ПНК является нелинейной и в большинстве случаев плохо обусловленной. Плохая обусловленность задачи не позволяет эффективно применять численно устойчивые алгоритмы без значительного увеличения числа арифметических операций, необходимых для ее решения.

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

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

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

1. Преобразование исходной задачи ПНК к задаче решения совместной расширенной СЛАУ.

2. Исследование обусловленности расширенной СЛАУ, соответствующей задаче ПНК.

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

4. Исследование и выбор алгоритма для вычисления минимального сингулярного числа в задаче ПНК.

5. Решение на основе ПНК частично приближенных СЛАУ (вектор правой части и некоторая часть столбцов матрицы которой известны приближенно) в задачах параметрической идентификации дискретных передаточных функций.

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

Научная новизна заключается в следующем. в Разработан метод преобразования исходной задачи ПНК к задаче решения совместной расширенной СЛАУ.

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

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

• Найдены экспериментальные оценки для оптимального масштабного множителя.

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

• Вычислено значение оптимального множителя в зависимости от нормы искомого вектора.

• Разработан численный алгоритм идентификации параметров дискретной передаточной функции в модели выходной ошибки.

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

Методы исследований. При формулировке и доказательстве результатов используются положения линейной алгебры, теории вероятностей, теории возмущений, а также теории идентификации дискретных динамических систем. Исследования полученных методов и алгоритмов проводились на основе имитационного моделирования. При разработке программного обеспечения использовался пакет МАТЬАВ (версия 5.3).

По теме диссертации опубликовано 4 работы [84], [14], [13], [24]. Диссертация состоит из введения, трех глав, заключения и списка литературы из 84 наименований источников отечественной и зарубежной литературы.

Заключение диссертации по теме «Применение вычислительной техники, математического моделирования и математических методов в научных исследованиях (по отраслям наук)», Шамаров, Павел Александрович

3.5. Выводы по главе 3

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

V; / Ж Ч V w/ Vi >

Д ' <7 л -У ' Н А ' i'l

Л л *} ' .<\А .

V • • / ' • . .V» . " -V-.■-. F ^ <?• \\ I ^ AsH' \ > • v 1

U<0 \ /'

A<t> \ y<t) оценю! метода ГМК о»енк-и коррелйниоиного метоля формируемой смещенной нормальной СЛАУ может быть вычислен без обращения матриц.

2. Результаты имитационного моделирования показали высокую численную устойчивость разработанного метода в применении к задаче идентификации параметров дискретных передаточных функций. В сравнении с методом Штайглица-Макбрайда и корреляционным методом, предлагаемый алгоритм соответственно имеет более низкую вычислительную сложность решения и позволяет найти более точные оценки. Особенно преимущество по точности оценок проявляется на плохо обусловленных задачах идентификации.

- 96-Заключение

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

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

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

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

5. Разработан метод поиска коэффициента смещения в задаче ПНК для частично приближенных СЛАУ, не требующий процедуры обращения матриц.

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

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

Список литературы диссертационного исследования кандидат физико-математических наук Шамаров, Павел Александрович, 2000 год

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

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

3. Бронштейн И.Н., Семендяев К.А. Справочник по математике. М.: Наука. 1965. 608 с.

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

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

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

7. Жданов А.И. Решение некорректных стохастических линейных алгебраических уравнений регуляризованным методом максимального правдоподобия. // ЖВМиМФ. 1988. Т. 28. №9. С. 14201425.

8. Жданов А.И. Вычисление регуляризованных оценок наименьших квадратов коэффициентов авторегрессии по неточным данным // АиТ. 1990. №3. С. 110-117.

9. Жданов А.И. О приближенных стохастических системах линейных алгебраических уравнений // ЖВМиМФ, 1989. Т. 29. №12. С. 1776-1787.

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

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

12. Жданов А.И., Кащоба O.A. Особенности применения метода наименьших квадратов для оценивания линейных разностных операторов в задачах идентификации объектов управления! / АиТ. 1979. №8. С. 86-92.

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

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

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

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

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

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

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

20. Савинов Г.В. Определение экстремальных собственных значений минимизацией функционалов специального вида. // ЖВМиМФ. 1985. Т. 25. №2. С. 292-295.

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

22. Шамаров П.А. О численной обусловленности задачи полных наименьших квадратов / / Вестник Самарского филиала Московского государственного университета печати. Выпуск 1. Технология, организация экономика и управление. Москва, 2000. С. 50-54.

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

24. Abatzoglou T.J., Mendel J.M. Constrained total least squares // Proc. IEEE Intemat. Conf. on Acoustic, Speech and Signal Processing. 1987. Dallas. P. 1485-1488.

25. Abatzoglou T.J., Mendel J.M., Harada G.A. The constrained total least squares technique and its application to harmonic surresolution // IEEE Trans. Signal Processing. 1991 SP-39. P. 1070-1087.

26. Ahmed M.S. Estimation of difference equation parameters SfSO systems by correlation analysis j/ Int. J. Control. 1982. Vol 35. No. 4. 677-687.

27. Akaike H. Some problems in the application of the cross-spectral methods // B. Harris (Ed.) Spectral Analysis of Time Series. New York: Wiley, 1967.

28. Ammann L.P., Van Ness J.W. Converting regressions algorithms into corresponding orthogonal regression algorithms // ACM Trans. Math. Software. 1988. No. 14. P. 76-87.

29. Ammann L.P., Van Ness J.W. Standard and robust orthogonal regression // Comm. Statist. B-Simulation Comput. 1989. No. 18. P. 145-162.

30. Aoki M., Yue P.C. On certain convergence questions in system identification // SIAM J. Control. 1970. Vol. 8. No. 2. P. 239-255.

31. Aoki M., Yue P.C. On a priory estimates of some identification methods H \Zih ASME Design and Automat. Conf. 1982. Boston. P. 215-220.

32. Arioli M., Duff I.S., de Rijk P.P.M. On the augment system approach to sparce least-squares problems // Numer. Math. 1989 Vol. 55. P. 667-684.

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

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

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

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

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

38. Bjork A., Heggernes P., Matstoms P. Methods for large scale total- 103least squares problems // Preprint. 1999. 18P.

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

40. Fernando K.V., Nicholson H. Identification of linear systems with input and output noise: Koopmans-Levin method // IEE Proc. D. 1985. Vol. 132. P. 30-36.

41. Fierro R.D., Bunch J.R. Perturbation Theory for Orthogonal Projection Methods with Application to Least Squares and Total Least Squares // Linear Algebra and its Applications. 1996. Vol. 234. P. 71-96.

42. Fierro R.D. Golub G.H., Hansen P.C., O'Leary D.P. Regularization by Truncated Total Least Squares. Report UNIC-93-14. 1993. 20 p.

43. Erkki O., Liuyue W. Robust Fitting by Nonlinear Neural Units // Neural Networks. 1996. Vol. 9. P. 435-444.

44. Givens W. Numerical computations of the characteristic values of a real symmetric matrix. Oak Ridge National Laboratory, ORNL-1574. 1954.

45. Golub G.H., Hansen P.C., O'Leary D.P. Tikhonov regularization and total least squares // SIAM J. Matrix Anal. Appl. 2000. Vol. 21. P. 185-194.

46. Golub G.H., Van Loan C.F. Total least squares// Smoothing Techníques for Curve Estimation. 1979. T. Gasser and M. Rosenblatt eds., Springer-Verlag: New York. P. 69-76.

47. Golub G.H., Van Loan C.F. An analysis of the total least squares problem // SIAM J. Numer. Anal. 1980. No. 17, P. 883-893.

48. Golub G.H., Van Loan C.F. Matrix Computations. Baitimor MD.: John Hopkins Press, 1989.

49. Heij C., Scherrer W. Consistency of system identifícation by global total least squares // Automatica. 1999. Vol. 35. P. 993-1008.

50. Kamm J., Nagy J.G. A total least squares method for Toeplitz systems of equations // BIT. 1998. No. 38. P. 521-534.

51. Koopmans T. Linear Regression Analysis of Economic Time Series. N.V. Haarlem, Netherlands: De Erven F. Bohn, 1937

52. Levin M. Estimation of a System Pulse Transfer Function in the Presence of Noise // IEEE Trans. Automat. Contr. 1964. Vol. AC-9. No. 3. P. 229-235.

53. Madansky A. The fítting of straight lines when both variables are subject to error // J. Amer. Statist. Assoc. 1959. No. 54. P. 173205.

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

55. Moonen M., De Moore B., Vandenberhg L., Vandewalle J. On-line and off-line identifícation of linear state-space models // Internat. J.- 105

56. Control. 1989. Vol. 49. P. 219-232.

57. Musheng W. Algebraic relations between the least squares and total least squares problems with more than one solution // Nurner. Math. 1992. Vol. 62. P. 123-148.

58. Musheng W. Perturbation theory for the Eckart-Young-Mirsky theorem and the constrained total least squares problem // Linear Algebra and its Applications. 1998. Vol. 280. P. 267-287.

59. Navia-Vazques A., Fiqueras-Vidal A.R. Total least squares for block training of neural networks // Neurocomputing. 1999. Vol. 25. P. 213-217.

60. Pearson K. On lines and planes of closest fit to points in space // Phil. Mag. 1901. No. 2. P. 559-572.

61. Peters G., Wilkinson J.H. Inverse iteration, ill-conditioned equations and Newton's method // SIAM Review, 1979. No 3. P. 339-360.

62. Pisarenko V.P. The retrieval of harmonics from a covariance function 11 Geophys. J. Roy. Astron. Soc. 1973. Vol. 33. P. 347-366.

63. Rahman M.A., Yu K.B. Total least squares approach for frequency estimation using linear prediction J/ IEEE Trans. Acoust. Speech Signal Process. 1987. ASSP-35. P. 1440-1454.

64. Spáth H. Orthogonal least squares fitting with linear manifolds // Numer. Math. 1986. Vol. 48. P. 441-445.

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

66. 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.

67. 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.

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

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

70. Szyld D.B. Criteria for combinig inverse and Rayleigh quontient iteration // SIAM J. Numer. Anal. 1988. No. 25. P. 1369-1375.

71. Trefethen L.N., Bau D. Numerical Linear Algebra. SIAM, 1997. -373 p.- 10776. Van Huffel S., Vandewalle J. Algebraic connection between the least squares and total least squares problems j/ Numer. Math. 1989. Vol. 55. P. 431-449.

72. Van Huífel 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.

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

74. Van Huffel S., Vandewalle J. The Total Least Squares Problem: Computational Aspects and Analysis, SIAM 1990. 313 p.

75. Wald A. Asymptotic properties of the maximum-likehood estimate of an unknown parameter of a discrete stochastic process // An. Math. Statist. 1948. No. 19. P. 40-46.

76. Ward R.K. Comparison and diagnostic of errors for six parameter estimation methods // Internat. J. Sys. Sci. 1984. No. 15. P. 745758.

77. Younan N.H., Fan X. Signal restoration via the regularized constrained total least squares // Signal Processing. 1998. Vol. 71. P. 85-93.

78. Ot^&^bYll/1.'. *,íi %ЕИ5ЛЯ0ТСГ.А1. ОП316-00