Матрица Коши (линейная алгебра)

В математике матрица Коши (названа в честь Огюстена Луи Коши) — это матрица размера m × n с элементами вида

[math]\displaystyle{ a_{ij} = \frac{1}{x_i - y_j};\quad x_i - y_j \neq 0,\quad 1 \leqslant i \le m, \quad 1 \leqslant j \le n, }[/math]

где [math]\displaystyle{ x_i }[/math] и [math]\displaystyle{ y_j }[/math] являются элементами поля [math]\displaystyle{ \mathcal{F} }[/math], а последовательности [math]\displaystyle{ (x_i) }[/math] и [math]\displaystyle{ (y_j) }[/math] таких элементов являются инъективными (не содержат повторяющихся элементов).

Матрица Гильберта является частным случаем матрицы Коши при

[math]\displaystyle{ x_i-y_j = i + j - 1. }[/math]

Каждая подматрица (матрица, получающаяся вычёркиванием определённой строки и столбца) матрицы Коши также является матрицей Коши.

Определители Коши

Определитель квадратной матрицы Коши является заведомо рациональной функцией параметров [math]\displaystyle{ (x_i) }[/math] и [math]\displaystyle{ (y_j) }[/math]. Если эти последовательности не инъективны, то определитель равен нулю. Если некоторые [math]\displaystyle{ x_i }[/math] стремятся к [math]\displaystyle{ y_j }[/math] , то определитель стремится к бесконечности. Таким образом, часть множества нулей и полюсов определителя Коши заранее известна. На самом деле других нулей и полюсов нет.

Явный вид определителя квадратной матрицы Коши A, называемый просто определитель Коши:

[math]\displaystyle{ \det \mathbf{A}={{\prod_{i=2}^n \prod_{j=1}^{i-1} (x_i-x_j)(y_j-y_i)}\over {\prod_{i=1}^n \prod_{j=1}^n (x_i-y_j)}} }[/math] (Schechter 1959, eqn 4).

Он всегда не равен нулю, таким образом, матрицы Коши являются обратимыми. Обратная матрица A⁻¹ = B = [b_ij] имеет вид:

[math]\displaystyle{ b_{ij} = (x_j - y_i) A_j(y_i) B_i(x_j) }[/math] (Schechter 1959, Theorem 1)

где A_i(x) и B_i(x) — многочлены Лагранжа для последовательностей [math]\displaystyle{ (x_i) }[/math] и [math]\displaystyle{ (y_j) }[/math], соответственно. То есть

[math]\displaystyle{ A_i(x) = \frac{A(x)}{A^\prime(x_i)(x-x_i)} }[/math] и [math]\displaystyle{ \quad B_i(x) = \frac{B(x)}{B^\prime(y_i)(x-y_i)}, }[/math]

где

[math]\displaystyle{ A(x) = \prod_{i=1}^n (x-x_i) }[/math] и [math]\displaystyle{ \quad B(x) = \prod_{i=1}^n (x-y_i). }[/math]

Обобщение

Матрица C называется матрицей типа Коши, если она имеет вид

[math]\displaystyle{ C_{ij}=\frac{r_i s_j}{x_i-y_j}. }[/math]

Обозначив X=diag(x_i), Y=diag(y_i), получим, что матрицы типа Коши (в частности, просто матрицы Коши) удовлетворяют смещённому уравнению:

[math]\displaystyle{ \mathbf{XC}-\mathbf{CY}=rs^\mathrm{T} }[/math]

(в случае матриц Коши [math]\displaystyle{ r=s=(1,1,\ldots,1) }[/math]). Следовательно, матрицы типа Коши имеют общую смещённую структуру, что может быть использовано при работе с такими матрицами. Например, известны алгоритмы для

приближённого умножения матрицы Коши на вектор за [math]\displaystyle{ O(n \log n) }[/math] операций,
LU-разложение за [math]\displaystyle{ O(n^2) }[/math] операций (алгоритм GKO), и соответствующий алгоритм решения систем линейных уравнений с такими матрицами,
неустойчивые алгоритмы для решения систем линейных уравнений за [math]\displaystyle{ O(n \log^2 n) }[/math] операций.

Через [math]\displaystyle{ n }[/math] обозначен размер матрицы (обычно имеют дело с квадратными матрицами, хотя все вышеприведённые алгоритмы легко могут быть обобщены на прямоугольные матрицы).

См. также

Матрица Тёплица

Ссылки

A. Gerasoulis. A fast algorithm for the multiplication of generalized Hilbert matrices with vectors (англ.) // Mathematics of Computation (англ.) (рус. : journal. — 1988. — Vol. 50, no. 181. — P. 179—188.
I. Gohberg, T. Kailath, V. Olshevsky. Fast Gaussian elimination with partial pivoting for matrices with displacement structure (англ.) // Mathematics of Computation (англ.) (рус. : journal. — 1995. — Vol. 64, no. 212. — P. 1557—1576.
P. G. Martinsson, M. Tygert, V. Rokhlin. An [math]\displaystyle{ O(N \log^2 N) }[/math] algorithm for the inversion of general Toeplitz matrices (англ.) // Computers and Mathematics with Applications : journal. — 2005. — Vol. 50. — P. 741—752.
S. Schechter. On the inversion of certain matrices (англ.) // Mathematical Tables and Other Aids to Computation (англ.) (рус. : journal. — 1959. — Vol. 13, no. 66. — P. 73—77.