Che materia stai cercando?

Anteprima

ESTRATTO DOCUMENTO

Problema dei due punti. ≥0

Data una funzione g(t) in [0,1] , si consideri , per una assegnata f(t), l'equazione

differenziale ∈

u"(t) - g(t)u(t) = f(t) t [0,1]

con le condizioni agli estremi: u(0)= a, u(1)= b.

Si può dimostrare che tale problema ammette una ed una sola soluzione per ogni termine

noto f(t). Consideriamo ora una discretizzazione dell'intervallo [0,1] di passo h=1/N, con N

intero, t =ih i=0,1,... N

i

e indichiamo con u le approssimazioni di u(t ), e con g ed f i valori g(t ) e f(t )

i i i i i i

rispettivamente. Approssimando u"(t ) , per i=1,...N-1, con la differenza centrale

i

u - 2u + u

i-1 i i+1 si ottiene,cambiando segno all'equazione e tenendo conto che u =a ed

0

2

h

=b, il seguente sistema lineare:

u

N 2 2

g )u - u = -h f + a

(2 + h 1 1 2 1

....... 2 2

-u +(2 + h g )u - u = -h f

i-1 i i i+1 i

....... 2 2

-u +(2 + h g )u = -h f + b

N-2 N-1 N-1 N-1

la cui matrice : -1

2

2 + h g

1

-1 -1

2

2 + h g

2

. . . -1

A = -1 2

2 + h g

i

. . . -1

-1 2

2 + h g

N-2

-1 2

2 + h g

N-1

43

risulta simmetrica e tridiagonale.

Dimostriamo ora che la matrice A risulta anche definita positiva. A tale scopo osserviamo

che H H H

x Ax = x Tx + x Gx

dove : 2 -1

-1 2 -1

. . .

T= . . . 2 2 2

g ,...h g ...,h g )

, G=diag(h 1 i N-1

. . .

-1 2 -1

-1 2

Poichè la matrice G è evidentemente semidefinita positiva a seguito della condizione

g(t)≥ 0, A risulterà definita positiva se tale è T. Per il corollario 1.6 si ha, per ogni x≠0,

λ ≤ ≤ λ

H H H

x x x Tx x x.

1 n ≥

D'altra parte, per il teorema di Gerschgorin, tutti gli autovalori di T sono 0. Se dimostro

che T è non singolare, allora posso dire che tutti gli autovalori sono positivi e quindi, per la

< H

relazione precedente, anche 0 x Tx.

Non resta dunque che dimostrare la non singolarità di T , per ogni dimensione della

la matrice tridiagonale T di

matrice. A tale scopo si osserva immediatamente che, detta T k

dimensione k, si ha )=2det(T ) - det(T )

det (T

k+1 k k-1

dalla quale, per induzione, si ricava

) =k+1.

