Lucrare de licenta - metoda lui jacobi pentru sistemele liniare infinite

Universitatea "Petru Maior" Targu Mures

Facultatea de Stiinte si Litere

Specializarea Matematica - Informatica

LUCRARE DE LICENTA

METODA LUI JACOBI PENTRU SISTEMELE LINIARE INFINITE

INTRODUCERE

In aceasta lucrare este prezentata extinderea metodei numerice iterative a lui Jacobi de la sistemele liniare finite la sistemele liniare infinite, dupa cum spune si titlul. Pana acum s-a studiat aceasta metoda doar pentru sistemele liniare finite in ℝⁿ. Pentru a realiza aceasta extindere, se considera in loc de norme in ℝⁿ, norme in spatii de siruri si in loc de norme matriciale in M_n(ℝ), norme pentru matrici infinite. Aceasta metoda reprezinta o noutate si nu apare in literatura de specialitate.

In capitolul 1 se readuc la cunostinta cateva elemente de analiza matematica si analiza functionala, de care avem nevoie pe parcursul celorlalte doua capitole. Amintim de spatiile metrice, spatiile normate, spatiile Banach, pe baza carora se contureaza normele vectoriale, matriciale si cateva proprietati ale spatiilor de siruri.

Capitolul 2 prezinta metoda numerica a lui Jacobi pentru sistemele liniare finite in ℝⁿ , si se mai face referire la normele vectoriale in ℝⁿ, normele matriciale in M_n (ℝ), compatibilitatea si subordonarea celor doua norme.

In capitolul 3 se prezinta extinderea metodei lui Jacobi la sistemele liniare infinite, la spatiile de siruri. Caracterizam mai intai spatiile de siruri, si anume: l¹, l²,l^p si l^∞. Apoi studiem normele vectoriale pe aceste spatii de siruri, normele matriciale pentru matrici infinite, compatibilitatea si subordonarea dintre ele si in final extinderea metodei lui Jacobi la sistemele liniare infinite.

Capitolul 1: Elemente de analiza matematica si analiza functionala

Spatii metrice

Spatiile metrice formeaza o clasa importanta de spatii topologice. Datoram aceasta notiune matematicianului M. Frechet (1878 - 1973) care, introducand notiunea de distanta intre obiecte matematice de acelasi tip, ne permite sa vorbim de distanta nu numai intre doua puncte din plan.

Definitie

Fie X o multime nevida. O functie d: X x X →ℝ cu proprietatile:

(D1) d(x,x) =0, ∀ x∈ X ;

(D2) d(x,y) =d(y,x), ∀ x,y∈ X (simetrie);

(D3) d(x,y) ≤d(x,z) + d(z,y), ∀ x,y,z∈ X (inegalitatea triunghiului)

se numeste semimetrica (sau semidistanta). Daca , in plus, d verifica si

(D4) d(x,y) =0 ⇒x=y, ∀ x,y∈ X, atunci d se numeste metrica (sau distanta)

Observatie

1. Daca in (D3) punem x=y obtinem d(x,x) ≤d(x,z) + d(z,x),

∀ x,z∈ X, de unde d(x,z) ≥0, ∀ x,z∈ X

2. Putem reduce numarul de axiome care caracterizeaza notiunea de semimetrica. Astfel, (D2) si (D3) sunt echivalente cu (D2')

(D2 ): d(x,y) ≤ d(x,z) + d(y,z), ∀ x,y,z∈ X, deci (D1) + (D2) + (D3)   ⇔ (D1) + (D2

Evident (D2) + (D3) ⇒ (D2 ). Reciproc, luam in (D2') z=x si obtinem

d(x,y) ≤ d(x,x) + d(y,x) ⇒ d(x,y) ≤ d(y,x)

Daca inversam pe x cu y avem d(y,x) ≤ d(x,y), deci,

d(x,y) d(y,x), adica (D2).

Definitie

O pereche (X, d) unde d: X x X →ℝ este o metrica (semimetrica) se numeste spatiu metric (semimetric). Elementele unui spatiu metric se numesc puncte.

Observatie

1. Daca perechea (X, d) este un spatiu metric si A ⊂ X este o submultime nevida a lui X, atunci perechea (A, d) este un spatiu metric.

2. Pe o multime nevida X pot fi definite mai multe distante, dupa cum vom constata mai jos, deci mai multe structuri de spatiu metric. Atunci, cand nu este pericol de confuzie, spatiu metric (X, d) va fi notat cu X.

In continuare, vom da cateva exemple de spatii metrice:

1. (ℝ, d) este un spatiu metric, unde d: ℝxℝ →ℝ, d (x,y) = |x-y|,

∀ x, y ∈ X este metrica euclidiana.

2. (ℂ, d) este un spatiu metric relativ la metrica euclidiana

d: ℂxℂ → ℝ, d(z₁, z₂) = |z₁-z₂|, ∀ z₁, z₂∈ ℂ

3. (ℝⁿ, d) este un spatiu metric, unde metrica euclidiana

d: ℝⁿ x ℝⁿ → ℝ se defineste astfel: ∀ x= (x₁, x₂, , x_n) ∈ ℝⁿ ,

∀y= (y₁, y₂, , y_n) ∈ ℝⁿ

d(x,y)

Verificarea proprietatilor (D1), (D2) si (D4) este imediata.

Pentru a verifica (D3) fie x= (x₁, x₂, , x_n), y= (y₁, y₂, , y_n) si

z= (z₁, z₂, , z_n) ∈ ℝⁿ

(D3) ⇔ [

Notam x_i - z_i = a_i si z_i - y_i = b_i , i=. Atunci, relatia de mai sus

devine

[ ]^1/2 ⇔

⇔ ⇔

⇔ ]^1/2 ⇔

⇔ [ ]

care nu este altceva decat inegalitatea Cauchy - Buniakowski - Schwartz.

Observam ca spatiile metrice (ℝ², d) si (ℂ, d) cu distantele euclidiene sunt identice.

4. (ℝⁿ, d) este un spatiu metric, unde d: ℝⁿ x ℝⁿ → ℝ

d(x,y) = , ∀ x= (x₁, x₂, , x_n) ∈ ℝⁿ , ∀y= (y₁, y₂, , y_n) ∈ ℝⁿ

este metrica Manhattan (distanta postasului).

5. (ℝⁿ, d) este un spatiu metric relativ la distanta d: ℝⁿ x ℝⁿ → ℝ .

d(x,y)= , ∀ x= (x₁, x₂, , x_n) ∈ ℝⁿ , ∀y= (y₁, y₂, , y_n) ∈ ℝⁿ  

6. (ℝⁿ, d) este un spatiu metric unde d: ℝⁿ x ℝⁿ → ℝ

d(x,y) = []^1/p, ∀ p≥1, p ∈ℝ, ∀x= (x₁, x₂, , x_n) ∈ ℝⁿ ,

∀y= (y₁, y₂, , y_n) ∈ ℝⁿ , este metrica Minkowski (1864- 1909).

7. pentru orice multime nevida X, (X,d), este un spatiu metric, unde

d: X x X→ ℝ, d(x,y)=∀ x,y ∈ X, este metrica discreta.

Un astfel de spatiu metric se numeste spatiu metric discret.

8. Hipercubul de dimensiune n.

Fie B= codul binar. Multimea Bⁿ=BxBx.xB se numeste hipercub de dimensiune n. Orice n-uplu x∈Bⁿ , x= (x₁, x₂, , x_n)= x₁x₂x_n reprezinta un cuvant de cod de lungime n. Definim adunarea modulo 2 in B si o extindem la elementele din Bⁿ . Astfel,∀ x,y∈Bⁿ , x= (x₁, x₂, , x_n) ,

y= (y₁, y₂, , y_n),

x⊕y=( x₁⊕y₁, x_n⊕y_n). Pentru ,∀ x,y∈Bⁿ se defineste d(x,y)=, adica numarul de componente ale lui x si y care nu coincid.

Se verifica usor ca (Bⁿ, d) este un spatiu metric d, unde d se numeste distanta Hamming (1915-1998).

Hipercubul de dimensiune 2 este patratul avand latura de lungime 1 si ca varfuri cuvintele de cod 00, 01, 10, 11. Hipercubul de dimensiune 3 este cubul obijnuit de latura avand lungimea 1, iar ca varfuri cuvintele de cod 000, 001, 010, 100, 011, 101, 110, 111.

Multimea Bⁿ are o interpretare remarcabila si anume Bⁿ ≃Aⁿ , unde Aⁿ este multimea de numere naturale . Orice numar x∈Aⁿ are o reprezentare unica de forma x=cu a_i∈B si poate fi astfel identificat cu punctul a₁a₂ a_n∈Bⁿ.

9. Fie A o multime nevida, A ∈ℝⁿ.

(M(A), d) este un spatiu metric unde M(A) este multimea functiilor numerice, reale, marginite definite pe A, iar d: M(A)x M(A) →ℝ definita prin

d(f,g)= sup_x∈A|f(x)-g(x)|, ∀ f,g ∈ M(A) este distanta uniforma. Verificarea conditiilor (D1), (D2) si (D4) este imediata. Aratam ca are loc si conditia (D3). Avem inegalitatile evidente ∀f,g,h ∈ M(A), ∀x∈A

|f(x)-g(x)|≤ |f(x)-h(x)| + |h(x)-g(x)|≤ sup_x∈A|f(x)-h(x)| + sup_x∈A|h(x)-g(x)|.

Atunci

sup_x∈A|f(x)-g(x)|≤ sup_x∈A|f(x)-h(x)| + sup_x∈A|h(x)-g(x)|,

adica d(f,g)≤ d(f,h) + d(h,g), ∀f,g,h ∈ M(A).

10. (C^k([a,b]),d) este spatiul metric, unde

C^k([a,b])=, iar

d: C^k([a,b])x C^k([a,b]) →ℝ este definita prin d(f,g)=|f⁽ⁿ⁾(x)- g⁽ⁿ⁾(x)|, metrica Cebasev (1821-1894).

1.1.9. Definitie

Fie (X,d) un spatiu metric. Spunem ca un sir de elemente din ℝⁿ converge la x∈ ℝⁿ, daca sirul de numere reale converge la 0, deci daca ∀ℇ> 0, ∃ n_ℇ∈ℝ^* astfel incat d(x_n, x)<ℇ , ∀n≥ n_ℇ . Vom folosi notatia

x_n →x sau .

Exemple:

1.Daca X= si d(x,y)=|x-y|, atunci converge la x daca ∀ℇ> 0,

∃ n_ℇ∈ℝ^* astfel incat |x_n- x|<ℇ , ∀n≥ n_ℇ.

Regasim astfel definitia cunoscuta a sirului de numere reale convergent.

2. Fie X= ℝⁿ , si fie , un sir de elemente (vectori) din ℝⁿ. Fiecare element x_k va fi de forma x_k=(x_k1,x_k2,x_kn), x_ki∈γ, ∀. Daca

x= (x₁, x₂, , x_n), atunci x_kx daca ∀ℇ> 0, ∃ n_ℇ∈ℝ^* astfel incat

d(x_k, x)<ℇ , ∀n≥ n_ℇ . Tinand seama de definitia distantei ℝⁿ aceasta revine la: | x_ki-x_i| < ℇ, ∀k≥ n_ℇ, ∀.

Astfel, am obtinut urmatorul rezultat

1.1.10. Teorema

Sirul de numere converge in ℝⁿ la elementul x, daca si numai daca x_ki converge in γ la x_i ,∀.

In concluzie, convergenta unui sir de elemente (vectori) din ℝⁿ, revine la convergenta pe componente.

De exemplu, sirul → (1,0) in ℝ².

3. Fie X=ℂ si d(z₁,z₂)=|z₁-z₂| , ∀z₁,z₂∈ℂ.

1.1.11. Teorema

Un sir de numere complexe , unde pentru ∀n, z_n=x_n+iy_n, converge in ℂ la z=x+iy, daca si numai daca x_n→x si y_n→y in γ.

Demonstratie

z_n→z in ℂ daca si numai daca .

Din inegalitatile evidente:

max≤ |x_n-x|+ |y_n-y| , rezulta ca z_n→z in ℂ daca si numai daca x_n→x si y_n→y in γ.

4. Fie X=B(E) multimea functiilor reale si marginite pe E. Un sir de functii converge la f in B(E) daca ∀ℇ> 0, ∃ n_ℇ∈ℕ^* astfel incat:

d(f_n,f) = < ℇ, ∀n≥ n_ℇ.

Aceasta definitie este echivalenta cu urmatoarea:

∀ℇ> 0, ∃ n_ℇ∈ℕ^* astfel incat |f_n(x)-f(x)| < ℇ, ∀n≥ n_ℇ, si ∀ x∈E.

1.1.12 Teorema

Un sir de functii converge la f in B(E) daca si numai daca.

1.1.13 Definitie

Un sir de elemente dintr-un spatiu metric X se numeste fundamental (Cauchy) daca ∀ℇ> 0, ∃ n_ℇ∈ℕ^* astfel incat d(x_n,x_m)< ℇ,

∀n,m≥ n_ℇ.

Daca X= γ si d(x,y)=|x-y|, reobtinem definitia sirului fundamental de numere reale.

1.1.14 Definitie

Un sir se numeste marginit daca ∃ a∈X si r>0, astfel incat d(x_n,a)<r, ∀ n∈ℕ . Principalele proprietati ale sirurilor de elemente dintr-un spatiu metric sunt concentrate in urmatoarea teorema:

1.1.15 Teorema

Fie (X,d) spatiu metric.

i) Daca x_n x si y_n y atunci d(x_n,y_n)=d(x,y);

ii) Orice sir convergent are limita unica;

iii) Orice sir convergent este fundamental;

