Förkonditionering

Förkonditionering (även förkonditionering ) är processen att omvandla villkoren för ett problem för dess mer korrekta numeriska lösning . Förkonditionering är vanligtvis förknippad med en minskning av problemets tillståndsnummer[ specificera ] . Det förkonditionerade problemet löses vanligtvis sedan med en iterativ metod.

Förkonditionering för system med linjära algebraiska ekvationer

I linjär algebra och beräkningsmatematik är förutsättningen för en matris om matrisen har ett villkorsnummer mindre än y . Det är också vanligare att säga att det är en förkonditionering än bara , eftersom det exakta värdet vanligtvis är beräkningsmässigt dyrt. Därför förstås förkonditionering ofta som beräkningen av , mer exakt, produkten av en kolumnvektor eller en matris av kolumnvektorer av , vilket vanligtvis utförs av komplexa programvarupaket med iterativa metoder, där i slutändan exakta värden beräknas inte för antingen , eller för .

Förkonditionering används i iterativa metoder när man löser system av linjära algebraiska ekvationer av formen , eftersom konvergenshastigheten för de flesta iterativa linjära lösare ökar med en minskning av villkorsnumret som ett resultat av förkonditionering. Förkonditioneringslösare är vanligtvis effektivare än att använda enkla lösare som Gausslösare för stora och särskilt glesa matriser . Iterativa förkonditioneringslösare kan använda matrislösa metoder , där koefficientmatrisen inte lagras separat, och dess element nås genom produkter av matrisvektorer.

Definition

Istället för att lösa det ursprungliga systemet med linjära algebraiska ekvationer kan man lösa det förkonditionerade systemet , som kan lösas genom formen , där uppfyller villkoret , eller lösa det vänstra förkonditionerade systemet: .

Resultatet är samma lösning som i originalsystemet, så länge förkonditioneringsmatrisen är icke-singular . Det vanligaste är förkonditionering till vänster. Syftet med förkonditionering är att minska villkorsnumret för det vänstra eller högra förkonditionerade systemet - resp . En förkonditionerad matris eller bildas nästan aldrig separat. Istället utförs förkonditioneringsoperationen endast på färdiga vektorer, som erhålls som ett resultat av beräkning med iterativa metoder.

Användning är alltid en kompromiss. Eftersom operatorn appliceras vid varje steg i den iterativa linjära lösaren, måste operationen vara lätt att beräkna (i termer av beräkningstid). Den snabbaste förkonditioneringen i detta fall är , eftersom . Uppenbarligen, som ett resultat av driften av en sådan förkonditionering, erhålls det ursprungliga systemet. I den andra ytterligheten kommer att välja , vilket ger , att resultera i ett optimalt tillståndstal på 1, vilket kräver en iteration för att lösningen ska konvergera. Ändå, i det här fallet , är komplexiteten för att beräkna förkonditioneraren jämförbar med komplexiteten för att lösa det ursprungliga systemet. Därför är det nödvändigt att välja någonstans mellan dessa två extrema fall, och försöka få det minsta antalet iterationer samtidigt som det är lätt att beräkna . Några exempel på grundläggande förkonditioneringsmetoder beskrivs nedan.

Iterativa metoder med förkonditionering

Iterativa metoder med förkonditionering för är i de flesta fall matematiskt likvärdiga med standard iterativa metoder utförda på ett förkonditionerat system . Till exempel skulle Richardsons standard iterationsmetod för en lösning se ut

I fallet med ett förkonditionerat system skulle den förkonditionerade metoden se ut

Exempel på de mest populära iterativa förkonditioneringsmetoderna för linjära system är den förkonditionerade konjugerade gradientmetoden, den bikonjugerade gradientmetoden och den generaliserade minimala residualmetoden. I iterativa metoder som beräknar iterativa parametrar i termer av prickprodukter krävs en motsvarande ändring av prickprodukten, tillsammans med en ändring av

Geometrisk tolkning

För en symmetrisk positiv-definitiv matris är förkonditioneraren vanligtvis också symmetrisk och positiv-definitiv. Efter det är förkonditioneringsoperatören också symmetrisk och positiv bestämd. I det här fallet är den önskade effekten vid applicering av förkonditioneringsmedlet att förkonditioneringsmedlet är kvadratiskt och ändå hålla prickprodukten sfärisk med .