อัลกอริทึมวิธีแบ่งครึ่งช่วง พร้อมตัวอย่าง

วิธีการแบ่งครึ่งคืออะไร?

วิธีการแบ่งครึ่งช่วง (Bisection Method) เป็นหนึ่งในเทคนิคเชิงตัวเลขพื้นฐานที่สุดสำหรับการหาค่ารากของสมการพหุนามหรือสมการอดิศัย วิธีการนี้ทำงานโดยการกำหนดช่วงที่ประกอบด้วยราก แล้วแบ่งช่วงนั้นออกเป็นครึ่งในแต่ละรอบการคำนวณ จนกว่าจะพบรากภายในค่าความคลาดเคลื่อนที่ยอมรับได้ เนื่องจากลักษณะการกำหนดช่วงเช่นนี้ วิธีการแบ่งครึ่งช่วงจึงถูกเรียกว่า วิธีการกำหนดช่วง (Bracketing Method) ด้วยเช่นกัน

เนื่องจากกลไกการทำงานคล้ายกับการค้นหาแบบไบนารี วิธีการแบ่งครึ่งจึงเป็นที่รู้จักกันในชื่อ วิธีการค้นหาแบบไบนารี วิธีการแบ่งครึ่ง หรือวิธีการแบ่งสองส่วน วิธีการนี้มีพื้นฐานทางทฤษฎีที่แข็งแกร่ง คือ ทฤษฎีบทค่ากลาง ซึ่งรับประกันว่าฟังก์ชันต่อเนื่องที่เปลี่ยนเครื่องหมายในช่วงหนึ่งจะต้องตัดผ่านศูนย์ที่ใดที่หนึ่งภายในช่วงนั้น

เมื่อเข้าใจความหมายพื้นฐานแล้ว เรามาสำรวจกันว่าเหตุใดการหาคำตอบของสมการจึงมีความสำคัญ และวิธีแบ่งครึ่งช่วง (Bisection Method) เข้ามามีบทบาทในภาพรวมนั้นอย่างไร

การหารากของสมการ

ในการอภิปรายนี้ เราจะเน้นเฉพาะสมการที่มีตัวแปรอิสระเพียงตัวเดียวเท่านั้น สมการดังกล่าวอาจเป็นสมการเชิงเส้นหรือสมการไม่เชิงเส้น สมการเชิงเส้นอธิบายกราฟของเส้นตรง ในขณะที่สมการไม่เชิงเส้นอธิบายเส้นโค้งและรูปทรงที่ซับซ้อนกว่า

รากของสมการคือค่าของตัวแปรอิสระที่สอดคล้องกับสมการนั้น ตัวอย่างเช่น รากของสมการ f(x) = 4 – x² = 0 คือ 2 เพราะ f(2) = 4 – 2² = 0

ให้เราพิจารณา f(x) เป็นฟังก์ชันต่อเนื่องจริง ตามทฤษฎีบทค่ากลาง สมการ f(x) = 0 จะมีรากอย่างน้อยหนึ่งรากอยู่ระหว่าง a และ b เมื่อใดก็ตามที่ f(a)f(b) < 0 กล่าวอีกนัยหนึ่ง ฟังก์ชัน f(x) มีราก “c” อยู่ที่ใดที่หนึ่งระหว่าง a และ b

คุณสมบัติการเปลี่ยนเครื่องหมายนี้เป็นสิ่งที่วิธีการแบ่งครึ่งใช้ประโยชน์อย่างแท้จริง ส่วนถัดไปจะแสดงให้เห็นว่าแนวคิดนี้มีลักษณะอย่างไรในรูปแบบกราฟิก

การแสดงผลเชิงกราฟของวิธีการแบ่งครึ่ง

กราฟต่อไปนี้แสดงกลไกการทำงานของวิธีแบ่งครึ่งช่วง จากกราฟ เราจะเห็นว่ารากที่แท้จริงของสมการถูกทำเครื่องหมายด้วยสีแดง

ขั้นตอนสามารถสรุปได้ดังนี้:

• ขั้นแรก เราเลือกค่าประมาณเริ่มต้นสองค่า คือ a₁ และ b₁ซึ่ง f(a₁)FB₁) < 0. ตามทฤษฎีบทค่ากลาง รากจะต้องอยู่ใน [a₁b₁].
• จากนั้นเราจะคำนวณจุดกึ่งกลางของ₁ และ b₁ซึ่งก็คือ b₂ช่วงเวลาเริ่มต้นลดลงเหลือ [a]₁b₂] เพราะฉ(ก₁)FB₂) < 0
• ในทำนองเดียวกัน ช่วงเวลาจะถูกแบ่งครึ่งอีกครั้งแล้วครั้งเล่า จนกว่าจะพบคำตอบโดยประมาณที่อยู่ในช่วงความคลาดเคลื่อนที่ต้องการ