iv) Orice sir fundamental este marginit;

v) Orice subsir al unui sir convergent este convergent si are limita egala cu limita sirului initial.

Demonstratie

i) Stim ca | d(x_n,y_n) - d(x,y) | < d(x_n,x) + d(y_n,y).

Cum d(x_n,x)= d(y_n,y)=0, rezulta ca d(x_n,y_n)= d(x,y).

ii) Presupunem ca si de asemenea . Din i) rezulta d(x,y)= , deci y=x.

iii) Daca x_n x , atunci ∀ℇ> 0, ∃ n_ℇ∈ℕ^* astfel incat d(x_n,x)< ℇ/2,

∀n≥ n_ℇ. Pentru ∀ m> n_ℇ avem de asemenea d(x_m,x)<

Din proprietatea a III-a a distantei rezulta

d(x_n,x_m)≤ d(x_n,x)+ d(x,x_m)< ℇ/2+ ℇ/2= ℇ, m,n> n_ℇ;

deci este fundamental.

iv) Fie un sir fundamental si ℇ = 1. Atunci, ∃ n₁∈ℕ^*, astfel incat d(x_n,x_m)<1, ∀ m,n≥n₁. In particular, d(x_n1,x_m)<1, m>n1.

Fie α = max si fie r=max. Evident, d(x_n1,x_m)<r, ∀ m∈ℕ^*, deci este marginit.

v) Fie x_nx. Orice subsir al sirului este la randul sau un sir de forma , unde k₁<k₂<.<k_n<. este un sir strict crescator de numere naturale.

Pentru ℇ> 0, ∃ n_ℇ∈ℕ^* astfel incat d(x_n,x)< ℇ, ∀n≥ n_ℇ. Deoarece k_n≥n, rezulta d(x_kn,x)< ℇ, ∀n≥ n_ℇ, deci x_kn→x.

Am vazut ca orice sir convergent este fundamental. Afirmatia reciproca nu este in general adevarata. Exista spatii metrice care contin siruri fundamentale divergente.

Exemplu

Fie X=ℕ si d(x,y)=|x-y|, ∀x,y∈ℕ. Consideram sirul x_n=. Acest sir este fundamental in γ, dar nu este convergent in ℕ deoarece

∉ ℕ.

1.2. Spatii normate

1.2.1. Definitie

Fie X o multime si functiile +:X x X→ X si functia ∗:K x X→ X cu urmatoarele proprietati:

sv1) x+(y+z)=(x+y)+z, ∀x,y,z∈X;

sv2) ∃ 0_x∈X astfel incat x+0_x=x, ∀x∈X;

sv3) 1∗x=x, ∀x∈X;

sv4) ∗x)= ( )∗x, ∀ ∈K, ∀x∈X;

sv5) (x+y)= x+ y, ∀ ∈K, ∀x,y∈X;

sv6) ( )x= x+ x, , ∀ ∈K, , ∀x∈X.

(X,+.∗) se numeste spatiu vectorial peste K. (X/K)

1.2.2. Observatie

1) x+y=y+x, ∀x,y∈X folosind sv3), sv5) si sv6);

2) ∀x∈X, ∃ x'∈X astfel incat x'+x=0_x

0_x=(1+(-1))∗x=1∗x+(-1)*x=x+(-1)*x

x'=(-1)*x=-x

Exemple:

kⁿ=

x+y= (x₁+y₁, x₂+y₂ , x_n+y_n ) 0_kⁿ=

αx=(αx₁, αx₂, , αx_n)

(kⁿ, +,*) spatiu vectorial peste K

s=

x=(x_n)_n∈ℕ, y∈(y_n)_n∈ℕ,

+: s x s → s

x+y= (x_n+y_n)_n∈ℕ

*: k x s → s, ∀α∈K

α*x=(αx_n) _n∈ℕ

0_s=(0,0,0,)

(s,+,*) spatiu vectorial peste K

Fie X spatiu vectorial peste K si I nevida

X^I

+:X^I x X^I → X^I

x,y∈ X^I

(x+y)(i)=x(i)+y(i), ∀ i∈I

∈K

*:K x X^I → X^I

*x)(i)= *x(i), ∀i∈I

(X^I, +, *) spatiu vectorial peste K.

