Előkondicionálás

Az előfeltételezés (egyben előkondicionálás ) az a folyamat, amelynek során egy probléma feltételeit átalakítjuk a helyesebb numerikus megoldás érdekében . Az előkondicionálás általában a probléma állapotszámának csökkenésével jár[ adja meg ] . Az előfeltételezett problémát általában iteratív módszerrel oldják meg.

Előfeltételezés lineáris algebrai egyenletrendszerekhez

A lineáris algebrában és a számítási matematikában a mátrix előfeltétele az, ha a mátrix feltételszáma kisebb, mint y . Szintén gyakrabban mondják, hogy ez egy előfeltétel, mint a , mivel a pontos érték általában számításilag drága. Ezért az előkondicionálást gyakran úgy értik, mint egy oszlopvektor vagy oszlopvektorok mátrixának szorzatának kiszámítását -val , amelyet általában összetett szoftvercsomagok hajtanak végre iteratív módszerekkel, ahol a végén pontos értékeket adnak meg. nem számítanak sem a , sem a -ra . $P$ $A$ $P^{-1}A$ $A$ $T=P^{-1}$ $P$ $P$ $T=P^{-1}$ $T=P^{-1}$ $P$ $T=P^{-1}$

Az előkondicionálást iteratív módszerekben alkalmazzák a alakú lineáris algebrai egyenletrendszerek megoldása során , mivel a legtöbb iteratív lineáris megoldó esetében a konvergencia sebessége nő a feltételszám csökkenésével az előfeltételezés eredményeként. Az előkondicionáló megoldók általában hatékonyabbak, mint az egyszerű megoldók, például a Gauss -megoldók használata nagy és különösen ritka mátrixokhoz . Az iteratív előkondicionáló megoldók használhatnak mátrix nélküli módszereket , amelyekben az együttható mátrix nincs külön tárolva, és elemei mátrixvektorok szorzatán keresztül érhetők el. $ax=b$ $A$

Definíció

Az eredeti lineáris algebrai egyenletrendszer megoldása helyett megoldható az előfeltételes rendszer , amely megoldható a formán keresztül , ahol a feltétel teljesül , vagy megoldható a bal oldali előfeltételes rendszer: . $AP^{-1}Px = b$ $AP^{-1}y=b$ $y$ $Px=y$ $P^{-1}(Ax-b)=0$

Az eredmény ugyanaz, mint az eredeti rendszerben, mindaddig, amíg az előkondicionáló mátrix nem szinguláris . A leggyakoribb a baloldali előkondicionálás. Az előkondicionálás célja a bal vagy jobb előkondicionált rendszer kondíciószámának csökkentése - ill . Előkondicionált mátrix vagy szinte soha nem képezik külön. Ehelyett az előkondicionálási műveletet csak kész vektorokon hajtjuk végre, amelyeket iteratív módszerekkel végzett számítás eredményeként kapunk. $P$ $P^{-1}A$ $AP^{-1}$ $P^{-1}A$ $AP^{-1}$ $P^{-1}$

A használat mindig kompromisszum. Mivel az iteratív lineáris megoldó minden lépésében az operátort alkalmazzuk, a műveletnek könnyen kiszámíthatónak kell lennie (számítási idő szempontjából). A leggyorsabb előfeltétel ebben az esetben az , mivel . Nyilvánvalóan egy ilyen előkondicionáló működésének eredményeként az eredeti rendszert kapjuk. A másik véglet, ha választjuk , ami azt adja , hogy az optimális feltételszám 1 lesz, ami egy iterációt igényel a megoldás konvergálásához. Ennek ellenére ebben az esetben az előkondicionáló kiszámításának bonyolultsága összemérhető az eredeti rendszer megoldásának bonyolultságával. Ezért választani kell valahol a két szélsőséges eset között, meg kell próbálnunk a minimális számú iterációt elérni, miközben megőrizzük a könnyű számítást . Az alábbiakban néhány példát ismertetünk az alapvető előkondicionálási megközelítésekre. $P$ $P^{-1}$ $P^{-1}$ $P=I$ $P^{-1}=I$ $P=A$ $P^{-1}A=AP^{-1}=I$ $P^{-1}=A^{-1}$ $P$ $P^{-1}$

Iteratív módszerek előfeltételezéssel

Az iteratív módszerek előkondicionálással a legtöbb esetben matematikailag egyenértékűek az előfeltételezett rendszeren végzett standard iteratív módszerekkel . Például Richardson szabványos iterációs módszere egy megoldáshoz így nézne ki $ax-b=0$ $P^{-1}(Ax-b)=0$ $ax-b=0$

\mathbf{x}_{n+1}=\mathbf{x}_n-\gamma_n (A\mathbf{x}_n-\mathbf{b}),\ n \ge 0.

Előfeltételes rendszer esetén az előfeltételes módszer így nézne ki $P^{-1}(Ax-b)=0$

\mathbf{x}_{n+1}=\mathbf{x}_n-\gamma_n P^{-1}(A\mathbf{x}_n-\mathbf{b}),\ n \ge 0.

A lineáris rendszerek legnépszerűbb iteratív előkondicionálási módszerei például az előfeltételes konjugált gradiens módszer, a bikonjugált gradiens módszer és az általánosított minimum maradékok módszere. Az iteratív módszereknél, amelyek az iteratív paramétereket pontszorzatok alapján számítják ki, a pontszorzat megfelelő módosítására van szükség, valamint a pontszorzat módosítására . $P^{-1}(Ax-b)=0$ $ax-b=0.$

Geometriai értelmezés

Szimmetrikus pozitív-definit mátrix esetén az előfeltétel általában szimmetrikus és pozitív-definit is. Ezt követően az előkondicionáló operátor is szimmetrikus és pozitív határozott. Ebben az esetben az előkondicionáló alkalmazásakor a kívánt hatás az, hogy az előkondicionáló négyzet alakú legyen, és a ponttermék továbbra is gömb alakú maradjon a -val . $A$ $P$ $P^{-1}A$ $P^{-1}A$ $P$

Az SLAE megoldásának módszerei
Közvetlen módszerek	Mátrix módszer Gauss módszer Gauss-Jordan módszer Cramer módszer LU bomlás Cholesky-bomlás Sweep módszer
Iteratív módszerek	Jacobi módszer Gauss-Seidel módszer Iterációs módszer Relaxációs módszer Konjugált gradiens módszer Bikonjugált gradiens módszer Stabilizált bikonjugátum gradiens módszer
Tábornok	inverz mátrix Vetítési módszerek SLAE megoldására Előkondicionálás