Μάθημα 1 - Μέθοδος διχοτόμησης - διάλεξη 1/10/2014

Εφαρμοσμένα Μαθηματικά : Μάθημα 1^ο . 1/10/2014

Μέθοδος Διχοτόμησης:

Έστω (1) f(x)=0

Από το γενικευμένο θεώρημα Bolzano έχουμε ότι:

Εάν f συνεχής στην (1) στο διάστημα <α,β> και υπάρχουν τα όρια:

(i)Limf(x), x->α+ και (ii)Limf(x), x->β-

Έτσι ώστε (i)*(ii)<0 τότε υπάρχει μια τουλάχιστον ρίζα της (1) στο (α,β)

Μεθοδολογία:

1)      Παίρνουμε το μέσο M1=(α+β)/2.

2)      Επαληθεύουμε στο f(Μ1).

3)      Εάν f(M1)<0 τότε στο [Μ1, β] υπάρχει ρίζα και Μ2=(Μ1+β)/2 κλπ.

αλλιώς εάν f(M1)>0 τότε η ρίζα υπάρχει στο [α, Μ1] και Μ2=(α+Μ1)/2 κλπ.

4)      Έτσι έχουμε Μ1,Μ2,Μ3....Μν -> Ρ άρα f(Ρ)=0

Ακρίβεια

Το ερώτημα που γεννάτε τώρα είναι το στα πόσα Μν σταματάμε;

Έστω |Μν-Ρ|<ε, όπου ε είναι η ακρίβεια που θέλουμε να έχουμε από την ρίζα.

Τότε |Μ1-Ρ|<(β-α)/2 και |Μ2-Ρ|<((β-α)/2)/2 κλπ, καταλήγουμε στο γενικευμένο (β-α)/2^n

Εάν ((β-α)/2^n)<ε λύνοντας ως προς n έχουμε n> (ln(β-α)-ln(ε))/ln(2)

Η οποία ανήσωση δεν αλλάζει φορά λόγω του ότι η ln είναι γνησίως αύξουσα.

Παρατήρηση:

Υπάρχει σοβαρή πιθανότητα το n να βγει δεκαδικός αριθμός, οπότε παίρνουμε κάνουμε πλήθος βημάτων στον αμέσως επόμενο ακέραιο αριθμό π.χ εάν n>6.5 τότε κάνουμε 7 βήματα.

Παράδειγμα 1.

f(x)=x^5+x-1=0, και ε=1/100

Παρατηρούμε ότι είναι συνεχής ως πολυωνυμική. Και το πεδίο ορισμού είναι το [0,1]

f(0)=-1<0

f(1)=1>0

Ακουλουθώντας τον παραπάνω αλγόριθμο βρίσκουμε το πλήθος των βημάτων:

n>((ln(1-0)-ln(1/100))/ln(2)= 6.64 ~ 7

Βρίσκουμε το M1, M1=(β-α)/2= (1-0)/2 = ½

Επαληθεύουμε στο f(M1)=(1/2)^5+(1/2)-1= -0.46875, άρα Μ1<0 κατά συνέπεια το «α» αντικαθήσταται από το Μ1. Δηλαδή το νέο διάστημα είναι [1/2, 1]

Βρίσκουμε το Μ1, Μ2=(1/2+1)/2=3/4, επαληθεύοντας στο f(M2) έχουμε -0.00126 άρα f(M2)<0 άρα το Μ1 αντικαθήσταται από το Μ2. Δηλαδή το νέο διάστημα είναι [3/4, 1]

Μ3=(Μ2+-β)/2= ((3/4)+1)/2= 7/8, επαληθεύοντας στο f(M3) έχουμε 0.3879 άρα το Μ3 αντικαθηστά το «β» και το νέο διάστημα είναι [3/4, 7/8]

Μ4=(Μ2+Μ3)/2= ((3/4)+(7/8))/2= 13/16, επαληθεύοντας στο f(M4) έχουμε 0,166>0 άρα αντικαθηστά το «β» και το νέο διάστημα είναι [3/4, 13/16]

Βρίσκουμε Μ5= 25/32. Με f(M5)=0.072 άρα το Μ5>0 άρα το νέο διάστημα είναι [3/4 , 25/32]

Βρίσκουμε Μ6= 49/64 και το f(M6)= 0.028 άρα M6>0 άρα το νέο διάστημα είναι [3/4, 49/64]

Και Μ7= 97/128 με f(M7)= 0.0077.

Παράδειγμα 2: Τριγωνομετρικό πολυώνυμο

Cosx=2x μεταφέροντας το 2x στο αριστερό μέλος έχουμε f(x)=cosx-2x=0 και ε=1/100

Με πεδίο ορισμού [0, π/2]

Βρίσκουμε πλήθος βημάτων n>8

Μ1=π/4 με f(M1)= -0.8636 άρα Μ1<0 και το νέο διάστημα γίνεται [0, π/4]

Μ2=π/8 με f(M2)=0.138>0 άρα το νέο διάστημα είναι [π/8, π/4]

Μ3=3π/16 με f(M3)=-0.34<0 άρα το νέο διάστημα είναι [π/8, 3π/16]

Μ4=5π/32 με f(M4)=-0.099<0 άρα το νέο διάστημα είναι [π/8, 5π/32]

M5=9π/64 με f(M5)=0.02>0 άρα το νέο διάστημα είναι [9π/64, 5π/32]

Μ6=19π/128 με f(M6)=-0.039<0 άρα το νέο διάστημα είναι [9π/64 ,19π/128]

M7= 37π/256 με f(M7)=-0.009<0 άρα το νέο διάστημα είναι [37π/256, 19π/128]

Μ8=73π/215 με f(M8)=0.001