Polynommatrisspektralfaktorisering

Polynommatriser studeras allmänt inom systemteori och kontrollteori och har sett andra användningsområden för stabila polynom . Inom stabilitetsteorin har Spectral Factorization använts för att hitta determinanta matrisrepresentationer för bivariata stabila polynom och reella nollpolynom. Ett nyckelverktyg som används för att studera dessa är en matrisfaktorisering känd som antingen Polynomial Matrix Spectral Factorization eller Matrix Fejer–Riesz Theorem.

Givet ett univariat positivt polynom $p(t)$ , ett polynom som antar icke-negativa värden för alla reella indata $t$ , ger Fejer–Riesz-satsen polynomspektralfaktoriseringen $p(t)=q(t)q({\bar {t}})^{*}$ . Resultat av detta formulär kallas allmänt för Positivstellensatz . Med tanke på positiv definititet som matrisanalogen av positivitet, tillhandahåller polynommatrisspektralfaktorisering en liknande faktorisering för polynommatriser som har ett positivt definitivt intervall. Denna nedbrytning relaterar också till Cholesky-nedbrytningen för skalära matriser $A=LL^{*}$ . Detta resultat bevisades ursprungligen av Wiener i ett mer allmänt sammanhang som handlade om integrerbara matrisvärderade funktioner som också hade integrerbar log-determinant. Eftersom applikationer ofta handlar om polynombegränsningen finns det enklare bevis och individuell analys med fokus på detta fall. Svagare positivstellensatz-förhållanden har studerats, speciellt med tanke på när polynommatrisen har en positiv bestämd bild på semi-algebraiska delmängder av realerna. Många publikationer nyligen har fokuserat på att effektivisera bevis för dessa relaterade resultat. Den här artikeln följer ungefär Lasha Ephremidzes senaste bevismetod som endast bygger på elementär linjär algebra och komplex analys .

Spektralfaktorisering används flitigt i linjär-kvadratisk-gaussisk kontroll . På grund av denna applikation har det funnits många algoritmer för att beräkna spektrala faktorer. Vissa moderna algoritmer fokuserar på den mer allmänna miljön som ursprungligen studerades av Wiener. I $1\times 1$ är problemet känt som polynomisk spektral faktorisering, eller Fejer-Riesz-satsen, och har många klassiska algoritmer. Vissa moderna algoritmer har använt Toeplitz-matrisframsteg för att påskynda faktorberäkningar.

Påstående

Låt $P(t)={\begin{bmatrix} p_{11}(t)&\ldots &p_{1n}(t)\\\vdots &\ddots &\vdots \\p_{n1}(t)&\cdots &p_{nn}(t)\\\end {bmatris}}$ vara en polynommatris där varje post $p_{ij}(t)$ är ett komplext koefficientpolynom med högst grad $N$ . Antag att vi för nästan alla $t\in \mathbb {R}$ har $P(t)$ är en positiv definitiv hermitisk matris. Då finns det en polynommatris $Q(t)$ så att $P(t)=Q(t)Q(t) ^{*}$ för alla $t\in \mathbb {R}$ . Vi kan dessutom hitta $Q(t)$ som är ickesingular på det nedre halvplanet.

Utökning till komplexa ingångar

