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

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

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

0.1 Введение.

1 Методы вычисления коэффициентов разложения

1.1 Предварительные сведения.

1.2 Введение в обобщенные ряды Фурье

1.3 Дискретное представление базисных функций.

1.4 Алгоритм вычисления ортогональных функций высокого порядка

1.5 Аналитические методы.

1.5.1 Метод подстановки.

1.5.2 Использование уравнения ломаной.

1.5.3 Преобразование степенного ряда в ортогональный.

2 Способы реализации и свойства оператора умножения на функцию

2.1 Пространство коэффициентов разложения.

2.2 Пространство функций дискретного аргумента.

2.3 Формулы для многочленов Чебышёва.

2.4 Базис из собственных функций оператора умножения.

3 Некоторые задачи обработки данных

3.1 Получение, преобразование и измерение одномерных сигналов для задач распознавания образов и анализа изображений.

3.1.1 Декартовы координаты.

3.1.2 Естественное уравнение кривой.

3.1.3 Интегрирование и дифференцирование.

3.1.4 Нерегулярные кривые.

3.1.5 Вычисление моментов.

3.1.6 Инвариантные признаки.

3.1.7 Метод пристрелки и движение по кривой

3.2 Диагностика и идентификация параметров динамических систем

3.2.1 Функции чувствительности и уравнения диагностики

3.2.2 Аппроксимация функции веса ядерного магнитного резонанса

Спектрально-аналитическое исследование нелинейного уравнения Шредингера

4.1 Математическая модель.

4.2 Конечномерное приближение.

Некоторые процедуры для работы с ортогональными рядами

А.1 Процедуры для полиномов Чебышёва первого рода.

А.2 Процедуры для функций Сонина-Лагерра.

Выводы

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

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

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

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

Сузить класс задач можно, если рассмотреть разные типы функций и соответственно разные базисы для аппроксимации этих функций. Одним из типов нестационарных сигналов являются так называемые функции веса, или импульсные переходные характеристики [1]. Функция веса является реакцией изучаемой управляющей системы на импульсное входное воздействие. Функции веса представляют собой затухающие сигналы, которые аппроксимируются наиболее короткими отрезками рядов в базисе функций Лагерра. Преобразование Лапласа от функции веса, называемое передаточной функцией системы, является универсальным способом описания линейных систем. Другим выделенным базисом в информатике является базис из функций Эрмита, которые являются собственными функциями преобразования Фурье. Разложение по функциям Эрмита предоставляет возможность аппроксимации интегрального преобразования Фурье, альтернативной по отношению к той аппроксимации, которую дает дискретное преобразование Фурье. Функциям Лагерра и Эрмита придавал большое значение Ноберт Винер, предложивший идею создания на их основе аналитической теории нелинейных систем [2, 3].

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

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

Реализация алгебраических операций над функциями, представленными отрезками ортогональных рядов, является достаточно трудоемким и малоизученным предметом. Умножение отрезков рядов не обладает свойством ассоциативности. В этом смысле имеется аналогия алгебры отрезков рядов с алгеброй чисел с плавающей запятой в машинном представлении действительных чисел. Использование машинной арифметики с сокращением знаков приводит фактически к развитию целой области математики - численного анализа. Все конечные вычислительные схемы, которые могут быть предложены на основе аппроксимации абстрактных математических понятий, требуют проверки на устойчивость. Таким образом, можно констатировать, что вычислительная математика, или практический анализ по терминологии Корнелия Ланцоша [5], изучает процессы конечномерного аппроксимирования, приводящие к рациональному решению задач, устойчивому к возмущениям в исходных данных и к ошибкам вычислений.

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

Основными задачами, которые были поставлены в процессе исследования, являются следующие задачи

1. Реализация и исследование алгебраических операций в пространстве коэффициентов разложения ортогональных рядов.

2. Исследование возможности и точности аппроксимации сложных экспериментальных данных в дискретной форме на основе классических ортогональных базисов.

3. Построение алгоритмов диагностики параметров систем по их функциям веса.

4. Решение дифференциальных и интегральных уравнений на основе ортогональных разложений.

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

