Bisection

อ่านก่อน

Bisection เป็นวิธีหาค่า root ของฟังก์ชัน หรือหา x ที่ทำให้ฟังก์ชัน f(x) = 0 การหารากต้องระบุช่วง [start, stop] รากต้องอยู่ในช่วงดังกล่าว การหารากเริ่มจากการแบ่งครึ่งช่วง ดูว่าที่จุดกึ่งกลางเป็นรากหรือไม่ ถ้าไม่ใช่ ก็เปลี่ยนช่วงใหม่ ช่วงใหม่จะเป็น [half, stop] ถ้า เครื่องหมาย + – หน้า f(start) กับ f(half) เหมือนกัน ถ้าเครื่องหมายต่างกัน ช่วงใหม่คือ [start, half] จากนั้นก็ทำซ้ำ (แบ่งครึ่ง, ตรวจสอบ, หาช่วงใหม่, …)

อินพุท

  • fn : ฟังก์ชันที่ต้องการหาราก
  • start : ค่าเริ่มต้นของช่วง
  • stop : ค่าสิ้นสุดของช่วง
  • e : ค่าความผิดพลาดที่ยอมรับได้
  • round : จำนวนรอบสูงสุด
def bisection(fn, start, stop, e = 0.00001, round = 1000)

เอาท์พุท

  • x ที่ทำให้ฟังก์ชัน fn มีค่าเท่ากับ 0 (หรือใกล้เคียง)

กรณีที่หาไม่พบภายในรอบที่กำหนด จะ raise Exception

โค้ดทั้งหมด

def bisection(fn, start, stop, e = 0.00001, round = 1000)
  for i in 1..round
    half = start + (stop - start) / 2.0
    
    #return half if fn.call(half) == 0 or (stop - start) / 2.0 < e
    return half if fn.call(half).abs < e
      
    if fn.call(half) * fn.call(start) > 0
      start = half
    else
      stop = half
    end
  end

  raise "Cannot find root in the range (#{start}, #{stop})"
end

เงื่อนไขการจบที่นำมาจากหนังสือคือเงื่อนไขที่ผม comment ไว้

ผมเขียนเงื่อนไขการจบใหม่ คือค่าที่หาได้ต้องใกล้เคียงกับ 0

การใช้งาน

หารากของสมการ x^5 + x^3 + x^2 – 1 = 0 ในช่วง [0, 1] (โจทย์จากหนังสือ ระเบียบวิธีเชิงตัวเลข โดย ดร.ธนาวุฒิ ประกอบผล)

f = lambda { |x| return x**5 + x**3 +x**2 - 1 }
x = bisection(f, 0, 1)
puts "f(#{x}) = #{f.call(x)}"

ผลการรัน


f(0.699737548828125) = 2.142188673559531e-06

คำตอบคือ 0.699737548828125

ซึ่ง f(0.699737548828125) = 2.142188673559531e-06 = 0.000002142188673559531 ซึ่งใกล้กับ 0

หากจะนำโค้ดหรือข้อความไปใช้ ต้องแสดงที่มา และห้ามใช้ในเชิงพาณิชย์

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s