In definitia spatiului metric nu s-a presupus ca multimea X are vreo structura algebrica. Din aceasta cauza, intr-un spatiu metric oarecare nu se poate dezvolta o teorie a seriilor, deoarece nu are sens operatia de adunare. Pentru a elimina aceasta deficienta vom introduce notiunea de spatiu normat, in care se presupune ca multimea X este un spatiu vectorial.

Definitie

Fie X un spatiu vectorial peste corpul K Se numeste norma pe X orice

aplicatie || || : X → ℝ cu proprietatile:

(i)         ||x||≥0, ∀ x∈X, si ||x||=0 daca si numai daca x=0_x

(ii)       ||λx||=|λ| ||x||, ∀λ∈K, ∀x∈X

(iii)     ||x+y||≤||x|| + ||y||, ∀x,y∈X

Perechea (X,|| ||) se numeste spatiu normat.

Exemple

Multimea este un spatiu normat in raport cu norma

||x|| = |x|, ∀x∈

Multimea ℝⁿ este un spatiu normat in raport cu norma

||x||_∞ =max , unde x= (x₁, x₂, , x_n)∈ ℝⁿ este un vector oarecare.

Multimea numerelor complexe este un spatiu normat in raport cu norma

||z|| = |z| = , ∀z=x+iy ∈ ℂ.

Multimea B(E) a functiilor reale si marginite pe E este un spatiu normat in raport cu norma

||f||_∞ = sup.

Observatie

Orice spatiu normat este un spatiu metric in raport cu distanta

d(x,y)=||x-y||, ∀x,y∈X.

Afirmatia reciproca nu este in general adevarata. Exista si spatii metrice care nu sunt spatii normate.

Exemplu

Fie A o multime oarecare si fie X=.

Evident X este un spatiu metric in raport cu distanta:

d(f,g)=sup.

Observam insa ca X nu este spatiu normat deoarece nu este spatiu vectorial.

Intr-adevar, daca f,g∈X si α,β∈γ, atunci αf+ βg in general nu apartine lui X.

Cum spatiile normate sunt cazuri particulare de spatii metrice, rezulta ca definitiile si rezultatele privind sirurile in spatii metrice raman valabile si in spatii normate. Astfel, daca X este un spatiu normat, atunci un sir de elemente din X converge la elementul x∈X, daca si numai daca:

.

1.3 Teorema de punct fix a lui Banach

1.3.1 Definitie

Un spatiu metric (X,d) se numeste complet daca orice sir fundamental de elemente din X este convergent catre un element din X. Din criteriul general de convergenta a lui Cauchy pentru siruri de numere reale rezula ca γ este un spatiu metric complet in raport cu distanta euclidiana

d(x,y) = |x-y|, ∀x,y∈ γ.

Teorema

Spatiul ℝⁿ este complet.

Demonstratie

Fie un sir de elemente din ℝⁿ . Fiecare element x_k este de forma

x_k= (x_k1, xk₂, , xk_n)

Din inegalitati evidente:

|x_ki-x_li| ≤ , rezulta ca in demonstratia teoremei 1.1.10 ca este fundamental in ℝⁿ daca si numai daca este fundamental in γ, . Afirmatia din teorema rezulta acum din criteriul general de convergenta a lui Cauchy pentru siruri de numere reale si din teorema 1.1.10. Intr-adevar , daca este fundamental in ℝⁿ atunci este fundamental in γ, deci convergent pentru . Din teorema 1.1.10 rezulta

convergent in ℝⁿ .

Teorema

Spatiul numerelor complexe ℂ este complet.

Demonstratie

Daca z_n=x_n+iy_n, atunci conform teoremei 1.1.11 z_n→z=x+iy daca si numai daca x_n→x si y_n→y in γ. In mod analog se arata ca este fundamental daca si numai daca si sunt fundamentale in γ. Afirmatia rezulta acum (ca si in teorema 1.3.2) din criteriul general de convergenta a lui Cauchy pentru siruri de numere reale.

Teorema

Spatiul B(E) al functiilor reale si marginite pe E este complet.

Demonstratie

Din teorema 1.1.12 rezulta ca converge la f in B(E) daca si numai daca .

Definitie

Fie (X,d) un spatiu metric. Se numeste contractie pe X orice aplicatie

T : X → X cu proprietatea ca exista 0≤α<1 astfel incat

d(T(x),T(y)) ≤ αd(x,y), ∀x,y∈X.

Teorema Banach

Daca (X,d) este un spatiu metric complet si T : X → X este o contractie, atunci exista z∈X, unic, astfel incat T(z)=z.

Demonstratie

Alegem un punct oarecare x₀∈X si notam cu

x₁=T(x₀), x₂=T(x₁), ., x_n=T(x_n-1), .

Vom arata ca sirul este fundamental. Intr-adevar,

d(x₁,x₂)=d(T_(x0),T_(x1))≤ d(x₀,x₁)

d(x₂,x₃)=d(T_(x1),T_(x2))≤ d(x₁,x₂) ≤ d(x₀,x₁).

Prin inductie completa se arata ca

d(x_k,x_k+1) ≤ ^kd(x₀,x₁), ∀k∈ℕ^*.

In continuare avem

d(x_k,x_k+p) ≤ d(x_k,x_k+1)+ d(x_k+1,x_k+2)+ + d(x_k+p-1,x_k+p) ≤

^{k k+1 k+p-1})d(x₀,x₁)=d(x₀,x₁)< <d(x₀,x₁),

∀k,p∈ℕ^*. (1.1)

Deoarece 0≤α≤1, avem α^k→0, deci ∀ ℇ>0, ∃ k_ℇ∈ℕ^*, astfel incat

^k<, ∀k> k_ℇ. Rezulta d(x_k,x_k+p)<ℇ, ∀k> k_ℇ si ∀p∈ℕ^*, deci este sir fundamental. Cum X este complet rezulta ca ∃ z∈ X astfel incat x_k→z. Mai departe avem:

