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.  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  për ndryshoren reale x, ku  është një funksion i vazhdueshëm i përcaktuar në një interval  dhe ku  dhe  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  duhet të ketë të paktën një rrënjë në intervalin .

Në çdo hap, metoda e ndan intervalin në dy pjesë/gjysma duke llogaritur pikën e mesit  të intervalit dhe vlerën e funksionit  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  dhe  kanë shenja të kundërta dhe kllapojnë një rrënjë, ose  dhe  kanë shenja të kundërta dhe kllaposin një rrënjë. If the function has the same sign at the endpoints of an interval, the endpoints may or may not bracket roots of the function. 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  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 , atëherë c mund të merret si zgjidhje dhe procesi ndalon. Përndryshe, nëse  dhe  kanë shenja të kundërta, atëherë metoda vendos  si vlerë të re për , dhe nëse  dhe  kanë shenja të kundërta, atëherë metoda vendos  si të re  . Në të dyja rastet,  dhe  e re kanë shenja të kundërta, kështu që metoda është e zbatueshme për këtë interval më të vogël.  for section

 Punët e iterimit 
Argumenti për metodën është një funksion i vazhdueshëm , një interval  dhe vlerat e funksionit  dhe . 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,   .
 Llogarit vlerën e funksionit në pikën e mesit, .
 Nëse konvergjenca është e kënaqshme (d.m.th., c - a është mjaft e vogël, ose  është mjaft e vogël), kthe numrin  dhe ndalo përsëritjen.
 Shqyrto shenjën e  dhe zëvendëso ose  ose  me  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  ë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  ; nuk ka asnjë vlerë me presje notuese që i përafrohet  e cila jep saktësisht zero. Për më tepër, ndryshimi midis  dhe  kufizohet nga saktësia e presjes notuese; dmth, ndërsa diferenca midis a dhe b zvogëlohet, në një moment mesi i  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



Së pari, dy numra  dhe  duhet të gjenden të tillë që  dhe  të kenë shenja të kundërta. Për funksionin e mësipërm,  dhe  plotësojnë këtë kriter, pasi



dhe



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

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



Vlera e funksionit në pikën e mesit është  . Sepse  është negative,  zëvendësohet me  për iterimin tjetër për të siguruar që  dhe  kanë shenja të kundërta. Ndërsa kjo vazhdon, intervali ndërmjet  dhe  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     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ë  nëse  është një funksion i vazhdueshëm në intervalin  dhe  së bashku me  kanë shenja të kundërta. Gabimi absolut përgjysmohet në çdo hap, kështu që metoda konvergjon në mënyrë lineare . Konkretisht, nëse   është mesi i intervalit fillestar, dhe  është mesi i intervalit në hapin e n- të, atëherë diferenca midis  dhe një zgjidhje c kufizohet nga , Theorem 2.1



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



ku madhësia fillestare e kllapave  dhe madhësia e kërkuar e kllapës  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  të zgjidhjes c që në rastin më të keq ka një gabim absolut   me më pak se  përsëritje.  Kjo është gjithashtu e vërtetë në disa supozime të zakonshme për funksionin  dhe sjelljen e funksionit në afërsi të rrënjës.  
Kategoria:Matematikë
Kategoria:Analiza numerike