Che materia stai cercando?

Analisi numerica - Ordine di convergenza Appunti scolastici Premium

In questo materiale didattico vengono trattati i seguenti argomenti. Ordine di convergenza del metodo di iterazione funzionale: sublineare, lineare, superlineare; teorema di convergenza del primo ordine; teorema di convergenza di ordine p, [math]p\in\mathbb{N}[/math].
Metodi iterativi: metodo delle corde (interpretazione geometrica... Vedi di più

Esame di Ricerca Operativa docente Prof. M. Castellani

Anteprima

ESTRATTO DOCUMENTO

Minicorso da 3 crediti

Ordine di convergenza

3

2.5

2 1 x

2

1.5 0.8

1

0.5 x

0 0.6 3

x

1

−0.5 0.4

−1

−1.5

−2 0.2

−2.5 x

0

−3 0

−3 −2.5 −2 −1.5 −1 −0.5 0 0.5 1 1.5 2 2.5 3 0 0.2 0.4 0.6 0.8 1 1.2

(x) = − =

Figura: Grafico di f x cos x e punto fisso di x cos x dsm

Marco Castellani (L’Aquila) Ricerca Operativa Minicorso da 3 crediti 8 / 27

Minicorso da 3 crediti

Ordine di convergenza ∈

Teorema (sulla convergenza di ordine p N)

p

∈ C

Sia x punto fisso per g tale che

2 p−1 p

= = = = 6 =

Dg(x) D g(x) D g(x) 0 e D g(x) 0.

. . . ∈ [x − + ] \ {x},

Allora esiste r 0 per cui, per ogni x r x r la

> ,

0

{x } (1) converge a x con ordine p.

successione generata dal metodo

n

Dimostrazione. Per il Teorema di Taylor con il resto di Lagrange

esiste z compreso tra x e x per cui

n n p

|g(x ) − |D )|

|x − x| g(x)| g(z

n n

n+1 = = .

p p

|x − |x −

x| x| p!

n n

Poiché se x converge a x anche z tende a x e la funzione g è di

n n

p

C

classe si ottiene la tesi. dsm

Marco Castellani (L’Aquila) Ricerca Operativa Minicorso da 3 crediti 9 / 27

Minicorso da 3 crediti

Ordine di convergenza

Esercizio

Determinare l’ordine di convergenza del metodo iterativo (1) applicato

all’equazione 2

− + =

x ln(x 1) 0

=

Ad occhio si vede che x 0 è una soluzione. Inoltre la funzione

2

(x) = − +

f x ln(x 1)

risulta crescente su tutto in quanto

R 2

(x − 1)

(x) = ≥

Df 0.

2 +

x 1 dsm

Marco Castellani (L’Aquila) Ricerca Operativa Minicorso da 3 crediti 10 / 27

Minicorso da 3 crediti

Ordine di convergenza

Quindi la soluzione è unica che determiniamo calcolando il punto fisso

della funzione 2

= + =

x ln(x 1) g(x).

Le derivate prima e seconda sono 2

2x 2 2x

2 ;

= =

Dg(x) e D g(x)

2 2 2

+ (x +

x 1 1)

2

= =

poiché Dg(0) 0 e D g(0) 2, la successione ha convergenza

=

quadratica. Partendo da x 1 si ottengono i seguente valori

0

n 0 1 2 3 4 5 6

x 1, 0000 0, 6931 0, 3923 0, 1431 0, 0202 0, 0004 0, 0000

n dsm

Marco Castellani (L’Aquila) Ricerca Operativa Minicorso da 3 crediti 11 / 27

Minicorso da 3 crediti

Ordine di convergenza

2

1.5 1

1 0.8 x

0.5 1

0 0.6 x

−0.5 2

0.4

−1 x

0.2 3

−1.5 x

0

−2 0

−1.5 −1 −0.5 0 0.5 1 1.5 2 2.5 3 0 0.2 0.4 0.6 0.8 1 1.2

2 2

(x) = − + = +

Figura: Grafico di f x ln(x 1) e punto fisso di x ln(x 1) dsm

Marco Castellani (L’Aquila) Ricerca Operativa Minicorso da 3 crediti 12 / 27

Minicorso da 3 crediti

Metodi iterativi (x) =

Supponiamo di voler risolvere l’equazione f 0.

Domanda: come costruire la funzione g i cui punti fissi coincidono con

le soluzioni dell’equazione?

Solitamente si pone (x)

f

= −

g(x) x h(x)

: (a, −→

dove h b) è una opportuna funzione tale che

R 6 = ∀x ∈ (a,

h(x) 0, b).

A seconda della scelta della funzione h si ottengono metodi diversi. dsm

Marco Castellani (L’Aquila) Ricerca Operativa Minicorso da 3 crediti 13 / 27

Minicorso da 3 crediti

Metodo delle corde Metodo delle corde

= 6 =

Si ottiene scegliendo h(x) m con m 0. In tal caso la funzione g è

(x)

f

= −

g(x) x m

{x }

e la successione generata dal metodo (1) è

n (x )

f n

= −

x x .

n

n+1 m

Domanda: come possiamo scegliere m affinché il metodo delle corde

converga? dsm

Marco Castellani (L’Aquila) Ricerca Operativa Minicorso da 3 crediti 14 / 27

Minicorso da 3 crediti

Metodo delle corde

1

∈ C

Se f , le ipotesi del Teorema sul punto fisso sono verificate se

esiste r 0 per cui

> (x)

Df

− − + ] \ {x}

