Τετάρτη, 28 Ιανουαρίου 2015

Η μέθοδος της διχοτόμησης (αριθμητική επίλυση εξισώσεων μέρος 2)

Τώρα θα εξετάσουμε την μέθοδο της διχοτόμησης. Η ανάρτηση αυτή αποτελεί συνέχεια της ανάρτησης Η μέθοδος Newton-Raphson. Η μέθοδος αυτή βασίζεται στο θεώρημα του Bolzano και είναι η ακόλουθη:

Θέλουμε πάλι να λύσουμε μία εξίσωση της μορφής
σε ένα διάστημα [a,b] για το οποίο ισχύει
Έτσι διχοτομούμε το διάστημα αυτό σε δύο υποδιαστήματα [a,xm] και [xm,b] όπου
Ελέγχουμε αν ισχύει
όπου το ε ένας πολύ μικρός αριθμός. Αν ναι τότε θεωρούμε το xm ρίζα. Αν όχι ελέγχουμε αν ισχύει 
Αν ισχύει η πρώτη ανισότητα απορρίπτουμε το διάστημα [xm,b] αφού η ρίζα βρίσκεται στο διάστημα [a,xm] από το θεώρημα του Bolzano. Έπειτα θέτουμε όπου b το xm και βρίσκουμε ένα νέο xm από την σχέση (1). Αν ισχύει η δεύτερη ανισότητα απορρίπτουμε το διάστημα [a, xm] αφού η ρίζα βρίσκεται στο διάστημα [xm,b] από το θεώρημα του Bolzano. Έτσι θέτουμε όπου a το xm και υπολογίζουμε ένα νέο xm από την σχέση (1). Είτε με τον ένα τρόπο είτε με τον άλλον καταλήγουμε πάντα σε ένα "βελτιωμένο" διάστημα της μορφής [a,b] (που είναι πιο κοντά στην ρίζα). Συνεχίζουμε αυτή την διαδικασία μέχρι να βρούμε κάποια ρίζα ή μέχρι να ξεπεράσουμε κάποιο όριο επαναλήψεων n. Ο αλγόριθμος αυτός υλοποιείται από τον κώδικα:

Private Sub Command1_Click()

'δήλωση των μεταβλητών
Dim flag As Boolean, a As Double, b As Double, xm As Double, n As Integer

'θέτουμε το flag=flase
flag = False

'εισαγωγή των δεδομένων από την φόρμα
a = Text1.Text
b = Text2.Text
n = Text3.Text

'θέτουμε το i=1
i = 1

'ανοίγουμε αρχείο για την εξαγωγή των αποτελεσμάτων
Open "results.txt" For Output As #1

'ελέγχουμε την αρχική συνθήκη για το διάστημα [a,b]
If f(a) * f(b) < 0 Then

'κάνουμε επαναλήψεις μέχρι να βρούμε ρίζα ή να ξεπεράσουμε το όριο των επαναλήψεων
Do Until i > n Or flag = True

'βρίσκουμε το xm
xm = (a + b) / 2

'τυπώνουμε στο αρχείο το i το xm και το f(xm)
Print #1, i, xm, f(xm)

'ελέγχουμε τις συνθήκες για τα διαστήματα [a, xm] και [xm,b]
If f(a) * f(xm) < 0 Then
'θέτουμε όπου b το xm 
b = xm
ElseIf f(b) * f(xm) < 0 Then
'θέτουμε όπου a το xm
a = xm
End If
'αν |f(xm)|<ε όπου ε=0.0001 έχουμε ρίζα
If Abs(f(xm)) < 0.0001 Then
flag = True
End If
i = i + 1

Loop

'αν δεν ισχύει η αρχική συνθήκη για το διάστημα [a,b] τότε παρουσιάζεται το παρακάτω μήνυμα
Else
If MsgBox("δεν συγκλίνει η μέθοδος εξαιτίας των επιλεγμένων a και b", vbOKOnly) = vbOK Then
End If
End If

'δώσε στην φόρμα την ρίζα
Text4.Text = Format(xm, "0.0000")
Close

End Sub

'όρισε την συνάρτηση
Function f(x As Double) As Double
f = x ^ 2 - 5 * x + 6
End Function

Όπως και προηγουμένως αυτός ο κώδικας έχει δημιουργηθεί για να επιλύσει την εξίσωση
Η φόρμα του φαίνεται στην εικόνα 1.

εικόνα 1, φαίνεται η φόρμα εισαγωγής δεδομένων στον κώδικα.

Αρχικά, τρέχουμε τον κώδικα επιλέγοντας ως a το 0 και b το 2.5 και ως όριο των επαναλήψεων θέτουμε πάλι 20. Έτσι παίρνουμε ως ρίζα το 2 (εικόνα 2).

