Metodo delle successive bisezioni

(1)

Francesca Mazzia

Dipartimento Interuniversitario di Matematica Universit` a di Bari

MATLAB:Metodi Numerici per zeri di funzioni.

Metodo delle successive bisezioni

Sappiamo che la procedura definita dal metodo delle bisezioni determina una sequenza di intervalli ciascuno dei quali ` e contenuto nel precedente

[a

n

, b

n

] ⊆ [a

ⁿ−1

, b

n−1

] ⊆ . . . ⊆ [a

¹

, b

1

] ⊆ [a

⁰

, b

0

];

il generico intervallo ha ampiezza pari alla met` a di quella dell’intervallo pre- cedentemente determinato e contiene lo zero α di f (x).

Generalizzando, la procedura costruisce la successione dei punti medi c

_n

= a

_n−1

+ b

_n−1

2 n ≥ 1

e se f (c

_n

) 6= 0, definisce i nuovi intervalli nel modo seguente

[a

_n

, b

_n

] =

(

[c

_n

, b

_n₋₁

] se f (c

_n

) f (b

_n₋₁

) < 0 [a

_n−1

, c

_n

] se f (a

_n−1

) f (c

_n

) < 0.

Vediamo come costruire una funzione Matlab che ci permette di risolvere il problema della ricerca degli zeri di una funzione mediante il metodo delle bisezioni:

Innanzitutto definiamo una funzione in un file Matlab che chiamiamo f1.m:

(2)

function y=f1(x) y=exp(x)-(2*x).^2;

Ora costruiamo la funzione bisezioni.m in cui viene implementato il metodo delle successive bisezioni:

% METODO DELLE SUCCESSIVE BISEZIONI

% PER LA SOLUZIONE DI EQUAZIONI NON LINEARI

%

% function [root,nit] = bisezioni(funz,a,b,tol,nmax)

%

% DATI DI INPUT:

% funz = stringa contenente il nome della funzione

% a,b = estremi dell’intervallo in cui si cerca la radice di funz

% tol = tolleranza

% nmax = numero massimo di iterate

%

% DATI DI OUTPUT:

% root = soluzione

% nit = numero di iterate

%

function [root,nit,errv] = bisezioni(funz,a,b,tol,nmax)

% L’istruzione feval ci permette di calcolare il valore della funzione

% in un punto.

fa = feval(funz,a);

fb = feval(funz,b);

if fa*fb > 0

error(’ERRORE: la funzione non cambia di segno agli estremi’) end

err = 1/eps;

nit = 0

(3)

while (err > tol) & (nit <= nmax) c = (a+b)*0.5;

fc = feval(funz,c);

if (fc*fa < 0) b = c;

fb = fc;

else a = c;

fa = fc;

end

nit = nit+1;

err = abs(b-a)/max(1,min([abs(a),abs(b)]));

errv(nit) = err;

end

root = c;

Eseguiamo la funzione:

>> a=-1;

>> b=0;

>> tol=1e-10;

>> nmax=100;

>> [root,nit]=bisezioni(’f1’,a,b,tol,nmax) root =

-4.0778e-01

nit = 36

Possiamo fare altri esempi:

(4)

>>

>> a=0;

>> b=1;

>> [root,nit]=bisezioni(’f1’,a,b,tol,nmax) root =

7.1481e-01

nit = 34

>> a=4;

>> b=4.5;

>> [root,nit]=bisezioni(’f1’,a,b,tol,nmax) root =

4.3066e+00

nit = 37

Ordine di convergenza

Il metodo delle bisezioni converge linearmente ad α ed ha costante asin- totica pari ad

¹₂

, risultando con ci` o molto lento.

