Corso di Laurea in Ingegneria Informatica Analisi Numerica

Corso di Laurea in Ingegneria Informatica Analisi Numerica

Lucio Demeio

Dipartimento di Scienze Matematiche

1

Equazioni Non Lineari

Problema: trovare le soluzioni di un’equazione del tipo

f (x) = 0

Problema: trovare le soluzioni di un’equazione del tipo f (x) = 0

Esempio

Problema: trovare le soluzioni di un’equazione del tipo f (x) = 0

Esempio

sin x − a x = 0

e

= x

Problema: trovare le soluzioni di un’equazione del tipo f (x) = 0

Esempio

sin x − a x = 0 e

= x

Out[54]=

-3 -2 -1 1 2 3

-0.5 0.5 1.0

0.5 1.0 1.5 2.0

Problema: trovare le soluzioni di un’equazione del tipo f (x) = 0

Esempio

sin x − a x = 0 e

= x

Out[54]=

-3 -2 -1 1 2 3

-1.0 -0.5 0.5 1.0

0.0 0.5 1.0 1.5 2.0

0.5 1.0 1.5 2.0

Mathematica file EqNonLin1.nb

Bisezione

Bisezione

Dal teorema degli zeri, data f : [a, b] → R continua, se

f (a) f (b) < 0 allora ∃ c tale che f (c) = 0.

Bisezione

Dal teorema degli zeri, data f : [a, b] → R continua, se f (a) f (b) < 0 allora ∃ c tale che f (c) = 0.

c b

a f(a)>0

f(b)<0 f(x)

x

Bisezione

Dal teorema degli zeri, data f : [a, b] → R continua, se f (a) f (b) < 0 allora ∃ c tale che f (c) = 0.

c b

a f(a)>0

f(b)<0 f(x)

x c₀

Bisezione

Dal teorema degli zeri, data f : [a, b] → R continua, se f (a) f (b) < 0 allora ∃ c tale che f (c) = 0.

c b

a f(a)>0

f(b)<0 f(x)

x c₀

Costruiamo tre successioni, {a

}, {b

} e {c

}: siano

a

= a b

= b c

= a + b

2

Bisezione

Bisezione

Nel nostro esempio, f (a

) f (c

) < 0, quindi il teorema degli zeri si applica nuovamente all’intervallo [a

, c

]. Siano allora

a

= a

b

= c

c

= a

+ b

2

Bisezione

Nel nostro esempio, f (a

) f (c

) < 0, quindi il teorema degli zeri si applica nuovamente all’intervallo [a

, c

]. Siano allora

a

= a

b

= c

c

= a

+ b

2

... e cos`ı via:

se f (a

) f (c

) < 0 allora a

= a

e b

= c

;

se f (a

) f (c

) > 0 allora a

= c

e b

= b

e c

= (a

+ b

)/2.

Bisezione

Nel nostro esempio, f (a

) f (c

) < 0, quindi il teorema degli zeri si applica nuovamente all’intervallo [a

, c

]. Siano allora

a

= a

b

= c

c

= a

+ b

2

... e cos`ı via:

se f (a

) f (c

) < 0 allora a

= a

e b

= c

; se f (a

) f (c

) > 0 allora a

= c

e b

= b

e c

= (a

+ b

)/2.

La successione {c

} converge a c (lo sappiamo dal teorema degli

zeri), quindi l’algoritmo basato sul metodo di bisezione

fornisce una successione che converge alla soluzione.

Bisezione

Nel nostro esempio, f (a

) f (c

) < 0, quindi il teorema degli zeri si applica nuovamente all’intervallo [a

, c

]. Siano allora

a

= a

b

= c

c

= a

+ b

2

... e cos`ı via:

se f (a

) f (c

) < 0 allora a

= a

e b

= c

; se f (a

) f (c

) > 0 allora a

= c

e b

= b

e c

= (a

+ b

)/2.

La successione {c

} converge a c (lo sappiamo dal teorema degli zeri), quindi l’algoritmo basato sul metodo di bisezione fornisce una successione che converge alla soluzione.

In pratica, l’algoritmo viene fermato dopo N passi (o iterazioni) ed otteniamo un’approssimazione per lo zero della funzione:

c ≈ c

. Come scegliere N (criterio di arresto)?

Criterio di arresto

Criterio di arresto

Varie possibilit`a:

Criterio di arresto Varie possibilit`a:

Fissare un massimo numero di iterazioni, N ≤ N

(`e di solito considerato un fallimento - legato a ragioni di costo

computazionale);

Criterio di arresto Varie possibilit`a:

Fissare un massimo numero di iterazioni, N ≤ N

(`e di solito considerato un fallimento - legato a ragioni di costo

computazionale);

Fissare una tolleranza η << 1 su c: |c

− c| ≤ η (ovviamente c

non lo conosciamo ... vedi pi` u avanti) - `e il caso pi` u frequente

nella prassi - la chiameremo tolleranza assoluta

Criterio di arresto Varie possibilit`a:

Fissare un massimo numero di iterazioni, N ≤ N

(`e di solito considerato un fallimento - legato a ragioni di costo

computazionale);

Fissare una tolleranza η << 1 su c: |c

− c| ≤ η (ovviamente c non lo conosciamo ... vedi pi` u avanti) - `e il caso pi` u frequente nella prassi - la chiameremo tolleranza assoluta

Fissare una tolleranza relativa η << 1 su c: |(c

− c)/c| ≤ η

(anche qui c non lo conosciamo ...);

Criterio di arresto Varie possibilit`a:

Fissare un massimo numero di iterazioni, N ≤ N

(`e di solito considerato un fallimento - legato a ragioni di costo

computazionale);

Fissare una tolleranza η << 1 su c: |c

− c| ≤ η (ovviamente c non lo conosciamo ... vedi pi` u avanti) - `e il caso pi` u frequente nella prassi - la chiameremo tolleranza assoluta

Fissare una tolleranza relativa η << 1 su c: |(c

− c)/c| ≤ η (anche qui c non lo conosciamo ...);

Fissare una tolleranza η << 1 su f (c): |f (c

)| ≤ η

Criterio di arresto Varie possibilit`a:

Fissare un massimo numero di iterazioni, N ≤ N

(`e di solito considerato un fallimento - legato a ragioni di costo

computazionale);

Fissare una tolleranza η << 1 su c: |c

− c| ≤ η (ovviamente c non lo conosciamo ... vedi pi` u avanti) - `e il caso pi` u frequente nella prassi - la chiameremo tolleranza assoluta

Fissare una tolleranza relativa η << 1 su c: |(c

− c)/c| ≤ η (anche qui c non lo conosciamo ...);

Fissare una tolleranza η << 1 su f (c): |f (c

)| ≤ η

Quale errore commettiamo nei vari casi?

Analisi dell’errore nel caso |c

− c| ≤ η

Analisi dell’errore nel caso |c

− c| ≤ η

Ricordiamo che c

∈ [a

, b

] e c ∈ [a

, b

];

Analisi dell’errore nel caso |c

− c| ≤ η Ricordiamo che c

∈ [a

, b

] e c ∈ [a

, b

];

c

= (a

+ b

)/2 e |b

− a

| = (b − a)/2

;

Analisi dell’errore nel caso |c

− c| ≤ η Ricordiamo che c

∈ [a

, b

] e c ∈ [a

, b

];

c

= (a

+ b

)/2 e |b

− a

| = (b − a)/2

;

quindi |c

− c| ≤ (b − a)/2

;

Analisi dell’errore nel caso |c

− c| ≤ η Ricordiamo che c

∈ [a

, b

] e c ∈ [a

, b

];

c

= (a

+ b

)/2 e |b

− a

| = (b − a)/2

; quindi |c

− c| ≤ (b − a)/2

;

ci fermiamo quando (b − a)/2

≤ η.

Analisi dell’errore nel caso |c

− c| ≤ η Ricordiamo che c

∈ [a

, b

] e c ∈ [a

, b

];

c

= (a

+ b

)/2 e |b

− a

| = (b − a)/2

; quindi |c

− c| ≤ (b − a)/2

;

ci fermiamo quando (b − a)/2

≤ η.

dunque N ≈ log

(b − a)/η.

a b x

c

a

b

c

Analisi dell’errore nel caso |c

− c| ≤ η Ricordiamo che c

∈ [a

, b

] e c ∈ [a

, b

];

c

= (a

+ b

)/2 e |b

− a

| = (b − a)/2

; quindi |c

− c| ≤ (b − a)/2

;

ci fermiamo quando (b − a)/2

≤ η.

dunque N ≈ log

(b − a)/η.

a b x

c

a

b

c

Nel caso |(c

− c)/c| ≤ η ci fermiamo quando (b − a)/(|c

|2

) ≤ η

Ordine di convergenza

Ordine di convergenza

Nel caso |c

− c| ≤ (b − a)/2

abbiamo che α

= c

e β

= 1/2

,

con K = b − a.

Ordine di convergenza

Nel caso |c

− c| ≤ (b − a)/2

abbiamo che α

= c

e β

= 1/2

, con K = b − a.

Quindi c

converge a c con tasso di convergenza O(1/2

), ovvero

c

= c + O  1 2



Un punto x = c si dice punto fisso per una funzione g(x) se g(c) = c,

cio`e una soluzione dell’equazione g(x) = x.

Un punto x = c si dice punto fisso per una funzione g(x) se g(c) = c, cio`e una soluzione dell’equazione g(x) = x.

g(x)

c x y

y=x

Un punto x = c si dice punto fisso per una funzione g(x) se g(c) = c, cio`e una soluzione dell’equazione g(x) = x.

g(x)

c x y

y=x

Punto fisso

Un punto x = c si dice punto fisso per una funzione g(x) se g(c) = c, cio`e una soluzione dell’equazione g(x) = x.

g(x)

c x y

y=x

Punto fisso

Un problema del tipo f (x) = 0 si pu` o sempre trasformare in un

equivalente problema di punto fisso; esiste cio`e sempre una

funzione g(x) per cui l’equazione f (x) = 0 `e equivalente

all’equazione g(x) = x.

Un punto x = c si dice punto fisso per una funzione g(x) se g(c) = c, cio`e una soluzione dell’equazione g(x) = x.

g(x)

c x y

y=x

Punto fisso

Un problema del tipo f (x) = 0 si pu` o sempre trasformare in un equivalente problema di punto fisso; esiste cio`e sempre una funzione g(x) per cui l’equazione f (x) = 0 `e equivalente all’equazione g(x) = x.

Ci sono diversi modi per definire una funzione g(x) a tale scopo:

ad esempio g(x) = x − f (x) (quello pi` u semplice) ma anche

g(x) = x + a f (x) e molti altri.

Data una funzione g(x), definita su un intervallo [a, b], quando ha un

punto fisso e quando questo `e unico? E come si costruisce?

Data una funzione g(x), definita su un intervallo [a, b], quando ha un punto fisso e quando questo `e unico? E come si costruisce?

Theorem

Se g `e una funzione continua su [a, b] e g(x) ∈ [a, b] ∀x ∈ [a, b], allora g ha un punto fisso in [a, b]; inoltre, se esiste k con 0 < k < 1 tale che

|g

(x)| < k ∀x ∈ [a, b], il punto fisso `e unico.

Data una funzione g(x), definita su un intervallo [a, b], quando ha un punto fisso e quando questo `e unico? E come si costruisce?

Theorem

Se g `e una funzione continua su [a, b] e g(x) ∈ [a, b] ∀x ∈ [a, b], allora g ha un punto fisso in [a, b]; inoltre, se esiste k con 0 < k < 1 tale che

|g

(x)| < k ∀x ∈ [a, b], il punto fisso `e unico.

Proof.

...

Data una funzione g(x), definita su un intervallo [a, b], quando ha un punto fisso e quando questo `e unico? E come si costruisce?

Theorem

Se g `e una funzione continua su [a, b] e g(x) ∈ [a, b] ∀x ∈ [a, b], allora g ha un punto fisso in [a, b]; inoltre, se esiste k con 0 < k < 1 tale che

|g

(x)| < k ∀x ∈ [a, b], il punto fisso `e unico.

Proof.

...

g(x) u(x)

h(x)

x a

a y

b b

Theorem (Teorema del punto fisso)

Sia g(x) una funzione che soddisfa le condizioni del teorema

precedente. Allora, ∀x

∈ [a, b] la successione definita da x

= g(x

)

converge al punto fisso x = c (unico !!) della funzione g.

Theorem (Teorema del punto fisso)

Sia g(x) una funzione che soddisfa le condizioni del teorema

precedente. Allora, ∀x

∈ [a, b] la successione definita da x

= g(x

) converge al punto fisso x = c (unico !!) della funzione g.

g(x)

a x a

y

b c b

x₀ x₁ x₂

Proof.

Per le condizioni del teorema precedente, x

∈ [a, b] ∀n. Inoltre, per il teorema di Lagrange,

|x

− c| = |g(x

) − g(c)| = |g

(ξ

)||x

− c| ≤ k|x

− c|, con ξ

∈ [a, b]. Per induzione, allora abbiamo che

|x

− c| ≤ k

|x

− c|. Siccome k < 1, si ha che lim

k

= 0 e

quindi lim

|x

− c| ≤ lim

k

|x

− c| = 0. Quindi {x

}

converge a c.

Theorem

Se g soddisfa le ipotesi del teorema del punto fisso, allora l’errore che si commette approssimando c con x

soddisfa alle limitazioni

|x

− c| ≤ k

max{x

− a, b − x

}

|x

− c| ≤ k

1 − k |x

− x

|

Theorem

Se g soddisfa le ipotesi del teorema del punto fisso, allora l’errore che si commette approssimando c con x

soddisfa alle limitazioni

|x

− c| ≤ k

max{x

− a, b − x

}

|x

− c| ≤ k

1 − k |x

− x

|

Proof.

...

Newton-Raphson

c f(x)

x₀ x

Newton-Raphson

c f(x)

x₀ x₁ x

Newton-Raphson

c f(x)

x₀ x₁ x₂ x

Newton-Raphson

c f(x)

x₀ x₁ x₂ x

Newton-Raphson

Tangente ad f (x) per (x

, f (x

)): y = f (x

) + f

(x

) (x − x

);

c f(x)

x₀ x₁ x₂ x

Newton-Raphson

Tangente ad f (x) per (x

, f (x

)): y = f (x

) + f

(x

) (x − x

);

l’intersezione della tangente con l’asse delle x fornisce

x

= x

− f (x

)/f

(x

);

c f(x)

x₀ x₁ x₂ x

Newton-Raphson

Tangente ad f (x) per (x

, f (x

)): y = f (x

) + f

(x

) (x − x

);

l’intersezione della tangente con l’asse delle x fornisce x

= x

− f (x

)/f

(x

);

... e cos`ı via:

x

= x

− f (x

)

f

(x

)

Quando converge Newton-Raphson?

Quando converge Newton-Raphson?

Theorem

Sia f (x) di classe C

([a, b]). Se esiste c ∈ [a, b] tale che f (c) = 0 ed

f

(c) 6= 0, allora esiste un δ > 0 tale che il metodo di Newton genera

una successione x

, con x

∈ (c − δ, c + δ), e con x

→ c per n → ∞.

Quando converge Newton-Raphson?

Theorem

Sia f (x) di classe C

([a, b]). Se esiste c ∈ [a, b] tale che f (c) = 0 ed f

(c) 6= 0, allora esiste un δ > 0 tale che il metodo di Newton genera una successione x

, con x

∈ (c − δ, c + δ), e con x

→ c per n → ∞.

Intuitivamente:

Quando converge Newton-Raphson?

Theorem

Sia f (x) di classe C

([a, b]). Se esiste c ∈ [a, b] tale che f (c) = 0 ed f

(c) 6= 0, allora esiste un δ > 0 tale che il metodo di Newton genera una successione x

, con x

∈ (c − δ, c + δ), e con x

→ c per n → ∞.

Intuitivamente:

c f(x)

x₀ x₁ x₂ x

S I

c f(x)

x₀ x₁ x

x₂

N O

Proof.

Il metodo di Newton `e un problema di punto fisso per la funzione g(x) = x − f (x)/f

(x) Dobbiamo innanzitutto determinare un intervallo I(δ) = [c − δ, c + δ] che viene mappato in se stesso dalla funzione g e per il quale esiste una costante reale k, con 0 < k < 1, per cui |g

(x)| ≤ k ∀x ∈ I(δ). Sia 0 < k < 1 arbitrario. Essendo f

(c) 6= 0, esiste un I(δ

) ⊂ [a, b] tale che ∀x ∈ I(δ

) si ha f

(x) 6= 0. Quindi, g `e definita e continua su I(δ

), abbiamo g

(x) = f (x)f

(x)/[f

(x)]

ed essendo f ∈ C

([a, b]) `e anche g ∈ C

(I(δ

)). Notiamo che g

(c) = 0;

quindi, per la continuit` a di g

, esiste un δ > 0 tale che, ∀x ∈ I(δ) `e

|g

(x)| ≤ k. Resta da dimostrare che g mappa I(δ) in I(δ). Sia dunque

x ∈ I(δ); per il teorema di Lagrange, esiste ξ compreso tra x e c tale

che |g(x) − c| = |g(x) − g(c)| = |g

(ξ)| |x − c| ≤ k|x − c| < |x − c| < δ, e

quindi g(x) ∈ I(δ). Le ipotesi del teorema del punto fisso sono dunque

tutte soddisfatte e la successione x = g(x ) converge al punto fisso

Convergenza

Convergenza

In metodo di Newton converge rapidamente se la scelta iniziale

x

e’ abbastanza vicina allo zero x = c, in particolare se f (x) `e

monotona tra x

e c;

Convergenza

In metodo di Newton converge rapidamente se la scelta iniziale x

e’ abbastanza vicina allo zero x = c, in particolare se f (x) `e monotona tra x

e c;

dopo poche iterazioni gi`a si capisce se il metodo converge o se “va

a galline” (cio`e non converge);

Convergenza

In metodo di Newton converge rapidamente se la scelta iniziale x

e’ abbastanza vicina allo zero x = c, in particolare se f (x) `e monotona tra x

e c;

dopo poche iterazioni gi`a si capisce se il metodo converge o se “va a galline” (cio`e non converge);

uno svantaggio `e dato dalla necessit`a di conoscere la derivata

f

(x);

Convergenza

In metodo di Newton converge rapidamente se la scelta iniziale x

e’ abbastanza vicina allo zero x = c, in particolare se f (x) `e monotona tra x

e c;

dopo poche iterazioni gi`a si capisce se il metodo converge o se “va a galline” (cio`e non converge);

uno svantaggio `e dato dalla necessit`a di conoscere la derivata f

(x);

i criteri di arresto sono essenzialmente gli stessi del metodo di bisezione, solo che non abbiamo a disposizione un intervallo [a

, b

] come nell’altro caso; allora, la tolleranza (semplice o relativa) viene testata sulla differenza |x

− x

|; vale a dire che

|x

− x

| < η diventa il criterio di arresto (tolleranza semplice).

Theorem (Ordine di convergenza quadratico)

Sia f tale da obbedire alle condizioni del teorema sulla convergenza del

metodo di Newton-Raphson. Allora il metodo gode di ordine di

convergenza quadratico.

Theorem (Ordine di convergenza quadratico)

Sia f tale da obbedire alle condizioni del teorema sulla convergenza del metodo di Newton-Raphson. Allora il metodo gode di ordine di convergenza quadratico.

Proof.

Con riferimento a quanto visto in precedenza, siano {α

} e {β

} le successioni date da α

= x

− c e β

= (x

− c)

. Allora abbiamo

|α

| ≤ |β

|

. Infatti, con uno sviluppo di Taylor possiamo scrivere:

0 = f (c) = f (x

) + (c − x

) f

(x

) + (c − x

)

f

(ξ)/2 da cui (dividendo per f

(x

))

f (x

)/f

(x

) + (c − x

) = −(c − x

)

f

(ξ)/(2 f

(x

)) e, ricordando che x

= x

− f (x

)/f

(x

),

c − x

= (c − x

)

f

(ξ)/(2 f

(x

)) e quindi |α

| ≤ K |β

|

.