Μέθοδος της τέμνουσας
Next: ΑΝΤΙΣΤΡΟΦΗ ΠΑΡΕΜΒΟΛΗ Up: ΜΗ ΓΡΑΜΜΙΚΕΣ ΕΞΙΣΩΣΕΙΣ ΣΕ Previous: ΜΕΘΟΔΟΣ ΤΟΥ ΝΕΥΤΟΝΟΣ.   Contents
Μέθοδος της τέμνουσας
Ένα μειονέκτημα της μεθόδου του Νεύτωνος είναι ότι τόσο η συνάρτηση όσο και το παράγωγο της πρέπει να εκτιμώνται σε κάθε επανάληψη. Το παράγωγο μπορεί να είναι άβολο ή ακριβό να εκτιμηθεί, έτσι πρέπει να σκεφτούμε να το προσεγγίσουμε μέσω μίας πεπερασμένης διαφοράς πηλίκου πάνω από μία μικρή 1136#1136 63#63, όπως στο Παράδειγμα 1.11, αλλά αυτό θα απαιτούσε μία δεύτερη εκτίμηση της συνάρτησης για κάθε επανάληψη καθαρά μόνο για την απόκτηση των παραγώγων πληροφοριών ( 1137#1137). Μία καλύτερη ιδέα είναι να βασίσουμε την πεπερασμένη διαφορά προσέγγισης σε επιτυχής επαναλήψεις, όπου η συνάρτηση πρέπει να υπολογίζεται ούτως ή άλλως. Αυτή η προσέγγιση δίνει μία μέθοδο της τέμνουσας:
Μία μέθοδος της τέμνουσας μπορεί να 1139#1139 καθώς προσεγγίζεται η συνάρτηση 51#51 από τη διατέμνουσα γραμμή μέσα από τις προηγούμενες δύο επαναλήψεις, και παίρνοντας το μηδέν της 1140#1140 γραμμικής συνάρτησης να είναι η προσεγγιστική λύση όπως παρουσιάστηκε στο Σχεδιάγραμμα 5.6.
ΣΧΕΔΙΑΓΡΑΜΜΑ 5.6 Μέθοδος της τέμνουσας για την επίλυση μη γραμμικών εξισώσεων,
Παίρνουμε 1142#1142 και 1143#1143 ως δύο αρχικές προβλέψεις για τη λύση. Υπολογίζουμε τη συνάρτηση για κάθε ένα από τα δύο σημεία και παράγουμε νέες προσεγγιστικές λύσεις τοποθετώντας μία ευθεία γραμμή στις δύο τιμές της συνάρτησης ανάλογα με τον τύπο της τέμνουσας. Τότε επαναλαμβάνουμε τη διαδικασία χρησιμοποιώντας τη νέα αυτή τιμή και τις πιο πρόσφατες των προηγούμενων δύο τιμών. Σημειώστε ότι μόνο ένας υπολογισμός της συνάρτησης είναι απαραίτητος σε κάθε επανάληψη. Η σειρά των επαναλήψεων φαίνεται παρακάτω, όπου 63#63 συμβολίζει τη μεταβολή του 33#33 σε κάθε επανάληψη.
Επειδή κάθε νέα προσεγγιστική λύση που παράγεται από τη μέθοδο της τεμνουσας εξαρτάται από τις προηγούμενες δύο επαναλήψεις, η συγκλίνουσα συμπεριφορά του είναι κάπως πιο πολύπλοκη στην ανάλυση, οπότε αποφεύγουμε τις λεπτομέρειες. Μπορεί να φανεί ότι τα λάθη ικανοποιούν την
για κάποια πεπερασμένη μη μηδενική σταθερά 655#655, που συνεπάγεται ότι η σειρά είναι τοπικά συγκλίνουσα και δείχνει ότι ο ρυθμός είναι υπεργραμμικός. Για κάθε 432#432 ορίζουμε
όπου 29#29 είναι ο ρυθμός σύγκλισης που αναζητείται. Γι' αυτό, έχουμε
έτσι ώστε
Αλλά 1149#1149, όπου ο προηγούμενη αναλογία στα αριστερά τείνει προς μία μη μηδενική σταθερά. Οπότε πρέπει να έχουμε 1150#1150, που συνεπάγεται ότι ο ρυθμός σύγκλισης δίνεται από τη θετική λύση στην εξίσωση δευτέρου βαθμού 1151#1151. Οπότε, η μέθοδος της τέμνουσας είναι συνήθως υπεργραμμικά συγκλίνουσα, αλλά όπως στη μέθοδο του Νεύτωνος, πρέπει να ξεκινήσει αρκετά κοντά στη λύση ώστε να συγκλίνει. Σε σύγκριση με τη μέθοδο του Νεύτωνος, η μέθοδος της τέμνουσας έχει το πλεονέκτημα ότι απαιτεί μόνο μία νέα αποτίμηση συνάρτησης ανά επανάληψη, αλλά έχει τα μειονεκτήματα ότι απαιτεί δύο αρχικές εικασίες και συγκλίνει αρκετά πιο αργά, αν και υπεργραμμικά. Το χαμηλότερο κόστος ανά επανάληψη της μεθόδου της τέμνουσας συχνά αντισταθμίζει περισσότερο το μεγαλύτερο αριθμό των επαναλήψεων που απαιτούνται για την μετατροπή, όμως, ώστε το συνολικό κόστος για την εύρεση της ρίζας να είναι συχνά πιο μικρό για τη μέθοδο της τέμνουσας από ότι για τη μέθοδο του Νεύτωνος.
Manolis Vavalis 2000-03-24