โจทย์
กำหนดฟังก์ชัน f(x) กับตัวเลข a และ b โดยที่ f(a) * f(b) > 0 และฟังก์ชัน f(x) ควรอยู่ระหว่าง a และ b คือ f(x) = [a, b] งานคือหาค่าของ root ที่อยู่ระหว่างช่วง a และ b ในฟังก์ชัน f(x) โดยใช้ bisection method
Bisection Method คืออะไร?
Bisection method ใช้เพื่อหาค่าของ root ในฟังก์ชัน f(x) ภายในขอบเขตที่กำหนดโดย 'a' และ 'b' Root ของฟังก์ชันสามารถนิยามได้ว่าเป็นค่า a ที่ทำให้ f(a) = 0
ตัวอย่าง
สมการกำลังสอง F(x) = x^2 - 8 สมการนี้เท่ากับ 0 เมื่อค่าของ x เป็น 2 คือ x^2 - 8 = 0 ดังนั้น root ของฟังก์ชันกำลังสอง F(x) นี้คือ 2
ตอนนี้ ถ้าฟังก์ชัน f(x) เป็นต่อเนื่องในช่วง [a..b] ที่กำหนด และเครื่องหมายของ f(a) ≠ เครื่องหมายของ f(b) แล้วจะมีค่า m ที่เป็นสมาชิกของช่วง a และ b ที่ทำให้ f(m) = 0
ค่า m ∈ [a..b] ที่ทำให้ f(m) = 0
เช่น m คือค่าของ root ซึ่งอาจมีหลายค่า
รูปด้านล่างแสดงช่วง f(a) และ f(b) เพื่อหา root ระหว่างช่วงเหล่านี้ ขอบเขตถูกแบ่งเป็นส่วนๆ และเก็บในตัวแปร m คือ
m = (a + b) / 2
หลังจากการแบ่งขอบเขต ช่วงใหม่จะถูกสร้างขึ้นตามรูปด้านล่าง
ตัวอย่าง
Input-: x^3 - x^2 + 2 ; a =-500 and b = 100 Output-: The value of root is : -0.991821 Input-: x^3 - x^2 + 2 ; a =-200 and b = 300 Output-: The value of root is : -1.0025
แนวทางที่ใช้ในโปรแกรมด้านล่าง
- รับสมการและค่าช่วง a และ b
- แบ่งช่วงเป็น: m = (a + b) / 2
- พิมพ์ m คือ root
- ถ้า f(m) ≠ 0
- ตรวจสอบถ้า f(a) * f(m) < 0
- Root จะอยู่ระหว่าง a และ m
- ตรวจสอบถ้า f(b) * f(m) < 0
- Root จะอยู่ระหว่าง b และ m
อัลกอริทึม
เริ่ม
ขั้นตอน 1 → ในฟังก์ชัน double solution(double x)
คืนค่า x*x*x - x*x + 2
ขั้นตอน 2 → ในฟังก์ชัน bisection(double a, double b)
ถ้า solution(a) * solution(b) >= 0 แล้ว
พิมพ์ "You have not assumed right a and b "
คืนค่า
จบถ้า
ตั้งค่า c = a
วนลูป While (b-a) >= EP
ตั้งค่า c = (a+b)/2
ถ้า solution(c) == 0.0
Break
จบถ้า
มิฉะนั้น ถ้า solution(c)*solution(a) < 0
ตั้งค่า b = c
จบมิฉะนั้น
มิฉะนั้น
ตั้งค่า a = c
จบมิฉะนั้น
จบวน
พิมพ์ "The value of root"
ขั้นตอน 3 → ในฟังก์ชัน int main()
ประกาศและเริ่มต้นอินพุต a =-500, b = 100
เรียกฟังก์ชัน bisection(a, b)
หยุด
ตัวอย่างโค้ด C++
#include <iostream>
using namespace std;
#define EP 0.01
// ฟังก์ชันตัวอย่างที่หาคำตอบโดยใช้ Bisection Method ฟังก์ชันคือ x^3 - x^2 + 2
double solution(double x) {
return x*x*x - x*x + 2;
}
// พิมพ์ root ของ solution(x) ด้วย error ใน EPSILON
void bisection(double a, double b) {
if (solution(a) * solution(b) >= 0) {
cout << "You have not assumed right a and b\n";
return;
}
double c = a;
while ((b-a) >= EP) {
// หาจุดกลาง
c = (a+b)/2;
// ตรวจสอบว่าจุดกลางเป็น root หรือไม่
if (solution(c) == 0.0)
break;
// กำหนดด้านที่จะทำซ้ำขั้นตอน
else if (solution(c)*solution(a) < 0)
b = c;
else
a = c;
}
cout << "The value of root is : " << c;
}
// ฟังก์ชันหลัก
int main() {
double a =-500, b = 100;
bisection(a, b);
return 0;
}
ผลลัพธ์
The value of root is : -0.991821