det(T

k

La matrice T è dunque non singolare e, di conseguenza, definita positiva. Ciò assicura,

come abbiamo osservato prima, che anche A è definita positiva.

44

Problema di Dirichelet. 2

Sia u(x,y) una funzione definita in un dominio D del piano R , il cui bordo sarà

Γ , che soddisfa l'equazione a derivate parziali

indicato con D

∂ ∂

2 2

u u ∈

+ = f(x,y) x,y D

∂ ∂

2 2

x y

con la condizione al contorno, Γ .

u(x,y)=0 x,y∈ D

Effettuiamo una reticolazione del dominio D con rette parallele agli assi coordinati, distanti

tra loro una quantità positiva h, ed enumeriamo con un indice progressivo i nodi P che

i

risultano interni al dominio.

Usando le differenze centrali per approssimare le derivate parziali seconde, si ottiene:

∂ 2 u(P

u(P ) )- 2u(P )+ u(P )

i i-1 i i+1

= 2

∂ 2 h

x

∂ 2 u(P

u(P ) )- 2u(P )+ u(P )

i i-ri i i+si

e = 2

∂ 2 h

y e P sono sovrastanti e sottostanti il punto P nel reticolo.

dove i punti P

i-ri i+si i

Per ogni punto interno del reticolo si avrà dunque

45

∂ ∂

2 2 u(P

u(P ) u(P ) )+u(P )- 4u(P )+ u(P )+u(P )

i i i-ri i-1 i i+1 i+si

+ = 2

∂ ∂

2 2 h

x y , prossimo al bordo, è tale che il nodo precedente, o

intendendo che se un punto P i

seguente o sovrastante o sottostante del reticolo esce dal domino, in tale nodo si assegna

il valore nullo.

In riferimento alla figura, il sistema lineare nelle incognite u(P ) i=1,...,12 ha una

i

matrice tridiagonale a blocchi della forma:

4 -1 -1

-1 4 -1 -1

-1 4 -1

4 -1

-1 -1 4 -1

A = -1 -1 4 -1 -1 (2.1)

-1 -1 4 -1

-1 4 -1 -1

-1 -1 4 -1

-1 4 4 -1

-1 -1 4

E' facile rendersi conto che la matrice risulta simmetrica. Inoltre, con ragionamenti

simili all'esempio precedente, si dimostra anche che è definita positiva. E' anche facile

capire che se l'equazione fosse stata di dimensione 3, cioè:

∂ ∂ ∂

2 2 2

u u u ∈

+ + = f(x,y,z) x,y,z D

∂ ∂ ∂

2 2 2

x y z

il sistema sarebbe risultato pentadiagonale a blocchi e la sua dimensione sarebbe

cresciuta considerevolmente. Se il dominio D fosse, per esempio, un cubo con lo spigolo

unitario, un reticolo con 10 punti interni su ogni coordinata darebbe luogo ad un sistema di

dimensione 1000. 46

1.M .

ETODI ITERATIVI

I metodi iterativi per la risoluzione dei sistemi lineari si fondano sulla trasformazione

dell'equazione Ax=b in un problema equivalente di punto fisso. Ciò si ottiene attraverso

uno spezzamento (splitting) della matrice A in

A = N - P , con N non singolare e P=N-A,

che dà luogo a

Nx = Px + b

-1 -1

x= N Px + N b

Il problema Ax=b è cosi trasformato nel problema di punto fisso

x = Mx + a (2.2)

-1 -1 -1

I

b ed M = N P = -N A. La matrice M è detta matrice di iterazione ed è

dove a=N

definita univocamente dallo splitting.

Il problema di punto fisso viene quindi affrontato con l'iterazione

k+1 k

x =Mx +a, (2.3)

o, più precisamente, con l'iterazione

k+1 k

Nx = Px + b 0

a partire da un vettore iniziale x assegnato. Affinchè questo approccio possa essere

vantaggioso occorre che il sistema

k

Ny = Px + b

sia risolvibile per y in maniera "diretta", cioè con un costo trascurabile rispetto al costo

richiesto per la risoluzione del problema originale Ax=b. k k

Sottraendo (2.2) da (2.3) si ottiene, per gli errori e := x - x,

k+1 k 2 k-1 k+1 0

= Me = M e =... = M e

e

Se la matrice M è convergente allora l'errore tende a zero, qualunque sia il vettore

0

iniziale x , mentre può accadere che l'errore tenda a zero senza che la matrice sia

47

k 0

infinitesima. Ciò accade quando M tende ad una matrice il cui nucleo includa e . Se

invece si vuole che l'errore tenda a zero per ogni vettore iniziale, allora M deve essere

convergente. Abbiamo dunque dimostrato il seguente teorema.

T 2.1. Condizione necessaria e sufficiente affinchè l'iterazione (2.3) converga per

EOREMA 0

ogni vettore iniziale x è che la matrice M sia infinitesima o, equivalentemente, che

ρ (M)<1.

Dunque nel proporre un metodo iterativo, lo splitting deve essere scelto con i

seguenti criteri:

1) N deve essere non singolare.

2) N deve essere invertibile a costo trascurabile.

3) La matrice di iterazione M che ne deriva deve essere convergente.

4) Il raggio spettrale di M deve essere più piccolo possibile.

