Riassunto calcolo numerico

SISTEMI LINEARI

A regolevo (inedicibile)

det A≠0

Metodo Eliminazione di Gauss

Fattorizzazione LU

det A≠0

A = LU

Ax = B

L Ux = B

Algoritmo sostitu. indietro (triang. sup)

ux = B

x_i = (b_i − Σ_k=i+1ⁿu_ikx_k) 1/u_ii

UX = B

X_m = b_m/u_mm

Algoritmo sostitu. avanti (triang. inferiore)

Lx = B

x_i = (b_i − Σ_k=i+1ⁿl_ikx_k) 1/l_ii

i = 2, 3... m

Matrice Tridiagonali → Algoritmo di Thomas

A

[ d₁ s₂ 0 ... ]

[ s₁ d₂ s₃ ... ]

[ 0 s₂ d₃ ... ]

[ 0 0 ... ]

[ 0 0 ... d_m-1 s_m ]

[ 0 0 ... s_m-1 d_m ]

A

[ μ₁ V₂ ]

[ μ₂ V₂ ]

[ μ₃ V_m V_m-1 V_m ]

L

[ 0 0 ... ]

[ 0 0 ... ]

[ 0 0 ... d_m ]

U

μ_i = d_i−d_iV_i-1 i=2,3,...m

SISTEMI LINEARI

A regola (irredicibile)

AX = B

det A ≠ 0

Metodo Eliminazione di Gauss

Fattorizzazione LU

det A ≠ 0

A = LU

Algoritmo sostitu. indietro (triang. sup)

• UX = B
• x_i = (b_i - Σ u_ikx_k) 1 / u_ii

Algoritmo sostitu. avanti (triang. inferiore)

• LX = B
• x_i = (b_i - Σ l_iky_k) 1 / l_ii

Matrice Tridiagonale → Algoritmo di Thomas

• d₁ s₁ r₁ 0 ...
• s₂ d₂ s₂ 0 ...

Triang. Superiore

L Triang. Inferiore → U

Fattorizzazione LU

d_i' = d_i

V_i = s_i / d_i i = 2, 3, ... m

L_i = a_i / d_i i = 2, 3, ... m

d_m' = d_m - l_mv_m-1

Esempio

y_i - b

• d₁ y₁ - b₁
• d₂ y₂ - b₂
• d₃ y₃ - b₃

codiag. sup

diag. dm

codiag. inf

METODI ITERATIVI

A X = B

X

X = C X + Q

METODO DI JACOBI

