Ξεχάσατε τον κωδικό σας?
ΜΕΘΟΔΟΣ ΔΙΧΟΤΟΜΗΣΗΣ
Document Actions
Next: Επαναλήψεις σταθερού σημείου Up: ΜΗ ΓΡΑΜΜΙΚΕΣ ΕΞΙΣΩΣΕΙΣ ΣΕ Previous: ΜΗ ΓΡΑΜΜΙΚΕΣ ΕΞΙΣΩΣΕΙΣ ΣΕ Contents
ΜΕΘΟΔΟΣ ΔΙΧΟΤΟΜΗΣΗΣ
Στην αριθμητική περιορισμένης ακρίβειας, μπορεί να μην υπάρχει κάποιος αριθμός κινούμενης υποδιαστολής 33#33 τέτοιος ώστε η 34#34 να είναι ακριβώς μηδέν. Εναλλακτικά, μπορείτε να ψάξετε για ένα μικρό διάστημα 1060#1060 στο οποίο η 51#51 έχει αλλαγή πρόσημου, αφού η αντίστοιχη συνεχής συνάρτηση πρέπει να μηδενιστεί κάπου μέσα σε ένα τέτοιο διάστημα. Ένα διάστημα στο οποίο το πρόσημο της 51#51 να διαφέρει στις άκρες του ονομάζεται 1061#1061. Η μέθοδος διχοτόμησης ξεκινάει με ένα αρχικό 1061#1061 και μειώνει διαδοχικά το μήκος του μέχρι να απομονωθεί η λύση με όση ακρίβεια είναι επιθυμητή. Σε κάθε επανάληψη, η συνάρτηση υπολογίζεται στη μέση του συγκεκριμένου διαστήματος, και έτσι διατηρείται μόνο το μισό του διαστήματος, ανάλογα με το πρόσημο της συνάρτησης στη μέση του διαστήματος. Πιο τυπικά, ο αλγόριθμος είναι ο εξής, όπου 1062#1062 αν 1063#1063 και 1064#1064 αν 1065#1065: Αρχικά δεδομένα εισόδου: Μία συνάρτηση 51#51, ένα διάστημα [α, β] τέτοιο ώστε 1066#1066 και ανοχή λάθους 1067#1067.
1068#1068
1069#1069
1070#1070
1071#1071
1072#1072
1073#1073
849#849
849#849
Για το αρχικό 1061#1061 διάστημα [α, β], παίρνουμε 1075#1075 και 1076#1076. Αυτό που έχει σημασία είναι οι τιμές της συνάρτησης στις δύο άκρες να διαφέρουν στο πρόσημο. Υπολογίζουμε την τιμή της συνάρτησης στο μέσο του διαστήματος 1077#1077 και βρίσκουμε ότι η 1078#1078 έχει αντίθετο πρόσημο από την 1079#1079, οπότε διατηρούμε το πρώτο μισό του αρχικού διαστήματος θέτοντας 1073#1073. Τότε επαναλαμβάνουμε τη διαδικασία μέχρι το 1061#1061 διάστημα να απομονώσει τη ρίζα της εξίσωσης με όση ακρίβεια επιθυμούμε. Η ακολουθία των επαναλήψεων φαίνεται εδώ.
1080#1080
Η μέθοδος διχοτόμησης δεν χρησιμοποιεί τον βαθμό(1081#1081) των τιμών της συνάρτησης, παρά μόνο το πρόσημό τους. Ως αποτέλεσμα, η διχοτόμηση συγκλίνει σίγουρα, αλλά το κάνει σχετικά αργά. Συγκεκριμένα, σε κάθε επιτυχής επανάληψη το μήκος του διαστήματος που περιέχει τη λύση, οπότε και τα όρια του πιθανού λάθους, μειώνονται στο μισό. Αυτό σημαίνει ότι η μέθοδος διχοτόμησης είναι γραμμικά συγκλίνων, με 1054#1054 και 1082#1082. Ένας άλλος τρόπος να εκφραστεί αυτό είναι ότι κερδίζουμε ένα 118#118 ακρίβειας στη προσεγγιστική λύση με κάθε επανάληψη της διχοτόμησης. Έχοντας ένα αρχικό διάστημα 1060#1060, το μήκος του διαστήματος ύστερα από 432#432 επαναλήψεις είναι 1083#1083, έτσι ώστε για να επιτευχθεί ανοχή λάθους 1067#1067 απαιτούνται
επαναλήψεις, ασχέτως της συγκεκριμένης συνάρτησης 51#51.
Manolis Vavalis 2000-03-24