Observera att om $}}$${\displaystyle Q(t)={\begin{ bmatrix}q_{11}(t)&\ldots &q_{1n}(t)\\\vdots &\ddots &\vdots \\q_{n1}(t)&\cdots &q_{nn}(t)\\ \end{$$Q({\bar {t}})^{*}={\begin{bmatrix}q_{11}({\bar {t}})^{*}&\ldots &q_{n1 }({\bar {t}})^{*}\\\vdots &\ddots &\vdots \\q_{1n}({\bar {t}})^{*}&\cdots &q_{nn} ({\bar {t}})^{*}\\\end{bmatrix}}$ sedan . När $q_{ij}(t)$ är ett komplext koefficientpolynom eller en komplex koefficientrationell funktion har vi $q_{ij}({\bar { t}})^{*}$ är också en polynom eller rationell funktion. För $t\in \mathbb {R}$ har vi

$$P(t)=Q(t)Q(t)^{*}=Q(t) Q({\bar {t}})^{*}$$

Detta på grund av följande observation: Eftersom inmatningarna av $Q(t)Q({\bar {t}})^{*}$ och ${\ displaystyle P(t)}$ är komplexa polynom som överensstämmer på den reella linjen, de är i själva verket samma polynom. Vi kan dra slutsatsen att de faktiskt är överens för alla komplexa indata.

Rationell spektral faktorisering

Låt $p(t)$ vara en rationell polynomfunktion där $p(t)>0$ för nästan alla $t\in \mathbb {R }$ . Då finns det rationell $q(t)$ med $p(t)=q(t)q({\bar { t}})^{*}$ där $q(t)$ inte har några poler eller nollor i det nedre halvplanet. Denna nedbrytning är unik upp till multiplikation med komplexa skalärer av norm $1$ . Detta är relaterat till uttalandet av polynommatrisspektralfaktoriseringssatsen begränsad till fallet ${\displaystyle 1\x1} .$

För att bevisa existens skriv ${\displaystyle p(x)=c{\frac {\prod _{i}(x-\alpha _{i})}{\prod _{j}(x-\beta _{j})}}} där$ α $\displaystyle \alpha _{i}\neq \beta _{j}}$ . Om vi ​​låter $x\to \infty$ , kan vi dra slutsatsen att $c$ är verklig och positiv. Genom att dela ut med ${\sqrt {c}}$ reducerar vi till det monotiska fallet. Täljaren och nämnaren har distinkta uppsättningar av rötter, så alla verkliga rötter som dyker upp i någondera måste ha jämn multiplicitet (för att förhindra att tecken ändras lokalt). Vi kan dela ut dessa reella rötter för att reducera till fallet där $p(t)$ bara har komplexa rötter och poler. Med hypotesen $p(x)={\frac {\prod _{i}(x-\alpha _{i})}{\prod _{j}(x-\beta _{j})}}= {\frac {\prod _{i}(x-{\bar {\alpha _{i}}})}{\prod _{j}(x-{\bar {\beta _{j}}}) }}={\bar {p({\bar {x}})}}$ vi . Eftersom alla $\alpha _{i},\beta _{j}$ är komplexa (och därmed inte fixerade konjugationspunkter) kommer de båda i konjugerade par. För varje konjugat par, välj nollan eller polen i det övre halvplanet och ackumulera dessa för att få $q(t)$ . Det unika resultatet följer på ett standardsätt.

Cholesky nedbrytning

Inspirationen till detta resultat är en faktorisering som kännetecknar positiva bestämda matriser.

Nedbrytning för skalära matriser

Givet varje positiv bestämd skalär matris ${\displaystyle A} tillåter$ Cholesky -nedbrytningen oss att skriva $A=LL^{*}$ där $L$ är en lägre triangulär matris. Om vi ​​inte begränsar oss till lägre triangulära matriser kan vi överväga alla faktoriseringar av formen $A=VV^{*}$ . Det är inte svårt att kontrollera att alla faktoriseringar uppnås genom att titta på omloppsbanan för $L$ under höger multiplikation med en enhetlig matris, $V=LU$ .

För att erhålla den nedre triangulära nedbrytningen inducerar vi genom att dela av den första raden och den första kolumnen:

$${\begin{bmatrix}a_{11}&\mathbf {a} _{12}^{*}\\\mathbf {a} _{12}&A_{ 22}\\\end{bmatrix}}={\begin{bmatrix}l_{11}&0\\\mathbf {l} _{21}&L_{22}\end{bmatrix}}{\begin{bmatrix}l_ {11}^{*}&\mathbf {l} _{21}^{*}\\0&L_{22}^{*}\end{bmatrix}}={\begin{bmatrix}l_{11}l_{ 11}^{*}&l_{11}\mathbf {l} _{21}^{*}\\l_{11}^{*}\mathbf {l} _{21}&\mathbf {l} _{ 21}\mathbf {l} _{21}^{*}+L_{22}L_{22}^{*}\end{bmatrix}}$$

Att lösa dessa i termer av $a_{ij}$ får vi

$$l_{11}={\sqrt {a_{11}}}$$

$$\mathbf {l} _{21}={\frac {1}{\sqrt {a_{11}}}}\mathbf {a} _{12}$$

$$L_{22}L_{22}^{*}=A_{22}-{\frac {1}{a_{11}} }\mathbf {a} _{12}\mathbf {a} _{12}^{*}$$

Eftersom $A$ är positivt definitivt har vi $a_{11}$ är ett positivt reellt tal, så det har en kvadratrot. Det sista villkoret från induktion sedan den högra sidan är Schur-komplementet av ${\displaystyle A} ,$ som i sig är positivt definitivt.

Nedbrytning för rationella matriser

Betrakta nu $P(t)={\begin{bmatrix }p_{11}(t)&\ldots &p_{1n}(t)\\\vdots &\ddots &\vdots \\p_{n1}(t)&\cdots &p_{nn}(t)\\\ end{bmatrix}}$ där $p_{ij}(t)$ är komplexa rationella funktioner och $P(t)$ är positiv definitiv hermitian för nästan alla reella $t$ . Sedan genom den symmetriska Gauss-elimineringen vi utförde ovan, är allt vi behöver visa att det finns en rationell $q_{11}(t)$ så att $p_{11}(t)=q_{11}(t)q_{11}(t)^{*}$ för verkligt $t$ , vilket följer av vår rationella spektral faktorisering. När vi väl har det kan vi lösa för $l_{11}(t),\mathbf {l} _{21}(t)$ . Eftersom Schur-komplementet är positivt definitivt för det reella $t$ bort från polerna och Schur-komplementet är en rationell polynommatris kan vi inducera för att hitta $L_{22}$ .

Det är inte svårt att kontrollera att vi faktiskt får $P(t)=L(t)L(t)^{*}$ där $L(t)$ är en rationell polynommatris utan poler i det nedre halvplanet.

Utvidgning till polynomupplösningar

För att bevisa förekomsten av polynommatrisspektralfaktorisering börjar vi med den rationella polynommatrisen Cholesky Decomposition och modifierar den för att ta bort singulariteter i det nedre halvplanet. Nämligen given $P(t)={\begin{bmatrix }p_{11}(t)&\ldots &p_{1n}(t)\\\vdots &\ddots &\vdots \\p_{n1}(t)&\cdots &p_{nn}(t)\\\ slut{bmatris}}$ med varje inmatning $p_{ij}(t)$ ett komplext koefficientpolynom har vi rationell polynommatris $L(t)$ med $P(t)=L(t)L(t)^{*}$ för verkligt $t$ , där $L(t)$ har inga nedre halvplanspoler. Givet en rationell polynommatris $U(t)$ som är enhetligt värderad för reell $t$ , finns det en annan nedbrytning, $P(t)=L(t)L(t)^{*}=(L(t)U(t) ))(L(t)U(t))^{*}$ .

Ta bort nedre halvplanssingulariteter

Om $\det(L(a))=0$ så finns det en skalär enhetlig matris $U$ så att $Ue_{1}={\frac {a}{|a|}}$ . Detta innebär att $L(t)U$ har första kolumn försvinner vid $a$ . För att ta bort singulariteten vid $a$ multiplicerar vi med

$$U(t)=\operatörsnamn {diag} (1,\ldots ,{\frac {z-{ \bar {a}}}{za}},\ldots ,1)$$

$L(t)UU(t)$ har en determinant med en noll mindre (med multiplicitet) vid a, utan att införa några poler i det nedre halvplanet av någon av posterna.

Utöka analyticiteten till hela C

Efter modifieringar uppfyller nedbrytningen $P(t)=Q(t)Q(t)^{*}$$Q( t)}$ displaystyle är analytisk och inverterbar på det nedre halvplanet. För att utöka analyticiteten till det övre halvplanet behöver vi denna nyckelobservation: Givet en rationell matris $Q(t)$ som är analytisk i det nedre halvplanet och icke-singular i det nedre halvplanet, har vi $Q(t)^{-1}$ är analytisk och icke-singular i det nedre halvplanet. Analyticiteten följer av den adjugerade matrisformeln (eftersom både posterna för $Q(t)$ och $\det(Q(t))^{- 1}$ är analytiska på det nedre halvplanet). Icke-singulariteten följer av $\det(Q(t)^{-1})=\det(Q(t))^{ -1}$ som bara kan ha nollor på platser där $\det(Q(t))$ hade poler. Determinanten för en rationell polynommatris kan bara ha poler där dess poster har poler, så $\det(Q(t))$ har inga poler i det nedre halvplanet.

