Rezolvari probleme

Subiectul 1 Metoda punctului fix

Evaluarea erorii

Vrem : test | a - x_n | < EPS

Avem efectiv : | x_n+1 - x_n | <= XTOL

Metoda punctului fix :

| a - x_n | = |(a- x_n+1)+( | x_n+1 - x_n)| < |a- x_n+1|+|x_n+1-x_n|<l a-x_x| + |x_n+1 - x_x|

g(x) - g(x") <= l(x-x') lipschitz ; l-constanta

(1-l a - x_n | <= | x_n+1 - x_n| ; |a - x_n| <= [1/(1-l)] | x_n+1 - x_n|

|a-x_n+1| = |g(a) - g(x_n)| <= l a - x_n |

a-x_n+1| <= l/[(1-l)] /| x_n+1 - x_n| <= EPS | x_n+1 - x_n| <= ((1-l)/l)EPS

| x_n+1 - x_n| <= XTOL

XTOL = ((1-l)/l)EPS

^g`*

Subiectul 2 Metoda punctului fix:

Procesul stationar.

X_n+1 = g(x_n)

g

| x₁=g(x₀), x₁ =/= x₀

|x₂=g(x₁)

iteratia se zice ca este un proces

stationar daca x₂ = x₀ si x₁ =/= x₀

g(g(x₀) = x₀ g(g(x) = x (1)

g'(g(x)g'(x) = 1

-satisface (1) g(

g'()g'() = 1 [g'()]² =1 g'()=±1

g(x) = g( ) + g'( x- )+. termenii de ordin superior

-iar cand se exclud termenii de termen superior se ajunge la : g(x)≈ + g'( x-

g g(x) ≈ + x- =x nu satisface pt ca x₁=x₀

g g(x) ≈  - (x-)=-x+2 satisface

concluzie : procesul stationar are loc daca g'() =-1 sau in practica g'() ≈ -1

obs procesul stationar este x₂ =x₀

x₀ x_n x₁ x_n+1 x₂ x_n+2

procesul stationar: x_n+2 = x_n

x_n x(n) x(n+2) = x(n)

x(t+T) = x(t) T-perioada fctie periodice

procedeul stationar studiat mai inainte se zice o orbita a aplicatiei g de perioada 2

x₀

x₁

x₂

x _{3  .}

x₄ = x₀

x(x+4) =x(n)

exemplu g(x)=

Subiectul 3 Metoda punctului fix:

Proceduri explicite de punct fix; Exemple: metoda coardei, metoda Newton.

Proceduri explicite ale pct fix:

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

propozitia 1 : fie Ф(x) fctie continua pe [a,b] si care nu se anuleaza pe [a,b]

g(x) = x- Ф(x)f(x) => ecuatia x=f(x) are aceeasi radacina ca si g(x)=x, f(x)=0 si numai acele radacini

Demonatratie: x=g(x) )f(

=g( ) =>- Ф( )f( )=0 => f(

f( )=0 => =g( Ф( )f(

propozitia 2: fie F(y) F(0)=0 si y=/=0 F(V)=/=0

(F(y)=0 =>y=0

atunci: g(x)=x-F(f(x)).

Ecuatia x=g(x) are o radacina ca si f(x)=0 si suma oe acestea

Ex metoda coardei: Ф(t)=m. y(x)=x-mf(x) f(x)=e^π - 3x² = 0

g(x)=x-0.01(e^x-3x²)

Trebuie sa avem g'( x) <1

-kg'(x) = 1-m f'(x) <1 -2<-mf'(x) <0 |(-1) o<mf'(x)<2

exemplu: f'(x) >0 =>m>0 m<2/f'(x)

obs: m-optim: g'( )≈0...... conv patratica p=2.

1-mf'( ) ≈ 0 m≈ m= cu x₀ ≈

interpretarea geometrica a metodei coardei

x_n+1 = x_n-mf(x_n) x₁ = x₀ - mf(x₀)

Y=f(x)

obs: m variabil

x_n+1 = x_n-mf(x_n)

la pas "n" = m_optim = ( x_n)

x_n+1 = x_n - f(x_n)

metoda newton

g(x)=x- Ф(x)f(x) Ф(x)=

subiectul 4 Metoda punctului fix:

Extrapolarea Aitken; Extrapolarea Aitken ca metoda de punct fix.

Extrapolarea aitken:

O procedura de accelerare a unui nr care converge liniar indiferent (oricare )ar fi procesul care genereaza sirul.

Cu trei valori succewsive se face o exploatare si aceasta valoare oinlocuieste uratoarea valoare x_n+1 = g(x_n) n ≥ 0

Ipoteza: sirul cinverge liniar: daca g'

general |C| => constanta erorii asimptotice

n>N₁ rap ≈ C

ip generala -egalkitatea este aproxim(≈)

relatia (1) se rezolva in raport cu

≈ a_n,n+2

Extrapolarea Aitken ca metoda de punct fix

a_n,n+2 = G(x) = x_n -

G(x) = x- x_n+1 = G(x_n) , x₀ = det

Proprietate: x= G(x) x=g(x)

Notam: p-ordin de convergenta a iteratiei x_n+1 = g(x_n)

P_G -odin de convergenta al iteratiei x_n+1 = G(x_n)

Teorema: f(x)=0, f( )=0 g(x) = x-Ф(x)f(x)

Atunci:a) daca p ≥ 2 in p_G =2_p-1

b) daca p = 1 in = radacina simpla => p_G=2

c) daca p ≤1 in =radacina multipla de ordin m

subiectul 5 Radacini multiple ale ecuatiei f(x) = 0:

Probleme; Metoda Newton; Metoda Newton modificata; Determinarea ordinului de multiplicitate.

Radacini multiple ale ecuatiei

Def: f(x)=(x- )^r -h(x) , h(

Conditie echivalenta f( ) = f'( )=...=f(^x+1)(

La problema poate fi modificata metoda Newton a.i. ardinea de convergenta sa devina 2 dar incertitudinea nu poate fi in laturata decat prin metode analitice, adica prin calculul lui ca radacina simpla a derivatei n1

r =2 f( ) = f'( ) = 0, f'(x)=/=0 f'(x)=0

Metoda Newton-radacini multiple

Daca =radacina multipla de ordinul r (a lui f)

atunci: 1.Metoda Newton au ord. p=1 in

2.C=1-1/r

Demonstratie: x_n+1 =g(x_n) g(x)=x- f(x)=(x- )h(x)

f'(x)=r(x- )^r-1h(x)+(x- )^rh'(x) g(x)=

g'( )=/=0 => ordin de convergenta (p)=1

Metoda Newton modificata

Este usor de modificat metoda Newton a.i. ordinul de convergenta sa devina iar 2.

Def. it. X_n+1 = x_n -r g(x) = x -r

g'( ) = 1-r => p=2

-recastigam convergenta partatica dar incertitudinea radacinii poate fi eliminata numai prin metoda analitica

Det ord de multiplicitate -x_n+1 = g( )-g(x_n) = g'(ξ_n)( -x_n)

g', g'-constant

n=mare

λ = g'( ) λ = - = 1 - λ r=

λ = Daca acest raport cvasi constant si produce un rest intreg atunci putem spune de de existenta unei radacini multiple

subiectul 6Radacinile unui polinom:

Calculul valorii polinomului; Reducerea gradului; Metoda Newton pentru polinoame.

1. calcul valorii polinomului:

a)forma data: p(x)=a₀+a₁x+......a_k(x^k-1)x+.....+a_n(x^n-1)x

nr de operatii (+ si x) in cazul a) sunt : n+; (2n-1)x

b)forma imbricata( schema Horner)

p(x)=a₀+x(a₁+x(a₂+......+x(a_n-1+xa_n)).....)

exemple: p(x)=a₀+a₁x+a₂x²+a₃x³ = a₀+x(a₁+a₂x+a₃x²) = a₀+x(a₁+x(a₂+xa₃)

nr de operatii: n+; n x

teoretic forma b) est emai precisa decea forma a)

p(x)=a₀+x(a₁+x(a₂+......+x(a_n-1+xa_n)).....) (*)

b_n=a_n

b_k = a_k+xb_k+1 ; k=n-1, n-2, ...1,0(**)

b_n=a_n

b_n-1=a_n-1 + xb_n

.........

b₂=a₂+xb₃

b₁ = a₁+xb₂

b₀ = a₀+xb_{1 .}

b₀ = p(x)

comentariu asupra calculului polinomului: consideram calcululpolinomului pe forma (a), apoi pe (b). Forma (b)poate fi:1).forma definita direct pe relatia (*) si 2). ciclu- (**)

din forma b2 in dubla precizie + rotunjire la simpla precizie => valoaea exacta in simpla precizie

2.reduerea gradului introducere in varisbila ξ

|b_n = a_n

|b_k = a_k + ξb_k+1; k= (1) b₀ = p₀(ξ)

introducem: 2(x, ξ) = b₁ + b₂x+......+b_nx^n-1

polinomul q(x) este catul impartiti lui p(x) la x - ξ

demonatratie: se verifica identitatea p(x) = q(x, ξ)(x - ξ) + p(ξ)

reducerea gradului:

ipoteza: ξ = radacina => p (ξ) = 0 p(x)=q(x ,ξ)(x - ξ)

Metoda Newton pt polinoame

p(x)= q(x, ξ)(x - ξ) + p(ξ)| x, ξ

p'(x)=g(x., ξ)+q'_x(x, ξ)(x - ξ) x, x =ξ

pt ξ, p'(ξ)=q(ξ ,ξ) q(ξ ,ξ) =q(x,ξ)|pt x =ξ x_n+1=x_n -

implementare : contine calculul valorii polinomului p' si pol q' din formula metodei Newton

-algoritmul

calculul se face intr-un ciclu pe baza formulelor coeficientilor pt p(x) si formulelor analoage pt q(x)

ξ=x_n | C_n=b_n

| C_k=b_k+ ξ C_k+1 ; k=n-1,...,1 (2)

C₁=q(ξ) (=q(ξ ,ξ)

Practic se scrie un segment de ciclu care inglobeaza formulele (1) si (2)

Subiectul 7 Radacinile unui polinom:

Algoritmul metodei Newton; Algoritmul cu reducerea gradului.

Algoritmul poate fi proiectat in doua moduri:

1)cate o radacina lucrand cu polinomuloriginal p(x)

2)reducerea gradului: - radaacina nr 1 se lucreaza cu p(x) - rad nr 2 se lucreaza cu q(x)

Reducerea gradului este un proces instabil; polinomul q(x, ξ) este afectat de err si va fi din ce in ce mai afectat de err pe masura ce gradul scade. Procesule ste instabi pt ca problema radacinilor unui polinim este de multe ori o problema instabila pt ca micile schimbari in ceficienti produc mari schimbari in problema

Wilkinson: 1)radacina se determina in ordine crescatoare 2) dupa pctul 1) cu valorile gasite ca aproximatie initiale se face o iteratie cu polinom original (rafinare, purificare a radacinilor )=> reducerea gradului

Determinarea succesiva a rada cu polinom dat p(x)

Subiectul 8 Radacinile unui polinom:

Radacini complexe; Stabilitatea radacinilor.

Radacini complexe

Metoda Newton se poate aplica si la radacini complexe cu conditia ca coeficientul polinomului sa fie declarat complex : in loc de Real a(0,n) avem Complex a(0,n)

Dezavantajul metodei este ca cere aproximatii initiale complexe

x1<x0<x2

Metoda Miller f(x)=0

-foloseste polinomul de interpolare

de gradul 2 f_i=f(x_i)

-se exclude pctul cel mai indepartat

de x₃ si se reia procedeul.

-metoda Muller are calitatea ca pornind de la aproximatii reale sa genereze radacini complexe

Metoda Laguerre - eficienta pt determinarea radacinilor reale sau complexe ale unui polinom. Avantaje: -converge independent de aproximatia initiala.

Z_i+1=z_i - unde fctia H(z_i) =(n-1)[(n-1)p'²(z_i)-np(z_i)p''(z_i)

Semnul dein fata radicalului se alege acelasi cu cel al lui p'(z_i)

-pt o radacina simpla p=3 -pt o radacina multipla p=1

in IMSL exista urmatoarea subrutina: ZPLRC determina toate zerouroile unui polinim

Are avantajul ca nu cere aproimatie initiala

Subiectul 9 Sisteme de ecuatii neliniare:

Definitii; Norme; Metoda punctului fix.

Un sistem de ecuatii neliare ae forma:

| f₁(x₁,x₂,...x_n)=0

|......

|f_n(x₁,x₂,...x_n)=0

f_i:I R; I Rⁿ (x₁,x₂,...x_n) I , f₁(x₁,x₂,...x_n)

; f(x)=

f(x)=0 f(

x=g(x).....(2') g(x)= f:I Rⁿ; g:I Rⁿ 

| x₁=g₁(x₁.....x_n)

| x_n=g_n(x₁,....,x_n) (2)

 =g()

norme:

norma unui vector: v...spatiu vectorial de dimensiune finita "n" xv; x=x₁e₁+.......+x_ne_n

x || . ||-norma ||x|| -norma lui x

definitia normei: norma este o apliactie a lui v in R care respecta urmatoarele axiome:

||x|| ≥ 0 si ||x||=0 x=0

||λx|| = |λ|.||x||.....λ=scalar (λR,xC)

||x+y|| ||x||+||y||

proprietati:

1. toate normele de pe spatiu V (de dimensiune finita subt echivalente) N(x)=||x||

N:v R_x fiind date doua norme N₁ si N₂ c,c'>0 C N₁(x) ≤ N₂(x) <C' N₁(x)

2.N(x) e fctie continua de x

observatie: concret N(x) =fctie continua de (x₁,x₂,...x_n)

norma unei matrici

An.... multimea matricelor A nxn ; a_ij R,C

Def2: ||.||:An R₊, adica A ||A||R₊ se numeste norma daca satisface urmaroarele axiome:

1||x|| ≥ 0 si ||x||=0 x=0

2||λx|| = |λ|.||x||.....λ=scalar (λR,xC)

3||x+y|| ≤ ||x||+||y||

4||Ax||_v ≤ ||A||.||x||_v...AA_n ;xv

5.||AB|| ≤ ||A||.||B||......A,BA_n

explicatii: matrice A:nxn poate fi considerata ca un vector cu n² coordonate

4.=axioma de compatibilitate a normei de matrice cu norma de vector din spatiul v

axioma5 se pune deoarece produsul a doua matrici de ordin n este o matrice de orin n

Norma unei matrici se defineste in felul urmator:

||A||= in fapt acesta este norma unui operator liniar, (A);Aa=operator liniar v

metoda pctului fix: x=.g(x); =g(x)

metoda: | x⁰ =dat

| x^(n-1)=g(xⁿ) n≤ 0 n=0,1,2,.......

subiectul 10Sisteme de ecuatii neliniare - Metoda punctului fix:

Convergenta. Convergenta de ordinul doi.

Convergenta

T2): ≤ λ <1;g=ct.,i,j=derivate partiale

I: |x-| ρ; ||g(x)-g(y)||< λ||x-y||

Iacobianul lui g

G_(x)=

Conditia coincide cu (o singura derivata)

Conditii de convergenta :1 g sa fie definit , constant pe II(

2. g tip (II) cu constanta tip <1 xyII ||g(x)-g(y)|| λ||x-y|| si 0≤ λ

3.x⁽⁰⁾ suficient de apropiat de

g:C C; CRⁿ+conditia 2 x₀C

teorena1: daca : 1. g e definit pe II : ||x-x⁽⁰⁾|| ≤ ρ

2.g e tip pe II cu λ≤1xyII ||g(x)-g(y)|| ≤ λ||x-y||, 0≤ λ <1

3. ||g(x⁽⁰⁾-x⁽⁰⁾|| ≤ (1- λ) ρ

atunci: a) it x⁽ⁿ⁾ II b) x⁽ⁿ⁾ II, =g( ) c) =unica in II

demo: este identica cu cea de la o singura variabila inlocuind in acelea mocelul cu norma (|.|

in teorema 2 se presupune ca exista radacin si intervalul II definit ca o vecinctate a lui

teprema2: daca: 1. exista  a.i. =g() 2.)g e definita pe II :||x-||_∞ ≤ ρ, e continua si are derivate partiale de ordin I continue pe II

3.) are loc ≤ λ <1

atunci: pt oricare x⁽⁰⁾ II : a) x⁽ⁿ⁾ II b) x⁽ⁿ⁾  c)  =unica in II

Subiectul.11. Sisteme de ecuatii neliniare-Metoda penctului fix

Procedura explicita de punct fix

La o necunoscuta (n=1): g(x)= g(x)=x-nn=ct.

Fie A(x)matrice n,nesingulara pe V(, atunci, definind :

g(x)=x-A(x) f(x),avem : x=g(x)f(x)=0

A=matrice constanta a-constante; g(x)=x-Af(x)

Matricial

Scalar g(x)=x- ;i=

-matricea ; =F(x)

=

G(x)=I - A F(x) ;vrem /A=?a.i. //G(x)//<1; G()=0

G() =I-A F()=0 A=

; n0 ; -dat

-daca sirul ,atunci: putem imbunatati aproximatia anterioara prin

una din iteratile urmatoare : se actualizeaza matricea A dupa un nr. de pasi luand locul

in locul iterata curenta(nr.de pasi

Ex:3 A= n=1

4 A=

;A-actualizat la nr a de pasi A=

Schema practica de iterare

; iterarea continua, oprindu-se la testele //ESP(se opreste procesul,daca e mai mic) nr. de iterati NLIM

-daca actualizam matricea A la fiecare pas obtinem o convergenta mai rapida Amatrice constanta (relatile anterioare nu mai sunt valabile)

,formula de

Metoda Newton , p=2

Subiectul.12.Sisteme de ecuatii neliniare

Metoda Newton

A(x)-nesingulara-(1)pp ca dp de ord I si contine pe

(2)pp ca F-nesingulara:det(F)

A(x)=pt p=2;G(=0;g(x)=x-A(x)f(x) A

Atunci se poate alege A(x)=

X⁽ⁿ⁺¹⁾=x⁽ⁿ⁾-

Schema practica de iterare det-nesingulara

(corectie)

Metoda Newton-modificata(cvasi-Newton)

F(x⁽ⁿ⁾) inlocuit A⁽ⁿ⁾≈ F(x⁽ⁿ⁾);formula de iteratie devine:

x⁽ⁿ⁺¹⁾=x⁽ⁿ⁾-[A⁽ⁿ⁾]^-1f(x⁽ⁿ⁾),n-scopul inlocuirii este de a micsora in calculatie numarul evaluarilor de functie

[F(x⁽ⁿ⁾]^-1≈(A⁽ⁿ⁾)^-1=B⁽ⁿ⁾

x⁽ⁿ⁺¹⁾=x⁽ⁿ⁾- B⁽ⁿ⁾f(x⁽ⁿ⁾)

Subiectul.13.Sisteme de ecuatii liniare

Consideratii generale;Eliminarea Gauss.

-rezolvarea unui system de ec. Liniare se poate dovedi dificila,datorita conditiilor de lucru:

(1)numar mici de operatii pt a gasi solutia(exclude calculul manual)

(2)propagarea erorilor intr-un sir lung de calculatii cu numere reprezentate printr-un nr finit de cifre(limiteaza utilizarea calculatorului)

-tipuri de probleme

(1)sisteme de ordin moderat,cu matrice densa(elementele matricei sunt majoritatea nenule)n1000 ecuatii-se rezolva cu metoda de eliminare Gauss(in memorie)

(2)sist de ordin mare,cu matrice rara(el.matricei sunt nule) n100000-nr de ec.f mare-se utilizeaza metode iterative:Jordan,Gauss-Sidel

(3)caz particular la (2)=in cazul in care memoria e insuficienta pt a contine matricea sistemului:-se genereaza si se proceseaza pe blocuri de elemente

-notatii: Ax=b

A=;X= ;b=

Eliminarea Gauss-consta in transformarea sistemelor date intr-un system cu matrice triunghiulara superioara prin procedeul de a face zerouri in coloana pe elemente inf.

=- =

Ax=b- Ux=g (Back substitution)

Exemplu: (2)- -1)+

matrice extinsa

X₃=1 ; X₂=-1 ; X₁=1

Subiectul 14 Sisteme de ecuatii liniare:

Factorizarea triunghiulara a unei matrici; Numar de operatii în eliminarea Gauss. Factorizarea triunghiulara a unei matrici;

l_ii=1......diagonala

l_ij=0 ......i<j

l_ij=m_ij......i>j

preopozitie : daca la fiecare pas pilotul a_kk^(k) sete =/=0 atunci L (matricea multiplicatorilor) si U (matricea superioara triunghiulara

avem ca A=L U [A]= [L\ x\ U]

demonatratie: (LU)_i,j=linia i_Lxcolj_U =....=a_ij⁽¹⁾=a_ii

consecinta: detA = U₁₁ U₂₂ ......U₂₂ detA=detL x detU

Numar de operatii în eliminarea Gauss

Operatii: inmultire / impartire

Numar de operatii

1.transformarea A U ......................

2. transformarea b S........................

3.reform sist Ux=S .............................

numar total de operatii =

NOP(nr operatii) ............p, n="mare"

Pt un nou "b" : | n²operatii

Pasii 2,3 |

Ax=b

Subiectul 15 Sisteme de ecuatii liniare:

Inversarea unei matrici, numar de operatii. Pasii rezolvarii unui sistem prin descompunerea LU.

Inversarea unei matrici

Ax=I X=A^-2 [A]=

x⁽¹⁾, x⁽²⁾ x⁽ⁿ⁾ e⁽¹⁾:e⁽²⁾...e⁽ⁿ⁾

A[x⁽¹⁾ : : x⁽²⁾|....::x⁽ⁿ⁾]=[e⁽¹⁾::e⁽²⁾::...::e⁽ⁿ⁾]

[Ax⁽¹⁾ : : Ax⁽²⁾|....::Ax⁽ⁿ⁾]=[e⁽¹⁾::e⁽²⁾::...::e⁽ⁿ⁾]

|A_x⁽¹⁾ = e⁽¹⁾

| A_x⁽²⁾ = e⁽²⁾ => x⁽¹⁾ , x⁽²⁾....x⁽ⁿ⁾

|.............. col in inv x=A^-1

| A_x⁽ⁿ⁾ = e⁽ⁿ⁾

(NOP)_inv 1/3n³+nxn² =4(n³/3) (NOP)_inv=4(NOP)_Gauss

Pasii rezolvarii unui sistem prin descompunerea LU.

NOP

1.A=L U [A]=[L\ x \U]

2. rezolvarea Ly=b [L\[y]=[b] => substitutie inapoi

3. rezolvare Ux=y \U][x]=[y] => substitutie inapoi

subiectul 16 Sisteme de ecuatii liniare:

Pivotare si scalare în eliminarea Gauss.

1.pivotarea elementul diagonal a_kk⁽¹⁾=pivot =/=0 practic a_kk^(k)=~0

m_ik= |a_kk^(k)|=mic!

Alegem sa permutam linia la car a_Ikeste cel mai mare in modul C_k=

I>k de exemplu prima linie pe care a_Ik=C_k. Pivotul dse cauta sub matricea formata din liniile si coloanele k pana al n.

Teoteric: pivotarea completa duce le resturi tot mai precise

Practic: nu efectueaza diferente intre cele doua pivotari (complecta si partiala) utilizata partiala cea complecta cere mai mult timp calculatorului.

La pivotarea complecta ordinea necunoscutelor se schimba si aceasta trebuie refacuta inainte de rezolvarea complecta

2.scalarea sa observat empiric ca ssolutita are o precizie mai buna atunci cand elementele matricii A nu sunt de ordine, de marime sunt aproximative de acelasi ordin de marime. Exista o explicatie teoretica satisfacatoare. Adunarea elementelor matricei A la ordine de marime asemenatoare

|1/ _i

scalare simultan cu pivotarea:

(pivotare urmata de scalare)

pivotare partiala: C_k=

Subiectul.17.Sistem de ecuatii liniare

Determinarea directa a factorilor LU

=[L\ x \U]

Pasi:1.A=LxU

2. Ly=b

3. Ux=y

Exemplu: n=3 =*

a =l_11xu₁₁ a₁₂=l₁₂xu₁₂ a₁₃=l₁₃xu₁₃

a =l₂₁xu₁₁ a₂₂=l₂₁xu₁₂₊l₂₂xu₂₂ a₂₃=l₂₁xu1₃+l₂₂xu₂₃

a =l₃₁xu₁₁ a₃₂=l₃₁xu₁₂+l₃₂xu₂₂ a₃₃=l₃₁xu₁₃+l₃₂xu₂₃+l₃₃xu₃₃

se alege l₁₁(arbitrar):

u₁₁= u₁₂= u₁₃=

l₂₂= u₂₂=. u₂₃=.

l₃₁= l₃₂ l₃₃(arbitrar): u₃₃ valoarea arbitrara0! L_ii(arb) u_ii,u_ii+1,u_i,n

l₁₁ u₁₁,u₁₂,u₁₃ ↓

↓ l₂₂(arbitrar) u₂₂,u₃₂  l_i+1,i

l₂₁ ↓ l_n

↓ l₃₂ l₃₃(arb) u₃₃

l₃₁

analog se pot alege u_ii arbitrar ;l_ii=arb.sau u_ii=arb.0

Doua metode:1)l_ii=1 Metoda DOOLITTLE ~ Eliminarea Gauss

2)u_ii=1 Metoda Crout

Formulele pt determinarea directa a factorilor L si U au avantajul(fata de formulele de la eliminarea Gauss)ca ele contin sume ce exprima produse scalare,ce pot fi calculate in dubla precizie(precizie mai buna)

Subiectul.18.Sisteme de ecuatii liniare

Metoda Cholesky

Este o varianta a descompunerii LU,se aplica la matrici simetrice si pozitiv definite

A-simetrica,A^T=A,a_ji=a_ij

A-pozitv definite x0 x^tAx>0 }se descompun independente

x^tAx=∑_i∑_j a_ijx_ix_j

Matrici simetrice si pozitiv definite

Propietati:1)elementele diagonalei a_ii­>0

x=e⁽ⁱ⁾=(i)(la pasul i);x=,x_k=,k=1,n

2)A a₂₂⁽²⁾>0 Â^(k)e simetric si pozitiv definite

Consecinta:la fiecare pas pivotia a_kk^(k)>0(0),nu e necesara pivotarea

3)valorile propii sunt reale si positive

daca A e simetrica valorile proprii sunt reale

daca A e pozitiv definite valorile proprii reale sunt pozitive(echivalenta)

daca A e simetrica sip oz.definita valori proprii reale si positive

Rezolvarea:Ax=b (A-simetric si poz.definta);A=L*U

-exista descompunerea A=L*L^T;U= L^T [A]=L* L^T;

matricea de baza:L: L*L^T

matricea de baza S:S^T*S

pasi:1)A=L*U 1)A= L*L^T -nr de operatii

2)Ly=b 2)Ly=b

3)U_x=y 3)L^T*x=y}

NOP: radacini patrate;pt.n"mare"NOP≈

Subiectul.19.Sisteme de ecuatii liniare

Analiza erorii.Nr de conditie al unei matrici.Proprietati

Stabilitatea solutiei(unui sistem)

Ax=b(sist dat);

Ã×x=b;

-solutia=x^~; x^~=x+ -variatia solutiei

se calc. in functie de A, b

Perturbatia in b.Numarul de conditie

Ax=b(1) notam

Ax^~=b^~(sist perturbat)

A() -r-perturbarea termenului liber b

A=r(2) -e-perturbarea soluitiei x

Vrem sa evaluam:

Daca k≈1:(caz favorabil,a aceasi perturbare)matricea e bine cond(stabile)

k>>1; matricea e rau cond(sol instabila)

b=Ax(1);x=A^-1b(1`) r=Ae(2);e=A<sup>-1</sup>r(2`)

(4) (6)

-inmultim rel(3)(6);(4)(5) nr de cond al matricei A,notat:cond(A)=

=reprezinta:e/x,r/b

Proprietatea normei de matrice

(A)=inf(matrice inf)

spectrul:

A-valoare proprie A^-1are val.1/_I

definim:cond(A)_*=

(cond(A)_* e cond(A) cel mai mic in raport cu toate normele)

Subiectul.20.Sisteme de ecuatii liniare

Matrici bine si rau conditionate

Definitie-matricea sistemului e bine condit(sol.stabila)

matricea sistemului e rau condit(sol.X e instabila)

(1)Exemplu8X₁+9X₂=b₁

7X₁+8X₂=b₂ ;A= detA=1;A^-1=

1)norma ∞(norma liniilor)

=17=8+9>8+7;

cond(A)=17x17=289

2)norma 1 (norma coloanelor)

cond(A)=17x17=289

3) norma 2(euclidiana)

cond(A)=258

4) cond(A)~254(margine inferioara)

p(

perturbarea solutiei

cond(A)~250o perturbare mica in termenul liber perturbare in solutie

b₁,b₂;X₁=0.1,X₂=0.1

b₁=0.8+0.9=1.7, b₂=1.5

fie:sistemul cu matricea A=,b reprez:X₁,X₂

r=-b=;X= =Ax+

(2)A=; A^-1=

cond(A)= 10⁷(foarte mare)problema rau conditionata;se inlatura prin scalare materiala(se inmulteste cu 10⁷):A

(3)Matricea Hilbert(rau conditionata)

H_n=;H_n^-1-se numeste analitic

(ordinal creste cu "n")

perturbatia A si b:Ax=b; AA+} XX+

bb+}