Cauchy matris (linjär algebra)

Inom matematik är Cauchy-matrisen  (  uppkallad efter Augustin Louis Cauchy ) en m × n -matris med poster av formen

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,

där och är element i fältet , och sekvenser av och sådana element är injektiva (innehåller inte upprepade element). $x_{i}$ $y_{j}$ ${\mathcal {F}}$ $(x_{i})$ $(y_{j})$

Hilbert-matrisen är ett specialfall av Cauchy-matrisen för

x_{i}-y_{j}=i+j-1.

Varje submatris (en matris som erhålls genom att ta bort en viss rad och kolumn) i Cauchy-matrisen är också en Cauchy-matris.

Cauchy determinanter

Determinanten för den kvadratiska Cauchy-matrisen är en medvetet rationell funktion av parametrarna och . Om dessa sekvenser inte är injektiva är determinanten noll. Om vissa tenderar att , tenderar determinanten till oändlighet. Således är en del av uppsättningen av nollor och poler för Cauchy-determinanten känd i förväg. Det finns faktiskt inga andra nollor och poler. $(x_{i})$ $(y_{j})$ $x_{i}$ $y_{j}$

En explicit form av determinanten för den kvadratiska Cauchy-matrisen A , helt enkelt kallad Cauchy-determinanten :

\det \mathbf {A} ={{\prod _{i=2}^{n}\prod _{j=1}^{i-1}(x_{i}-x_{j}) (y_{j}-y_{i})} \över {\prod _{i=1}^{n}\prod _{j=1}^{n}(x_{i}-y_{j}) }}

(Schechter 1959, ekv. 4).

Den är alltid icke-noll, så Cauchy-matriserna är inverterbara . Den inversa matrisen A −1 = B = [b ij ] har formen:

b_{ij}=(x_{j}-y_{i})A_{j}(y_{i})B_{i}(x_{j})

(Schechter 1959, sats 1)

där A i (x) och Bi ( x ) är Lagrangepolynomen för sekvenserna respektive . Det är $(x_{i})$ $(y_{j})$

A_{i}(x)={\frac {A(x)}{A^{\prime }(x_{i})(x-x_{i)))))

och

\quad B_{i}(x)={\frac {B(x)}{B^{\prime }(y_{i})(x-y_{i))))),

var

A(x)=\prod _{i=1}^{n}(x-x_{i})

och

\quad B(x)=\prod _{i=1}^{n}(x-y_{i}).

Generalisering

En matris C kallas en matris av Cauchy-typ om den har formen

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

Genom att beteckna X =diag(xi ) , Y =diag(y i ), får vi att matriser av Cauchy-typ (i synnerhet bara Cauchy-matriser) uppfyller den skiftade ekvationen :

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

(när det gäller Cauchy-matriser ). Därför har matriser av Cauchy-typ en gemensam partisk struktur , som kan användas när man arbetar med sådana matriser. Det finns till exempel kända algoritmer för $r=s=(1,1,\ldots ,1)$

ungefärlig multiplikation av Cauchy-matrisen med en vektor i operationer, $O(n\log n)$
LU-sönderdelning i operationer (GKO-algoritm) och motsvarande algoritm för att lösa system av linjära ekvationer med sådana matriser, $O(n^{2})$
instabila algoritmer för att lösa system av linjära ekvationer i operationer. $O(n\log ^{2}n)$

V anger storleken på matrisen (vanligtvis handlar det om kvadratiska matriser , även om alla ovanstående algoritmer lätt kan generaliseras till rektangulära matriser). $n$

Se även

Toeplitz matris

Länkar

A. Gerasoulis. En snabb algoritm för multiplikation av generaliserade Hilbert-matriser med vektorer // Mathematics of Computation : journal. - 1988. - Vol. 50 , nej. 181 . - S. 179-188 .
I. Gohberg, T. Kailath, V. Olshevsky. Snabb gaussisk eliminering med partiell svängning för matriser med förskjutningsstruktur // Mathematics of Computation : journal. - 1995. - Vol. 64 , nr. 212 . - P. 1557-1576 .
P. G. Martinsson, M. Tygert, V. Rokhlin. En algoritm för inversion av allmänna Toeplitz-matriser $O(N\log ^{2}N)$ // Computers and Mathematics with Applications : journal . - 2005. - Vol. 50 . - s. 741-752 .
S. Schechter. Om invertering av vissa matriser // Matematiska tabeller och andra hjälpmedel för beräkning : journal. - 1959. - Vol. 13 , nr. 66 . - S. 73-77 .