Quest'ultima affermazione discende dalla seguente analisi asintotica dell'errore.

Analisi asintotica dell'errore. k

Nel valutare la bontà di un metodo iterativo attraverso l'analisi della successione e

0

degli errori , si deve osservare che questa dipende dal punto iniziale x col quale si

innesca l'iterazione e dalla particolare norma con la quale viene valutata l'ampiezza degli

errori. Una valutazione corretta della velocità di convergenza del metodo deve

prescindere da entrambi questi fattori. Partendo quindi dalla relazione ricorsiva sugli errori

n n-1 n 0

e = Me = M e

si ottiene, per una norma arbitraria,:

|| || || |||| ||

n n 0

e M e

e quindi, || ||

n

e || ||

≤ n

M

||

|| 0

e 48 || ||

n

e || ||

n

Dunque in n iterazioni il fattore di smorzamento dell'errore è maggiorato da M , e

||

|| 0

e

|| ||

n

e , che rappresenta, dopo n passi, il fattore medio di smorzamento

quindi la quantità ||

|| 0

e

ad ogni passo, è a sua volta maggiorato da

|| ||

n n

e n || ||

≤ n

M .

||

|| 0

e ρ

→ ∞ (M). Di

Il termine a destra della disuguaglianza ammette limite, per n , pari a

conseguenza il termine a sinistra, che in generale non ammette limite, possiede

certamente il massimo limite e per esso si avrà:

|| ||

n n

e ρ

max lim (M).

||

||

n→∞ 0

e 0 0

in modo tale che e sia autosoluzione di M associata

Osserviamo infine che scegliendo x

µ di modulo massimo, si ha

all'autovalore µ

n n

e =M e = e

n 0 0

Da ciò si ricava

|| || ρ || ||

=

n n 0

e (M) e

e quindi || ||

n n

e ρ .

= (M)

||

|| 0

e

Di conseguenza rispetto a tutti i possibili vettori iniziali ed a tutte le norme si ha:

|| ||

n n

( )

e ρ

=

maxe max lim (M)

||

||

0 n→∞ 0

e

Il termine a sinistra si chiama fattore asintotico di convergenza e rappresenta il

peggiore fattore medio di cui viene smorzato asintoticamente l'errore iniziale,

indipendentemente dal vettore iniziale e dalla norma con cui si misura l'errore.

Il fatto che il fattore asintotico di convergenza coincide col raggio spettrale della

matrice di iterazione del metodo, giustifica l'asserzione che un metodo iterativo è, in

49

generale, tanto più veloce quanto più piccolo è il raggio spettrale. Ciò non esclude che per

certi vettori iniziali un metodo risulti più veloce di un altro di raggio spettrale inferiore.

Per dare una stima a priori del numero di iterazioni necessarie per avere un errore al

di sotto di una assegnata tolleranza, è utile il concetto di ordine asintotico di

convergenza. Esso rappresenta il numero di iterazioni necessarie per smorzare

-1

asintoticamente l'errore di un fattore 10 e verrà indicato con R.

Sulla base dei risultati precedenti si può dire che asintoticamente, cioè dopo un

numero sufficientemente grande di iterazioni, sarà sufficiente che R soddisfi la

disuguaglianza:

ρ ρ ρ

≤10 <1,

R -1 e quindi , poiche R≥-1/log 10

Come prima, questa è una stima pessimistica inquanto il fattore asintotico di smorzamento

per l'iterazione che si sta calcolando potrebbe essere, in realtà, più piccolo. Si osservi che

ρ , il suo ordine asintotico di

se un altro metodo ha il raggio spettrale che è il quadrato di

convergenza è la metà. Si noti infine che disponendo di una maggiorazione del raggio

spettrale, purchè inferiore ad 1, si dispone di una maggiorazione di R.

Metodo di Jacobi (metodo delle sostituzioni simultanee).

Il metodo di Jacobi consiste nel decomporre la matrice A in

N=D:=diag(a ,....,a ) e P=N-A.

nn

11

Poichè N deve essere invertibile, si deve premoltiplicare A per una matrice di

