Metode numerice

Mihai Rebican, Gabriela Ciuprina, Daniel Ioan

Metode numerice ingineria n electric a Indrumar de laborator pentru studentii facultii de Inginerie at Electric a

2011

Cuprins0 Preliminarii asupra Laboratorului de Metode Numerice 0.1 Informatii utile . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 0.1.1 0.1.2 0.1.3 0.1.4 0.1.5 0.2 0.3 0.4 Lista de lucrri . . . . . . . . . . . . . . . . . . . . . . . . . . . . . a Calendar . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Regulament . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Modul de notare al laboratorului . . . . . . . . . . . . . . . . . . . Calculul notei nale la disciplina Metode Numerice . . . . . . . . . 1 1 1 2 2 3 4 4 5 6 6

Modul de desfurare a unei edinte de seminar sau laborator . . . . . . . as s Programe demonstrative . . . . . . . . . . . . . . . . . . . . . . . . . . . . Implementare in C . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 0.4.1 0.4.2 0.4.3 Exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Vectori . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 Matrice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 15

1 Implementarea structurilor de date i a algoritmilor numerici s 1.1 1.2

Caracterizarea lucrrii . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 a Descrierea pseudolimbajului . . . . . . . . . . . . . . . . . . . . . . . . . . 16 1.2.1 1.2.2 Structuri de date . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 Structuri de control . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

1.3 1.4

Tipuri abstracte de date . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 Complexitatea algoritmilor . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 i

ii

CUPRINS

1.5 1.6 1.7

Chestiuni de studiat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 Modul de lucru . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 Exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 1.7.1 1.7.2 Exemple rezolvate . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 Exemple propuse . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

1.8 Intrebri i probleme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 a s 2 Erori rezolvarea problemelor numerice n 2.1 2.2 53

Caracterizarea lucrrii . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 a Principiul lucrrii . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 a 2.2.1 2.2.2 2.2.3 Erori de rotunjire . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 Erori inerente . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 Erori de trunchiere . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

2.3 2.4

Chestiuni de studiat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 Modul de lucru . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 2.4.1 2.4.2 2.4.3 2.4.4 Determinarea erorii relative de rotunjire a sistemului de calcul . . . 60 Analiza propagrii erorilor inerente . . . . . . . . . . . . . . . . . . 60 a Analiza erorii de trunchiere . . . . . . . . . . . . . . . . . . . . . . 61 Implementarea unor algoritmi cu controlul erorii . . . . . . . . . . . 63

2.5

Exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 2.5.1 2.5.2 Exemple rezolvate . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 Exemple propuse . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

2.6 Intrebri i probleme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 a s

3 Rezolvarea sistemelor de ecuatii liniare prin metoda Gauss. Strategii de pivotare rez n 3.1 Metoda Gauss fr pivotare . . . . . . . . . . . . . . . . . . . . . . . . . . 69 aa 3.1.1 3.1.2 Caracterizarea metodei . . . . . . . . . . . . . . . . . . . . . . . . . 69 Principiul metodei . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 LMN, Draft din 30 septembrie 2011

CUPRINS

iii

3.1.3 3.1.4 3.1.5 3.2

Pseudocodul algoritmului Gauss fr pivotare . . . . . . . . . . . . 71 aa Analiza complexitii . . . . . . . . . . . . . . . . . . . . . . . . . . 72 at Analiza erorilor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73

Strategii de pivotare rezolvarea sistemelor algebrice liniare . . . . . . . . 74 n 3.2.1 3.2.2 3.2.3 3.2.4 3.2.5 Caracterizarea metodei . . . . . . . . . . . . . . . . . . . . . . . . . 74 Principiul metodei . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 Pseudocodul algoritmului Gauss cu pivotare partial . . . . . . . . 75 a Analiza complexitii . . . . . . . . . . . . . . . . . . . . . . . . . . 76 at Analiza erorilor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77

3.3 3.4

Chestiuni de studiat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 Modul de lucru . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 3.4.1 3.4.2 3.4.3 3.4.4 Rezolvarea unor sisteme algebrice liniare . . . . . . . . . . . . . . . 78 Analiza experimental a algoritmului . . . . . . . . . . . . . . . . . 78 a Implementarea algoritmilor ntr-un limbaj de programare . . . . . 79

Cutare de informatii . . . . . . . . . . . . . . . . . . . . . . . . . . 80 a

3.5


3.6 Intrebri . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 a 8 Metode iterative de rezolvare a sistemelor algebrice liniare 8.1 8.2 8.3 8.4 8.5 8.6 93

Caracterizarea metodelor . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 Principiul metodei . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 Pseudocodul algoritmilor . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 Analiza algoritmilor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99 Chestiuni de studiat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 Mod de lucru . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 8.6.1 Rezolvarea unor sisteme de ecuatii liniare prin metodele Jacobi/Gauss-Seidel100 Document disponibil la http://mn.lmn.pub.ro

iv

CUPRINS

8.6.2 8.6.3 8.6.4 8.7

Analiza experimental a algoritmilor . . . . . . . . . . . . . . . . . 102 a Implementarea algoritmilor . . . . . . . . . . . . . . . . . . . . . . 103 Cutare de informatii pe Internet . . . . . . . . . . . . . . . . . . . 103 a


8.8 Intrebri i probleme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 a s 10 Analiza numeric a circuitelor electrice liniare regim permanent a n 117

10.1 Caracterizarea lucrrii . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 a 10.2 Principiul metodei . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118 10.3 Pseudocodul metodei . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120 10.4 Analiza algoritmilor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123 10.5 Chestiuni de studiat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124 10.6 Modul de lucru . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124 10.6.1 Analiza numeric a unui circuit rezistiv liniar . . . . . . . . . . . . 125 a 10.6.2 Analiza unui circuit de curent alternativ . . . . . . . . . . . . . . . 126 10.6.3 Implementarea algoritmilor . . . . . . . . . . . . . . . . . . . . . . 127 10.6.4 Cutarea de informatii pe Internet . . . . . . . . . . . . . . . . . . 127 a 10.7 Exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127 10.7.1 Exemple rezolvate . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127 10.7.2 Exemple propuse . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131 10.8 Intrebri i probleme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131 a s 11 Interpolarea polinomial a functiilor reale a 135

11.1 Caracterizarea metodei . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135 11.2 Principiul metodei . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136 11.3 Pseudocodul algoritmilor . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141 LMN, Draft din 30 septembrie 2011

CUPRINS

v

11.4 Analiza complexitii algoritmilor . . . . . . . . . . . . . . . . . . . . . . . 145 at 11.4.1 Efort de calcul . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145

11.4.2 Necesar de memorie . . . . . . . . . . . . . . . . . . . . . . . . . . . 145 11.5 Eroarea de interpolare . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146 11.6 Chestiuni de studiat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148 11.7 Mod de lucru . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149 11.7.1 Interpolarea polinomial a functiilor pe retele uniforme/Cebsev . . 149 a 11.7.2 Analiza experimental a erorilor de interpolare . . . . . . . . . . . . 150 a 11.7.3 Analiza experimental a timpului de calcul necesar interpolrii polinomiale150 a a 11.7.4 Implementarea unor algoritmi de interpolare polinomial . . . . . . 150 a 11.7.5 Cutare de informatii pe Internet . . . . . . . . . . . . . . . . . . . 151 a 11.8 Exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151 11.8.1 Exemple rezolvate . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151 11.8.2 Exemple propuse . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159 11.9 Intrebri i probleme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160 a s 14 Derivarea numeric a functiilor reale a 163

14.1 Caracterizarea metodelor de derivare numeric . . . . . . . . . . . . . . . . 163 a 14.2 Principiile metodelor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163 14.3 Analiza algoritmilor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166 14.4 Pseudocodul metodei . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167 14.5 Chestiuni de studiat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168 14.6 Modul de lucru . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169 14.6.1 Evaluarea numeric a primei derivate . . . . . . . . . . . . . . . . . 169 a 14.6.2 Analiza experimental a erorii de derivare numeric . . . . . . . . . 170 a a 14.6.3 Analiza derivrii numerice de ordin superior . . . . . . . . . . . . . 170 a 14.6.4 Implementarea algoritmului . . . . . . . . . . . . . . . . . . . . . . 171 14.6.5 Cutare de informatii pe Internet . . . . . . . . . . . . . . . . . . . 171 a Document disponibil la http://mn.lmn.pub.ro

vi

CUPRINS

14.7 Exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171 14.7.1 Exemple rezolvate . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171 14.7.2 Exemple propuse . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174 14.8 Probleme i s ntrebri . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174 a 15 Integrarea numeric a functiilor reale a 177

15.1 Caracterizarea metodelor de integrare numeric . . . . . . . . . . . . . . . 177 a 15.2 Principiul metodei . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177 15.3 Pseudocodul algoritmilor . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180 15.4 Analiza algoritmilor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181 15.5 Chestiuni de studiat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182 15.6 Modul de lucru . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182 15.6.1 Calculul integralei unor functii elementare . . . . . . . . . . . . . . 183 15.6.2 Analiza erorii la integrarea numeric . . . . . . . . . . . . . . . . . 183 a 15.6.3 Implementarea algoritmului . . . . . . . . . . . . . . . . . . . . . . 184 15.6.4 Cutare de informatii pe Internet . . . . . . . . . . . . . . . . . . . 184 a 15.7 Exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184 15.7.1 Exemple rezolvate . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184 15.7.2 Exemple propuse . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189 15.8 Probleme i s ntrebri . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191 a 16 Rezolvarea numeric prin metode iterative a ecuatiilor neliniare a 195

16.1 Caracterizarea lucrrii . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195 a 16.2 Principiul lucrrii . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195 a 16.3 Pseudocodul algoritmilor . . . . . . . . . . . . . . . . . . . . . . . . . . . . 198 16.4 Analiza algoritmilor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201 16.5 Chestiuni de studiat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203 16.6 Modul de lucru . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203 LMN, Draft din 30 septembrie 2011

CUPRINS

vii

16.6.1 Rezolvarea unor ecuatii neliniare prin diferite metode iterative . . . 203

16.6.2 Analiza experimental a erorilor i a timpului de calcul la rezolvarea prin metode it a s 16.6.3 Implementarea algoritmilor de rezolvare iterativ a ecuatiilor neliniare205 a 16.6.4 Cutare de informatii pe Internet . . . . . . . . . . . . . . . . . . . 205 a 16.7 Exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 206 16.7.1 Exemple rezolvate . . . . . . . . . . . . . . . . . . . . . . . . . . . . 206 16.7.2 Exemple propuse . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212 16.8 Intrebri i probleme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213 a s

18 Rezolvarea ecuatiilor diferentiale ordinare cu conditii initiale prin metoda Euler215 18.1 Caracterizarea metodei . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215 18.2 Principiul metodei . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215 18.3 Pseudocodul metodei . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 216 18.4 Analiza algoritmului . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 219 18.5 Chestiuni de studiat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 220 18.6 Mod de lucru . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 220 18.6.1 Rezolvarea unor ecuatii diferentiale de ordin 1 . . . . . . . . . . . . 221

18.6.2 Analiza experimental a erorilor i a timpului de calcul functie de pasul de integr a s n

18.6.3 Rezolvarea unei ecuatii diferentiale caracteristice unui circuit electric de ordinul I22 18.6.4 Implementarea algoritmului ntr-un limbaj de programare i testarea rutinei.224 s 18.6.5 Cutare de informatii pe Internet . . . . . . . . . . . . . . . . . . . 224 a 18.7 Exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224 18.7.1 Exemple rezolvate . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224 18.7.2 Exemple propuse . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224 18.8 Probleme i s ntrebri . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224 a 19 Analiza numeric a circuitelor electrice regim tranzitoriu a n Bibliograe i webograe s Document disponibil la http://mn.lmn.pub.ro 227 228

