next up previous contents
Next: Μηδενικά των πολυωνύμων Up: ΜΗ ΓΡΑΜΜΙΚΕΣ ΕΞΙΣΩΣΕΙΣ ΣΕ Previous: Γραμμική κλασματική παρεμβολή   Contents

13#13 μέθοδος

Μέθοδοι ταχείας σύγκλισης για την επίλυση μη γραμμικών εξισώσεων όπως η μέθοδος του Νεύτονα, η μέθοδος της τέμνουσας και άλλοι τύποι μεθόδων που βασίζονται στην παρεμβολή είναι ανασφαλείς στο ότι μπορεί να μην συγκλίνουν εκτός εάν ξεκίνησουν αρκετά κοντά στη λύση. Ασφαλής μέθοδοι όπως η διχοτόμηση από την άλλη πλευρά είναι αργές και γι' αυτό ακριβές. Ποια πρέπει κάποιος να διαλέξει; Μία λύση σ' αυτό το δίλημμα παρέχεται από υβριδικές μεθόδους που συνδυάζουν χαρακτηριστικά και των δύο ειδών μεθόδων. Για παράδειγμα ένας μπορεί να χρησιμοποιήσει μία μέθοδο ταχείας σύγκλισης αλλά να διατηρήσει ένα διάστημα (1061#1061) γύρω από τη λύση. Εάν η επόμενη κατά προσέγγιση λύση που δίνεται από το γρήγορο αλγόριθμο πέσει εκτός του διαστήματος 1061#1061. Κάποιος θα επιστρέψει σε μία ασφαλή μέθοδο όπως η διχοτόμηση για μια επανάληψη. Τότε κάποιος μπορεί να δοκιμάσει την ταχεία μέθοδο ξανά σε ένα μικρότερο διάστημα με μεγαλύτερη πιθανότητα επιτυχίας. Τελικά η τάξη ταχείας σύγκλισης θα επικρατήσει. Αυτή η προσέγγιση σπάνια αποδίδει χειρότερα απ' ότι η αργή μέθοδος και συνήθως καλύτερα. Μία δημοφιλής υλοποίηση μίας τέτοιας υβριδικής προσέγγισης αναπτύχθηκε αρχικά από 1179#1179 και 1180#1180 και αργότερα βελτιώθηκε από τον 1181#1181. Αυτή η μέθοδος που βρίσκεται σ' έναν αριθμό από υπορουτίνες βιβλιοθηκών, συνδυάζει την ασφάλεια της διχοτόμησης με την ταχύτερη σύγκλιση της αντίστροφης τετραγωνικής παρεμβολής. Μία προσεκτική υλοποίηση πρέπει να διευθύνει έναν αριθμό από δυνητικές παγίδες σε αριθμητική κινούμενης υποδιαστολής, όπως υπο(εκ)χείλιση, υπερ(εκ)χείλιση ή μία μη ρεαλιστικά στενή αποδοχή λαθών, που παρέχεται από το χρήστη.



Manolis Vavalis 2000-03-24