sdgfsge

UNIVERSITATEA VASILE ALECSANDRI din BACU

FACULTATEA DE TIINE

DEPARTAMENTUL MATEMATIC, INFORMATIC I TIINELE EDUCAIEI

SPECIALIZAREA INFORMATIC

FORMA DE NVMNT FRCALCUL NUMERIC

NOTE DE CURS Mihai Talmaciu, Alina-Mihaela PatriciuCuprins Introducere4

Capitolul 1

Erorile de calcul numeric 6

1.1. Surse de erori

6

1.2. propagarea erorilor de calcul

7

1.3. Algoritmi i complexitate de calcul

9

1.4. Metode de programare

11

Capitolul 2

Rezolvarea numeric a ecuaiilor i sistemelor de ecuaii algebrice neliniare13

2.1. Introducere13

2.2. Rezolvarea numeric a ecuaiilor neliniare13

2.2.1. Metoda aproximaiilor succesive14

2.2.2. Metoda Lagrange15

2.2.3. Metoda Newton 16

2.2.4. O teorem de punct fix17

2.2.5. Ordinul metodei22

2.2.6. Accelerarea convergenei24

2.2.6.1. Metoda Aitken24

2.2.6.2. Metoda Steffensen26

2.2.7. Metoda poziiei false28

2.2.8. Principiul dihotomiei30

2.3. Rezolvarea numeric a sistemelor neliniare31

2.3.1. Metoda aproximaiilor succesive31

2.3.2. Metoda Newton33

2.4. Exerciii35

Capitolul 3

Rezolvarea sistemelor algebrice liniare36

3.1. Introducere36

3.2. Metode directe36

3.2.1. Metoda de eliminare a lui Gauss

37

3.2.2. Factorizarea LU40

3.2.3. Factorizarea Cholesky42

3.3. Metode iterative43

3.3.1. Metoda iterativ Jacobi44

3.3.2. Metoda iterativ Gauss-Seidel46

3.3.3. Metoda relaxrii48

3.4. Exerciii48

Capitolul 4

Rezolvarea numeric a problemelor algebrice de valori i vectori proprii50

4.1. Abordarea elementar a subiectului50

4.2. Aspecte teoretice generale51

4.2.1. Clase speciale de matrici51

4.2.2. Punerea corect a problemei54

4.3. Metoda lui Jacobi55

4.4. Probleme de valori proprii generalizate61

4.5. Exerciii62

Capitolul 5

Aproximarea funciilor prin polinoame63

5.1. Introducere63

5.2. Aproximarea prin interpolare63

5.2.1. Interpolarea polinomial Lagrange64

5.2.2. Algoritmul Aitken66

5.2.3. Evaluarea restului la interpolarea Lagrange68

5.2.4. Diferene divizate70

5.2.5. Formula lui Newton de interpolare71

5.2.6. Diferene finite73

5.2.7. Formule de interpolare pe noduri echidistante73

5.2.8. Interpolarea polinomial Hermite75

5.2.9. interpolarea prin funcii spline77

5.3. Aproximarea n sensul celor mai mici ptrate79

5.3.1. Problema fundamental a aproximrii liniare79

5.3.2. Teoreme fundamentale80

5.3.3. Aproximarea discret n sensul celor mai mici ptrate81

5.4. Exerciii83

Capitolul 6

Rezolvarea ecuaiilor difereniale ordinare de ordinul I84

6.1. Introducere84

6.2. Metode85

6.2.1. Metoda Euler85

6.2.2. Metoda Euler backward85

6.3. Generalizri86

6.3.1. Metode Runge Kutta86

6.3.1.1. Metoda clasic Runge Kutta de ordin 486

6.3.1.2. Metode Runge Kutta explicite87

6.3.1.3. Metode Runge Kutta ajustative

6.3.1.4. Metode Runge Kutta implicite88

6.3.2. Caracteristici88

6.4. Metode alternative89

Capitolul 7 Integrarea numeric91

7.1. Introducere91

7.2. Integrarea n puncte echidistante97

7.2.1. Formulele Newton Cotes97

7.2.2. Metoda dreptunghiurilor99

7.2.3. Regula trapezului100

7.2.4. Metoda Romberg101

7.2.5. Regula Simpson102

7.2.6. Metoda ajustativ Simpson104

7.3. Integrarea n puncte neechidistante105

7.3.1. Cvadratura gaussian105

7.3.2. Cvadratura tanh sinh109

7.3.3. Cvadratura Clenshaw Curtis110

7.3.4. Cvadratura Fejer113

7.3.5. Cvadratura ajustativ113

7.4. Integrarea cu funcii pondere115

7.5. Metoda Nystrom116

7.6. Formula Euler MacLaurin116

7.7. T - integrarea121

Bibliografie123

Fia disciplinei124

Introducere Ultimele decenii au fost marcate de progresul mijloacelor de calcul. Asistm la o competiie ntre dezvoltarea tehnologic i dezvoltarea aplicaiilor, n particular, a celor numerice. Tehnica de calcul a devenit accesibil pentru categorii tot mai largi de utilizatori. Globalizarea accesului la magistralele informaiilor organizate n reeaua Internet a dat o nou dimensiune utilizrii calculatoarelor, revoluionnd domenii ntregi de activitate.

Obiectul calculului numeric l reprezint gsirea unor metode de aproximare eficient a soluiilor problemelor care pot fi exprimate prin modele matematice, eficien ce depinde de precizia cerut pentru rezultate i de uurina implementrii. Calculul numeric este una dintre disciplinele matematice ce depinde n cea mai mare msur de calculatorul numeric.

Drumul parcurs pentru rezolvarea unei probleme dintr-un domeniu oarecare cu ajutorul calculatorului const n: stabilirea unui model matematic al problemei concrete (model ce se poate ncadra ntr-o categorie cum ar fi: o ecuaie neliniar, un sistem de ecuaii liniare sau neliniare), care fiind de multe ori de natur continu trebuie discretizat; soluia problemei discretizate trebuie s fie consistent i stabil (robust); modelul discretizat trebuie transpus ntr-un algoritm realizabil i eficient, descris de obicei ntr-un limbaj de programare evoluat.

Calculul numeric opernd cu mrimi variate presupune folosirea tipului real a crui reprezentare n calculator este aproximativ, aprnd erori de rotunjire care se propag. Deci, o metod numeric trebuie aleas innd seama de convergen, stabilitate, propagarea erorilor i de analiza complexitii algoritmului asociat.

Pentru parcurgerea i utilizarea unui asemenea material, cititorul are nevoie de cunotine de matematic la ndemna studenilor care au promovat primul an de studiu al oricrei faculti cu profil tehnic, matematico-informatic sau economic.

Metodele numerice sunt prezentate n detaliu, prin discutarea aspectelor de ordin strict matematic i descrierea algoritmilor cu ajutorul unui limbaj de tip pseudocod.

Lucrarea Calcul numeric are apte capitole.

Primul capitolul are un caracter eterogen la nceput se prezint sursele de erori i propagarea lor, apoi algoritmi i complexitate de calcul, iar n final, metode de programare.

Capitolul al doilea are ca obiect rezolvarea numeric a ecuaiilor i sistemelor de ecuaii algebrice neliniare. Sunt prezentate metode de localizare a soluiei, de aproximaii succesive i de accelerare a convergenei pentru ecuaii neliniare, precum i metode numerice de rezolvare a sistemelor algebrice neliniare.

Capitolul al treilea este dedicat rezolvrii numerice a sistemelor algebrice liniare. Sunt examinate metode directe bazate pe factorizarea gaussian, precum i metode de aproximare.

n capitolul al patrulea se prezint metode de tip Jacobi de rezolvare numeric a problemelor algebrice de valori i vectori proprii, precum i generalizarea lor.

n capitolul al cincilea se prezint aproximarea funciilor prin interpolare de tip Lagrange, Hermite i prin funcii spline, precum i aproximarea n sensul celor mai mici ptrate.

n cel de al aselea capitol sunt prezentate cteva metode numerice de rezolvare a ecuaiilor cu derivate pariale, iar n utimul capitol sunt prezentate diferite metode pentru integrarea numeric.Capitolul 1Erorile de calcul numeric

Obiectivul capitolului

nsuirea unor noiuni referitoare la erorile de calcul numeric, algoritmi i complexitate de calcul, metode de programare.Cuvinte cheie: algoritmi, complexitate de calcul, metode de programare.1.1. Surse de erori

Suntem n posesia unui numr suficient de mare de metode numerice pentru a considera mai n detaliu problema erorilor de calcul numeric. Se observ c o formul de calcul numeric se aplic de obicei n mod repetat. n consecin, prezint importan nu numai eroarea introdus ntr-o etap, ci i tendina de a amplifica sau, dimpotriv, de a atenua erorile introduse anterior, adic stabilitatea metodei numerice.

Erorile inerente sunt erorile legate de cunoaterea aproximativ a unor valori provenite din msurtori sau din faptul c avem de-a face cu numere iraionale. Rezultatul oricror calcule depinde i de precizia datelor introduse iniial. Ca erori inerente pot fi considerate i erorile de conversie fcute la trecerea n baza 2 a unor numere care se introduc n memoria calculatoarelor numerice. De exemplu, numrul 0.1 reprezentat printr-un numr finit de zecimale n baza 10, devine o fracie zecimal periodic n baza 2 (0.110 = 0.0(0011)2).

Erorile de metod sau erorile de trunchiere sunt provenite din aproximaiile fcute la deducerea formulelor de calcul. De exemplu, restul la interpolarea polinomial, distana la rdcin, din metodele iterative de calcul, etc. spre deosebire de erorile inerente, erorile de metod pot fi reduse, n principiu, orict de mult.

Erorile de rotunjire sunt legate de posibilitile limitate de reprezentare a numerelor n calculatoarele numerice. n calculator se pot reprezenta numere cu un numr de cifre semnificative n funcie de lungimea cuvntului (msurat n bii) utilizat la stocarea unui numr.

n memoria intern a unui calculator numeric se folosete reprezentarea n virgul mobil, n form normalizat. Orice numr real x se scrie

,

unde m este un numr real numit mantis, () este baza sistemului de numeraie, iar e (ntreg) este exponentul.

n forma normalizat, mantisa este cuprins n intervalul ().

Excepia de la aceast regul de reprezentare este numrul zero.

Deci, un numr real cu mai multe cifre semnificative este rotunjit la numrul de cifre maxim, lucru care se realizeaz prin rotunjirea mantisei. Alte rotunjiri se fac n decursul operaiilor.

Notnd cu x valoarea exact a numrului i cu valoarea calculat (aproximativ), eroarea absolut se definete ca

,

iar raportul se numete eroare relativ, notat cu ,

.

Fie k numrul de cifre semnificative. Presupunem c b = 10. Atunci, un numr x se va scrie

, ,

unde n conine cifrele care nu pot incluse n mantisa m.

Rotunjirea se face simetric (de obicei), adic se nlocuiete

dac , dac .

n acest fel marginea erorii relative este

.

Erorile cu marginea dat mai sus se fac la introducerea numerelor reale n memoria calculatorului numeric.

1.2. propagarea erorilor de calcul

Fie dou numere, x i y, introduse cu erorile , respectiv . , .

Propagarea erorilor la adunare

Presupunem c se efectueaz suma numerelor

,

astfel nct eroarea relativ la sumare este

,