Заключение диссертации по теме «Дискретная математика и математическая кибернетика», Панкратов, Антон Николаевич

Основные результаты работы состоят в следующем:

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

2. Показано, что задачи нахождения отношения рядов, извлечения квадратного корня из ряда сводятся к соответствующим операциям над матрицами.

3. Разработан эффективный метод вычисления функций Лагерра и Эрмита без ограничения на порядок полинома.

4. Реализованы квадратурные формулы Гаусса высокого порядка в целях вычисления коэффициентов разложения функций дискретного аргумента в базисах Лагерра, Эрмита и Чебышёва.

5. Найдены и классифицированы решения нелинейного уравнения Шредин-гера.

6. Предложены алгоритмы диагностики динамических систем по их весовым функциям.

Автор благодарен своим научным руководителям Ф.Ф.Дедусу и В.Д.Лахно, под руководством которых была выполнена работа. Также автор признателен своему научному руководителю магистерской диссертации А.М.Молчанову и также своим соавторам и коллегам Э.Э.Шнолю, Н.К.Балабаеву, М.Н.Устинину, С.А.Махортых, Н.К.Быстровой и А.К.Бритенкову. Данная работа выполнялась в Институте математических проблем биологии Российской академии наук при финансовой поддержке ряда проектов РФФИ Ж№ 94-01-00226, 97-01-00526, 9802-16833, 00-01-00417, 01-07-90317, 01-02-16127, 04-01-00756 и одного международного проекта Американского фонда гражданских исследований и развития (С1ШГ) 11В1-2027.

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

1. Поляк Б.Т., Щербаков П.С. Робастная устойчивость и управление. - М.: Наука, 2002

2. Wiener N. Hermitian polynomials and Fourier analysis// J.Math.Phys., v.8, 1929, p.70-73

3. Мишкин Э. Аналитическая теория нелинейных систем. //Приспосабливающиеся автоматические системы/ Под ред. Мишкина. Э. и Брауна Л. М.: Издательство иностранной литературы, 1963

4. Курант Р., Гильберт Д. Методы математической физики. М.-Л.:Гостехтеоретиздат, 1951

5. Ланцош К. Практические методы прикладного анализа. М.:Физматгиз, 1961

6. Виденский В. Сергей Натанович Бернштейн// Квант, 1997, №1, с.17-21

7. Тихомиров В. Две теоремы Бернштейна// Квант, 1997, №1, с.21-23

8. Дедус Ф.Ф., Махортых С.А., Устинин М.Н., Дедус А.Ф. Обобщенный спектрально-аналитический метод обработки информационных массивов. Задачи анализа изображений и распознавания образов. М.: Машиностроение, 1999.

9. Суетин П.К. Классические ортогональные многочлены. М.:Наука, 1979

10. Никифоров А.Ф., Уваров В.Б. Специальные функции математической физики. М.:Наука, 1984

11. Волощенко A.M., Журавлев В.И. Вычисление весов и узлов квадратурных формул Гаусса с весовыми функциями классических ортогональных полиномов непрерывного и дискретного переменного// Препринт №89 М.: ИПМ АН СССР, 1977

12. Press W.H., Teukolsky S.A., Vetterling W.T., Flannery B.P. Numerical Recipes in С. The Art of Scientific Computing. Cambridge University Press, 1992

13. Shen J. Stable and Efficient Spectral Methods in Unbounded Domains Using Laguerre Functions// SIAM Journal on Numerical Analysis, v.38, 2000, JV® 4, p.1113-1133.

14. Funaro D. FORTRAN Routines for Spectral Methods Instituto di analisi numerica, Pavia, 1993

15. Grafov B.M., Grafova I.B. Theory of the wavelet analysis for electrochemical noise by use of Laguerre functions// Electrochemistry Communications, v.2, 2000, p.386-389

16. Графов Б.М. Использование преобразования Лапласа для описания шумовых сигналов электрохимических датчиков// Электрохимия, т.29, 1993, №12, с.1474-1475

17. Бахвалов Н.С. Об устойчивом вычислении значений многочленов// Журнал вычислительной математики и математической физики, т.11,1971, №6, с. 1568-1574