|Dg(x)| = ∀x ∈ [x

1 r x r

1, ,

<

m

che possiamo riscrivere − + ] \ {x}.

|m − (x)| |m|, ∀x ∈ [x r x r

Df ,

<

Elevando al quadrato ambo i membri della disuguaglianza e

semplificando i calcoli si ottiene

(x)(Df (x) − ∀x ∈ [x − + ] \ {x}.

Df 2m) 0, r x r

< , dsm

Marco Castellani (L’Aquila) Ricerca Operativa Minicorso da 3 crediti 15 / 27

Minicorso da 3 crediti

Metodo delle corde

La precedente disequazione equivale alla verifica delle seguenti tre

∈ [x − + ] \ {x}:

condizioni al variare di x r x r

, 1

(x) 6 = (x) |m| |Df (x)|

Df 0, mDf 0, max

> > 2 ]

x∈[x−r ,x+r

Per quanto riguarda l’ordine di convergenza del metodo delle corde,

sotto le tre precedenti condizioni si ha 6 = (x),

convergenza del primo ordine se m Df

= (x).

convergenza superlineare se m Df dsm

Marco Castellani (L’Aquila) Ricerca Operativa Minicorso da 3 crediti 16 / 27

Minicorso da 3 crediti

Metodo delle corde

Esercizio

Utilizzando il metodo delle corde, determinare la soluzione

3 + − =

dell’equazione x 4x 2 0 con una precisione fino alla quarta cifra

decimale.

Il primo passo consiste nell’individuare m. Abbiamo visto che esiste

2

∈ [0, (x) = +

x 1] e Df 3x 4; quindi

una sola soluzione ≤ (x) ≤ ∀x ∈ [0,

4 Df 7, 1].

La prima condizione è verificata, per la seconda dobbiamo scegliere

7 =

m 0 mentre per la terza si deve avere m . Per m 4 otteniamo

> > 2

3

2−x

(x) = =

la funzione g studiata precedentemente mentre per m 5

4 4 3

2+x−x

(x) =

otteniamo la funzione g .

5 5 dsm

Marco Castellani (L’Aquila) Ricerca Operativa Minicorso da 3 crediti 17 / 27

Minicorso da 3 crediti

Metodo delle corde

Confrontiamo le due successioni utilizzando Excel scegliendo come

|x − |

criterio di arresto x 0, 0001.

<

n

n+1 g g 5

4

x 0 0

0

x 0, 50000 0, 40000

1

x 0, 46875 0, 46720

2

x 0, 47425 0, 47304

3

x 0, 47333 0, 47344

4

x 0, 47349 0, 47346

5

x 0, 47346 STOP

6

x STOP

7

Domanda: che cosa possiamo dedurre da questo confronto? dsm

Marco Castellani (L’Aquila) Ricerca Operativa Minicorso da 3 crediti 18 / 27

Minicorso da 3 crediti

Metodo delle corde

1

0.8

0.6 x

2

0.4 x

1

0.2 x

0

0 0 0.2 0.4 0.6 0.8 1 1.2

3

2+x−x

=

Figura: Punto fisso della funzione g(x) 5 dsm

Marco Castellani (L’Aquila) Ricerca Operativa Minicorso da 3 crediti 19 / 27


PAGINE

27

PESO

466.03 KB

AUTORE

Atreyu

PUBBLICATO

+1 anno fa


DESCRIZIONE DISPENSA

In questo materiale didattico vengono trattati i seguenti argomenti. Ordine di convergenza del metodo di iterazione funzionale: sublineare, lineare, superlineare; teorema di convergenza del primo ordine; teorema di convergenza di ordine p, [math]p\in\mathbb{N}[/math].
Metodi iterativi: metodo delle corde (interpretazione geometrica ed esempi); metodo delle tangenti (o di Newton) (interpretazione geometrica ed esempi).


DETTAGLI
Corso di laurea: Corso di laurea in economia e amministrazione delle imprese
SSD:
Università: L'Aquila - Univaq
A.A.: 2011-2012

I contenuti di questa pagina costituiscono rielaborazioni personali del Publisher Atreyu di informazioni apprese con la frequenza delle lezioni di Ricerca Operativa e studio autonomo di eventuali libri di riferimento in preparazione dell'esame finale o della tesi. Non devono intendersi come materiale ufficiale dell'università L'Aquila - Univaq o del prof Castellani Marco.

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 Ricerca operativa

Programmazione Lineare Intera
Dispensa
Programmazione lineare
Dispensa
Algoritmi su grafi - Prima parte
Dispensa
Modelli
Dispensa