49155556 c5 Sisteme Algebrice

download 49155556 c5 Sisteme Algebrice

of 28

  • date post

    19-Jan-2016
  • Category

    Documents

  • view

    20
  • download

    7

Embed Size (px)

Transcript of 49155556 c5 Sisteme Algebrice

  • Metode directe de rezolvri pentru

  • Metoda direct 1: metoda de eliminare a lui GaussMetoda lui Gauss de rezolvare a unui sistem de ecuaii liniare const n eliminarea succesiv a necunoscutelor astfel nct sistemul s se reduc la unul echivalent avnd matricea superior triunghiular, iar apoi determinarea necunoscutelor prin substituie invers.

    Metoda lui Gauss nu este ntotdeauna cea mai bun alegere n rezolvarea sistemelor algebrice liniare, dar este uor de neles ca principiu. Este "cea mai direct" metod i este deosebit de util pentru cazurile cnd rezolvarea sistemului algebric este esenial n ansamblul rezolvrii unei probleme.

  • Metoda direct 1: metoda de eliminare a lui GaussAlgoritmul eliminrii lui Gauss reduce o matrice dat la o matrice a crei componente de pe diagonal i deasupra ei rmn diferite de zero, iar n rest ea este nul. Matricea de aceast form se numete superior triunghiular.

    Eliminarea lui Gauss se realizeaz n n pai, unde n este ordinul matricii A. Pentru a evita creterea erorilor de rotunjire se folosesc proceduri de pivotare, care determin elementele de pe diagonal ce se folosesc n transformrile Gauss. Aceste procedee se repet la fiecare etap a eliminrii i pot fi de dou feluri:-eliminare cu semipivot-eliminare cu pivot

  • Metoda direct 1: metoda de eliminare a lui GaussSemipivot este acel element care la etapa k se afl pe poziia elementului akk, fiind determinat dintr-o linie i0 i o coloan k cu proprietatea c

    Pentru acest lucru s-a mutat linia i0 la linia k i linia k la linia i0. Operaia se numete semipivotare.Pivot este acel element care la etapa k se afl pe poziia elementului akk, fiind determinat dintr-o linie i0 i o coloan j0 cu proprietatea Pentru acest lucru s-a schimbat linia i0 cu linia k i coloana j0 cu coloana k. Acest procedeu de permutare a liniilor n vederea aducerii elementului maxim n valoare absolut n poziia corespunztoare pe diagonala principal se numete pivotare.

  • Metoda direct 1: metoda de eliminare a lui GaussFie sistemul algebric liniar: Ax=b;

    Mnxn (R); Rn

    Transformarea sistemului iniial ntr-un sistem de form triunghiular se realizeaz cu ajutorul a trei operaii elementare:a) interschimbarea a dou ecuaii ntre ele;b) nmulirea unei ecuaii cu o constant nenul;c) scderea unei ecuaii din alta

  • Metoda direct 1: metoda de eliminare a lui GaussPasul1:Eliminarea necunoscutei x1 din ecuaia sistemului ncepnd cu o a doua eliminare cu semipivot.

    eliminare cu semipivot.

    Se nmulete prima ecuaie cu:i=2,3,...,n

    i se adun la celelalte corespunztor coeficieniilor ecuaiilor. Vom obine

    ib=

  • Metoda direct 1: metoda de eliminare a lui GaussPasul 2:Eliminarea necunoscutei x2 din ecuaia sistemului ncepnd cu a treia ecuaie.Avem

    Se nmulete a doua ecuaie cu:i=3,4,...,n

  • Metoda direct 1: metoda de eliminare a lui Gauss

    Vom obine:

    unde

  • Metoda direct 1: metoda de eliminare a lui GaussPasul n: Dup parcurgerea tuturor pailor de eliminiare Gauss, sistemul algebric s-a redus astfel:

  • Metoda direct 1: metoda de eliminare a lui GaussOdat procesul de eliminare ncheiat, urmeaz substituia invers pentru determinarea soluiei sistemului algebric Ax=b:

    ...

    i = n, n-1, ..., 1

  • Metoda direct 1: metoda de eliminare a lui Gaussncercai s rezolvai prin eliminarea lui Gauss sistemul:

    2X1 + 4X2 - X3 = 153X1 - 5X2 + X3 = -43X1 + 2X2 + 3X3 = 38

  • Metoda direct 2: metoda de eliminare a lui Gauss-JordanSpre deosebire de metoda lui Gauss de eliminare, metoda lui Gauss-Jordan reduce matricea sistemului la o matrice diagonal cu toate elementele nule cu excepia diagonalei. Metoda Gauss-Jordan este foarte stabil din punct de vedere numeric, ea particularizeaz eliminarea lui Gauss i rezolv dintr-o dat dou probleme:-determin soluia sistemului liniar-determin matricea invers a sistemului: A-1 . Metoda lui Gauss poate fi considerat a fi poziionat, din punct de vedere al aplicabilitii, ntre metoda Gauss-Jordan i metodele de descompunere triunghiular, de tipul LU.

  • Metoda direct 2: metoda de eliminare a lui Gauss-JordanDezavantajele principale ale acestei proceduri sunt:

    Cere ca tot ce este n partea dreapt s fie stocat i manipulat n acelai timp. Atunci cnd matricea invers nu este dorit procedura de eliminare a lui Gauss-Jordan este de trei ori mai nceat dect cea mai bun tehnic de rezolvare a sistemului liniar.

    Principalul atuu al metodei este c este att de stabil ca i oricare metod direct, poate chiar un pic mai mult, cnd este folosit tehnica de pivotare total. Ea este "foarte direct", uor de neles i reprezint o bun garanie (soluie de rezerv) de fiecare dat cnd ceva nu merge bine i ne-am putea gndi c poate fi vorba de metoda de rezolvare a sistemului liniar.

  • Metoda direct 2: metoda de eliminare a lui Gauss-JordanVectorul soluie nu se schimb n nici un fel dac nlocuim orice linie n A cu o combinaie liniar de ea nsi i orice alte linii atta vreme ct respectm aceleai combinaii liniare cu liniile din b. Procedura de eliminare a lui Gauss-Jordan folosete operaiuni de acest tip pentru a reduce matricea A la matricea identitate de aceeai dimensiune.

    Prima linie este mprit la elementul a11.(astfel ea devine o combinaie liniar trivial de elemente ale primei linii cu orice alt linie; bineneles coeficientul este zero pentru orice alt linie).Apoi se scade cantitatea liniei nti din toate celelalte astfel nct toi ai1 s devin zero. Astfel prima coloan a matricei A coincide cu prima coloan a matricei identice.

  • Metoda direct 2: metoda de eliminare a lui Gauss-JordanAcum ne ocupm de a doua coloan i mprim linia a doua cu a22 i apoi scdem linia a doua din liniile 1,3,4,... astfel nct s avem valorile zero pe a doua coloan. A doua coloan s-a redus astfel la forma coloanei a doua identitate.

    i aa mai departe procedura se continu pentru toate liniile matricei A.

    Evident vom ajunge s avem probleme dac ntlnim un element nul pe diagonal cnd mprim linia cu elementul diagonal al ei (pivotul).

    Nu att de evident, dar adevrat este faptul c eliminarea Gauss-Jordan fr pivotare este numeric instabil n prezena unui roundoff, chiar dac un pivot zero nu este ntlnit. Cu alte cuvinte nu se va folosi eliminarea Gauss-Jordan sau eliminarea Gauss fr pivotare.

  • Metoda direct 2: metoda de eliminare a lui Gauss-Jordann eliminarea lui Gauss Jordan, fiecare lan de calcul constituie o scdere i o nmulire, deci sunt de N3 ori executate pentru o matrice ptratic i de N2M pentru un sistem de N ecuaii i M necunoscute. n cazul lanului de calcul a lui Gauss, eliminarea se face numai 1/3 * N^3 ori deoarece se reduce numai jumtate de matrice i numerele fcute zero reduc ordinul la o treime.

    Att eliminarea lui Gauss ct i eliminarea lui Gauss-Jordan au dezavantajul c membrul drept trebuie cunoscut nainte. Metoda descompunerii LU nu are acest dezavantaj i are tot un numr mic de operaii att pentru soluii cu oricte pri drepte, ct i pentru inversare de matrici.

  • Metoda direct 3: metoda factorizrii LUFie sistemul algebric : Ax=b, unde A este matrice ptratic de dimensiune nxn.

    Metoda factorizrii sau a descompunerii LU are la baz ideea scrierii oricrei matrici ptrate A sub form de produs a dou matrici, una inferior triunghiular i cealalat superior triunghiular. Rezolvarea sistemului realizdu-se prin transformarea sub form de dou sisteme simplificate ce se rezolv prin substituie direct, respectiv prin substituie invers.

    Exist mai multe variante de descompunere a matricii A sub forma LU. Vom discuta varianta Crout a descompunerii LU. Varianta Crout are particularitatea c matricea superior triunghiular U are pe diagonala principal elementele egale cu unitatea.

  • Metoda direct 3: metoda factorizrii LUFactorizarea matricii sistemului sub forma A=LU, presupune o modificare a algoritmul lui Gauss astfel: 1) La fiecare etap k a algoritmului Gauss se copiaz mai nti elementele coloanei k din A, aflate sub diagonal (inclusiv elementele akk) n coloana k a matricei L. 2) Apoi se efectueaz etapa k a algoritmului Gauss asupra matricii A (linia k se mparte la akk, se nmulete pe rnd cu aki, pentru i>k i se scade din liniile urmtoare, pentru anularea elementelor coloanei k aflate sub pivot).

    Dup ultima etap a algoritmului s-a obinut matricea L, iar matricea A adus la forma superior triunghiular conine chiar elementele matricei U.

  • Metoda direct 3: metoda factorizrii LUmatricile L i U n varianta Crout arat astfel:

    Problema determinrii matricii L se regsete tot n paii algoritmului Gauss de eliminare.Eliminarea poate fi privit ca o transformare a matricii A n matricea U. S notm cu F aceast transformare i avem c: FA=U.

  • Metoda direct 3: metoda factorizrii LUMatricea transfomrilor F poate fi determinat dac aplicm eliminarea Gauss la o matrice identitate, deoarece matricea identitate este element neutru pentru inelul matricilor. Considernd un exemplu de matrice de dimensiune 3x3, avem:

    Aplicm nti transformarea F matricii A, obinnd matricea U i apoi aplicm transformarea F matricii I pentru a obine pe F. Rezultatele calculului sunt:

  • Metoda direct 3: metoda factorizrii LUPrima matrice este aadar FA=U. A doua matrice este rezultatul aplicrii lui F asupra matricii identitate I, care este egal cu matricea F nsi. Se observ c F este o matrice inferior triunghiular.

    Prin comparaie cu expresia matriceal A=LU, relativ la expresia transformrii A=F-1U se observ uor c L=F-1. Aadar L poate fi obinut din inversa lui F.

    Inversa unei matrici triunghiulare este uor i rapid de obinut. Inversa unei matrici triunghiular inferioar este tot o matrice inferior triunghiular.

  • Metoda direct 3: metoda factorizrii LUProblema se pune n continuare la ct de mult este afectat matri