Capitolul 0 Preliminarii asupra Laboratorului de Metode Numerice

0.1

Informatii utile

0.1.1

Lista de lucrri a

Index L1 L2 L3,4 L8 L10 L11 L14 L15 L16 L18 L20

Nume lucrare Algoritmi si structuri de date Erori in calculele numericei Metoda Gauss - fr i cu pivotare aas Metode iterative pentru rezolvarea sistemelor liniare Rezolvarea circuitelor rezistive liniare Interpolarea numeric a functiilor a Derivarea numeric a functiilor a Integrarea numeric a functiilor a Rezolvarea ecuatiilor neliniare Rezolvarea ecuatiilor diferentiale Rezolvarea circuitelor regim tranzitoriu n 1

2

Capitolul 0. Preliminarii asupra Laboratorului de Metode Numerice

0.1.2

CalendarTema Prezentarea laboratorului L1 + L2 - seminar L1 + L2 - laborator L3,4 + L8 - seminar L3,4 + L8 - laborator L10 seminar T1 - Test de aplicatii numerice - partea I L11 - seminar L11 - laborator L14 + L15 - seminar L14 + L15 - laborator L16 + L18 - seminar L16 + L18 - laborator T2 - Test de aplicatii numerice - partea II i test de implementare s

Sptmna a a a 1 2 3 4 4 6 7 8 9 10 11 12 13 14

0.1.3

Regulament

Un student poate intra examen doar dac particip la minim 5 edinte de seminar n a a s (din maxim 6), 4 edinte de laborator (din maxim 5) i cele dou teste de aplicatii numerice s s a i implementare. Practic, se admite o singur absent la seminar i o singur absent la s a a s a a laborator. De mentionat c laboratorul reprezint 50 % din punctajul notei la aceast disciplin. a a a a Dei teoretic este posibil ca un student care are punctaj zero la laborator s promoveze s a aceast disciplin, acumulnd punctaj maxim la examen, experienta anilor anteriori nu a a a a oferit niciun astfel de exemplu. Deoarece posibilitile de recuperare a laboratoarelor sunt limitate, refacerea unei at lucrri de seminar sau laborator se poate realiza numai cursul sptmnii afectate a n a a a lucrrii i numai msura care exist un calculator liber. Este permis refacerea a s n a n a a lucrrii numai la grupele din seria de care apartine studentul respectiv. Nu se refac a lucrri de seminar sau laborator la sfritul semestrului! a a s Inainte de ecare edint de seminar se recomand ca ecare student s citeasc s a a a a lucrarea care urmeaz a efectuat, conform calendarului. Se va pune accent special a a n pe aspecte teoretice i exemple rezolvate. s LMN, Draft din 30 septembrie 2011

0.1. Informatii utile

3

La nceputul unei edinte de laborator ecare student trebuie s prezinte un pres a referat al lucrrii care urmeaz a efectuat, conform calendarului. Studentii care nu a a a au pre-referate nu vor primiti s efectueze lucrarea. Pe parcursul edintei, studentul a s si completeaz pre-referatul cu date, grace i concluzii. Studentii trebuie sa aib la ei a s a hartie milimetric pentru trasarea gracelor. Astfel, se realizeaz referatul, care trebuie a a predat la sfritul edintei respective. a s s

0.1.4

Modul de notare al laboratorului

Fiecare tem de laborator (L*) este punctat cu o not a a a ntre 1 i 10 pentru referat. s Referatul va contine: 1. Numele studentului i grupa din care face parte s 2. Numele cadrului didactic ndrumator 3. Titlul lucrarii 4. Scopul lucrarii 5. Rezultate experimentale, grace, etc. (conform cerintelor din ndrumar) 6. Observatii i concluzii s Pre-referatul va contine punctele 1, 2, 3, 4 din referat. Foarte important: Observatiile i, mai ales, concluziile au ponderea cea mai mare nota primit pe s n a referat. Un referat fr observatii i concluzii poate avea nota maxim 4 din 10. aa s a Dou sau mai multe referate care contin observatii i concluzii identice vor avea a s ecare nota 1. Referatul nu trebuie s contin: descrierea lucrrii, principiul algoritmilor, pseua a a docodul algoritmilor. Testele de aplicatii numerice (din sptmnile 7 i 14) vor realizate scris i con a a a s n s stau rezolvarea numeric a unor exemple cu ajutorul metodelor studiate. Testele n a de aplicatii vor punctate cu note ntre 1 i 10. s Document disponibil la http://mn.lmn.pub.ro

4


Testul de implementare (din sptmna 14) va consta implementarea limbajul a a a n n de programare C sau limbajul Scilab a unuia din pseudocodurile lucrrilor studiate. a Testul de implementare va punctat cu o not a ntre 1 i 10. Pentru pregtirea s a acestui test, studentii vor ncurajati s exerseze implementarea algoritmilor pe a parcursul edintelor de laborator. s Nota de laborator reprezint 50% din nota disciplinei Metode Numerice Ingineria a n Electric, i se calculeaz astfel: a s a 25% pentru referate; 20% pentru cele dou teste de aplicatii numerice; a 5% pentru testul de implementare.

0.1.5

Calculul notei nale la disciplina Metode Numerice

Modul de calcul al notei nale va prezentat la curs.

0.2

Modul de desfurare a unei edinte de seminar as s sau laborator

