Sisteme Liniare

PLANUL LUCRĂRII

Introducere

Capitolul I – Elemente teoretice privind compatibilitatea sistemelor liniare

Algoritmii

Sisteme de ecuații liniare

Capitolul II – Metode directe de rezolvare a sistemelor liniare

2.1. Metoda CRAMMER

2.2. Metoda eliminarii successive (GAUSS

2.3. Metoda GAUSS-JORDAN

Capitolul III – Metode interactive pentru rezolvarea unui sistem liniar

3.1. Metoda GAUSS – SEIDEL

3.2. Metoda JACOBI

3.3. Metode de relaxare

Bibliografie

INTRODUCERE

Metodele numerice și parțial metodele aproximative de rezolvare a problemelor științelor naturii și a tehnicii formează o ramură specială a matematicii, numita Analiză numerică.

În cadrul disciplinelor matematice, analiza numericăocupă un loc aparte, fiind de cele mai multe ori locul de întâlnire dintre matematică și modelarea matematică din diverse domenii.

Creștere continuă a diversității și complexității problemelor de calcul și modelare pe cre le-a pus activitatea de cercetare, ca domeniu de avangardă, în fața oamenilor de știință, a dus în cea de-a doua jumătate a secolului la o dezvoltare explozivă a metodelor și mijloacelor de calcul. Asistăm la o adevărată competiție între dezvoltarea tehnologică, având ca rezultat echipamentele de calcul (hardware) din ce în ce mai performante, și dezvoltarea fără precedent a componentelor logice (software), în particular a aplicațiilor de calcul numeric.

Sistemele de ecuații algebrice liniare intervin în aproape toate domeniile matematicii aplicate. În unele cazuri ele apar natural, din însăși formularea problemei. În multe cazuri, însă, sistemele de ecuații liniare rezultă ca urmare a aplicării unor metode numerice de rezolvare a problemei inițiale. Integrarea funcțiilor raționale, interpolarea cu funcții netede pe porțiuni si ajustarea metodelor prin regresie, precum și anumite tipuri de probleme asociate ecuațiilor sau sistemelori de ecuații diferențiale, sunt exemple tipice care conduc la sisteme de ecuații liniare. Fără a exagera, se poate considera că rezolvarea sistemelor de ecuații liniare joacă un rol central în cadrul analizei numerice. În mod corespunzător, ar trebui să fie puse la punct procedee numerice adecvate, atât pentru reducerea numărului mare de operații, cât și pentru reducerea erorilor de calcul care cresc cu dimensiunile sistemului de ecuații.

În cadrul capitolului rezervat sistmelor liniare sunt propuse spre studiere doar metodele Cramer și Gauss. Din acestea, metoda Cramer este destul de greoaie, se bazează pe un număr mare de calcule și nu este eficientă decât în cazul sistemelor cu un număr mic de ecuații.

Metodele numerice pe care le propune această lucrare reprezintă tehnici prin care probleme matematice complexe sunt reformulate astfel încât ă poată fi rezolvate numai cu operații aritmetice simple. Simplificarea operațiilor conduce în schimb la un număr destul de mare de calcule, ceea ce devine eficient doar cu ajutorul unor echipamente rapide de calcul, computerele. De aceea, această lucrare își propune să îmbine partea de matematică (prezentarea efectivă a metodelor matematice de rezolvare a sistemelor liniare, rezolvarea de sisteme liniare folosind aceste metode, studii de compatibilitate a sistemelor liniare etc.), cu o parte de informatică (prezentarea unor programe care să aplice aceste metode în rezolvarea sistemelor liniare).

Metodele de rezolvare a sistemelor liniare sunt grupate în metode directe și metode iterative. Folosirea uneia sau alteia dintre metode la rezolvarea unui sistem liniar Ax=b depinde de forma matricei A în primul rând și de factori ca : numărul de operații elementare efectuate (la metodele directe), verificarea condițiilor de convergență și evaluarea erorii (la metodele iterative).

Spre deosebire de alte capitole ale analizei numerice, în cazul rezolvării sistemelor liniare, metodele iterative concurează strîns cu metodele exacte în ceea ce privește realizarea unui optim al raportului timp – calculator (costul rezolvării problemei) și precizie.

Metodele exacte necesită multe operații aritmetice cu acumulări mari ale erorilor de rotunjire, cu timp mare de utilizare a calculatorului și necesități mari de memorie, făcând ca, în final, precizia scontată să nu se realizeze.

Metodele iterative sunt mai rapide decât cele exacte, necesită un număr mai mic de operații aritmetice, putând fi aplicate cu succes și în rezolvarea sistemelor de dimensiuni mari (n ≥60), când metodele exacte devin costisitoare.

CAPITOLUL I

Elemente teoretice privind compatibilitatea sistemelor liniare

Implementarea C++ unor algoritmi de rezolvare.

Atunci când suntem puși în fața unei probleme pentru care să elaborăm un algoritm de rezolvare a ei, de multe ori suntem în situația că ,, nu știm cum să începem,,. Conform cu Horowitz și Sahni (Fundamentals of computer algorithms, Springer Verlag, 1978), ,,actul de creare a unui algoritmeste o artă care nu va fi niciodată complet automatizat,,. Cu alte cuvinte, nu va exista niciodată un algoritm pentru scrierea algoritmilor!

Arta de a elabora algoritmi pentru diverse probleme ce se cer a fi rezolvate, se bazează pe experiența acumulată anterior prin elaborarea altor algoritmi în rezolvarea unor probleme asemănătoare.

Ca în orice altă activitate, există totuși câteva principii care ne pot ajuta în asemenea situații. Aceste principii (metode) generale, dacă sunt bine însușite, ne pot ajuta în nenumărate situații în care avem de rezolvat o problemă ca să elaborăm algoritmul pentru rezolvarea acelei probleme. Aceste metode sunt din ce în ce mai mult în atenția celor ce au de rezolvat probleme cu ajutorul calculatorului. Sunt bine cunoscute metodele generale de elaborare a algoritmilor ca: metoda Greedy, metoda Backtracking, metoda Programării dinamice, metoda Branch and Bound, metoda Divide et Impera, etc.

Unele dintre aceste metode sunt atât de generale încât mulți le folosesc frecvent ca reguli elementare de gândire (fără să cunoască fundamentarea lor teoretică ci bazându-se numai pe intuiții).

Majoritatea programatorilor care au depășit faza de inițiere în programare și au auzit de existența acestor metode generale de elaborare a algoritmilor sau ,,tehnici de programare,, le-au privit cu un optimism exagerat crezând că ele îi vor scăpa de chinurile elaborării algoritmilor pentru problemele dificile. Probabil că în scurt timp ei au fost dezamăgiți constatând că, deși aceste tehnici le ușurau munca, nu întotdeauna, pentru o problemă dată, este ușor de identificat și de aplicat ,,tehnica,, adecvată.

De altfel, arta de a crea un algoritm nu va putea fi niciodată automatizată (Horowitz și Sahni) și, prin urmare, ,,tehnicile de programare,, trebuie să fie privite doar ca niște metode generale de elaborare a algoritmilor aplicabile unor clase largi de probleme, astfel încât programatorul să nu mai fie nevoit să conceapă câte o metodă ad-hoc pentru fiecare problemă din clasa respectivă pe care o are de rezolvat. El nu trebuie decât să identifice clasa din care face parte acea problemă și să particularizeze acea metodă generală de elaborare a algoritmilor pentru problema concretă pe care o are de rezolvat.

În multe situații o problemă concretă poate fi încadrată în mai multe astfel de clase, adică i se pot aplica mai multe metode de elaborare a algoritmilor. Astfel, unei probleme i se poate aplica, de exemplu, atât metoda Greedy cât și metoda Backtracking.

De altfel, se știe că algoritmii pentru rezolvarea unei probleme nu sunt unici. Ajunși în acest punct ne punem întrebarea în ce claă să încadrăm problema dată pentru a o rezolva. Cei mai mulți aleg una din metodele cele mai ușoare de aplicat (cum ar fi, de exemplu, metoda Backtracking pentru care trecerea de la forma generală a metodei la o problemă concretă se face după un scenariu bine stabilit, această trecere făcându-se aproape mecanic, deci ,,aproape algoritmic,,). Dar alegerea metodei cel mai ușor de aplicat nu conduce întotdeauna la rezolvarea optimă a problemei date.

În multe cazuri, alegerea metodei cel mai ușor de aplicat conduce la algoritmi mari consumatori de timp sau de memorie pentru execuția lor. De aceea, este bine să alegem acea metodă de elaborare a algoritmilor care conduce, pentru problema dată, la un algoritm optim, chiar dacă aplicarea acelei metode la probleme concrete este mult mai dificilă (de exemplu, metoda programării dinamice este mult mai dificil de aplicat, trecerea de la forma generală a metodei la o problemă concretă necesitând multă ingeniozitate și o înțelegere profundă a metodei).

Tehnicile de programare s-au dezvoltat începând cu anii 1970 fiind studiate azi în multe școli și mai ales în instituțiile de învățământ superior, ele reprezentând un pas important pe care l-a înregistrat informatica în ultima vreme. Studierea și aplicarea lor în rezolvarea a cât mai multor probleme formează mintea tânărului programator, îi folosesc acestuia mult în viață. Din păcate, din diverse motive, acestui domeniu nu i se acordă toată atenția cuvenită.

S-ar putea ca mulți să fie dezamăgiți dacă, după toate acestea, le spunem că totuși există o anumită categorie de probleme pentru care tehnicile de programare cunoscute nu duc la nici un rezultat. Acestea sunt problemele în care ordinul de complexitate al algoritmului nu este polinomial (practica impunându-i ca acceptabili numai pe aceștia). O excepție în acest sens putem să spunem că o face metoda Greedy dar se știe că aplicând această metodă nu avem siguranța că găsim soluția optimă ci o soluție apropiată de aceasta. Deci, prin aplicarea metodei Greedy practic renunțăm la optimalitatea soluției. Totuși, ce e de făcut atunci când aplicarea unei tehnici de programare cunoscute conduce la un algoritm al cărui ordin de complexitate este exponențial? Tendința mondială din ultimii 10 – 15 ani este de a renunța la obținerea soluției optime pentru problemele practice și de a găsi algoritmi care conduc la o solutie apropiată de aceasta, dar pentru care să cunoaștem totuși marja de eroare. Acești algoritmi se găsesc în literatura de specialitate sub numele de algoritmi euristici.

De-a lungul timpului, oamenii de știință și-au dat seama din ce în ce mai mult că pentru a crea algoritmi performanți va trebui, ținând seama de esența divină a acestei lumi, să împrumutăm metodele care acționează deja în natură. În acest fel au apărut algoritmii neuronali și algoritmii genetici. Algoritmii genetici au apărut după anul 1990, deci putem să spunem că e una din noile tendințe din domeniul elaborării algoritmilor și sperăm să prezinte interes pentru toți cei ce doresc să studieze în domeniul elaborării algoritmilor.

În concluzie, programarea unui calculator nu înseamnă doar translatarea unor instrucțiuni într-un limbaj recunoscut de calculator. Cunoașterea mai multor limbaje de programare nu este suficientă pentru a ști să programezi. Există tendința ca pentru o problemă dată să elaborăm un algoritm (plecând de la prima idee care ne vine în minte) în mod direct.

Deși este natural, acest mod de a elabora algoritm nu este cel mai potrivit, mai ales atunci când avem de-a face cu probleme mari care necesită prelucrarea unei mari cantități de informații. Desigur, acești algoritmi s-ar putea să funcționeze bine pe probleme mici, dar pot fi catastrofali pe probleme care au date de intrare de dimensiuni mari. Dacă, în plus, acești algoritmi trebuie rulați de mai multe ori, atunci apare cu atât mai mult necesitatea găsirii unor metode mai bune, mai rapide, chiar dacă algoritmul devine mai complicat și mai greu de înțeles. În ciuda faptului că se pierd ore din timpul programatorului, se pot câștiga uneori chiar și numai secunde din timpul calculatorului, dar care să răsplătească efortul depus.

ALGORITMII ȘI EFICIENȚA LOR

Ce este un algoritm

Noțiunea de algoritm este o noțiune foarte veche. Cuvântul ,,algoritm,, este de origine arabă. El derivă din numele matematicianului Abu Ja`far Mohamed ibn Musâ al-Khowârizmî (autor persan, sec. VII – IX) care a scris o carte de matematiÎn ciuda faptului că se pierd ore din timpul programatorului, se pot câștiga uneori chiar și numai secunde din timpul calculatorului, dar care să răsplătească efortul depus.

ALGORITMII ȘI EFICIENȚA LOR

Ce este un algoritm

Noțiunea de algoritm este o noțiune foarte veche. Cuvântul ,,algoritm,, este de origine arabă. El derivă din numele matematicianului Abu Ja`far Mohamed ibn Musâ al-Khowârizmî (autor persan, sec. VII – IX) care a scris o carte de matematică celebră intitulată ,,Kitab al jabr w`ai-muquabala,, cunoscută în traducere latină ca ,, Algorithmi de numero indorum,, , iar apoi ca ,, Liber algorithmi,, , unde ,, algorithm,, provine de la ,, al- Khowârizmî,, , ceea ce literal înseamnă ,,din orașul Khowârizmî,, . Acest oraș se numește în prezent Khiva și el se află în Uzbekistan în Evul Mediu, atât al- Khowârizmî cât și alți matematicieni înțelegeau prin algoritm o regulă de bază căreia se efectuau calcule aritmetice. Astfel în timpul lui Adam Reise (sec. XVI), algoritmii foloseau la: înjumătățiri, dublări, înmilțiri de numere. În lucrările lui Stifer (,,Arithmetica integra,, , Nurnberg, 1544) ți Cardano (,,Ars magna sive de reguli algebraicis,, , Nurnberg 1545) apar și alți algoritmi. Chiar și Leibnitz vorbește de ,,algoritmi de înmulțire,, . Totuși, mult timp termenul de algoritm a rămas cu o întrebuințare destul de restrânsă, chiar și în domeniul matematicii.

Actul de naștere al teoriei funcțiilor recursive este semnat de Kronecker (în 1886) și Dedekind (în 1888) și conceptul de recursivitate devine insolubil legat de cel de algoritm. Teoria recursivității și a algoritmilor începe să se constituie ca atare abia în deceniul al treilea și al patrulea ale secolului nostru, prin lucrările lui Skolem, Ackeremann, Sudan, Godel, Church, Kleene, Turing, Peter și alții.

În ultima vreme, ca rezultat al conexiunii dintre algoritm și calculator, gândirea algoritmică a căpătat o transformare uimitoare dintr-un instrument matematic particular, într-o modalitate fundamentală de abordare a majorității problemelor din domenii care, aparent, nu au nimic în comun cu matematica. Pentru algoritmi nu există o definiție așa cum și în matematică nu există o definiție pentru noțiunea de mulțime. Noțiunea de algoritm este o noțiune primară. Astăzi, prin algoritm se înțelege o metodă generală de rezolvare a unui anumit tip de probleme, metodă ce se poate implementa pe calculator. Deci, un algoritm este compus dintr-o mulțime de pași, fiecare necesitând una sau mai multe operații. Prin urmare, în acest context, un algoritm este esența absolută a unei rutine. Operațiile, pentru a putea fi implementate pe calculator, trebuie să fie bine definite (ceea ce înseamnă că, cel puțin în principiu, o persoană dotată cu hârtie și creion trebuie să poată efectua orice pas într-un timp fini). Se consideră că un algoritm trebuie să se termine după un număr finit de operații într-un timp rezonabil (deci nu exagerat de lung, ca de exemplu, ani sau secole). De exemplu, aritmetica cu numere reale nu este efectiva deoarece unele numere sunt exprimabile prin secvențe infinite pe când, aritmetica cu numere întregi este efectivă.

Desigur, cel mai cunoscut algoritm este algoritmul lui Euclid pentru aflarea celui mai mare divizor comun a două numere întregi, dar mai sunt și alți algoritmi foarte cunoscuți (ca, de exemplu, metodele învățate în școală pentru a înmulți – împărți două numere, pentru a extrage rădăcina pătrată dintr-un număr ș.a.). Dar, ceea ce dă generalitate unui algoritm, este faptul că el poate opera nu numai cu numere. Astfel, este posibil chiar să construim anumite rețete culinare cu algoritmi, chiar dacă nu includ instrucțiuni ca: ,,adăugați sare după gust,, . Practic, nu există domeniu în care să nu putem să descoperim sectoare ce funcționează algoritmic.

Prin program vom înțelegeexprimarea unui algoritm într-un limbaj de programare cunoscut de un calculator.

Studiul algoritmilor cuprinde mai multe aspecte:

Elaborarea algoritmilor. Actul de creare a unui algoritm este o artă ce presupune creativitate umană bazată pe o serie de reguli cunoscute (tehnici de elaborare a algoritmilor, despre care vom discuta în această lucrare) și pe ingeniozitatea (intuiția, creativitatea) umană.

Repreyentarea algoritmilor. Algoritmii pot fi reprezentați prin mai multe metode: pseudocod, scheme logice, diagrame, etc.

Corectitudinea algoritmilor. După elaborarea și reprezentarea sa, un algoritm trebuie să fie validat (să i se verifice corectitudinea) pentru a ne asigura că el funcționează corect, indiferent în ce limbaj de programare va fi implementat.

Analiza algoritmilor. Pentru o anumită problemă pot fi elaborați mai mulți algoritmi. Pentru a putea decide care dintre ei este cel mai bun, este nevoie să definim un criteriu de apreciere a valorii unui algoritm. În general, acest criteriu se referă la timpul de calcul și la memoria necesară unui algoritm.

Elaborarea programelor. Un algoritm corect, de obicei, este implementat într-un limbaj de programare pentru a fi utilizat pe calculator. În practică, sunt cazuri când unii algoritmi sunt implementați în alt context (nu neapărat pe un calculator). Noi ne vom ocupa în mod special de algoritmii ce sunt implementați pe calculator.

Testarea programelor. Acest aspect constă din două faze: depanare și trasare.

Depanarea (debugging) este procesul ce constă în executarea programului pe date de test și corectarea eventualelor erori. Prin depanare, așa cum afirmă E. W. Dijksta, putem evidenția doar prezența erorilor dar nu și absența lor. În schimb, demonstrarea faptului că un program este corect este mult mai valoroasă decât o mie de teste deoarece prin demonstrație se poate garanta că programul funcționează corect în orice situație.

Trasarea (Profiling) este procesul de execuție a unui program corect pe diferite date de test (bine alese) cu scopul de a determina timpul de calcul și memoria necesară. Rezultatele obținute în această etapă se pot compara, după aceea, cu rezultatele obținute în etapa de analiză a algoritmului. Când avem de rezolvat o problemă, este important să ne decidem ce algoritm vom folosi pentru rezolvare. Răspunsul poate să depindă de mulți factori: dimensiunea exemplului de rezolvat, modul în care problema este prezentată, viteza și memoria disponibilă a echipamentului de calcul și așa mai departe.

Sisteme de ecuații liniare

,,De ce trebuie să învețe omul logică? Să știe să judece corect?

Nu, ci ca să învețe mai repede să judece corect,,.

Gr. C. Moisil

Scopul acestui capitol este de a studia metodele de rezolvare a sistemelor de n ecuații liniare cu n necunoscute:

unde coeficienții și termenii liberi sunt numere reale.

În tot ceea ce urmează vom folosi notațiil:

Matricea A, formată cu coeficienții sistemului, este o matrice pătrată de tipulnxn și se numește matrucea sistemului, x și b sunt vectori din se numește vectorul necunoscutelor, iar b vectorul termenilor liberi. Cu aceste notații sistemul(I) se scrie sub forma matriceală

Ax=b

În continuare, vom presupune întodeauna că matricea sistemului este nesingulară. Prin urmare, sistemul are soluție unică.

Observație. Dacă matricea A are elemente numere complexe și atunci sistemul complex Ax=b este echivalent cu un sistem real de ordinul 2n.

Într-adevăr, dacă , sistemul (I) este echivalent cu

Prin egalarea părților reale și imaginare din ambii membrii se obține sistemul

care poate fi scris sub formă matriceală astfel:

Acesta este un sistem real de ordinul 2n echivalent cu sistemul Ax=b. De aceea putem presupune în continuare că sistemele studiate sunt reale.

CAPITOLUL II

Metode directe de rezolvare a sistemelor liniare:

2.1. Metoda Cramer.

Metoda este indicată pentru

Considerăm sistemul:

A•X=B

cu det(A) 0 caz în care soluția este unică, deci sistemul este compatibil determinat.

Dacă det(A) (inversa matricei), care are propietatea:

(matricea unitate)

Atunci, înmulțind ecuația la stânga cu se obține, pe rând

adică soluția sistemului este:

Dar

unde A* este matricea formată cu complemenți algebrici ai elementelor matriceiA. Rezultă că:

adică

undesunt determinați obținuți prin înlocuirea coloanei i cu coloana termenilor liberi.

Deci

Exemplu: Să se rezolve sistemul

Atunci soluția sistemului este:

Programul C++ care implementează această metodă este:

2.2. Metoda Gauss a eliminării succesive

Metoda lui Gauss este una din metodele tradiționale de rezolvare a sistemelor de ecuații liniare. Ideea de bază a metodei constă în aducerea sistemului, prin transformări elementare, la o formă echivalentă, având matrice superior triunghiulară, urmată de rezolvarea sistemului rezultat prin procedee recurente specifice, foarte eficiente. Transformarea sistemului este echivalentă cu eliminarea succesivă a necunoscutelor din ecuații, și de aceea se numește faza eliminării.

La sfârșitul procedeului putem obține:

a. Un sistem triunghiular în care ultima ecuație comține numai necunoscuta atunci sistemul este compatibil determinat.

Rezolvarea sistemului cu matricea triunghiulară constă în explicarea necunoscutelor și substituția lor în ecuațiile sistemului în ordine inversă, fiind denumită din acest motiv faza substituției inverse.

b. Un sistem în care unde k<n; atunci sistemul este compatibil nedeterminat.

c. Un sistem în care cel puțin o ecuație este de forma ; atunci sistemul este incoruptibil.

Să considerăm acum cazul general, al unui sistem de n ecuații cu n necunoscute:

Fie sistemul (S) compatibil determinat (are o singură soluție):

I. Faza eliminării

Vom transforma, succesiv, sistemul (S) în sisteme echivalente, eliminând câte o necunoscută, folosind următorii pași:

Pasul 1. vom elimina necunoscuta X1 din ultimele n-1 ecuații. Pentru aceasta împărțim ecuația (E1) la a11 (presupus diferit de zero; astfel schimbăm ecuația E1 cu o alta care are a11 diferit de zero și renumerotăm ecuațiile), apoi din ecuația (E2) vom scădea ecuația (E1) înmulțită cu numărul a21; din ecuația (E3) vom scădea ecuația (E1) înmulțită cu numărul a31 etc. În general din ecuația (Ei) vom scădea ecuația (E1) înmulțită mi=ail (i=2,3,…,n).

Astfel sistemul (S) a căpătat forma echivalentă (S1):

unde am notat:

La pasul 1 elementul a11 a jucat un rol important, de aceea el se numește pivot, iar linia 1 se numește linie pivot..

La pasul k, vom elimina Xk din ultimele n-k ecuații ți sistemul este adus la forma:

Noile elemente ale liniei pivot k având expresiile:

iar noile elemente ale liniilor situate sub linia pivot fiind:

Se observă că la pasulk se modifică doar elementele delimitate de linia și coloana k, celelalte elemente rămânând neschimbate față de pasul anterior.

În final, la pasul n se realizează doar împărțirea ultimei ecuații la ultimul element pivot,

și sistemul primește forma:

sau matricea ,unde:

Așa cum se vede, matricea este superior triunghiulară, iar sistemul este echivalent cu cel inițial, deci are aceeași soluție

II. Faza substituției

Vom considera acum procesul invers, de reyolvare a sistemului. Din ultima ecuație a sistemului (Sn) obținem:

și apoi respectiv:

Exemplu:

Eliminând x1 din ecuațiile 2,3 și 4, obținem:

împărțim a doua ecuație la -5 și apoi eliminăm x2 din ecuațiile 3 și 4:

împărțim a treia ecuație la 3 și eliminăm x3 din ultima ecuație:

împărțim a patra ecuație la

Folosind substituția inversă, obținem:

deci soluția sistemului este (1,2,-1,-2).

Observația 1. metoda de eliminare a lui Gauss permite și calculul determinantei matricei sistemului. Se observă că determinamtul matricei triunghiulare este egal cu I. Având însă în vedere că împărțirea liniilor pivot succesive la elementele pivot corespunzătoare, conduce la o matrice având determinantul egal cu determinantul matricei inițiale A împărțit la produsul elementelor pivot, avem:

De aici rezultă că determinantul matricei sistemului este dat de produsul elementelor pivot.

Observația 2. În procesuldirect putem omite scrierea necunoscutelor lucrând cu matricea extinsă

a sistemului. După primul pas aceasta devine:

În implementarea algoritmului eliminării gaussiene, la fiecare pas k al fazei eliminării se efectuează împărțirea liniei pivot k la elementul diagonal. În practică este posibil ca acesta să fie zero, situație în care este imposibilă continuarea algoritmului. Mai mult, se poate arăta că erorile de rotunjire ăn calculele elementelor matricei sunt cu atât mai mici cu cât elementul pivot este mai mare în valoare absolută. În spiritul celor arătate, se efectuează pivotarea parțială pe coloane, ceea ce, pentru pasul k al eliminării, revine la a găsi elementul maxim în valoarea absolută al matricei situat pe coloana k și liniile (pe și sub diagonala principală). Dacă acest element este, de exemplu, alk, atunci, pentru a-l pune pe diagonala principală, trebuie interschimbate liniile k și l.

Există metode de pivotare mai performante, cum ar fi metoda elementului principal în care elementul pivot se caută pe toate liniile și coloanele matricei , pe care nu s-a realizat pivotarea până la acel pas. Erorile de rotunjire sunt astfel reduse și mai mult, în schimb codificarea acestor algoritmi de pivotare este mai laborioasă.

Exemplu: Folosind metoda eliminării gaussiene, să se rezolve următorul sistem de ecuații:

Rezultă că:

Pentru a observa influența alegerii pivotului asupra preciziei rezultatelor, refacem calculele de mai sus fără a mai schimba liniile 2 și 3 pentru a aduce valoarea 1.75 pe poziția pivotului în etapa a doua. Se va obține:

și soluțiile

Se observă apariția unor valori diferite, comparativ cu valorile obținute în cazul anterior.

În continuare prezentăm un program C++ care realizează eliminarea gaussiană cu pivotare parțială pe coloane:

2.3. Metoda GAUSS JORDAN

Metoda Gauss – Jordan reprezintă o variantă a metodei lui Gauss. Spre deosebire de metoda lui Gauss, în care matricea sistemului este adusă, prin transformări elementare, la forma superior triunghiulară, în metoda Gauss – Jordan matricea sistemului este transformată în matricea unitate. Prin aceasta, deși faza eliminării este mai laborioasă, faza substituției inverse este eliminată.

În urma pasului k de eliminare este eliminată necunoscuta xk din toate ecuațiile sistemului, cu excepția pivot k și sistemul este adus la forma:

sau, în forma matriceală:

Noile elemente ale liniei pivot k sunt:

iar noile elemente ale liniilor nepivot sunt:

Se observă că la pasul k se modifică numai elemetele matricei sistemului situate în dreapta coloanei k, ce devine identică cu coloana corespunzătoare din matricea unitate. La fiecare pas se modifică, în schimb, toate elementele matricei termenilor liberi.

În final, după pasul n, sistemul are forma:

unde In reprezintă matricea unitate de ordinul n. Este evident că nu este necesară, ca la metoda lui Gauss, o fază a substituției inverse, iar soluția sistemului este:

Ca și în cazul metodei lui Gauss, determinantul matricei A se calculează cu formula:

Exemplu: Să se rezolve, folosind metoda eliminării complete, următorul sistem de ecuații:

Pentru simplitate vom folosi matricea extinsă și vom marca pivotul folosit la pasul următor:

Deci soluția sistemului este

Programul care realizează acest lucru este:

CAPITOLUL III

Metode iterative de rezolvare a sistemelor liniare:

3.1. Metoda Jacobi

Metodele directe (metoda eliminării gaussiene, metoda factorizării etc.) permit determinarea soluției unui sistem de ecuații liniare de ordinul n într-un număr finit de pași, prin efectuarea unui număr de operații elementare de ordinul n3. Odată cu creșterea ordinului sistemului, erorile e rotunjire se pot acumuladramatic, ducând la erori relative apreciabile ale soluției. Pentru minimizarea acestor erori se impune, în general, pivotarea, adică reordonarea ecuațiilor după fiecare etapă de calcul pentru a avea elemente maximale pe diagonala principală a matricei sistemului. Această tehnică implică un efort de calcul suplimentar, care poate fi semnificativ în cazul sistemelor cu un număr mare de ecuații.

Metodele iterative permit, în principiu, determinarea soluției unui sistem de ecuații liniare pe baza unui proces iterativ, pornind de la o aproximație inițială a soluției. Dacă sistemul este bine condiționat numeric (matricea lui satisface anumite condiții), procesul iterativ converge către soluția exactă. Practic, procesul este întrerupt după un număr finit de pași, furnizând soluția cu o anumită precizie, afectată de erori de rotunjire, mai mici decât în cazul metodelor exacte, și de erori de trunchiere. Unul din avantajele importante ale metodelor iterative constă in faptul că erorile de rotunjire, și chiar cele de trunchiere, pot fi practic eliminate. De altfel, unele metode iterative pot fi utilizate pentru îmbunătățirea soluției obținute prin alte metode. Dacă se cunoaște o aproximație inițială apropiată de soluția exactă a sistemului, convergența metodelor iterative este rapidă, necesitând, pentru aceeași precizie a soluției, un număr de operații mai mic decât metodele directe. În plus, metodele iterative se disting prin marea simplitate a programării lor.

Una din cele mai vechi și cunoscute metode iterative pentru rezolvarea sistemelor de ecuații liniare este metoda Jacobi.

Pentru sistemul:

Ax=b,

Cu A nesingulară, rezolvăm prima ecuație în raport cu x1, a doua în raport cu x2 etc. și obținem:

Dacă notăm:

numită matricea Jacobi asociată lui A, și

atunci putem scrie sistemul sub forma matriceală:

Rezolvăm acest sistem, numit sistem redus, prin metoda aproximațiilor succesive. Ca aproximație de ordin zero, de cele mai multe ori, se ia vectorul nul, și construim aproximația de ordin k pe baza aproximației de ordin k-l, utilizând formula de recurență:

atunci aceasta este soluția sistemului inițial.

În practică, este mult mai comod să folosim, în locul relației matriceale, o relație discretă pe componente:

Introducând corecțiile componentelor soluției:

procesul iterativ trebuie continuat, în principiu, până când eroarea relativ maximă a componentelor soluției devine mai mică decât o eroare maximă admisibilă, ε, adică:

Dăm, fără demonstrație, o condiție suficientă pentru convergența procesului iterativ, sub forma următoarei teoreme:

Teoremă: dacă pentru sistemul redus x=j•x+t este valabilă cel puțin una dintre următoarele condiții:

atunci procesul iterativ converge către soluția unică a sistemului, indiferent de alegerea aproximației inițiale.

Corolar: pentru un sistem liniar, procesul iterativ este convergent dacă au loc inegalitățile:

adică, dacă pe fiecare linie a sistemului valoarea absolută a coeficientului diagonal este mai mare decât suma valorilor absolute ale coeficienților extradiagonali.

În practică, pentru ca metoda Jacobi să fie convergentă, nu este neapărat necesară îndeplinirea acestor condiții, ci, în multe situații este suficient ca matricea sistemului să fie diagonal dominantă, adică:

Exemplu: Să se rezolve sistemul:

Pentru că sistemul nu este diagonal dominant, schimbăm poziția ultimelor două ecuații:

Rezolvăm fiecare ecuație în raport cu necunoscuta respectivă:

Alegem soluția inițială: și, după prima aproximare, obținem:

După a doua aproximare, avem:

etc. Din valorile numerice, putem alcătui următorul tabel:

Se observă că după a șaptea iterație soluțiile nu se mai schimbă, deci putem trage concluzia că soluțiile sistemului sunt:

Programul care implementează acest algoritm este următorul:

3.2. Metoda GAUSS – SEIDEL

Metoda Gauss – Seidel reprezintă o variantă superioară a metodei Jacobi, caracterizată prin viteză de convergență sporită și necesar de memorie redus. Idea de bază a metodei Gauss – Seidel constă în utilizarea în procesul iterativ Jacobi a celor mai recente componente ale soluției sistemului, pe măsură ce acestea sunt calculate.

În acest caz, trecerea de la iterația k-l la iterația k nu se mai face simultan pentru toate ecuațiile, ci prin utilizarea soluțiilor obținute la ecuațiile precedente.

Pentru sistemul liniar, iterația k se realizează cu formulele:

Criteriul de convergență pentru metoda Gauss – Seidel poate fi exprimat, ca și la metoda Jacobi, cerând ca eroarea relativă maximă a componentelor soluției să devină mai mică decât o toleranță prescrisa, , adică:

În cazul în care există componente nule, în locul erorii relative trebuie utilizată eroarea absolută

Teorema de convergență dată în secțiunea anterioară, pentru metoda Jacobi, își păstrează valabilitatea și în cazul metodei Gauss – Seisel.

În general, metoda Gauss – Seidel, sub forma prezentată, nu converge deloc. Realizând însă, așa cum se va arăta în continuare, anumite transformări asupra sistemului inițial, convergența algoritmului este garantată.

Definiție: Un sistem liniar Ax=b se numește normal dacă matricea coeficienților este simetrică și pozitiv definită.

Teorema 1: Dacă ambii membri ai sistemului liniar Ax=b, având matricea A nesingulară, sunt înmulțiți la stânga cu atunci sistemul rezultat, este normal.

Teorema 2: Procesul iterativ Gauss – Seidel convergeîntodeauna pentru un sistem normal, indiferent de alegerea aproximației inițiale.

Putem folosi însă și teorema lui Reich: Dacă A este o matrice simetrică cu diagonala principală pozitivă, atunci metoda Gauss – Seidel converge dacă și numai dacă matricea A este pozitiv definită.

Exemplu: Vom folosi același exemplu ca și la metoda Jacobi, pentru a arăta rapiditatea convergenței soluției numerice:

Din valorile numerice, putem alcătui următorul tabel:

Se observă că după a cincea iterație soluțiile nu se mai schimbă, deci putem trage concluzia că soluțiile sistemului sunt:

Programul C++ care implementrază această metodă este:

3.3. Metode de relaxare.

Aceste metode au drept scop înbunătățirea vizitei de convergență a soluției unui sistem de ecuații liniare.

Metoda lui SOUTHWELL (Metoda de relaxare cu pașii separați)

Prin urmare, dacă la pasul k componenta l a șirului era maximă în modul, la pasul următor, k+l, ea se anulează.

Ca o notație similară cu (*), putem scrie și variațiile componentelor șirului la pasul k+l:

Procedeul se repetă. Ne oprim atunci când unde ε este o eroare maximă admisibilă dată.

O condiție suficientă pentru ca șirul să fie convergent, oricare ar fi către soluția sistemului este ca matricea să fie strict diagonal dominantă (la fel ca și pentru metodele Gauss – Seidel și Jacobi)

Programul C++ care implementează această metodă este:

Metoda relaxării succesive

Metoda relaxării succesive este o variantă modificată a metodei iterative Gauss – Seidel care urmărește accelerarea suplimentară a convergenței procesului iterativ. În acest scop, vom porni cu formulele de iterație Gauss – Seidel scrise sub forma echivalenta:

unde

Se consideră descompunerea matricei sistemului:

A=L+D+U,

unde L este inferior triunghiulară cu elementele:

U este superior triunghiulară cu elementele:

Iar D are pe diagonală elementele matricei A și în rest zero.

Folosind această descompunere, relațiile (**) devin:

Atunci când șirul tinde către soluția sistemului dat, șirul tinde către zero.

Vom introduce un parametru de accelerare și vom modifica relația (**) în felul următor.

Parametru ε se alege în așa fel încât viteza de convergență a metodei să crească.

Cu această relație se obține șirul iterativ:

sau

Pentru ω=1 se obține metoda Gauss – Seidel. Dacă avem o subrelaxare, care se folosește în special atunci când metoda Gauss – Seidel nu este convergentă. Pentru avem o suprarelaxare, folosită în special atunci când vrem să înbunătățim viteza de convergență a metodei Gauss – Seidel; în practică se folosește în special această variantă, de aceea metoda de față se numește de obicei metoda suprarelaxării succesive.

Problema determinării valorii optime a parametrului de accelerare ω astfel încât să avem efectiv o accelerare a convergenței este dificilă.

S-a constatat în practică faptul că, dacă n este mic (2,3,4,5,….,19), valoarea optimă a parametrului de accelerare este apropiată de 1 (1,1.2,2), deci diferența față de metoda Gauss – Seidel nu este importantă, de atunci când n este mare (20,21….), valoarea optimă a lui ω se plasează de regulă în intervalul 1.7-1,9 și avantajul este mare.

Exemplu: Să se găsească primele trei iterații, folosind metoda relaxării succesive cu ω=0,5, pentru sistemul:

Programul C++ corespunzător acestei metode este:

Metoda relaxării simultane

Această metodă înbunătățește viteza de convergență a metodei Jacobi.

Scriem relația de definiție a șirului Jacobi sub forma:

unde:

Să introducem, ca și la metoda precedentă, un parametru de accelerare ω, (ω>0, ω≠1) astfel încât să fie ăndeplinită relația:

Obținem atunci șirul:

sau

În relațiile precedente, pentru se obțin rezultatele din metoda Jacobi.

Se demonstrează că metoda relaxării simultane este convergentă dacă și numai dacă:

unde este raza spectrală a matricei

Având în vedere că raza spectrală este greu de aflat, în aplicații se folosește pentru ω o valoare satisfăcând condiția:

Valoarea optimă a parametrului ω este: unde sunt valorile proprii maximă și minimă a matricei

Eroarea este majorată din inegalități:

Programul C++ pentru această metodă este:

BIBLIOGRAFIE

Marius Burtea, Georgeta Burtea – Matematică – clasa a XI-a Elemente de algebră liniară, Eelemente de analiză matematică. Exerciții și probleme, Editura Carminis, Pitești, 2006.

Marius Burtea, Georgeta Burtea – Matematică – clasa a XI-a Elemente de algebră liniară și geometrie analitică, Editura Carminis, Pitești, 2001.

Marius Burtea, Georgeta Burtea – Matematică Manual pentru clasa a XI-a (M1) Editura Carminis, Pitești, 2001.

Luminița Duță, Nicolae Istrate, Adriana Alexandru, Gabriel Gorghiu – Programarea calculatoarelor în limbajul C++, Editura Zoom, 2003.

Luminița Duță, Nicolae Istrate – Programarea calculatoarelor în limbajul C++, Editura Zoom, 2003.

Gh. Marinescu – Analiză numerică, Editura Didactică și Pedagogică, 1978.

C. Mortici – Bazele matematicii, Editura Minus, 2008.

Ileana Popescu, Irina Rizzoli, Cristina Ștefan – Caiet de laborator de analiză numerică, București, 1981.

Petre Stavre, Marius Marinel Stănescu – rezolvarea algoritmică a sistemelor de ecuații liniare. Aplicații, Editura Matrix Rom, București, 2007.

Nicolae Dăneț – Analiză numerică cu aplicații rezolvate în Mathcad, Editura Matrix Rom, București, 2002.

Stelian Niculescu, Sorin Eftene – Algoritmi și limbaje de programare, Editura Didactică și Pedagogică, București, 1995.

BIBLIOGRAFIE

Marius Burtea, Georgeta Burtea – Matematică – clasa a XI-a Elemente de algebră liniară, Eelemente de analiză matematică. Exerciții și probleme, Editura Carminis, Pitești, 2006.

Marius Burtea, Georgeta Burtea – Matematică – clasa a XI-a Elemente de algebră liniară și geometrie analitică, Editura Carminis, Pitești, 2001.

Marius Burtea, Georgeta Burtea – Matematică Manual pentru clasa a XI-a (M1) Editura Carminis, Pitești, 2001.

Luminița Duță, Nicolae Istrate, Adriana Alexandru, Gabriel Gorghiu – Programarea calculatoarelor în limbajul C++, Editura Zoom, 2003.

Luminița Duță, Nicolae Istrate – Programarea calculatoarelor în limbajul C++, Editura Zoom, 2003.

Gh. Marinescu – Analiză numerică, Editura Didactică și Pedagogică, 1978.

C. Mortici – Bazele matematicii, Editura Minus, 2008.

Ileana Popescu, Irina Rizzoli, Cristina Ștefan – Caiet de laborator de analiză numerică, București, 1981.

Petre Stavre, Marius Marinel Stănescu – rezolvarea algoritmică a sistemelor de ecuații liniare. Aplicații, Editura Matrix Rom, București, 2007.

Nicolae Dăneț – Analiză numerică cu aplicații rezolvate în Mathcad, Editura Matrix Rom, București, 2002.

Stelian Niculescu, Sorin Eftene – Algoritmi și limbaje de programare, Editura Didactică și Pedagogică, București, 1995.