18. Oliver J. Rounding error propagation in polynomial evaluation schemes// Journal of Computational and Applied Mathematics, v.5, 1979, №2, p.85-97.

19. Barrio R., Berges J.С. Perturbation simulations of rounding errors in the evaluation of Chebyshev series// Journal of Universal Computer Science, v.4, 1998, №6, p.561-573.

20. Бейтмэн Г., Эрдейи А. Таблицы интегральных преобразований, т.1. Преобразования Фурье, Лапласа, Меллина. М.: Наука, 1969

21. Weeks W.T. Numerical Inversion of Laplace Transforms Using Laguerre Functions// Journal of the Association for Computing Machinery, v.13, 1966, №, p.419-426

22. Weideman J.A.C. Algorithms for Parameter Selection in the Weeks Method for Inverting the Laplace Transform// SIAM Journal for Scientific Computing, v.21, 1999, m, p.111-128

23. Хэмминг P.B. Численные методы. M.: Наука, 1972

24. Délie G., Malherbe S.M. Subroutines For Convolution Sums Of Chebyshev And Fourier Series// Computer Physics Communications, v.48, 1988, p.305-312

25. D'Aguanno В., Nobile A., Roman E. CHPACK: A package for the manipulation of Chebyshev approximations// Computer Physics Communications, v.29, 1983, p.361-374

26. Fox L., Parker I.B. Chebyshev Polynomials in Numerical Analysis. Oxford University Press, 1968

27. Гохберг И.Ц., Фельдман И.А. Уравнения в свертках и проекционные методы их решения. М.: Наука, 1971

28. Chen H. The Quadrature Discretization Method and Its Applications// Thesis, The University of British Columbia, 1998

29. Broucke R. Construction of Rational and Negative Powers of a Formal Series// Communications of the ACM, v.14, 1971, JV®1, p.32

30. Broucke R. A446 Ten Subroutines for the Manipulation of Chebyshev Series// Communications of the ACM, v.16, 1973, JV«4, p.254

31. Bultheel A., Martinez-Sulbaran H. Recent developments in the theory of fractional transform// K.U.Leuven, Department of Computer Science, ReportTW376, 2003

32. Бахвалов H.С., Жидков H.П., Кобельков Г.М. Численные методы. -М.:Наука, 1987

33. Higham N.J. Computing real square roots of a real matrix// Linear Algebra and Appl., 88/89, 1987, p.405-430

34. Bjorck A., Hammarling S. A Schur method for the square root of a matrix// Linear Algebra and Appl., 52/53, 1983, p.127-140

35. Ильин B.A., Позняк Э.Г. Линейная алгебра. М.: Наука, 1984

36. Дуда Р., Харт П. Распознавание образов и анализ сцен. М.: Мир, 1976.

37. Сонин Н.Я. Об определении максимальных и минимальных свойств плоских кривых// Варшавские университетские известия, 1886, №1-2, с.1-68

38. Pratt Ian Shape Representation Using Fourier Coefficients of the Sinusoidal Transform// Journal of Mathematical Imaging and Vision, v.10, 1999, p.221-235.

39. Коганов А.В. Метод контурных моделей в распознавании визуальных образов// Вопросы кибернетики. Распознавание видеографической информации. Вып. под ред. В.Б.Бетелина. М., 1999, с.75-91

40. Montiel М.Е., Aguado A.S., Zaluska E.J. Fourier Series Expansion of Irregular Curves// Fractals, v.5, 1997, №1, p.105-119.

41. Aguado A.S., Montiel M.E., Nixon M.S. Parameterising Arbitrary Shapes via Fourier Descriptors for Evidence-Gathering Extraction// CVIU: Computer Vision and Image Understanding, v.69, 1998, №2, p.202-221.

42. Фокс А., Пратт M. Вычислительная геометрия. Применение в проектировании и на производстве. М., Мир, 1982

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

44. Федер Е. Фракталы. М.: Мир, 1991

45. Hunt B.R. The Hausdorff Dimension of Graphs of Weierstrass Functions// Proc. Amer. Math. Soc., v.126, 1998, p.791-800.

