ในทางคณิตศาสตร์วิธีการแบ่งครึ่งช่วง (bisection method)เป็นวิธีการหาค่ารากที่ใช้กับฟังก์ชันต่อเนื่อง ใดๆ ที่เรารู้ค่าสองค่าที่มีเครื่องหมายตรงข้ามกัน วิธีการนี้ประกอบด้วยการแบ่งครึ่งช่วงที่กำหนดโดยค่าเหล่านี้ซ้ำๆ จากนั้นเลือกช่วงย่อยที่ฟังก์ชันเปลี่ยนเครื่องหมาย ซึ่งจะต้องมีราก อยู่ ในช่วงย่อยนั้น วิธีนี้เป็นวิธีที่ง่ายและแข็งแกร่งมาก แต่ก็ค่อนข้างช้า ด้วยเหตุนี้ จึงมักใช้เพื่อหาค่าประมาณคร่าวๆ ของคำตอบ ซึ่งจะใช้เป็นจุดเริ่มต้นสำหรับวิธีการที่ลู่เข้าได้เร็วกว่า^{[ 1 ]}วิธีนี้เรียกอีกอย่างว่าวิธี^การแบ่งครึ่งช่วง^{[ 2 ]}วิธีการค้นหาแบบไบนารี [ ^{a ] ​​[ 3 ]}หรือวิธีการแบ่งสองส่วน^{[ 4 ]}

สำหรับพหุนามมีวิธีการที่ซับซ้อนกว่าในการตรวจสอบการมีอยู่ของรากในช่วง ( เช่น กฎเครื่องหมายของเดส์การ์ต , ทฤษฎีบทของสเติร์ม , ทฤษฎีบทของบูดาน ) วิธีการเหล่านี้ช่วยให้สามารถขยายวิธีการแบ่งครึ่งช่วงไปสู่ขั้นตอนวิธีที่มีประสิทธิภาพในการค้นหารากจริงทั้งหมดของพหุนาม ดู การ แยก รากจริง

วิธีการนี้ใช้ได้กับการแก้สมการเชิงตัวเลขสำหรับตัวแปรจริงโดยที่เป็นฟังก์ชันต่อเนื่องที่กำหนดบนช่วงและ โดยที่และมีเครื่องหมายตรงข้ามกัน ในกรณีนี้และกล่าวได้ว่าอยู่ล้อมรอบราก เนื่องจากตามทฤษฎีบทค่ากลางฟังก์ชันต่อเนื่อง จะต้องมีรากอย่างน้อย หนึ่ง รากในช่วง${\displaystyle f(x)=0}$${\displaystyle x}$${\displaystyle f}$${\displaystyle [a,b]}$${\displaystyle f(a)}$${\displaystyle f(b)}$${\displaystyle a}$${\displaystyle b}$${\displaystyle f}$${\displaystyle (a,b)}$

ในแต่ละขั้นตอน วิธีการนี้จะแบ่งช่วงออกเป็นสองส่วน/ครึ่ง โดยคำนวณจุดกึ่งกลางของช่วงและค่าของฟังก์ชันณ จุดนั้น หากตัวมันเองเป็นราก กระบวนการก็จะสำเร็จและหยุดลง มิฉะนั้น จะมีเพียงสองความเป็นไปได้เท่านั้น คือและมีเครื่องหมายตรงข้ามกันและครอบคลุมราก หรือและมีเครื่องหมายตรงข้ามกันและครอบคลุมราก^{[ 5 ]}วิธีการนี้จะเลือกช่วงย่อยที่รับประกันว่าเป็นวงเล็บเป็นช่วงใหม่ที่จะใช้ในขั้นตอนถัดไป ด้วยวิธีนี้ ช่วงที่มีศูนย์ของจะลดความกว้างลง 50% ในแต่ละขั้นตอน กระบวนการนี้จะดำเนินต่อไปจนกว่าช่วงจะมีขนาดเล็กพอ ${\displaystyle c=(a+b)/2}$${\displaystyle f(c)}$${\displaystyle c}$${\displaystyle f(a)}$${\displaystyle f(c)}$${\displaystyle f(c)}$${\displaystyle f(b)}$${\displaystyle f}$

