Implicit metod med alternerande riktning

I numerisk linjär algebra är den alternerande riktningen implicita (ADI) metoden en iterativ metod som används för att lösa Sylvester matrisekvationer . Det är en populär metod för att lösa de stora matrisekvationerna som uppstår i systemteori och styrning , och kan formuleras för att konstruera lösningar i en minneseffektiv, faktoriserad form. Den används också för att numeriskt lösa paraboliska och elliptiska partiella differentialekvationer, och är en klassisk metod som används för att modellera värmeledning och lösa diffusionsekvationen i två eller flera dimensioner. Det är ett exempel på en metod för operatörsdelning .

ADI för matrisekvationer

Metoden

ADI-metoden är en iterationsprocess i två steg som växelvis uppdaterar kolumn- och radutrymmen för en ungefärlig lösning till $AX-XB=C$ . En ADI-iteration består av följande steg:

1. Lös för $X^{(j+1/2)}$ , där $\left(A-\beta _{j+1}I\right)X^{(j+1/2)}=X^{(j)}\left(B-\beta _{j+ 1}I\right)+C.$

2. Lös för $X^{(j+1)}$ , där $X^{(j+1)}\left(B-\alpha _{j+1}I\right)= \left(A-\alpha _{j+1}I\höger)X^{(j+1/2)}-C$ .

Siffrorna $(\alpha _{j+1},\beta _{j+1})$ kallas skiftparametrar, och konvergens beror starkt på valet av dessa parametrar. För att utföra $K$ iterationer av ADI, krävs en initial gissning ${\displaystyle X^{(0)}},$ såväl som $K$ skiftparametrar, $\{(\alpha _{j},\beta _{j})\}_{j=1}^{K}$ .

När ska man använda ADI

Om $A\in \mathbb {C} ^{m\times m}$ och $B\in \mathbb {C} ^{n\times n }$ , då kan $AX-XB=C$ lösas direkt i ${\mathcal {O}}(m^{3}+ n^{3})$ med Bartels-Stewart-metoden . Det är därför bara fördelaktigt att använda ADI när matris-vektormultiplikation och linjära lösningar som involverar $A$ och $B$ kan tillämpas billigt.

Ekvationen $AX-XB=C$ har en unik lösning om och bara om $\sigma (A)\cap \sigma ( B)=\emptyset$ , där $\sigma (M)$ är spektrumet för $M$ . ADI-metoden fungerar dock särskilt bra när $\sigma (A)$ och $\sigma (B)$ är väl åtskilda, och $A$ och $B$ är normala matriser . Dessa antaganden uppfylls till exempel av Lyapunovs ekvation $AX+XA^{*}=C$ när $A$ är positiv definitiv . Under dessa antaganden är nästan optimala skiftparametrar kända för flera val av $A$ och $B$ . Dessutom kan a priori felgränser beräknas, vilket eliminerar behovet av att övervaka restfelet vid implementering.

ADI-metoden kan fortfarande tillämpas när ovanstående antaganden inte är uppfyllda. Användningen av suboptimala skiftparametrar kan påverka konvergensen negativt, och konvergensen påverkas också av icke-normaliteten hos $A$ eller $B$ (ibland fördelaktigt). Krylov subrymdmetoder , såsom Rational Krylov Subspace Method, observeras vanligtvis konvergera snabbare än ADI i denna miljö, och detta har lett till utvecklingen av hybrida ADI-projektionsmetoder.

Val av skiftparameter och ADI-felekvationen

Problemet med att hitta bra växlingsparametrar är inte trivialt. Detta problem kan förstås genom att undersöka ADI-felekvationen. Efter $K$ iterationer ges felet av

$XX^{(K)}=\prod _{j=1}^{K}{\frac {(A-\alpha _{j}I)}{(A-\beta _{j}I )}}\left(XX^{(0)}\right)\prod _{j=1}^{K}{\frac {(B-\beta _{j}I)}{(B-\alpha _{j}I)}}.$

Att välja $X^{(0)}=0$ resulterar i följande gräns för det relativa felet:

${\frac {\left\|XX^{(K)}\right\|_{2}}{\|X\|_{2}}}\leq \|r_{K}(A) \|_{2}\|r_{K}(B)^{-1}\|_{2},\quad r_{K}(M)=\prod _{j=1}^{K}{ \frac {(M-\alpha _{j}I)}{(M-\beta _{j}I)}}.$

där $\|\cdot \|_{2}$ är operatornormen . Den ideala uppsättningen av skiftparametrar $\{(\alpha _{j},\beta _{j})\}_{j=1}^{K }$ definierar en rationell funktion $r_{K}$ som minimerar kvantiteten $\|r_{K}(A) \|_{2}\|r_{K}(B)^{-1}\|_{2}$ . Om $A$ och $B$ är normala matriser och har egenuppdelningar $A=V_{A}\Lambda _{A}V_{A}^{ *}$ och ${\displaystyle B=V_{B}\Lambda _{B}V_{B}^{*}} ,$ sedan