adic o sum ponderat a erorilor introduse la reprezentarea n calculator a cantitii sumate. Notm cu eroarea introdus suplimentar la reprezentarea sumei . Eroarea relativ total la sumare, , va fi

.

Propagarea erorilor la scdere

Presupunem c se efectueaz scderea numerelor

,

astfel nct eroarea relativ la scdere este

,

adic o diferen ponderat a erorilor introduse la reprezentarea n calculator a diferenei. Notm cu eroarea introdus suplimentar la reprezentarea diferenei . Eroarea relativ total la scdere, , va fi

.

Fie , i . S se calculeze .

Avem , , deci

, .

.

Aceast eroare relativ a lui se propag n toate calculele ulterioare.

Propagarea erorilor la nmulire

Presupunem c se efectueaz produsul numerelor

,

unde s-a neglijat produsul considerat ca avnd un ordin de mrime suficient de mic. Eroarea la nmulire este

.

Deci la nmulire erorile relative introduse iniial se adun. Pot aprea noi erori, deoarece produsul xy poate avea un numr de cifre semnificative mai mare dect cel admis, necesitnd o nou rotunjire. Notnd cu aceast nou eroare, vom obine eroarea relativ total la nmulirea a dou numere

,

iar ca margine a erorii , acoperitoare deoarece erorile se compun dup legi probabilistice.

Eroarea total la calculul expresiei a crei valoare aproximativ este este

,

cu mrginirea

.

Propagarea erorilor la mprire

Presupunem c se efectueaz mprirea numerelor

.

Deoarece seria este convergent, exprimnd-o liniar, obinem

.

Eroare la mprire este

.

Notnd cu noua eroare datorat mpririi i cu eroarea total la mprirea a dou numere obinem .

1.3. Algoritmi i complexitate de calcul

Procesele de prelucrare automat a informaiei se caracterizeaz prin natura lor algoritmic i faptul c sunt efectuate cu ajutorul unor maini automate de calcul. Calculatoarele electronice sunt capabile s rezolve problemele de calcul descompuse n operaii elementare, precizndu-se succesiunea operaiilor. Din aceast perspectiv, prin algoritm se nelege o mulime finit de reguli de calcul (care constituie paii algoritmului), care indic operaiile elementare necesare rezolvrii unei probleme i ordinea efecturii lor. Orice algoritm pornete de la datele iniiale, pe care le prelucreaz n vederea obinerii rezultatului problemei. Algoritmii se caracterizeaz prin generalitate, finitudine i unicitate. Oricrei probleme care admite o formulare matematic i se poate asocia un algoritm de rezolvare, care nu se confund nici cu formularea matematic i nici cu reprezentarea sub form unui program ntr-un limbaj de programare. Printre cele mai utilizate metode de descriere a algoritmilor se numr reprezentarea prin scheme logice i cea cu ajutorului limbajelor de tip pseudocod. n capitolele urmtoare vom folosi pentru descrierea algoritmilor un limbaj de tip pseudocod, iar n seciunile 1.4 i 1.5 a acestui capitol vom prezenta, pe scurt, cteva din metodele de programare i cteva din elementele limbajului de programare C n vederea implementrii algoritmilor n acest limbaj de programare. Algoritmii prezentai sunt exprimai ntr-un pseudocod care posed urmtoarele operaii simple: atribuirea (variabil ( expresie), apelul de procedur (funcie) (execut nume (list_parametri)), citirea (citete list_variabile), scrierea (scrie list_expresii) i n urmtoarele structuri de control: secvena ({instruciune_1 ... instruciune_n}), selecia unar (dac condiie atunci instruciune), selecia binar (dac condiie atunci instruciune_1 altfel instruciune_2), selecia multipl (alege selector dintre valoare1:intruciune1 valoaren:instruciunen), iteraia cu numr prestabilit de ciclri (pentru contor ( expresie_1:expresie_2 repet instruciune), iteraia pretestat (ct timp condiie repet instruciune), iteraia posttestat (repet instruciune pn cnd condiie).

Vom nelege prin problem algoritmic o funcie total definit , unde I este mulimea informaiilor iniiale (intrrile problemei) iar F este mulimea informaiilor finale. Presupunem c I i F sunt cel mult numrabile. Dac este precizat, atunci determinarea lui se numete o instan a problemei P. Vom folosi pentru o instan notaia p i prin abuz de notaie vom scrie . Un algoritm care rezolv problema P va porni de la o codificare a unei instane oarecare a problemei P i va oferi o codificare a rezultatului.

Din multitudinea de algoritmi existeni pentru rezolvarea unei probleme se va alege cel mai performant, adic s fie uor de neles, codificat, modificat, depanat i s utilizeze n mod eficient resursele. Eficiena unui algoritm este evaluat prin timpul consumat n unitatea central i memoria ocupat, iar pentru algoritmii cu specific numeric mai sunt considerai i factori precum precizia i stabilitatea numeric. Deoarece analizm performanele unui algoritm i nu performanele unor calculatoare i nici software-ul folosit, vom exprima timpul consumat n numr de operaii (n virgul mobil). Vom nota prin numrul de operaii efectuate de algoritmul A pentru rezolvarea instanei p i vom asocia problemei rezolvate un numr numit dimensiunea problemei reprezentnd numrul datelor de intrare.

Resursa timp se exprim ca o funcie de dimensiunea problemei, funcie numit complexitatea n timp a algoritmului . Aceast funcie este polinomial sau exponenial, iar dac dimensiunea problemei crete la infinit se obine complexitatea asimptotic n timp a algoritmului. Comportarea n cazul cel mai nefavorabil a algoritmului A pe o intrare de dimensiune n este

i ,

iar comportarea medie a algoritmului este

i

(adic media variabilei aleatoare ).

Deoarece determinarea exact a lui este dificil vom cuta margini superioare i inferioare pentru . Pentru funcia ,

.

Vom spune c P are complexitatea dac exist un algoritm A care rezolv problema P i are complexitatea . O problem P are complexitatea dac orice algoritm A care rezolv problema P are complexitatea . Un algoritm A cu , unde p este un polinom n n, se numete polinomial. Un algoritm care nu este polinomial se numete exponenial. Astfel algoritmii cu complexitate exponenial sunt irealizabili, n timp ce algoritmii polinomiali de grad mai mare dect 2 sunt nepractici. Importana practic a acestora rezult i din urmtorul exemplu. Presupunem c un pas necesit secunde, adic secunde, atunci pentru n = 40,

un algoritm cu funcia de complexitate n necesit 0.00004 secunde,

un algoritm cu funcia de complexitate necesit 1.7 minute,

un algoritm cu funcia de complexitate necesit 129 ani (!).

1.4. Metode de programare

Vom prezenta un scurt istoric al unor metode de programare, dar nu exhaustiv. Am considerat necesar acest lucru, n vederea implementrii ulterioare, n limbaje de evoluate de programare, a algoritmilor prezentai n lucrare. O clasificare cronologic ar fi urmtoarea: programarea artizanal, procedural, modular, structurat, prin abstractizarea datelor i orientat pe obiecte.

Programarea artizanal este prima modalitatea de programare, n care iniiativa i experiena programatorului joac un rol important, fiecare programator i are propriile reguli de programare, iar programele au un singur corp de instruciuni, sunt lungi i greu de neles.

Programarea procedural are la baz utilizarea procedurilor (care se mai numesc i subprograme sau subrutine uniti distincte de program) care trebuie parametrizate cu anumite variabile numite parametri formali a cror valori de apel se numesc parametri efectivi. Procedurile realizeaz o abstractizare prin parametri (ele trebuie s fie generale deci procesarea s fac abstractizare de valorile datelor). La apelare o procedur funcioneaz dup principiul cutiei negre (se cunosc intrrile i ieirile, rezultatele din acestea dar nu i modul de transformare). Sunt proceduri care definesc o valoare de revenire (numite i funcii) i proceduri care nu definesc o valoare de revenire.

Programarea modular are la baz elaborarea programelor pe module. O colecie de funcii nrudite (funciile obinute n urma programrii unei subprobleme component a descompunerii arborescente a problemei date n subprobleme mai simple), mpreun cu datele pe care le prelucreaz n comun formeaz un modul. Deoarece o parte din datele utilizate n comun de funciile modulului nu sunt necesare i n alte module ele sunt protejate (ascunse n modul).

Programarea structurat. descompunerea unei probleme n subprobleme mai simple se face succesiv n mai multe etape, pn cnd subproblemele sunt direct programabile sub forma unor proceduri sau module. Aceast descompunere, numit rafinare pas cu pas, este o descompunere arborescent. n cadrul procedurilor se folosesc anumite structuri de control a execuiei. Prelucrarea de baz n cadrul acestor structuri de control este cea de atribuire. Aceast abordare a programrii s-a nscut din necesitatea eliminrii saltului necondiionat, determinndu-l pe Dijsktra s impun D-structurile de control: secvena (n care prelucrrile se execut n ordinea scrierii lor);

iteraia pretestat (ct timp o condiie este adevrat execut o prelucrare, prelucrare ce trebuie s modifice valoarea de adevr a condiiei);

alternativa simpl (dac o condiie este adevrat execut o prelucrare).

S-a demonstrat (Bohm i Jacopini) c orice algoritm se poate descrie doar cu D-structurile, dar pentru o mai bun lizibilitate i nelegere a programelor surs s-au adugat i iteraia posttestat, iteraia cu un numr prestabilit de ciclri, alternativa binar i alternativa generalizat.

Programarea prin abstractizarea datelor propune metodologii n care conceptele deduse din analiza problemei s poat fi reflectate ct mai fidel n program. n general un tip abstract de date are dou componente: datele membru care reflect reprezentarea tipului i funciile membru care reflect comportamentul tipului.

Programarea orientat spre obiecte. n cadrul structurilor ierarhice, unde conceptele sunt strns legate ntre ele, nu este suficient doar legtura dintre concepte n care datele membru ale unei clase pot fi obiecte ale unei alte clase. Exprimarea ierarhiilor conduce la atribute suplimentare cum sunt cele de motenire, atribute care conduc la un model nou de programare numit programare orientat obiect. n vrful ierarhiei se afl fenomenul sau forma de existen care are trsturi comune pentru toate celelalte componente ale ierarhiei respective. Pe nivelul urmtor al ierarhiei se afl componente care pe lng trsturile comune de pe nivelul superior, mai au trsturi specifice. O ierarhie are, de obicei, mai multe nivele, iar situarea unui element pe un nivel sau altul al ierarhiei este uneori o problem complex.

Discuii finale:

S se discute despre erorile de calcul numeric, despre algoritmi i complexitate de calcul, despre metode de programare.

Tema propus:

S se fac o lucrare despre erorile de calcul numeric, despre algoritmi i complexitate de calcul, despre metode de programare.

Capitolul 2

Rezolvarea numeric a ecuaiilor i sistemelor de

ecuaii algebrice neliniareObiectivul capitoluluinsuirea unor noiuni referitoare la metodele Newton, Aitken, Steffensen, falsei poziii.

Cuvinte cheie: metode numerice.2.1. Introducere

Forma general a unei ecuaii (sistem de ecuaii) algebrice neliniare este:

unde f este o funcie vectorial pe , , cu n componente: , iar x este vectorul necunoscutelor cu n componente . Pentru , notnd , avem o ecuaie algebric neliniar sau transcendent, cu o necunoscut.

2.2. Rezolvarea numeric a ecuaiilor neliniare

Fie o funcie dat (n anumite cazuri, f va fi o funcie de la C la C).

Presupunnd c avem funcia real de argument real

,

orice valoare pentru care se numete rdcin (soluie) a ecuaiei sau zero al funciei f (x).

n general, prin rdcin aproximativ a ecuaiei se nelege o valoare apropiat de valoarea exact . O rdcin aproximativ poate fi definit n dou moduri: numrul cu proprietatea sau, numrul cu proprietatea .

S se gseasc una sau mai multe soluii ale ecuaiei . Presupunem c f este o funcie continu i cu ajutorul, fie matematic, fie experimental, se va determina un interval [a,b] n care ecuaia are o rdcin i numai una care se va nota cu .

2.2.1. Metoda aproximaiilor succesive

Metoda const n construirea unui ir de aproximaii succesive (ir de iterare) a lui , rdcina exact a ecuaiei , de forma:

= aproximaia iniial (dat);

,

care s tind la .

Pentru a genera acest ir, se nlocuiete ecuaia printr-o ecuaie echivalent, n intervalul considerat, , unde g este o funcie continu. De exemplu, sau cu . Apoi, plecnd de la ales n [a,b], se construiete:

Geometric, se nlocuiete cutarea interseciei graficului funciei f cu axa absciselor, prin cutarea interseciei curbei de ecuaie cu dreapta de ecuaie .

Exist numeroase moduri de a obine metoda de aproximaii succesive, adic de a determina g plecnd de la f.

n acest sens sunt necesare rspunsuri la ntrebrile:

i) irul este convergent?

ii) dac irul converge, limita sa este ?

