03.1 Metodo di Bisezione

3.1 Il metodo di Bisezione

Il metodo di bisezione è un metodo numerico che consiste nel dimezzare di volta in volta l'Intervallo di separazione e usare il punto medio di tale intervallo come approssimazione della soluzione $ξ$ .
Consente di costruire una successione { $x_{k}$ } di approssimazioni di $ξ$ , ottenute assumendo $x_{k}$ come punto medio di un intervallo $[a_{k - 1}, b_{k - 1}]$ con $k \in N^{+}$ .

☑️ Ipotesi

ipotesi

$I = [a, b]$ Intervallo di separazione
$f (x) \in C^{0} [a, b]$
$f (a) \cdot f (b) < 0$

Algoritmo

Individuato unIntervallo di separazione $[a_{0}, b_{0}]$ ne calcolo il punto medio che chiamerò $x_{1}$ :

x_{1} = \frac{b_{0} + a_{0}}{2}

Ora controllo in quale tra gli intervalli $[a_{0}, x_{1}]$ e $[x_{1}, b_{0}]$ appartiene la soluzione $ξ$ , verificando che il prodotto $f (a_{k - 1}) \cdot f (x_{k})$ oppure il prodotto $f (b_{k - 1}) \cdot f (x_{k})$ sia negativo.

Una volta individuato l'intervallo, ripeto il procedimento usando quello come nuovo intervallo di separazione. Supponiamo ad esempio che la soluzione cada nell'intervallo $[a_{0}, x_{1}]$ , questo sarà proprio il nuovo intervallo di separazione $[a_{1}, b_{1}] = [a_{0}, x_{1}]$ .

Chiamo $x_{2}$ il punto medio tra $a_{1}$ e $b_{1}$ :

x_{2} = \frac{a_{1} + b_{1}}{2}

Continuando a ripetere questo processo, ammesso che il metodo converga, $x_{k}$ sarà man mano sempre più vicino alla soluzione $ξ$ .

Input: $a = a_{0}, b = b_{0}$ per $k = 1, 2, . . .$
- $x_{k} = \frac{b_{k - 1} - a_{k - 1}}{2}$
se:
- $f (a_{k - 1}) \cdot f (x_{k}) < 0 \Rightarrow [a_{k}, b_{k}] = [a_{k - 1}, x_{k}]$
- $f (b_{k - 1}) \cdot f (x_{k}) < 0 \Rightarrow [a_{k}, b_{k}] = [x_{k}, b_{k - 1}]$

Errori

Errore di troncamento

Nell'applicazione del metodo di bisezione, compiamo un Errore di troncamento dovuto quindi al numero di iterazioni che compiamo

Convergenza

Calcolo l'errore $e_{k}$ tenendo presente che esso dovrà per forza essere minore della metà dell'ampiezza dell'intervallo.
A sua volta l'ampiezza dell'intervallo $[a_{k - 1}, b_{k - 1}]$ sarà la metà dell'intervallo della iterazione predente $[a_{k - 2}, b_{k - 2}]$ e così via

\begin{aligned} | e_{k} | = | ξ - x_{k} | \leq & \frac{b_{k - 1} - a_{k - 1}}{2} \\ \leq \frac{1}{2} \frac{b_{k - 2} - a_{k - 2}}{2} \\ ⋮ \\ \leq \frac{1}{2^{k}} (b_{0} - a_{0}) \end{aligned}

\Rightarrow | e_{k} | = | ξ - x_{k} | \leq \frac{1}{2^{k}} (b_{0} - a_{0})

Converge?

lim_{k \to \infty} | e_{k} | = lim_{k \to \infty} | \frac{1}{2^{k}} (b_{0} - a_{0}) | = 0

Ordine di convergenza

ordine di convergenza

Il metodo di bisezione ha ordine di convergenza pari a 1:
$p = 1$

Dimostrazione:

Ricordo che:
$| e_{k + 1} | = \frac{b_{k} - a_{k}}{2} = \frac{1}{2} \frac{b_{k - 1} - a_{k - 1}}{2} = \frac{b_{k - 1} - a_{k - 1}}{2^{2}}$
e che:
$| e_{k} | = \frac{b_{k - 1} - a_{k - 1}}{2}$
per cui
$\frac{| e_{k + 1} |}{| e_{k} |^{p}} \approx \frac{b_{k - 1} - a_{k - 1}}{2^{2}} \cdot \frac{2}{b_{k - 1} - a_{k - 1}} = \frac{1}{2}$
con $p = 1$ .

