Microsoft Word - CURS 2

CURS 2

METODE NUMERICE PENTRU SISTEME DE ECUAII NELINIARE

0. Preliminarii: Norma unui vector si norma unei matrici (rapel).

1. Sisteme de ecuaii neliniare. Definiii.

2. Metoda punctului fix.

3. Metoda Newton; metode cvasi-Newton.

0. Norma unui vector i norma unei matrici

Fie V un spaiu vectorial: n cazul de fa, V este Rn sau Cn .

Norma unui vector x V este aplicaie || . || : V R+, satisfcnd axiomele:

1. || x || 0 i || x || = 0 x = 0.

2. || x || = | | || x ||, = scalar ( R sau C).

3. ||x + y|| || x || + || y ||Exemple de norme ale unui vector:

norma- (norma maximum)

norma-1

norma-2 (norma euclidian)Fie An mulimea matricilor n n cu elemente scalare (reale, complexe).

Norma unei matrici A An este o aplicaie || . || : An R+, care satisface axiomele 1 3, i n plus, urmtoarele:

4. ||A B|| || A || || B ||5. ||A x|| || A || || x ||n axiomele 4 5, B An, iar x este un vector. Normele care satisfac 5 se zic compatibile cu norma vectorului.

ObservaieDefiniia normei unei matrici, indus de norma vectorului, este:

Pentru detalii privind norma unui vector i norma unei matrici, vezi Capitolul 4 I.Exemple de norme ale unei matrici:

norma liniilor

norma coloanelor

norma euclidian,

n care: (A conjugat transpus);

, unde sunt valorile proprii ale matricii A. se zice raz spectral.

1. Definiii

Fie sistemul de ecuaii neliniare:

.

Acesta se scrie vectorial

f(x) = 0

(1)

unde f : I Rn, I Rn . Explicit:

O soluie a sistemului (1) se va nota cu , adic: f() = 0.Metodele iterative de rezolvare a unui sistem de ecuaii f(x) = 0 presupun construcia unui ir (xk)k convergent ctre o rdcin x* a ecuaiei. Eroare absolut cu care xk aproximeaz x* este ek = x* ( xk. Se spune c irul (xk)k converge cu rata r dac exist o constant C ( (0, ) astfel nct

Dac

r = 1 i C > 1, rata convergenei se spune liniar r=1 i C = 0 (sau dac r > 1), rata convergenei se spune superliniar r = 2, rata convergenei se spune ptratic2. Metoda punctului fix

Pentru rezolvarea prin metoda punctului fix, sistemul (1) se va considera pus sub forma:

x = g(x)

(2)

n care g : I Rn, I Rn.O soluie a lui (2) se va nota , adic: = g() .

n ceea ce urmeaz, se presupun cunoscute noiunile de norm a unui vector || x || i norm a unei matrici ptratice || A || . n particular, norma- este:

Considerm ecuaii de forma x = g(x) .

Metoda const n construirea iruiui:

aproximaia iniial, dat;

A nu se confunda indicele superior (n) (indicele iteratei) cu ordinui n al sistemului (indice inferior al coordonatei ).Convergena procesului iterativ este asigurat de urmtoarele condiii:

(1) g este contractant pe o vecintate I a rdcinii: pentru x, y I||g(x) g(y)|| M ||x y||, M < 1.

(2) Aproximaia iniial x(0) I este suficient de apropiat de rdcina .

ObservaieDac g : C C i C Rn este un compact (mulime mrginit i nchis), atunci procesul converge pentru x(0) C .

Teorema 1.Presupunem:

1. x = g(x) are o rdcin .

2. g este continu i are derivate pariale de ordinul 1 continue, pe I definit de:

||x || .

3. Derivatele satisfac condiia:

.Atunci, x(0) I:

(a) Iteratele x(n) I. (b) irul x(n) .

(c) este unica rdcin n I.

Intervalul I din Condiia (2).

Sumarul demonstraiei:

Fie x, y I : ||x || , ||y || . Din dezvoltarea Taylor, se arat c avem:

||g(x) g(y)|| ||x y||Rezult:

||x(n+1) || = ||g(x(n) g()|| ||x(n) || <

i prin inductie:

||x(n) || n

Cum < 1, rezult n 0, sau x(n) . Concluzia (c) se demonstreaz prin contradicie.Observaii.1) Matricea jacobian a funciei g:

Introducem jacobianul G al lui g, prin:

Cu definiia normei || A || = , condiia 3 se scrie:

3'. ||G(x)|| < 1, x IG(x) joac rolui lui g(x) pentru o funcie scalar.

2) Convergena liniar:

n condiiile din Teorema 1, cu > 0, convergena este liniar, conform relaiei:

||x(n+1) || ||x(n) ||.

3) Convergena de ordinul 2 (ptratic):S presupunem c n rdcina , avem:

unde O este matricea nul, i c gi / xj sunt continue pe o vecintate a lui .

Atunci, > 0 astfel nct condiia 3 sau 3' este satisfcut. Dac, n plus, derivatele de ordinul 2 exist i sunt mrginite pe ||x || , adic:

,atunci din formula Taylor rezult:

||g(x) g()|| M ||x ||2,

unde

Cu x = x(n), g(x(n)) = x(n+1), rezult:

||x(n+1) || M ||x(n) ||2care arat c convergena este de ordinul 2.2.2. Procedur explicit de punct fix

Considerm sistemul dat sub forma f(x) = 0 i vrem s-l transformm ntr-un sistem echivalent de forma x = g(x) .

Fie A(x) = [aij(x)] o matrice n n , nesingular pe o vecintate a lui . Definim:

g(x) = x A(x) f(x)

Este evident c A fiind nesingular, avem:

x = g(x) f(x) = 0.

Exemplul 1: Iterare cu matrice constant

A(x) = A, unde A = matrice constant (aij = constant) i nesingular.

g(x) = x A f(x)

Se verific imediat c, jacobianul lui g este dat de:

G(x) = I A F(x) ,

unde I este matricea unitate, iar F(x) este jacobianul lui f,

.Explicit:

Conform Teoremei 2, iteraia va converge dac elementele matricii G(x) sunt suficient de mici, i x(0 ) este suficient de apropiat de .

Pentru o convergen mai rapid, s cerem v. Observaia 3:

G() = O.

Rezult A F() = I, sau

A = [F()]1.

(3)

Cum nu este cunoscut, lum de exemplu, x(0), rezul:

A = [F(x(0))]1.

(4)Iteraia va fi definit de

x(n+1) = x(n) A f(x(n)),

(5)

unde A este definit de (4).

Procedura se zice iterare cu matricea constant A, i este analoag cu metoda coardei pentru o funcie scalar.2.3. Schema practic de iterare

Procedeul practic, care evit inversarea matricii F(x(0)), este urmtorul. Punem:

x(n+1) = x(n+1) x(n),

i rezult:

n 0

(6)Procedeul revine la determinarea coreciei x(n+1) prin rezolvarea sistemului liniar din prima ecuaie (6). Iteraia se oprete prin testele

||x(n+1)|| eps,

(7a)

n + 1 lnit

(7b)

unde tolerana eps i numrul limit de iteraii lnit, sunt alese dinainte. Procedeul este util mai ales dac actualizm A dup un numr de pai, conform Observaiei 1.Algoritm:

Date de intrare:

f (contracie)

x0 (termenul iniial al irului)

