Förkonditionering

Förkonditionering, även känd som preconditioning, är en metod inom numerisk linjär algebra som syftar till att förbättra ett linjärt problem inför lösning med iterativa metoder. Genom att omformulera systemet A x = b till ett närmare och bättre konditionerat problem, exempelvis M^{-1} A x = M^{-1} b eller A M^{-1} y = b, där M är en lättinverterbar matris som speglar dominerande egenskaper hos A, kan konvergenshastigheten hos algoritmer som Conjugate Gradient eller GMRES öka avsevärt.

M används som en modell av A som fångar dess struktur men som är enklare att hantera. Den idealiska M är sådan att M ≈ A och att M^{-1} kan tillämpas billigt. Genom att ersätta A med M^{-1} A (eller liknande) före lösningen får man vanligtvis ett system med lägre konditionsnummer κ, vilket leder till färre iterationer för att uppnå önskad noggrannhet. Förkonditioneringens framgång hänger starkt samman med problemets struktur och val av iterativ lösningsteknik.

Vanliga typer av förkonditionering inkluderar diagonal (Jacobi) preconditioning där M är diagonalen av A, diagonala skaleringar samt SSOR, samt inkompletta faktoriseringar som ILU (incomplete LU) och Incomplete Cholesky (för symmetriska positiva definita matriser). För symmetriska positiva definite system används ofta ILU eller Incomplete Cholesky som effektiva alternativ.

Kritiska överväganden är balansen mellan kostnad per iteration och antal iterationer. En mycket stark preconditioner kan vara dyr att tillämpa och ge marginell förbättring om den inte används klokt. Förkonditionering används i stora linjära system från finita element-metoder, flödesdynamik, elektroteknik och relaterade områden samt i vissa optimerings- och maskininlärningsproblem.