d(z, T(z)) ≤ d(z,x_k) + d(x_k, T(z))= d(z,x_k) + d(T(x_k-1, T(z)) ≤

≤ d(z,x_k) + α d(x_k-1,z).

Deoarece, conform teoremei 1.1.15. punctul i), membrul drept tinde la 0, rezulta d(z, T(z))=0, deci, T(z)=z. Pentru a putea demonstra unicitatea punctului fix z, sa presupunem ca ∃z`∈X astfel incat T(z`)=z`. Atunci avem:

d(z,z`)=d(T(z),T(z`))≤ α d(z,z`).

Cum, 0≤α<1, aceasta ineglitate nu poate avea loc decat daca d(z,z`)=0, adica daca z=z` si cu aceasta teorema este demonstrata.

Sirul , obtinut pornind de la un punct arbitrar x₀∈X, prin relatia de recurenta x_k=T(x_k-1), ∀k∈ℕ^*, se numeste sirul aproximatiilor succesive, iar metoda de obtinere a punctului fix z ca limita a acestui sir, poarta numele de metoda aproximatiilor succesive. E. Picard a obtinut metoda aproximatiilor succesive cu mult inainte ca Banach sa fi stabilit rezultatul sau foarte general (Teorema 1.3.6.). Din aceasta cauza, aceasta metoda se mai numeste si metoda Picard - Banach.

Pentru a evalua eroarea in metoda aproximatiilor succesive, trecem la limita dupa p in inegalitatea (1.1) si obtinem:

d(x_k,x)≤ d(x₀,x₁) (1.2)

Asadar, daca aproximam pe z cu x_k facem o eroare care este mai mica decat d(x₀,x₁).

Teorema 1.3.6. are numeroase aplicatii in matematica. Pentru exemplificare, vom arata cum poate fi folosita metoda aproximatiilor succesive la rezolvarea ecuatiilor algebrice sau transcendente.

Fie ecuatia F(x)=0, x∈[a,b]  (1.3)

Aceasta ecuatie se inlocuieste cu ecuatia echivalenta:

x=f(x); x∈[a,b] (1.4)

Acest lucru se poate realiza de exemplu, daca notam f(x)= x+F(x). Sa presupunem ca f: [a,b] →[a,b] este derivbila si exista 0≤α<1 astfel incat

|f`(x)|≤α, ∀ x∈ [a,b]. (1.5)

Din teorema Lagrange rezulta ca ∀ x,y∈ [a,b], ∃ξ intre x si y astfel incat

f(x) - f(y)= f`( )(x-y). Tinand seama de (1.5) obtinem:

|f(x)-f(y)|≤ |x-y|, ∀ x,y∈ [a,b]. (1.6)

Din (1.6) rezulta ca f este o contractie pe [a,b], iar din teorema (1.3.6) rezulta ca exista o solutie unica z a ecuatiei (1.4) care se poate obtine cu metoda aproximatiilor succesive. Din punct de vedere geometric, orice solutie a ecuatiei (1.4) este abscisa unui punct de intersectie din dreapta y=x si graficul functiei y=f(x).

Pe figura (1) se poate urmari sirul aproximatiilor succesive pentru 0<f`(x)≤α<1 , iar pe figura (2), pentru -1<-α≤f`(x)<0.

.Figura 1

x0

y=f(x)

x2

x3

x1

z

Figura 2

Exemplu

Fie ecuatia x⁵-x-0,2=0, care admite o radacina in intervalul

[-0,3; -0,2]. Ecuatia echivalenta este x=x⁵-0,2, deci f(x)= x⁵-0,2.

Se verifica imediat ca |f'(x)|<0,05, ∀x∈[-0,3; -0,2] deci putem lua

Dupa prima aproximatie se poate lua x₀=-0,2.

Aflarea unei solutii aproximative se face cu ajutorul calculatorului.

1.4. Spatii Banach

1.4.1. Definitie

Orice spatiu normat si complet se numeste spatiu Banach.

Intre cele mai simple spatii Banach distingem spatiile liniare standard n-dimensionale ℝⁿ si ℂⁿ peste corpul ℝ, respectiv ℂ, normate cu ajutorul normei euclidiene

||z||= (|z₁|² + . + |z_n|² )^1/2, z=(z₁, . , z_n).

In continuare, vom da cateva exemple de spatii Banach pe care le vom demonstra.

1.4.2. Normarea si completitudinea spatiului CB(T).

Fie T un spatiu topologic Hausdorf, T≠∅, se defineste

CB(T)=.

1. CB(T) ⋐ B(T) ne bazam pe adunare si produsul cu scalari. Normam cu norma indusa ||x||= sup. Pentru orice element din B(T), este verificata ca a fi spatiu normat.

Observatie:

T compact Hausdorf. ∀ f:T →ℝ continua rezulta ca f este marginita (isi atinge marginile: ∃ t₀∈T astfel incat f(t₀)= f(t)).

Daca x: T→K este continua, cu f: T→ℝ atunci f(t)=|x(t)| va fi continua.

||x(t)|- |x(t`)||≤|x(t)- x(t`)|, atunci x este continua , deci rezulta |x(t)- x(t`)|<ℇ rezulta ca f este continua. Prin compunere rezulta ca sup< +∞

(∃t₀∈T: |x(t₀)|= sup).

Observatie: supremumul daca este atins se noteaza cu max.

Daca T este spatiu topologic Hausdorf, T≠∅, definim

C(T)=.

CB(T) ⋐ C(T).

2. Stiind ca spatiul T este un compact Hausdorf, T≠∅, ⇒

⇒ C(T)=CB(T).

3. CB(T) este un spatiu Banach (urmeaza sa demonstram completitudinea).

B(T) este spatiu Banach, CB(T) ⋐ B(T) si tinand cont ca CB(T) este inchis in B(T) din aceste doua reiese ca CB(T) este un spatiu Banach.

x∈ ⇒ ∃ (x_n)_n∈ℕ ∈ CB(T) : x_n →x in B(T).

∀ℇ>0 ∃n₀∈ℕ astfel incat ∀n≥n₀ ||x_n-x|| < ℇ.

∀ℇ>0 ∃n₀∈ℕ astfel incat ∀t∈T, ∀n≥n₀ : |x_n(t)-x(t)| < ℇ.

|x_n(t)-x(t)| <||x_n-x||. (este o convergenta uniforma )

∀ℇ>0 si ∀t∈T ∃n₀∈ℕ, n₀= n₀(ℇ, t) , ∀n≥n₀ : |x_n(t)-x(t)| < ℇ, adica x_n converge punctual catre x.

Avem un sir de functii continue care converge catre x, deci x este continua..

x este marginita deoarece lucram in B(T).

x este continua: ∀t∈T, ∀ℇ>0, ∃ V∈V (t): ∀t`∈V, |x(t)-x(t`)| < ℇ.

ℇ>0, ∃n₀∈ℕ, ∀n≥n₀ , ∀t∈T, |x_n(t)-x(t)| < ℇ/3.

t₀∈T fixat: ∀t∈T, |x_n0(t)-x(t)| < ℇ/3.

x_n0 este continua rezulta ∃ V∈V (t₀), ∀t∈V

t∈V, |x(t)-x(t₀)|≤ |x(t)-x_n0(t)| + |x_n0(t)-x_n0(t₀)| + |x_n0(t₀)-x(t₀)| < ℇ.

1.4.3 Normarea si completitudinea spatiului B(T)

Definitie:

B(T):=, spatiul functiilor marginite pe T.

x marginita ⇔ sup < ∞.

B(T) este un spatiu vectorial.

x,y ∈ B(T) x+y ∈B(T)

(x+y)(t)= x(t)+ y(t), t∈T (punctual)

Definim aplicatia : || || B(T) →ℝ

||x|| = sup , x∈B(T)

(B(T), || ||) este un spatiu normat.

a) x=0 ⇒ ||x||>0

x=0 ⇔ ∀t∈T, x(t)=0, x≠0 ⇒∃t₀∈T :

x(t₀)≠0, ||x||≥| x(t₀)|>0.

b) ||αx||=|α|*||x||.

c) ||x+y||≤||x||+||y||.

∀t∈T  |(x+y)(t)|=|x(t)+y(t)| ≤|x(t)|+|y(t)| ≤||x||+||y||

|x(t)| ≤||x|| si |y(t)| ≤||y||.

Trecand la supremumum ||x+y||≤||x||+||y||.

B(T) este un spatiu Banach. (normat si complet)

Demonstratie

||x||=sup

B(T) este complet daca si numai daca orice sir fundamental este convergent.

(x_n)_n∈ℕ sir fundamental in B(T):

∀ℇ>0 ∃n₀∈ℕ astfel incat ∀n, m≥n₀ ||x_n-x_m|| < ℇ.

a) ∀ℇ>0 ∃n₀∈ℕ astfel incat ∀n,m≥n₀ < ℇ.

∀ℇ>0 ∃n₀∈ℕ astfel incat ∀n,m≥n₀ ∀t∈T |x_n(t)-x_m(t)| < ℇ. (1.10)

Pentru t∈T (x_n(t))_n∈ℕ sir fundamental in K rezulta din (1.10)

(x_n(t)) convergent pentru t∈T fixat, caci K este complet.

Definim x: T → K astfel incat x(t) (1.11)

x∈B(T) ? (x marginita

Fie ℇ=1 ⇒∃n₀ ∀t∈T ∀n,m≥n₀ |x_n(t)-x_m(t)| <1

∀t∈T , m≥n₀ : |x_n0(t)-x_m(t)| <1

m→∞ ⇒∀ t∈T, |x_n0(t)-x(t)| ≤1

b) x = (in convergenta in B(T)

∀ℇ>0 ∃n₀∈ℕ ||x_n-x|| < ℇ

∀ℇ>0 ∃n₀∈ℕ ∀n≥n₀ , ∀t∈T |x_n(t)-x(t)| < ℇ

sirul de functii (x_n) converge uniform catre x

Stim ca ∀t∈T , ∀ℇ>0, ∃n₀∈ℕ, ∀n≥n₀ |x_n(t)-x(t)| < ℇ

∀ℇ>0 ∃n₀∈ℕ , ∀n,m≥n₀ , ∀t∈T :

|x_n(t)-x_m(t)| <ℇ

pentru n≥n₀ fixat si t∈T, m→∞ ⇒ |x_n(t)-x(t)| < ℇ.

∀ℇ>0 ∃n₀∈ℕ ∀n≥n₀ , ∀t∈T ⇒ |x_n(t)-x(t)| < ℇ

pentru n≥n₀, |x_n(t)-x(t)| ≤ℇ. ||x_n-x|| < ℇ.

In continuare vom demonstra ca spatiul sirurilor convergente este un spatiu Banach.

Spatiul l^∞ . l^∞:=B(ℕ) spatiul sirurilor marginite (spatiu Banach)

1.4.4 Normarea si completitudinea spatiului c.

1) c:= este spatiul sirurilor convergente.

Orice sir convergent este marginit. c⋐ l^∞ deci c este subspatiu al lui l^∞.

Definim || || : c →ℝ

||x||= sup

2) (c, || ||) normat, este spatiu Banach.

Lema:

Daca (X, S) este spatiu semimetric complet, Y⊆X inchisa ⇒Y completa.

Consecinta:

X spatiu Banach, Y⋐X inchis ⇒ Y spatiu Banach.

Pentru ca c sa fie complet e de ajuns sa aratam ca c este inchis in l^∞.

c= c⊂ ⊂c ?

x∈ ⇒x∈c

x∈⇔ ∃ (x_n)_n∈ℕ ⊂c astfel incat lim x_n=x (in l^∞)

x_n= (x_nⁱ)_i∈ℕ ; x=(xⁱ)_i∈ℕ

∀ℇ>0 ∃n₀∈ℕ ∀n≥n₀ , ||x_n-x|| < ℇ.

∀ℇ>0 ∃n₀∈ℕ ∀n≥n₀ , |x_nⁱ-xⁱ| <ℇ

∀ℇ>0 ∃n₀∈ℕ ∀n≥n₀ , |x_nⁱ-xⁱ| <ℇ (1.12)

x∈c ⇔ (xⁱ)_i∈ℕ este sir fundamental.

∀ℇ>0 ∃i₀∈ℕ : ∀i,j≥0 , |xⁱ-x^j| <ℇ

∀ℇ>0 ∃n₀∈ℕ ∀n≥n₀ , ∀i∈ℕ, |x_nⁱ-xⁱ| <ℇ/3 (1.13)

Rezulta ca pentru n=n₀, ∀i∈ℕ, |x_nⁱ-xⁱ| <ℇ/3 x_n0∈c ⇒ (xⁱ)_i∈ℕ este sir fundamental ⇒∃i₀∈ℕ : ∀i,j∈ℕ , i,j≥i₀ : |x_n0ⁱ-x_n0^j| <ℇ/3

i,j≥i₀ |xⁱ-x^j|≤|xⁱ-x_n0ⁱ| + |x_n0ⁱ-x_n0^j| + |x_n0^j-x^j| <ℇ (1.14)

Se poate arata ca

x_n∈c, n∈ℕ x_n=(x_nⁱ)

(siruri convergente

daca lim x_n=x in l^∞

x=(xⁱ)_i∈ℕ rezulta ca x∈c si

x₁ x₁ x₁² . x₁ⁱ →

x₂ x₂ x₂² . x₂ⁱ →

x  x x² . xⁱ →

teorema de inversare la limita

1.4.5 Normarea si completitudinea spatiului c₀

c₀ = este spatiul sirurilor convergente la 0.

Pentru x=(xⁱ)_i∈ℕ ∈c₀ ||x||=sup

(se poate arata ca ||x||=max

∃ i₀∈ℕ astfel incat ∀i∈ℕ |xⁱ|≤|xⁱ⁰|

c₀⋐c⋐ l^∞

c₀ este spatiu Banach

c₀⋐ l^∞ c₀ inchis c₀=

⊂c₀ ? x∈ → x∈ c₀ ?

x∈ ⇒∃ (x_n)_n∈ℕ ⊂ c₀

∀ℇ>0 ∃n₀∈ℕ ∀n≥n₀ , ||x_n-x|| <ℇ

∀ℇ>0 ∃n₀∈ℕ ∀n≥n₀ , ∀i∈ℕ, |x_nⁱ-xⁱ| <ℇ

x∈c₀ ⇔ ∀ℇ>0 ∃i₀∈ℕ ∀i≥i₀ , |xⁱ| <ℇ

∀ℇ>0 ∃n₀∈ℕ ∀n≥n₀ , ∀i∈ℕ, |x_nⁱ-xⁱ| <ℇ/2

n=n₀ ⇒ ∀i∈ℕ, |x_n0ⁱ-xⁱ| <ℇ/2 (1.15)

(x_n0) ∈c₀ ⇒ ∃i₀∈ℕ ∀i≥i₀ , |x _n0ⁱ| <ℇ/2 (1.16)

Din (1.15) si (1.16) rezulta ca ∀i≥i₀ , |x ⁱ| ≤|x_nⁱ-xⁱ| + |x _n0ⁱ| <ℇ

Capitolul 2: Metoda lui Jacobi pentru sistemele liniare finite in ℝⁿ

2.1. Norme vectoriale in ℝⁿ

Consideram spatiul ℝⁿ si orice norma definita pe acest spatiu o vom denumi norma vectoriala. Sa reamintim axiomele normei: norma || || : ℝⁿ →ℝ este o functie care verifica urmatoarele axiome:

1. ||x+y||≤ ||x|| + ||y|| pentru orice x,y ∈ ℝⁿ

2. ||αx||= |α| ||x|| pentru orice α ∈ ℝ si orice x ∈ ℝⁿ

3. ||x||≥0 pentru orice x ∈ ℝⁿ si ||x||=0 daca si numai daca x=θ_ℝⁿ

In continuare dam exemple de norme vectoriale:

1. Norma euclidiana: ||x||₂=, unde x=(x₁, x₂, ., x_n) ∈ ℝⁿ

2. Norma maximum: ||x||_∞= max , unde

x=(x₁, x₂, ., x_n) ∈ ℝⁿ

3. Norma octaedrica: ||x||₁= , unde x=(x₁, x₂, ., x_n) ∈ ℝⁿ

O generalizare naturala a acestor norme ar fi norma data de formula :

||x||_p= , unde p∈[1, +∞)

este un numar real fixat sau simbolul +∞, iar x=(x₁, x₂, ., x_n) ∈ ℝⁿ.

In cazul p +∞ dam urmatoarea interpretare:

||x||_∞== max

Mentionam faptul ca, pe spatiul ℝⁿ oricare doua norme vectoriale sunt compatibile, adica oricare ar fi o norma vectoriala || || pe ℝⁿ exista constantele c₁, c₂ >0 astfel incat c₁||x||₂≤||x||≤c₂||x||₂, pentru orice x∈ ℝⁿ.

2.2. Norme matriciale in M_mxn (ℝ).

Consideram spatiul liniar al matricilor cu elemente numere reale avand m lini si n coloane, notat cu M_mxn (ℝ).

2.2.1 Definitie

O norma, || ||: M_mxn (ℝ) →ℝ definita pe spatiul liniar M_mxn (ℝ) o vom numi norma matriciala si se defineste cu aceleasi axiome:

1. ||A+B||≤||A|| + ||B||, pentru orice A,B ∈ M_mxn (ℝ)

2. ||αA||=|α| ||A||, pentru orice α∈ℝ si orice A∈ M_mxn (ℝ)

3. ||A||≥0, pentru orice A ∈ M_mxn (ℝ) si ||A||=0 daca si numai daca A=O_mxn, unde cu O_mxn am notat matricea nula cu m lini si n coloane.

Un exemplu de norma matriciala ar fi:

||A||= , unde A=∈ M_mxn (ℝ).

Daca m=n atunci avem matricile patratice de ordinul n cu numere reale, notate simplu cu M_n (ℝ) in loc de M_nxn (ℝ). In acest caz mai adaugam si urmatoarea axioma la axiomele normei matriciale:

4. ||A·B||≤||A||·||B|| pentru orice A,B ∈ M_n (ℝ)

Exemple de norme matriciale pentru matrici patratice

Norma Frobenius definita de relatia ||A||_F = , este o norma matriciala.

Vom arata ca aceasta norma satisface conditiile din definita normei matriciale.

Introducem notatiile:

= [C₁ C₂.C_n] in care

L_i = (a_i1 a_i2 . a_in)∈ℂⁿ, i=1, ., n; C_j = ∈ℂ^m, j=1, ., n.

Cu aceste notatii vom avea:

||A||_F =

Din definitie rezulta ca:

(1) ||A||_F ≥0 ⇔∀i=1,.m, ∀j=1,.n, a_ij = 0 ⇔A = 0.

(2) Fie A = () ∈ℂ^mxn si B=( ∈ℂ^mxn

Consideram vectorii:

a = () ∈ℂ^m si b ) ∈ℂ^m . Atunci produsul scalar in ℂ^m . Din aceste relatii rezulta

.

Deci .

(3) Fie ∈ ℂ si A ∈ ℂ^mxn . Avem

(4) Fie matricile A ∈ℂ^mxn si B ∈ℂ^mxn

, ℂⁿ, - linia i a matricii A

ℂⁿ - coloana j a matricii B.

Matricea produs M=A*B ∈ ℂ^mxp are elementele

.

Am aratat ca aplicatia Frobenius este o norma matriciala.

Aplicatia ||A||_max = max nu este o norma matriciala.

Pentru n=2 fie

A*B = I₂, ||A||_max =||B||_max =

||A*B||_max =1 > ||A||_max ·||B||_max =

2.2.2 Norme matriciale naturale

Fie ||·||_v : ℝⁿ → ℝ o norma vectoriala. Pornind de la aceasta norma vectoriala definim o norma matriciala numita norma matriciala naturala sau indusa.

= max

= max

||A||_i se numeste norma matriciala naturala sau norma indusa de norma vectoriala ||·||_v .

Avem urmatoarea relatie:

||Ax||_v≤ ||A||_i||x||_v , ∀A∈ ℝ^nxn, ∀x∈ ℝⁿ .

Norma Frobenius ||·||_F nu este o norma naturala. Intr-adevar, pentru orice norma vectoriala ||·||_v , norma matriciala indusa a matricii unitate este 1:

iar in cazul normei Frobenius avem :

||I_n||_F = (1+1+.+1)^1/2 = ≠1 pentru n≥2.

Pentru ||x||₁ = norma matriciala indusa este:

||A||₁ = max

Pentru ||x||_∞ = max norma matriciala indusa este:

||A||_∞ = max.

Daca ||·||_v este o norma vectoriala si P∈ ℝ^nxn este o matrice nesingulara atunci aplicatia ||·||_P: ℝⁿ→ ℝ , ||x||_p = ||Px||_v este deasemenea o norma vectoriala. Consideram normele matriciale induse de ||·||_v si ||·||_P - ||·||_i si respectiv ||·||_i,P . Legatura dintre cele doua norme matriciale este data de relatia ||A||_i,P= ||PAP^-1||_i .

2.3. Compatibilitatea normelor vectoriale cu cele matriciale in ℝⁿ

2.3.1 Definitie

O norma matriciala pe spatiul liniar M_n (ℝ) se numeste compatibila cu o norma vectoriala pe spatiul ℝⁿ daca are loc inegalitatea ||A·x||≤ ||A||·||x|| pentru orice matrice A∈ M_n (ℝ) si orice vector x∈ℝⁿ .

Se verifica usor ca norma matriciala ||A||=, unde

A= ∈ M_n (ℝ), este compatibila cu norma vectoriala euclidiana ||x||₂=, unde x=(x₁, x₂, ., x_n) ∈ ℝⁿ

Mentionam faptul ca inegalitatea ||A·x||≤||A||·||x|| exprima continuitatea aplicatiilor liniare definite pe spatiul ℝⁿ reprezentate prin matricile A.

2.4. Norme matriciale subordonate normelor vectoriale in ℝⁿ

2.4.1 Definitie

Dintre toate normele matriciale compatibile cu o norma vectoriala sa alegem pe cea mai mica, data de formula

In acest fel se defineste o norma. Tot la fel se demonstreaza ca

.

Aceasta norma matriciala o vom denumi norma matriciala subordonata normei vectoriale.

In continuare prezentam normele matriciale subordonate diferitelor norme vectoriale:

1. pentru norma vectoriala euclidiana avem norma matriciala subordonata data de formula: ||A||₂ = unde este cea mai mare valoare proprie a matricii A*A, unde A* este matricea adjuncta a matricii A. Mentionam ca toate valorile proprii ale lui A*A sunt pozitive, iar matricea adjuncta A* se obtine din matricea A printr-o transpunere in cazul real.

2. pentru norma vectoriala maximum avem norma matriciala linie data de formula :

||A||_∞ = .

3. pentru norma vectoriala octaedrica avem norma matriciala coloana data de formula:

||A||₁ = .

2.5. Perturbatii

Fie dat sistemul liniar sub forma matriciala A·x = b, unde

A=∈ M_n (ℝ), x=(x₁, x₂, ., x_n)^T ∈ ℝⁿ, b=(b₁, b₂, ., b_n)^T ∈ ℝⁿ. Presupunem ca avem un sistem de tip Cramer cu det A≠0. Totodata presupunem ca datele de intrare: elementele matricii A si elementele termenului liber b sufera mici perturbatii, si am astepta ca si la datele de iesire x sa obtinem perturbatii de acelasi ordin. Insa acest lucru nu se adevereste, si ne vom exprima sub forma: sistemul liniar este instabil din punct de vedere numeric, daca numarul de conditionare ℋ(A)=||A|| ·||A^-1|| este "mare", de ordinul 10⁵, 10⁶, .

Presupunem prima data ca termenul liber b sufera mici perturbatii, iar matricea A ramane neschimbata. Variatia termenului liber b, notata cu δb, induce o variatie a solutiei x, notata cu δx: A·(x + δx) = b + δb, de unde rezulta Ax + Aδx = b + δb, deci A·δx = δb, adica δx = A^-1·δb. Prin urmare:

||δx|| = ||A^-1·δb|| ≤ ||A^-1||·||δb||. Asadar,

.

Insa, ||A||·||x||≥||A·x|| = ||b||, deci

.

Prin urmare daca numarul de conditionare este "mic" de ordinul 10^-1, 10⁰, 10¹, atunci o perturbatie mica a termenului liber δb, va implica conform inegalitatii anterioare o perturbatie mica a solutiei δx.

Insa, daca numarul de conditionare ℋ(A)=||A|| ·||A^-1|| este mare, de ordinul 10⁵, 10⁶, , atunci se poate intampla ca la o variatie mica a termenului liber δb, de exemplu de ordinul 10^-2 , sa obtinem o variatie a solutiei δx de ordinul 10^-2·10⁵ = 10³. Prin urmare, daca numarul de conditionare este "mic" atunci sistemul liniar este stabil din punct de vedere numeric, iar daca numarul de conditionare este "mare", atunci sistemul liniar poate sa fie instabil din punct de vedere numeric.

De aceasta data presupunem ca elementele matricii A sufera mici perturbatii, notate cu δA, iar termenul liber ramane neschimbat. Obtinem o perturbatie a solutiei x notata cu δx: (A+ δA)(x+ δx) = b, adica

A·x + δA·x + A·δx + δA·δx = b, deci A·δx = -δA(x+δx). Prin urmare: δx = +A^-1· δA·(x+ δx) de unde :

|| δx || = ||-A^-1· δA·(x+ δx)|| = ||A^-1·δA·(x+ δx)|| ≤

≤ ||A^-1||·||δA||·||x+· δx||,

adica,

.

Se observa ca si si de aceasta data putem trage aceleasi concluzii ca si la prima presupunere, si anume: daca numarul de conditionare ℋ(A) este "mic", atunci sistemul este stabil din punct de vedere numeric, iar daca numarul de conditionare este "mare", atunci sistemul liniar devine instabil din punct de vedere numeric.

2.6. Metoda numerica a lui Jacobi pentru sistemele liniare finite in ℝⁿ

Se considera sistemul liniar sub forma matriciala A·x b, unde

A=∈ M_n (ℝ), x=(x₁, x₂, ., x_n)^T ∈ ℝⁿ,

b=(b₁, b₂, ., b_n)^T ∈ ℝⁿ. Forma algebrica a sistemului liniar este:

Daca presupunem ca a_ii≠0 pentru orice , atunci sistemul liniar se poate pune sub forma echivalenta, denumita forma iterativa, in felul urmator: din prima ecuatie se scoate necunoscuta x₁, din a doua necunoscuta x₂, , din ultima ecuatie necunoscuta x_n, si se obtine:

Transcriem sistemul iterativ sub forma matriciala:

.

Introducem notatiile:

, si .

Astfel sistemul initial apare sub forma matriciala iterativa echivalenta: x=B_j·x + c_j. Alegem un punct initial de pornire x=(x⁰₁, x⁰₂, ., x⁰_n) ∈ ℝⁿ si incepem sa iteram sirul (x^k)_k∈ℕ⊂ℝⁿ in felul urmator:

x¹=B_j·x⁰ + c_j, x²=B_j·x¹ + c_j, , x^k+1=B_j·x^k + c_j,

Iteratia x^k+1=B_j·x^k + c_j scrisa pe larg inseamna:

ceea ce este echivalent cu

pentru orice . Astfel putem determina matricile B_j si c_j in functie de datele initiale: matricile A si b. Intr-adevar, fie A=L+D+U descompunerea matricii A in matricea strict inferior triunghiulara L, matricea diagonala D si matricea strict superior triunghiulara U. Mentionam ca matricile L, D, U sunt matrici patratice de ordinul n, unde elementele nealese din matricea A sunt egale cu zero. Prin urmare: L·x^k + D·x^k+1 + U·x^k = b, adica:

x^k+1 = -D^-1(L+U)·x^k + D^-1b, ceea ce inseamna ca B_j = -D^-1(L+U) si c_j=D^-1b. Deoarece conform presupunerii a_ii≠0 pentru orice rezulta ca exista matricea inversa D^-1, caci det(D)=

Mentionam urmatorul rezultat referitor la convergenta sirului (x^k)_k∈ℕ ca o conditie suficienta:

2.6.1 Propozitie

Daca matricea A este dominant diagonala, adica pentru orice , atunci sirul iterativ (x^k)_k∈ℕ⊂ℝⁿ generat mai sus va fi convergent pentru orice punct initial de pornire x⁰∈ℝⁿ .

Demonstratie: Sa alegem pe ℝⁿ norma vectoriala maximum:

||x||_∞ = max si norma matriciala subordonata, numita norma linie, data de formula ||B_j||_∞ = , unde B=. Pentru orice conditia este echivalenta cu , adica suma elementelor in modul in linia i din matricea B_j este strict mai mica decat unu. Prin urmare

.

Astfel, daca notam cu Φ: ℝⁿ → ℝⁿ , Φ(x) = B_jx + c_j, functia iterativa prin care generam sirul iterativ (x^k)_k∈ℕ (x^k+1=Φ(x^k)=B_jx^k + c_j), atunci pentru orice

x,y ∈ℝⁿ avem:

|| Φ(x) - Φ(y)||_∞ = ||(B_jx + c_j) - (B_jy + c_j)||_∞ = ||B_j(x - y)||_∞ ≤ ||B_j||_∞·||x - y||_∞ .

Aceasta conditie exprima faptul ca Φ este o contractie pe ℝⁿ avand constanta de contractie ||B_j||_∞ < 1. Suntem gata cu demonstratia teoremei, fiindca este de ajuns sa aplicam teorema de punct fix a lui Banach pentru contractia Φ pe spatiul metric complet ℝⁿ , unde metrica este generata de catre norma vectoriala maximum. q.e.d.

Presupunem ca sirul iterativ (x^k)_k∈ℕ⊂ℝⁿ este convergent, si fie

lim_k→∞ x^k = x^*. Trecand la limita in recurenta x^k+1 = B_jx^k + c_j pentru k→∞ obtinem ca x^* = B_jx^* + c_j , ceea ce este echivalent cu Ax^* = b. Prin urmare in acest fel generam un sir iterativ (x^k)_k∈ℕ care converge catre solutia sistemului initial A·x = b.

Capitolul 3: Metoda lui Jacobi pentru sistemele liniare infinite

3.1. Spatii de siruri: l¹, l², l^p, l^∞.

Spatiile Banach finit dimensionale reprezinta fara indoiala cea mai investigata clasa de spatii Banach si constituie un model si in acelasi timp un instrument pentru teoria infinit dimensionala.

Spatiile Banach finit dimensionale sunt reflexive, au baza, sunt complementate in orice spatiu Banach care le contine ca subspatii. Toate spatiile Banach de dimensiune n sunt izomorfe (algebric si topologic), astfel incat teoria izomorfa a acestor spatii este saraca. In schimb teoria izometrica ridica probleme interesante si profunde a caror solutionare necesita un aparat matematic complicat, bazat pe demonstrarea unei inegalitati foarte fine.

Cele mai simple spatii Banach finit dimensionale sunt spatiile l^p (n), 1≤p≤∞, formate din toate n-uplurile a = (a₁,,a_n) de scalari si inzestrate respectiv, cu norma:

Exemple

Spatiul de siruri l¹ = , adica suma seriei trebuie sa fie o suma finita.

Exemplu:

Spatiul de siruri l²

deoarece

, dar

Spatiul de siruri l^p: l^p =

Spatiul l

Vom vorbi in continuare si vom face o prezentare mai pe larg a spatiului general de siruri l^p, cand p≥0.

Fie K o multime (K poate fi ℝ sau ℂ).

Fie un spatiu s =

Fie x,y∈s. x+y∈s, ∈k. s este spatiu vectorial.

Pentru p>0, l^p=

Pentru p=0, l⁰=

Fie X un spatiu vectorial. Y⋐X. Y subspatiu vectorial a lui X

⇔

3.1.1 Propozitie

Spatiul l^p , cu p≥0, este spatiu vectorial.

Demonstratie

Vrem sa aratam ca l^p este un subspatiu a lui s, adica l^p⋐s.

Fie x = (xⁱ)_i∈ℕ, x ∈ l^p,

si y = (yⁱ)_i∈ℕ, y ∈ l^p,

x + y = (xⁱ + yⁱ) _i∈ℕ ⇒(?) (x + y) ∈ l^p

|xⁱ + yⁱ|^p ≤ (|xⁱ| + |yⁱ|)^p ≤ (2⋅max)^p =

= 2^p⋅(max)^p =

=2^p⋅(max) ≤ 2^p⋅(|xⁱ|^p + |yⁱ|^p)

, aceasta suma este finita, deci apartine lui l^p.

In continuare vom demonstra inegalitatea lui Young

Inegalitatea lui Young

Fie p,q>1, astfel incat . Atunci ,

Demonstratie

Fie t > 0.

t = 1 este punct de minim. Se ia

, t=1

/⋅uv

, , atunci

Folosind inegalitatea lui Young, vom demonstra acum inegalitatea lui Hőlder.

Inegalitatea lui Hőlder

Fie p,q > 1. x ∈ l^p, y l^q. Atunci,

.

Daca am avea p=2, q=2, am avea

care este inegalitatea lui Cauchy - Buniakowski - Schwarz

Demonstratie

,

;

Asadar

Folosind inegalitatea lui Hőlder, vom demonstra inegalitatea lui Minkowski

Inegalitatea lui Minkowski

Fie p ≥ 1 si x,y ∈ l^p. Atunci:

Demonstratie

p=1.

p>1

ζ∈s, ζ_i=|xⁱ+yⁱ|^p-1. ζ∈l^q ⇔

, deoarece x,y ∈ l^p

continuam inegalitatea

pentru adevarat

altfel impartim cu si rezulta

, ceea ce trebuia demonstrat.

Cu ajutorul inegalitatii lui Minkowski am demonstrat acum inegalitatea triunghiului, deoarece ||x||_p = , care este norma pe l^p. Si atunci:

||x+y||_p = ||x||_p + ||y||_p, care este o proprietate a normei.

3.2. Norme vectoriale pe spatii de siruri l^p

3.2.1 Definitie

Fie un sir de numere reale reprezentate in forma unui vector infinit de tip coloana, si notam cu s spatiul liniar real al acestor siruri. Fie

p ∈[1,+∞) un numar real si definim l^p = .

Este binecunoscut ca l^p este un subspatiu liniar real al spatiului s si pentru orice x∈ l^p formula defineste o norma pe l^p. Astfel, (l^p, ||·||_p) nu doar ca este un spatiu normat liniar, ci si un spatiu Banach, de asemenea. Pentru p=1 si p=2 vom reobtine spatiul Banach l¹ si respectiv, spatiul Hilbert l². In l² vom considera produsul scalar standard dat de formula (x,y) = pentru orice x, y ∈ l². Pentru p,q ∈[1,+∞) numere reale, p<q rezulta l^p⊂l^q. Daca s₀ este un subspatiu liniar al sirurilor convergente la 0 atunci l^p ⊂ s₀ pentru orice p ∈[1,+∞). Vom considera de asemenea subspatiul liniar l^∞ = . Pentru orice x∈ l^∞ formula

||x||_∞ = defineste o norma pe l^∞. Astfel, (l^∞, ||·||_∞) nu este doar un spatiu liniar normat ci si un spatiu Banach de asemenea. Avem: l¹ ⊂ l² ⊂ s₀ ⊂ l^∞ ⊂ s. Toate aceste spatii le vom numi spatii vectoriale cu elemente vectori si mai sus mentionatele norme vectoriale.

Norme matriciale pentru matrici infinite

3.3.1 Teorema

Fie A=(a_ij)_i,j∈ℕ o matrice infinita de numere reale si vom nota cu M spatiul liniar real al acestor matrici infinite. Fie M¹ = . Atunci M¹ este un subspatiu liniar real al lui M si pentru fiecare A∈M¹, formula defineste o norma pe M¹ numita norma coloana. Astfel, (M¹, ||·||₁) devine nu numai un spatiu normat linear real, ci si un spatiu Banach, de asemenea.

Fie p∈(1, +∞) un numar real si definim

M^p = , unde q este un numar real astfel incat .

Teorema

Spatiul M^p este un subspatiu real liniar al lui M si pentru orice A∈M^p, formula

||A||_p =

defineste o norma pe M^p. Spatiul (M^p, ||·||₁) este un spatiu Banach.

Demonstratie

Folosind de doua ori inegalitatea lui Minkowski vom obtine:

||A+B||_p = =

= ≤

≤

≤

=

=||A||_p + ||B||_p.

Pentru α∈ℝ si A∈ M^p avem

A||_p =

.

In final obtinem ||A||_p ≥ 0 si ||A||_p = 0 de unde rezulta =0, deci a_ij =0 pentru orice i,j ∈ℕ , adica A = O_∞ , unde O_∞ inseamna matricea nula.

Fie (Aⁿ)_n∈ℕ , Aⁿ = , un sir fundamental in spatiul normat

(M^p, ||·||_p), adica pentru orice Ɛ>0 exista n_Ɛ ∈ℕ astfel incat pentru orice

n,m≥ n_Ɛ, ||Aⁿ-A^m||_p≤Ɛ. Oricare ar fi i₀,j₀∈ℕ numere naturale fixate, vom obtine:

==

= ||Aⁿ-A^m||_p ≤ Ɛ.

In consecinta, pentru fiecare i₀,j₀∈ℕ, sirul de numere reale este fundamental, ceea ce implica convergenta acestui sir in ℝ. Fie ℝ astfel incat si vom construi matricea A=(a_i0j0)_i0,j0∈ℕ. Vom folosi notatia deoarece pentru orice i,j∈ℕ. Acum, folosind continuitatea normei ||·||_p, din inegalitatea ||Aⁿ-A^m||_p≤Ɛ adevarat pentru orice n,m≥n_Ɛ vom avea:

, adica ||Aⁿ-A^m||_p≤Ɛ, oricare ar fi n≥n_Ɛ.

Asta inseamna ca sirul (A_n)_n∈ℕ este convergent la matricea A in norma ||·||_p. Dar, ||A||_p≤||A-Aⁿ⁰||_p+||Aⁿ⁰||_p≤Ɛ+||Aⁿ⁰||_p,

Pentru un punct fixat n₀∈ℕ, n₀≥n_Ɛ.

Asadar A∈M^p, ceea ce incheie aceasta demonstratie.

Pentru p=2 vom obtine M² = . Daca luam in M² produsul scalar dat de formula (A,B) = , unde A = (a_ij)_i,j∈ℕ si

B = (b_ij)_i,j∈ℕ atunci (M², (·,·)) va fi un spatiu Hilbert.

Fie M^∞ = .Atunci M^∞ este un subspatiu liniar real al lui M si pentru orice A∈M^∞, formula ||A||_∞ = defineste o norma pe M^∞, numita norma linie. Astfel, (M^∞, ||·||_∞) devine nu numai un spatiu liniar normat, ci si un spatiu Banach.

3.3.3. Corolar

Daca pentru matricea A=(a_ij)_i,j∈ℕ avem a_ij = 0 pentru i>n sau j>n, n∈ℕ, atunci din teorema de mai sus vom reobtine rezultatele in spatiul finit dimensional ℝⁿ.

Toate aceste spatii le vom numi spatii matriciale si mai sus mentionatele norme, norme matriciale.

3.4. Compatibilitatea normelor vectoriale cu normele matriciale in l^p

Fie x ∈ s un sir de numere reale si A=(a_ij)_i,j∈ℕ ∈M o matrice infinita de numere reale.

3.4.1. Definitie Vom defini produsul A·x daca pentru fiecare i∈ℕ, seriile sunt convergente. In acest caz vectorul rezultat y = A·x este un vector coloana cu componentele .

3.4.2. Teorema

Pentru orice p ∈ [1, +∞] = [1, +∞) ∪ , norma vectoriala ||·||_p definita pe l^p este compatibila cu norma matriciala ||·||_p definita pe M^p , adica ||Ax||_p ≤ ||A||_p ·||x||_p oricare ar fi x∈ l^p si oricare ar fi A ∈ M^p .

Demonstratie

Fie p=1. Atunci

Fie p ∈ [1, +∞]. Folosind inegalitatea lui Hölder vom obtine

=

.

Fie p = +∞. Atunci,

.

3.4.3. Corolar

Daca pentru matricea A=(a_ij)_i,j∈ℕ avem a_ij = 0 pentru i>n sau j>n, n∈ℕ, atunci din teorema 3.4.2. vom reobtine rezultatele in spatiul finit dimensional ℝⁿ.

3.5. Norme matriciale subordonate normelor vectoriale in l^p

Pentru orice p ∈[1, +∞] si pentru orice x ∈ l^p si A ∈ M^p avem ||Ax||_p ≤ ||A||_p ·||x||_p conform teoremei 3.4.2. Daca x ≠ (elementul nul al spatiului vectorial l^p), atunci si putem defini . Se stie ca aceasta formula defineste o norma matriciala pe M^p pe care o putem numi norma matriciala subordonata normei vectoriale ||·||_p definita pe l^p si notam cu . Este evident ca pentru orice A ∈ M^p .

3.5.1. Teorema

Pentru orice p∈ avem

Demonstratie

Fie p=1. Stim ca . Trebuie sa aratam ca . Din rezulta ca : pentru orice ℇ>0 exista un j₀∈ℕ astfel incat . Alegem vectorul x∈l¹ astfel incat toate componentele lui x sunt zero, cu exceptia componentei j₀. Deci

.

In consecinta,

,

adica

pentru orice ℇ>0. asta inseamna ca .

Fie p=+∞. Avem . Trebuie sa demonstram ca .

Din ||A||_∞ obtinem: pentru orice ℇ>0 atunci exista i₀∈ℕ astfel incat

. Alegem un vector x∈l^∞ astfel incat componenta j∈ℕ a lui x este egala cu x_j=sign(a_i0j), oricare ar fi j∈ℕ, unde sign este functia semn.

Deci ||x||_∞=1 si

In consecinta,

, adica

oricare ar fi ℇ>0. Asta inseamna ca .

3.5.2. Corolar

Daca pentru matricea A = (a_ij)_I,j∈ℕ avem a_ij=0 pentru i>n sau j>n, n∈ℕ, atunci din teorema 3.5.1. vom reobtinem rezultatele in spatiul finit dimensional ℝⁿ.

Mentionam ca este necunoscut cum putem calcula pentru p∈(1,+∞) norma matriciala subordonata normei vecoriale ||⋅||_p definita pe l^p.

Spatiile vectoriale si matriciale mai sus prezentate le vom folosi pentru a extinde metoda lui Jacobi, cunoscuta ca metoda iterativa numerica, din sisteme liniare finite la sisteme liniare infinite. In acest fel putem studia procesele liniare stationare cu un numar de parametri infinit dar numarabil..

3.6. Metoda lui Jacobi pentru sistemele liniare infinite

Mai intai sa ne reamintim bine-cunoscuta teorema de punct fix a lui Banach pentru spatiile Banach

3.6.1. Teorema

Fie ( X, ||⋅||_x ) un spatiu Banach, si φ o contractie (exista o constanta α∈(0,1) astfel incat || (x)- (y)||_x ≤ ⋅ ||x-y||_x , oricare ar fi x,y ∈ X). Atunci pentru orice x⁰ ∈ X sirul (x^k)_k∈ℕ, generat de formula recursiva x^k+1 = (x^k), este convergent si are limita in punctul x^* ∈ X, care este un punct unic, fix, al functiei φ in X.

Sa consideram sistemul liniar infinit de ecuatii Ax = b, unde A∈M si x,b ∈ s .

3.6.2. Definitie

Se da A ∈ M si b ∈ s. Vom spune ca x^* ∈ s este solutie a sistemului liniar infinit de ecuatii Ax = b si avem Ax^* = b.

Asta inseamna ca toate aceste serii sunt convergente si avem

, oricare ar fi i ∈ ℕ.

Sa presupunem ca a_ii ≠ 0 pentru orice i ∈ ℕ. Atunci ecuatia este echivalenta cu ecuatia

, adica

.

Asadar sistemul initial de ecuatii liniare Ax = b este echivalent cu urmatorul sistem iterativ de ecuatii liniare: x = B_jx + c, unde

si .

Alegem x⁰ ∈ s si generam sirul (x^k)_{k∈ ℕ} ⊂ s dupa urmatoarea formula iterativa: x^k+1 = B_j⋅x^k + c.

3.6.3. Definitie

Matricea A = (a_ij)_{i,j∈ ℕ} este l¹ dominant diagonala daca exista λ ∈ (0,1) astfel incat pentru fiecare j ∈ ℕ avem λ⋅|a_jj| >

Este imediat evident ca A este l¹ dominant diagonala daca si numai daca

.

3.6.4. Definitie

Matricea A = (a_ij)_i,j∈ℕ este l^p dominant diagonala daca exista constanta pozitiva α_i > 0 pentru i∈ℕ astfel incat si ,

unde p > 1 si .

Este imediat evident ca A este l^p dominant diagonala daca si numai daca

.

3.6.5 Definitie

Matricea A = (a_ij)_i,j∈ℕ este l^∞ dominant diagonala daca exista λ ∈ (0,1) astfel incat pentru fiecare i ∈ ℕ avem λ⋅|a_ii| >

Este imediat evident ca A este l^∞ dominant diagonala daca si numai daca

.

3.6.6 Teorema

Daca A este l^p dominant diagonala, unde p ∈ [1, +∞], atunci sirul iterativ (x^k)_k∈ℕ este convergent in l^p oricare ar fi x⁰ ∈ l^p. Punctul limita x^* ∈ l^p este unica solutie a sistemului liniar Ax = b.

Demonstratie

Conditia ca A sa fie l^p dominant diagonala este echivalenta cu ||B_j||_p < 1 pentru orice p ∈ [1,+∞]. Astfel putem aplica teorema de punct fix a lui Banach pentru functii iterative : l^p → l^p, φ(x) = B_j⋅x + c. Intr-adevar, φ este o contractie pe l^p , deoarece || (x) - (y)||_p = ||(B_j⋅x + c) - (B_j⋅y + c) ||_p =

= ||B_j(x - y) ||_p ≤ ||B_j||_p ⋅ ||x - y||_p.

Asta inseamna ca sirul (x^k)_k∈ℕ este convergent in l^p oricare ar fi x⁰ ∈ l^p si punctul limita x^* ∈ l^p este unicul punct fix din φ in l^p, astfel incat φ(x^*) = x^*.

Deci B_j ⋅ x^* + c = x^*, ceea ce este echivalent cu Ax^* = b.

3.6.7 Consecinta

Daca pentru matricea A = (a_ij)_i,j∈ℕ avem a_ij = 0, unde i > n sau j > n, si

b_i = 0 pentru i > n, n ∈ ℕ , atunci vom reobtine sistemul linear cu numar finit de ecuatii si numar finit de necunoscute. Astfel din teorema 3.6.6 obtinem metoda clasica numerica iterativa a lui Jacobi de rezolvare a sistemelor liniare finite de ecuatii.

Bibliografie

[1] Cristescu M., Analiza matematica, Editura Universitatii "Petru

Maior" Targu Mures, 2003

[2] Finta B., Analiza numerica, Editura Universitatii "Petru Maior"

Targu Mures, 2004

[3] Finta B., Jacobi's Theorem for Infinte Systems of Linear Equations,

volum omagial, Profesor Gheorghe Farcas la varsta de 70 de ani,

Editura Universitatii "Petru Maior" Targu - Mures, pag. 103-108,

2004

[4] Gaspar D., Analiza functionala, Editura Facla, Timisoara, 1981

[5] Niculescu C., Popa N., Elemente din teoria spatiilor Banach Editura Academiei, Bucuresti, 1981

[6] Paltineanu G., Analiza matematica, Calcul diferential, Editura Agir, Bucuresti, 2002