WikiSort.ru - Не сортированное

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

${\displaystyle a_{ij}={\frac {1}{x_{i}-y_{j}}};\quad x_{i}-y_{j}\neq 0,\quad 1\leqslant i\leq m,\quad 1\leqslant j\leq n,}$

где ${\displaystyle x_{i}}$ и ${\displaystyle y_{j}}$ являются элементами поля ${\displaystyle {\mathcal {F}}}$ , а последовательности ${\displaystyle (x_{i})}$ и ${\displaystyle (y_{j})}$ таких элементов являются инъективными (не содержат повторяющихся элементов).

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

${\displaystyle x_{i}-y_{j}=i+j-1.}$

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

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

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

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

${\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})}}}$     (Schechter 1959, eqn 4).

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

${\displaystyle b_{ij}=(x_{j}-y_{i})A_{j}(y_{i})B_{i}(x_{j})}$     (Schechter 1959, Theorem 1)

где A_i(x) и B_i(x) — многочлены Лагранжа для последовательностей ${\displaystyle (x_{i})}$ и ${\displaystyle (y_{j})}$ , соответственно. То есть

${\displaystyle A_{i}(x)={\frac {A(x)}{A^{\prime }(x_{i})(x-x_{i})}}}$ и ${\displaystyle \quad B_{i}(x)={\frac {B(x)}{B^{\prime }(y_{i})(x-y_{i})}},}$

где

${\displaystyle A(x)=\prod _{i=1}^{n}(x-x_{i})}$ и ${\displaystyle \quad B(x)=\prod _{i=1}^{n}(x-y_{i}).}$

Обобщение

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

${\displaystyle C_{ij}={\frac {r_{i}s_{j}}{x_{i}-y_{j}}}.}$

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

${\displaystyle \mathbf {XC} -\mathbf {CY} =rs^{\mathrm {T} }}$

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

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

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

См. также

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

Ссылки

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