$\|r_{K}(A )\|_{2}\|r_{K}(B)^{-1}\|_{2}=\|r_{K}(\Lambda _{A})\|_{2}\| r_{K}(\Lambda _{B})^{-1}\|_{2}$ .

Nästan optimala växlingsparametrar

Nästan optimala skiftparametrar är kända i vissa fall, som när $\Lambda _{A}\subset [a,b]$ och ${\ displaystyle \Lambda _{B}\subset [c,d]}$ , där $[a,b]$ och $[c,d]$ är disjunkta intervall på den verkliga linjen. Lyapunovs ekvation ${\displaystyle AX+XA^{*}=C} ,$ till exempel, uppfyller dessa antaganden när $A$ är positiv definitiv . I det här fallet kan skiftparametrarna uttryckas i sluten form med elliptiska integraler och kan enkelt beräknas numeriskt.

Mer allmänt, om de är stängda, disjunkta uppsättningar $E$ och $F$ , där $\Lambda _{A}\subset E$ och ${\displaystyle \Lambda _{B}\subset F} ,$ är kända, löses det optimala skiftparametervalsproblemet ungefär genom att hitta en extremal rationell funktion som uppnår värdet

$Z_{K}(E,F):=\inf _{r}{\frac {\sup _{z\in E}|r(z)|}{\inf _{z\in F }|r(z)|}},$

där infimum tas över alla rationella funktioner av grad $(K,K)$ . Detta approximationsproblem är relaterat till flera resultat i potentiell teori , och löstes av Zolotarev 1877 för $E$ = [a, b] och $F=-E.$ Lösningen är också känd när $E$ och $F$ är disjunkta skivor i det komplexa planet.

Heuristiska skiftparameterstrategier

När mindre är känt om $\sigma (A)$ och $\sigma (B)$ , eller när $A$ eller $B$ är icke -normala matriser, kanske det inte går att hitta nära optimala skiftparametrar. I den här inställningen kan en mängd olika strategier för att generera bra skiftparametrar användas. Dessa inkluderar strategier baserade på asymptotiska resultat i potentiell teori, med användning av Ritz-värdena för matriserna $A$ , ${\displaystyle A^{-1}} ,$ B $\displaystyle B}$ och $B^{-1}$ för att formulera ett girigt tillvägagångssätt, och cykliska metoder, där samma lilla samling skiftparametrar återanvänds tills en konvergenstolerans uppfylls. När samma skiftparameter används vid varje iteration, är ADI ekvivalent med en algoritm som kallas Smiths metod.

Faktoriserad ADI

I många applikationer är $A$ och $B$ mycket stora, glesa matriser, och $C$ kan faktoriseras som $C=C_{1 }C_{2}^{*}$ , där $C_{1}\in \mathbb {C} ^{m\times r},C_ {2}\in \mathbb {C} ^{n\ gånger r}$ , med $r=1,2$ . I en sådan inställning kanske det inte är möjligt att lagra den potentiellt täta matrisen $X$ explicit. En variant av ADI, kallad factored ADI, kan användas för att beräkna $ZY^{*}$ , där $X\approx ZY^{*}$ . Effektiviteten av faktoriserad ADI beror på om $X$ är väl approximerad av en matris med låg rangordning. Detta är känt för att vara sant under olika antaganden om $A$ och $B$ .

ADI för paraboliska ekvationer

Historiskt har ADI-metoden utvecklats för att lösa 2D-diffusionsekvationen på en kvadratisk domän med ändliga skillnader. Till skillnad från ADI för matrisekvationer kräver ADI för paraboliska ekvationer inte valet av skiftparametrar, eftersom skiftet som uppträder i varje iteration bestäms av parametrar som tidssteg, diffusionskoefficient och rutnätsavstånd. Kopplingen till ADI på matrisekvationer kan observeras när man beaktar verkan av ADI-iterationen på systemet vid steady state.

Exempel: 2D diffusionsekvation

Stencilfigur för den alternerande riktningen implicita metoden i finita differensekvationer

Den traditionella metoden för att lösa värmeledningsekvationen numeriskt är Crank–Nicolson-metoden . Denna metod resulterar i en mycket komplicerad uppsättning ekvationer i flera dimensioner, som är kostsamma att lösa. Fördelen med ADI-metoden är att de ekvationer som ska lösas i varje steg har en enklare struktur och kan lösas effektivt med den tridiagonala matrisalgoritmen .