( (precizia ce determin condiia de oprire: se calculeaz termenii irului pn la xN cu proprietatea ||xN ( xN-1|| < ().

Date de ieire:

xN (aproximaie satisfctore (determinat de () pentru punctul fix).

x1 : = x0;

x2 : = f(x1);

ct timp ||x2 ( x|| ( execut

x1 : = x2;

x2 : = f(x1);La ieire x2 este aproximaie pentru x*, punctul fix al lui f. Faptul c f este contracie asigur terminarea programului ntr-un numr finit de pai. Pentru a evita ciclarea n situaia n care s-ar ncerca folosirea algoritmului pentru o funcie care nu este contracie, se poate stabili de la nceput un numr maxim de pai ce urmeaz a fi executai. De asemenea se poate afia la fiecare pas diferena dintre termenii consecutivi cureni (pentru a observa c irul nu converge dac f nu e contracie). Astfel se poate folosi urmtoarea variant a algoritmului:

Date de intrare:

f (contracie)

x0 (termenul iniial al irului)

( (precizia)

Nmax (numr maxim de termeni ai irului ce urmeaz a fi calculai)

Condiia de oprire: se calculeaz termenii irului pn la xN cu proprietatea

.

Date de ieire:

xN (dac f este contracie, xN este aproximaie satisfctore determinat de ( i Nmax pentru punctul fix al lui f).

x1 : = x0;

x2 : = f(x1);

n : = 1;

ct timp (||x2 x1|| ) sau (n < Nmax) executx1 : = x2;

x2 : = f(x1);

n : = n + 1;

Dac f este contracie i Nmax suficient de mare, la ieirea din ciclu, x2 este aproximaie pentru x*, punctul fix al lui f.

Interpretare geometric: f : I I contracie, I R interval nchis

Exemple.

1) S se rezolve (n mulimea numerelor reale) ecuaia urmtoare aplicnd metoda punctului fix

x3 x 1 = 0.

Se poate arta c ecuaia x3 x 1 = 0 are o singur rdcin real, i c aceast rdcin este n intervalul (1, 2). Ecuaia se poate scrie:

x3 = x + 1

Fie f : [1, 2] [1, 2], definit prin f(x) = . Avem i deci

Ca urmare f este contracie pe intervalul [1, 2]. Deci soluia ecuaiei poate fi aflat ca limita irului (xn)n, cu

.

2) S se rezolve (n mulimea numerelor reale) ecuaia urmtoare aplicnd metoda punctului fix

x cos(x) = 0

Notm g(x) = x cos(x). Cum cos(x) [1, 1], soluiile ecuaiei x cos(x) = 0 se gsesc n intervalul [1, 1]. Deoarece g(x) = 1 + sin(x) > 0 pentru x din intervalul [1, 1], rezult c g este strict cresctore pe [1, 1] i deci ecuaia

x cos(x) = 0

are cel mult o rdcin. Cum g(0)g < 0, ecuaia x cos(x) = 0 are exact o rdcin n intervalul . Fie , . Avem i deci

Ca urmare f este contracie pe intervalul . Deci soluia ecuaiei poate fi aflat ca limita irului (xn)n, cu

.3. Metoda Newton

Metoda Newton (varianta m-dimensional, m > 1) este o generalizare a metodei tangentei. Este o metod iterativ de rezolvare a unor sisteme de m ecuaii i m necunoscute:

f(x) = 0,

unde f : G Rm, G Rm.

Considerm ecuaia echivalent x = g(x), unde g(x) = x A(x) f(x).

Cutm A(x), astfel ca metoda punctului fix pentru g s aib ordinul doi. Condiia este v. mai sus, G() = O, sau

Se verific faptul c aceasta conduce la condiia A() = [F()]1.

Atunci, presupunem c:

f este continu i cu derivate pariale de ordinul 1 continue, pe o vecintate a lui rdcinii .

Jacobianui lui f este nesingular n :

det(F()) 0.

Determinantul fiind funcie continu de elementele jacobianului, > 0 astfel c pentru ||x || s avem

det(F(x)) 0.

Alegem atunci

A(x) = [F(x)]1,||x || ,

care asigur A() = [F()]1 . Rezult:

g(x) = x [F(x)]1 f(x)

Metoda Newton este atunci:

x(n+1) = x(n) [F(x(n))]1 f(x(n))

(8)Conform Teoremei 1 i Observaiei 3, rezult urmtoarea:PropoziieDac f are derivate pariale de ordinul 2, mrginite pe ||x || i x(0) este suficient de apropiat de , atunci metoda Newton are convergen ptratic.n propoziia de mai sus, i n relatiile anterioare, || . || este || . ||.

3.1. Schema practic de iterare

Schema practic de iterare este cea de la 2.3, evitndu-se inversarea matricii F(x(n)), i anume:

n 0

(9)Corecia x(n +1) se calculeaz prin rezolvarea sistemului liniar din prima ecuaie (9).

Iteraia se oprete prin testul||x(n+1)|| eps,

(10a)

unde tolerana eps este aleas dinainte. Obinuit, se adaug i testul:

Numr de iteraii lnit

(10b)

unde lnit este numrul limit prescris de iteraii.

3.2. Calculul numeric al derivatelor parialeEvaluarea jacobianului F(x(k)), la pasul k, cere evaluarea a n2 functii fi / xk. Chiar dac acestea se pot calcula analitic, pentru n mare efortul de calcul este mare. Alteori, fi(x) sunt date numeric. n astfel de cazuri, derivatele se calculeaz numeric, prin diferene divizate:

,unde | h | este mic. Creterea h poate fi constant, sau poate fi variat de la un pas la altul (lund h = h(k)). h nu se ia excesiv de mic, pentru a nu conduce la erori de rotunjire mari. Se art c, pentru a menine convergena ptratic, h trebuie s satisfac condiia (la pasul k):

| h | C ||f(x(k))||,

unde C este o constant pozitiv, fixat dinainte (Raiston & Rabinowitz (1978)).

3.3. Metode cvasi-Newton

Metoda Newton este metoda descris de formula de iterare (6), care utilizeaz jacobianul evaluat la fiecare pas x(n) (analitic sau numeric).

Dac jacobianul F(x(n)) este nlocuit cu o aproximaie a acestuia, metodele se zic metode Newton-modificate sau metode cvasi-Newton.

Pentru a reduce efortul de calcul se procedeaz la nlocuirea jacobianului F(x(k)) de la pasul k, cu o aproximaie a acestuia, fie aceasta A(k), dup una din urmtoarele scheme:

Jacobianul nu se actualizeaz dup fiecare pas, ci dup un numr m de pai:

A(l) = F(x(k)) pentru l = k,, k + (m 1).

Aceast schem reduce viteza convergenei, dar este economic la o rulare lung.

Aproximaia jacobianului la pasul k + 1 se genereaz din cea de la pasul k, fr evaluri suplimentare de funcii. Aceast schem este mai bun dect precedenta.

Pentru modaliti de generare a lui A(k+1) v. Raiston & Rabinowitz (1978).

Cu modificrile precedente, formula de iterare (8) devine:

x(k+1) = x(k) [A(k)]1 f(x(k))

(11)

Nota 1: Metoda Newton prin liniarizarea ecuaiilorFie ecuaia neliniar f(x) = 0 sau explicit, sistemulfi(x) = 0, i = 1, 2,, nDac x(0) este n vecintatea rdcinii, considerm dezvoltarea Taylor a lui fi(x) n jurul lui x(0):

unde termenii nescrii sunt de ordin mai mare sau egali cu doi n ().

Presupunem c acetia sunt neglijabili n raport cu termenii de orinul nti, i avem

Notm elementele jacobianului F al lui f, adic

Dezvoltarea devine

,Sau, matriceal,

.Ecuaiile scrise pentru i = 1,2,, n, dau:

f(x) f(x(0)) + F(x(0))(x x(0))

Rezolvm aproximativ sistemul f(x) = 0, nlocuind f(x) prin expresia sa liniarizat (n membrul doi al relaiei precedente; punem semnul = n loc de ).

Rezult:

F(x(0))x = f(x(0)),

(11)

unde s-a pus

x = x x(0).

Relaia (11) este formula schemei de iterare n metoda Newton.

Soluia x(1) = x(0) + x este o aproximaie a rdcinii (este soluia sistemului liniarizat).

Presupunnd c aproximatia x(1) este mai bun dect x(0), atunci metoda const n aplicarea repetat a formulei (10), nlocuind, la pasul urmtor, x(0) cu x(1).

Astfel, n general, metoda Newton este:

F(x(k+1))x(k+1) = f(x(k)), k = 0, 1, unde x(k+1) = x(k+1) x(k).Problema const acum, n a proba c irul x(k) .

Nota 2: Interpretare geometric pentru cazul n = 2S punem z = f1(x, y), z = f2(x, y). Acestea sunt ecuaiile a dou suprafee, fie acestea S1 i S2.

Ecuaia f1(x, y) = 0, revine la z = 0, adic la intersecia suprafeei S1 cu planul x y: aceasta este o curb C1. Soluia sistemului , revine la intersecia curbelor C1 i C2.

Funcia liniarizat este:

.Aceasta reprezint ecuaia planului tangent n (x(0), y(0)), la suprafaa Si.

Deci metoda revine la nlocuirea suprafeei, n vecintatea rdcinii, prin planul tangent. (Analog cu metoda Newton pentru o ecuaie scalar f(x) = 0, unde graficul se nlocuiete cu tangenta la grafic).

Interseciile planelor tangente cu planul x y vor fi dou drepte care aproximeaz curbele C1 i C2. Intersecia dreptelor este aproximaia rdcinii.

ExempluFie sistemul de dou ecuaii neliniare:

f(x, y) x2 + y2 5 = 0,

f(x, y) y ex 1 = 0.

Aproximaiile iniiale se iau: x(0) = (2, 1), i x(0) = (0.5, 2) .

De exemplu, acestea se pot gsi analiznd intersecia graficelor curbelor

x2 + y2 = 5,y = ex + 1.

Matricea jacobian este:

Lum eps = 1E6. Calculul este efectuat n simpl precizie. Soluia calculat (x, y), numrul de iteraii i valorile lui f n soluie, sunt date n tabelele de mai jos.

1) Metoda punctului fix, iterare cu matricea constant A = F(x(0)), cu actualizare dup 3 pai:

x(0)Nr. iteraiix yf1(x, y) f2(x, y)

(2, 1)51.919 684 1.146 6532.761 E7 2.995 E8

(0.5, 2)170.2043 374 2.226 7127.210 E8 4.654 E8

ObservaiiDerivatele pariale ale funciilor fi sunt calculate numeric, cu h = 0.001. Numrul de iteraii pentru a doua rdcin este mai mare dect cel pentru prima rdcin, ntruct aproximaia iniial (0.5, 2) este mai ndeprtat de rdcin. Cu aproximaia x(0) = (0.2, 2.2), se gsete aceeai soluie n 8 iteraii.

2) Metoda Newton:

x(0)Nr. iteraiix yf1(x, y) f2(x, y)

(2, 1)41.919 684 1.146 6532.761 E7 2.995 E8

(0.5, 2)50.2043 374 2.226 7125.384 E8 8.289 E9

Not: Derivatele pariale sunt calculate cu matricea jacobian F(x, y)

ExerciiuS se rezolve sistemul:

S se gseasc rdcinile din vecintatea punctelor w0 = (2, 2, 1) i w0 = (1, 1, 1).

_1317710446.unknown

_1317795837.unknown

_1317803278.unknown

_1317803854.unknown

_1317805248.unknown

_1317810547.bin

_1317810782.bin

_1317805829.unknown

_1317806740.unknown

_1317804152.unknown

_1317805144.unknown

_1317804011.unknown

_1317803736.unknown

_1317803794.unknown

_1317803395.unknown

_1317799016.unknown

_1317800886.unknown

_1317801861.unknown

_1317800086.unknown

_1317798010.unknown

_1317798098.unknown

_1317797379.unknown

_1317711613.unknown

_1317712852.unknown

_1317713953.unknown

_1317795601.unknown

_1317713694.unknown

_1317712264.unknown

_1317712347.unknown

_1317712107.unknown

_1317710732.unknown

_1317710834.unknown

_1317711181.unknown

_1317710792.unknown

_1317710611.unknown

_1317710658.unknown

_1317710532.unknown

_1302591943.unknown

_1316250427.unknown

_1316331643.bin

_1317709960.unknown

_1317710013.unknown

_1317709840.unknown

_1316250736.unknown

_1316251133.unknown

_1316251246.unknown

_1316251330.unknown

_1316251413.unknown

_1316251169.unknown

_1316251048.unknown

_1316251083.unknown

_1316251006.unknown

_1316250583.unknown

_1316250647.unknown

_1316250497.unknown

_1316011079.unknown

_1316188233.unknown

_1316009150.unknown

_1300267613.unknown

_1302590903.unknown