Documente online.
Username / Parola inexistente
  Zona de administrare documente. Fisierele tale  
Am uitat parola x Creaza cont nou
  Home Exploreaza













Rezolvari probleme

Matematica



loading...











ALTE DOCUMENTE

Var 99 S I 1,4,5,6
LUCRARE SCRISA LA CLASA A VIII-A Mate
Blaise Pascal
Test inițial clasa a VII-a
PROBLEME CU SIRURI DE NUMERE
Adunarea si scaderea numerelor naturale
Reciproca teoremei lui Stolz-Cessaro
FORMULE TRIGONOMETRICE
restul de rang
Test de evaluare finala


Subiectul 1 Metoda punctului fix

Evaluarea erorii

Vrem : test | a - xn | < EPS

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

Metoda punctului fix :

| a - xn | = |(a- xn+1)+( | xn+1 - xn)| < |a- xn+1|+|xn+1-xn|<l|a-xx| + |xn+1 - xx|

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

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

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

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

    | xn+1 - xn| <= XTOL

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

g`*

Subiectul 2 Metoda punctului fix:

Procesul stationar.

Xn+1 = g(xn)

g

 
| x1=g(x0), x1 =/= x0

|x2=g(x1)

iteratia se zice ca este un proces

stationar daca x2 = x0 si x1 =/= x0

g(g(x0) = x0 g(g(x) = x (1)

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

-satisface (1) = g()

g'()g'() = 1 [g'()]2 =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'()=1 g(x) ≈ + x-=x nu satisface pt ca x1=x0

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

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


obs procesul stationar este x2 =x0

x0 xn x1 xn+1 x2 xn+2

procesul stationar: xn+2 = xn

xn 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

x0

x1

x2

x 3 .

x4 = x0

x(x+4) =x(n)

exemplu: g(x)= = 0.7877106

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()=0

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

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

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π - 3x2 = 0

g(x)=x-0.01(ex-3x2)

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 x0

interpretarea geometrica a metodei coardei

xn+1 = xn-mf(xn) x1 = x0 - mf(x0)

Y=f(x)

 
obs: m variabil

xn+1 = xn-mf(xn)

la pas "n" = moptim = (xn)

xn+1 = xn - f(xn)

 

 

 

 

 

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 xn+1 = g(xn) n ≥ 0

Ipoteza: sirul cinverge liniar: daca g'

general |C| => constanta erorii asimptotice

n>N1 rap ≈ C

ip generala -egalkitatea este aproxim(≈)

relatia (1) se rezolva in raport cu

≈ an,n+2

Extrapolarea Aitken ca metoda de punct fix

an,n+2 = G(x) = xn -

G(x) = x- xn+1 = G(xn) , x0 = det

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

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

PG -odin de convergenta al iteratiei xn+1 = G(xn)

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

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

b) daca p = 1 in = radacina simpla => pG=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() =/=0

Conditie echivalenta f() = f'()=...=f(x+1)() =/=0


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: xn+1 =g(xn) 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. Xn+1 = xn -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 -xn+1 = g()-g(xn) = g'(ξn)( -xn)

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)=a0+a1x+......ak(xk-1)x+.....+an(xn-1)x

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

b)forma imbricata( schema Horner)

p(x)=a0+x(a1+x(a2+......+x(an-1+xan)).....)

exemple: p(x)=a0+a1x+a2x2+a3x3 = a0+x(a1+a2x+a3x2) = a0+x(a1+x(a2+xa3)

nr de operatii: n+; n x

teoretic forma b) est emai precisa decea forma a)

p(x)=a0+x(a1+x(a2+......+x(an-1+xan)).....) (*)

bn=an

bk = ak+xbk+1 ; k=n-1, n-2, ...1,0(**)

bn=an

bn-1=an-1 + xbn

.........

b2=a2+xb3

b1 = a1+xb2

b0 = a0+xb1 .

b0 = 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 ξ

|bn = an

|bk = ak + ξbk+1; k= (1) b0 = p0(ξ)

introducem: 2(x, ξ) = b1 + b2x+......+bnxn-1

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

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

reducerea gradului:

Line Callout 2: Grad=n-1Line Callout 2: Grad=nipoteza: ξ = 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 =ξ xn+1=xn -

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)

ξ=xn | Cn=bn

| Ck=bk+ ξ Ck+1 ; k=n-1,...,1 (2)

C1=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) avemComplex 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 fi=f(xi)

-se exclude pctul cel mai indepartat

de x3 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.

Zi+1=zi - unde fctia H(zi) =(n-1)[(n-1)p'2(zi)-np(zi)p''(zi)

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

-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:

| f1(x1,x2,...xn)=0

|......

|fn(x1,x2,...xn)=0

fi:I R; I Rn (x1,x2,...xn) I , f1(x1,x2,...xn)

; f(x)=

f(x)=0 f()=0

x=g(x).....(2') g(x)= f:IRn; g:I Rn

| x1=g1(x1.....xn)

| xn=gn(x1,....,xn) (2)

 =g()

norme:

norma unui vector: v...spatiu vectorial de dimensiune finita "n" xv; x=x1e1+.......+xnen

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

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

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

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

3.      ||x+y|| ||x||+||y||

proprietati:

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

N:vRx fiind date doua norme N1 si N2 c,c'>0 C N1(x) ≤ N2(x) <C' N1(x)

2.N(x) e fctie continua de x

observatie: concret N(x) =fctie continua de (x1,x2,...xn)

norma unei matrici

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

Def2: ||.||:AnR+, 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...AAn ;xv

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

explicatii: matrice A:nxn poate fi considerata ca un vector cu n2 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: | x0 =dat

| x(n-1)=g(xn) 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(0) suficient de apropiat de

g:CC; CRn+conditia 2 x0C

teorena1: daca : 1. g e definit pe II : ||x-x(0)|| ≤ ρ

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

3. ||g(x(0)-x(0)|| ≤ (1- λ) ρ

atunci: a) it x(n) II b) x(n) 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(0) II : a) x(n) II b) x(n) 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,2,3

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(n+1)=x(n)-

Schema practica de iterare det-nesingulara

(corectie)

Metoda Newton-modificata(cvasi-Newton)

F(x(n))inlocuit A(n)≈ F(x(n));formula de iteratie devine:

x(n+1)=x(n)-[A(n)]-1f(x(n)),n-scopul inlocuirii este de a micsora in calculatie numarul evaluarilor de functie

[F(x(n)]-1≈(A(n))-1=B(n)

x(n+1)=x(n)- B(n)f(x(n))

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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(1/2)-

X3=1 ; X2=-1 ; X1=1

Subiectul 14 Sisteme de ecuatii liniare:

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

lii=1......diagonala

lij=0 ......i<j

lij=mij......i>j

preopozitie : daca la fiecare pas pilotul akk(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 iLxcoljU =....=aij(1)=aii

consecinta: detA = U11 U22 ......U22 detA=detL x detU

Numar de operatii n eliminarea Gauss

Operatii: inmultire / impartire

Numar de operatii

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

2. transformarea bS........................

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

numar total de operatii =

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

Pt un nou "b" : | n2operatii

Pasii 2,3 |

Proces

Nr operatii

Exemplu n=10

Eliminarea Gauss

~

340

Inversarea unei matrici nxn

~

1330

Regula Kramer

(n+1)!

39916800

Inmultirea a doua matrici

n3

1000

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(1), x(2) x(n) e(1):e(2)...e(n)

A[x(1) : : x(2)|....::x(n)]=[e(1)::e(2)::...::e(n)]

[Ax(1) : : Ax(2)|....::Ax(n)]=[e(1)::e(2)::...::e(n)]

|Ax(1) = e(1)

| Ax(2) = e(2) => x(1) , x(2)....x(n)

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

| Ax(n) = e(n)

(NOP)inv1/3n3+nxn2 =4(n3/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 akk(1)=pivot =/=0 practic akk(k)=~0

mik= |akk(k)|=mic!

Alegem sa permutam linia la car aIkeste cel mai mare in modul Ck=

I>k de exemplu prima linie pe care aIk=Ck. 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: Ck=

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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 =*

a11=l11xu11 a12=l12xu12 a13=l13xu13

a21=l21xu11 a22=l21xu12+l22xu22 a23=l21xu13+l22xu23

a31=l31xu11 a32=l31xu12+l32xu22 a33=l31xu13+l32xu23+l33xu33

se alege l11(arbitrar):

u11= u12= u13=

l22= u22=. u23=.

l31= l32 l33(arbitrar):u33 valoarea arbitrara0! Lii(arb)0uii,uii+1,ui,n

l11u11,u12,u13

l22(arbitrar)u22,u32 li+1,i

l21 ln,1

l32 l33(arb)u33

l31

analog se pot alege uii arbitrar ;lii=arb.sau uii=arb.0

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

2)uii=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,AT=A,aji=aij

A-pozitv definite x0 xtAx>0 }se descompun independente

xtAx=∑ij aijxixj

Matrici simetrice si pozitiv definite

Propietati:1)elementele diagonalei aii>0

x=e(i)=(i)(la pasul i);x=,xk=,k=1,n

2)A(2)=a22(2)>0(k)e simetric si pozitiv definite

Consecinta:la fiecare pas pivotia akk(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 definitevalorile proprii reale sunt pozitive(echivalenta)

daca A e simetrica sip oz.definitavalori proprii reale si positive

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

-exista descompunerea A=L*LT;U= LT [A]=L* LT;

matricea de baza:L: L*LT

matricea de baza S:ST*S

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

2)Ly=b 2)Ly=b

3)Ux=y 3)LT*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-1r(2`)

