Матрица Коши: определитель, интерполяция и гильбертовы пространства

Конструкция и формула определителя Коши

Матрица Коши C формируется из двух непересекающихся наборов чисел (x_1...x_n и y_1...y_n). Каждый элемент матрицы, стоящий в i-й строке и j-м столбце, вычисляется по формуле 1 / (x_i - y_j). В отличие от большинства числовых таблиц, вычисление определителя матрицы Коши не требует кубического времени метода Гаусса. Коши вывел потрясающую аналитическую формулу: определитель матрицы равен произведению всех попарных разностей элементов внутри множества x (x_i - x_k), умноженному на произведение всех попарных разностей элементов внутри множества y (y_i - y_k), и все это делится на произведение абсолютно всех возможных комбинаций разностей между элементами двух множеств (x_i - y_j). Из этой формулы мгновенно следует, что если все элементы множества x уникальны, и все элементы y уникальны, матрица Коши гарантированно невырождена.

Матрица Гильберта: патологическая обусловленность

Самым знаменитым и коварным частным случаем матрицы Коши является Матрица Гильберта. Она возникает, если задать узлы как x_i = i и y_j = -j + 1. В этом случае элементы матрицы приобретают вид дробей единичной последовательности: 1/(i+j-1). Матрица Гильберта симметрична и положительно определена, так как она представляет собой матрицу Грама для мономов (1, x, x^2...) при интегрировании на отрезке от 0 до 1. Однако она печально известна как абсолютный эталон плохой обусловленности в линейной алгебре. Число обусловленности матрицы Гильберта растет с пугающей скоростью O(e^(3.5*n)). Даже для крошечной матрицы размера 15x15 стандартная компьютерная арифметика с плавающей запятой полностью разрушается: решение системы уравнений с такой матрицей методом Гаусса выдает 100% информационный мусор (числа, не имеющие отношения к реальности).

Аппроксимация Паде и системная идентификация

Несмотря на вычислительные риски, матрицы Коши лежат в основе аппроксимации Паде — метода наилучшего приближения сложных функций (например, экспонент или логарифмов) в виде отношения двух полиномов. Разложение Паде часто сходится гораздо быстрее и точнее, чем классические ряды Тейлора (особенно за пределами радиуса сходимости). Нахождение коэффициентов числителя и знаменателя в разложении Паде сводится к решению системы линейных уравнений, ядром которой выступает блочная структура матриц Коши (и Тёплица). В теории автоматического управления этот же алгебраический аппарат применяется для аппроксимации бесконечномерных систем (например, линий задержки сигнала) конечномерными фильтрами (IIR-фильтрами).

Быстрые алгоритмы для матриц типа Коши (Cauchy-like)

Поскольку классические алгоритмы (LU-разложение) разрушаются или работают слишком долго на матрицах типа Коши, математики разработали специализированные итерационные методы, опирающиеся на понятие ранга смещения (displacement rank). Оказывается, если вычесть из матрицы Коши ее версию, умноженную на специальные диагональные матрицы слева и справа, ранг полученной матрицы мгновенно падает до невероятно малых значений (например, до 1 или 2). Это алгебраическое свойство позволяет сжимать матрицы Коши и разрабатывать сверхбыстрые алгоритмы, которые инвертируют такие матрицы или решают системы уравнений всего за O(n^2) или даже O(n log^2 n) операций. Эти «быстрые решатели» (Fast solvers) жизненно необходимы для численного интегрирования сингулярных уравнений в теории упругости и аэродинамике.