Från vår observation i Extension to Complex Inputs har vi $P(t)=Q(t)Q({\bar {t}})^{ *}$ för alla komplexa tal. Detta innebär $Q({\bar {t}})=(P(t)Q(t)^{-1}) ^{*}$ . Eftersom $Q(t)^{-1}$ är analytisk på det nedre halvplanet, är $Q(t)$ analytisk på det övre halvplanet. Slutligen om $Q(t)$ har en pol på den reella linjen så har $Q({\bar {t}})^{*}$ samma pol på den reella linjen som motsäger faktumet att $P(t)$ inte har några poler på den reella linjen (den är analytisk överallt genom hypotes).

Ovanstående visar att om $Q(t)$ är analytisk och inverterbar på det nedre halvplanet så är $Q(t)$ analytisk överallt och därmed en polynommatris.

Unikhet

Givet två polynommatrisuppdelningar som är inverterbara på det nedre halvplanet ${\displaystyle P(t)=Q(t )Q({\bar {t}})^{*}=R(t)R({\bar {t}})^{*}} vi arrangerar om$ till $(R(t)^{-1}Q(t))(R({\bar {t}})^{-1 }Q({\bar {t}}))^{*}=I$ . Eftersom $R(t)$ är analytisk på det nedre halvplanet och icke-singular, $R(t)^{-1}Q(t)$ är en rationell polynommatris som är analytisk och inverterbar på det nedre halvplanet. Med samma argument som ovan har vi $R(t)^{-1}Q(t)$ är i själva verket en polynommatris som är enhetlig för alla reella ${ \displaystyle t}$ . Detta betyder att om $\mathbf {q} _{i}(t)$ är den ${\displaystyle i}:$ e raden av $Q(t)$ så är $\mathbf {q} _{i}(t)\mathbf {q} _{i}({\bar {t}})^{*} =1$ . För real $t$ är detta en summa av icke-negativa polynom som summeras till en konstant, vilket innebär att var och en av summan i själva verket är konstanta polynom. Då $Q(t)=R(t)U$ där $U$ är en skalär enhetlig matris.

