วิธีแบ่งครึ่ง

การแบ่งครึ่งช่วง (อังกฤษ: Bisection method) คือการแบ่งออกเป็นสองส่วนเท่ากันในคณิตศาสตร์เป็นวิธีการหารากที่ซ้ำ ๆ การแบ่งออกเป็นสองส่วนเท่ากันช่วงเวลาและจากนั้นเลือกช่วงย่อยซึ่งรากต้องอยู่ในแนวแกน X สำหรับการประมวลผลต่อไป เป็นวิธีที่ง่ายและมีประสิทธิภาพ แต่ยังค่อนข้างช้า ด้วยเหตุนี้มันจึงมักใช้เพื่อหาแนวทางในการแก้ปัญหาโดยประมาณซึ่งใช้เป็นจุดเริ่มต้นของวิธีการบรรจบกันอย่างรวดเร็วมากขึ้น วิธีการนี้เรียกว่าวิธีการลดช่วงเวลา วิธีการค้นหาแบบไบนารี

กระบวนการ

การเตรียมฟังก์ชัน : จัดรูปให้ฟังก์ชันอยู่ในรูป f(x) = 0

ลำดับที่ 1: ทำการเดาจุดสองจุดคือค่า X_l และค่า X_uสมมุติว่าค่า X_l เป็นค่าที่ต่ำกว่าจากนั้นทดสอบว่า f(X_l) f(X_u) < 0 ถ้าไม่ใช้ให้หาจุดใหม่ซึ่งจากขั้นตอนนี้ เรารู้ว่ารากจะต้องอยู่ในช่วงนี้

ลำดับที่ 2: ทําการประมาณค่า Root ที่ต้องการที่จุดกึ่งกลางระหว่างสองค่าใน Step 1 โดยคํานวณ

ลำดับที่ 3: หาว่าตอนนี้ Root ที่ต้องการอยู่ในครึ่งไหนดังนี้

กราฟแสดงค่า F(a_n) เข้าใกล้ 0

3.1) ถ้า f(X_l) f(X_r) < 0 แสดงว่า Root ที่ต้องการอยู่ในครึ่งล่าง ให้ตั้ง X_u= X_r และกลับไปทํา ลำดับที่ 2

3.2) ถ้า f(X_l) f(X_r) > 0 แสดงว่า Root ที่ต้องการอยู่ในครึ่งบน ให้ตั้ง X_l = X_r และกลับไปทํา ลำดับที่ 2

3.3) ถ้า f(X_l) f(X_r) = 0 แสดงว่าคําตอบที่ต้องการเท่ากับ X

อัลกอริทึม

จากกระบวนการ จะสามารถเขียนเป็นภาษาโปรแกรมไพทอนได้ดังนี้

# มีรากเดียว def fn(x): return x**3 + 5*x - 9 # กำหนดวิธีการแบ่งช่วง def bisection( eq, segment, app = 0.3 ): a, b = segment['a'], segment['b'] Fa, Fb = eq(a), eq(b) if Fa * Fb > 0:   raise Exception('No change of sign - bisection not possible')   while( b - a > app ):   x = ( a + b ) / 2.0   f = eq(x)   if f * Fa > 0: a = x   else: b = x  return x #test  print(bisection(fn, {'a':0,'b':5}, 0.00003)) # => 1.32974624634 

ตัวอย่าง: การหารากของพหุนาม

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

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

ประการแรกต้องใช้ตัวเลขสองตัว a และ b เพื่อให้ f(a) และ f(b) มีสัญญาณตรงกันข้าม สำหรับฟังก์ชันข้างต้น a = 1 และ b = 2

เป็นไปตามเกณฑ์นี้เช่น

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

และ

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

เนื่องจากฟังก์ชันเป็นแบบต่อเนื่องต้องมีรากภายในช่วง [1, 2] ในจุดเริ่มต้นจุดสิ้นสุดของช่วงที่วงเล็บรากเป็น a₁ = 1 และ b₁ = 2 ดังนั้นจุดกึ่งกลางคือ

${\displaystyle c_{1}={\frac {2+1}{2}}=1.5}$

ค่าฟังก์ชันที่จุดกึ่งกลางคือ f(c₁) = (1.5)³ - (1.5) - 2 = -0.125 เนื่องจาก f(c₁) เป็นค่าลบ a = 1 จะถูกแทนที่ด้วย a = 1.5 สำหรับการทำซ้ำถัดไปเพื่อให้แน่ใจว่า f(a) และ f(b) มีสัญญาณที่ตรงกันข้าม เช่นนี้ยังคงช่วงระหว่าง a และ b จะกลายเป็นเล็กมากขึ้นบรรจบกับรากของฟังก์ชัน ดูสิ่งนี้เกิดขึ้นในตารางด้านล่าง