Трехдиагональные матрицы и ортогональные многочлены

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

Алгоритм Томаса (Метод Прогонки)

Решение системы линейных уравнений с трехдиагональной матрицей является эталоном вычислительной эффективности. Для классической плотной матрицы метод Гаусса требует времени, пропорционального кубу размерности (O(n^3)). Однако благодаря узкой ленточной структуре, прямой ход метода Гаусса для трехдиагональной матрицы сводится к одной единственной цепочке исключений: нам нужно обнулить только одну нижнюю диагональ, двигаясь сверху вниз. Обратный ход также выполняется за один проход снизу вверх. Этот специализированный вариант метода Гаусса называется Алгоритмом Томаса (в русскоязычной литературе — Метод Прогонки). Его вычислительная сложность составляет всего O(n) операций. Система из миллиона уравнений решается на обычном ноутбуке за тысячные доли секунды.

Трехчленные рекуррентные соотношения

Если мы начнем вычислять определитель трехдиагональной матрицы (главные миноры) с помощью разложения по последней строке, мы получим рекуррентное соотношение. Определитель матрицы порядка k зависит только от определителей матриц порядка k-1 и k-2. Эта алгебраическая конструкция является точным отражением трехчленного рекуррентного соотношения, которому подчиняются все классические системы ортогональных многочленов (такие как многочлены Чебышёва, Лежандра, Эрмита и Лагерра). В спектральной теории доказывается фундаментальный факт: характеристический многочлен любой симметричной трехдиагональной матрицы формирует систему ортогональных полиномов. И наоборот, для любой системы ортогональных полиномов можно построить уникальную бесконечную трехдиагональную матрицу (матрицу Якоби).

Перемежаемость корней и последовательность Штурма

Если мы рассмотрим последовательность характеристических многочленов для всех угловых миноров симметричной трехдиагональной матрицы, мы обнаружим потрясающее свойство: корни этих многочленов (собственные значения подматриц) строго чередуются. Между любыми двумя корнями минора порядка k обязательно находится ровно один корень минора порядка k-1. Это свойство называется перемежаемостью Коши (Cauchy interlacing theorem). Благодаря перемежаемости, знаки определителей этих миноров при подстановке конкретного числа lambda образуют так называемую последовательность Штурма. Подсчитывая количество смен знака в этой последовательности, алгоритм бисекции может без труда локализовать (зажать в вилку) и с гигантской точностью вычислить абсолютно любое собственное значение симметричной трехдиагональной матрицы.

Алгоритм QR и связь с цепными дробями

Трехдиагональные матрицы являются промежуточной и самой желанной станцией в задаче поиска собственных значений. Перед применением итерационного QR-алгоритма любую симметричную матрицу сначала приводят (с помощью отражений Хаусхолдера) к трехдиагональному виду. Это делается один раз, а затем все QR-итерации выполняются исключительно над этой узкой трехдиагональной формой, что сокращает время поиска спектра в сотни раз. Более того, алгебра трехдиагональных матриц имеет глубокие исторические связи с теорией непрерывных (цепных) дробей. Нахождение элементов обратной матрицы к трехдиагональной сводится к вычислению подходящих дробей, что делает этот раздел математики мостом между непрерывной линейной алгеброй и дискретной теорией чисел.

Оценить