εικόνα 2, η φόρμα μετά το πρώτο τρέξιμο του κώδικα.

Το αρχείο το οποίο παίρνουμε είναι το ακόλουθο:

i              xi                                      f(xi)
1             1.25                                  1.3125 
2             1.875                                0.140625 
3             2.1875                             -0.15234375 
4             2.03125                           -0.0302734375 
5             1.953125                          0.049072265625 
6             1.9921875                        0.00787353515625 
7             2.01171875                     -1.15814208984375E-02 
8             2.001953125                   -1.94931030273438E-03 
9             1.9970703125                  2.93827056884766E-03 
10            1.99951171875               4.88519668579102E-04 
11            2.000732421875            -7.31885433197021E-04 
12            2.0001220703125          -1.22055411338806E-04 
13            1.99981689453125         1.83138996362686E-04 
14            1.99996948242188         3.05185094475746E-05 

Παρατηρούμε ότι έχουμε εύρεση ρίζας μετά από 14 επαναλήψεις. Θέτοντας ως a το 0 και b το 2.5 είναι λογικό να παίρνουμε ως ρίζα το 2 αφού 2ε[0,2.5]. Για να βρούμε την άλλη ρίζα θέτουμε όπου a το 2.5 και b το 5 και τρέχουμε τον κώδικα (πάλι με n=20). Παίρνουμε, όπως είναι αναμενόμενο, ως ρίζα το 3 (εικόνα 3).

εικόνα 3, η φόρμα μετά το δεύτερο τρέξιμο του κώδικα.
Βλέπουμε πάλι το αρχείο του κώδικα:

i              xi                                      f(xi)
1             3.75                                  1.3125
2             3.125                                0.140625
3             2.8125                             -0.15234375
4             2.96875                           -0.0302734375
5             3.046875                          0.049072265625
6             3.0078125                        0.00787353515625
7             2.98828125                     -1.15814208984375E-02
8             2.998046875                   -1.94931030273438E-03
9             3.0029296875                  2.93827056884766E-03
10            3.00048828125               4.88519668579102E-04
11            2.999267578125            -7.31885433197021E-04
12            2.9998779296875          -1.22055411338806E-04
13            3.00018310546875          1.83138996362686E-04
14            3.00003051757813          3.05185094475746E-05

Πάλι έχουμε σύγκλιση μετά από 14 επαναλήψεις. Ας κάνουμε μία ακόμη εκτέλεση του κώδικα με a το -100 και b το 100. Μόλις τρέξουμε τον κώδικα παίρνουμε το μήνυμα της εικόνας 4.

εικόνα 4, το μήνυμα που παίρνουμε για a=-100 και b=100.
Αυτό δεν σημαίνει ότι δεν υπάρχει ρίζα στο διάστημα [-100,100] καθώς έχουμε αποδείξει περίτρανα ότι η εξίσωση έχει ρίζες το 2 και 3. Σημαίνει απλώς ότι η μέθοδος δεν μπορεί να λειτουργήσει αν δεν ισχύει η συνθήκη

Σχόλια και παρατηρήσεις για την μέθοδο Newton-Raphson και για την μέθοδο της διχοτόμησης:
  1. Η μέθοδος Newton-Raphson είναι μία γρήγορη επαναληπτική διαδικασία η οποία στην περίπτωση που δώσουμε αρχική τιμή κοντά στην ρίζα μας υπολογίζει σε λίγες επαναλήψεις την ρίζα, ενώ αν δώσουμε μία απομακρυσμένη τιμή χρειάζεται περισσότερες επαναλήψεις αλλά και πάλι μας δίνει αποτέλεσμα. Το ποια ρίζα της εξίσωσης θα πάρουμε εξαρτάται από την αρχική τιμή.
  2. Η μέθοδος της διχοτόμησης δεν είναι τόσο γρήγορη όσο η Newton-Raphson και έχει ως βασικό περιορισμό το f(a)f(b)<0.
  3. Αν η συνάρτηση f(x) έχει "εύκολη" παράγωγο συνιστάται η μέθοδος Newton-Raphson ενώ αν είναι η παράγωγος της πιο "δύσκολη" να βρεθεί μπορούμε να χρησιμοποιήσουμε την μέθοδο της διχοτόμησης ή και μερικές φορές και απλές συναρτησιακές επαναλήψεις.

2 σχόλια:

  1. Βαγγέλη μου αρέσει η ανάρτηση και συνδυάζει την παρουσίαση
    της μεθόδου, αλλά και τον απαραίτητο κώδικα.
    Μπράβο.

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

      Διαγραφή