Teorema. Se le successioni convergono con la stessa velocit` a, ovvero 0 < lim

n→∞

a

_n

− α b

_n

− α

< ∞, (1)

allora

n→∞

lim

b

n+1

− α b

_n

− α

= 1

2 .

(5)

In particolare applicando il metodo al calcolo degli zeri di una data fun- zione, si pu` o osservare che ad ogni iterata si guadagna una cifra binaria e quindi dopo 3.3 iterate circa si guadagner` a una cifra decimale esatta, essendo

3.3 ' log

2

10. Quindi tenendo conto della seguente relazione

|c

ⁿ

− α| ≈ c|c

ⁿ−1

− α|

possiamo valutare l’ordine di convergenza del metodo delle bisezioni nel seguente modo:

>> [root,nit,errv]=bisezioni(’f1’,a,b,tol,nmax) root =

-4.0778e-01

nit = 36

>> p=errv(2:nit)./errv(1:nit-1) .

p =

Columns 1 through 4

5.0000e-01 5.0000e-01 5.7143e-01 5.0000e-01 Columns 5 through 8

5.1852e-01 5.0943e-01 5.0476e-01 5.0239e-01

...

(6)

...

Columns 33 through 35

5.0000e-01 5.0000e-01 5.0000e-01

Il Metodo di Newton

Supponiamo che la funzione f (x) abbia derivata non nulla; la funzione iteratrice φ(x) = x − f(x)/f

⁰

(x) definisce il procedimento iterativo

x

_n+1

= x

_n

− f (x

_n

) f

⁰

(x

_n

) detto metodo di Newton .

Per costruire una funzione Matlab che ci permette di risolvere il proble- ma della ricerca degli zeri di una funzione mediante il metodo di Newton, innanzitutto definiamo una funzione in un file Matlab che chiamiamo f4.m, e poi definiamo anche la derivata prima di f4(x) nel file fj4.m:

function y=fj4(x)

y=tan(x) + 1/(1+x^2);

Ora costruiamo la funzione newt.m in cui viene implementato il metodo di Newton:

% METODO DI NEWTON PER LA SOLUZIONE DI EQUAZIONI NON LINEARI

%

% function [x0, nit, errv] = newt(funz,jfunz,x0,tol,nmax)

%

% DATI DI INPUT

% funz = stringa contenente il nome della funzione

% jfunz = stringa contentente il nome della derivata prima

% x0 = punto iniziale della successione

(7)

% tol = tolleranza

% nmax = numero massimo di iterate

%

% DATI DI OUTPUT

% x0 = soluzione

% nit = numero di iterate

% errv = vettore con l’errore stimato ad ogni iterata

%

function [x0, nit, errv] = newt(funz,jfunz,x0,tol,nmax)

% procedimento iterativo nit = 0;

err = 1/eps;

F = 1/eps;

while (err > tol) & ( nit <= nmax) & (norm(F) > tol) xk = x0;

JF = feval(jfunz,xk);

F = feval(funz,xk);

d = -JF\F;

x0 = xk + d;

err = norm(d)/max([1,min([norm(x0),norm(xk)])]);

nit = nit + 1;

disp([err nit]) errv(nit) = err;

end

>> x0=-1;

>> tol=1e-10;

>> nmax=100;

>> [root,nit,errv]=newt(’f1’,’fj1’,x0,tol,nmax)

4.3406e-01 1.0000e+00

(8)

1.4000e-01 2.0000e+00 1.7870e-02 3.0000e+00 2.9837e-04 4.0000e+00 8.3136e-08 5.0000e+00 6.4453e-15 6.0000e+00

root =

-4.0778e-01

nit = 6

errv =

4.3406e-01 1.4000e-01 1.7870e-02 2.9837e-04 8.3136e-08 6.4453e-15

Ora vediamo come possiamo costruire un formula che ci permette di valutare l’ordine di convergenza del metodo di Newton. Sappiamo che:

|x

ⁱ⁺¹

− x

ⁱ

| ≈ c|x

ⁱ

− x

ⁱ−1

|

^p

e

|x

i

− x

i−1

| ≈ c|x

i−1

− x

i−2

|

^p

Facendo il rapporto tra queste due relazioni e quindi il logaritmo di entrambi i membri otteniamo che:

log( |x

i+1

− x

i

|

|x

i

− x

i−1

| ) ≈ p ∗ log( |x

i

− x

i−1

|

|x

i−1

− x

i−2

| )

(9)

Quindi possiamo valutare l’ordine di convergenza del metodo di Newton con la seguente formula:

>> p=log2(errv(3:nit)./errv(2:nit-1))./log2(errv(2:nit-1)./errv(1:nit-2)) p =

1.8192e+00 1.9881e+00 2.0001e+00 2.0002e+00

ESERCIZIO:

Determinare gli altri zeri di f1 partendo dai punti iniziali x0 = 1 e x0 = 4.

Valutare l’ordine di convergenza del metodo.

Definire le funzioni f 2(x) = (x − 1)

³

e f 3(x) = exp(x

²

) − 1 con relative derivate prime, e determinarne gli zeri con il metodo di Newton. Usare diversi punti iniziali, e valutare la bonta’ dell’approssimazione ottenuta.

Scrivere un programma per il metodo della direzione costante con una semplice modifica di newt.m. Testarlo. Ricordiamo che nel metodo della direzione costante la funzione iteratrice ` e data da:

x

_n+1

= x

_n

− f (x

_n

) g

dove g rappresenta il valore della direzione costante.

Il metodo delle secanti

x

_n+1

= x

_n

− x

_n

− x

n−1

f (x

_n

) − f(x

n−1

) f (x

_n

)

≡ f (x

_n

)x

_n−1

− f(x

n−1

)x

_n

f (x

_n

) − f(x

n−1

) .

Questo procedimento iterativo non rientra nella classe dei procedimenti x

_n+1

= φ(x

_n

), ma il nuovo punto dipende da due punti precedenti, cio` e:

x

n+1

= φ(x

n−1

, x

n

).

e necessita, per poter partire, di due punti iniziali.

Vediamo come costruire una funzione Matlab che ci permette di risolvere

il problema della ricerca degli zeri di una funzione mediante il metodo delle

secanti. Chiameremo tale funzione secanti.m:

(10)

% METODO DELLE SECANTI PER LA SOLUZIONE DI EQUAZIONI NON LINEARI

%

% function [x0, nit, errv] = secanti(funz,x0,x1,tol,nmax)

%

% DATI DI INPUT

% funz = stringa contenente il nome della funzione

% x0 = punto iniziale della successione

% x1 = secondo punto iniziale

% tol = tolleranza

% nmax = numero massimo di iterate

%

% DATI DI OUTPUT

% x0 = soluzione

% nit = numero di iterate

% errv = vettore con l’errore stimato ad ogni iterata

%

function [x0, nit, errv] = secanti(funz,x0,x1,tol,nmax)

% procedimento iterativo nit = 0;

err = 1/eps;

F0 = feval(funz,x0);

while (err > tol) & ( nit <= nmax) & (norm(F0) > tol) xk = x1;

x1 = x0;

F1 = F0;

F0 = feval(funz,xk);

x0 = xk - ((xk-x1)/(F0-F1))*F0;

err = norm(xk-x0)/max([1,min([norm(x0),norm(xk)])]

nit = nit + 1;

disp([err nit]) errv(nit) = err;

end

(11)

Ora eseguiamo la funzione:

>> x0=0;

>> x1=x0-f1(x0)/fj1(x0) x1 =

-1

>> tol=1e-10;

>> namx=100;

>> [root,nit,errv]=secanti(’f1’,x0,x1,tol,nmax) 7.8412e-01 1.0000e+00

4.6606e-02 2.0000e+00 2.7549e-01 3.0000e+00 .

. . . . . .

7.2880e-09 3.5000e+01 4.5764e-07 3.6000e+01 2.3137e-11 3.7000e+01

root =

-4.0778e-01

(12)