Exempel

Betrakta $A(t)={\begin{bmatrix}t^{2}+1&2t\\2t&t^{2}+1 \\\end{bmatrix}}$ . Sedan genom symmetrisk gaussisk eliminering får vi den rationella nedbrytningen $A(t)={\begin{bmatrix}ti&0\\{\frac {2t}{t+i}}&{\frac {t^{2}-1}{t+i}}\\ \end{bmatrix}}{\begin{bmatrix}ti&0\\{\frac {2t}{t+i}}&{\frac {t^{2}-1}{t+i}}\\\end {bmatrix}}^{*}$ . Denna nedbrytning har inga poler i det övre halvplanet. Determinanten är dock ${\frac {(t-1)(ti)(t+1)}{t+i}}$ , så vi måste modifiera vår nedbrytning för att bli av med singulariteten vid $-i$ . Först multiplicerar vi med en skalär enhetlig matris för att få en kolumn att försvinna vid $i$ . Betrakta $U={\frac {1}{\sqrt {2}}}{\begin{bmatrix}1&1\\i&-i\\\end{bmatrix} }$ . Då har vi en ny kandidat för vår nedbrytning ${\begin{bmatrix}ti&0\\{\frac {2t}{t+i}}&{\frac {t^{2}-1}{t+i}}\\ \end{bmatrix}}U={\frac {1}{\sqrt {2}}}{\begin{bmatrix}ti&t-i\\i{\frac {(ti)^{2}}{t+i }}&-i(t+i)\\\end{bmatris}}$ . Nu försvinner den första kolumnen kl

$i$ , så vi multiplicerar genom (till höger) med ${\displaystyle U(t)={\frac {1}{\sqrt {2}}}{\begin{bmatrix}{\frac {t+i}{ti}}&0\\0&1\end{bmatrix}}} för att$ få $Q(t)={\begin{bmatrix}ti&0\\{\frac {2t}{t+i}}&{\frac {t^{2}-1}{t+i}}\\ \end{bmatrix}}UU(t)={\frac {1}{\sqrt {2}}}{\begin{bmatrix}t+i&t-i\\i(ti)&-i(t+i) \\\end{bmatrix}}.$ Observera $\det(Q(t))=i(1-t^{2})$ . Detta är vår önskade sönderdelning $A(t)=Q(t)Q(t)^{*}$ utan singulariteter i det nedre halvplanet.

Se även

• Matrisfaktorisering av ett polynom