Che materia stai cercando?

Anteprima

ESTRATTO DOCUMENTO

f ( x )

n

= − .

x x

+ −

n n

1 ( ) ( )

f x f a

n −

x a

n

Per verificare la convergenza locale e l'ordine di convergenza del metodo, utilizziamo il

f x

( )

ϕ( = −

teorema 7.2. La funzione di iterazione è e si vede facilmente che

x ): x −

f ( x ) f ( a )

x a

f '( *)( * )

x x a

ϕ'( = +

x *) <1 per ogni a di un intervallo nel quale la radice x* è unica. Infatti il

1 ( )

f a

x * a è sempre opposto al segno di f'(x*). Inoltre se a è sufficientemente vicino a

segno di f ( a )

x* si ha |ϕ'(x*)|<1 e quindi, per il teorema 7.2, esiste un intorno U dove sono verificate le

x*

ipotesi di convergenza locale di ordine 1. Quindi vale il seguente teorema:

2

Teorema 7.3. Se la funzione f(x) è di classe C e f'(x*)≠0, allora esiste un intorno

U (=[a,b]) nel quale il metodo delle corde è localmente convergente con ordine di

x*

convergenza p=1, e con costante d'errore:

max | f ''( t )|

1 ∈

t U

⋅ −

x * | b a |

con c= min | f '( t )|

2 ∈

t U x *

Per trovare in concreto l'intervallo U =[a,b] del teorema 7.2 e la corrispondente

x*

costante d'errore c, consideriamo la formula di Newton sui nodi a ed x calcolata nel punto

fisso x* η

f''( )

f(x*) = f(x) + (x*-x) f[a,x] + (x*-x) (x*-a) 2

η

f''( )

0 = (x*-ϕ(x)) f[a,x] + (x*-x) (x*-a) 2

η

f''( )

0= (x*-ϕ(x)) f'(ρ) + (x*-x) (x*-a) 2

η max | f ''( t )|

| f ''( )| 1

1 t U

≤ x *

|x*-ϕ(x)| = |x*-x| |(x*-a)| |(x*-a)| |x*-x|.

ρ min | f '( t )|

| f '( )| 2

2 ∈

t U x *

Si osservi che per ottenere tale stima abbiamo assunto che la funzione f(x) sia di classe

2

C e che f'(x*)≠0. max | f ''( t )|

1 t U x * |(x*-a)|<1 allora il metodo converge per ogni punto di

Se U è tale che c=

x* min | f '( t )|

2 ∈

t U x *

partenza in U .

x*

f(x)=ex+x2-2.

Esempio: Sia Si osservi che f(0)=-1 e f(1)=e-1=1.7.. e quindi in [0,1] c'è una

f'(x)=ex+2x

radice di f. Poichè >0 per ogni x in [0,1], la radice è unica. Si verifichi se il

199

metodo delle corde è localmente convergente in [0,1] ed in caso contrario si determini un

sottointervallo di convergenza.

Il metodo di Newton e le sue varianti.

Uno dei metodi più noti ed efficaci per la soluzione dell'equazione f(x)=0 è il

metodo di Newton. Esso consiste nella seguente formula iterativa:

( )

f x n

= − .

x x

+

n n

1 '( )

f x n ,f( )), la retta

che corrisponde a prendere, nel fascio di rette (7.5) passanti per ( x x

n n

tangente. ≠

Come si vede, il metodo si applica a funzioni derivabili per le quali la derivata prima è 0

almeno in un intorno del punto fisso x*, altrimenti l'iterazione potrebbe non essere ben

definita. Osserviamo subito che vale la seguente proprietà:

2

T 7.4. Se la funzione f(x) è di classe C e f'(x*)≠0, allora esiste un intorno U nel

EOREMA x*

quale il metodo di Newton è localmente convergente con ordine di convergenza

p=2, e con costante d'errore: max | f ''( t )|

1 t U

⋅ x *

con d= min | f '( t )|

2 ∈

t U x *

Poichè f'(x*)≠0, il metodo è ben definito in tutto un intorno di x*. Inoltre, dalla

f x

( ) ϕ'(x*)=0

ϕ(x):=x , si ottiene immediatamente

derivazione della funzione di iterazione - f '( x )

e quindi, in base ai teoremi 7.1 e 7.2, il metodo è localmente convergente con ordine p=2.

Infine, per il calcolo della costante d, si considera il seguente sviluppo di Taylor della

funzione f(x): − 2

( x * x )

f(x*) = f(x) + (x*-x)f'(x) + f''(η)

2

Dividendo entrambi i membri per f'(x) , si ottiene:

η

f ''( )

f x

( ) 1 2

x x

( * )

0= + (x*-x)+ f x

'( )

f '( x ) 2 200

η

f ''( )

1 2

ϕ(x) x x

( * )

- x* = f x

'( )

2 max | f ''( t )|

1 t U

− 2 x *

|ϕ(x) - x*| < | x * x | .

min | f '( t )|

2 ∈

t U x *

In questo caso, in accordo col teorema 7.1, l'intorno [a,b]=U di convergenza locale deve

x*

*

essere tale che, in ogni suo punto x , la costante a:= d||x -x || sia <1.

0 0

Esempio. Si determini un intervallo di convergenza locale del metodo di Newton

2

relativamente al calcolo di vista come radice positiva dell'equazione x -2=0

2

Variante del metodo di Newton per radici multiple.

Nel caso che la radice x* sia doppia, cioè che sia f(x*)=0, f'(x*)=0 ed inoltre f''(x*)≠

0, è evidente che il metodo di Newton è ancora ben definito in un intorno sufficientemente

piccolo di x* dove la f'(x)≠0 per tutti i punti diversi da x*. In tal caso però il metodo, che

rimane localmente convergente, converge con ordine p=1. Ciò si verifica direttamente, in

base al teorema 7.2, derivando la funzione di iterazione per la quale si ha (con la regola

dell'Hôpital): ϕ'(x*) = -1/2.

D'altra parte si verifica facilmente che la seguente variante del metodo di Newton:

f ( x )

n

= − .

x x 2

+

n n

1 f '( x )

n ϕ(x):=x

è ancora convergente con ordine p=2. In questo caso la funzione di iterazione è -

f x

( ) ϕ'(x*)=0.

2 per la quale Si osservi però che, dal punto di vista computazionale, la

f '( x )

formula è instabile in prossimità della soluzione x*, dove si avvicina ad una forma

indeterminata del tipo 0/0.

Più in generale, vale la seguente proprietà:

T 7.5. Se la radice x* ha molteplicità s, cioè se

EOREMA (s-1) (s)

f(x*)=f'(x*)=...=f (x*)=0 ed f (x*)≠0,

201

allora il metodo iterativo:

( )

f x n

= − .

x x s

+

n n

1 '( )

f x n

è localmente convergente con ordine di convergenza p=2.

La dimostrazione segue immediatamente dall'applicazione del teorema 7.2.

Se, viceversa, non si conosce la molteplicità della radice x* allora si osserva che

( )

f x

=

( ):

u x

per la funzione il punto x* è una radice semplice e quindi si applica il metodo

'( )

f x

di Newton che diventa, in termini di f(x) e di f'(x),:

f x f x

( ) '( )

n n

= −

x x

+

n n

1 2 −

f '( x ) f ( x ) f "( x )

n n

Considerazioni geometriche sull'iterazione di Newton, rendono intuitiva la seguente

proprietà:

T 7.6. Se la funzione f(x) mantiene costante il segno di f' e di f'' in R, allora il

EOREMA

metodo di Newton converge per ogni punto iniziale x e, a parte eventualmente il

0

primo passo, l'iterazione converge in modo monotono. f(x)

x*

x 0 x3 x2 x1

Il metodo di Steffensen.

Un metodo che conserva l'ordine 2 ma non richiede l'uso della derivata di f è il

metodo di Steffensen che consiste nell'iterazione:

202 f ( x )

n

= −

x x

+

n n + −

1 f x f x f x

( ( )) ( )

n n n

f x

( )

n

Essa è ricavata dall'iterazione di Newton dove, per ogni punto della traiettoria, la derivata

f'(x) è sostituita dal rapporto incrementale con incremento f(x).

Attraverso il teorema 7.2 si verifica facimente che il metodo è localmente convergente con

ordine 2 in quanto la derivata della funzione di iterazione si annulla in x*.

Il metodo delle secanti

Una variante molto utile del metodo di Newton è data dal seguente metodo delle secanti:

f ( x )

f ( x ) n

n

= − =x n≥1,

x x

+ − n

n n

1 ( ) ( )

f x f x − f x , x

−1

n n 1 n n

x x −

n n 1

con x , x dati.

0 1

Esso si ottiene dal metodo di Newton sostituendo il valore f'(x ) con il rapporto

n

f ( x ) f ( x )

n n 1

incrementale costruito sugli ultimi due passi dell'iterazione.

x x −

n n 1

Il metodo delle sacanti non rientra nella classe dei metodi iterativi di Picard perchè si

presenta come un metodo iterativo a 2 passi e per esso non valgono i teoremi

precedenti. Cionondimeno, in ogni intorno nel quale il rapporto incrementale è ben

definito, il metodo è localmente convergente con ordine di convergenza p=1.618... . Vale

cioè la relazione: . .

.

− 1 618

|x - x*| < k| x * x | per n>1.

n

n+1

Per dimostrare le precedenti affermazioni, consideriamo la formula d'interpolazione di

ed x ,

Newton sui due punti x

n-1 n ξ

f( )

f(x)=f(x )+(x-x )f[x , x ] + (x-x )(x-x )

n n n-1 n n-1 n 2

e calcoliamola in x*: ξ

f "( )

n

0=f(x )+(x*-x )f[x , x ] + (x*-x )(x*-x )

n n n-1 n n-1 n 2 ξ

f "( )

n

0=f(x )+(x*-x +x -x )f[x , x ] + (x*-x )(x*-x )

n n+1 n+1 n n-1 n n-1 n 2

ξ

f "( )

n

0=(x*-x )f[x , x ] + (x*-x )(x*-x ) .

n+1 n-1 n n-1 n 2

203

ξ

f "( )

n

(x*-x ) = - (x*-x )(x*-x )

n+1 n-1 n η

f '( )

2 n

ξ

f "( )

1 n

e e e . (7.6)

n+1 = n n-1 η

f '( )

2 n

Si vede quindi che se x e x appartengono ad un intorno U tale che

0 1 x*

max | f ''( t )|

1 t U

⋅ x *

c:= e max {ce , ce }= d < 1

0 1

min | f '( t )|

2 ∈

t U x *

si ha: ≤

e e e c =d e .

2 1 0 1

∈U

Di conseguenza anche x , ed al passo successivo si avrà ancora

2 x* ξ

f "( )

1

≤ 2

e e e

3 2 1 η

f '( )

2 2

ξ η ∈U

con e . Quindi

2 2 x* ≤ ≤ 2

e e e c de (≤d e )

3 2 1 2 1

e, per induzione, si dimostra che

≤d ∀n

n

e

e

n+1 1

da cui discende la convergenza del metodo.

Per quanto riguarda la velocità di convergenza, si osservi che la relazione (7.6) si

può scrivere ξ

f "( )

1 n

≤ →0

e e d con d =e per n→∞

n+1 n n n n-1 η

f '( )

2 n

In questo caso si dice che il metodo converge in modo superlineare. Per trovare l'ordine

di convergenza facciamo il seguente ragionamento euristico.

Supponiamo di sapere che c'e un numero reale p tale che

204

e +

n →

1 k per n→∞.

p

e n

Ciò significa che per n sufficientemente grande il rapposto rimane pressochè costante

uguale a k. Indicheremo questo fatto con la notazione:

np

≈ ∀n>>1.

e ke (7.7)

n+1

Al passo precedente ho: np

e ke −1

n

da cui −1 1

≈ p

p

e k e .

n-1 n

Dalla (7.6) ho f "( x *)

1

e e e c con c= .

n+1 n n-1 f '( x *)

2

e quindi −1 − +

1 1

1 1

≈ p p

p p

e e k e c =ck e .

n+1 n n n

Infine dalla (7.7) − + 1

1 1

np ≈ p

p

ke c k e n

da cui +

1 5

1

p=1+ (⇒ p= =1.618....)

p 2

e + 1

1 f "( x *)

1 1

p =

= p

p p

c

c≈k k (⇒k= )

f '( x *)

2

La costante k è detta costante asintotica del metodo.

Nel confrontare il metodo di Newton col metodo delle secanti, si osservi che quest'ultimo

non richiede la conoscenza della derivata della funzione f(x). Inoltre il costo

computazionale si riduce, dopo il primo passo, ad una sola valutazione di f per ogni passo,

contro una valutazione di f e una di f' del metodo di Newton. Possiamo quindi dire che il

costo di un passo del metodo di Newton corrisponde al costo di due passi del metodo

delle secanti per i quali si ha la seguente stima dell'errore:

205 . ..

1 618

. .

. . .. . .. . ..

− − = −

1 618 1 618 2 618 2 618

|x - x*|< k| x * x | <k k | x * x | k | x * x |

− −

n n n

1 1

n+1

Possiamo quindi concludere che, in generale, il metodo delle secanti riesce più

conveniente del metodo di Newton.

3. S (cenni)

ISTEMI DI EQUAZIONI n n

Consideriamo ora funzioni di R in R che, per distinguere dal caso scalare, indicheremo

con n

F(x)=(f (x),f (x),...,f (x)) x∈R .

1 2 n

n

In R vale il teorema 7.1, ed un criterio di convergenza, simile al teorema 7.2 (parte a), è il

ϕ'(x ϕ ρ(ϕ'(x

* *

seguente, dove ) è la matrice jacobiana di nel punto x*, e )) è il suo raggio

