Metoda e përgjysmimit

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. ^[1] Metoda quhet edhe ^[2] metoda e kërkimit binar, ^[3] ose metoda e dikotomisë . ^[4]

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ë. ^[5] 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. ^[6]

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ë.

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 ^[7]

|c_{n}-c|\leq {\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 $\epsilon$ (d.m.th., një gabim i garantuar të jetë maksimumi $\epsilon$ ), kufizohet nga

n\leq 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 \leq \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. ^[8] 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. ^[8] ^[9]

^ Burden & Faires 1985
^ "Interval Halving (Bisection)". Arkivuar nga origjinali më 2013-05-19. Marrë më 2013-11-07. {{cite web}}: Mungon ose është bosh parametri |language= (Ndihmë!)
^ Burden & Faires 1985
^ "Dichotomy method - Encyclopedia of Mathematics". www.encyclopediaofmath.org. Marrë më 2015-12-21. {{cite web}}: Mungon ose është bosh parametri |language= (Ndihmë!)
^ If the function has the same sign at the endpoints of an interval, the endpoints may or may not bracket roots of the function.
^ Burden & Faires 1985, p. 28 for section
^ Burden & Faires 1985, p. 31, Theorem 2.1
^ ^a ^b Sikorski, K. (1982-02-01). "Bisection is optimal". Numerische Mathematik (në anglisht). 40 (1): 111–117. doi:10.1007/BF01459080. ISSN 0945-3245.
^ Sikorski, K (1985-12-01). "Optimal solution of nonlinear equations". Journal of Complexity (në anglisht). 1 (2): 197–209. doi:10.1016/0885-064X(85)90011-1. ISSN 0885-064X.

[1] Burden & Faires 1985

[2] "Interval Halving (Bisection)". Arkivuar nga origjinali më 2013-05-19. Marrë më 2013-11-07. {{cite web}}: Mungon ose është bosh parametri |language= (Ndihmë!)

[3] Burden & Faires 1985

[4] "Dichotomy method - Encyclopedia of Mathematics". www.encyclopediaofmath.org. Marrë më 2015-12-21. {{cite web}}: Mungon ose është bosh parametri |language= (Ndihmë!)

[5] If the function has the same sign at the endpoints of an interval, the endpoints may or may not bracket roots of the function.

[6] Burden & Faires 1985, p. 28 for section

[7] Burden & Faires 1985, p. 31, Theorem 2.1

[:0-8] Sikorski, K. (1982-02-01). "Bisection is optimal". Numerische Mathematik (në anglisht). 40 (1): 111–117. doi:10.1007/BF01459080. ISSN 0945-3245.

[9] Sikorski, K (1985-12-01). "Optimal solution of nonlinear equations". Journal of Complexity (në anglisht). 1 (2): 197–209. doi:10.1016/0885-064X(85)90011-1. ISSN 0885-064X.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]