Metoda e përgjysmimit

[[Skeda:Bisection_method.svg|parapamje|291x291px| Disa hapa të metodës së përgjysmimit të zbatuara në intervalin e fillimit [a 1 ;b 1 ]. Pika e kuqe është rrënja e funksionit.]]
Në matematikë, **metoda e përgjysmimit** është një metodë e gjetjes së rrënjëve që zbatohet për çdo funksion të vazhdueshëm për të cilin dihen dy vlera me shenja të kundërta. Metoda mbështetet në përgjysmimin e përsëritur të intervalit të përcaktuar nga këto vlera dhe më pas në zgjedhjen e nënintervalit në të cilin funksioni ndryshon shenjën, dhe për këtë arsye duhet të përmbajë një rrënjë . Është një metodë shumë e thjeshtë dhe e fuqishme, por është gjithashtu relativisht e ngadaltë. Për shkak të kësaj, shpesh përdoret për të marrë një përafrim të thatë me një zgjidhje e cila më pas përdoret si pikënisje për metodat që konvergjojnë më shpejt.  Metoda quhet edhe   **metoda e kërkimit binar**,  ose **metoda e dikotomisë** . 

Për polinomet, ekzistojnë metoda më të përpunuara për testimin e ekzistencës së një rrënjë në një interval ( rregulli i shenjave të Dekartit, teorema e Shturmit, teorema e Budanit ). Ato lejojnë zgjerimin e metodës së përgjysmimit në algoritme efikase për gjetjen e të gjitha rrënjëve reale të një polinomi; shih Izolimi me rrënjë reale .

## Metoda 
Metoda është e zbatueshme për zgjidhjen numerike të ekuacionit f(x)=0 për ndryshoren reale *x*, ku f është një funksion i vazhdueshëm i përcaktuar në një interval [a,b] dhe ku f(a) dhe f(b) kanë shenja të kundërta. Në këtë rast *a* dhe *b* thuhet se kllapojnë një rrënjë pasi, sipas teoremës së vlerës së ndërmjetme, funksioni i vazhdueshëm f duhet të ketë të paktën një rrënjë në intervalin (a,b).

Në çdo hap, metoda e ndan intervalin në dy pjesë/gjysma duke llogaritur pikën e mesit c = \frac{(a+b)}{2} të intervalit dhe vlerën e funksionit f(c) në atë pikë. Nëse *c* në vetvete është një rrënjë, atëherë procesi ka pasur sukses dhe ndalon. Përndryshe, tani ekzistojnë vetëm dy mundësi: ose f(a) dhe f(c) kanë shenja të kundërta dhe kllapojnë një rrënjë, ose f(c) dhe f(b) kanë shenja të kundërta dhe kllaposin një rrënjë.  Metoda zgjedh nënintervalin që është i garantuar të jetë një kllapë si interval i ri që do të përdoret në hapin tjetër. Në këtë mënyrë një interval që përmban një zero të funksionit f zvogëlohet në gjerësi me 50% në çdo hap. Procesi vazhdon derisa intervali të jetë mjaft i vogël.

Në mënyrë të qartë, nëse f(c)=0, atëherë *c* mund të merret si zgjidhje dhe procesi ndalon. Përndryshe, nëse f(a) dhe f(c) kanë shenja të kundërta, atëherë metoda vendos c si vlerë të re për b, dhe nëse f(b) dhe f(c) kanë shenja të kundërta, atëherë metoda vendos c si të re a . Në të dyja rastet, f(a) dhe f(b) e re kanë shenja të kundërta, kështu që metoda është e zbatueshme për këtë interval më të vogël. 

### Punët e iterimit 
Argumenti për metodën është një funksion i vazhdueshëm f, një interval [a,b] dhe vlerat e funksionit f(a) dhe f(b). Vlerat e funksionit janë me shenjë të kundërt (ka të paktën një prerje me zeron brenda intervalit). Çdo përsëritje kryen këto hapa:

# Llogarit *c*, mesin e intervalit, c = \frac{a+b}{2}  .
# Llogarit vlerën e funksionit në pikën e mesit, f(c).
# Nëse konvergjenca është e kënaqshme (d.m.th., *c* - *a* është mjaft e vogël, ose |f(c)| është mjaft e vogël), kthe numrin c dhe ndalo përsëritjen.
# Shqyrto shenjën e f(c) dhe zëvendëso ose (a, f(a)) ose (b,f(b)) me (c,f(c)) në mënyrë që të ketë një prerje me zeron brenda intervalit të ri. 