Dac nu-i convergent atunci metoda aleas trebuie eliminat. Dac (unde , deoarece i cum g este o funcie continu urmeaz c , adic ) atunci . Deci rspunsul la ntrebarea ii) este orice ir.

Deoarece, din punct de vedere numeric se efectueaz un numr finit de iteraii, este necesar s ne preocupe i urmtoarele probleme:

iii) dac precizia este dat atunci este necesar s se cunoasc cum se opresc iteraiile astfel nct aceast condiie s fie ndeplinit.

iv) deoarece se cere obinerea rapid a rezultatului aproximativ, este necesar s fie estimat maniera n care evolueaz eroarea n cursul iteraiilor.

Metoda aproximaiilor succesive conduce la urmtorul algoritm.

Algoritmul 2.2.1.1.

Intrri: g = funcia din relaia

= precizia

x = aproximaia iniial

nr_max = numrul maxim de iteraii admis

ieiri: x = soluia aproximativ ndeplinind sau nr_max

{

ct timp i nr_max

{

}

}.

Pentru a detecta timpuriu procesele divergente i a nu parcurge n mod inutil numrul maxim de iteraii nr_max, imediat dup ce este calculat noua valoare a funciei g (care cu semn schimbat nseamn corecia rdcinii) este comparat cu corecia din pasul anterior (pstrat). Dac corecia crete n valoare absolut procesul este divergent.

Dm cteva metode clasice a metodei aproximaiilor succesive.

2.2.2. Metoda Lagrange

Metoda Lagrange se mai numete i metoda de pri proporionale i const n nlocuirea graficului funciei f restrns la un interval [a,b] prin dreapta determinat de punctele i . Dreapta are ecuaia:

.

Dac este intersecia dreptei AB cu axa absciselor atunci:

.

Presupunnd c atunci i repetnd procedeul de mai sus, nlocuind b cu obinem:

.

n general avem unde funcia g este definit prin

, sau

.2.2.3. Metoda Newton

Metoda Newton se mai numete i metoda tangentei i const n nlocuirea graficului funciei f restrns la un interval [a,b] prin tangenta ntr-un punct al graficului.

Tangenta la curb n punctul are ecuaia:

.

Dac este intersecia acestei tangente cu axa absciselor atunci:

.

Se rencepe procedeul precedent cu tangenta n punctul , n general se obine:

unde .

Remarca 2.2.3.1. Metoda lui Newton este bine definit dac . Este suficient ca s fie un zero simplu al lui f, cci, dac este continu i suficient de aproape de vom avea .

Metoda Newton conduce la urmtorul algoritm.

Algoritmul 2.2.3.1.

Intrri: f = funcia din metod

fd = derivata funciei f

= precizia

nr_max = numrul maxim de iteraii admis

x = aproximaia iniial

ieiri: x = soluia aproximativ ndeplinind sau nr_max

{

ct timp i nr_max

{

}

}.

Dac pe parcursul procesului iterativ se anuleaz derivata funciei atunci se execut o iteraie de salvare n care corecia rdcinii se calculeaz fr a o mpri la derivata funciei. Aceast abordare are avantajul c rezolv i zerourilor de ordin superior, n care funcia i prima ei derivat au zerouri comune.

2.2.4. O teorem de punct fix

n exemplele precedente, avem urmtoarea situaie:

dat

.

Problema care se pune este de a alege o metod, deci funcia g astfel nct irul s fie convergent la .

Este necesar ca soluia ecuaiei n intervalul [a,b] s fie aceeai cu soluia ecuaiei n intervalul [a,b].

Are loc urmtorul rezultat:

Teorema 2.2.4.1. Dac n intervalul [a,b] funcia g verific urmtoarele condiii:

a) pentru orice are loc ;

b) g este o aplicaie strict contractant, adic exist un numr real L: astfel nct pentru , avem:

atunci, oricare ar fi irul definit prin

converge spre unica soluie a ecuaiei cu .

Demonstraie.

Dac i sunt dou soluii distincte ale ecuaiei urmeaz c

cu .

Deci . Deoarece obinem = .

Avem

.

Deci sau

Deci

Deoarece urmeaz c pentru .

Deoarece irul verific criteriul lui Cauchy urmeaz c el este convergent spre limita sa i cum g este funcie continu, deoarece este strict contractant, aceast limit verific .

Dac atunci . Deoarece elementele irului aparin intervalului [a,b] (deoarece ) i converge, urmeaz c limita sa aparine intervalului [a,b].

Se poate evalua eroarea fcnd p s tind spre :

.

Se constat c pentru n fixat, eroarea este cu att mai mic cu ct L se apropie de zero, n timp ce, dac L este apropiat de 1 eroarea se diminueaz.

Dac g este o funcie derivabil atunci o condiie suficient astfel nct g s fie strict contractant este urmtoarea.

Propoziia 2.2.4.1. Fie g o funcie derivabil n [a,b]. Dac verific atunci g este o aplicaie strict contractant n intervalul [a,b].

Utiliznd formula creterilor finite:

cu ,

unde .

Condiia a) din teorema precedent trebuie s fie ndeplinit.

ntr-adevr. Pentru funcia , unde , , , dar ecuaia nu are punct fix n intervalul considerat, deoarece.

Intervalul [a,b] n care ipotezele teoremei de punct fix sunt verificate este, n general greu de determinat.

Dac se poate calcula (estima) atunci are loc urmtorul rezultat.

Propoziia 2.2.4.2. Fie o soluie a ecuaiei cu funcie continu. Dac atunci exist un interval [a,b] coninnd pentru care irul definit prin i converge la .

Demonstraie.

Fie . Atunci, din continuitatea lui , exist un interval coninnd pentru care

i .

Funcia g restrictiv la intervalul [p, q] este strict cresctoare i verific .

Artm c dac atunci . Deoarece , este suficient s artm c .

Deoarece urmeaz c , adic .

Similar, deoarece urmeaz c .

Deci .

Lund , avem verificate ipotezele teoremei de punct fix.

Fie . Atunci exist un interval astfel nct

i .

Se arat i n acest caz c sunt verificate ipotezele teoremei de punct fix.

irul converge la din .

Dm fr demonstraie urmtorul rezultat.

Propoziia 2.2.4.3. Fie o soluie a ecuaiei . Dac este continu ntr-o vecintate a lui i , , irul definit de i nu converge spre .

Dac atunci irul poate converge sau diverge.

Exemplu. S se gseasc condiia care asigur existena unui interval [a,b], coninnd , n care ipotezele teoremei de punct fix sunt verificate pentru:

1) metoda aproximaiilor succesive;

2) metoda lui Lagrange;

3) metoda lui Newton.Rezolvare.

1) Fie funcia g definit prin . Dac f este derivabil atunci . Condiia devine , adic .

2) Fie , i funcia g definit prin

.

Dac f este derivabil avem

,

de unde

,

deoarece .

Dar

cu ,

de unde

.

Deci devine .

3) Fie , i funcia g definit prin

.

Dac exist atunci .

Deci .

Deci exist totdeauna un interval n care ipotezele teoremei de punct fix sunt verificate, n cazul metodei tangentei.

Este mai uoar aplicarea metodei Newton apelnd la rezultatul urmtor.

Teorema 2.2.4.2. Dac verific

(1)

(2)

,

(3)

,

atunci alegnd astfel nct , irul definit prin i converge spre unica soluie a ecuaiei n intervalul .

Demonstraie.

Condiiile (1), (2) i (3) asigur existena i unicitatea unei rdcini simple n [a,b] a ecuaiei .

Deoarece

urmeaz c

cu cuprins ntre i .

Deci

,

adic

.

Dac i sunt de acelai semn pe [a,b] atunci pentru , , irul este minorat de plecnd de la rangul 1.

Dac i sunt de semne contrare pe [a,b] atunci pentru , , irul este majorat de plecnd de la rangul 1.

1) Fie pentru . Din ipotez urmeaz c .

a) Fie . Atunci irul este minorat de plecnd de la rangul 1.

Cum urmeaz c , .

Deoarece nu se anuleaz dect pentru , oricare din termenii irului sunt mai mari dect urmeaz c este de acelai semn cu , deci pozitiv.

Deci

.

irul este descresctor, minorat, deci convergent la .

b) Fie . Atunci irul este majorat de plecnd de la rangul 1.

Cum urmeaz c , .

Deoarece nu se anuleaz dect pentru i oricare din termenii irului sunt mai mici dect urmeaz c este de acelai semn cu , deci pozitiv.

Deci

.

irul este cresctor, majorat, deci convergent la .

2) Fie pentru . Demonstraia este similar cu cea de la punctul 1).

2.2.5. Ordinul metodei

n afar de convergen, trebuie s tim ct de rapid este convergena irului definit prin , adic cum se diminueaz eroarea n urmtoarea iteraie.

Aceasta ne conduce la urmtoarea definiie a ordinului metodei.

Definiia 2.2.5.1. Metoda definit prin este de ordin p, dac are limit n mulimea numerelor reale strict pozitive cnd n tinde spre .

Explicaia acestei definiii.

sau

.

Metoda este, deci, de ordinul p, dac i numai dac:

i .

Metoda aproximaiilor succesive este de ordinul 1 (adic convergena este liniar)

ntr-adevr. Se cunoate, din exemplul 1, c .

Dac atunci metoda Lagrange este de ordinul 1.

Rezult imediat din exemplul 2.

Metoda lui Newton este de ordinul cel puin 2.

Teorema 2.2.5.1.

Dac este un zero simplu atunci metoda Newton este de ordinul cel puin doi.

Verificare.

Avem .

Deoarece

urmeaz c .

Dac este un zero simplu al lui f atunci .

Dac atunci altfel ordinul metodei este mai mare dect 2.

Pentru metodele de ordinul doi se mai spune nc: convergen este ptratic.

