MN02

Algorytm {Metoda bisekcji}

---

xl = a; xr = b;
x = (a+b)/2;  e = (b-a)/2;
while (e > <math>\displaystyle \epsilon</math>) 
{
	if (f(x)*f(xl) < 0)	
		xr = x;
	else
		xl = x;
	x = (xl+xr)/2; e = e/2;
} 

Z konstrukcji metody łatwo wynika, że po wykonaniu $k$ iteracji (czyli po obliczeniu $k$ wartości funkcji) otrzymujemy $x$, które odległe jest od pewnego rozwiązania $x^{*}$ o co najwyżej

$|x-x^{*}|\le \left(\frac{1}{2}{)}^k\right(\frac{b-a}{2}).$

Metoda bisekcji jest więc zbieżna liniowo z ilorazem $1/2$. Choć ta zbieżność nie jest imponująca, bisekcja ma kilka istotnych zalet. Oprócz jej prostoty, należy podkreślić fakt, że bisekcja jest w pewnym sensie uniwersalna. Jeśli tylko dysponujemy dwoma punktami $a$ i $b$ takimi, że $f$ przyjmuje w nich wartości przeciwnych znaków, to metoda bisekcji z pewnością znajdzie miejsce zerowe funkcji, choćby początkowa długość przedziału $|b-a|$ była bardzo duża: zbieżność metody bisekcji jest globalna. Co ważniejsze, dla zbieżności metody bisekcji wystarcza jedynie ciągłość funkcji. Poza tym możemy łatwo kontrolować błąd bezwzględny aproksymacji miejsca zerowego. Konsekwencją (Uzupelnic: blbis ) jest bowiem następujący wniosek.

Wniosek

Dla znalezienia zera $x^{*}$ z dokładnością $ϵ>0$, wystarczy obliczyć w metodzie bisekcji

$k=k(ϵ)=\lceil {\log }_2\frac{(b-a)}{ϵ}\rceil -1$

wartości funkcji.

Zbieżność metody bisekcji dla ....

Dodajmy jeszcze, że bisekcja minimalizuje błąd najgorszy w klasie $F$ zdefiniowanej Uzupełnij: na początku tej sekcji, wśród wszystkich algorytmów korzystających z określonej liczby obliczeń wartości funkcji, zob. Uzupełnij: uwaga na końcu wykładu.

Uwaga

Metoda bisekcji jest optymalna w następującym sensie. Niech $A:F\to R$ będzie dowolną metodą (algorytmem) aproksymującą zero $x^{*}(f)$ funkcji $f$ z klasy $F$ zdefiniowanej w (Uzupelnic: dfkl ), korzystającą jedynie z obliczeń (informacji o) $f$ w $k$ punktach. Wtedy dla dowolnego $\gamma >0$ istnieje funkcja $f_{\gamma }\in F$ mająca tylko jedno zero $x^{*}(f_{\gamma })$ w $[a,b]$ i taka, że

$|A(f_{\gamma })-x^{*}(f_{\gamma })|\ge \left(\frac{1}{2}{)}^k\right(\frac{b-a}{2})+\gamma .$

Co więcej, można pokazać, że fakt ten zachodzi też w węższej klasie $F_1$ funkcji $f\in F$, które są dowolnie wiele razy różniczkowalne. Oczywiście, nie wyklucza to istnienia metod iteracyjnych (takich jak metoda Newtona), które dla $f\in F_1$ są zbieżne szybciej niż liniowo.

Metoda iteracji prostej Banacha

Zupełnie inne, i jak się okaże --- przy odrobinie sprytu bardzo skuteczne --- podejście do wyznaczania miejsca zerowego jest oparte na metodzie Banacha.

Najpierw nasze równanie nieliniowe

$f(x)=0$

przekształcamy (dobierając odpowiednią funkcję $\varphi$) do równania równoważnego (tzn. mającego te same rozwiązania)

$x=\varphi (x).$

Następnie, startując z pewnego przybliżenia początkowego $x_0$, konstruujemy ciąg kolejnych przybliżeń $x_k$ według wzoru

$x_k=\varphi (x_{k-1}),k\ge 1.$

Twierdzenie Banacha, o zbieżności iteracji prostej

Niech $D_0$ będzie domkniętym 

podzbiorem dziedziny $D$,

${\bar{D}}_0=D_0\subset D,$

w którym $\varphi$ jest odwzorowaniem zwężającym. To znaczy, $\varphi (D_0)\subset D_0$, oraz istnieje stała $0\le L<1$ taka, że

$\Vert \varphi (x)-\varphi (y)\Vert \le L\Vert x-y\Vert ,\mathrm{\forall }x,y\in D_0.$

Wtedy równanie (Uzupelnic: rrw ) ma dokładnie jedno rozwiązanie $x^{*}$, oraz

$x^{*}=\underset{k\to \mathrm{\infty }}{\lim }{x}_k,$

dla dowolnego przybliżenia początkowego $x_0\in D_0$.

Dowód

Wobec

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \displaystyle \aligned \| x_k- x_{k-1}\| &= \|\phi( x_{k-1})-\phi( x_{k-2})\| \,\le\,L\,\| x_{k-1}- x_{k-2}\| \\ &\le &\cdots\;\le\;L^{k-1}\| x_1- x_0\|, \endaligned}

dla $k\ge s$ mamy

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \displaystyle \aligned \| x_k- x_s\| &\le & \sum_{j=s+1}^k\| x_j- x_{j-1}\| \,\le\,\sum_{j=s+1}^k L^{j-1}\| x_1- x_0\| \\ &= L^s(1+L+\cdots+L^{k-s-1})\| x_1- x_0\| \,\le\,\frac{L^s}{1-L}\| x_1- x_0\|. \endaligned}

Ciąg $\{x_k{\}}_k$ jest więc ciągiem Cauchy'ego. Stąd istnieje granica $\overrightarrow{\alpha }=\underset{k\to \mathrm{\infty }}{\lim }{x}_k$, która należy do $D_0$, wobec domkniętości tego zbioru. Ponieważ lipschitzowskość $\varphi$ implikuje jej ciągłość, mamy też

$\varphi (\overrightarrow{\alpha })=\varphi \left(\underset{k\to \mathrm{\infty }}{\lim }{x}_k\right)=\underset{k\to \mathrm{\infty }}{\lim }\varphi (x_k)=\underset{k\to \mathrm{\infty }}{\lim }{x}_k=\overrightarrow{\alpha },$

tzn. $\overrightarrow{\alpha }$ jest punktem stałym odwzorowania $\varphi$. Dla jednoznaczności zauważmy, że jeśliby istniał drugi, różny od $\overrightarrow{\alpha }$, punkt stały $\overrightarrow{\beta }$, to mielibyśmy

$\Vert \overrightarrow{\alpha }-\overrightarrow{\beta }\Vert =\Vert \varphi (\overrightarrow{\alpha })-\varphi (\overrightarrow{\beta })\Vert \le L\Vert \overrightarrow{\alpha }-\overrightarrow{\beta }\Vert .$

Stąd $1<L$, co jest sprzeczne z założeniem, że

$\varphi$ jest zwężająca.