Stima iterazioni necessarie

Per ottenere l'approssimazione della soluzione con una tolleranza scelta $ε$ sono necessarie almeno un certo numero $k$ di iterazioni. Questo numero può essere stimato a partire dalla relazione:

| e_{k} | = \frac{1}{2^{k}} (b - a) \leq ε

Risolvendo per $k$ otteniamo infatti:

\begin{aligned} 2^{k} & \geq \frac{b - a}{ε} \\ l o g_{2} (2^{k}) & \geq l o g_{2} (\frac{b - a}{ε}) \\ k & \geq l o g_{2} (\frac{b - a}{ε}) \end{aligned}

Tenendo presente che $k$ deve per definizione essere un numero intero positivo.

Criterio di arresto

Criterio di arresto a posteriori

Posso interrompere l'algoritmo quando l'errore al passo k è minore di una tolleranza scelta $ε$ .

| e_{k} | \leq ε

Implementazione in Matlab

function [soluzioneApprox,erroreStimato, iterazioniNecessarie] = MetodoBisezioneNonLineari(estremoInferiore, estremoSuperiore, funzione, tolleranza, numeroMaxIterazioni)

% Questa funzione serve ad applicare il metodo di bisezione a una funzione
% assegnata per ricavarne la soluzione approssimata.
% Input:
% estermoInferiore, estremoSuperiore: Estremi dell'intervallo di separazione
% funzione: la funzione, definita come anonymous function, a cui
% applicare il metodo
% tolleranza: La tolleranza con la quale si vuole trovare la soluzione
% numeroMaxIterazioni: Il numero max di iterazioni che si vogliono
% provare prima di interrompere il calcolo. (Se non specificato è
% inizializzato a 100

% ------------

% Outpu:
% soluzioneApprox: la soluzione approssimata
% erroreStimato: la media degli errori calcolati come b-a e come f(xn)
% iterazioniNecessarie: Il numero di iterazioni necessarie alla stima
% dell'errore
% Cerco la radice di una funzione f nell'intervallo [a,b] con il metodo di
% bisezione
% Suppongo di aver già individuato gli estremi degli intervalli di
% separazione
% Sfrutteremo un criterio di arresto basato sulla tolleranza:
% f = Funzione della quale vogliamo cercare la radice
% a = Estremo inferiore in cui è stata isolata la radice
% b = Estremo superiore in cui è stata isolata la radice
% toll = Tolleranza (\tollilon)
% numeroMaxIterazioni = Massimo numero di iterazioni

f = funzione;

% So che nell'intervallo definito sotto sicuremante ci sarà una soluzione
a = estremoInferiore;
b = estremoSuperiore;

% Definisco la tolleranza
toll = tolleranza;
maxIter = 100;
maxIter = numeroMaxIterazioni;

% Vogliamo calcolare:
% xn: Approx della radice
% err1 = |x(n) - x(n-1)|
% err2 = f(xn)
% iter = Numero di iterazioni

format long

% Inizializzo i parametri necessari
iter = 0; err1 = b-a; err2 = toll+1; x0 = a;

% Verifico che la radice esista
if f(a)*f(b) > 0
	error('Non ci sono soluzioni nellintervallo [a,b]') % Con questo comando blocco l'esecuzione dello script
elseif f(a)*f(b) == 0
	if f(a) == 0
		xn = a;
	elseif f(b) == 0
		xn = b;
	end
	return % Return perché non voglio andare avanti se queste condizioni del secondo if sono rispettate
end

% Calcolo successione
while (err1 > toll) && iter < maxIter
	xn = (a+b)/2;
	if f(a)*f(xn) < 0
		b = xn;
	elseif f(xn)*f(b) < 0
		a = xn;
end

iter = iter + 1;
err1 = abs(xn-x0);
err2 = abs(f(xn));
x0 = xn;
end

soluzioneApprox = xn;
erroreStimato = abs((err1 + err2)/2);
iterazioniNecessarie = iter;

end