Ordinul depinde att de metoda aleas ct i de natura zeroului.

Propoziia 2.2.5.1. Dac este un zero al lui f de multiplicitate m, metoda iterativ definit prin cu este de ordinul cel puin doi.

Verificare.

n loc s considerm ecuaia care admite ca soluie de multiplicitate m, se poate lua care admite ca soluie simpl.

Metoda Newton este atunci definit prin:

cu ,

adic

.2.2.6. Accelerarea convergenei

2.2.6.1. Metoda Aitken

Remarca 2.2.6.1.1. n metoda aproximaiilor succesive i metoda Lagrange eroarea este de forma

,

unde:

, i .

Verificare.

n metoda aproximaiilor succesive:

, , ,

, .

,

.

.

Din exemplul 1 urmeaz c .

n metoda Lagrange:

.

Din exemplul 2 urmeaz c , unde cu .

, ,

.

Fie .

.

.

Dac presupunem atunci

Deci

,adic

.

Deci

Adic, dac atunci soluia se obine numai dup dou iteraii succesive.

Fie . Este de ateptat ca irul definit prin:

s aproximeze mai bine rdcina dect .

Teorema 2.2.6.1.1. Dac este un ir care converge la avnd ordinul de convergen unu atunci irul definit prin converge mai repede, adic .

Demonstraie.

Deoarece are ordinul de convergen unu avem cu i . Deci

cu

.

Deci .

La fel, .

Deci

Deci .

Metoda definit de se numete metoda lui Aitken.2.2.6.2. Metoda Steffensen

Dac se aplic procedeul de accelerare a convergenei al lui Aitken irului definit prin avem c este o aproximare mai bun a lui dect . Este, deci, natural s continum nlocuind cu , apoi de a calcula i pentru a aplica accelerarea lui Aitken.

Aceasta revine la a calcula succesiv:

deci

.

Se poate defini n funcie de plecnd de la g:

ceea ce se poate scrie:

.

Aceasta este metoda Steffensen, care se poate defini formal prin funcia G care d procesul iterativ:

.

Are loc urmtorul rezultat:

Teorema 2.2.6.2.1.

Fie o rdcin simpl a ecuaiei .

Dac metoda generat de g este de ordinul unu atunci metoda Steffensen este de ordinul cel puin doi.

Dac metoda generat de g este de ordinul atunci metoda Steffensen este de ordinul .

Demonstraie.

Pentru , n vecintatea lui , avem

.

Notnd cu avem

.

Dac ordinul metodei este 1, adic , deoarece

atunci

dac .

Deci metoda Steffensen este de ordinul cel puin 2.

Dac ordinul metodei este , adic atunci

,

,

,

adic metoda Steffensen este de ordinul .

Metoda Steffensen furnizeaz urmtorul algoritm.

Algoritmul 2.2.6.2.1.

Intrri: g = funcia din metoda neaccelerat

= precizia

nr_max = numrul maxim de iteraii admis

x = aproximaia iniial

ieiri: x = soluia aproximativ ndeplinind sau nr_max

{

ct timp i nr_max

{

}

}.

2.2.7. Metoda poziiei false

Metoda Newton prezint inconvenientul de a calcula derivata lui f. Se poate ca aceast derivat s fie dificil de calculat. Atunci, se nlocuiete derivata printr-o aproximaie n funcie de valori ale lui f.

De exemplu

.

Aceasta este metoda falsei poziii (corzii).

Atunci avem

,

.

Se remarc c se obine n funcie de i i nu numai n funcie de , ca n cazul metodelor precedente.

Dac se compar cu metoda Lagrange definit prin:

se remarc c metoda poziiei false se obine din metoda Lagrange nlocuind a cu .

Se poate, deci, prevedea c ordinul metodei poziiei false va fi mai bun dect al metodei Lagrange, dar mai puin bun dect al metodei Newton.

Are loc

Teorema 2.2.7.1.

Ordinul metodei poziiei false este

,

dac i .

Demonstraie.

Avem:

,

.

Dac i atunci

.

Atunci:

EMBED Equation.3 .

Pentru n tinznd spre infinit urmeaz c , unde .

Ordinul metodei falsei poziii este p, dac avem

cu .

Deci:

i ,

de unde

.

nlocuind n , obinem:

,

oricare ar fi k i , deci p trebuie s verifice

,

adic

.

2.2.8. Principiul dihotomiei

Dac este relativ uor de a verifica condiiile n pentru a asigura convergena irului de iteraii, este n general greu de a alege - iteraia iniial. Procedeul dihotomiei permite s se determine valoarea n vecintatea lui .

Fie o rdcin a ecuaiei cu f continu.

Dac exist un interval nchis [a,b] astfel nct s fie negativ, exist cel puin o rdcin n intervalul [a,b]. Dac n plus f este strict monoton n acest interval atunci aceast rdcin este unic.

Se poate atunci considera punctul , mijlocul intervalului [a,b] i calcula i localiza n noul interval avnd pentru extremiti i punctul a sau b dup cum sau este de semn contrar lui . La fiecare iteraie se njumtete lungimea intervalului. La nceputul iteraiei n, lungimea intervalului era .

Aceast metod furnizeaz urmtorul algoritm.

Algoritmul 2.2.8.1.

Intrri: a, b = capetele intervalului

f = funcia

= precizia

ieiri: x = rdcina localizat

{

ct timp

i

{

dac

atunci

altfel

}

}.

2.3. Rezolvarea numeric a sistemelor neliniare

Pentru mai mult claritate, ne limitm la sisteme de dou ecuaii cu dou necunoscute. Se constat c teoria este identic cu cea a ecuaiilor nlocuind cu i valoarea absolut n R cu norma n .

Fie i dou aplicaii n .

Se caut astfel nct

Domeniul D se va alege astfel nct s existe n D o soluie i numai una a sistemului.2.3.1. Metoda aproximaiilor succesive

Fie sistemul echivalent cu sistemul:

Aceasta ne conduce, lund :

Iternd, obinem

punnd ,

,

atunci iteraia se scrie:

.

Drept norm lum: .

Dm fr demonstraie urmtorul rezultat:

Teorema 2.3.1.1. Fie mulimea nchid . Dac

1)

;

2) exist o constant L: astfel nct:

,

atunci irul definit prin , este convergent i limita sa aparine lui D.

O condiie suficient pentru ca G s fie o aplicaie contractant este dat de urmtoarea teorem.

Teorema 2.3.1.2. Dac i sunt funcii cu derivate pariale continui n D, atunci,

,

unde .

Demonstraie.

Inegalitatea este echivalent cu , adic

.

Utiliznd formula creterilor finite avem:

,

unde i .

Deci:

unde .

.

Deci

Deci:

Metoda aproximaiilor succesive conduce la urmtorul algoritm. Algoritmul 2.3.1.1.

Intrri: n = numr de necunoscute

g = procedura de evaluare

= precizia

nr_max = numrul maxim de iteraii admis

X = aproximaia iniial

ieiri: X = soluia aproximativ ndeplinind i nr_max

{

execut

ct timp i nr_max

{

execut

}

}.

2.3.2. Metoda Newton

Metoda Newton n cazul unei ecuaii poate fi interpretat astfel: plecnd de la o valoare aproximnd soluia , se caut o cretere astfel ca .

De fapt, utiliznd formula Taylor i neglijnd termenii de ordinul 2, obinem:

,

de unde i deci .

Pentru sisteme se procedeaz la fel. Se dezvolt fiecare din cele dou funcii n serie Taylor i se neglijeaz termenii de ordinul .

Plecnd de la , cutm astfel ca:

Dezvoltm n serie Taylor i neglijm termenii de ordinul 2:

Deci, trebuie s verifice urmtorul sistem:

Fie matricea . Dac determinantul lui (matricea lui Jacobi) este diferit de zero atunci sistemul are o soluie i numai una . Atunci metoda Newton devine:

i n cazul sistemelor, metoda Newton este de ordin cel puin 2. Pentru a evita inversarea matricii jacobiene, avem .

Un algoritm furnizat de metoda Newton este:

Intrri: n = numrul de necunoscute

f = procedura de evaluare a lui

J = procedur de calcul a matricii jacobiene

= precizia

nr_max = numrul maxim de iteraii admis

X = aproximaia iniial

ieiri: X = soluia aproximativ ndeplinind i nr_max

