Che materia stai cercando?

Analisi numerica - Ordine di convergenza

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

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

Minicorso da 3 crediti

Metodo delle corde

L’interpretazione geometrica dell’algoritmo della corda è la seguente:

+ (x) =

Al passo n 1 si sostituisce l’equazione nonlineare f 0 con

un’opportuna equazione lineare

− ) + (x ) =

m(x x f 0;

n n = (x)

in altre parole si approssima la funzione y f con la retta

(x (x ))

passante per f ed avente coefficiente angolare m

,

n n = (x ) + − )

y f m(x x

n n

Tanto più il coefficiente angolare m si avvicina al coefficiente angolare

della retta tangente in x tanto più veloce è la velocità della

convergenza. dsm

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

Minicorso da 3 crediti

Metodo delle corde

6

5

4

3

2

1

0 x

x

x 2

1

0

−1

−2 0 0.5 1 1.5 2 2.5

Figura: Passi dell’algoritmo della corda dsm

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

Minicorso da 3 crediti

Metodo delle tangenti (di Newton)

Metodo delle tangenti

1

∈ C

Se ipotizziamo f , invece di considerare ad ogni iterazione rette

con la stessa inclinazione potremmo prendere le rette tangenti al

= (x).

h(x) Df Per far questo dobbiamo

grafico di f scegliendo

(x) 6 =

supporre Df 0 in un opportuno intorno di x; in tal caso la funzione

g è (x)

f

= −

g(x) x (x)

Df

e la successione generata risulta (x )

f n

= −

x x .

n

n+1 (x )

Df n dsm

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

Minicorso da 3 crediti

Metodo delle tangenti (di Newton)

2 1

∈ C ∈ C

Se inoltre ipotizziamo f , allora g e la derivata di g è

2

(x) · (x)

f D f

=

Dg(x) .

2

[Df (x)]

= 0, per il Teorema della permanenza del segno

Essendo Dg(x)

esiste r 0 per cui

> |Dg(x)| ∀x ∈ [x − + ].

1, r x r

< ,

Quindi, per il Teorema sul punto fisso, la successione generata dal

metodo di Newton converge; in particolare per il Teorema sulla

convergenza del primo ordine si ha che la convergenza è superlineare.

dsm

Marco Castellani (L’Aquila) Ricerca Operativa Minicorso da 3 crediti 23 / 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