เมื่อเข้าใจหลักการทางเรขาคณิตอย่างชัดเจนแล้ว เราสามารถกำหนดขั้นตอนอย่างเป็นทางการในรูปแบบของอัลกอริธึมทีละขั้นตอนได้

อัลกอริธึมวิธีการแบ่งส่วน

ขั้นตอนการใช้อัลกอริธึมวิธีแบ่งครึ่งช่วงเพื่อหาคำตอบของสมการ f(x) = 0 มีดังต่อไปนี้

ขั้นตอน 1) เลือกค่าเริ่มต้นที่คาดเดาไว้คือ a, b และอัตราความคลาดเคลื่อนคือ e

ขั้นตอน 2) ถ้า f(a)f(b) >= 0 แสดงว่ารากไม่อยู่ในช่วงนี้ ในกรณีนั้น จะไม่มีคำตอบใดๆ ภายในช่วง [a, b]

ขั้นตอน 3) หาจุดกึ่งกลาง c = (a + b)/2

(i) ถ้าค่าฟังก์ชันที่จุดกึ่งกลาง f(c) = 0 แล้ว c คือราก ไปที่ขั้นตอนที่ 5
(ii) ถ้า f(a)f(c) < 0 รากจะอยู่ระหว่าง a และ c จากนั้นให้กำหนด a = a และ b = c
(iii) มิฉะนั้น ให้กำหนด a = c, b = b

ขั้นตอน 4) ถ้าค่าความคลาดเคลื่อนสัมบูรณ์สูงกว่าอัตราความคลาดเคลื่อนที่ยอมรับได้ นั่นคือ (b – a) > e ให้กลับไปที่ขั้นตอนที่ 3

ขั้นตอน 5) แสดง c เป็นรากโดยประมาณ

เรามาดูตัวอย่างการใช้งานอัลกอริทึมวิธีแบ่งครึ่งช่วง (Bisection Method) กัน เราจะหาค่ารากของฟังก์ชันต่อเนื่องต่อไปนี้โดยใช้สูตรวิธีแบ่งครึ่งช่วง

ฉ(x) = x³ - x² + 2

ตัวอย่างวิธีการแบ่งส่วน

ขั้นตอน 1) สมมติว่า...

         ก = -10,
         ข = 10 และ
         e = 1% หรือ 0.01

ขั้นตอน 2) ตอนนี้เราจะตรวจสอบว่า f(a)f(b) >= 0 หรือไม่

         f(a) = f(-10) = (-10)³ – (-10)² +2 = -1098
         f(b) = f(10) = (10)³ - (10)² +2 = 902
         ฉ(ก)ฉ(ข) = ฉ(-10)ฉ(10) = (-1098)(902) < 0

ดังนั้น รากของฟังก์ชันข้างต้นจึงอยู่ในช่วง [-10, 10]

ขั้นตอน 3) ขั้นตอนต่อไปคือการคำนวณจุดกึ่งกลาง c

ตอนนี้จะต้องตรวจสอบเงื่อนไขต่อไปนี้:

(i) ว่า f(c) = 0 หรือไม่:
         f(c) = f(0) = (0)³ - (0)² + 2 = 2 ซึ่งไม่เท่ากับ 0

(ii) ว่า f(a)f(c) < 0 หรือไม่:
         f(c)f(a) = 2 * (-1098) < 0

เงื่อนไขเป็นไปตามที่กำหนด สำหรับการวนซ้ำครั้งต่อไป ค่าต่างๆ จะเป็นดังนี้:

         ก = ก = -10
         ข = ค = 0

ขั้นตอน 4) เนื่องจาก (b – a) = (0 – (-10)) = 10 > 0.01 กระบวนการจึงถูกทำซ้ำ การทำซ้ำครั้งต่อไปแสดงอยู่ในตารางด้านล่าง

ขั้นตอน 5) ในการวนซ้ำครั้งที่ 11 เงื่อนไขในขั้นตอนที่ 4 จะกลายเป็นเท็จ ดังนั้น รากโดยประมาณของสมการนี้คือ -1.00586

เมื่อยกตัวอย่างเชิงตัวเลขเสร็จแล้ว ส่วนถัดไปจะนำเสนอแผนภาพเชิงตรรกะที่แสดงการไหลของการควบคุมทั้งหมด

แผนภาพลอจิกวิธีการแบ่งส่วน

ผังงานด้านล่างนี้สรุปตรรกะการตัดสินใจของวิธีการแบ่งครึ่งช่วง รวมถึงการตรวจสอบขอบเขต การปรับปรุงจุดกึ่งกลาง และการทดสอบค่าความคลาดเคลื่อน