46. Рисс Ф., Сёкефальви-Надь Б. Лекции по функциональному анализу. М.: Мир, 1979

47. Yang L., Albregtsen F. Fast and Exact Computation of Cartesian Geometric Moments Using Discrete Green's Theorem// Pattern Recognition, v.29, 1996, №, p. 1061-1073

48. Flusser J., Suk T. Pattern Recognition by Affine Moment Invariants// Pattern Recognition, v.26, 1993, Л»1, p.167-174

49. Clenshaw C.W., Norton H.J. The solution of nonlinear ordinary differential equations in Chebyshev series// The Computer Journal, v.6, 1963, №1, p.88-92

50. Belikov M.V. Methods of numerical integration with uniform and mean square approximation for solving problems of ephemeris astronomy and satellite geodesy// Manuscripta Geodaetica, v.18, 1993, p.182-200

51. Nex C.M.M. The Use of Chebyshev Series In Computational Physics// Computer Physics Communications, v.20, 1980, p. 1-5

52. Абрамов A.A., Балла К., Конюхова Н.Б. Перенос граничных условий из особых точек для систем обыкновенных дифференциальных уравнений// Сообщения по вычислительной математике М.: ВЦ АН СССР, 1981

53. Быховский М.Л. Основы динамической точности электрических и механических цепей. М.: АН СССР, 1958

54. Быховский М.Л. Чувствительность и динамическая точность систем управления. М.: Изв. АН СССР. Техническая кибернетика, 1964, №6

55. Кузьмин И.В. Проектирование телемеханических систем контроля и управления. Харьков: ХВКИУ, 1964.

56. Кузьмин И.В. Оценка эффективности автоматических систем контроля и управления. Харьков: ХВКИУ, 1964.

57. Воронов А.А. Основы теории автоматического управления. 4.2. -Л.: "Энергия", 1966

58. Кокотович П.В., Рутман P.C. Чувствительность систем автоматического управления. Обзор// Автоматика и телемеханика, т.26, 1965, JV}4

59. Дедус Ф.Ф., Воронцов В.Б. Диагностика непрерывных систем с использованием ортогональных фильтров// Труды I Всесоюзного совещания по технической диагностике. М.: Наука, 1972, с.103-108

60. Дероум Э. Современные методы ЯМР для химических исследований. М.: Мир, 1990

61. Khabibrakhmanov I.K., Summers D. The Use of Generalized Laguerre Polynomials in Spectral Methods for Nonlinear Differential Equations// Computers Math. Applic., v.36, 1998, №2, p.65-70

62. Треногин B.A. Функциональный анализ. M.: Наука, 1993

63. Пекар С.И. Исследования по электронной теории кристаллов. М.-Л.:Гостехтеоретиздат, 1951

64. Ландау Л.Д., Лифшиц Е.М. Квантовая механика (нерелятивистская теория). М.: Наука, 1989

65. Фейнмановские лекции по физике. Задачи и упражнения с ответами и решениями. М.: Мир, 1969

66. Балабаев Н.К., Луневская Л.В. Движение по кривой в n-мерном пространстве. Алгоритмы и программы на ФОРТРАНе Пущино: ОНТИ НЦБИ АН СССР, 1978

67. Балабаев Н.К., Лахно В.Д. Делокализованные состояния избыточных электронов в кластерах// Журнал физической химии, т.69, 1995, №8, с.1358-1362

68. Балабаев Н.К., Лахно В.Д. Солитонные решения в теории полярона// Теоретическая и математическая физика, т.45, 1980, №1, с.139

69. Лахно В.Д., Балабаев Н.К. Самосогласованные решения в континуальной модели F-центра и проблема релаксированного возбужденного состояния// Оптика и спектроскопия, т.55, 1983, вып.2, с.308

70. ТО. Rosenblit М., Jortner. J Excess electron surface states on helium clusters// J. Chem. Phys., v. 101, 1994, №11, p.9982-9996

71. Hertel I.V., Huglin C., Nitsch C., Schulz C.P. Photoionization of Na(NH3)n and Na(H20)n Clusters: A Step Towards the Liquid Phase?// Physical Review Letters v.67, 1991, p.1767