Fiecare edint de seminar sau laborator dureaz 2 ore i are o anumit tematic (vezi s a a s a a subcapitolul 0.1.2). cadrul edintei de seminar sunt prezentate studentilor de ctre cadrul didactic In s a urmtoarele chestiuni despre lucrarea respectiv: aspecte teoretice i exemple rezolvate. a a s De asemenea, se vor prezenta pe scurt chestiunile de studiat si modul de lucru, aspecte necesare pentru efectuarea lucrrii de laborator sptmna urmtoare. a n a a a a De mentionat c exemplele rezolvate la ecare edint de seminar sunt esentiale pentru a s a cele dou teste de aplicatii numerice. a Activitile propriu-zise pe care trebuie s le desfoare ecare student at a as ntr-o edint s a de laborator sunt prezentate mai jos. Prima activitate const exploatarea unor programe demonstrative ce ilusa n treaz tematica lucrrii. a a Sistemul de operare sub care se lucreaz este Linux (http://www.linux.org/). Proa gramele demonstrative sunt scrise in Scilab (http://www.scilab.org/) dar exploatarea LMN, Draft din 30 septembrie 2011

0.3. Programe demonstrative

5

Figura 1: Meniul principal al programelor demonstrative. lor nu necesit cunoaterea acestui limbaj de programare. urma exploatrii acestor proa s In a grame, studentul trebuie s redacteze un referat, conform cerintelor ecrei lucrri, i a a a s s predea la sfritul edintei. a l a s s msura timpului disponibil, se va implementa cel putin unul din algoritmii studiati In a cadrul temei respective. Implementarea se va efectua limbajul C sau limbajul Scilab, n n concordant cu pseudocodul prezentat lucrare. n a n

0.3

Programe demonstrative

Pentru lansarea programelor demonstrative faceti un singur clic pe icoana cu sigla LMN. continuare urmati modul de lucru descris In n ndrumar. Observatie: programele demonstrative sunt disponibile la adresa http://mn.lmn.pub.ro/. Pentru a putea lucra cu ele trebuie s aveti instalate sistemul de a operare Linux i pachetul de programe Scilab. Arhiva LMN.tar.gz trebuie decomprimat s a i dezarhivat. Lansati Scilab i la consola acestuia tastati exec(main.sci). Meniul s a s principal este cel prezentat gura 1. n Not important a a Document disponibil la http://mn.lmn.pub.ro

6


Pentru ca un referat s e luat considerare, prezenta la laborator este obligatorie. a n Este obligatoriu ca exploatarea acestor programe s e fcut sub a a a ndrumarea cadrului didactic. Exercitii: 1. Intrati contul dvs.; n 2. Remarcati icoana LMN i executati un singur clic pe ea; s 3. Inchideti programele demonstrative.

0.4

Implementare in C

Inainte de toate, v este util o re a a mprosptare a cunotiintelor de C dobndite anii a s a n anteriori. Metodele numerice ce vor studiate implementeaz exclusivitate algoritmi numerici, a n care efectueaz de cele mai multe ori calcule cu vectori i matrice. a s De aceea, cele ce urmeaz vom face cteva consideratii asupra declarrii i alocrii n a a a s a vectorilor i matricelor, astfel at activitatea de programare cadrul acestui laborator s nc n s e ct mai ecient. a a a Pentru nceput a, v recomandm s studiati cu atentie urmtoarele exemple i ns a a a a s apoi, pentru ntelegerea lor, s cititi paragrafele urmtoare. a a

0.4.1

Exemple

La adresa http://mn.lmn.pub.ro/ gsiti dou exemple pentru a v familiariza cu a a a stilul de lucru al acestui laborator. 1. Creati un director numit L0 cu comanda mkdir L0 2. Descarcati ierele nrutil lmn.c, nrutil lmn.h, aduna vec.c, rw matrix.c. s 3. Comentati continutul acestor iere. s 4. Compilati primul exemplu cu comanda gcc aduna_vec.c nrutil_lmn.c -o aduna_vec LMN, Draft din 30 septembrie 2011

0.4. Implementare in C

7

5. Executati programul cu comanda ./aduna_vec 6. Compilati al doilea exemplu cu comanda gcc rw_matrix.c nrutil_lmn.c -o rw_matrix 7. Executati programul cu comanda ./rw_matrix Observatie: Comanda de compilare contine un ier surs C ( care se a funtia main i o s a n a s n functie ce implementeaz un anumit pseudocod), apoi ierul nrutil lmn.c ( care se a s a functiile de alocare/dealocare de memorie). Numele ce urmeaz dup -o este numele a a a programului executabil generat. Iat continutul acestor iere: a s Fiierul aduna vec.c s#include "nrutil_lmn.h" void aduna_vectori1 (int , VECTOR , VECTOR , VECTOR ); int main (void) { /* program principal - adunarea a doi vectori * apeleaza aduna_vectori */ int n; /* dimensiunea vectorilor */ VECTOR a, b; /* vectorii de intrare */ VECTOR c; /* vectorul rezultat c = a + b */ int i; printf ("\n Introduceti dimensiunea vectorilor "); scanf ("%d", &n); /* aloca spatiu de memorie pentru vectori */ a = vector (1, n); b = vector (1, n); c = vector (1, n); /* citeste vectorii a si b */ for (i = 1; i 0, astfel at eroarea de trunchiere satisface inegalitatea: nc |n | = |x xn | c , np (2.17)

pentru orice n > 1. Se constat c ordinul vitezei de convergent a unui algoritm este a a a dat de panta dreptei ce mrginete superior gracul functiei || = f (n) scar dublu a s n a logaritmic. a LMN, Draft din 30 septembrie 2011

2.2. Principiul lucrrii a

59

O categorie important de procese numerice innite o reprezint seriile Taylor. Acesa a tea, ind serii de puteri, pot utilizate la evaluarea functiilor elementare (sinus, cosinus, exponential, logaritm, etc.) i a celor speciale (Bessel, integrale eliptice ) prin reducerea a s la operatii aritmetice elementare (adunri si a nmultiri). Pentru a exemplica modul care poate sumat numeric o serie cu controlul erorii n a de trunchiere se consider dezvoltarea serie Taylor a functiei y = sin x: a n x3 x5 x7 + + ... 3! 5! 7! Termenul general al seriei poate calculat recursiv: y =x Tk = (1)k 2k1 x2 x = Tk1 . (2k 1)! (2k 1)(2k 2)n

(2.18)

(2.19)

Prin trunchierea seriei la rangul n se obtine y =k=1

(1)k+1 x2k1 . (2k 1)!

(2.20)

Deoarece seria este alternant, eroarea de trunchiere este majorat de modulul primului a a termen neglijat: |x|2n+1 |y | = |y y | . (2.21) (2n + 1)! Rezult urmtorul pseudocod pentru evaluarea functiei sinus cu o eroare de trunchiere a a mai mic dect eroarea de rotunjire. a a functia sinus(x) real x, t, s ntreg k t=x s=t k=1 repet a k =k+2 t = tx2 /k/(k 1) s=s+t pn cnd |t| 0 a dac sin(x) 0 a

iar dezvoltarea ei serie Fourier conduce la n crenel (x) = sin(x) + armonicii alternante 1 1 1 A = 1 + + ... = 2 3 4 k=1

sin(3x) sin(5x) + + 3 5

(1)k+1

1 k

LMN, Draft din 30 septembrie 2011

2.5. Exemple

63

armonicii alternante cu convergent a mbuntit a at a 1 1 1 A = 1 + + . . . = 0.5 + 2 3 4 k=1 1 2k1 1 2k+1 . 4k

Se vor comenta rezultatele i se va aprecia viteza de convergent. s a Indicatie: Pentru estimarea vitezei de convergent se calculeaz panta dreptei ce a a mrginete gracul erorii, scara dublu logaritmic. a s n a

2.4.4

Implementarea unor algoritmi cu controlul erorii

Se va genera pseudocodul functiei cosinus, determinat prin serie Taylor trunchiat a a pn la atingerea unei erori de trunchiere impuse. Se va implementa acest algoritm a a ntrun limbaj de programare sub forma unei functii cosinus(x, ert), care x este variabil n a independent iar ert este eroarea de trunchiere impus. Se va implementa algoritmul de a a determinare al erorii relative de rotunjire err, iar nal se va implementa algoritmul de n evaluare a functiei cosinus cu ert = err i cu controlul propagrii erorii, sub forma unei s a proceduri care s calculeze cos(x) i eroarea relativ asociat. a s a a

2.52.5.1

ExempleExemple rezolvate 2 cu 2

1. S se calculeze o margine a erorii relative pentru aproximarea numrului a a cifre semnicative exacte. Rezolvare:

a a Notm cu x = 2 = 1.4142 . . ., valoarea exact a numrului 2. Aproximarea cu a 2 cifre semnicative exacte a lui 2 este: x = 1.41. Eroarea absolut este: ex = x x = 1.4142 . . . 1.41 = 0.0042 . . .. a Eroarea relativ este: a x = care este mrginit de: a a |x | < Deci: 2 = 1.41 0.36%. Document disponibil la http://mn.lmn.pub.ro 0.005 = 0.0035 . . . < 0.0036 = 0.36%. 1.4 ex 0.0042 . . . = , x 1.4142 . . .

64

Capitolul 2. Erori n rezolvarea problemelor numerice

2. Fie x = 5.43 1%, y = 5.42 2%, z = 3 1%. S se calculeze (x + y) z. Comentati rezultatul obtinut. a Rezolvare: Mai ai se efectueaz operatia din paranteze, care este, de fapt, o scdere: x + y = nt a a 5.43 5.42 = 0.01. Eroarea relativ va mrginit de: a a a x+y = x y 5.43 1 5.42 2 x + y = + = x+y x+y 0.01 100 0.01 100

= 5.43 + 10.84 = 16.27 = 1627%. Eroarea este foarte mare deoarece au fost sczute dou numere foarte apropiate (a a a aprut fenomenul de anulare prin scdere). a a Rezultatul nal (x + y) z = 0.03 este calculat cu o eroare relativ mrginit de: a a a (x+y)z = x+y + z = 1 1628 1627 + = = 1628%. 100 100 100

3. Fie x = 2.3 2%, y = 3.2 3%, z = 5.5 5%. S se calculeze (x + y) + z si x + (y + z). Comentati rezultatele obtinute. a Rezolvare: S calculm (x + y) + z. Mai ai se efectueaz operatia din paranteze: x + y = a a nt a 2.3 + 3.2 = 5.5. Eroarea relativ va mrginit de: a a a x+y = x+y = x y x + y ; x+y x+y (2.22)

2.3 2 3.2 3 2.58 + = = 2.58%. 5.5 100 5.5 100 100

Rezultatul nal (x + y) + z = 5.5 + 5.5 = 11.0 este calculat cu o eroare relativ a mrginit de: a a (x+y)+z = (x+y)+z = x+y z x+y + z ; (x + y) + z (x + y) + z (2.23)

5.5 14.2 1 5.5 5 3.79 + = = 3.79%. 11 5.5 100 11 100 100

In continuare calculm x + (y + z). Mai ai se efectueaz operatia din paranteze a nt a y + z = 3.2 + 5.5 = 8.7. Eroarea relativ va mrginit de: a a a y+z = z y y + z ; y+z y+z (2.24)


2.5. Exemple

65 5.5 5 4.26 3.2 3 + = = 4.26%. 8.7 100 8.7 100 100

y+z =

Rezultatul nal x + (y + z) = 2.3 + 8.7 = 11.0 este calculat cu o eroare relativ a mrginit de: a a x+(y+z) = x+(y+z) = Observm c: a a (x+y)+z = x+(y+z) . Intr-adevr, a nlocuind relatia (2.22) relatia (2.23), obtinem: n (x+y)+z = y z x x + y + z . x+y+z x+y+z x+y+z (2.26) y+z x x + y+z ; x + (y + z) x + (y + z) (2.25)

8.7 37.1 1 3.79 2.3 2 + = = 3.79%. 11 100 11 8.7 100 100

Similar, nlocuind (2.24) (2.25), obtinem exact acelai rezultat, (2.26). n s realitate, aceste calcule nu am inut cont de erorile de rotunjire eps. Acestea In n t se suprapun peste erorile inerente, astfel at este mai corect s scriem: nc a x+y = Urmeaz c: a a (x+y)+z = x+y z x+y + z + eps. (x + y) + z (x + y) + z (2.28) x y x + y + eps. x+y x+y (2.27)

Inlocuind (2.27) (2.28), rezult c: n a a (x+y)+z = y z x+y x x + y + z + eps + eps. x+y+z x+y+z x+y+z x+y+z

Similar se obtine: x+(y+z) = y z y+z x x + y + z + eps + eps. x+y+z x+y+z x+y+z x+y+z

consecint: In a (x+y)+z = x+(y+z) . Adunarea numerelor reale pe un sistem de calcul nu este asociativ. a Document disponibil la http://mn.lmn.pub.ro

66


2.5.2

Exemple propuse

1. S se calculeze o margine a erorii relative pentru aproximarea numrului cu 3 cifre a a semnicative exacte. 2. S se calculeze o margine a erorii relative pentru aproximarea numrului e cu 2 cifre a a semnicative exacte. 3. Fie x = 2.01 1%, y = 4.24 4%, z = 2.12 2%. S se calculeze x y/z. Comentati rezultatul obtinut. a 4. Fie x = 3.12 1%, y = 2 1%, z = 1.21 2%. S se calculeze x y + z. a

2.6

Intrebri i probleme a s

1. Cum poate caracterizat eroarea unei variabile vectoriale x? a 2. Implementati algoritmul de determinare a erorii relative de rotunjire diferite n limbaje de programare ( simpl i dubl precizie) i apoi comparati rezultatele. n as a s 3. Ce modicri trebuie aduse algoritmului de determinare a erorii relative de rotunjire a pentru ca acesta s determine nu numai ordinul de mrime al erorii ci i valoarea a a s sa exact? a 4. Deniti i implementati un tip abstract de date, care s reprezinte ecare numr real s a a ca o pereche de numere reale ce l ncadreaz (valoare maxim, valoare minim). a a a 5. Este adunarea numerelor reale rotunjite o operatie asociativ? Pentru a aduna mai a multe numere reale diferite cu eroare minim ele trebuie sortate ordine cresctoare a n a sau descresctoare? a 6. Pentru a micora erorile de rotunjire la sumarea unei serii cum trebuie adunati s termenii, ordine cresctoare sau descresctoare? n a a 7. Folositi optiunea Calcule cu controlul erorii pentru a determina rezistenta de unt s ce trebuie folosit la transformarea unui galvanometru de 1mA ( clasa 2%) a crui a n a rezistent R = 57.5 a fost determinat cu precizie de 0,5(%) a a ntr-un ampermetru de 1A. LMN, Draft din 30 septembrie 2011

2.6. Intrebri i probleme a s

67

8. Generati un algoritm pentru rezolvarea unei ecuatii de gradul doi, care evit fenomenul a de anulare prin scdere. a 9. Generati i implementati un algoritm, pentru evaluarea functiilor Bessel. s

Document disponibil la http://mn.lmn.pub.ro

68


Brook Taylor

Born: 18 Aug 1685 in Edmonton, Middlesex, England Died: 29 Dec 1731 in Somerset House, London, England http://www-groups.dcs.st-and.ac.uk/~history/Mathematicians/Taylor.html

Jean Baptiste Joseph Fourier

Born: 21 March 1768 in Auxerre, Bourgogne, France Died: 16 May 1830 in Paris, France http://www-groups.dcs.st-and.ac.uk/~history/Mathematicians/Fourier.html


Capitolul 3 Rezolvarea sistemelor de ecuatii liniare prin metoda Gauss. Strategii de pivotare rezolvarea sistemelor n algebrice liniare

3.1

Metoda Gauss fr pivotare a a

3.1.1

Caracterizarea metodei

Metoda Gauss este o metod direct de rezolvare a sistemelor de ecuatii algebrice a a liniare care au matricea sistemului ptrat i nesingular. Solutia sistemului se obtine a a s a dup un numr nit de pai. a a s lucrare se prezint principiul metodei i se analizeaz algoritmul att din punctul In a s a a de vedere al complexitii ct i al stabilitii numerice, evidentiindu-se limitele acestei at a s at metode. 69

70

Capitolul 3. Rezolvarea sistemelor de ecuatii liniare prin metoda Gauss. Strategii de pivotare n rezolvarea sistemelor algebrice liniare

3.1.2

Principiul metodei

Fie sistemul de ecuatii: a11 x1 + a12 x2 + . . . + a1n xn = b1 a21 x1 + a22 x2 + . . . + a2n xn = b2 ...... an1 x1 + an2 x2 + . . . + ann xn = bn sau forma matriceal n a Ax = b (3.2) (3.1)

A ind matricea ptrat n n - dimensional, iar b si x doi vectori n - dimensionali. a a a Cunoscnd matricea sistemului A i termenul liber b se pune problema determinrii solutiei a s a x. Inmultind prima ecuatie, pe rnd, cu ai1 /a11 , pentru i = 2, . . . , n, apoi adunnd-o la a a ecuatia cu numrul i, se elimin x1 din toate ecuatiile, cu exceptia primei ecuatii: a a a11 x1 + a12 x2 + . . . + a1n xn = b1 a22 x2 + . . . + a2n xn = b2 ...... an2 x2 + . . . + ann xn = bn Coecientii care apar linile 2, . . . , n, dei modicati, s-au notat acelai mod, n s n s deoarece ei se vor memora aceleai locatii de memorie. n s Inmultind a doua ecuatie cu ai2 /a22 i adunnd-o apoi la ecuatia i, pentru i = 3, . . . , n, s a se elimina x2 din toate ecuatiile aate sub linia a doua. Se continu astfel pn se aduce sistemul la forma: a a a a11 x1 + a12 x2 + . . . + a1n xn = b1 a22 x2 + . . . + a2n xn = b2 ...... ann xn = bn unde a11 , . . . , ann , b1 , . . . , bn au alte valori dect sistemul initial. a n LMN, Draft din 30 septembrie 2011 (3.4) (3.3)

3.1. Metoda Gauss fr pivotare a a

71

Necunoscutele se determin prin retrosubstitutie: a xn xn1 = = ...... xk = ...... x1 = b1 bn , ann bn1 an1,n xn , an1,n1 bk n j=k+1 akj xj

ak,kn j=2 a1,j xj

,

(3.5)

a11

.

Etapa de aducere a matricei A la forma triunghiular se numete eliminare sau triana s gularizare, iar etapa de determinare a solutiilor - substitutie regresiv sau retrosubstitutie. a Fiecare din elementele akk , cu k = 1, 2, . . . , n se numete pivot. s Dac la o etap a algoritmului se alnete un pivot nul, pentru a evita o artire a a nt s mp la 0 este necesar o permutare a liniilor (sau a liniilor i coloanelor) scopul aducerii pe a s n linia i, coloana i a unui element nenul. Aceast operatie poart numele de pivotare. a a

3.1.3

Pseudocodul algoritmului Gauss fr pivotare a aprocedura gauss fp(n, a, b, x) tablou real a(n, n), b(n), x(n) ;eliminare pentru k = 1, n 1 pentru i = k + 1, n p = aik /akk pentru j = k + 1, n aij = aij akj p bi = bi bk p ;retrosubstitutie xn = bn /ann pentru i = n 1, 1, 1 s = bi pentru j = n, i + 1, 1 s = s aij xj xi = s/aii retur

;etapele eliminrii a ;parcurge coloana de sub pivot ;parcurge linia i, la dreapta ;pivotul


72


Procedura are parametrii: de intrare: n = dimensiunea sistemului; a(n, n) = matricea sistemului; b(n) = vectorul termenilor liberi; de ieire: s x(n) = vectorul solutie. Matricea A este adus la forma superior triunghiular dup n 1 pai. La ecare pas a a a s k, linia k i cele de deasupra ei, colona k i cele din stnga ei nu sunt afectate. s s a

3.1.4

Analiza complexitii at

Efort de calcul Pentru trecerea de la pasul k la pasul k + 1 se efectueaz: a (n k)(n k + 1) nmultiri, (n k)(n k + 1) adunri, a (n k) artiri. mp consecint, pentru trecerea de la matricea initial la forma superior triunghiular, In a a a se vor efectua: n1 k=1 (n n1 k=1 (n n1 k=1 (n

k)(n k + 1) = n(n2 1)/3 nmultiri, k)(n k + 1) = n(n2 1)/3 adunri, a k) = n(n 1)/2 artiri. mp

etapa de retrosubstitutie se mai efectueaz: In a n1 i=1 (n n1 i=1 (n

i) = n(n 1)/2 nmultiri, i) = n(n 1)/2 adunri, a LMN, Draft din 30 septembrie 2011

3.1. Metoda Gauss fr pivotare a a

73

n imprtiri. a Deci, total se efectueaz: n a n(n 1)(2n + 5)/6 nmultiri, n(n 1)(2n + 5)/6 adunri, a n(n + 1)/2 artiri. mp Deoarece, general, timpul necesar calculatorului pentru a efectua o n nmultire sau o mpartire este aproximativ egal cu cel consumat pentru o adunare, efortul de calcul este 2n(2n2 + 6n 2)/6 operatii aritmetice elementare. Dac n este mare (n > 2), efortul de calcul este de ordinul 2n3 /3 i se noteaz O(2n3 /3). a s a Necesarul de memorie Pentru memorarea matricei A i a vectorilor b i x sunt necesare: n2 + n + n = n(n + 2) s s locatii de memorie, ecare locatie de memorie ind rezervat unui numr real. a a

3.1.5

Analiza erorilor

Rulat pe un calculator ipotetic de precizie innit, algoritmul Gauss permite detera minarea solutiei exacte a sistemului. Cu alte cuvinte acest algoritm nu introduce eroare de metod. a Pot apare a erori de rotunjire, datorate preciziei nite a echipamentului de calcul. ns Aceste erori cresc odat cu creterea dimensiunii n a sistemului. a s Metoda Gauss aceast variant (fr pivotare) poate genera instabiliti numerice n a a aa at chiar dac nu se alnete vreun element aii nul, din cauza erorilor de rotunjire. a nt s Pentru evaluarea erorii se poate folosi reziduul r = Ax b, mai precis norma lui. Aceast norm poate evaluat euclidian: a a a r| =k 2 rk

(3.6)

(3.7)

sau sens Cebsev: n r = max rk , k = 1, . . . , n. (3.8)


74


Eroarea relativ se denete ca a s r = r / b . (3.9)

Norma reziduului denit anterior, nu trebuie confundat cu norma erorii adevrate: a a a e = xadevrat x . a Eroarea relativ adevrat se denete ca: a a a s = e/ xadevrat . a (3.11) (3.10)

Calculul erorii (3.10) ar necesita a cunoaterea solutiei exacte a sistemului. De ns s aceea, practic se face doar o evaluare a erorii, folosind norma reziduului, care a n a ns poate avea o valoare mai mare sau mai mic dect eroarea real. a a a

3.2

Strategii de pivotare rezolvarea sistemelor aln gebrice liniare

3.2.1

Caracterizarea metodei

Pivotarea este o metod care permite extinderea domeniului de aplicabilitate a metodei a Gauss i s mbuntirea stabilitii ei numerice. a at at acest paragraf se analizeaz diferite strategii de pivotare i efectele lor asupra erorii In a s cu care se obtine solutia.

3.2.2

Principiul metodei

La rezolvarea unui sistem de ecuatii prin metode directe, de exemplu prin metoda Gauss, poate apare situatia care un element pivot akk este nul, chiar dac matricea n a sistemului este nesingular. Metodele directe necesitnd artirea la pivot, sistemul nu a a mp se poate rezolva forma dat. n a Permutarea liniilor i/sau a coloanelor astfel at s se aduc pe pozitia diagonal s nc a a a (k, k), un element nenul se numete pivotare. Pentru a obtine o bun stabilitate numeric s a a (erori de rotunjire minime) se prefer alegerea ca pivot a unui element de modul maxim. a LMN, Draft din 30 septembrie 2011

3.2. Strategii de pivotare n rezolvarea sistemelor algebrice liniare

75

Se pot utiliza trei strategii de pivotare: partial, total sau diagonal. a a a Pivotarea partial const cutarea pivotului de modul maxim printre toti coecientii a a n a aati sub linia k i pe coloana k i aducerea acestui element pe pozitia (k, k) prin permutri s s a de linii (ceea ce este echivalent cu schimbarea ordinii ecuatiilor). Pivotarea total const cutarea pivotului de modul maxim printre toti coecientii a a n a aati sub linia k i la dreapta coloanei k i aducerea acestui element pe pozitia (k, k) prin s s permutri de linii i de coloane (se schimb att ordinea liniilor ct i cea a coloanelor). a s a a a s Pivotarea diagonal const cutarea pivotului optim doar printre elementele dia a n a agonale aii , cu i k. Aducerea acestui element pe pozitia (k, k) se face, ca i la pivotarea s total, prin permutri de linii i coloane. Avantajul acestei strategii de pivotare este a a s pstrarea simetriei matricei sistemului. a La metoda cu pivotare partial, unde se fac doar permutri de linii, ordinea necunos a a cutelor ecare ecuatie nu se modic. La metodele cu pivotare total sau diagonal, n a a a datorit permutrii coloanelor, se modic i ordinea necunoscutelor sistem. De aceea, a a as n aceste strategii impun memorarea permutrilor de coloane fcute pe parcursul algoritmua a lui, pentru a se putea reconstitui la sfrit ordinea initial a necunoscutelor. as a

3.2.3

Pseudocodul algoritmului Gauss cu pivotare partial a

functia gausspp (n, a, b, x) tablou real a(n, n), b(n), x(n) ; eliminare ; etapele eliminrii a pentru k = 1, n 1 ; gsire pivot a max = k pentru m = k + 1, n dac |amx | > |amax,k | atunci max = m a dac amax,k = 0 atunci a ntoarce 1 ; eroare dac max = k atunci a ; permut liniile max, k a pentru m = k, n temp = akm akm = amax,m amax,m = temp temp = bk ; permut termenii liberi a bk = bmax bmax = temp ; s-a gsit pivotul a pentru i = k + 1, n ; parcurge coloana de sub pivot Document disponibil la http://mn.lmn.pub.ro

76


dac aik = 0 atunci a p = aik /akk pentru j = k + 1, n aij = aij akj p bi = bi bk p ; retrosubstitutie dac an,n = 0 atunci a ntoarce 1 xn = bn /an,n pentru i = n 1, 1, 1 s = bi pentru j = n, i + 1, 1 s = s aij xj xi = s/aii ntoarce 0 Functia are parametrii: de intrare: n = dimensiunea sistemului; a(n, n) = matricea sistemului; b(n) = vectorul termenilor liberi. de ieire: s x(n) = vectorul solutiei. Functia ntoarce: 0 1 - dac algoritmul s-a executat integral; a - dac matricea sistemului este singular. a a

; parcurge linia i ; la dreapta pivotului

; eroare

3.2.4

Analiza complexitii at

Efort de calcul Dac se neglijeaj timpul consumat datorit permutrilor de linii, efortul de calcul la a a a a 3 procedura Gauss cu pivotare este de ordinul O(2n /3), ca i la cea fr pivotare. s aa LMN, Draft din 30 septembrie 2011

3.3. Chestiuni de studiat

77

Necesarul de memorie Pentru memorarea matricei A i a vectorilor b i x sunt necesare: s s n2 + n + n = n(n + 2) locatii, ecare locatie de memorie ind rezervat unui numr real. a a

3.2.5

Analiza erorilor

Erorile se calculeaz la fel ca la algoritmul Gauss fr pivotare. Dei stabilitatea a aa s numeric a algoritmului cu pivotare este general mai bun, totui, erorile de rotunjire a n a s pot afecta grav solutia cazul sistemelor slab conditionate. n

3.3

Chestiuni de studiat

1. Rezolvarea unor sisteme algebrice liniare; 2. Analiza experimental a algoritmilor; a 3. Implementarea algoritmilor ntr-un limbaj de programare; 4. Cutare de informatii legate de aceast tem. a a a

3.4

Modul de lucru

Se selecteaz lucrarea Rezolvarea sistemelor cu metoda Gauss din meniul principal. a Aceasta are ca efect lansarea urmtorului meniu: a

Rezolvare sisteme de ecuatii Analiza algoritmilor Document disponibil la http://mn.lmn.pub.ro

78


3.4.1

Rezolvarea unor sisteme algebrice liniare

Se selecteaz optiunea Rezolvare sisteme de ecuatii. a Se vor introduce parametrii x1 + x2 + 2x1 + x2 + x + x2 + 1 2x1 + 3x2 + x + x + 1 2 necesari pentru rezolvarea urmtoarelor sisteme: a x3 x3 3x3 x3 x3 + x4 + 3x4 + x4 + 2x4 + x4 + x5 + x5 + 2x5 + x5 + 4x5 = = = = = 9 12 17 15 15 R : x1 x2 x3 x4 x5 =1 =2 =3 =1 =2

x1 + x2 2x3 = 3 3x + x3 = 10 1 x1 + 2x2 + x3 = 12

R : x1 = 2 x2 = 3 x3 = 4

y + z = 4 2x + y + 2z = 11 x + 2y + z = 7

x + 2y + z = 7 x + 2y + 2z = 10 2x + 4y + 3z = 11

mx1 + 1000x2 = 1000 1000x1 = 1000

unde m ia valorile: 1000, 100, 10, 1, 101 , 104 , 105 , 106 . Se vor selecta pe rnd metoda fr pivotare i apoi cu pivotare. Se vor comenta a aa s rezultatele obtinute.

3.4.2

Analiza experimental a algoritmului a

Se selecteaz optiunea Analiza algoritmilor. a Astfel, se apeleaz un program care rezolv sisteme de ecuatii liniare de diferite mrimi a a a prin metoda Gauss fr pivotare, Gauss cu pivotare partial i Gauss cu pivotare total. aa as a Parametrul de intrare al programului este dimensiunea sistemului, n. Dup preluarea a acestui parametru programul genereaz aleator un sistem de n ecuatii i n necunoscute, a s LMN, Draft din 30 septembrie 2011

3.4. Modul de lucru

79

rezolv i aeaz: eroarea absolut, eroarea relativ i reziduul rezultatului, calculate l as s a a as ecare cu formula normei Euclidiene, sau a normei Cebsev ( total 6 valori). Se aeaz n s a de asemenea timpul de calcul. Pentru a simplica operatia de culegere a datelor numerice, programul cere valoarea initial a lui n, valoarea nal i pasul. Se recomand folosirea urmtoarelor valori: a a s a a valoare initial 10, valoare nal 100, pas 10, ceea ce corespunde irului de valori n = a a s 10, 20, 30, 40, 50, 60, 70, 80, 90, 100. Rezultatele numerice sunt aate consola Scilab i reprezentate grac. s n s Se vor nota pentru ecare n i ecare metod eroarea relativ (norma Euclidian i s a a a s norma Ceb sev) i reziduul relativ (norma euclidian), precum i timpul de calcul. s a s n timp [s] er.rel (Euclid) er.rel (Cebsev) reziduu rel. (Euclid) G.f.p G.p.p G.p.t G.f.p G.p.p. G.f.p G.p.p. G.f.p G.p.p. 10 20 90 100

Se vor reprezenta pe hrtie milimetric: a a curba timpului de calcul functie de dimensiunea sistemului n; n curbele erorilor de calcul functie de n. n

3.4.3

Implementarea algoritmilor ntr-un limbaj de programare

Se va implementa o procedur proprie de rezolvare a unui sistem de ecuatii prin metoda a Gauss fr pivotare. Se va compila procedura elimin aa ndu-se eventualele erori. Se va scrie pseudocodul i se va implementa pe calculator un program care apeleaz s a procedura de la punctul anterior i rezolv sistemul de ecuatii: s a 2x + y + z = 7 R: x=1 x + y + z = 6 y=2 2x + y + 3z = 13 z=3 Document disponibil la http://mn.lmn.pub.ro

80


Acest program va permite introducerea datelor de la consol i aarea pe ecran a a s s solutiei. Se vor nota i comenta rezultatele obtinute, eventualele diculti aprute pe s at a parcursul lucrului.

3.4.4

Cutare de informatii a

Cutati pe Internet informatii (coduri) legate de metoda Gauss pentru rezolvarea dia rect a sistemelor de ecuatii liniare. Exemple de cuvinte cheie: Gauss elimination and a back substitution.

3.53.5.1

ExempleExemple rezolvate

1. Fie sistemul de ecuatii: x + 2y z = 4 2x + 2y 3z = 2 3x + 2y + 2z = 2 S se rezolve sistemul de ecuatii prin metoda Gauss. a Rezolvare: Deoarece matricea coecientilor sistemului de ecuatii este ptrat i nesingular, a a s a metoda Gauss se poate aplica pentru rezolvarea sistemului de ecuatii. Metoda Gauss const etapa de eliminare i etapa de retrosubstitutie. a n s etapa de eliminare (sau triangularizare) matricea coecientilor sistemului de In ecuatii se aduce la forma superior triunghiular. a Pentru triangularizarea matricii, prima ecuatie (linie, notat L1 c ele ce urmeaz) a n a se nmultete cu (2/1) i se adun la a doua ecuatie (linie, L2 ) pentru a se elimina s s a termenul x din a doua ecuatie. De notat c, dup acest pas, prima ecuatie nu se n a a modic, doar a dou ecuatie sufer modicri, conform relatiei L2 = L2 + (2) L1 . a a a a LMN, Draft din 30 septembrie 2011

3.5. Exemple

81

L1 L2 L3 L1 L2 L3

2 x + 2y z = 4 | ( 1 ) 2x + 2y 3z = 2 3x + 2y + 2z = 2

L2 =L2 +(2)L1

=

continuare, prima ecuatie (L1 ) se In nmultete cu [(3)/1] i se adun la a treia s s a ecuatie (L3 ), astfel eliminndu-se termenul x i din a treia ecuatie (L3 = L3 + 3 a n s L1 ). L1 L2 L3 L1 L2 L3 x + 2y z = 4 | ( 3 ) 1 2y z = 6 3x + 2y + 2z = 2 x + 2y z = 4 2y z = 6 + 8y z = 14

x + 2y z = 4 2y z = 6 3x + 2y + 2z = 2

L3 =L3 +3L1

=

Se observ c elementele de sub elementul diagonal din prima ecuatie sunt nuli. a a Mai departe, se urmrete anularea elementelor de sub elementul diagonal din a a s doua ecuatie. Astfel, a doua ecuatie (L2 ) se nmultete cu [8/(2)] i se adun la a treia ecuatie s s a (L3 ), eliminndu-se termenul y din a treia ecuatie (L3 = L3 + 4 L2 ). De notat a n c ecuatia a doua (L2 ) nu sufer modicri. a a a L1 L2 L3 L1 L2 L3 x + 2y z = 4 8 2y z = 6 | ( 2 ) + 8y z = 14

L3 =L3 +4L2

=

Se observ c matricea coecientilor ultimului sistem de ecuatii este superior tria a unghiular. a Document disponibil la http://mn.lmn.pub.ro

x + 2y z = 4 2y z = 6 5z = 10

82


Necunoscutele sistemului se determin in etapa de retrosubstitutie (substitutie a regresiv). a ultima ecuatie apare o singur necunoscut, z, care se calculeaz astfel: In a a a z= 10 = 2. 5

a doua ecuatie, avem tot o singur necunoscut, y, deoarece z este deja calculat In a a la pasul precedent. Astfel: y= 6 + 2 6 + z = = 2. 2 2

sfrit, prima ecuatie, singura necunoscuta este acum x, iar y i z ind calculate In a s n s la paii anteriori. Rezult: s a x= 4 2y + z = 4 4 + 2 = 2. 1

Solutia sistemului de ecuatii este (2, 2, 2). 2. Fie sistemul de ecuatii: x + 2y + 4z = 5 3x y + z = 3 2x y + z = 2 S se rezolve sistemul de ecuatii prin metoda Gauss. a Rezolvare: Etapa de eliminare: Prima ecuatie (L1 ) se nmultete cu [3/(1)] i se adun la a doua ecuatie (L2 ), s s a astfel se elimin termenul x din a doua ecuatie. Doar a doua ecuatie se modic a n a (L2 = L2 + 3 L1 ). Prima ecuatie (L1 ) se nmultete cu [(2)/(1)] i se adun la a treia ecuatie s s a (L3 ), astfel se elimin termenul x i din a treia ecuatie (L3 = L3 + (2) L1 ). a n s De precizat c prima ecuatie (L1 ) nu se modic. a a LMN, Draft din 30 septembrie 2011

3.5. Exemple

83

L1 L2 L3 L1 L2 L3

3 x + 2y + 4z = 5 | ( 1 ) | ( 2 ) 1 3x y + z = 3 2x y + z = 2 x + 2y + 4z = 5 5y + 13z = 18 5y 7z = 12

L2 =L2 +3L1

=

L3 =L3 +(2)L1

=

A doua ecuatie (L2 ) se nmultete cu [(5)/5] i se adun la a treia ecuatie (L3 ), s s a eliminndu-se y din a treia ecuatie (L3 = L3 + 1 L2 ). a a a De notat c ecuatia a doua (L2 ) nu sufer modicri. a L1 L2 L3 L1 L2 L3 x + 2y + 4z = 5 5y + 13z = 18 | ( 5 ) 5 5y 7z = 12

L3 =L3 +L2

=

Se observ c matricea coecientilor ultimului sistem de ecuatii este superior tria a unghiular. a Etapa de retrosubstitutie: Necunoscutele sistemului se determin astfel: a z = y = x =6 =1 6 1813z = 1813 = 1 5 5 52y4z = 524 = 1 1

x + 2y + 4z = 5 5y + 13z = 18 6z = 6

1.

Solutia sistemului de ecuatii este (1, 1, 1). 3. Fie sistemul de ecuatii: 2x + y z = 3 4x + 4y + z = 7 6x + 2y + 3z = 19

S se rezolve sistemul de ecuatii prin metoda Gauss. a


84


Rezolvare: Etapa de eliminare:

L1 L2 L3 L1 L2 L3 L1 L2 L3

6 4 2x + y z = 3 | ( 2 ) | ( 2 ) 4x + 4y + z = 7 6x + 2y + 3z = 19 2x + y z = 3 5 2y + 3z = 13 | ( 2 ) 5y = 10 y 2y + z = 3 3z = 13 15 z = 45 2 2

L2 =L2 +(2)L1

=

L3 =L3 +3L1

=

L3 =L3 +(5/2)L2

=

2x +

Matricea coecientilor ultimului sistem de ecuatii este superior triunghiular. a Se observ c ultima ecuatie a penultimului sistem de ecuatii de mai sus exist a a n a o singur necunoscut, y. Determinarea lui y din aceast ecuatie este corect din a a a a punct de vedere matematic, dar nu este conform metodei Gauss. La metoda Gauss, necunoscutele sistemului se determin cnd matricea sistemului are o form superior a a a triunghiular, ceea ce nu este cazul matricii penultimului sistem de ecuatii. a Etapa de retrosubstitutie: z = y = x = 45 2 =3 15 2 133z = 139 = 2 2 2 3y+z = 32+3 2 2

= 1.

Solutia sistemului de ecuatii este (1, 2, 3). 4. Fie sistemul de ecuatii: 2y 3z = 1 x + y z = 1 2x + 3y + z = 2

S se rezolve sistemul de ecuatii prin metoda Gauss. a Rezolvare:


3.5. Exemple

85

Etapa de eliminare: prima ecuatie coecientul diagonal (pivotul, termenul x) este nul, ceea ce ar In n duce la o artire la zero etapa de eliminare. Din acest motiv, trebuie s se mp n a aplice o tehnic de pivotare. Se va utiliza pivotarea partial (permutarea a dou a a a linii), ind cea mai uor de aplicat. s Pentru a obtine erori de rotunjire minime, se permut prima ecuatie (cu pivot nul) a cu ecuatia care are termenul x maxim modul (coecientul de sub pivotul nul). n n Se observ c a treia ecuatie a a ndeplinete aceast conditie (| 2| > |1|). s a Astfel, prima ecuatie se permut cu a treia ecuatie, iar sistemul de ecuatii devine: a L1 L2 L3 L1 L2 L3 L1 L2 L3 1 2x + 3y + z = 2 | ( 2 ) x + y z = 1 2y 3z = 1 2x + 3y + z = 2 1 4 5 y 2z = 2 | ( 5 ) 2 2y 3z = 11 z 2 13 z 5

L2 =L2 +(1/2)L1

=

L3 =L3 +(4/5)L2

=

Matricea coecientilor ultimului sistem de ecuatii este superior triunghiular. a Etapa de retrosubstitutie: z = y = x = 13 5 = 13 5 1 2+ 2 z5 2

2x + 3y + 5 y 2

z = 2 = 2 13 = 5

12+ 1 25 2

=

=1 = 1.

23yz 2

=

231 2

Solutia sistemului de ecuatii este (1, 1, 1). 5. Fie sistemul de ecuatii: x 2x 3x x + y + z 2y z + 2y + z 3y + z + w + w w + 2w = 2 = 0 = 1 = 1


86


S se rezolve sistemul de ecuatii prin metoda Gauss. a Rezolvare: Etapa de eliminare: x + y + z 2x 2y z 3x + 2y + z x 3y + z x + y +

L1 L2 L3 L4 L1 L2 L3 L4

+ +

w = w =

1 2 2 | ( 1 ) | ( 3 ) | ( 1 ) 1

0

L2 =L2 +2L1

=

w = 1 1

L3 =L3 +(3)L1

=

+ 2w =

L4 =L4 +L1

=

z z y 2z 2y + 2z

+ w = 2 + 3w = 4 4w = 7 + 3w = 3

a doua ecuatie coecientul diagonal (pivotul, termenul y) este nul, ind neceIn n sar o pivotare partial. a a Pentru a obtine erori de rotunjire minime, se permut a doua ecuatie (cu pivot nul) a cu ecuatia care are termenul y maxim modul (coecientul de sub pivotul nul). n n Se observ c a patra ecuatie a a ndeplinete aceast conditie (| 2| > | 1|). s a Astfel, a doua ecuatie se permut cu a patra ecuatie, iar sistemul de ecuatii devine: a 2 x + y + z + w = 1 2y + 2z + 3w = 3 | ( 2 ) y 2z 4w = 7 z + 3w = 4 w 3w 11 w 2 3w

L1 L2 L3 L4 L1 L2 L3 L4 L1 L2 L3 L4

L3 =L3 +(1/2)L2

=

x + y + z + 2y + 2z + 3z

x + y + z + 2y + 2z + 3z z +

= 2 = 3 1 = 17 | ( 3 ) 2 = 4

L4 =L4 +(1/3)L3

=

w 3w 11 w 2 7 w 6

= 2 = 3 17 = 2 7 = 6


3.5. Exemple

87

Matricea coecientilor ultimului sistem de ecuatii este superior triunghiular. a Etapa de retrosubstitutie: w = z = y = x =7 6 7 6

=1

17 + 11 17 + 11 w 2 2 = 23 2 = 1 3 32z3w = 323 = 1 2 2 2yzw = 2111 = 1. 1 1

Solutia sistemului de ecuatii este (1, 1, 1, 1).

3.5.2

Exemple propuse 3x y + z = 3 3x 6y + z = 2 x + 2y + 4z = 5

1. Fie sistemul de ecuatii:

S se rezolve sistemul de ecuatii prin metoda direct Gauss. a a 2. Fie sistemul de ecuatii: x + y 3z = 1 2x + y z = 2 x y z = 1

S se rezolve sistemul de ecuatii prin metoda direct Gauss. a a 3. Fie sistemul de ecuatii: x + 2y z = 2 2x y 2z = 1 x + y + z = 1

S se rezolve sistemul de ecuatii prin metoda Gauss. a 4. Fie sistemul de ecuatii:


y + z = 3 2x + y z = 1 x y + 2z = 2


88


5. Fie sistemul de ecuatii: x + y + z = 1 2x 2y z = 1 3x + y + z = 1


3.6

Intrebri a

1. Cum se pot verica solutiile obtinute urma rezolvrii unui sistem de ecuatii? Cum n a s-ar putea evalua eroarea cu care s-au determinat necunoscutele? 2. Dati exemplu de un sistem, cu matricea A nesingular, care nu poate rezolvat a prin algoritmul Gauss fr pivotare. aa 3. Care este ordinul de complexitate al algoritmului Gauss? S se compare valoarea a teoretic cu valorile obtinute urma experimentrilor. a n a 4. S se evalueze durata medie a unei operatii matematice elementare. a 5. Cum variaz erorile de calcul introduse de algoritmul Gauss cu dimensiunea sisa temului? Care este explicatia? 6. Ct de bine este evaluat eroarea adevrat prin norma reziduului? a a a a 7. Evidentiati utilitatea acestei proceduri electrotehnic. n a 8. Ce modicri trebuie aduse procedurii pentru a rezolva sisteme cu coecienti coma pleci? s 9. Ce alte mbuntiri se pot aduce procedurii? a at 10. Ce limitri are algoritmul prezentat capitolul 3? a n 11. Cum variaz timpul de calcul la rezolvarea de sisteme liniare prin metodele Gauss a fr pivotare i cu pivotare? Care este explicatia? aa s 12. Care sunt avantajele i dezavantajele metodelor cu pivotare? s 13. Cum variaz erorile de calcul introduse de algoritmul Gauss pentru metodele: fr a aa pivotare, cu pivotare partial, cu pivotare total? a a LMN, Draft din 30 septembrie 2011

3.6. Intrebri a

89

14. S se fac o analiz a celor trei metode, lund consideratie erorile i timpul de a a a a n s calcul. Care este metoda optim? a 15. Ce modicri trebuie aduse algoritmului pentru a rezolva sistemul cu coecienti a compleci? s 16. Ce alte mbuntiri se pot aduce algoritmului? a at


90


Johann Carl Friedrich Gauss

Born: 30 April 1777 in Brunswick, Duchy of Brunswick (now Germany) Died: 23 Feb 1855 in Gttingen, Hanover (now Germany) http://www-gap.dcs.st-and.ac.uk/~history/Mathematicians/Gauss.html http://scienceworld.wolfram.com/biography/Gauss.html

Pafnuty Lvovich Chebyshev

Born: 1821 in Okatovo, Russia Died: 1894 http://scienceworld.wolfram.com/biography/Chebyshev.html


3.6. Intrebri a

91

Euclid of Alexandria

Born: about 325 BC Died: about 265 BC in Alexandria, Egypt http://www-gap.dcs.st-and.ac.uk/~history/Mathematicians/Euclid.html http://scienceworld.wolfram.com/biography/Euclid.html


92



Capitolul 8 Metode iterative de rezolvare a sistemelor algebrice liniare8.1 Caracterizarea metodelor

Metodele iterative sunt metode care permit obtinerea solutiei numerice a unui sistem de ecuatii, prin generarea unui ir care tinde ctre solutia exact. Elementele acestui ir s a a s de iteratii se calculeaz recursiv, iar procesul se oprete dup un numr nit de pai, la a s a a s ndeplinirea criteriului de eroare. Chiar dac solutia obtinut prin metode iterative este afectat de erori de trunchiere, a a a erori care nu apar cazul metodelor directe, este totui posibil ca solutia iterativ s e n s a a mai precis dect cea obtinut prin metode directe. Pentru o anumit clas de sisteme, a a a a a metodele iterative sunt superioare att din punctul de vedere al erorii ct i din cel al a a s efortului de cacul.

8.2

Principiul metodei

lucrare se prezint cele mai simple metode iterative pentru rezolvarea sistemelor In a algebrice liniare i se descrie clasa sistemelor pentru care acestea pot aplicate. s Metodele iterative de rezolvare a sistemelor de ecuatii liniare sunt metodele care n termenul x(k) al irului solutiilor se obtine din termenul anterior, x(k1) . s Solutia exact se obtine teoretic dup un numr innit de iteratii. practic, prin a a a In a efectuarea unui numr nit de iteratii, se poate ajunge la o aproximare sucient de bun a a a 93

94

Capitolul 8. Metode iterative de rezolvare a sistemelor algebrice liniare

solutiei exacte. Dac irul iteratiilor este convergent, cu ct se efecteaz mai multe iteratii, as a a cu att solutia numeric este mai precis determinat, erorile, att cele de trunchiere ct a a a a a i cele de rotunjire, devenind tot mai mici. s metodele iterative, se pornete de la o initializare arbitrar pentru vectorul solutie In s a 0 numeric x . Pentru a determina noua valoare a solutiei numerice, se rescrie ecuatia sub a forma: x = F (x), (8.1) care F se numete aplicatie cu punct x, iar la ecare pas k al algoritmului, se determin n s a noua solutie numeric din relatia: a xk = F (xk1). Pentru a aduce sistemul de rezolvat Ax = b (8.3) la forma unei aplicatii cu punct x, general se caut o descompunere a matricei A n a ntr-o diferent de dou matrice: a a A = B C, (8.4) sistemul putnd astfel adus la forma: a x = B1 (b + Cx), solutia la pasul k ind: xk = B1 (Cxk1 + b), sau xk = Mxk1 + u, care M = B1 C se numete matrice de iteratie, iar u = B1 b. n s Una din problemele metodelor iterative este convergenta irului de iteratii. Se demon s streaz c o conditie sucient pentru ca metoda s e convergent este ca valorile proprii a a a a a 1 ale matricei de iteratie M = B C s e toate, modul, mai mici dect 1. Denind a n a raza de convergent a matricei M, (M), ca ind modulul celei mai mari valori proprii, a conditia de convergent se scrie: a (M) < 1 (8.8) Aceast conditie de convergent este corelat cu norma matricei de iteratie M. Se demona a a streaz c, pentru orice matrice, exist urmtoarea relatie a a a a ntre norma i raza sa de s convergent: a (M) M (8.9) LMN, Draft din 30 septembrie 2011 (8.7) (8.6) (8.5) (8.2)

8.2. Principiul metodei

95

Prin urmare, dac matricea M are norma subunitar ( M < 1), raza sa de convergent a a a va i ea mai mic dect 1, iar metoda iterativ va acest caz convergent. s a a a n a Metodele iterative cele mai cunoscute sunt: metoda deplasrilor simultane (Jacobi), a metoda deplasrilor succesive (Gauss-Seidel), a metoda suprarelaxrilor succesive(Frankel-Young), a metoda directiilor alternante (Peaceman-Rachford), metoda iteratiilor bloc, metoda factorizrii incomplete, a metoda Southwell. Metoda Jacobi a deplasrilor simultane const alegerea partititiei matricei A astfel: a a n B este matricea alctuit din elementele diagonale ale lui A a a B = D, (8.10)

iar matricea C contine restul elementelor din matricea A, luate cu semn schimbat: C = (L + U), (8.11)

care s-au notat cu L i U triunghiul inferior, respectiv cel superior din A. Cu aceast n s a descompunere, vectorul solutie la ecare pas k va avea expresia: xk = D1 (b (L + U)xk1 ), iar matricea de iteratie M va : M = D1 (L + U). Se consider linia i a sistemului de ecuatii care trebuie rezolvat: a ai1 x1 + ai2 x2 + . . . + aii xi + . . . + ain xn = bi (8.14) (8.13) (8.12)

Partitionarea aleas pentru matricea A revine la a determina pe xi la pasul curent k din a ecuatia i, cu relatia: k1 bi n j=1,j=i aij xj k xi = , (8.15) aii Document disponibil la http://mn.lmn.pub.ro

96


care xi din membrul stng reprezint componenta i a noii solutii, iar xj din membrul n a a drept sunt valorile obtinute la precedentul pas al iteratiei. Se observ c, pentru deter a a minarea noii solutii, trebuie cunoscute, pe tot parcursul iteratiei k, valorile solutiei de la pasul anterior k 1. metoda Gauss-Seidel, a deplasrilor succesive, partitionarea se alege astfel: In a B = D + L, (8.16)

matricea B continnd astfel partea inferior triunghiular a matricei A inclusiv diagonala, a a iar C = U (8.17)

matricea C continnd partea superior triunghiular a matricei. Matricea de iteratie va a a avea forma M = (D + L)1 U. (8.18)

Aceast partitionare presupune c membrul stng al ecuatiei i din sistem rmn tera a n a a a menii care contin xj , j i, iar membrul drept trec toti ceilalti termeni: n ai1 x1 + ai2 x2 + . . . + aii xi = bi ai,i+1 xi+1 . . . ain xn . (8.19)

Ca i pn acum, componentele vectorului solutie aate membrul stng reprezint s a a n a a valori noi, calculate la pasul curent k, pe cnd componentele din membrul drept sunt a cele calculate la pasul anterior. Din aceast relatie rezult valoarea componentei xi la a a pasul curent:i1 n (k) aij xj j=1

xk = i

bi

aij xjj=i+1

(k1)

aii

.

(8.20)

Se observ c o component xi a solutiei la pasul k este calculat functie de componena a a a n tele precedente 1, . . . , i 1, deja calculate la pasul curent i de urmtoarele componente s a i + 1, . . . , n, calculate la pasul precedent. Algoritmul nu necesit pstrarea vechii coma a ponente i, dup ce cea nou a fost calculat, de aceea xi nou se poate plasa memorie a a a n aceeai locatie ca i vechea valoare. Astfel, algoritmul Gauss-Seidel nu necesit spatiu n s s a pentru memorarea dect a unui vector solutie, spre deosebire de algoritmul Jacobi, unde a trebuiau memorati att x nou ct i x vechi. metoda Gauss-Seidel, imediat ce o compo a a s In nent a fost determinat, ea este folosit calculele urmtoare, a a a n a nlocuind valoarea veche care se pierde, idee cunoscut sub numele de principiul lui Seidel. a Una din problemele care apar la rezolvarea sistemelor de ecuatii liniare prin metode iterative este alegerea criteriului de oprire a procesului iterativ. O metod de a rezolva a LMN, Draft din 30 septembrie 2011

8.3. Pseudocodul algoritmilor

97

aceast problem a criteriului de oprire const evaluarea, dup ecare iteratie, a erorii a a a n a Cauchy e = xnou xvechi (8.21) i s ntreruperea calculelor atunci cnd aceast valoare devine mai mic dect eroarea ima a a a pus, . a ceea ce privete convergenta metodelor, se demonstreaz c la metodele Jacobi i In s a a s Gauss-Seidel, o conditie sucient ca metodele s e convergente este ca matricea A a a a sistemului s e diagonal dominant, adic a a a |aii | > |aij | i. (8.22)

j=i

Desigur, aa cum s-a artat, conditia de mai sus este echivalent cu impunerea conditiei s a a ca norma matricei de iteratie s e subunitar, procesul iterativ ind cu att mai rapid a a a convergent cu ct norma matricei de iteratie este mai mic. cazul matricelor simetrice a a In i pozitiv denite, metoda Gauss-Seidel este de aproximativ 2 ori mai rapid dect metoda s a a Jacobi. Acest avantaj, corelat i cu necesitatea memorrii unui singur vector solutie, face s a ca metoda Gauss-Seidel s e preferabil metodei Jacobi din toate punctele de vedere. a a

8.3

Pseudocodul algoritmilor

Urmtoarea procedur permite rezolvarea sistemelor de ecuatii liniare prin metoda Jacobi. a a procedura Jacobi (n,a,b,x,nrit,eps) tablou real a(n,n),b(n),x(n) nteg nrit real eps tablou real xn(N) ; initializri a k=0 pentru i=1,n xi = 0 ; iteratii repet a err= 0; pentru i= 1,n s = b(i)

; x nou ; contor iteratii ; initializarea solutiei ; parcurge iteratiile ; eroarea la pasul curent ; parcurge ecuatiile


98


pentru j=1,n s = s a(i, j)x(j) s = s + a(i, i)x(i) xn(i) = s/a(i, i) s = |xn(i) x(i)| dac err < s atunci err = a pentru i= 1,n x(i) = xn(i) k =k+1 pn cnd (err < eps) sau (k > nrit) a a a retur

; parcurge ecuatia i

; x nou s ; nlocuiete x vechi cu x nou s ; incrementeaz contor iteratii a

Urmtoarea procedur permite rezolvarea sistemelor de ecuatii liniare prin metoda a a Gauss-Seidel procedura Gauss-Seidel(n,a,b,x,nrit,eps) tablou real a(n,n), b(n), x(n) ntreg nrit real eps initializri a k=0 pentru i=1,n x(i) = 0 ; iteratii repet a err = 0 pentru i=1,n s = b(i) pentru j=1,n s = s a(i, j)x(j) s = (s + a(i, i)x(i))/a(i, i) err = err + (s x(i)) x(i) = s k =k+1 err = sqrt(err) pn cnd (err < eps) sau (k > nrit) a a a retur

; contor iteratii ; initializarea solutiei ; parcurge iteratiile ; eroarea la pasul curent ; parcurge ecuatiile ; parcurge ecuatia i

; x nou ; incrementeaz contor iteratii a


8.4. Analiza algoritmilor

99

Procedurile Jacobi i Gauss-Seidel au parametrii: s de intrare n = dimensiunea sistemului; a(n,n)= matricea sistemului; b(n) = vectorul termenilor liberi; nrit = numrul maxim de iteratii; a eps = eroarea admis; a de ieire x(n) = vectorul solutie. s Pentru a demonstra modul diferit care se poate evalua eroarea, algoritmul Jacobi n n s-a folosit norma Cebsev a erorii, iar algoritmul Gauss-Seidel norma Euclidian. n a

8.4

Analiza algoritmilor

Efort de calcul Pentru o iteratie, ordinul de complexitate al metodelor Jacobi i Gauss-Seidel este s O(n(n + 2)). Efortul de calcul pentru rezolvarea ntregului sistem de ecuatii liniare prin 2 metode iterative este de ordinul O(mn ), care numrul total de iteratii m care vor n a efectuate nu este general cunoscut dinainte. Efortul de calcul depinde de norma n matricei de iteratie, ind cu att mai mic cu ct norma este mai mic. a a a Necesar de memorie Pentru memorarea matricei sistemului, a vectorilor termen liber i solutie sunt necesare s plus, la algoritmul Jacobi mai sunt necesare n locatii pentru n +2n locatii de memorie. In memorarea solutiei obtinute la pasul curent. 2

Dac matricea sistemului este o matrice rar, atunci metodele iterative se dovedesc a a extrem de eciente din punctul de vedere al memoriei, ele negenernd umpleri. a Analiza erorilor Spre deosebire de metodele directe, la care singurele erori care apar sunt cele de rotunjire, la metodele iterative apar i erori de trunchiere prin retinerea din irul convergent s s ctre solutia exact, a unui numr nit de termeni. Datorit convergentei lor, metodele a a a a iterative au proprietatea remarcabil de a corecta erorile de rotunjire aprute pe parcurs. a a Document disponibil la http://mn.lmn.pub.ro

100


Eroarea absolut la itertia k este de cel putin M ori mai mic dect eroarea de la a a a pasul anterior: ek = xk x M xk1 x = M ek1 M k e0 . (8.23)

Se constat c eroarea nal depinde de eroarea initial, de numrul de iteratii efectua a a a a ate i de norma matricei de iteratie, care determin viteza de convergent. Aceeai relatie s a a s k este valabil i pentru reziduul Ax b . as

8.5

Chestiuni de studiat

Rezolvarea unor sisteme de ecuatii liniare prin metodele Jacobi i Gauss-Seidel; s Analiza experimental a erorilor i a efortului de calcul, la metodele Jacobi i Gaussa s s Seidel; Implementarea algoritmilor; Cutare de informatii pe Internet. a

8.6

Mod de lucru

Pentru desfurarea lucrrii se selecteaz lucrarea Metode iterative de rezolvare a sisas a a temelor algebrice liniare din meniul general de lucrri. a Aceasta are ca efect aarea meniului: s 1. Rezolvare de sisteme cu metodele Jacobi/Gauss-Seidel 2. Analiza algoritmilor

8.6.1

Rezolvarea unor sisteme de ecuatii liniare prin metodele Jacobi/Gauss-Seidel

Programul lansat permite rezolvarea unor sisteme liniare prin metode iterative. Se vor introduce: numrul de ecuatii; a LMN, Draft din 30 septembrie 2011

8.6. Mod de lucru

101

elementele a(i, j) ale matricei sistemului; termenii liberi b(i); eroarea admis; a numrul maxim de iteratii admis. a Programul aeaz consola Scilab informatii despre procesul iterativ: dac a fost s a n a convergent sau nu, norma matricei de iteratie, cazul care procesul a fost convergent, n n cte iteratii au fost necesare i care este solutia. a s Se vor introduce parametrii necesari pentru rezolvarea urmtoarelor sisteme: a x1 + x2 = 5 2x1 + 3x2 = 13 : R x1 = 2 x2 = 3

Se va inversa ordinea ecuatiilor i se va comenta efectul asupra solutiei. s

8x1 + 2x2 + x3 = 15 10x1 + 4x2 + x3 = 21 50x1 + 25x2 + 8x3 = 124 2x1 + x2 + x3 = 7 x + 2x2 + x3 = 8 1 x1 + x2 + x3 = 6 3x1 + x3 = 10 x + 2x2 + x3 = 12 1 x1 + x2 + 2x3 = 13

R : x1 = 1 x2 = 2 x3 = 3

R : x1 = 1 x2 = 2 x3 = 3

R : x1 = 2 x2 = 3 x3 = 4

Se va inversa ordinea a dou ecuatii din sistem i se va comenta efectul asupra solutiei. a s Se vor comenta rezultatele obtinute, convergenta metodelor pentru ecare sistem re zolvat. Document disponibil la http://mn.lmn.pub.ro

102


8.6.2

Analiza experimental a algoritmilor a

Se selecteaz optiunea Analiza algoritmilor. Aceasta are ca efect aarea unui meniu cu a s optiunile: Eroarea functie de numrul de iteratii; n a Numrul de iteratii functie de norma matricei de iteratie. a n La selectarea optiunii Eroarea functie de numrul de iteratii, utilizatorul introduce: n a norma matricei de iteratie Jacobi i numrul de ecuatii (valoare initial, valoare nal, s a a a pas). Astfel se apeleaz un program care rezolv, pe baza celor dou metode iterative, a a a sisteme de ecuatii liniare generate aleator. Programul aeaz rezultatele numerice s a n consola Scilab i reprezint grac variatia erorii Cauchy functie de iteratie. Valorile s a n recomandate sunt: norma matricei de iteratie Jacobi 0.5, dimensiunile sistemelor 20, 40, 60. Datele se pot nota ntr-un tabel de tipul: iteratii n = 20 eroare J eroare GS n = 40 eroare J eroare GS n = 60 eroare J eroare GS Se vor reprezenta pe acelai grac erorile functie de numrul de iteratii. Se vor s n a comenta rezultatele obtinute. La selectarea optiunii Numrul de iteratii functie de norma matricei de iteratie a n utilizatorul alege dimensiunea n a sistemului i eroarea de oprire. Programul aeaz s s a numrul de iteratii necesar celor dou metode pentru sisteme generate aleator, de dimena a siune n, avnd norma matricei de iteratie 0.1, 0.2, . . ., 0.9. Datele se pot nota a ntr-un tabel de tipul: norma matricei Jacobi nr. iteratii Jacobi nr. iteratii Gauss-Seidel Se vor reprezenta pe acelai grac numrul de iteratii functie de norma matricei. Se s a n vor comenta rezultatele obtinute. LMN, Draft din 30 septembrie 2011 0.1 0.2 . . . 0.9 1 5 9 13 17

8.7. Exemple

103

8.6.3

Implementarea algoritmilor

Se va implementa pe calculator, limbajul C, o procedur proprie de rezolvare a unui n a sistem de ecuatii liniare, prin una din cele dou metode iterative. Se va compila i testa a s procedura, eliminndu-se eventualele erori. a Se va scrie pseudocodul i se va implementa pe calculator un program principal, care s apeleaz procedura anterioar i rezolv sistemul de ecuatii: a as a 2x + z = 5 R: x=1 x + y + z = 6 y=2 y + 3z = 11 z=3

Acest program va permite introducerea datelor de la consol i aarea pe ecran a a s s solutiei. Se vor nota i comenta rezultatele obtinute i eventualele diculti aprute pe s s at a parcursul lucrului.

8.6.4

Cutare de informatii pe Internet a

Se vor cuta pe Internet informatii (coduri) legate de rezolvarea iterativ a sistemelor a a algebrice de ecuatii prin metode iterative. Cuvinte cheie recomandate: Iterative methods for algebraic systems, Jacobi, Gauss-Seidel.

8.78.7.1

ExempleExemple rezolvatex 2y = 2 3x + 2y = 6 (a) s se determine solutia sistemului de ecuatii pentru primele dou iteratii ale a a (0) (0) metodei Jacobi, cunoscnd solutia initial x = y = 0; a a (b) s se ilustreze grac procesul iterativ i s se comenteze convergenta lui; a s a (c) s se comenteze rezultatele obtinute atunci cnd se schimb ordinea ecuatiilor. a a a Rezolvare: Document disponibil la http://mn.lmn.pub.ro

1. Fie sistemul de ecuatii:

104


(a) Iteratiile metodei Jacobi se calculeaz conform formulelor: a x(k+1) = 2 + 2y (k) 2y (k+1) = 6 + 3x(k) Solutia la prima iteratie este: x(1) = 2 + 2y (0) = 2 (0) y (1) = 6+3x = 3, 2 iar la a doua iteratie: x(2) = 2 + 2y (1) = 2 6 = 8 (1) y (2) = 6+3x = 66 = 6. 2 2 (b) Din punct de vedere geometric, rezolvarea sistemului este echivalent cu gsirea a a punctului de intersectie al dreptelor ecuatiilor, D1 i D2 : s D1 : x 2y + 2 = 0 D2 : 3x + 2y + 6 = 0 Vom reprezenta grac aceste drepte. Dreapta D1 taie axele punctele de n coordonate (0, 1) i (2, 0). Dreapta D2 taie axele punctele de coordonate s n (0, 3) i (2, 0). Dreptele D1 i D2 sunt concurente punctul (4, 3), solutia s s n sistemului de ecuatii. Procesul iterativ este ilustrat gura 1 i se observ c este divergent. Dei n s a a s problema este bine formulat matematic (solutia exist i este unic), metoda a as a Jacobi eueaz. s a Convergenta metodei depinde de proprietile matricei de iteratie. Dac notm at a a 1 A = D + L + U, atunci M = D (L + U) este matricea de iteratie cazul n metodei Jacobi. cazul problemei considerate: In D= 1 0 0 21

, L=

0 0 3 0 =

, U=

0 2 0 0

.

M =

1 0 0 2

0 2 3 0

1 0 0 1 2

0 2 3 0

=

0 2 3 0 2i=1,2

.

unde i sunt valorile proprii, care reprezint solutiile ecuatiei det(M I) = 0. a LMN, Draft din 30 septembrie 2011

Raza spectral (de convergent) a matricei de iteratie M este: (M) = max |i |, a a

8.7. Exemple

105

y D2 000000000000000 111111111111111 000000000000000 111111111111111 00000000000000000000000000000 11111111111111111111111111111 000000000000000 111111111111111 11111111111111111111111111111 00000000000000000000000000000 111111111111111 000000000000000 00000000000000000000000000000D 11111111111111111111111111111 000000000000000 111111111111111 1 0 00000000000000000000000000000 1 11111111111111111111111111111 000000000000000 111111111111111 1 0 11111111111111111111111111111 00000000000000000000000000000 (4,3) 000000000000000 111111111111111 00000000000000000000000000000 11111111111111111111111111111 000000000000000 111111111111111 00000000000000000000000000000 11111111111111111111111111111 000000000000000 111111111111111 00000000000000000000000000000 11111111111111111111111111111 000000000000000 111111111111111 00000000000000000000000000000 11111111111111111111111111111 000000000000000 111111111111111 11111111111111111111111111111 00000000000000000000000000000 111111111111111 000000000000000 00000000000000000000000000000 11111111111111111111111111111 000000000000000 111111111111111 00000000000000000000000000000 11111111111111111111111111111 (0,1) 000000000000000 111111111111111 00000000000000000000000000000 11111111111111111111111111111 000000000000000 111111111111111 11111111111111111111111111111 00000000000000000000000000000 000000000000000 111111111111111 (x 00000000000000000000000000000 11111111111111111111111111111 (2,0) 1 0 0,y0) 000000000000000 111111111111111 0 1 00000000000000000000000000000 11111111111111111111111111111 1 0 000000000000000 111111111111111 0 1 00000000000000000000000000000 11111111111111111111111111111 000000000000000 111111111111111 1 0 11111111111111111111111111111 00000000000000000000000000000 x 0 (2,0) 111111111111111 000000000000000 0 1 00000000000000000000000000000 11111111111111111111111111111 000000000000000 111111111111111 0 1 00000000000000000000000000000 11111111111111111111111111111 000000000000000 111111111111111 0 1 00000000000000000000000000000 11111111111111111111111111111 000000000000000 111111111111111 1 0 00000000000000000000000000000 11111111111111111111111111111 000000000000000 111111111111111 1 0 11111111111111111111111111111 00000000000000000000000000000 000000000000000 111111111111111 0 1 00000000000000000000000000000 11111111111111111111111111111 000000000000000 111111111111111 0 1 00000000000000000000000000000 11111111111111111111111111111 000000000000000 111111111111111 0 (x ,y ) 1 00000000000000000000000000000 11111111111111111111111111111 000000000000000 111111111111111 00 10 11 1 00000000000000000000000000000 11111111111111111111111111111 000000000000000 111111111111111 11111111111111111 00000000000000000 (0,3) 1 0 00 1 11 00000000000000000000000000000 11111111111111111111111111111 000000000000000 111111111111111 1 0 0 1 00000000000000000000000000000 11111111111111111111111111111 000000000000000 111111111111111 1 0 0 1 000000000000000 111111111111111 1 0 1 0 000000000000000 111111111111111 1 0 0 1 000000000000000 111111111111111 1 0 0 1 000000000000000 111111111111111 1 0 0 1 000000000000000 111111111111111 1 0 0 1 000000000000000 111111111111111 1 0 0 1 000000000000000 111111111111111 1 0 0 1 000000000000000 111111111111111 1 0 (x ,y ) 0 1 000000000000000 111111111111111 1 0 2 2 0 1 1111111111111 0000000000000 11 00 000000000000000 111111111111111 1 0 0 1 11 00 000000000000000 111111111111111 1 0 1 0 000000000000000 111111111111111 1 0 1 0 Fig. 1. Proces iterativ divergent al metodei Jacobi cazul studiat: In 3 2

M I =

Valorile proprii sunt 1,2 = 3, iar (M) = max |i| = 3.i=1,2

2

= det(M I) = 2 3 = 0.

Deoarece (M) > 1, procesul iterativ este divergent. (c) cazul care se schimb ordinea ecuatiilor, sistemul de rezolvat este: In n a 3x + 2y = 6 x 2y = 2 Solutia la prima iteratie se calculeaz astfel: a 3x(1) = 6 2y (0) = 2y (1) = 2 x(0) Iar solutia la a doua iteratie este: Document disponibil la http://mn.lmn.pub.ro x(1) = 2 y (1) = 1

106


y D1 111111111111 000000000000 111111111111 000000000000 1111111111111111111 0000000000000000000 111111111111 000000000000 1111111111111111111 0000000000000000000 111111111111 000000000000 1111111111111111111 0000000000000000000 D 111111111111 000000000000 1 0 1111111111111111111 0000000000000000000 2 111111111111 000000000000 1 0 1111111111111111111 0000000000000000000 111111111111 000000000000 (4,3) 1111111111111111111 0000000000000000000 (x 2,y2) 0 111111111111 000000000000 1 1111111111111111111 0000000000000000000 111111111111 000000000000 1 0 1 0 1 00 1111 0000 11 00 1111111111111111111 0000000000000000000 1 0 111111111111 000000000000 1 1 0 0 11 1111111111111111111 0000000000000000000 1 0 111111111111 000000000000 1 1 0 0 1111111111111111111 0000000000000000000 1 0 1 1 0 0 111111111111 000000000000 1111111111111111111 0000000000000000000 111111111111 000000000000 11 1 00 0 111111 1 111 0 000 1111111111111111111 0000000000000000000 (0,1) 000000 111111111111 000000000000 1 0 1111111111111111111 0000000000000000000 111111111111 000000000000 (x ,y1) 1 0 1111111111111111111 0000000000000000000 111111111111 1 1111111111111111111 0000000000000000000 (2,0) 000000000000 1 0 10 111111111111 000000000000 1 0 1111111111111111111 0000000000000000000 1 0 111111111111 000000000000 1 0 1111111111111111111 0000000000000000000 x 111111111111 (x000000000000 1111111111111111111 0000000000000000000 (2,0) 111111111111 000000000000 0,y0) 0 1111111111111111111 0000000000000000000 111111111111 000000000000 1111111111111111111 0000000000000000000 111111111111 000000000000 111111111111 000000000000 111111111111 000000000000 111111111111 000000000000 111111111111 000000000000 111111111111 000000000000 111111111111 000000000000 111111111111 000000000000 (0,3) 111111111111 000000000000 111111111111 000000000000 111111111111 000000000000

Fig. 2. Proces iterativ convergent al metodei Jacobi

3x(2) = 6 2y (1) = 2y (2) = 2 x(1)

8 x(2) = 3 y (2) = 2

Procedeul iterativ este convergent aa cum se observ gura 2. s a n Intr-adevr, pentru acest sistem, matricea de iteratie este: a 1

M =

3 0 0 2

0 2 1 0

=

1 3 0 0 1 2

0 2 1 0

=

01 2

2 3

0

,

iar valorile proprii sunt solutiile ecuatiei: det(M I) = 0 = Deci: 2 1 2 2 3

= 0.

1 1 1 = 0 = 1,2 = = (M) = max |i| = . i=1,2 3 3 3

Deoarece (M) < 1, procesul iterativ este convergent. Aceeai concluzie se poate obtine dac se observ c matricea sistemului este s a a a diagonal dominant (vezi relatia (8.22)). Aceasta este o conditie sucient de a a convergent. a Inegalitatea (8.22) este adevrat pentru cele dou ecuatii ale sistemului: a a a | 3| > |2|, | 2| > |1|,


8.7. Exemple

107

deci matricea sistemului este diagonal dominant, ceea ce este echivalent cu a ||M|| < 1. Pentru orice matrice avem (M) ||M||, astfel c (M) < 1. a 2. Fie sistemul de ecuatii de la exercitiul anterior: x 2y = 2 3x + 2y = 6 (a) s se determine solutia sistemului de ecuatii pentru primele dou iteratii ale a a (0) (0) metodei Gauss-Seidel, cunoscnd solutia initial x = y = 0; a a (b) s se ilustreze grac procesul iterativ i s se comenteze convergenta lui; a s a (c) s se comenteze rezultatele obtinute atunci cnd se schimb ordinea ecuatiilor. a a a Rezolvare: (a) Iteratiile metodei Gauss-Seidel se calculeaz conform formulelor: a x(k+1) = 2 + 2y (k) 2y (k+1) = 6 + 3x(k+1) Solutia la prima iteratie este: x(1) = 2 + 2y (0) = 2 (1) y (1) = 6+3x = 66 = 6, 2 2 iar la a doua iteratie: x(2) = 2 + 2y (1) = 2 12 = 14 (2) y (2) = 6+3x = 642 = 24. 2 2 (b) Procesul iterativ este ilustrat gura 3 i se observ c este divergent. Dei n s a a s problema este bine formul

Metode numerice

Documents

Transcript of Metode numerice