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

การแบ่งครึ่งช่วง (อังกฤษ: 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

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

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

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

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

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

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

และ

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

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

$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 จะกลายเป็นเล็กมากขึ้นบรรจบกับรากของฟังก์ชัน ดูสิ่งนี้เกิดขึ้นในตารางด้านล่าง