Riassunto calcolo numerico

Sistemi lineari

Regolevo (inedicibile) det A≠0

Metodo di 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

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

XX = 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] [oa₁₂ ... 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_ii1 - a_ijX_j^(k) + bi(o)[a_ij x_j^(k)b_i ]

∴#Bisogna riempure K vetai: &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&rightarrow;∞} X^(k)= x¯

Criterio arresto (stima a Piazza)

= num K dt tensoriib_P

K ≥ log₃||x^(k+1)-X¯(k)|| < ε

E : tolleranza

Velocità conorption

Metodo Gauss-Seidel

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

C_GS = -(D+L)^-1U

Q_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 = 1

Secanti: 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₀ dato

x_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) ∈ Id

x_k+1 = φ(x_k) converve

b)_{xk>0, 3gx}

Metodo approssimazione successive in Rⁿ (Vettori)