Betrakta den linjära diffusionsekvationen i två dimensioner,

${\partial u \over \partial t}=\left({\partial ^{2}u \over \partial x^{2}}+{\partial ^{2}u \over \partial y^{2}}\right)=(u_{xx}+u_{yy})$

Den implicita Crank–Nicolson-metoden producerar följande finita differensekvation:

${u_{ij }^{n+1}-u_{ij}^{n} \over \Delta t}={1 \over 2(\Delta x)^{2}}\left(\delta _{x}^{2 }+\delta _{y}^{2}\right)\left(u_{ij}^{n+1}+u_{ij}^{n}\right)$

var:

$\Delta x=\Delta y$

och $\delta _{p}^{2}$ är den centrala andra differensoperatorn för den p -:te koordinaten

$\delta _{p}^{2}u_{ij}=u_{ij+e_{p }}-2u_{ij}+u_{ij-e_{p}}$

med $e_{p}=10$ eller $01$ för $p=x$ respektive $y$ (och $ij$ en stenografi för gitterpunkter ${\displaystyle (i,j)} )$ .

Efter att ha utfört en stabilitetsanalys kan det visas att denna metod kommer att vara stabil för alla $\Delta t$ .

En nackdel med Crank–Nicolson-metoden är att matrisen i ovanstående ekvation är bandad med en bandbredd som i allmänhet är ganska stor. Detta gör direkt lösning av systemet med linjära ekvationer ganska kostsam (även om det finns effektiva ungefärliga lösningar, till exempel användning av den konjugerade gradientmetoden förutsatt med ofullständig Cholesky-faktorisering ).

Tanken bakom ADI-metoden är att dela upp de finita differensekvationerna i två, en med x -derivatan tagen implicit och nästa med y -derivatan tagen implicit,

$y}^{2}u_{ij}^{n}\right) \över \Delta x^{2}}$

${\displaystyle {u_{ij} ^{n+1/2}-u_{ij}^{n} \over \Delta t/2}={\left(\delta _{x}^{2}u_{ij}^{n+1/ 2}+\delta _$

${u_{ij}^{n+1}-u_{ij} ^{n+1/2} \over \Delta t/2}={\left(\delta _{x}^{2}u_{ij}^{n+1/2}+\delta _{y} ^{2}u_{ij}^{n+1}\höger) \över \Delta y^{2}}$

Det involverade ekvationssystemet är symmetriskt och tridiagonalt (bandbredd 3) och löses vanligtvis med hjälp av tridiagonal matrisalgoritm .

Det kan visas att denna metod är ovillkorligt stabil och andra ordningen i tid och rum. Det finns mer förfinade ADI-metoder som Douglas metoder, eller f-faktormetoden som kan användas för tre eller flera dimensioner.

Generaliseringar

Användningen av ADI-metoden som ett operatörsdelningsschema kan generaliseras. Det vill säga, vi kan överväga allmänna evolutionsekvationer

${\dot {u}}=F_{1}u+F_{2}u,$

där $F_{1}$ och $F_{2}$ är (möjligen olinjära) operatorer definierade på ett Banach-mellanslag. I diffusionsexemplet ovan har vi $F_{1}={\partial ^{2} \over \partial x^{2}}$ och $F_{2}={\partial ^{2} \over \partial y^{2}}$ .

Fundamental ADI (FADI)

Förenkling av ADI till FADI

Det är möjligt att förenkla den konventionella ADI-metoden till Fundamental ADI-metoden, som bara har liknande operatörer på vänster sida samtidigt som den är operatörsfri på höger sida. Detta kan betraktas som det grundläggande (grundläggande) schemat för ADI-metoden, utan fler operatorer (som ska reduceras) till höger, till skillnad från de flesta traditionella implicita metoder som vanligtvis består av operatorer på båda sidor av ekvationerna. FADI-metoden leder till enklare, mer koncisa och effektiva uppdateringsekvationer utan att försämra noggrannheten hos den konventionella ADI-metoden.

Relationer till andra implicita metoder

Många klassiska implicita metoder av Peaceman-Rachford, Douglas-Gunn, D'Yakonov, Beam-Warming, Crank-Nicolson, etc., kan förenklas till grundläggande implicita scheman med operatörsfria högersidor. I sina grundläggande former kan FADI-metoden för andra ordningens tids noggrannhet relateras nära till den grundläggande lokalt endimensionella (FLOD) metoden, som kan uppgraderas till andra ordningens tids noggrannhet, såsom för tredimensionella Maxwells ekvationer i beräkningselektromagnetik . För två- och tredimensionella värmelednings- och diffusionsekvationer kan både FADI- och FLOD-metoder implementeras på enklare, mer effektivt och stabilt sätt jämfört med deras konventionella metoder.