(3) (5)

(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)Exemplu8X1+9X2=b1

7X1+8X2=b2 ;A= detA=1;A-1=

1)norma ∞(norma liniilor)

=17=8+9>8+7; =17

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()==(8- )2-63=0;( -8)2=63; 1,2=8

===127+254

perturbarea solutiei

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

b1,b2;X1=0.1,X2=0.1

b1=0.8+0.9=1.7, b2=1.5

fie:sistemul cu matricea A=,b==reprez:X1,X2

r=-b=;X=;=Ax+=

(2)A=; A-1=

=1 , =107

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

(3)Matricea Hilbert(rau conditionata)

Hn=;Hn-1-se numeste analitic

Nr

Cond(Hn)1

3

7.48 E2

4

2.8 E4

5

9.44 E5

6

2.91 E7

7

9.85 E8

(ordinal creste cu "n")

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

bb+}


Document Info


Accesari: 2786
Apreciat:

Comenteaza documentul:

Nu esti inregistrat
Trebuie sa fii utilizator inregistrat pentru a putea comenta


Creaza cont nou

A fost util?

Daca documentul a fost util si crezi ca merita
sa adaugi un link catre el la tine in site

Copiaza codul
in pagina web a site-ului tau.

 


Copyright Contact (SCRIGROUP Int. 2014 )