กล่าวโดยชัดเจน หาก เงื่อนไข ดังกล่าวสามารถนำมาพิจารณาเป็นคำตอบได้ กระบวนการก็จะหยุดลง ${\displaystyle f(c)=0}$${\displaystyle c}$

มิฉะนั้น หากและมีเครื่องหมายเดียวกัน ${\displaystyle f(a)}$${\displaystyle f(c)}$

• จากนั้นเมธอดจะตั้งค่า,${\displaystyle a=c}$
• มิเช่นนั้นเมธอดจะตั้งค่า.${\displaystyle b=c}$

ในทั้งสองกรณี ค่าใหม่จะมีเครื่องหมายตรงข้ามกัน ดังนั้นวิธีนี้จึงสามารถนำไปใช้กับช่วงเวลาที่เล็กกว่านี้ได้^{[ 6 ]}${\displaystyle f(a)}$${\displaystyle f(b)}$

เมื่อกระบวนการเริ่มต้นแล้ว เครื่องหมายที่ปลายด้านซ้ายและด้านขวาของช่วงเวลาจะคงที่เหมือนเดิมในทุกรอบการทำซ้ำ

เพื่อกำหนดว่าการวนซ้ำควรหยุดเมื่อใด จำเป็นต้องพิจารณาเงื่อนไขการหยุดที่เป็นไปได้ต่างๆ โดยคำนึงถึงค่าความคลาดเคลื่อน ( ) Burden และ Faires (2016) ระบุเงื่อนไขการหยุดสามประการ: ^{[ 7 ]}${\displaystyle \epsilon }$

• ค่าความคลาดเคลื่อนสัมบูรณ์:${\displaystyle |p_{N}-p_{N-1}|<\epsilon }$
• ค่าความคลาดเคลื่อนสัมพัทธ์: ||${\displaystyle \left|{\frac {p_{N}-p_{N-1}}{p_{N}}}\right|<\epsilon ,}$${\displaystyle p_{N}\neq 0}$
• ${\displaystyle |f(p_{N})|<\epsilon .}$