permutazione in modo che la matrice permutata abbia sulla diagonale elementi tutti non

nulli. Si vede che ciò è sempre possibile a condizione che A stessa sia non singolare.

1 1

,....,

-1

, si ha:

Risulta N =diag( ) e per la matrice di iterazione M=(m )

ij

a a

nn

11

a

ij

m = - , per i≠j , ed m =0.

ij ii

a

ii

L'iterazione di Jacobi si scrive dunque:

a b

ij i

k+1 k

x = - x + i=1,...,n

i j

a a

ii ii

j≠i 50

Una matrice A si dice a predominanza diagonale stretta, se per ogni riga si ha:

∑ |a |<|a | (i=1,...,n) .

ij ii

j≠i |a |

ij

∑ |<1 per ogni i, allora si dimostra

Poichè la predominanza diagonale stretta implica |a

ii

j≠i

immediatamente il seguente teorema

Teorema 2.2. Se la matrice A è a predominanza diagonale stretta allora il metodo di

Jacobi è convergente. |a |

ij

|| || ∑

Dim: M < 1.

= max

∞ i |a |

ii

j≠i || ||

M <1,

Un'altra condizione sufficiente per la convergenza è data da 1

cioè da |a |

ij

max < 1.

j |a |

ii

i≠j

Si badi bene che la precedente relazione non significa la predominanza diagonale per

∑ |a |<|a | (j=1,...,n), ma una relazione più

colonne, che si esprime invece con ij jj

i≠j

complessa che può comunque essere utile in qualche caso. D'altra parte la predominanza

diagonale per colonne assicura anch'essa la convergenza del matodo di Jacobi.

Teorema 2.3. Se la matrice A è a predominanza diagonale stretta per colonne, il metodo

di Jacobi converge. - T la trasposta dell'inversa di B. La

Dim. Data la matrice B, indichiamo con B

predominanza diagonale per colonne di A implica la predominanza diagonale per

T

righe di A , la cui matrice di iterazione di Jacobi è

- -1

T T T

P =D P .

M'=D ρ -1 T

Per tale matrice si ha, in base al teorema precedente, (D P )<1 e quindi anche

ρ ρ ρ

-1 -1 -1 -1 -1

T T

((D P ) )= (PD )<1. Poichè PD è simile a D P anche (D P)<1.

51


PAGINE

20

PESO

190.30 KB

AUTORE

Teemo92

PUBBLICATO

+1 anno fa


DESCRIZIONE DISPENSA

In questa dispensa di Matematica a cura del professore Bellen si parla di sistemi lineari. In particolare vengono esaminati i seguenti argomenti:
- Problema dei due punti;
- Problema di Dirichelet;
- Metodi iterativi;
- Analisi asintotica dell'errore;
- Metodo di Jacobi (metodo delle sostituzioni simultanee);
- Metodo di Gauss-Seidel (metodo delle sostituzioni successive);
- Il metodo SOR (successive over-relaxation method);
- Metodi iterativi a blocchi;
- Criteri d'arresto.


DETTAGLI
Corso di laurea: Ingegneria informatica
SSD:
Università: Trieste - Units
A.A.: 2007-2008

I contenuti di questa pagina costituiscono rielaborazioni personali del Publisher Teemo92 di informazioni apprese con la frequenza delle lezioni di Calcolo numerico e studio autonomo di eventuali libri di riferimento in preparazione dell'esame finale o della tesi. Non devono intendersi come materiale ufficiale dell'università Trieste - Units o del prof Bellen Alfredo.

Acquista con carta o conto PayPal

Scarica il file tutte le volte che vuoi

Paga con un conto PayPal per usufruire della garanzia Soddisfatto o rimborsato

Recensioni
Ti è piaciuto questo appunto? Valutalo!

Altri appunti di Calcolo numerico

Dispensa di Matematica - Equazioni non lineari
Dispensa
Dispensa di Matematica - Approssimazione delle funzioni
Dispensa
Dispensa di Informatica - Spazi vettoriali normati
Dispensa