{

repet

execut

execut

execut Gauss /* Eliminarea Gauss

execut Sist_Tr /*Rezolvarea sistemelor triunghiulare

pn cnd sau k > nr_max

}.

2.4. Exerciii

1) Fie ecuaia . Precizai un interval , n care se gsete o singur rdcin real, apoi determinai cu o eroare aceast rdcin folosind metodele:

a) metoda lui Newton;

b) metoda coardei.

2) Ci pai sunt necesari pentru determinarea rdcinii reale a ecuaiei , cu o aproximaie de , prin metodele:

a) metoda lui Newton;

b) metoda coardei.

3) S se rezolve sistemul neliniar

folosind metoda lui Newton cu iteraia iniial .

Discuii finale:

S se programeze utiliznd metoda Newton, Aitken, Steffensen, falsei poziii.Tema propus:

S se fac o lucrare cu tema metoda Newton, Aitken, Steffensen, falsei poziii.Capitolul 3

Rezolvarea sistemelor algebrice liniareObiectivele invatarii

nsuirea unor noiuni referitoare la metoda de eliminare a lui Gauss, factorizarea LU, factorizarea Cholesky, metoda iterativ Jacobi, metoda iterativ Gauss-Seidel.

Cuvinte cheie: metode directe, metode iterative.3.1. Introducere

Un sistem de ecuaii algebrice liniare poate fi scris sub forma

,

unde sunt coeficieni, sunt necunoscutele sistemului, iar sunt termenii liberi.

Sunt posibile situaiile:

(i) dac atunci trebuie alei n m parametri pentru a obine o soluie;

(ii) dac atunci se caut o soluie care s minimizeze ;

(iii) pentru m = n, dac atunci sistemul are o soluie unic altfel (adic, ) atunci sistemul poate avea o infinitate de soluii sau poate s nu aib nici o soluie.

Metodele de rezolvare sunt de dou feluri: directe (sau exacte) n care soluia este obinut dup un numr de operaii dinainte cunoscut i metode iterative, care utiliznd o aproximaie iniial o mbuntete de la o etap la alta.

3.2. Metode directe

Ca exemple de metode directe se pot aminti metoda lui Cramer bazat pe calculul determinanilor, metoda de eliminare a lui Gauss, metoda factorizrii directe. Dei n esen foarte simpl, metoda lui Cramer se dovedete cu totul ineficient sub aspectul numrului de operaii i nu este n general implementat.

3.2.1. Metoda de eliminare a lui Gauss

Fie un sistem de n ecuaii liniare cu n necunoscute scris sub forma, unde A este o matrice ptrat, nesingular, de dimensiune , iar x i b sunt vectori coloan de dimensiune n.

Metoda const n a obine zerouri sub diagonala principal a matricii A succesiv, nti pe prima coloan, apoi pe coloana a doua .a.m.d., pe ultima linie a lui A rmnnd doar coeficientul - modificat de operaiile de eliminare anterioare. Un pas (etap) k al metodei const n obinerea de zerouri sub diagonala principal, n coloana k a matricei A. Etapa este simbolizat prin indice superior att pentru matricea A ct i pentru vectorul b. Notm, iniial, i . n urma pasului al fazei eliminrii, sistemul are forma echivalent

la pasul k () este eliminat necunoscuta din ultimele n k ecuaii i sistemul este adus la forma

n final se obine sistemul

,

n care matricea este superior triunghiular.

Sistemul se rezolv prin metoda substituiei inverse potrivit relaiilor

Sistemul poate fi transformat ntr-un sistem superior triunghiular echivalent (adic cu matricea sistemului triunghiular superior) folosind rezultatele urmtoarei teoreme:

Teorema 3.2.1.1. Dac , , cu sunt nesingulare, atunci exist , nesingular i inferior triunghiular astfel nct matricea este superior triunghiular.

Demonstraie. Fie un produs de matrici elementare de forma , n care este matricea unitate, este coloana k a lui , iar , n care ultimele elemente sunt neprecizate deocamdat.

nmulind la stnga matricea sistemului A cu matricea de transformare T obinem

,

sau exprimat printr-o secven de transformri elementare:

n care fiecare operaie anuleaz elementele subdiagonale din coloana k ale matricei :

,

unde este coloana i a matricei .

.

Componenta i a coloanei transformate este:

Remarcm faptul c, n timpul transformrii, primele k componente nu se modific, fiind afectate numai elementele subdiagonale.

Din condiia de anulare a acestora urmeaz

, pentru ,

determinndu-se vectorul , deci i matricea .

Coloanele () se vor modifica astfel:

,

iar pe componente:

, , .

Coloanele () au elementele subdiagonale deja anulate ( pentru ) astfel c transformarea le las nemodificate:

.

Metoda de triangularizare i substituia invers conduc la un - algoritm.

Algoritmul 3.2.1.1.

Intrri: n = dimensiunea sistemului

A = matricea sistemului

b = vectorul termenilor liberi

Ieiri: A = matricea sistemului triunghiular

b = termenii liberi ai sistemului triunghiular

x = vectorul necunoscutelor

{

pentru

pentru

{

}

pentru

{

suma suma +

- suma) /

}

}.

n implementarea algoritmului eliminrii gaussiene, la fiecare pas k al eliminrii se efectueaz mprirea liniei pivot k la elementul diagonal . n practic, este posibil ca acest element s fie egal cu zero, situaie n care este imposibil continuarea algoritmului. Erorile de rotunjire n calculul elementelor matricii sunt cu att mai mici cu ct elementul pivot este mai mare n valoare absolut. Astfel, se efectueaz pivotarea parial pe coloane, ceea ce pentru pasul k al eliminrii revine la a gsi elementul maxim al matricei situat pe coloana k i liniile , adic i permut ntre ele liniile i k. Permutarea a dou linii sau coloane dintr-o matrice se poate face prin nmulirea cu o matrice de permutare care difer de matricea unitate prin: ,. Astfel nmulirea: are ca efect permutarea liniilor i k din matricea A, n timp ce: , produce permutarea coloanelor k i .

Cutarea elementului maxim n valoare absolut n submatricea delimitat de ultimele linii i coloane duce la performane mai bune de stabilitate numeric. Astfel se efectueaz pivotarea total.

3.2.2. Factorizarea LU

Fiind dat matricea , a unui sistem nesingular ne propunem s descompunem aceast matrice n produsul matricei inferior triunghiulare L cu matricea superior triunghiular U:

.

Motivul acestei descompuneri const n transformarea sistemului dat n dou sisteme liniare: i a cror matrici sunt triunghiulare i deci rezolvarea lor este uoar. Relaia ce leag elementele celor trei matrici poate fi scris , .

Sunt posibile mai multe factorizri LU. Matricele L i U au n total elemente nenule, n timp ce ne furnizeaz relaii. Este necesar particularizarea, de exemplu, a elementelor diagonale a uneia din matricile L sau U. Dac se consider elementele diagonale ale matricii U unitare se obine factorizarea Crout, n timp ce dac elementele diagonale ale lui L sunt unitare se obine factorizarea Doolittle.

Considerm, nti, . Atunci .

Pentru , avem .

Pentru , avem .

La pasul k () avem

, ,

.

, ,

.

Fie, acum , .

Pentru , avem

Pentru , avem

.

La pasul k () avem

,,n, :

.

, :

Factorizarea Crout conduce la urmtorul - algoritm.

Algoritmul 3.2.2.1.

Intrri: n = dimensiunea matricii

A = matricea de factorizat

Ieiri: L, U (folosesc acelai spaiu de memorie ca A)

{

pentru

{

pentru

{

}

pentru

{

}

}

}.

Din teorema 3.2.1.1. are loc urmtorul rezultat:

Teorema 3.2.2.1. Dac toate submatricele principale ale unei matrici A nesingulare de ordinul n sunt nesingulare atunci exist o factorizare LU, unde L este triunghiular inferior i U este superior triunghiular.

3.2.3. Factorizarea Cholesky

Fie A o matrice simetric i pozitiv definit (adic pentru orice ). Deoarece factorizarea LU stric simetria matricii A, factorizarea Cholesky menine simetria matricii A, avnd i avantajul unui timp de execuie mai mic pe calculator. Aceast factorizare const n descompunerea lui A sub forma , unde L este o matrice inferior triunghiular, ceea ce revine la

, .

La primul pas avem .

Pentru , avem .

La pasul k () avem ,

.

Pentru , :

EMBED Equation.3 .3.3. Metode iterative

Numrul de operaii pentru metodele directe de rezolvare a sistemelor algebrice liniare este (n fiind numrul de ecuaii i necunoscute), n timp de metodele iterative pot conduce la un numr mai mic de operaii.

Principiul general de rezolvare este similar cu cel de la rezolvarea ecuaiei , n care ecuaia este scris sun forma

,

conducnd la procesul iterativ

.

Fie

i

EMBED Equation.3 . Pentru rezolvarea sistemului algebric de ecuaii liniare

considerm clasa de metode iterative

,unde i R sunt parametrii care definesc metoda iterativ.

Pornind de la un element arbitrar se construiete un ir unde fiecare element reprezint o aproximaie a soluiei sistemului , dac aceast soluie exist. Aceasta constituie o metod iterativ de rezolvare a sistemului algebric.

Ne intereseaz condiiile n care irul de aproximaii converge ctre soluia sistemului.

Pentru matricea A introducem notaiile:

,

,

.

3.3.1. Metoda iterativ Jacobi

Dac , atunci necunoscuta din ecuaia i este

.

Construim irul definit prin formulele de recuren

, ,

, iar prima aproximaie este un element din . Relaia de mai sus se mai scrie , sau sub form matriceal . Raportat la cazul general, n metoda Jacobi avem i . irul definit prin formulele de recuren , , se rescrie prin , , unde . Vom stabili n ce condiii irul definit mai sus converge la soluia exact a sistemului . Fie x soluia exact i eroarea n aproximaia k : . Sistemul se mai scrie sau . Deci

sau, trecnd la norme i notnd cu obinem

.

Deci, dac atunci irul este convergent la soluia exact.

innd seama de formulele de recuren scrise pe componente i folosind respectiv norma maxim, norma unu sau norma euclidian, condiia de convergen devine:

sau

sau

.

Din motive de eficien verificm condiia considernd irul convergent ncepnd cu un rang k.

Metoda Jacobi conduce la urmtorul algoritm.

Algoritmul 3.3.1.1.

Intrri: n = ordinul matricii sistemului

A = matricea sistemului

b = vectorul termenilor liberi

y = aproximaia iniial / precedent a soluiei

nr_max = numrul maxim admis de iteraii

= precizia

Ieiri: x = soluia (aproximaia cerut)

{

ct timp (k < nr_max) i () pentru

{

pentru

pentru

}

}.

3.3.2. Metoda iterativ Gauss-Seidel

n aceast metod, construim irul definit prin formulele de recuren

,

, , ,

i un element din .

Formulele de recuren se pot scrie sub forma

,

sau sub form matriceal

i .

Astfel i . Remarcm faptul c, n aceast metod se folosesc noile valori ale componentelor vectorului necunoscutelor imediat ce au fost calculate. irul definit prin formulele de recuren

, , ,

se rescrie prin , , unde

. Condiia de convergen este:

.

Deoarece calcularea inversei necesit operaii, o condiie simpl de convergen a metodei Gauss-Seidel este: pentru fiecare linie a matricii A, elementul diagonal considerat n modul s fie strict mai mare dect suma tuturor modulelor celorlalte elemente ale liniei respective. Notnd cu

condiia precedent se scrie: .

S demonstrm convergena. Sistemul de ecuaii se mai scrie

, ,

cu valorile exacte ale necunoscutelor i nenuli.

Obinem,, sau, trecnd la module:

, .

Utiliznd norma maxim a vectorului eroare , obinem , sau

EMBED Equation.3 cu .

Metoda Gauss-Seidel furnizeaz urmtorul algoritm.

Algoritmul 3.3.2.1.

Intrri: n = ordinul matricii sistemului

A = matricea sistemului

b = vectorul termenilor liberi

y = aproximaia iniial / precedent a soluiei

nr_max = numrul maxim admis de iteraii

= precizia

Ieiri: x = soluia (aproximaia cerut)

{

ct timp (k > nr_max) i () pentru

{

pentru

pentru

}

}.

3.3.3. Metoda relaxrii

Fie q( R*. Metoda relaxrii este dat de

,

adic

, . Dac obinem metoda Gauss-Seidel.

Exist i alte condiii n care procedeele iterative sunt convergente. Dac i A este o matrice simetric i strict pozitiv atunci irul de aproximaii construit prin metoda relaxrii converge ctre soluia exact a sistemului Ax = b.

3.4. Exerciii

1) S se rezolve sistemele:

a) utiliznd metoda Jacobi;

b) utiliznd metoda Gauss;

c) utiliznd metoda Gauss-Seidel.

2) Analizai comparat metodele Jacobi, Gauss-Seidel i relaxrii pentru

, , .

Discuii finale:

S se discute despre metoda de eliminare a lui Gauss, factorizarea LU, factorizarea Cholesky, metoda iterativ Jacobi, metoda iterativ Gauss-Seidel.

Tema propus:

S se realizeze o lucrare cu tema metoda de eliminare a lui Gauss, factorizarea LU, factorizarea Cholesky, metoda iterativ Jacobi, metoda iterativ Gauss-Seidel.Capitolul 4

Rezolvarea numeric a problemelor algebrice de

valori i vectori propriiObiectivul capitolului

nsuirea noiunilor necesare programrii algoritmul lui Jacobi de determinare a valorilor si vectorilor proprii.

Cuvinte cheie: valori proprii, vectori proprii.4.1. Abordarea elementar a subiectului

La probleme algebrice de valori i vectori proprii conduc numeroase probleme tehnico-tiinifice.

Vom arta n cele ce urmeaz cum se ajunge la o problem algebric de valori i vectori proprii, extinznd problema rezolvrii unui sistem omogen de ecuaii.

Astfel lund sistemul:

constatm c acesta se poate scrie sub forma , unde A este matricea format din elementele cu i , iar x este vectorul coloan . Sistemul nu are alte soluii dect cea banal exceptnd cazul .

S presupunem c matricea A depinde de un parametru i anume s lum , unde I este matricea unitate.

n acest fel putem cuta acele valori pentru care i apoi putem cuta soluiile nebanale ale ecuaiei .

Problema pe care o avem de rezolvat se poate scrie sun forma:

.

Deci o problem algebric de valori i vectori proprii se exprim prin relaia:

unde A este o matrice ptratic de ordin n, x un vector (nenul) care se numete vector propriu (la dreapta) ce trebuie calculat iar un numr care se numete valoare proprie ce trebuie calculat.

Valorile proprii pentru problema sunt rdcinile ecuaiei (numit ecuaie caracteristic):

,

fiind un polinom de grad n n obinut din dezvoltarea determinantului . Avnd o valoare proprie , un vector propriu corespunztor x este soluia nebanal a sistemului omogen de ecuaii .

4.2. Aspecte teoretice generale

4.2.1. Clase speciale de matrici

Matricea adjunct (notat ) este matricea transpus i conjugat ( dac ).

Dac A este o matrice ptratic i , matricea A se numete hermetian (autoadjunct).

Se demonstreaz c:

O matrice A este unitar dac .

Dac A real atunci (transpusa) i dac atunci A se numete ortogonal. ntr-o matrice unitar (ortogonal), coloanele formeaz o baz ortonormal.

O matrice de rotaie este o matrice care difer de matricea unitate numai prin liniile p i q, unde singurele elemente nenule sunt:

,

unde c, s sunt dou numere complexe astfel ca . (Se poate lua , cu . Pentru matrici reale, , ).

Se verific uor c , adic matricea de rotaie este unitar (ortogonal).

Norma euclidian a unei matrici este definit prin

.

Prin definiie, urma matricei A este

.

Dac H este nesingular, matricele A i se numesc asemenea (similare).

Ecuaiile caracteristice a dou matrici asemenea sunt identice, deoarece:

Dac x este vector propriu al matricei A atunci Hx este vector propriu al matricii , deoarece:

din .

O matrice asemenea cu o matrice diagonal se numete regulat.

Dac A este regulat atunci ea admite n vectori proprii liniar independeni (o baz de vectori proprii).

Dac i rezult . Notm . Avem

.

Obinem .

Teorema 4.2.1.1. Dac valorile proprii ale unei matrici sunt distincte, atunci matricea este regulat.

Teorema 4.2.1.2. Pentru orice matrice ptratic complex A exist o matrice unitar P, astfel nct

s fie superior triunghiular.

O matrice A este normal dac

.

Lema 4.2.1.1. O matrice normal i triunghiular este matrice diagonal.

Demonstraie. Fie superior triunghiular (). Scriem egalitatea ce rezult din faptul c A este normal:

.

Deci:

pentru ,

pentru ,

,

deci T este diagonal.

Teorema 4.2.1.3. O matrice normal este regulat i admite o baz ortonormal de vectori proprii i reciproc.

Demonstraie. Fie A normal. Din teorema 4.2.1.2. exist P unitar astfel nct s fie superior triunghiular.

Avem

( pentru c P este unitar).

( pentru c A este normal).

Deci , adic B este normal. Conform lemei 4.2.1.1. rezult c B este diagonal. Cum (P unitar) i B diagonal rezult c A este regulat. Coloanele lui P sunt vectori proprii i formeaz o baz ortonormal.

Reciproc. Dac A admite o baz ortonormal de vectori proprii avem , unde P este matricea unitar a acestor vectori proprii i D este matricea diagonal a valorilor proprii. Avem (P unitar). Avem

Deci , adic A este normal.4.2.2. Punerea corect a problemei

Ne punem problema efectului perturbaiei matricei asupra valorilor proprii ale ei (adic la mici variaii ale datelor de intrare s vedem efectul asupra datelor de ieire din metod).

Teorema 4.2.2.1. Fie A o matrice regulat i fie H o matrice ale crei coloane sunt vectori proprii liniar independeni ai matricei A. Atunci, pentru fiecare valoare proprie a matricei perturbate , unde B are elementele de modul subunitare, exist o valoare proprie a matricei A astfel nct

.

Demonstraie. Din A regulat rezult

.

Scriem ecuaia caracteristic a lui i rezult:

.

Deci

.

Dac atunci teorema este demonstrat. Presupunem c pentru . Atunci .

Deci

este singular (avem teorema: dac atunci este nesingular).

Deci . Utiliznd norma spectral:

.

Deci .

Dar

. Deci

.

4.3. Metoda lui Jacobi

Cazul matricelor complexe hermitiene se reduce la cel al matricelor reale simetrice.

Fie , B, C reale. Fie valoare proprie (n acest caz este real) creia i corespunde un vector propriu de forma cu .

Deci , sau

adic

.

Deci problema devine real dar de dimensiune dubl.

A hermitiani.

Deci matricea de ordin este real i simetric.

Ne limitm la o matrice A real i simetric. Deci A normal. Conform lemei 4.2.1.3., A este regulat i admite o baz ortonormal de vectori proprii. A regulat, este asemenea cu o matrice diagonal ce are pe diagonal valorile proprii.

Metoda lui Jacobi utilizeaz matrice de rotaie reale i construiete un ir de matrice asemenea cu A.

Lum i n general, , n care o matrice de rotaie real, avnd la interseciile liniilor i cu coloanele i elementele , i respectiv , , iar n rest elementele matricei unitate.

Pentru un k fixat notm . Alegem p i q astfel nct (maximul n modul dintre elementele nediagonale). Alegem astfel nct s se anuleze pentru elementele simetrice cele mai mari n modul.

Dac este simetric atunci

.

Prin inducie

simetric.

Se observ c

.

Deci

asemenea cu .

Facem calculele n relaia

i avem

Deci

celelalte elemente rmnnd neschimbate:

,pentru toi .

Din condiia de anulare a lui obinem:

.

Alegem cu .

Lucrm cu numrtorul i numitorul separat (pentru a evita pierderea preciziei la mprire).

i , unde c = numrtorul cu semnul fraciei, d = numitorul n modul.

Teorema 4.3.1. irul matricelor construit cu metoda lui Jacobi este convergent i

unde sunt valorile proprii ale matricii A.

Demonstraie. S lum

,

unde este matricea simetric a elementelor nediagonale ale lui cu zero pe diagonal. Din relaiile de mai sus rezult

adic suma ptratelor elementelor nediagonale, cu excepia celor din poziiile (p,q) i (q, p) nu se modific.

Dar elementele din poziiile (p,q) i (q, p) n sunt zero.

Deci

pentru c . Rezult c

cu . ntr-adevr, pentru . n sunt termeni, deci

Deci cu . Rezult . Deci la limit se obine o matrice diagonal. Deoarece toate matricile irului sunt asemenea cu A elementele diagonale sunt valorile proprii ale lui A. Convergena este cel puin comparabil cu cea a lui , din punct de vedere al rapiditii.

Dac ultima rotaie care se efectueaz pn elementele nediagonale devin inferioare preciziei a calculelor ( fiind dat) este atunci avem:

.

Cu aceast precizie vectorii proprii sunt coloanele matricii .

Iniializm V = I i la fiecare pas nmulim la stnga pe V cu rotaia respectiv. Notm .

nmulirea de mai sus se transpune n formulele:

Metoda Jacobi conduce la urmtorul algoritm.

Algoritmul 4.3.1.

Intrri: n = ordinul matricei simetrice A

A = matricea simetric

= precizia

Ieiri: x = vectorul cu valorile proprii

B = matricea ale crei coloane conine vectorii proprii

{

ct timp

{

pentru

pentru

dac atunci

dac atunci

{

}

dac atunci

{

}

altfel

{

}

pentru

{

dac i atunci

{

pentru

dac i atunci

{

}

}

}

pentru

pentru

pentru

pentru

dac atunci

}

pentru

pentru

{

\* vectorul propriu j

pentru

}

}.

4.4. Probleme de valori proprii generalizate

n unele probleme ale fizicii matematice intervin ecuaii de valori proprii generalizate

,

unde att A ct i B sunt matrici ptrate.

O posibilitate de transformare a ecuaiei de mai sus ntr-o problem standard, de forma

,const n nmulirea ecuaiei la stnga cu , presupunnd c matricea B este nesingular:

.

Dac A i B sunt simetrice, nu ntotdeauna este simetric.

Dac A i B sunt simetrice i B este pozitiv definit, se poate transforma problema generalizat ntr-o problem standard pornind de la descompunerea Chalescki a matricii B:

,

unde L este inferior triunghiular.

Obinem:

,

sau,

,

adic

pentru matricea simetric

.

Valorile proprii ale matricei coincid cu cele ale lui A, iar vectorii proprii corespunztori sunt

,adic

.4.5. Exerciii

1) S se determine valorile proprii i vectorii proprii pentru matricea.

2) S se determine cea mai mare valoare proprie pentru

.

3) Fie matricile:

a) b) .

S se determine valorile proprii i vectorii proprii prin metoda Jacobi. De asemenea, s se scrie programul n C pentru metoda mai sus menionat.

Discuii finale:

S se discute despre algoritmul lui Jacobi de determinare a valorilor i vectorilor proprii.

Tema propus:

S se fac o lucrare cu tema algoritmul lui Jacobi de determinare a valorilor i vectorilor proprii.

Capitolul 5

Aproximarea funciilor prin polinoame

Obiectivele invatarii

nsuirea unor noiunie referitoare la interpolarea polinomial Lagrange, algoritmul Aitken, diferene divizate, formula lui Newton de interpolare, diferene finite, formule de interpolare pe noduri echidistante, interpolarea polinomial Hermite, aproximarea discret n sensul celor mai mici ptrate.

Cuvinte cheie: interpolare.5.1. Introducere

Pentru o funcie problema aproximrii ei printr-un polinom se pune fie cnd este dificil de evaluat f, fie cnd nu se cunoate expresia analitic a lui f ci doar valorile ei n anumite puncte , , obinute n general ca urmarea a unor msurri i prezentate ntr-un tabel. Mulimea de puncte , , cu proprietatea , o vom nota prin i o vom numi diviziune a intervalului . Punctele , vor fi numite nodurile diviziunii.

Alegerea unui polinom pentru aproximarea funciei f se justific prin modul simplu computerizat de evaluare a valorii polinomului ntr-un punct.

Weierstrass, n 1885, demonstreaz c orice funcie continu pe un interval este limita uniform pe a unui ir de polinoame i d un procedeu pentru calculul acestor polinoame. Bernstein, n 1912, d o metod prin care putem calcula, pentru o funcie continu pe , un ir de polinoame uniform convergent ctre f.

Fiind dat o funcie arbitrar se pune problema stabilirii unui criteriu de alegere a polinomului P care s aproximeze funcia dat. Astfel este necesar un instrument matematic pentru msurarea distanei dintre dou funcii, care impune situarea ntr-un spaiu vectorial normat complet i n funcie de stabilirea criteriului de alegere a polinomului P care s aproximeze funcia f vom avea metode de aproximare a funciilor prin polinoame i anume: aproximarea prin interpolare, aproximarea n medie ptratic.

5.2. Aproximarea prin interpolare

Fie i diviziunea

: . Presupunem cunoscute valorile funciei f n nodurile , ale diviziunii i (eventual) derivatele de anumite ordine ale funciei f n aceste noduri. Se pune problema determinrii unui polinom P care are aceleai valori ca i f n noduri i (eventual) derivatele de anumite ordine ale lui f i P n noduri s coincid. Un astfel de polinom P l vom numi polinom de interpolare ataat funciei f i diviziunii .

5.2.1. Interpolarea polinomial Lagrange

Fie i , astfel nct s fie toate distincte. Presupunem c se cunosc valorile funciei f n nodurile , , . Se pune problema determinrii unui polinom P astfel nct

pentru .

Teorema 5.2.1.1. Exist un polinom i numai unul de grad cel mult n astfel ca pentru .

Demonstraie. Dac P i Q sunt dou polinoame de grad cel mult n astfel ca pentru atunci polinomul este de asemenea de grad cel mult n i pentru . Deoarece polinomul R se anuleaz de cel puin (n + 1) ori i este de grad cel mult n, urmeaz c R este polinomul identic nul, adic .

Existena polinomului P o demonstrm construind efectiv polinomul P rspunznd condiiilor pentru . S gsim un polinom n spaiul vectorial al polinoamelor de grad cel mult n, notat , astfel ca

pentru , .

Acest polinom se anuleaz de n ori pentru , . Deci

.

Deoarece urmeaz c

.

Cele (n + 1) polinoame () sunt liniar independente n spaiul vectorial al polinoamelor de grad cel mult n. ntr-adevr, fie o combinaie liniar nul:

.

Pentru , , avem

.

Deci pentru .

Cele (n + 1) polinoame formeaz deci o baz a acestui spaiu vectorial de dimensiune n + 1. polinomul P cutat se obine ca o combinaie liniar de polinoame , adic polinomul dat de formula Lagrange:

.

ntr-adevr,

, pentru .

Pentru calculul valorii polinomului de interpolare Lagrange ntr-un punct a folosind relaia

a fost definit algoritmul urmtor:

Algoritmul 5.2.1.1.

Intrri: n = gradul polinomului de interpolare

a = valoarea argumentului polinomului

x = tabloul absciselor punctelor de interpolare

y = tabloul ordonatelor punctelor de interpolare

ieiri:

= valoarea polinomului de interpolare n a

{

pentru

{

pentru

dac atunci

}

}.

complexitatea metodei este , mai exact operaii ( adugri, nmuliri i mpriri).

n continuare dm o alt manier de scriere a polinomului Lagrange. Fie w polinomul de grad definit prin:

.

Atunci

.

Deci

cu .

nlocuind prin expresia sa n formula Lagrange, obinem:

.

n cazul cnd pentru orice k avem relaia . Cum

obinem formulele baricentrice

.

n acest caz numrul de operaii este de ordinul , dar o nou evaluare a lui , dac se conserv valorile lui , nu va cere dect 2n operaii.

5.2.2. Algoritmul Aitken

Atunci cnd se dorete modificarea punctelor de interpolare, se prefer urmtorul algoritm.

Lema 5.2.2.1. Fie Q i R dou polinoame de interpolare de grad cel mult n, construite respectiv pe i pe astfel nct:

pentru

.

Atunci polinomul de interpolare de grad n + 1, construit pe astfel nct

pentru

poate s se obin plecnd de la Q i R astfel:

.

Demonstraie. P este un polinom de grad cel mult n + 1.

,

.

n continuare se va construi polinomul P de grad cel mult n astfel nct: pentru .

Considerm urmtorul tabel triunghiular:

0123jj + 1 n

0

1

2

3

k

n

Fie urmtoarea relaie de recuren:

pentru

;

pentru

pentru

. Teorema 5.2.2.1. Polinomul de interpolare este egal cu .

Demonstraie. Se va arta c cu este polinomul de interpolare pe punctele , ceea ce va implica faptul c este polinomul cutat.

Facem demonstraia prin recuren pe al doilea indice

pentru .

Dac ipoteza este verificat pentru j fixat atunci pentru :

este polinomul de interpolare pe punctele ;

este polinomul de interpolare pe punctele .

Aplicnd lema 5.2.2.1., este polinomul de interpolare pe punctele .

5.2.3. Evaluarea restului la interpolarea Lagrange

Fie i fie . Ce se poate spune despre restul , unde P este polinomul de interpolare, astfel c , .

Se remarc faptul c x nu poate s aparin lui . n aceste caz, se spune c avem o extrapolare.

Aproximarea realizat cu ajutorul polinomului de interpolare Lagrange este nelocal, n sensul c la evaluarea funciei de interpolat contribuie informaii din toate punctele de interpolare, nu numai din cele din vecintatea argumentului considerat. Aceasta conduce la oscilaii complet strine de comportarea real a funciei aproximate. Un exemplu n acest sens este pentru aproximarea funciei . Distribuirea n mod echidistant a punctelor de interpolare reduce oscilaiile pn aproape la dispariie.

Teorema 5.2.3.1.

Dac i atunci

,

unde .

Demonstraie. Fie , definit prin

unde c este o constant aleas astfel nct .

Deci , unde .

Din condiiile de interpolare , .

Deci F are n + 2 zerouri distincte i anume: pe . Aplicnd teorema Rolle pe acest interval, va avea cel puin zerouri distincte, cel puin zerouri distincte. Din aproape n aproape, va avea cel puin un zero i deci .

Sub aceast form restul nu poate fi determinat n practic, deoarece punctul , care depinde de x i de nodurile de interpolare nu este cunoscut. Dac, ns, se cunoate estimaia , se poate evalua

.

Interpolarea polinomial Lagrange este util pentru construirea formulelor de aproximare a integralelor, derivatelor i ecuaiilor difereniale.

n practic, pentru a aproxima o mulime de puncte de interpolare, se va limita la polinoame de grad cel mult 10.

Se va prefera pentru polinoame de grad mai mare dect 10, s se utilizeze funcii spline care au cele mai bune proprieti de stabilitate.

Exemplul 1. S se construiasc polinomul de interpolare Lagrange a funciei f definit pe prin .

Rezolvare. Se constat c se aproximeaz curba la centrul intervalului, iar la extremiti se produc oscilaii numite efecte de margine.

Exemplul 2. S se construiasc polinomul de interpolare Lagrange a funciei f definite pe prin .

Rezolvare. Se remarc faptul c se produc efecte de margine.

Exemplul 3. Se d funcia f prin urmtorul tabel:

012

110

Se cere polinomul Lagrange .

Rezolvare.

5.2.4. Diferene divizate

Formula restului amintete oarecum de restul unei alte aproximri polinomiale a unei funcii de n ori continuu difereniabil formula lui Taylor. Vom arta c i polinomul lui Lagrange se poate exprima sub o form similar cu polinomul lui Taylor, n care derivatele se nlocuiesc cu diferene divizate.

Diferena divizat de ordinul zero n este

.

Prin definiie diferena divizat de ordinul nti pe nodurile distincte i este numrul notat cu i este dat de:

.

Diferena divizat de ordinul al doilea pe nodurile distincte , i este:

.

n general, diferena divizat de ordinul k pe noduri distincte se definete prin recuren:

n care diferenele divizate de la numrtor sunt de ordin .

Rezultatul care urmeaz precizeaz c diferena divizat depinde de nodurile n care este definit i de valorile funciei f n aceste noduri.

Teorema 5.2.4.1. Pentru orice i orice noduri distincte are loc formula:

.

Demonstraie. Facem inducie dup k. Pentru , formula din enun se verific conform definiiei diferenei divizate de ordinul nti. Presupunem adevrat formula din enun pentru k noduri distincte oarecare i verificm pentru noduri. Utiliznd formula de recuren din definiia diferenei divizate de ordinul k i ipoteza de inducie avem:

diferenele divizate definite prin recuren furnizeaz un algoritm de complexitate .

Algoritmul 5.2.4.1.

Intrri: n + 1 = numrul de puncte

x = tabloul celor n + 1 puncte

y = tabloul valorilor funcie f n cele n + 1 puncte

ieiri: y = diferenele divizate de ordin 0 .. n n

{

pentru

pentru

}.

5.2.5. Formula lui Newton de interpolare

Cu ajutorul diferenei divizate putem exprima restul la interpolarea Lagrange sub o alt form. Avem:

de unde, conform relaiei din teorema 5.2.4.1.

,

unde (am renotat) .

Polinomul Lagrange

se scrie:

.

Pentru fiecare m, , polinomul

are gradul cel mult m i

,pentru . Deci

,unde

. Pentru obinem ; comparnd cu expresia lui , pentru i , deducem .

Se obine polinomul lui Newton de interpolare:

Calculul polinomului Newton de interpolare se exprim prin:

Algoritmul 5.2.5.1.

Intrri: n = gradul polinomului de interpolare

a = abscisa n care se calculeaz polinomul

x = tabloul punctelor de interpolare

y = tabloul valorilor prin f a punctelor de interpolare

ieiri: = valoarea polinomului de interpolare n a

{

apeleaz Dif._div. (n,x,y)

pentru

{

}

}.

5.2.6. Diferene finite

Nodurile de interpolare sunt echidistante dac , .

Numim diferen finit de ordinul nti n x .

Se verific direct c este un operator liniar, iar diferena finit de ordinul k n x se definete prin relaia

, .

Formula de calcul pentru este urmtoarea:

.

Pentru demonstraie, procedm prin inducie. Avem:

fcnd n prima sum schimbarea de indice i renotnd apoi , obinem:

Prin inducie dup k, se arat c are loc:

.

5.2.7. Formule de interpolare pe noduri echidistante

S presupunem c punctul x n care se face interpolarea pe nodurile echidistante este apropiat de . Fcnd transformarea n polinomul lui Newton de interpolare i innd cont de legtura dintre diferene finite i divizate, obinem dup simplificri:

Aceasta se numete formula lui Newton progresiv pe noduri echidistante.

Dac x este apropiat de , fcnd transformarea , , formula lui Newton devine:

fcnd transformarea i innd cont de legtura dintre diferene finite i divizate, obinem dup simplificri:

numit polinomul Newton regresiv pe noduri echidistante.

Formula lui Newton progresiv pe noduri echidistante conduce la urmtorul algoritm.

Algoritmul 5.2.7.1.

Intrri: n + 1 = numrul de puncte

h = pasul

x = tabloul punctelor de interpolare

= abscisa n care se calculeaz polinomul

ieiri:

= valoarea polinomului de interpolare n

{

pentru

{

pentru

dac k este par atunci

altfel

pentru

{

pentru

dac este par atunci

altfel

}

}

}.

exemplu. Se d funcia f prin urmtorul tabel:

0123

11029

Se cere polinomul Newton progresiv.

Rezolvare. Se ntocmete un tabel cu diferene finite i se obine:

EMBED Equation.3

EMBED Equation.3 .

5.2.8. Interpolarea polinomial Hermite

Fie i noduri de interpolare, toate distincte. Se caut un polinom P astfel nct:

, .

Teorema 5.2.8.1. Exist un polinom P i numai unul singur de grad cel mult astfel nct:

pentru .

Demonstraie. Presupunem c exist polinoamele P i Q de grad cel mult astfel ca i pentru . Polinomul , care are de asemenea gradul cel mult , admite fiecare ca rdcin dubl (). Deoarece R are cel puin rdcini i are gradul cel mult urmeaz c R este polinomul nul i deci .

S artm c polinomul

,

unde:

cu

ndeplinete condiiile din enun.

Deoarece este un polinom de grad n, i sunt polinoame de grad . Cum

,

,

,

pentru avem:

, ,

adic .

,

.

Deci:

, ,

pentru avem , , deci .

Pentru evaluarea erorii la interpolarea Hermite avem

Teorema 5.2.8.2.

Dac i atunci

,

unde .

Demonstraia este asemntoare celei de la interpolare Lagrange.

Polinomul P avnd expresia

se numete polinomul lui Hermite construit pe baza condiiilor de interpolare

, .

Pentru calculul valorii polinomului Hermite ntr-un punct a a fost definit un - algoritm. Algoritmul 5.2.8.1.

Intrri: n + 1 = numrul nodurilor de interpolare

a = abscisa n care se calculeaz valoarea polinomului

x = tabloul celor n + 1 puncte de interpolare

y = tabloul valorilor funciei de interpolat n cele n+1 puncte

= tabloul valorilor derivatelor funciei de interpolat n cele n+1 puncte

ieiri: = valoarea polinomului Hermite n a

{

s

pentru

{

pentru

dac atunci

{

s s + +

}

s

}.5.2.9. interpolarea prin funcii spline

Studiul interpolrii polinomiale ne conduce la dou constatri. Prima este costul calculelor care devine ridicat cnd gradul polinomului este mare, iar a doua este c se stpnete ru efectul de margine dac intervalul de interpolare este mare.

O alt aproximare este cea local, adic fcnd interpolarea pe subintervale prin funcii spline.

Fie punctele de interpolare. Pe fiecare subinterval se caut un polinom de interpolare astfel nct condiiile de interpolare s fie ndeplinite:

pentru .

n plus se cere ca s fie de clas . De asemenea, pentru :

, continuitatea primei derivate,

, continuitatea derivatei a doua.

Condiiile de interpolare i cele de clas impun a cuta de gradul trei. Exprimm n funcie de i (necunoscute nc).

Prin interpolare liniar avem, punnd :

.

Integrnd de dou ori obinem:

,

unde i sunt constante de integrare, care se pot calcula innd cont de i , adic

i ,

de unde

i .

nlocuind i prin expresiile lor obinem:

punem condiia ca derivata s fie o funcie continu pe intervalul dat. avem

,

echivalent cu:

,

sau nc pentru :

.

Am obinut un sistem de ecuaii liniare cu necunoscute. Preciznd valorile lui i se poate rezolva sistemul liniar tridiagonal.

Exemplu. Pe intervalul fie funciile f i g definite prin i . S se fac interpolarea prin funcii spline cu 3, 5 i respectiv 9 puncte echidistante i s se dea valorile derivatelor la extremiti.

Rezolvare. Se constat c pentru 9 puncte de interpolare avem o foarte bun aproximare i nici un efect de margine.

5.3. Aproximarea n sensul celor mai mici ptrate

5.3.1. Problema fundamental a aproximrii liniare

Exemplu. S aproximm pe pe intervalul printr-un polinom .

Se pune problema s se gseasc P astfel ca:

a)

s fie minim;

b)

s fie minim;

c)

s fie minim.

Este necesar o msur numeric a distanei dintre funcia de aproximat i polinomul aproximant ntr-un spaiu vectorial normat.

Fie X un spaiu vectorial normat peste corpul K (adesea ). Notm prin produsul scalar i prin norma.

Fie , n elemente din X liniar independente. Trebuie s aproximm y printr-o combinaie liniar de , adic, s gsim cu , astfel ca s fie ct mai mic posibil.

Definiia 5.3.1.1. Cea mai bun aproximare a lui y printr-o combinaie liniar de este un element astfel ca:

. Cea mai bun aproximare const n a gsi minimul normei erorii.

Drept norme se consider:

1) dac atunci (modulul);

2) dac atunci (norma euclidian);

3) dac (= spaiul vectorial al funciilor continue pe ) atunci:

a) (norma convergenei uniforme);

b) (norma convergenei ptratice).

5.3.2. Teoreme fundamentale

Teorema 5.3.2.1. Fie n elemente liniar independente din . Pentru orice , problema celei mai bune aproximri are o soluie.

Verificare. Trebuie artat c funcia norma erorii

are un minim. Pentru aceasta, se arat c aceast funcie este continu i c este suficient a limita mulimea de variaie a lui la o mulime mrginit i nchis (exteriorul acestei mulimi nu conine minimul) pentru a aplica teorema: orice funcie continu pe o mulime nchis i mrginit din i atinge minimul su.

Corolarul 5.3.2.1. Fie , n ntreg fixat.

Problema: s se gseasc astfel ca:

are o soluie. Aceast soluie este unic.

Aceasta se numete aproximarea Tchebycheff de grad n a lui f.

Corolar 5.3.2.2. Fie , n ntreg fixat.

Problema: s se gseasc astfel ca:

are o soluie. Aceast soluie este unic.

Aceasta se numete aproximarea continu n sensul celor mai mici ptrate.

Corolarul 5.3.2.3. Date fiind , puncte distincte cu , problema: s se gseasc astfel ca:

are o soluie.

Aceasta se numete aproximarea discret n sensul celor mai mici ptrate.

5.3.3. Aproximarea discret n sensul celor mai mici ptrate

a) Cazul general

S se determine unde

,

ceea ce revine la a determine numere .

Cele funcii liniar independente sunt date. Se pot alege, () sau funciile trigonometrice sau cele exponeniale. Se cunosc perechi () cu , unde sunt distincte. Fie , .

S se determine astfel ca s fie minim.

Considernd norma euclidian n , avem , unde . Lum: . , matricea rectangular cu linii i coloane.

Avem .

Minimul lui R este caracterizat prin , , , adic:

Pentru , mprind prin i fcnd s tind spre zero obinem . pentru , mprind prin i fcnd s tind spre zero obinem . Cele dou inegaliti dau .

Notnd cu transpusa lui U obinem , . Deci valoarea minim a funciei R verific sistemul liniar , unde este o matrice ptratic de ordin .

Acest sistem se numete sistemul ecuaiilor normale.

b) Cazul liniar

n acest caz particular, se caut polinomul de grad unu, astfel ca , . Fie i . Sistemul de ecuaii normale devine:

,

adic . Notnd , , deoarece , avem , care, n statistic, se numete covariana vectorilor X i Y i se noteaz

.

Dac , obinem .

Rezolvarea sistemului d , .

5.4. Exerciii

1) S se determine polinomul de interpolare Lagrange care aproximeaz funcia f, cu valorile din tabelul alturat:

012

0127

2) S se calculeze, folosind polinomul de interpolare Lagrange, funcia definit de urmtorul tabel:

01,22,54,05,16,06,57,0

3,006,8414,252739,2151,0058,2566,00

Se va evalua .

3) Pentru , , s se determine diferenele finite pentru .

4) Fie funcia definit prin .

a) Construii polinomul P de interpolare Lagrange pe punctele 0, 1, 3, 5.

b) Calculai i comparai cu .

c) Calculai polinomul Q al lui Hermite astfel ca:

, , , .

Comparai cu . Care este concluzia?

5) S se determine valorile polinoamelor de interpolare: Lagrange, Aitken, Newton i Hermite ce aproximeaz urmtoarele funcii pe nodurile de interpolare corespunztoare n punctele precizate i s se calculeze diferenele finite i divizate:

a) i nodurile: 0; 2; 4; 6; 8 n 0,1;

b) i nodurile 1; 2; 3; 4 n 1,1;

c) i nodurile 2; 3; 4; 5; 6 n 4,5.

De asemenea, s se scrie programele n C pentru metodele mai sus menionate.

Discuii finale:

S se discute despre interpolarea polinomial Lagrange, algoritmul Aitken, diferene divizate, formula lui Newton de interpolare, diferene finite, formule de interpolare pe noduri echidistante, interpolarea polinomial Hermite, aproximarea discret n sensul celor mai mici ptrate.Tema propus:

S se ntocmeasc o lucrare cu tema interpolarea polinomial Lagrange, algoritmul Aitken, diferene divizate, formula lui Newton de interpolare, diferene finite, formule de interpolare pe noduri echidistante, interpolarea polinomial Hermite, aproximarea discret n sensul celor mai mici ptrate.Capitolul 6

Rezolvarea ecuaiilor difereniale ordinare de ordinul I

Obiectivul capitoluluinsuirea unor noiuni referitoare la metoda Euler i la metode Runge Kutta.

Cuvinte cheie: metode de rezolvare a ecuaiilor difereniale ordinare de ordinul I.6.1. Introducere

Ecuaiile difereniale numerice ordinare sunt o parte a analizei numerice care studiaz soluia numeric a ecuaiilor difereniale ordinare (ODE). Aceast parte este cunoscut de asemenea sub denumirea de integrare numeric, dar unii cercettori rezerv acest termen pentru calculul integralelor. Multe ecuaii difereniale nu pot fi rezolvate analitic, caz n care trebuie s ne mulumim cu o aproximaie a soluiei. Algoritmii studiai aici pot fi folosii pentru a calcula astfel de aproximaie. O metod alternativ este s folosim tehnicile din calcul pentru a obine o dezvoltare n serie a soluiei. Ecuaiile difereniale ordinare apar n multe discipline tiinifice, de exemplu n mecanic, chimie, biologie i economie. n plus, unele metode n numerica ecuaiilor difereniale ordinare transform ecuaia cu derivate pariale ntr-o ecuaie diferenial ordinar, care trebuie rezolvat.

Problema Vrem s aproximm soluia ecuaiei difereniale:

(1)

unde f este o funcie care duce [t0,)Rd n Rd, i condiia iniial y0Rd este un vector dat.

Formularea de mai sus se numete problema valorii iniiale (IVP). Teorema Picard Lindelf afirm c exist o soluie unic, dac f este Lipschitz continu. n contrast, problemele valorii mrginite (BVP) menioneaz soluia y n mai mult de un punct. Diferite metode trebuie s fie folosite pentru a rezolva BVP, de exemplu shooting method, multiple shooting sau metode globale metoda diferenelor finite sau metode sintagm.

Ne limitm la ecuaii difereniale de ordinul I (adic, n ecuaie apare doar prima derivat a lui y). Orict, o ecuaie de ordin superior poate fi uor convertit ntr-o ecuaie de ordinul I introducnd noi variabile. De exemplu, ecuaia de ordinul II poate fi rescris ca ecuaiile de ordinul I:

i .6.2. Metode Prezentm dou metode elementare.

6.2.1. Metoda EulerPlecnd de la ecuaia diferenial (1), nlocuim derivata prin diferena finit

(2)

care conduce la formula urmtoare:

(3)

Aceast formul este de obicei aplicat n felul urmtor. Alegem un pas h i construim irul t0, t1=t0+h, t2=t0+2h, .

Notm prin yn o estimare numeric a soluiei exacte y(tn). motivai de (3), calculm aceste estimri prin urmtoarea schem recursiv:

(4)

Aceasta este metoda Euler (sau metoda Euler forward, n contrast cu metoda Euler backward, care va fi descris n continuare). Metoda este numit dup Leonhard Euler care a descris-o n 1768.

Metoda Euler este un exemplu de metod explicit. Aceasta nseamn c noua valoare este definit n funcie de ceva ce deja se cunoate, precum .

6.2.2. Metoda Euler backward Dac, n locul lui (2), folosim aproximarea:

(5)

obinem metoda Euler backward:

(6)

Metoda Euler backward este o metod implicit, adic trebuie s rezolvm o ecuaie pentru a gsi . Adesea folosim o iteraie de punct fix sau metoda Newton Raphson (sau modificat) pentru a obine asta. Bineneles, ia timp s rezolvm aceast ecuaie; acest cost tr