Μέθοδος διχοτόμησης – Τι είναι, Αλγόριθμος και Παράδειγμα

Τι είναι η μέθοδος διχοτόμησης;

Η μέθοδος διχοτόμησης είναι μια από τις βασικές αριθμητικές λύσεις για την εύρεση της ρίζας μιας πολυωνυμικής εξίσωσης. Περιλαμβάνει το διάστημα στο οποίο βρίσκεται η ρίζα της εξίσωσης και τις υποδιαιρεί στα μισά σε κάθε επανάληψη μέχρι να βρει τη ρίζα. Έτσι, η μέθοδος διχοτόμησης ονομάζεται επίσης μέθοδος bracketing.

Ωστόσο, καθώς ο μηχανισμός εργασίας είναι παρόμοιος με τον αλγόριθμο δυαδικής αναζήτησης, η μέθοδος διχοτόμησης είναι επίσης γνωστή ως μέθοδος δυαδικής αναζήτησης, μέθοδος κατά το ήμισυ ή μέθοδος διχοτομίας. Βασίζεται κυρίως στο θεώρημα της ενδιάμεσης τιμής.

Εύρεση ριζών εξισώσεων

Σε αυτό το παράδειγμα, εξετάζουμε μόνο εξισώσεις με μία ανεξάρτητη μεταβλητή. Μπορεί να είναι είτε γραμμικό είτε μη γραμμικό. Οι γραμμικές εξισώσεις χρησιμοποιούνται για την αναπαράσταση της γραφικής παράστασης μιας ευθείας γραμμής, ενώ οι μη γραμμικές εξισώσεις για την αναπαράσταση καμπυλών.

Η ρίζα μιας εξίσωσης σημαίνει την τιμή της ανεξάρτητης μεταβλητής που ικανοποιεί την εξίσωση. Για παράδειγμα: η ρίζα μιας εξίσωσης 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," μεταξύ α και β.

Γραφική αναπαράσταση της μεθόδου διχοτόμησης

Το παρακάτω γράφημα αναπαριστά τον μηχανισμό λειτουργίας της μεθόδου διχοτόμησης. Από το γράφημα, μπορούμε να δούμε ότι η ρίζα της εξίσωσης σημειώνεται με κόκκινο χρώμα.

Για αρχή:

Πρώτα πήραμε δύο αρχικές εικασίες, α₁ και β_1, για το οποίο f(a₁) στ(β₁) < 0. Σύμφωνα με το θεώρημα της ενδιάμεσης τιμής, η ρίζα πρέπει να βρίσκεται στο [a₁, β₁].
Μπορούμε να βρούμε το μέσο του α₁ και β_1,που είναι β₂. Έτσι, το αρχικό διάστημα μειώνεται τώρα σε [a₁, β₂] επειδή f(a₁) στ(β₂) < 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 ως κατά προσέγγιση ρίζα.

Ας δούμε ένα παράδειγμα του αλγόριθμου της μεθόδου διχοτόμησης.
Πρέπει να βρούμε τη ρίζα της ακόλουθης συνεχούς συνάρτησης χρησιμοποιώντας τον τύπο της μεθόδου διχοτόμησης.

f (x) = x³ - Χ² + 2

Παράδειγμα μεθόδου διχοτόμησης

Βήμα 1) Ας υποθέσουμε,

         a = -10,
         b = 10, και
         e = 1% ή 0.01

Βήμα 2) Τώρα, θα ελέγξουμε εάν f(a)f(b) >= 0 ή όχι.

         f(a) = f(-10) = (-10)3 – (-10)2 + 2 = -1098
         f(b) = f(10) = (10)3 – (10)2 + 2 = 902
         f(a)f(b) = f(-10)f(10) = (-1098)(902) < 0

Επομένως, η ρίζα της παραπάνω συνάρτησης βρίσκεται σε αυτό το διάστημα [-10, 10].

Βήμα 3) Τότε πρώτα θα υπολογιστεί το μέσο c.

Τώρα πρέπει να ελεγχθούν οι ακόλουθες συνθήκες:

(i) εάν f(c) = 0:
f(c) = f(0) = (0)3 – (0)2 + 2 = 2 ≠ 0

(ii) εάν f(a)f(c) < 0:
f(c)f(a) = 2*(-1098) < 0

Η προϋπόθεση πληρούται. Για την επόμενη επανάληψη, οι τιμές θα είναι:

a = a = -10
b = c = 0

Βήμα 4) Ως (ba) = (0-(-10)) = 10>0.05, η διαδικασία θα επαναληφθεί. Οι επόμενες επαναλήψεις φαίνονται στον πίνακα.

Επανάληψη	a	b	c	βα	f(c)
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++

εισόδου:

#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;
}

Παραγωγή:

The root is :-1.00586

Παράδειγμα μεθόδου διχοτόμησης σε Python