Αλγόριθμος Μεθόδου Διχοτόμησης με Παραδείγματα

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

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

Δεδομένου ότι ο μηχανισμός λειτουργίας της μοιάζει με δυαδική αναζήτηση, η Μέθοδος Διχοτομίας είναι επίσης γνωστή ως μέθοδος δυαδικής αναζήτησης, μέθοδος διχοτόμησης ή μέθοδος διχοτομίας. Βασίζεται σε μια ισχυρή θεωρητική βάση: το Θεώρημα Ενδιάμεσης Τιμής, το οποίο εγγυάται ότι μια συνεχής συνάρτηση που αλλάζει πρόσημο σε ένα διάστημα πρέπει να μηδενίζεται κάπου μέσα σε αυτό το διάστημα.

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

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

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

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

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

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

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

Η διαδικασία μπορεί να συνοψιστεί ως εξής:

• Αρχικά επιλέγουμε δύο αρχικές εικασίες, μια₁ και β₁, για το οποίο f(a₁) στ(β₁) < 0. Σύμφωνα με το Θεώρημα Ενδιάμεσης Τιμής, η ρίζα πρέπει να βρίσκεται στο [a₁, β₁].
• Στη συνέχεια υπολογίζουμε το μέσο σημείο ενός₁ και β₁, το οποίο είναι β₂Το αρχικό διάστημα μειώνεται τώρα σε [a₁, β₂] επειδή f(a₁) στ(β₂) < 0.
• Με τον ίδιο τρόπο, το διάστημα μειώνεται στο μισό ξανά και ξανά μέχρι να βρεθεί μια κατά προσέγγιση λύση εντός της επιθυμητής ανοχής.

Έχοντας σαφή τη γεωμετρική διαίσθηση, μπορούμε τώρα να τυποποιήσουμε τη διαδικασία ως έναν αλγόριθμο βήμα προς βήμα.

Αλγόριθμος μεθόδου διχοτόμησης

Τα βήματα για την εφαρμογή του αλγορίθμου της Μεθόδου Διχοτόμησης για την εύρεση της ρίζας της εξίσωσης f(x) = 0 είναι τα εξής.

Βήμα 1) Επιλέξτε αρχικές εικασίες a, b και a ποσοστό ανοχής 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 ως κατά προσέγγιση ρίζα.

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

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

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

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

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

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

         f(α) = f(-10) = (-10)³ – (-10)² + 2 = -1098
         f(β) = f(10) = (10)³ - (10)² + 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)³ - (0)² + 2 = 2, το οποίο δεν είναι ίσο με 0.

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

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

         a = a = -10
         b = c = 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³ - Χ² + 2 εντός του διαστήματος [-10, 10].

εισόδου:

#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

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

εισόδου:

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)

Παραγωγή:

The root is :  -1.0059

Πλεονεκτήματα και περιορισμοί της μεθόδου διχοτόμησης

Όπως κάθε αριθμητική τεχνική, η Μέθοδος Διχοτόμησης έχει σαφή πλεονεκτήματα και μερικά πρακτικά μειονεκτήματα. Ο παρακάτω πίνακας συνοψίζει τα σημαντικότερα πλεονεκτήματα και μειονεκτήματα.

Εφαρμογές της μεθόδου διχοτόμησης

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

• Μηχανικές προσομοιώσεις: Επίλυση μη γραμμικών εξισώσεων που εμφανίζονται στη μεταφορά θερμότητας, τη ρευστοδυναμική και τη δομική ανάλυση.
• Χρηματοοικονομική μοντελοποίηση: Υπολογισμός αποδόσεων, εσωτερικών ποσοστών απόδοσης και σημείων νεκρού σημείου όπου δεν υπάρχουν λύσεις κλειστής μορφής.
• Μηχανική μάθηση και Τεχνητή Νοημοσύνη: Εντοπισμός κατωφλίων, βαθμονόμηση μοντέλων και ρύθμιση υπερπαραμέτρων μέσα σε αριθμητικούς επιλυτές που βασίζονται σε τεχνητή νοημοσύνη.
• Γραφικά υπολογιστή: Προσδιορισμός των τομών ακτίνας-επιφάνειας και των τιμών των παραμέτρων κατά μήκος των καμπυλών.
• Ενσωματωμένα συστήματα: Προσέγγιση των ριζών σε ελεγκτές χαμηλών πόρων όπου η απλότητα και η προβλεψιμότητα είναι πιο πολύτιμες από την ταχύτητα.

Συχνές Ερωτήσεις