Gjatë zbatimit të metodës në një kompjuter, mund të ketë probleme me saktësinë e fundme, kështu që shpesh ka teste shtesë të konvergjencës ose kufizime në numrin e përsëritjeve. Edhe pse f është i vazhdueshëm, saktësia e fundme mund të përjashtojë zeron si një vlerë të funksionit, gjë e padëshirueshme. Për shembull, merrni parasysh f(x) = \cos x ; nuk ka asnjë vlerë me presje notuese që i përafrohet x= \frac{\pi}{2} e cila jep saktësisht zero. Për më tepër, ndryshimi midis a dhe b kufizohet nga saktësia e presjes notuese; dmth, ndërsa diferenca midis *a* dhe *b* zvogëlohet, në një moment mesi i [a,b] do të jetë numerikisht identik me (brenda saktësisë së pikës lundruese) ose *a* ose *b* .

### Shembull: Gjetja e rrënjës së një polinomi 
Supozoni se metoda e përgjysmimit përdoret për të gjetur një rrënjë të polinomit

:  f(x) = x^3 - x - 2 \,.

Së pari, dy numra  a  dhe  b  duhet të gjenden të tillë që f(a) dhe f(b) të kenë shenja të kundërta. Për funksionin e mësipërm,  a = 1  dhe  b = 2  plotësojnë këtë kriter, pasi

:  f(1) = (1)^3 - (1) - 2 = -2 

dhe

:  f(2) = (2)^3 - (2) - 2 = +4 \,.

Për shkak se funksioni është i vazhdueshëm, duhet të ketë një rrënjë brenda intervalit [1,2].

Në iterimin e parë, janë pikat fundore të intervalit që lidh rrënjën  a_1 = 1  dhe  b_1 = 2 , pra pika e mesit është

:  c_1 = \frac{2+1}{2} = 1.5 

Vlera e funksionit në pikën e mesit është  f(c_1) = (1.5)^3 - (1.5) - 2 = -0.125  . Sepse  f(c_1)  është negative,  a = 1  zëvendësohet me  a = 1.5  për iterimin tjetër për të siguruar që  f(a)  dhe  f(b)  kanë shenja të kundërta. Ndërsa kjo vazhdon, intervali ndërmjet  a  dhe  b  do të bëhet gjithnjë e më i vogël, duke konvergjuar në rrënjën e funksionit. Shihni këtë të ndodhë në tabelën më poshtë.

Pas 13 përsëritjesh, bëhet e qartë se ka një konvergjencë në rreth 1.521: një rrënjë për polinomin.

## Analiza 
Metoda është e garantuar të konvergjojë në një rrënjë të f nëse f është një funksion i vazhdueshëm në intervalin [a,b] dhe f(a) së bashku me f(b) kanë shenja të kundërta. Gabimi absolut përgjysmohet në çdo hap, kështu që metoda konvergjon në mënyrë lineare . Konkretisht, nëse c_1=\frac{a+b}{2}  është mesi i intervalit fillestar, dhe c_{n} është mesi i intervalit në hapin e *n-* të, atëherë diferenca midis c_{n} dhe një zgjidhje *c* kufizohet nga 

: |c_n-c|\le\frac{2^n}.

Kjo formulë mund të përdoret për të përcaktuar, paraprakisht, një kufi të sipërm në numrin e iterimeve që metoda e përgjysmimit duhet të konvergjojë në një rrënjë brenda një tolerance të caktuar. Numri *n* i përsëritjeve të nevojshme për të arritur një tolerancë të kërkuar \epsilon (d.m.th., një gabim i garantuar të jetë maksimumi \epsilon), kufizohet nga

: n \le n_{1/2} \equiv \left\lceil\log_2\left(\frac{\epsilon_0}{\epsilon}\right)\right\rceil, 

ku madhësia fillestare e kllapave \epsilon_0 = |b-a| dhe madhësia e kërkuar e kllapës \epsilon \le \epsilon_0. Motivimi kryesor për të përdorur metodën e përgjysmimit është se mbi grupin e funksioneve të vazhdueshme, asnjë metodë tjetër nuk mund të garantojë të prodhojë një vlerësim c_{n} të zgjidhjes c që në *rastin më të keq* ka një gabim absolut \epsilon  me më pak se n_{1/2} përsëritje.  Kjo është gjithashtu e vërtetë në disa supozime të zakonshme për funksionin f dhe sjelljen e funksionit në afërsi të rrënjës.