72. Опубликованные работы по теме диссертации

73. Балабаев Н.К., Лахно В.Д., Панкратов А.Н., Устинин М.Н. Поляронные состояния в незаряженных молекулярных кластерах// Материалы Всероссийского совещания "Физика кластеров"(Пущино, 1996)/ Ред. Лахно В.Д., Чуев Г.Н. Пущино: ОНТИ ПНЦ РАН, 1997

74. Балабаев Н.К., Лахно В.Д., Панкратов А.Н., Устинин М.Н. Поляронные состояния в незаряженных молекулярных кластерах// Изв.РАН, сер.физ., т.61, 1997, с.1831

75. Дедус Ф.Ф., Панкратов А.Н., Дедус Ф.Ф. (младший) Диагностика сложных динамических объектов на основе обобщенного спектрально-аналитического метода// Контроль.Диагностика, №12(18), 1999, с.7-12

76. Лахно В.Д., Панкратов А.Н. Связанные состояния электрона полярной диэлектрической сферой// Изв.РАН, сер.физ., т.64, 2000, №8, с.1465-1468

77. Панкратов А.Н. Состояния электрона, связанного полярной диэлектрической сферой// Школа-конференция "Горизонты физико-химической биологии" (Пущино, 28 мая 2 июня 2000г.) Том 1. Тезисы стендовых сообщений. - Пущино: ОНТИ ПНЦ РАН, 2000, т.1, 11.29, с.47

78. Махортых С.А., Панкратов А.Н. О спектральном разложении нерегулярных кривых// Доклады I Всероссийской конференции "Спектральные методы обработки информации в научных исследованиях"("Спектр-2000", Пущино, 24-28 октября 2000г.) Москва, 2000, с.44

79. Смирнов Д.В., Коростелев А.И., Панкратов А.Н., Коробков A.A. База данных характеристик летательных аппаратов// Научно-технический сборник института Серпухов: СВИ РВ, 2001

80. Смирнов Д.В., Коростелев А.И., Панкратов А.Н., Коробков A.A. Методика формирования баз данных характеристик летательных аппаратов// Материалы XX Межвузовской НТК Серпухов: СВИ РВ, 2001, часть 5

81. Панкратов А.Н., Дедус Ф.Ф. Аппроксимация оригинала и изображения в интегральном преобразовании Лапласа// 5-я Пущинская конференция молодых ученых, (Пущино, 16-20 апреля 2001г.) Тула: ЗАО "Гриф и К",2001, с.334

82. Панкратов А.Н., Дедус Ф.Ф. Идентификация математических моделей спектрально-аналитическим методом// Доклады X Всероссийской конференции "Математические методы распознавания образов", Москва, 2001, с. 107

83. Pankratov A.N., Dedus F.F. Adaptive Approximation of Arbitrary Signals// 5th International congress of mathematical modelling (Sep 30 Oct 6, 2002, Dubna Moscow Region), Book of abstracts, M.:"JANUS-K", 2002, v.2, p.72

84. Панкратов A.H. Обработка и моделирование нерегулярных сигналов с использованием ортогональных базисов// Биология наука XXI века: 7-ая Пущинская школа-конференция молодых ученых (Пущино, 14-18 апреля 2003 г.): Сборник тезисов - Серпухов, 2003, с. 254

85. Панкратов А.Н. Исследование и классификация функций посредством глубокого разложения в ортогональные ряды// Доклады XI Всероссийской конференции "Математические методы распознавания образов", М.: ООО "Регион-Холдинг", 2003, с. 159

86. Махортых С.А., Дергузов A.B., Куликова Л.И., Панкратов А.Н. Спектральный анализ, классификация и диагностика цифровых массивов/ SpectMate. Свидетельство РОСПАТЕНТ об официальной регистрации программы для ЭВМ №2004610405 от 10.02.2004

87. Панкратов А.Н. О реализации алгебраических операций над рядами ортогональных функций. Препринт Пущино: ОНТИ ПНЦ РАН, 2004