Metodi numerici e modelli matematici - 139 di 139

ESEMPIO

m=3

x₁^(k) = ^{b₁ - a₁₂x₂(k-1) - a₁₃x₃(k-1)}/_a11

x₂^(k) = ^{b₂ - a₂₁x₁(k) - a₂₃x₃(k-1)}/_a22

x₃^(k) = ^{b₃ - a₃₁x₁(k) - a₃₂x₂(k)}/_a33

Se A è a predominanza diagonale per righe o per colonne allora Gauss-Siedel converge (più velocemente rispetto a Jacobi)

4x₁ + x₂ = 6

3x₁ + 2x₂ = 7

x = ⁽¹⁾/₍₂₎ A = ^{(4 1)}/_{(3 2)} b = ⁽⁶⁾/₍₇₎

METODI DI RILASSAMENTO

PER LA RISOLUZIONE DI SISTEMI LINEARI Ax = b

A = N - N

M = D - P

M^-1N = (D - P)^-1N

GAUSS-SEIDEL FA PARTE DELLA CLASSE DEI METODI DI RILASSAMENTO OVVERO TUTTI QUEI METODI IN CUI:

• x^(k) = x^(k-1) + ω v_k
• ω = PARAMETRO DI RILASSAMENTO
• v_k = x^(k) - x^(k-1)

x^(k) = x^(k-1) + ω(x^(c) - x^(k-1))

x^(k) = x^(k-1) + ω [(D^Px)^(k) + (D^N)x^(k-1) + (D^-1b) - x^(k-1)]

D_x^(c) = D_x^(k-1) + ωP x^(c) + ωN x^(k-1) + ωb - ωD x^(k-1)

(D - ωP)x^(c) = [(1 - ω)D + ωN] x^(k-1) + ωb

x^(k) = (D - ωP)^-1 [(1 + ω)D + ωN] x^(k-1) + (D - ωP)^-1ωb

PER ω = 1 ABBIAMO PROPRIO IL METODO DI GAUSS-SEIDEL

AL VARIARE DI ω SI GENERANO I VARI METODI DI RILASSAMENTO

Localizzazione degli autovalori:

1° Teorema di Gerschgorin

λ ∈ ∪_i=1^mK_i, i=1,...,m

K_i = {z ∈ C | |z - a_ii| ≤ ∑_j≠i^m|a_ij|} i=1,...,m

Questo teorema si può applicare anche sulla trasposta di A (che ha gli stessi autovalori) quindi:

λ ∈ (∪_i=1^mK_i) ∩ (∪_i=1^mH_i)

Esempio

A = ( 15 -2 21 10 -3-2 1 0 )

A^T = ( 15 1 -2-2 10 12 -3 0 )

• K₁ = {z ∈ C | |z - 15| ≤ 4}
• K₂ = {z ∈ C | |z - 10| ≤ 4}
• K₃ = {z ∈ C | |z| ≤ 3}
• H₂ = {z ∈ C | |z - 15| ≤ 3}
• H₂ = {z ∈ C | |z - 10| ≤ 3}
• H₃ = {z ∈ C | |z| ≤ 5}

Dunque: λ ∈ K₃ ∪ H₂ ∪ H₁

Le φ_i sono la base dello spazio P_m

{φ₀(x) = 1 φ₁(x) = x φ₂(x) = x² ... φ_m(x) = x^m}

Infatti la matrice del sistema è la matrice di Gauss

| 1 x₀ x₀² ... x₀^m |

| 1 x₁ x₁² ... x₁^m |

• ...

| 1 x_m x_m² ... x_m^m |

(fortunatamente malcondizionata)

Considerando che φ(x)∈P_m(x) ⇒ g_m(x)∈P_m(x) ⇒ g∼_m W_m(x)−P_m(y)

Quindi per m+1 punti, discontinui

∃! P_m(x) P_m(x_i) = f(x_i) ∀i ∈ N | ∉ 0 ≤ i ≤ m

Considerando la difficile risoluzione del sistema

La Grange pensò di cambiare base per

facilitare la risoluzione.