{

X^(k+1) = C J X^(k) + Q J

X D C₃ Q₃ k≥0

C₃ = -D^-1(L+U) =

[

a₁₁ ... a_1j ... a_1m

a₂₁ a₂₂ a₂₃ ... a_2m

a_m1...

a_m2 ... a_mm

] [

o

a₁₂ ... a₁₃ ... a_1m

a₁₂ ... a_1j ... a_mm

Q₃ = D^-1b =

[

b₁

b₂

...

b_m

]

a₂₂

a₁₁

a₂₁

a_m1 a_m2 ...

[‡?>

X₁^(k+1)

a_m2 =

X_m^(k+1)

X₂^(k+1)

X₃^(k+1)

[

X₁^(k+1)

X₂^(k+1)

X₃^(k+1)

X_m^(k+1)

]

= [ ] C_J [ ] + [ ] Q_J

= [ ] + [ ]

si_jX_j^(k)

x_i^(k+1)

=

a_ii

1 - a_ijX_j^(k) + bi

(o)

[

a_ij x_j^(k)

b_i ]

∴

#Bisogna riempure K vet

ai: &value; rigale i ciclo

• Dominio
• Dominate
• C S | C N conv Y
• (nome )
• S(C₃) ≥

S(C) = lim _k→∞

||x^k||

Max degtii

Autovalorii

S(C₃) = max (|YI - det(C₃ - λ I

])o

Convergenza

C S {

|| C_J||∞||C S|| ≤ 1

C N.S. s(C₃) < 1

CM lim _k→∞ X^(k)= x¯

Criterio Arresto

(Stima A Piazza)

= num K dt tensorii

b_P K ≥ log₃

||x^(k+1)-X¯(k)|| < ε E : tollarenza

Velocit&act;à conorption

Metodo Gauss-Seidel

^(k+1)X = -C_GSX^(k) + Q_GS

C_GS = -(D+L)^-1UQ_GS = (D+L)^-1B

X_i^(k+1) = (1/a_ii)[ -Σ_j=1^i-1 a_ijx_j^(k+1) - Σ_j=i+1ⁿ a_ij x_j^(k) + b_i ]

Convergenza

^C.S. ||C_GS|| < 1

Cond. num: X_sup ~ X_∧

C.S. - Se diag. dominante e def. positiva => metodo converge

Criterio arresto (stima a priori)

||X^(k+1) - X^(k)|| < E

Tolleranza prefissata

Stima a priori: k numero k di iterazioni

Velocità convergenza

Se A converge (Ammetti A ∈ R^mxn)

||E^(k+1)|| < ||C^(k+1)|| ≈ g*(C)V =_log10 g(C)

Condizionamento

(modulo)!!!

K(A) = ||A|| ||A^-1||

Calcoli A^-1 = (…) …

||A|| = max (…) { … }in base a testa

||A^-1|| = max (…)

K(A) = ||A|| ||A_∞^-1

- condizion. migliore quando K (s.condiz.) ha valore minimo.

Matrici definite positive

A ∈ ℝ^n×n è simmetrica e det. positiva se vale Sylvester⇒ una matrice def. positiva ha autovalori reali ha autovalori >0

⇒ è regolare, detA _m ≠ 0

⇒ se A = H^T H ⇒ A è def. positiva

⇒ se A è simmetrica, è definita positiva se diagonalmente dominante

Criterio Sylvester

A ∈ ℝ^n×n simmetrica e definita positiva se solo se tutte i sottomaatrici ∁ di rango >0 sono >0

A = a₁₁a₁₂a₁n a₂₁a₂₂a₂n a_n1a_n2a_nn

Se A def. positiva ⇒ (se A simmetrica, C_∁ → anche A^-1)

||A||₂ = √β(ATA) = √β(A^-2) = λ max di A, A = λ

||A^-1||₂ = √β(A^-1) = √β(A^-2) = λ min aut. A^-1 = ¹/_λ

K₂(A) = λ_max / λ_min

||A||₁ – colonne

||A||_∞ – max (righe)

||A||₂ = √β(A^TA)

ρ(C) = max (λ_i: det(C-λI)=0)0 ≤ i ≤ n

EQUAZIONI NON LINEARI

SEPARAZIONE DELLE RADICI

Es: si devono 1) scrivi sistema

• ...
• ...

2) individua intersezioni delle curve

ORDINE di CONVERGENZA

BISEZIONE

convergenza

Può modo

• Se                                           stop
• ...

CRITERIO ARRESTO POSTERIORE

METODO DELLE TANGENTI

ALGORITMO

• Metodo delle Tangenti
• Estremo Fourier --> due volte con messo

METODO DELLE SECANTI

VANTAGGI

• quando è...
• ...

SVANTAGGI

• servono 2 approssimazioni iniziali ₀, ₁
• ...

Convergenza

Se

• Se
• ...

ORDINE CONVERGENZA

^{|x_k+1 - ξ|}_{|xk - ξ|^p}

Secanti → p = ^{1 + √5}⁄₂ ≈ 1,62 conv. superlineare

Tangenti → p ≥ 2 conv. (almeno quadratica)

Bisezione → p = 1 lineare

EFFICIENZA COMPUTAZIONALE E = p^1/k r = num. valuti. funzionali

Bisezione: E = 1        r = 1Secanti: E = (^1+√5⁄₂)^1/(√2) ≈ 1,62     _{r = 1}

Tangenti: E = 2^1/2 ≈ 1,41      r = 2

fx xξ g(x) 2 valutaz. g'(x) funzioni

METODO PUNTO UNITO (esumsolva. dell'equaz. com lineare)

g'(x) =_{(φ(x) - x)^θ}

x ≥ φ(x)Se ξ | viriciude che | f è punto unito de φ

g(ξ) = 0 se φ(ξ) = ξ

METODO APPROSSIMAZIONE SUCCESSIVE

x₀ datox_k+1 = φ(x_k)       k ≥ 1, 2, ...

Convergeva:

Lim x_k = ξ

Arresto:

Lim |x_k| = 0 |x_k - x_k-1| ≤ εk→∞

CS: comv._φ0gx^1/ω

Th: f x ] ≈ φ(g(x),

s ≥ φ(s) ∈ I

d x_k+1 = φ(x_k) converve

b)_{xk>0, 3gx}

METODO APPROSSIMAZIONE SUCCESSIVE IN Rⁿ (Vettori)