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

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

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

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

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

ลำดับที่ 3: หาว่าตอนนี้ Root ที่ต้องการอยู่ในครึ่งไหนดังนี้
ถ้า f(Xl) f(Xr) < 0 แสดงว่า Root ที่ต้องการอยู่ในครึ่งล่าง ให้ตั้ง Xu= Xr และกลับไปทํา ลำดับที่ 2 
ถ้า f(Xl) f(Xr) > 0 แสดงว่า Root ที่ต้องการอยู่ในครึ่งบน ให้ตั้ง Xl = Xr และกลับไปทํา ลำดับที่ 2 
ถ้า f(Xl) f(Xr) = 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

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

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

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



และ

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

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

หมวดหมู่:ขั้นตอนวิธี