วิธีการแบ่งส่วน - คืออะไร อัลกอริทึม และตัวอย่าง

วิธีแบ่งส่วนคืออะไร?

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

อย่างไรก็ตาม เนื่องจากกลไกการทำงานนั้นคล้ายคลึงกับอัลกอริทึมการค้นหาแบบไบนารี วิธีการแบ่งครึ่งจึงเรียกอีกอย่างหนึ่งว่าวิธีการค้นหาแบบไบนารี วิธีการแบ่งครึ่ง หรือวิธีการแบ่งแยก โดยวิธีการนี้ใช้ทฤษฎีบทค่ากลางเป็นหลัก

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

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

รากของสมการหมายถึงค่าของตัวแปรอิสระที่เป็นไปตามสมการ ตัวอย่างเช่น รากของสมการ 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

การแสดงภาพกราฟิกของวิธีแบ่งส่วน

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

เริ่มต้นกับ:

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

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

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

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

ขั้นตอน 2) ถ้า f(a)f(b) >=0 แล้วรากจะไม่อยู่ในช่วงเวลานี้ จึงจะไม่มีทางแก้ไขได้

ขั้นตอน 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) หากข้อผิดพลาดสัมบูรณ์สูงกว่าอัตราที่ยอมรับได้หรือ (ba) > e ให้ไปที่ขั้นตอนที่ 3

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

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

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

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

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

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

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

         ฉ(ก) = ฉ(-10) = (-10)3 – (-10)2 + 2 = -1098
         ฉ(ข) = ฉ(10) = (10)3 – (10)2 + 2 = 902
         ฉ(ก)ฉ(ข) = ฉ(-10)ฉ(10) = (-1098)(902) < 0

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

ขั้นตอน 3) จากนั้นจุดกึ่งกลาง c จะถูกคำนวณก่อน

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

(i) ว่า f(c) = 0:
ฉ(ค) = ฉ(0) = (0)3 – (0)2 + 2 = 2 ≠ 0

(ii) ถ้า f(a)f(c) < 0:
ฉ(ค)ฉ(ก) = 2*(-1098) < 0

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

ก = ก = -10
ข = ค = 0

ขั้นตอน 4) เมื่อ (ba) = (0-(-10)) = 10>0.05 กระบวนการจะถูกทำซ้ำ การวนซ้ำครั้งต่อไปจะแสดงในตาราง

การย้ำ	a	b	c	ba	ฉ(ค)
1	-10	0	0	10	2
2	-5	0	-5	5	-148
3	-2.5	0	-2.5	2.5	-19.875
4	-1.25	0	-1.25	1.25	-1.52562
5	-1.25	-0.625	-0.625	0.625	1.36523
6	-1.25	-0.9375	-0.9375	0.3125	0.297119
7	-1.09375	-0.9375	-1.09375	0.15625	-0.50473
8	-1.01562	-0.9375	-1.01562	0.078125	-0.0791054
9	-1.01562	-0.976562	-0.976562	0.0390625	0.115003
10	-1.01562	-0.996094	-0.996094	0.0195312	0.0194703
11	-1.00586	-0.996094	-1.00586	0.00976562	-0.0294344

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

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

รหัสหลอก

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++

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