Usò come base i polinomi fondamentali di Lagrange

{l₀(x), l₁(x), l₂(x), ..., l_m(x)}

Mha polinomi l_ik(x) =

Π_j≠k (x-x_j)/Π_j≠k (x_k-x_j)

k=0,m ⇒

l_k(x) = | 0 per j ≠ k

| 1 per j = k

⇒ d_j = f(x_j) ⇒

P_n(x) = (∑^m_j=0 l_j(x) f(x_j)

Polinomio interpolante di Lagrange

Polinomi Interpolanti Osculatori

I polinomi interpolanti sono osculatori quando tra le condizioni interpolanti ci sono condizioni sulle derivate della funzione.

_P^(k)(xi) = f^(k)(x_i)

Polinomio Osculatore di Hermite

Quando oltre ad avere tutte le informazioni sulla funzione le abbiamo anche sulla sua derivata prima:

{ x_i, f(x_i), f'^(k)(x_i) }

Per P_2m+1(x)

{

P(x_i) = f(x_i)

P'(x_i) = f'(x_i)

i = 0, ..., m

} => 2m + 2 condizioni

P_2m+1(x) = ^m∑_i=0 U_i(x) f(x_i) + V_i(x) f'(x_i)

dove:

{

U_i(x) = [1 - 2(x - x_i) l'_i(x)] l_i²(x)

V_i(x) = (x - x_i) l_i²(x)

}

x = x₀ + th ∀ x ∈ [x₀, x_m], t ∈ ℝ⁺

=> x - x₀ = th

x - x_n, x₀ + th - x₀ - h = h(t-1)

x_n, h(t-z)

x - x_m-1 = h(t-m-1)

P_m(x₀ + th) = Δ⁰f(x₀) + (t)₁Δ¹f(x₀) + (t)(t-1)Δ²f(x₀) + ...

... + (t)(t-1)...(t-m-1)Δ^mf(x₀)

= ∑^m_k=0 (t ^k) Δ^kf(x₀) = ∏^m_k-i(t-q) K! Δ^kf(x₀)

(t)_x = (t-1)...(t-k+1)/k!

ESEMPIO

P_h(x₀ + th) = f(x₀) + tΔ¹f(x₀) + t(t-1)Δ²f(x₀)

= f(x₀) + t{Δ¹f(x₀) + (t-1)/2[Δ²f(x₀) + (t-2)/3(Δ³f(x₀) + (t-3)/4(Δ⁴f(x₀))] }

d₄ = Δ³f(x₀)/4

d₃ = d_n(t+3)H Δ³f(x₀)/3

d₂ = d₃(t-2) + Δ²f(x₀)/2

d₁ = d₂(t-1) + Δ¹f(x₀)

P_h = d₁t + f(x₀)

Θ(h_n)

74

CONSIDERANDO LE DUE CONDIZIONI CHE SI POSSONO AGGIUNGERE SI AVRANNO DIVERSI TIPI DI SPLINE:

PLINE NATURALE

S''(x₀) = 0₀

S''(x_r) = 0

SPLINE PERIODICA

S'(x₀) = S'(x_r)

S''(x₀) = S''(x_r)

SPLINE COMPLETA (VINCOLATA)

S'(x₀) = f'(x₀)

S'(x_r) = f'(x_r)

SARÀ QUINDI POSSIBILE TROVARE I COEFFICIENTI RISOLVENDO IL SISTEMA DI ORDINE 4r.

POSSIAMO RIMANIPOLARE I DATI PER RIDURRE TALE ORDINE

SI CONSIDERI CHE:

S_j(x) ∈ ℙ₃ , S_j'(x) ∈ ℙ₂ , S_j''(x) ∈ ℙ₁

S_d''(x) = ^{x - x_j+1}/_{xj - xj+1} S_j'(x_j) + ^{x - x_j}/_{xj+1 - xj} S_j'(x_j+1)

S_d''(x) = ^{x_j+1 - x}/_{xj+1 - xj} S_j'(x_j) + ^{x - x_j}/_{xj+1 - xj} S_j'(x_j+1)