Cap2. Sisteme de ecuatii algebrice liniare - metode .1 Metode directe - gasesc solu¸tia teoretic˘

download Cap2. Sisteme de ecuatii algebrice liniare - metode .1 Metode directe - gasesc solu¸tia teoretic˘

of 46

  • date post

    28-Jun-2019
  • Category

    Documents

  • view

    214
  • download

    0

Embed Size (px)

Transcript of Cap2. Sisteme de ecuatii algebrice liniare - metode .1 Metode directe - gasesc solu¸tia teoretic˘

  • 1/46

    Formularea problemeiMetode stationare

    Concluzii

    Cap2. Sisteme de ecuatii algebrice liniare -metode iterative

    Prof.dr.ing. Gabriela Ciuprina

    Universitatea "Politehnica" Bucuresti, Facultatea de Inginerie Electrica,Departamentul de Electrotehnica

    Suport didactic pentru disciplina Metode numerice, 2017-2018

    Gabriela Ciuprina Sisteme de ecuatii algebrice liniare - metode iterative

  • 2/46

    Formularea problemeiMetode stationare

    Concluzii

    Cuprins

    1 Formularea problemei

    2 Metode stationareIdeeaMetoda JacobiMetoda Gauss-SeidelSOR

    3 Concluzii

    Gabriela Ciuprina Sisteme de ecuatii algebrice liniare - metode iterative

  • 3/46

    Formularea problemeiMetode stationare

    Concluzii

    Formularea problemei

    Sistem de n ecuatii algebrice liniare cu n necunoscute:

    a11x1 + a12x2 + + a1nxn = b1,a21x1 + a22x2 + + a2nxn = b2, an1x1 + an2x2 + + annxn = bn.

    (1)

    Gabriela Ciuprina Sisteme de ecuatii algebrice liniare - metode iterative

  • 4/46

    Formularea problemeiMetode stationare

    Concluzii

    Formularea problemei

    Se da matricea coeficientilor

    A =

    a11 a12 a1na21 a22 a2n an1 an2 ann

    IRnn (2)

    si vectorul termenilor liberi

    b =[

    b1 b2 bn]T

    IRn, (3)

    se cere sa se rezolve sistemul

    Ax = b, (4)

    unde x este solutia

    x =[

    x1 x2 xn]T

    IRn. (5)

    Gabriela Ciuprina Sisteme de ecuatii algebrice liniare - metode iterative

  • 5/46

    Formularea problemeiMetode stationare

    Concluzii

    Buna formulare matematica

    Problema este bine formulata din punct de vedere matematic(solutia exista si este unica)matricea A este nesingulara (are determinantul nenul).Se scrie formal:

    x = A1b

    trebuie citita ca:"x este solutia sistemului algebric liniar Ax = b"si NU "se calculeaza inversa matricei A care se nmulteste cuvectorul b".

    Gabriela Ciuprina Sisteme de ecuatii algebrice liniare - metode iterative

  • 6/46

    Formularea problemeiMetode stationare

    Concluzii

    Conditionarea problemei

    (A) = AA1 (6)

    numar de conditionare la inversare al matricei A.

    x (A)b, (7)

    (A) 1:

    Cazul cel mai favorabil: nA = 1 si x = b. (matrice ortogonala)

    Numarul de conditionare este o proprietate a matricei si nu arelegatura nici cu metoda de rezolvare propriu-zisa, nici cu erorilede rotunjire care apar n mediul de calcul.

    n practica:Daca (A) > 1/eps problema se considera slab conditionata.

    Gabriela Ciuprina Sisteme de ecuatii algebrice liniare - metode iterative

  • 7/46

    Formularea problemeiMetode stationare

    Concluzii

    Clasificarea metodelor

    1 Metode directe - gasesc solutia teoretica a problemeintr-un numar finit de pasi. (Gauss, factorizare LU)

    2 Metode iterative - genereaza un sir de aproximatii alesolutiei care se doreste a fi convergent catre solutiaexacta.

    stationare: Jacobi, Gauss-Seidel, SOR, SSORnestationare (semiiterative): gradienti conjugati (GC),reziduu minim (MINRES), reziduu minim generalizat(GMRES), gradienti biconjugati (BiGC), etc.

    Gabriela Ciuprina Sisteme de ecuatii algebrice liniare - metode iterative

  • 8/46

    Formularea problemeiMetode stationare

    Concluzii

    IdeeaMetoda JacobiMetoda Gauss-SeidelSOR

    Ideea metodelor stationare

    Ax = b (8)

    se construieste un sir de aproximatiix(0),x(1), . . . ,x(k), . . .

    limk

    x(k) = x, unde Ax = b. (9)

    x(k) =

    x(k)1

    x(k)2...

    x(k)n

    IRn1.

    Gabriela Ciuprina Sisteme de ecuatii algebrice liniare - metode iterative

  • 9/46

    Formularea problemeiMetode stationare

    Concluzii

    IdeeaMetoda JacobiMetoda Gauss-SeidelSOR

    Ideea metodelor stationare

    Algoritmul are nevoie de1 o initializare x(0);2 un mod de generare a sirului de iteratii;3 un criteriu de oprire.

    1. Initializarea

    n principiu, arbitrara;

    daca este posibil, ct mai aproape de solutie.

    Gabriela Ciuprina Sisteme de ecuatii algebrice liniare - metode iterative

  • 10/46

    Formularea problemeiMetode stationare

    Concluzii

    IdeeaMetoda JacobiMetoda Gauss-SeidelSOR

    Ideea metodelor stationare

    2. Sirul de iteratii se genereaza recursiv:

    x(k) = F (x(k1)), (10)

    x = F (x), (11)

    x este punct fix pentru aplicatia F .n concluzie, solutia exacta a sistemului de ecuatii este si punctfix pentru F . Rezolvarea sistemului de ecuatii algebrice liniarese face prin cautarea unui punct fix pentru F .

    Gabriela Ciuprina Sisteme de ecuatii algebrice liniare - metode iterative

  • 11/46

    Formularea problemeiMetode stationare

    Concluzii

    IdeeaMetoda JacobiMetoda Gauss-SeidelSOR

    Ideea metodelor stationare

    A = B C. (12)

    Bx = Cx + b (13)

    x = Mx + u, (14)

    M = B1C,

    u = B1b.(15)

    M IRnn se numeste matrice de iteratie.

    F (x) = Mx + u, (16)

    Gabriela Ciuprina Sisteme de ecuatii algebrice liniare - metode iterative

  • 12/46

    Formularea problemeiMetode stationare

    Concluzii

    IdeeaMetoda JacobiMetoda Gauss-SeidelSOR

    Ideea metodelor stationare

    x(k) = F (x(k1)), (17)

    x(k) = Mx(k1) + u, (18)

    x(k) = B1Cx(k1) + B1b. (19)

    Bx(k) = Cx(k1) + b, (20)

    B are o structura particulara.

    Gabriela Ciuprina Sisteme de ecuatii algebrice liniare - metode iterative

  • 13/46

    Formularea problemeiMetode stationare

    Concluzii

    IdeeaMetoda JacobiMetoda Gauss-SeidelSOR

    Ideea metodelor stationare

    3. Criteriul de oprireConditie de oprire bazata de criteriul Cauchy de convergenta:

    x(k) x(k1) , (21)

    Se poate ntmpla nsa ca sirul iteratiilor sa nu fie convergent.Procedurile iterative vor avea ca parametri de intrare, pe lngamarimile ce definesc sistemul:

    o eroare ce reprezinta criteriul dorit de oprire a iteratiilor;

    un numar maxim de iteratii, util pentru a asigura oprireanaturala a procedurii n caz de neconvergenta.

    Nu are sens ca < eps x(k).

    Gabriela Ciuprina Sisteme de ecuatii algebrice liniare - metode iterative

  • 14/46

    Formularea problemeiMetode stationare

    Concluzii

    IdeeaMetoda JacobiMetoda Gauss-SeidelSOR

    Util: vectori si valori proprii

    Definitie: vectorii proprii v ai unei matrice patrate reale M, dedimensiune n sunt acei vectori nenuli, pentru care exista unscalar astfel nct

    Mv = v. (22)

    Obs:

    Reprezentarea geometrica: prin aplicarea M asupra lui,vectorul nu se roteste;

    Vectorii proprii ai unei matrice nu sunt unici. Daca v esteun vector propriu, atunci si vectorul scalat v este deasemenea vector propriu;

    se numeste valoare proprie a matricei M asociatavectorului propriu v.

    Gabriela Ciuprina Sisteme de ecuatii algebrice liniare - metode iterative

  • 15/46

    Formularea problemeiMetode stationare

    Concluzii

    IdeeaMetoda JacobiMetoda Gauss-SeidelSOR

    Util: vectori si valori proprii

    Mkv = kv. (23)

    Daca || < 1 atunci limk Mk v = 0.Daca || > 1 atunci limk Mk v = .

    -2 -1 0 1 2 3 4 5 6 7-2

    -1

    0

    1

    2

    3

    4

    5

    6

    7

    8Doi vectori proprii ai matricei M = [1 3/4; 2 1/2]

    v

    1 = [-1; 2],

    1 = -0.5

    v2 = [1,5; 2],

    2 = 2

    -2 -1 0 1 2 3 4 5 6 7-2

    -1

    0

    1

    2

    3

    4

    5

    6

    7

    8M v = v

    M v

    1 =

    1 v

    1

    M v2 =

    2 v

    2

    -2 -1 0 1 2 3 4 5 6 7-2

    -1

    0

    1

    2

    3

    4

    5

    6

    7

    8M2 v = 2 v

    M2 v

    1 =

    12 v

    1

    M2 v2 =

    22 v

    2

    nmultirea repetata dintre o matrice si vectorii ei proprii.

    Gabriela Ciuprina Sisteme de ecuatii algebrice liniare - metode iterative

  • 16/46

    Formularea problemeiMetode stationare

    Concluzii

    IdeeaMetoda JacobiMetoda Gauss-SeidelSOR

    Util: vectori si valori proprii

    Daca M este simetrica, atunci ea are n vectori proprii liniarindependenti:v(1), v(2), . . . , v(n).Aceasta multime nu este unica, dar fiecare vector propriu are asociato valoare proprie unica.Daca cei n vectori proprii ai lui M formeaza o baza, atunci orice vectoru =

    ni=1 i v

    (i).

    Mk u = 1k1v

    (1) + + nknv

    (n). (24)

    Daca toate valorile proprii sunt subunitare n modul, atunci normavectorului rezultant va tinde catre zero. E suficient ca o singuravaloare proprie sa fie n modul mai mare ca 1, ca norma vectoruluirezultant sa tinda catre infinit.

    Gabriela Ciuprina Sisteme de ecuatii algebrice liniare - metode iterative

  • 17/46

    Formularea problemeiMetode stationare

    Concluzii

    IdeeaMetoda JacobiMetoda Gauss-SeidelSOR

    Util: vectori si valori proprii

    Raza spectrala a unei matrice: proprii

    (M) = maxi

    |i |. (25)

    Valorile proprii sunt radacinile polinomului caracteristic.Deoarece

    (I M)v = 0 (26)

    rezulta in mod necesar anularea polinomului caracteristic almatricei:

    det(I M) = 0. (27)

    Ecuatie de gradul n n care, cf. teoremei fundamentale aalgebrei, are exact n solutii (reale sau n perechi complexconjugate), care sunt valorile proprii ale matricei.

    Gabriela Ciuprina Sisteme de ecuatii algebrice liniare - metode iterative

  • 18/46

    Formularea problemeiMetode stationare

    Concluzii

    IdeeaMetoda JacobiMetoda Gauss-SeidelSOR

    Convergenta

    Teorema 1: Conditia necesara si suficienta

    ca procesul iterativ sa fie convergent este ca raza spectrala amatricei de iteratie sa fie strict subunitara: