Equazioni e sistemi
non lineari
a.a. 2010/2011
1
Equazioni non lineari
una funzione f : R  R consideriamo il problema di determinare i valori x
tali che
 Data
f (x)  0
Tali valori sono solitamente chiamati zeri o radici della funzione f.
Esempi:
Equazioni algebriche: Pn (x ) 
x  4 sin(x)  0,

n
a x
k 0
k
k
0
ex  x2 ,
x  log(x)  3
In generale non sono disponibili formule esplicite per la determinazione delle
radici di una funzione (per esempio equazioni algebriche)
metodi iterativi
2
Metodi iterativi



Tecniche che consentono di approssimare le soluzioni con un prestabilito
grado di precisione
(0)
A partire da una approssimazione iniziale x si costruisce una successione x(1), x(2),
tale che, sotto opportune ipotesi, risulta convergere alla radice cercata.
E’ importante tener presente tre questioni fondamentali
1. Velocità di convergenza
x(1), x(2) ,
Definizione: data una successione
convergente ad un limite α, si
( n)
( n)
ponga e  x   se esistono due numeri reali p  1 e C  0 tali che sia
lim
n 

e(n 1)
( n)
e
p
C
si dice che la successione ha ordine di convergenza p e fattore di
convergenza C.
Per p=1 e p=2 la convergenza si dice anche lineare e quadratica. Nel caso p=1
si ha necessariamente C<1.
3
Metodi iterativi 2
2. Scelta del valore di innesco. x (0)
Un metodo converge localmente ad α se la
convergenza della successione
(0)
dipende in modo critico dalla vicinanza dix ad α. Il procedimento è
(0)
globalmente convergente quando la convergenza non dipende da quanto x è
vicino ad α.
• Per i metodi a convergenza locale la scelta del punto di innesco è cruciale.
3. Criteri di arresto. Chiaramente non è possibile generare infinite iterate della
successione x(k ) . Il procedimento dovrebbe arrestarsi quando
erel 

x (k )  

 toll
e(k ) . Una
Non disponendo della soluzione è necessario procurarsi
una
stima
di
possibile strategia è quella di approssimare e(k ) con x (k 1)  x (k ) . Si ottiene
il criterio relativo
( k 1)
(k )
x
x
x
( k 1)
 toll
Quando x (k 1) è molto piccolo tale criterio risulta troppo stringente ed è più
opportuno usare un criterio di arresto assoluto dato da
x (k 1)  x (k )  toll
4
Metodi iterativi 3
 Fondendo i due criteri si ottiene il seguente Criterio di arresto misto
x (k 1)  x (k )  tollR x (k 1)  toll A
Dove tollR e toll A sono rispettivamente la tolleranza relativa ed assoluta.
 Automaticamente il criterio sarà di tipo assoluto quando x (k ) è molto piccolo
e di tipo relativo nei restanti casi.
(k )
 Si può vedere che x (k 1)  x (k ) è asintoticamente una buona stima di e
nel caso di convergenza quadratica o superlineare, mentre nel caso di
convergenza lineare l’approssimazione sarà tanto migliore quanto la
costante C è vicina a zero.
5
Metodo di bisezione


Il metodo di bisezione è il metodo iterativo più semplice per approssimare gli zeri
reali di una funzione.
Ipotesi: 1) f(x) continua nell’intervallo [a,b]
2) f(a) f(b)<0
per il teorema degli zeri ammette almeno una soluzione α di f(x)=0, in (a,b).
 Si procede suddividendo ad ogni passo l’intervallo [a,b] a metà e determinando in
quale dei due sottointervalli si trova la soluzione, dimezzando cosi’ l’ampiezza
dell’intervallo che contiene α.
ALGORITMO:
1. Si pone a1  a, b1  b
2. Per i=1,2,….,nmax si calcolano ci  ai  bi e f(ci )
2
1. Se f (ci )  f (ai )  0 si pone ai 1  ci ; bi 1  bi
2. Altrimenti se f (ci )  f (ai )  0 si pone ai 1  ai ; bi 1  ci
3. altrimenti f (ci )  0, si ha   ci
3. Il procedimento viene arrestato se per un indice i risulta
f (ci )  
bi  ai  
e /o
6
Ampiezza dell’intervallo ed errore


Per costruzione ad ogni passo l’ampiezza dell’intervallo e’ dimezzata, dopo n passi
arriviamo all’intervallo an , bn  di ampiezza
b a
b  an 1 bn 2  an 2
bn  an  n 1

 ...  0 n 0
2
2
2
2
an  bn
Se come stima di α prendiamo cn 
abbiamo
2
en    cn  en 

Se poniamo
b0  a0
  otteniamo n da
n 1
2
2n 1 
b0  a0


b0  a0
2n 1
 b  a0 
n  log2  0
1

 

 Il metodo di bisezione converge sempre alla soluzione con la sola ipotesi che f sia
continua nell’intervallo [a,b]
 La convergenza è però lenta e questo costituisce il limite del metodo. Una spiegazione
può essere ricercata nel fatto che non si tiene conto dei valori della funzione ma
soltanto dei segni. Geometricamente il metodo costruisce ad ogni passo
l’approssimazione della radice calcolando l’intersezione con le ascisse della retta
passante per i punti
(ai , sgn(f (ai )), (bi , sgn(f (bi ))
7
Metodo della regula falsi

Un modo naturale per migliorare il metodo di bisezione è quello di considerare
anche i valori che la funzione assume negli estremi dell’intervallo e prendere come
nuova approssimazione della soluzione l’intersezione delle ascisse con la retta
passante per
(ak , f (ak )), (bk , f (bk ))

Il metodo metodo risultante è noto come metodo regula falsi o della falsa posizione
1.
2.
Dato [a0 , b0 ] tale che f (a0 )  f (b0 )  0
Finchè non sia verificato un criterio di arresto, poni wk  (f (bk ) ak  f (ak )bk ) /(f (bk )  f (ak ))
1.
2.
3.
3.
Se f (ak )  f (wk )  0, allora ak 1  ak , bk 1  wk
Altrimenti ak 1  wk , bk 1  bk
k=k+1
  wk
 Il metodo genera una successione di intervalli decrescenti in cui è
contenuta la radice
 è più veloce rispetto al metodi di bisezione, anche se in generale
[ak , bk ] 0, per k  
pertanto il criterio di arresto basato sull’ampiezza dell’intervallo non
è applicabile.
 La scelta dell’intervallo comporta una convergenza globale
 Si può dimostrare che la velocità di convergenza è lineare:
8
Metodo delle secanti



Una variante della regula falsi è il metodo delle secanti in cui sono richieste due
approssimazioni iniziali senza alcun’ altra condizione e senza la necessità di
controllare il segno di f(x)
( 1)
(0)
Assegnati due valori iniziali x , x
si costruisce la successione
x(k )  x(k 1)
(k 1)
(k )
x
x 
f (x (k ) )
k 0
(k )
( k 1)
f (x )  f (x
)
La convergenza del metodo è garantita se le approssimazioni iniziali sono
abbastanza vicine alla radice α: convergenza locale.
Vale il seguente risultato:
f (x)  C 2(I ) , essendo I un intorno
opportuno della radice, e si assuma f ''( )  0
( 1)
(0)
Allora se i dati iniziali x , x
sono scelti in I
Teorema: Sia
sufficientemente vicini ad α, la successione converge
ad α in modo superlineare, con ordine
p
(1  5)
 1.63
2
9
Metodo di Newton


Se si vuole migliorare ancora di più la velocità di convergenza è necessario
utilizzare più informazioni della funzione. Nel caso in cui essa sia derivabile si
può considerare anche la sua derivata f’(x).
Sviluppando f in serie di Taylor in un intorno di α ed arrestando lo sviluppo al
prim’ordine si ottiene una versione linearizzata del problema f(x)=0.
f ( )  0  f (x)  (  x) f '( )

  (, x)
Assumendo quindi f’(α)≠0 (radice semplice) ed assegnato un valore iniziale x (0) si
ottiene il metodo di Newton
x
(k 1)
x
(k )
f (x (k ) )

f '(x(k ) )
k 0
 Geometricamente si prende come nuova
approssimazione l’intersezione delle ascisse con la retta
tangente in (x(k ), f (x(k ) ))
 Alla k-esima iterazione questo metodo richiede due
(k )
(k )
valutazioni funzionali f (x ) e f '(x ). L’aumento del
costo computazionale è compensato dal fatto che la
convergenza (locale) è di ordine superiore al primo. In
generale è quadratica
10
Metodi di iterazione funzionale
 La ricerca degli zeri di una funzione f è ricondotta allo studio dei punti fissi di
un’opportuna funzione g f ( )  0    g( )
 La successione delle approssimazioni sarà definita come x(k 1)  g(x(k ) )
 La funzione di iterazione g non è unica e può essere costruita nei modi più
diversi, ma non tutti daranno luogo a strumenti efficienti.
 Bisogna studiare sotto quali condizioni la successione delle iterate appartenga
sempre al dominio di f e sia convergente ad α.
Teorema: Data la successione x(k 1)  g(x(k ) ) per k  0 e x(0) assegnato.
Supponiamo che la funzione g soddisfi le seguenti condizioni
(i) g: [a,b] →[a,b]
1
(ii) g  C [a, b]
(iii)  k  1 : g '(x)  k  x  [a, b]
Allora g ha un unico punto fisso α in [a,b] e la successione delle iterate da essa generate
converge ad α, per ogni scelta del punto iniziale in [a,b]. Inoltre
x (k 1)  
lim (k )
 g '( )
k  x

dim. L’ipotesi (i) e la continuità di g (implicita in (ii)) garantiscono che g abbia almeno un
punto fisso in [a,b]. L’hp (iii) assicura che g è una contrazione per cui il punto fisso è unico
11
(si dimostra per assurdo).
Metodi di iterazione funzionale 2
Per dimostrare che la successione converge si considera
x(k 1)    g(x(k ) )  g( ) applicando il teorema della media
 g '( (k ) ) ( x (k )   )
dove  (k )  ( , x (k ) )
 k 1 per ( iii )
 x (k 1)    k x (k )    k k 1 x (0)  
per cui
lim x (k 1)    0
k 
Inoltre dalla continuità di g’ si ha
lim
k 
x(k 1)  
x (k )  
 lim g '( (k ) )  g '( )
12
Convergenza

Risultato importante teoricamente, ma nella pratica è difficile stabilire a priori
l’intervallo [a,b] in cui sono soddisfatte le ipotesi.
Teorema (Otrowski): Sia α un punto fisso di g  C 1[   ,    ]. Se  x(0)  [   ,    ],
g '(x)  1,  x  [  ,   ],
allora
la successione delle iterate generata da g è tale che
(k )
x

(unico punto fisso)
(a)
(k )
(b) x  [   ,    ],
 La convergenza può esserci in insiemi molto più grandi di quelli in cui
g '( )  1
(condizione sufficiente, convergenza locale)
1  g '( )  0
convergenza alternata
0  g '( )  1
convergenza monotona
13
Ordine di convergenza

Per i metodi di iterazione funzionale è possibile anche dare una relazione
tra ordine del metodo e molteplicità di α rispetto a g’
Teorema: Sia   I (opportuno intervallo) punto fisso di g  C p[I ], con p  2


(k )
(i )
(0)
Se per un punto x  I la successione x
è convergente e se g ( )  0
per i=1,....p-1 e g( p)( )  0 allora il metodo ha ordine di convergenza p e
risulta
x (k 1)  
g( p)( )
lim
k 

x
(k )

p

p!
A parità di ordine di convergenza p, quanto più piccola risulterà la
( p)
quantità g ( ) / p ! tanto più veloce sarà la convergenza delle iterate ad
α
14
Convergenza metodo di Newton
 Il metodo di Newton può essere visto come un metodo di iterazione funzionale
con la funzione g data da g(x )  x  f (x )
f '(x)
f ''(x) f (x)
2
 g '( )  0
 Osservando che se f  C e f '( )  0 : g '(x) 
(f '(x ))2
il metodo è localmente sempre convergente
 La convergenza è quadratica per radici semplici e si riduce a lineare per radici
multiple.
 Risultati di convergenza globale:
Teorema: Sia f  C 2[     ] tale che
(i) f (x) f ''(x)  0 in (    ]
(ii) f '(x)  0 in (     )
  x0  (     ]

la successione originata dal metodo di Newton DECRESCE
monotonicamente ad α.
Per gli intorni sinistri [α+ρ, α) si ottiene una successione che converge in modo monotono
CRESCENTE ad α.
15
Sistemi non lineari
 La maggior parte dei metodi considerati per il caso monodimensionale
possono venire generalizzati con successo al caso di sistemi. Tra essi non ci
possono essere quei metodi che considerano, ad ogni iterazione, una scelta
opportuna di un intervallo in cui era compresa la radice (bisezione, regula
falsi).
n
n
*
n
*
Problema: data F : R  R , trovare x  R tale che F(x )  0
 Tra i metodi il più usato è l’estensione vettoriale del metodo di Newton
x
( k 1)
x
(k )
1
  JF (x(k ) ) F(x(k ) )
dove JF (x) indica la matrice Jacobiana
 JF (x)i , j
 Fi


(x) 
 x

 j

 Dal punto di vista implementativo il metodo può essere riscritto considerando,
ad ogni iterazione, due sottopassi
Risolvere
JF (x(k ) ) δx(k )  F(x(k ) )
Calcolare x(k 1)  x(k )  δx(k )
(k )
J
(
x
)
 Ad ogni passo k si deve risolvere un sistema lineare con matrice F
16
 Per quanto riguarda la convergenza si può dimostrare (risultato dovuto a
Kantorovich) che se la matrice Jacobiana è non singolare, partendo da
una approssimazione iniziale x(0) sufficientemente buona, il processo
*
iterativo genera una successione convergente alla radice x
 L’ordine di convergenza è quadratico
 La sensibilità del metodo alla scelta del punto iniziale è molto più
marcata che nel caso scalare
 Il costo richiesto ad ogni passo per la risoluzione del sistema lineare è
molto elevato per n grande
 La matrice Jacobiana può essere malcondizionata dando luogo a
soluzioni non necessariamente accurate.
VARIANTI METODO DI NEWTON
17
Varianti metodo di Newton



Valutazione ciclica della matrice Jacobiana: si mantiene la stessa
matrice Jacobiana per un certo numero p>1 di iterazioni: metodo di
Newton modificato. L’aumento di efficienza è pagato da una velocità di
convergenza più bassa.
Risoluzione inesatta dei sistemi lineari: si risolvono i sistemi lineari con
un metodo iterativo (facendone solo alcuni passi); per esempio Jacobi,
Gauss-Seidel o Gauss-Seidel con rilassamento: metodi di Newton
inesatti.
Approssimazione Jacobiana con rapporti incrementali: ad ogni passo si
considera al posto della matrice Jacobiana una sua approssimazione
mediante rapporti incrementali n-dimensionali (come vantaggio non si
deve calcolare le n2 derivate parziali costituenti J(x)
(k )
( Jh ) j 
F(x(k )  h(j k )e j )  F(x(k ) )
(k )
j
h
,
k  0
18
Metodi di iterazione funzionale

Come nel caso monodimensionale il problema può essere riformulato in
modo da trovale la soluzione come punto fisso di una opportuna funzione
di iterazione
Data G : Rn  Rn , trovare x*  Rn tale che G(x* )  x*

Si considerano metodi iterativi della forma
x(k 1)  G(x(k ) )
Teorema: Se x*è punto fisso di G, condizione sufficiente per la convergenza alla
radice , del metodo iterativo è che esistano due numeri positivi K e ρ, con K<1, tali
che si abbia
*
G(x)  K ,

 x  D  x : x  x


(0)
*
purché x sia scelto in D ; in tal caso x è l’unico punto fisso di G in D
19
 Per quanto riguarda l’ordine di convergenza, il teorema
monodimensionale non può essere esteso direttamente, tuttavia se
esistono continue le derivate seconde delle componenti di G, si può
dimostrare che condizione sufficiente perché il metodo (se converge al
punto fisso) converga linearmente è che sia
G(x* )  0
 Se G(x* )  0 la convergenza è almeno quadratica ed è esattamente
quadratica se risulta non nulla almeno una delle matrici hessiane
 2Gi

2

x
1

Hi (x* )  
 2
  Gi
 x x
 n 1
2Gi
x1 x2
2Gi
xnx2
2Gi 

x1 xn 


2
 Gi 
xn2 x  x*
20