• Non ci sono risultati.

Error Norm

N/A
N/A
Protected

Academic year: 2022

Condividi "Error Norm"

Copied!
36
0
0

Testo completo

(1)

••

Applicazioni di metodi di estrapolazione vettoriale a problemi lineari e non lineari

Maria Rosaria Russo, Roberto Bertelle Universit`a degli Studi di Padova

Dipartimento di Matematica Pura ed Applicata

(2)

Outline

••

◮ Motivazioni

◮ Teoria e metodi

◮ Applicazioni a sistemi lineari

◮ Applicazioni a problemi non lineari

Risultati

◮ Conclusioni

(3)

Motivazioni

••

◮ Diversi metodi numerici generano successioni di vettori convergenti alla soluzione di un dato problema;

(4)

Motivazioni

••

◮ Diversi metodi numerici generano successioni di vettori convergenti alla soluzione di un dato problema;

◮ risoluzione di sistemi di grandi dimensioni provenienti dalla discretizzazione di EDP.

(5)

Motivazioni

••

◮ Diversi metodi numerici generano successioni di vettori convergenti alla soluzione di un dato problema;

◮ risoluzione di sistemi di grandi dimensioni provenienti dalla discretizzazione di EDP.

◮ Spesso il processo di convergenza è lento.

(6)

Motivazioni

••

◮ Diversi metodi numerici generano successioni di vettori convergenti alla soluzione di un dato problema;

◮ risoluzione di sistemi di grandi dimensioni provenienti dalla discretizzazione di EDP.

◮ Spesso il processo di convergenza è lento.

◮ In tutti i casi in cui è rilevante il tempo di calcolo si può ricorrere a tecniche di accelerazione della convergenza;

(7)

Motivazioni

••

◮ Diversi metodi numerici generano successioni di vettori convergenti alla soluzione di un dato problema;

◮ risoluzione di sistemi di grandi dimensioni provenienti dalla discretizzazione di EDP.

◮ Spesso il processo di convergenza è lento.

◮ In tutti i casi in cui è rilevante il tempo di calcolo si può ricorrere a tecniche di accelerazione della convergenza;

◮ modellistica tridimensionale (dispositivi elettronici, elaborazione di immagini, ecc...);

(8)

Motivazioni

••

◮ Diversi metodi numerici generano successioni di vettori convergenti alla soluzione di un dato problema;

◮ risoluzione di sistemi di grandi dimensioni provenienti dalla discretizzazione di EDP.

◮ Spesso il processo di convergenza è lento.

◮ In tutti i casi in cui è rilevante il tempo di calcolo si può ricorrere a tecniche di accelerazione della convergenza;

◮ modellistica tridimensionale (dispositivi elettronici, elaborazione di immagini, ecc...);

◮ calcolo del vettore PageRank di Google.

(9)

Teoria generale

••

Si considerano metodi di accelerazione della convergenza basati sull’idea della estrapolazione vettoriale

(10)

Teoria generale

••

Si considerano metodi di accelerazione della convergenza basati sull’idea della estrapolazione vettoriale

Data una successione vettoriale convergente xn, con

n→∞lim xn = s

(11)

Teoria generale

••

Si considerano metodi di accelerazione della convergenza basati sull’idea della estrapolazione vettoriale

Data una successione vettoriale convergente xn, con

n→∞lim xn = s

un metodo di accelerazione consiste nel costruire una trasformazione T che produce una nuova successione yn la

quale converge più velocemente al medesimo limite:

n→∞lim kxn − sk/kyn − sk = 0

(12)

••

Le tecniche di accelerazione prese in analisi in questo lavoro appartengono a due categorie:

◮ metodi basati su estrapolazione polinomiale;

◮ metodi di tipo ε-algorithms;

si prendono in considerazione applicazioni di tali tecniche per risolvere

sistemi lineari

◮ sistemi di EDP non lineari

a partire da successioni ottenute con metodi iterativi.

K. Jbilou, H. Sadok, ”Some results about vector extrapolation methods and related fixed- point iterations”, Journal of Computational and Applied Mathematics - 1991

W.H.A. Schilders, P.A. Gough, K. Whight, ”Extrapolation techniques for improved conver- gence in semiconductor device simulation”, NASECODE VIII - 1992

(13)

Metodi polinomiali

••

Sia

{x

n

}, n = 0, 1, 2, . . .

successione di vettori in

R

N con limite

s

. I metodi polinomiali forniscono una approssimazione di

s

come combinazione lineare dei termini della successione.

(14)

Metodi polinomiali

••

Sia

{x

n

}, n = 0, 1, 2, . . .

successione di vettori in

R

N con limite

s

. I metodi polinomiali forniscono una approssimazione di

s

come combinazione lineare dei termini della successione.

Fissato un numero opportuno

k

di elementi della successione, con

k < N

, definiti:

ui = ∆xi = xi+1 − xi, wi = ∆ui = ∆2xi, i = 0, 1, 2, . . . ,

si risolve il sistema lineare dove Λζ = α Λ matrice (

N × k

)

α vettore colonna di dimensione

N

,

ζ = (ζ

0

, ζ

1

, . . . , ζ

k−1

)

T vettore dei coefficienti.

La matrice Λ e il vettore α dipendono dal metodo.

(15)

Metodi polinomiali

••

◮ Reduced Rank Extrapolation (RRE):

Λ = [w

n

, w

n+1

, · · · , w

n+k−1

]

,

α = −u

n

risolvendo, nel senso dei minimi quadrati, il sistema sovradeterminato, si ha

s

(n)k

= x

n

+ P

k−1

j=0

ζ

j

u

n+j

.

(16)

Metodi polinomiali

••

◮ Reduced Rank Extrapolation (RRE):

Λ = [w

n

, w

n+1

, · · · , w

n+k−1

]

,

α = −u

n

risolvendo, nel senso dei minimi quadrati, il sistema sovradeterminato, si ha

s

(n)k

= x

n

+ P

k−1

j=0

ζ

j

u

n+j

.

◮ Minimal Polynomial Extrapolation (MPE):

Λ = [u

n

, u

n+1

, . . . , u

n+k−1

]

,

α = −u

n+k

determinati i coefficienti risolvendo ai minimi quadrati, posto

ζ

k

= 1

,

γ

j

=

Pkζj

i=0 ζi

, j = 0, 1, . . . , k

si ha l’approssimazione

s

(n)k

= P

k

j=0

γ

j

x

n+j

(17)

Metodi ε -algorithms

••

Sia

{x

n

}, n = 0, 1, 2, . . .

successione vettoriale con limite s.

I metodi di tipo ε-algorithms definiscono una trasformazione vettoriale per accelerare la convergenza di tale successione, basata sul rapporto di determinanti.

Sono algoritmi che si possono implementare con formule ricorsive; si considerano

◮ Vectorial Epsilon Algorithm (VEA)

◮ Topological Epsilon Algorithm (TEA)

(18)

Metodi ε -algorithms

••

Vectorial ε-algorithms

ε(n)−1 = 0, ε(n)0 = xn, n = 0, 1, . . .

ε(n)k+1 = ε(n+1)k−1 + [ε(n+1)k − ε(n)k ]−1 k, n = 0, 1, . . . . z−1 = z/kzk2

(19)

Metodi ε -algorithms

••

Vectorial ε-algorithms

ε(n)−1 = 0, ε(n)0 = xn, n = 0, 1, . . .

ε(n)k+1 = ε(n+1)k−1 + [ε(n+1)k − ε(n)k ]−1 k, n = 0, 1, . . . . z−1 = z/kzk2

◮ Topological ε-algorithms

ε(n)−1 = 0, ε(n)0 = xn, n = 0, 1, . . .

ε(n)2k+1 = ε(n+1)2k−1 + y/

y, ∆ε(n)2k  ε(n)2k+2 = ε(n+1)2k + ∆ε(n)2k / 

∆ε(n)2k+1, ∆ε(n)2k 

(20)

Metodi ε -algorithms

••

◮ In entrambi viene generata ricorsivamente una tavola di valori a partire da un numero k di elementi della

successione di partenza e si approssima il limite con

s = ε

(n)2k

Per TEA l’efficacia del metodo è legata alla scelta del vettore y.

(21)

Applicazioni: sistemi lineari

••

◮ Risoluzione di un sistema lineare di grandi dimensioni:

Ax = b

⇒ è un classico ed importante problema per cui si adoperano algoritmi di tipo iterativo.

Sia

{x

i

}, i = 0, 1, 2, . . .

successione di vettori di

R

N,

generata linearmente a partire da un vettore iniziale

x

0,

x

i+1

= Gx

i

+ d

,

dove la matrice G e il vettore d dipendono dal metodo scelto; sotto opportune ipotesi

lim

i→∞

x

i

=

s

= A

1

b .

◮ Il processo di convergenza può essere

computazionalmente oneroso: è di interesse indagare l’efficacia e l’applicabilità dei metodi di accelerazione.

(22)

Algoritmo di estrapolazione

••

Initializations guess

x

(0)0

, k

j ← 0, s

0

← x

(0)0 repeat

1. Collection step, si generano e collezionano

k

vettori:

x

(j)i+1

= Gx

(j)i

+ d, i = 0, . . . , k − 1

2. Extrapolation step, si estrapola con uno dei metodi:

x

(j)0

, . . . , x

(j)k =⇒

x

(j)e

→ s

j+1

3. Restarting step, si utilizza il vettore estrapolato come vettore iniziale:

j ← j + 1, x

(j)0

← s

j+1

until

kAs

j+1

− bk < ε

(23)

Sistemi lineari: alcuni risultati

••

Esempio 1

A =

tridiag

([−1, 2.1, −1]), N = 500, b = Ax, x = [1, · · · , 1]

T

x

i+1

= Gx

i

+ d →

Gauss Seidel

0 200 400 600 800 1000 1200 1400

10−7 10−6 10−5 10−4 10−3 10−2 10−1 100 101

Number of iteration

Error Norm

MPE

RRE VEA

TEA

GAUSS SEIDEL

0 200 400 600 800 1000 1200 1400

10−9 10−8 10−7 10−6 10−5 10−4 10−3 10−2 10−1 100 101

Number of iteration

Residual Norm

VEA

TEA RRE MPE

GAUSS SEIDEL

(24)

Sistemi lineari: alcuni risultati

••

Esempio 2

ORSIRR 1- Oil reservoir simulation 21x21x5 irregular grid Harwell-Boeing Collection, (1030 x 1030), 6858 entries

0 100 200 300 400 500 600 700 800 900 1000

0

100

200

300

400

500

600

700

800

900

1000

nz = 6858

0 1000 2000 3000 4000 5000 6000

10−12 10−10 10−8 10−6 10−4 10−2 100 102

Number of iteration

Error Norm

GAUSS SEIDEL

VEA

TEA RRE

MPE

k = 20

,

y =

randn(N,1) a media nulla e varianza unitaria.

(25)

TEA: scelta del vettore y

••

◮ Gli esempi numerici mostrano che l’efficacia del metodo è legata alla scelta di y;

◮ sono in corso approfondimenti per trarre giustificazioni teoriche;

◮ alcune possibili scelte:

◮ y generato random e mantenuto fisso durante l’esecuzione (y fix);

◮ y generato random ad ogni restarting (y rand);

◮ y posto uguale al residuo

(b − As

i

)

ad ogni restarting (y res);

◮ y posto uguale alla differenza

(s

i+1

− s

i

)

tra due

(26)

TEA: scelta del vettore y

••

Esempio 1

A =

tridiag

([−1, 2.1, −1]), N = 500, b = Ax, x = [1, · · · , 1]

T

x

i+1

= Gx

i

+ d →

Gauss Seidel

0 200 400 600 800 1000 1200 1400 1600 1800 2000

10−10 10−8 10−6 10−4 10−2 100 102 104

Number of iteration

Error Norm Gauss Seidel

y fix y diff

y rand y res

0 200 400 600 800 1000 1200 1400 1600 1800 2000

10−12 10−10 10−8 10−6 10−4 10−2 100 102 104

Number of iteration

Residual Norm

Gauss Seidel y diff

y rand

y res y fix

◮ In seguito a diversi test numerici la scelta migliore risulta essere y res.

(27)

Caso non lineare: mappa di Gummel

••

Tipico problema che nasce dalla fisica dei semiconduttori, descritto dal modello Drift-Diffusion

∇ · (−ǫ∇ψ) = q(p − n + C)

∇ · Jn = Rn

∇ · Jp = Rp,

dove Jn e Jp sono le correnti associate ai portatori n e p.

Jn = −qµnn∇ψ + qDn∇n Jp = −qµpp∇ψ − qDp∇p,

e la funzione di ricombinazione di Schockley–Read–Hall è np − n2

(28)

Modello Drift Diffusion

••

◮ Sistema composto da un’equazione di diffusione per il potenziale elettrostatico associata alle equazioni di

convezione-diffusione per i portatori di carica;

◮ tre equazioni differenziali non lineari mutuamente

accoppiate nelle tre variabili ψ, n e p, in cui ciascuna

dipende contemporaneamente da tutte e tre le incognite;

◮ si introducono i quasi-livelli di Fermi per elettroni e lacune,

φ

n ,

φ

p e le associate variabile di Slotboom

u =

exp

(−φ

n

)

,

v =

exp

p

)

;

◮ si usa un’algoritmo per disaccoppiare ogni equazione dalle altre due: mappa di Gummel

(29)

Mappa di Gummel: algoritmo

••

Initializations

guess

ψ

(0)

, φ

(0)n

, φ

(0)p

k ← 0

repeat

1. solve

−λ

2

△ψ

(k+1)

= −n

i

e

ψ(k+1)φ(k)n

+ n

i

e

φ(k)p ψ(k+1)

+ C

acceleration procedure on

ψ

2. solve

∇ · [n

i

µ

n

e

ψ(k+1)

∇u

(k+1)

] = R(ψ

(k+1)

, φ

(nk)

, φ

(pk)

)

acceleration procedure on

φ

n

3. solve

∇ · [n

i

µ

p

e

ψ(k+1)

∇v

(k+1)

] = R(ψ

(k+1)

, φ

(nk)

, φ

(pk)

)

acceleration procedure on

φ

p

4.

k = k + 1

until

max{ε

ψ

, ε

φn

, ε

φp

} <

ε

(30)

Condensatore MOS - modello

••

◮ Il modello è assimilabile ad un condensatore classico in cui

◮ una delle due armature è metallica: il contatto

AB

◮ l’altra è formata dal semiconduttore (p-Silicon):

regione

CDEF

◮ Le tensioni sono applicate ai contatti AB ed ED.

(31)

Condensatore MOS - risultati

••

0 10 20 30 40 50 60 70 80 90

10−10 10−8 10−6 10−4 10−2 100

Gummel Iterations

Control Parameter Value

NO ACCELERATION

MPE

RRE VEA TEA

◮ in condizioni stazionarie, nessuna corrente attraversa l’ossido,

J

n

= J

p

= 0

ed il modello si riduce

all’equazione di Poisson (accelerazione su

ψ

);

◮ il tempo di calcolo è ridotto di circa 3 volte;

(32)

Giunzione p–n

••

◮ Il diodo a giunzione è stato il primo dispositivo a semiconduttore reso disponibile commercialmente;

◮ è un rettificatore bipolare, la cui funzione ideale è quella di permettere il flusso di corrente elettrica in una

direzione e di bloccarla nell’altra.

(33)

Giunzione p–n brusca

••

Giunzione brusca, simmetrica con i seguenti parametri

Na = Nd = 1022m−3 (drogaggio, funzione C(x));

τn = τp = 10−5s (generazione, funzione R);

µn = µp = 0.06m2/s (mobilità, funzioni µn, µp).

Va = 0.3V, Va = −5V

Forti gradienti si presentano in corrispondenza dell’unione dei due drogaggi differenti; la soluzione presenta strati limite.

0.05 0.1 0.15 0.2 0.25 0.3 0.35

electrostatic potential [ V ] 1

2 3 4 5 6

Electrostatic potential [ V ]

(34)

Giunzione p − n brusca - risultati

••

0 2 4 6 8 10 12 14 16 18 20

10−8 10−7 10−6 10−5 10−4 10−3 10−2 10−1 100

Gummel Iterations

Control Parameter Value

RRE 5

RRE 10 VEA 10

NO ACCELERATION

◮ L’accelerazione riduce di circa 2 volte il tempo di calcolo;

◮ l’efficienza è maggiore per i metodi polinomiali.

(35)

MOSFET

••

◮ dispositivo fondamentale della moderna microelettronica;

◮ da notare la presenza del condensatore MOS e delle giunzioni p–n.

(36)

Conclusioni

••

◮ Le tecniche di accelerazione hanno fornito buoni risultati per i sistemi lineari, in particolare

◮ I metodi polinomiali sono più efficienti;

◮ si sta indagando per migliorare le prestazioni degli

ε

-algorithms.

◮ L’applicazione alla mappa di Gummel fornisce risultati buoni, anche se preliminari.

◮ Si intende estendere lo studio al caso bidimensionale per la giunzione p–n;

◮ applicare l’accelerazione ad altri dispositivi (MOSFET,...).

R. Bertelle, M.R. Russo, ”An Approach to the Gummel Map by Vector Extrapolation Methods”, submitted.

Riferimenti

Documenti correlati

Corso di Laurea in Ingegneria per l’Ambiente e il Territorio 6 CFU

Corso di Laurea in Ingegneria per l’Ambiente e il Territorio 6 CFU

Corso di Laurea in Ingegneria per l’Ambiente e il Territorio 6 CFU

3.3 Solution of nuclear norm problem via proximal algorithms 83 We notice that we have the initial problem, therefore it is not useful to apply the proximal Newton method to this

Entrambe le forme di trattamento comportano un miglioramento della funzione b-cellulare, forse con un effetto più spiccato per gli analoghi del GLP-1, mentre comparabile

Il grosso della progettazione del controllo deve essere quindi eseguito nel modo pi´ u preciso possibile proprio nella prima fase in modo da utilizzare i test solo per la verifica

In modo del tutto analogo si prova convergenza uniforme anche su intervalli tipo (−∞, a]... Dunque la successione converge uniformemete

Il territorio dell’isolotto, un tipo di Friche (Clèment, 2006), cosparso di rovine e macerie che si dispongono ben visibili agli occhi del protagonista, incontra il destino, che