หลอกCode

รหัสเทียมด้านล่างนี้สะท้อนถึงอัลกอริทึมและทำหน้าที่เป็นแบบแผนสำหรับการนำวิธีการแบ่งครึ่งช่วงไปใช้ในภาษาโปรแกรมใดๆ ก็ได้

Start
Set a, b, e
if f(a)*f(b) >= 0
    Output("Root does not exist in this interval")
    Stop
while (b-a) > e do
    c ← (a + b)/2
    if f(c) = 0
        break
    end if
    if f(c)*f(a) < 0 then
        b ← c
    else
        a ← c
end while
Output(c)
Stop

ตัวอย่างวิธีการแบ่งส่วนในภาษา C/C++

ต่อไปนี้ C/C++ โปรแกรมนี้ใช้วิธีแบ่งครึ่งช่วงเพื่อหาค่ารากของ f(x) = x³ - x² + 2 ภายในช่วง [-10, 10]

Input:

#include <bits/stdc++.h>
using namespace std;
#define Error 0.01
double value(double x)
{
    return x*x*x - x*x + 2;
}
void bisection_method(double a, double b)
{
    if (value(a) * value(b) >= 0)
    {
        cout << "The root does not lie in this interval\n";
        return;
    }
    double c = a;
    while ((b-a) >= Error)
    {
        c = (a+b)/2;
        if (value(c) == 0.0)
            break;
        else if (value(c)*value(a) < 0)
            b = c;
        else
            a = c;
    }
    cout << "The root is :" << c;
}
int main()
{
    double a = -10, b = 10;
    bisection_method(a, b);
    return 0;
}

Output:

The root is :-1.00586

ตัวอย่างวิธีการแบ่งส่วนใน Python

การขอ Python เวอร์ชันด้านล่างนี้ให้ผลลัพธ์เป็นรากโดยประมาณเดียวกันโดยใช้ตรรกะเดียวกัน ทำให้เหมาะสำหรับการทดลองอย่างรวดเร็วและการสอน

Input:

def value(x):
    return x*x*x - x*x + 2

def bisection_method(a, b):
    if (value(a) * value(b) >= 0):
        return
    c = a
    while ((b-a) >= 0.01):
        c = (a+b)/2
        if (value(c) == 0.0):
            break
        if (value(c)*value(a) < 0):
            b = c
        else:
            a = c
    print("The root is : ", "%.4f" % c)

a = -10
b = 10
bisection_method(a, b)

Output:

The root is :  -1.0059

ข้อดีและข้อจำกัดของวิธีการแบ่งครึ่ง

เช่นเดียวกับเทคนิคเชิงตัวเลขทุกวิธี วิธีการแบ่งครึ่งช่วงมีจุดแข็งที่ชัดเจนและข้อเสียในทางปฏิบัติอยู่บ้าง ตารางด้านล่างสรุปข้อดีและข้อเสียที่สำคัญที่สุด

การประยุกต์ใช้ของวิธีการแบ่งครึ่ง

วิธีการแบ่งครึ่งช่วง (Bisection Method) ถูกนำมาใช้ในสถานการณ์การคำนวณเชิงปฏิบัติและสมัยใหม่หลายอย่างที่ต้องการขั้นตอนการหาค่ารากที่แม่นยำและเชื่อถือได้

• การจำลองทางวิศวกรรม: การแก้สมการไม่เชิงเส้นที่ปรากฏในด้านการถ่ายเทความร้อน พลศาสตร์ของไหล และการวิเคราะห์โครงสร้าง
• การสร้างแบบจำลองทางการเงิน: การคำนวณผลตอบแทน อัตราผลตอบแทนภายใน และจุดคุ้มทุน ในกรณีที่ไม่มีสูตรสำเร็จรูปสำหรับการคำนวณ
• การเรียนรู้ของเครื่องจักรและปัญญาประดิษฐ์: การระบุค่าเกณฑ์ การปรับเทียบแบบจำลอง และการปรับค่าพารามิเตอร์ภายในตัวแก้ปัญหาเชิงตัวเลขที่ขับเคลื่อนด้วย AI
• กราฟิกคอมพิวเตอร์: การหาจุดตัดระหว่างรังสีกับพื้นผิว และค่าพารามิเตอร์ตามเส้นโค้ง
• ระบบฝังตัว: การประมาณค่ารากในตัวควบคุมที่มีทรัพยากรจำกัด ซึ่งความเรียบง่ายและความสามารถในการคาดการณ์มีความสำคัญมากกว่าความเร็ว

คำถามที่พบบ่อย