spettrale.

Teorema 7.7. 1

ϕ(x) *

Se è di classe C , e R=ρ(ϕ'(x ))<1, allora esiste U ed una costante c, tali

x*

che 0<c<1 e ∀x∈U

* *

||x -ϕ(x)||≤c||x -x|| x*

cioè il metodo converge con ordine 1. ε>0

Dim: Per le proprietà del raggio spettrale, in corrispondenza ad ogni esiste una norma

tale che ||ϕ'(x*)||< R+ε. (7.8)

ϕ

Inoltre, considerato il differenziale della funzione nel punto x*

ϕ(x*)+ϕ'(x*)(x-x*),

esiste un intorno U per quale si ha:

x*

ϕ(x) ≤ ε||x-x*|| ∀

|| -ϕ(x*)-ϕ'(x*)(x-x*)|| x∈U .

x*

Da quest'ultima e dalla (7.8) 206


PAGINE

19

PESO

138.90 KB

AUTORE

Teemo92

PUBBLICATO

+1 anno fa


DESCRIZIONE DISPENSA

In questa dispensa di Matematica a cura del professore A. Bellen si parla di equazioni non lineari. In particolare si trattano i seguenti argomenti:
- Problemi equivalenti di punto fisso;
- Equazioni scalari;
- Il metodo di Newton e le sue varianti;
- Variante del metodo di Newton per radici multiple;
- Il metodo di Steffensen;
- Il metodo delle secanti;
- Metodo di Newton-Raphson;
- Commenti e varianti al metodi di Newton-Raphson;
- Metodo dell'omotopia.


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 - Approssimazione delle funzioni
Dispensa
Dispensa di Matematica - Sistemi lineari
Dispensa
Dispensa di Informatica - Spazi vettoriali normati
Dispensa