Metoda e përgjysmimit

Disa hapa të metodës së përgjysmimit të zbatuara në intervalin e fillimit [a ₁ ;b ₁ ]. 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:

1. Llogarit c, mesin e intervalit, $c=\frac{a+b}{2}$ .
2. Llogarit vlerën e funksionit në pikën e mesit, $f(c)$.
3. 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.
4. 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ë.

Përsëritje	$a_n$	$b_n$	$c_n$	$f(c_n)$
1	1	2	1.5	−0,125
2	1.5	2	1.75	1.6093750
3	1.5	1.75	1.625	0.6660156
4	1.5	1.625	1,5625	0,2521973
5	1.5	1,5625	1.5312500	0,0591125
6	1.5	1.5312500	1.5156250	−0,0340538
7	1.5156250	1.5312500	1.5234375	0,0122504
8	1.5156250	1.5234375	1.5195313	−0,0109712
9	1.5195313	1.5234375	1.5214844	0.0006222
10	1.5195313	1.5214844	1.5205078	−0,0051789
11	1.5205078	1.5214844	1.5209961	−0,0022794
12	1.5209961	1.5214844	1.5212402	−0.0008289
13	1.5212402	1.5214844	1.5213623	−0.0001034
14	1.5213623	1.5214844	1.5214233	0.0002594
15	1.5213623	1.5214233	1.5213928	0.0000780

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{|b-a|}{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 $ϵ$ (d.m.th., një gabim i garantuar të jetë maksimumi $ϵ$), kufizohet nga

$n\le n_{1/2}\equiv \lceil {\log }_2\left(\frac{{ϵ}_0}{ϵ}\right)\rceil ,$

ku madhësia fillestare e kllapave ${ϵ}_0=|b-a|$ dhe madhësia e kërkuar e kllapës $ϵ\le {ϵ}_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 $ϵ$ 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.