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

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

กระบวนการ

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

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

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

 

Bisection method

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

3.2 ถ้า f (X_l) f (X_r) > 0 แสดงว่า Root ที่ต้องการอยู่ในครึ่งบน ให้ตั้ง X_l = X_r และกลับไปทํา Step 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} = 1 และ b_ {1} = 2 ดังนั้นจุดกึ่งกลางคือ

c_{1 = 2 + 1 / 2 = 1.5}

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