วิธีแบ่งครึ่ง
การแบ่งครึ่งช่วง (Bisection method) คือการแบ่งออกเป็นสองส่วนเท่ากันในคณิตศาสตร์เป็นวิธีการหารากที่ซ้ำ ๆ การแบ่งออกเป็นสองส่วนเท่ากันช่วงเวลาและจากนั้นเลือกช่วงย่อยซึ่งรากต้องอยู่ในแนวแกน X สำหรับการประมวลผลต่อไป เป็นวิธีที่ง่ายและมีประสิทธิภาพ แต่ก็ยังค่อนข้างช้า ด้วยเหตุนี้มันจึงมักใช้เพื่อหาแนวทางในการแก้ปัญหาโดยประมาณซึ่งใช้เป็นจุดเริ่มต้นของวิธีการบรรจบกันอย่างรวดเร็วมากขึ้น วิธีการนี้เรียกว่าวิธีการลดช่วงเวลา วิธีการค้นหาแบบไบนารี
Steep1: ทำการเดาจุดสองจุดคือค่า X และค่า Xสมมุติว่าค่า X เป็นค่าที่ต่ำกว่าจากนั้นทดสอบว่า f (X) f (X) < 0 ถ้าไม่ใช้ให้หาจุดใหม่ซึ่งจากขั้นตอนนี้ เรารู้ว่ารากจะต้องอยู่ในช่วงนี้
Step 2: ทําการประมาณค่า Root ที่ต้องการที่จุดกึ่งกลางระหว่างสองค่าใน Step 1 โดยคํานวณ
Step 3: หาว่าตอนนี้ Root ที่ต้องการอยู่ในครึ่งไหนดังนี้
3.1 ถ้า f (X) f (X) < 0 แสดงว่า Root ที่ต้องการอยู่ในครึ่งล่าง ให้ตั้ง X= X และกลับไปทํา Step 2
3.2 ถ้า f (X) f (X) > 0 แสดงว่า Root ที่ต้องการอยู่ในครึ่งบน ให้ตั้ง X = X และกลับไปทํา Step 2
3.3 ถ้า f (X) f (X) = 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
ค่าฟังก์ชันที่จุดกึ่งกลางคือ 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 จะกลายเป็นเล็กมากขึ้นบรรจบกับรากของฟังก์ชัน ดูสิ่งนี้เกิดขึ้นในตารางด้านล่าง