Precondiționare

Precondiționarea (de asemenea, precondiționarea ) este procesul de transformare a condițiilor unei probleme pentru o soluție numerică mai corectă . Precondiționarea este de obicei asociată cu o scădere a numărului de stare a problemei[ specificați ] . Problema precondiționată este de obicei rezolvată printr-o metodă iterativă.

Precondiționare pentru sisteme de ecuații algebrice liniare

În algebra liniară și matematica computațională, precondiționatul pentru o matrice este dacă matricea are un număr de condiție mai mic decât y . De asemenea, este mai frecvent să spunem că este un precondiționant decât doar , deoarece valoarea exactă este de obicei costisitoare din punct de vedere computațional. Prin urmare, precondiționarea este adesea înțeleasă ca calculul , mai precis, a produsului unui vector coloană sau a unei matrice de vectori coloană prin , care este de obicei realizat de pachete software complexe folosind metode iterative, unde, în final, valorile exacte nu sunt calculate nici pentru , nici pentru . $P$ $A$ $P^{-1}A$ $A$ $T=P^{-1}$ $P$ $P$ $T=P^{-1}$ $T=P^{-1}$ $P$ $T=P^{-1}$

Precondiționarea este utilizată în metodele iterative atunci când se rezolvă sisteme de ecuații algebrice liniare de forma , deoarece rata de convergență pentru majoritatea solutorilor liniari iterativi crește odată cu scăderea numărului de condiții ca urmare a precondiționării. Rezolvatorii de precondiționare sunt de obicei mai eficienți decât folosirea soluțiilor simple, cum ar fi rezolvatorii gaussieni pentru matrici mari și mai ales rare . Rezolvatorii de precondiționare iterativă pot folosi metode fără matrice , în care matricea de coeficienți nu este stocată separat, iar elementele sale sunt accesate prin produse ale vectorilor matrici. $ax=b$ $A$

Definiție

În loc să rezolvăm sistemul original de ecuații algebrice liniare, se poate rezolva sistemul precondiționat , care poate fi rezolvat prin forma , unde satisface condiția , sau se poate rezolva sistemul precondiționat din stânga: . $AP^{-1}Px = b$ $AP^{-1}y=b$ $y$ $Px=y$ $P^{-1}(Ax-b)=0$

Rezultatul este aceeași soluție ca în sistemul original, atâta timp cât matricea de precondiționare este nesingulară . Cea mai comună este precondiționarea din stânga. Scopul precondiționării este reducerea numărului de condiții a sistemului precondiționat stânga sau dreapta - sau respectiv. O matrice precondiționată sau aproape niciodată nu se formează separat. În schimb, operația de precondiționare se efectuează numai pe vectori gata pregătiți, care se obțin ca urmare a calculului prin metode iterative. $P$ $P^{-1}A$ $AP^{-1}$ $P^{-1}A$ $AP^{-1}$ $P^{-1}$

Utilizarea este întotdeauna un compromis. Deoarece operatorul este aplicat la fiecare pas al rezolutorului liniar iterativ, operația trebuie să fie ușor de calculat (în termeni de timp de calcul). Cel mai rapid precondiționant în acest caz este , deoarece . Evident, ca urmare a funcționării unui astfel de precondiționat, se obține sistemul original. La cealaltă extremă, alegerea , care va da , va avea ca rezultat un număr de condiție optimă de 1, necesitând o iterație pentru ca soluția să convergă. Cu toate acestea, în acest caz , complexitatea calculării precondiționării este comparabilă cu complexitatea rezolvării sistemului original. Prin urmare, este necesar să alegeți undeva între aceste două cazuri extreme, încercând să obțineți numărul minim de iterații, păstrând în același timp ușurința de calcul . Câteva exemple de abordări de bază de precondiționare sunt descrise mai jos. $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}$

Metode iterative cu precondiționare

Metodele iterative cu precondiționare pentru sunt, în cele mai multe cazuri, echivalente matematic cu metodele iterative standard efectuate pe un sistem precondiționat . De exemplu, metoda standard de iterație a lui Richardson pentru o soluție ar arăta ca $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.

În cazul unui sistem precondiționat , metoda precondiționată ar arăta ca $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.

Exemple dintre cele mai populare metode de precondiționare iterativă pentru sisteme liniare sunt metoda gradientului conjugat precondiționat , metoda gradientului biconjugat și metoda reziduurilor minime generalizate. În metodele iterative care calculează parametrii iterativi în termeni de produse punctiforme, este necesară o modificare corespunzătoare a produsului punctual, împreună cu o modificare a $P^{-1}(Ax-b)=0$ $ax-b=0.$

Interpretare geometrică

Pentru o matrice simetrică pozitiv-definită, precondiționatul este de obicei simetric și pozitiv-definit. După aceea, operatorul de precondiționare este, de asemenea, simetric și definit pozitiv. În acest caz, efectul dorit în aplicarea precondiționantului este de a pătrare precondiționant și de a păstra produsul punctual sferic cu . $A$ $P$ $P^{-1}A$ $P^{-1}A$ $P$

Metode de rezolvare a SLAE
Metode directe	Metoda matricei metoda Gauss Metoda Gauss-Iordan Metoda Cramer descompunerea LU Descompunerea Cholesky Metoda de măturare
Metode iterative	metoda Jacobi Metoda Gauss-Seidel Metoda iterației Metoda de relaxare Metoda gradientului conjugat Metoda gradientului biconjugat Metoda gradientului biconjugat stabilizat
General	matrice inversă Metode de proiecție pentru rezolvarea SLAE Precondiționare