Некоторые вычислительные алгоритмы для Теплицевых матриц

Физико-математический факультет, 4 курс, направление «Прикладная математика»

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

Отто Теплиц (1 августа 1881 - 15 февраля 1940) - немецкий математик, работающий в области функционального анализа, сумел вывести определенный вид матриц, который, в последствии, был назван в честь самого учёного – Теплицева матрица или диагонально-постоянная.

Матрица Теплица – это матрица, в которой на всех диагоналях, параллельных главной, стоят равные элементы; элементы теплицевой матрицы зависят только от разности строчного и столбцового индексов (): . Такие матрицы возникают в вычислительных задачах прикладной электродинамики, акустики, обработки изображений.

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

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

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

Задача эффективного вычисления собственных значений Теплицевых матриц является одной из основных задач линейной алгебры. Для них, безусловно, были сформулированы следующие алгоритмы: алгоритм Уильяма Тренча - эффективный метод вычисления собственных значений симметрической теплицевой матрицы, учитывающий особенности структуры матриц, и допускающий эффективную параллельную реализацию.

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

Список литературы

1. Гагарин Ю.И. Математические модели и алгоритмы быстрых ортогональных преобразований: учеб. пособие / Ю. И. Гагарин; М-во общ. и проф. образования Рос. Федерации. С.-Петерб. гос. техн. ун-т. - СПб.: Изд-во СПбГТУ, 1999. - 99 С.

2. Тыртышников, Е.Е. Теплицевы матрицы, некоторые их аналоги и приложения / ответственный редактор чл.-корр. СССР В.В. Воеводин. - М.: ВИНИТИ, 1989. - 184 С.

3. Пустыльников, Л.Д. Тёплицевы и ганкелевы матрицы и их применения // Успехи математических наук. - 1984. - Т. 39, № 4(238). - С. 53 - 84.

УДК 373.5

И. А. Качалина

(научный руководитель: Е. И. Чернышева, зав. кафедрой технологических

и естественнонаучных дисциплин кандидат педагогических наук, доцент)