${\displaystyle |f(p_{N})|<\epsilon }$จะไม่ให้ผลลัพธ์ที่แม่นยำภายในเว้นแต่ ความเป็นไปได้อีกสองประการแสดงถึงแนวคิดที่แตกต่างกัน: ความแตกต่างสัมบูรณ์กล่าวว่า c และ a เหมือนกันถึงตำแหน่งทศนิยม ในขณะที่ความแตกต่างสัมพัทธ์กล่าวว่า c และ a เหมือนกันถึงตัวเลขสำคัญ^{[ 8 ]}หากไม่ทราบค่าของราก การยอมรับความคลาดเคลื่อนสัมพัทธ์ถือเป็นเงื่อนไขการหยุดที่ดีที่สุด^{[ 9 ]}${\displaystyle \epsilon }$${\displaystyle |f'(p_{N})|\geq 1}$${\displaystyle |ca|\leq 5\times 10^{-t}}$${\displaystyle t}$${\displaystyle \left|{\frac {ca}{c}}\right|\leq 5\times 10^{-t}}$${\displaystyle t}$

อินพุตของเมธอดนี้คือฟังก์ชันต่อเนื่องและช่วงโดยที่ค่าของฟังก์ชันและ มีเครื่องหมายตรงข้ามกัน (มีจุดตัดศูนย์อย่างน้อยหนึ่งจุดภายในช่วง) แต่ละรอบการทำงานจะดำเนินการตามขั้นตอนเหล่านี้: ${\displaystyle f}$${\displaystyle [a,b]}$${\displaystyle f(a)}$${\displaystyle f(b)}$

1. คำนวณหาจุดกึ่งกลางของช่วง;${\displaystyle c}$${\displaystyle c={\frac {a+b}{2}}}$
2. คำนวณค่าฟังก์ชันที่จุดกึ่งกลาง;${\displaystyle f(c)}$
3. ถ้าเป็นเช่นนั้นให้ส่งคืนค่า c;${\displaystyle f(c)=0}$
4. หากการลู่เข้าเป็นที่น่าพอใจ (นั่นคือ) ให้ส่งคืน;${\displaystyle \left|ca\right|\leq 5\times 10^{-t}|c|}$${\displaystyle c}$
5. ตรวจสอบเครื่องหมายของและแทนที่หรือด้วยเพื่อให้มีจุดตัดศูนย์ภายในช่วงเวลาใหม่${\displaystyle f(c)}$${\displaystyle a}$${\displaystyle b}$${\displaystyle c}$

สมมติว่าใช้วิธีแบ่งครึ่งช่วงเพื่อหาค่ารากของพหุนาม

${\displaystyle f(x)=x^{3}-x-2\,.}$

ขั้นแรก ต้องหาจำนวนสองจำนวนคือ และ ที่ทำให้ และมีเครื่องหมายตรงข้ามกัน สำหรับฟังก์ชันข้างต้น จำนวนและเป็นไปตามเกณฑ์นี้ เนื่องจาก ${\displaystyle a}$${\displaystyle b}$${\displaystyle f(a)}$${\displaystyle f(b)}$${\displaystyle a=1}$${\displaystyle b=2}$

${\displaystyle f(1)=(1)^{3}-(1)-2=-2}$

และ

${\displaystyle f(2)=(2)^{3}-(2)-2=+4\,.}$

เนื่องจากฟังก์ชันมีความต่อเนื่อง จึงต้องมีรากภายในช่วง [1, 2] การทำซ้ำวิธีการแบ่งครึ่งช่วงนี้จะให้ค่าประมาณที่แม่นยำขึ้นเรื่อยๆ:

การวนซ้ำ	${\displaystyle a_{n}}$	${\displaystyle b_{n}}$	${\displaystyle c_{n}}$	${\displaystyle 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

หลังจากทำการวนซ้ำ 13 ครั้ง ก็เห็นได้ชัดว่าค่าที่ได้มีแนวโน้มลู่เข้าสู่ประมาณ 1.521 ซึ่งเป็นรากของพหุนาม

วิธีการแบ่งครึ่งได้รับการขยายให้ครอบคลุมฟังก์ชันหลายมิติ วิธีการดังกล่าวเรียกว่าวิธีการแบ่งครึ่งแบบทั่วไป^{[ 10 ] [ 11 ]}

วิธีการเหล่านี้บางส่วนขึ้นอยู่กับการคำนวณระดับโทโพโลยี^{[ 12 ]}

วิธีการแบ่งครึ่งลักษณะเฉพาะใช้เพียงเครื่องหมายของฟังก์ชันในจุดต่างๆ เท่านั้น ให้fเป็นฟังก์ชันจาก R ^dไปยัง R ^dสำหรับจำนวนเต็มd ≥ 2 บางตัว โพลีเฮดรอนลักษณะเฉพาะ^{[ 13 ]} (เรียกอีกอย่างว่าโพลีกอนที่ยอมรับได้ ) ^{[ 14 ]}ของfคือโพลีเฮดรอนใน R ^dที่มีจุดยอด 2 ^dจุด โดยที่ในแต่ละจุดยอดvการรวมกันของเครื่องหมายของf ( v ) มีเอกลักษณ์เฉพาะตัว ตัวอย่างเช่น สำหรับd =2 โพลีเฮดรอนลักษณะเฉพาะของfคือรูปสี่เหลี่ยมที่มีจุดยอด (เช่น) A, B, C, D โดยที่:

• เครื่องหมายf (A) = (−,−) นั่นคือf ₁ (A)<0, f ₂ (A)<0
• เครื่องหมายf (B) = (−,+) นั่นคือf ₁ (B)<0, f ₂ (B)>0
• เครื่องหมายf (C) = (+,−) นั่นคือf ₁ (C)>0, f ₂ (C)<0
• เครื่องหมายf (D) = (+,+) นั่นคือf ₁ (D)>0, f ₂ (D)>0

ขอบแท้ของรูปหลายเหลี่ยมลักษณะเฉพาะ คือ ขอบระหว่างจุดยอดสองจุด โดยที่เวกเตอร์เครื่องหมายของขอบทั้งสองแตกต่างกันเพียงเครื่องหมายเดียว ในตัวอย่างข้างต้น ขอบแท้ของรูปสี่เหลี่ยมลักษณะเฉพาะคือ AB, AC, BD และ CD เส้นทแยงมุมคือ จุดยอดสองจุด โดยที่เวกเตอร์เครื่องหมายของขอบทั้งสองแตกต่างกันด้วย เครื่องหมาย d ทั้งหมด ในตัวอย่างข้างต้น เส้นทแยงมุมคือ AD และ BC

ในแต่ละรอบการทำงาน อัลกอริทึมจะเลือกขอบที่เหมาะสมของทรงหลายเหลี่ยม (เช่น A—B) และคำนวณเครื่องหมายของfที่จุดกึ่งกลาง (เช่น M) จากนั้นจะดำเนินการดังต่อไปนี้:

• ถ้า Sign f (M) = Sign(A) แล้ว A จะถูกแทนที่ด้วย M และเราจะได้รูปทรงหลายเหลี่ยมลักษณะเฉพาะที่มีขนาดเล็กลง
• ถ้า Sign f (M) = Sign(B) แล้ว B จะถูกแทนที่ด้วย M และเราจะได้รูปทรงหลายเหลี่ยมลักษณะเฉพาะที่มีขนาดเล็กลง
• หรืออีกทางหนึ่ง เราจะเลือกขอบที่เหมาะสมใหม่แล้วลองอีกครั้ง

สมมติว่าเส้นผ่านศูนย์กลาง (= ความยาวของขอบที่เหมาะสมที่ยาวที่สุด) ของรูปหลายเหลี่ยมลักษณะเฉพาะดั้งเดิมคือDดังนั้น จะต้องมีการแบ่งขอบอย่างน้อยสองครั้งเพื่อให้เส้นผ่านศูนย์กลางของรูปหลายเหลี่ยมที่เหลืออยู่มีค่าไม่เกิน[ ^{14 ] : 11, Lemma.4.7} ${\displaystyle \log _{2}(D/\varepsilon )}$${\displaystyle \varepsilon }$

• อัลกอริทึมการค้นหาแบบไบนารี
• อัลกอริทึมเลห์เมอร์-ชูร์คือ การขยายวิธีการแบ่งครึ่งในระนาบเชิงซ้อน
• ช่วงเวลาซ้อนกัน

• Corliss, George (1977), "อัลกอริทึมการแบ่งครึ่งหารากใด?", SIAM Review , 19 (2): 325– 327, doi : 10.1137/1019044 , ISSN  1095-7200
• Kaw, Autar; Kalu, Egwu (2008), วิธีการเชิงตัวเลขพร้อมการประยุกต์ใช้ (ฉบับพิมพ์ครั้งที่ 1), เก็บถาวรจากต้นฉบับเมื่อ 2009-04-13

เว็บไซต์ Wikibook เรื่องวิธีการเชิงตัวเลขมีหน้าหนึ่งที่กล่าวถึงหัวข้อ: การแก้สมการ

• เอกสารประกอบการอธิบาย วิธีการแบ่งครึ่งช่วง (Bisection Method)ในรูปแบบ PowerPoint, Mathcad, Maple, Matlab, Mathematica จากHolistic Numerical Methods Institute

⊤