next up previous contents
Next: ΑΝΤΙΣΤΡΟΦΗ ΠΑΡΕΜΒΟΛΗ Up: ΜΗ ΓΡΑΜΜΙΚΕΣ ΕΞΙΣΩΣΕΙΣ ΣΕ Previous: ΜΕΘΟΔΟΣ ΤΟΥ ΝΕΥΤΟΝΟΣ.   Contents

Μέθοδος της τέμνουσας

Ένα μειονέκτημα της μεθόδου του Νεύτωνος είναι ότι τόσο η συνάρτηση όσο και το παράγωγο της πρέπει να εκτιμώνται σε κάθε επανάληψη. Το παράγωγο μπορεί να είναι άβολο ή ακριβό να εκτιμηθεί, έτσι πρέπει να σκεφτούμε να το προσεγγίσουμε μέσω μίας πεπερασμένης διαφοράς πηλίκου πάνω από μία μικρή 1136#1136 63#63, όπως στο Παράδειγμα 1.11, αλλά αυτό θα απαιτούσε μία δεύτερη εκτίμηση της συνάρτησης για κάθε επανάληψη καθαρά μόνο για την απόκτηση των παραγώγων πληροφοριών ( 1137#1137). Μία καλύτερη ιδέα είναι να βασίσουμε την πεπερασμένη διαφορά προσέγγισης σε επιτυχής επαναλήψεις, όπου η συνάρτηση πρέπει να υπολογίζεται ούτως ή άλλως. Αυτή η προσέγγιση δίνει μία μέθοδο της τέμνουσας:


1138#1138

Μία μέθοδος της τέμνουσας μπορεί να 1139#1139 καθώς προσεγγίζεται η συνάρτηση 51#51 από τη διατέμνουσα γραμμή μέσα από τις προηγούμενες δύο επαναλήψεις, και παίρνοντας το μηδέν της 1140#1140 γραμμικής συνάρτησης να είναι η προσεγγιστική λύση όπως παρουσιάστηκε στο Σχεδιάγραμμα 5.6.

ΣΧΕΔΙΑΓΡΑΜΜΑ 5.6 Μέθοδος της τέμνουσας για την επίλυση μη γραμμικών εξισώσεων,


27#27

Παράδειγμα 5.8   ΜΕΘΟΔΟΣ ΤΗΣ ΤΕΜΝΟΥΣΑΣ. Παρουσιάζουμε τη μέθοδο της τέμνουσας βρίσκοντας πάλι τη ρίζα της εξίσωσης


1141#1141

Παίρνουμε 1142#1142 και 1143#1143 ως δύο αρχικές προβλέψεις για τη λύση. Υπολογίζουμε τη συνάρτηση για κάθε ένα από τα δύο σημεία και παράγουμε νέες προσεγγιστικές λύσεις τοποθετώντας μία ευθεία γραμμή στις δύο τιμές της συνάρτησης ανάλογα με τον τύπο της τέμνουσας. Τότε επαναλαμβάνουμε τη διαδικασία χρησιμοποιώντας τη νέα αυτή τιμή και τις πιο πρόσφατες των προηγούμενων δύο τιμών. Σημειώστε ότι μόνο ένας υπολογισμός της συνάρτησης είναι απαραίτητος σε κάθε επανάληψη. Η σειρά των επαναλήψεων φαίνεται παρακάτω, όπου 63#63 συμβολίζει τη μεταβολή του 33#33 σε κάθε επανάληψη.

1144#1144


27#27

Επειδή κάθε νέα προσεγγιστική λύση που παράγεται από τη μέθοδο της τεμνουσας εξαρτάται από τις προηγούμενες δύο επαναλήψεις, η συγκλίνουσα συμπεριφορά του είναι κάπως πιο πολύπλοκη στην ανάλυση, οπότε αποφεύγουμε τις λεπτομέρειες. Μπορεί να φανεί ότι τα λάθη ικανοποιούν την

1145#1145

για κάποια πεπερασμένη μη μηδενική σταθερά 655#655, που συνεπάγεται ότι η σειρά είναι τοπικά συγκλίνουσα και δείχνει ότι ο ρυθμός είναι υπεργραμμικός. Για κάθε 432#432 ορίζουμε

1146#1146

όπου 29#29 είναι ο ρυθμός σύγκλισης που αναζητείται. Γι' αυτό, έχουμε

1147#1147

έτσι ώστε

1148#1148

Αλλά 1149#1149, όπου ο προηγούμενη αναλογία στα αριστερά τείνει προς μία μη μηδενική σταθερά. Οπότε πρέπει να έχουμε 1150#1150, που συνεπάγεται ότι ο ρυθμός σύγκλισης δίνεται από τη θετική λύση στην εξίσωση δευτέρου βαθμού 1151#1151. Οπότε, η μέθοδος της τέμνουσας είναι συνήθως υπεργραμμικά συγκλίνουσα, αλλά όπως στη μέθοδο του Νεύτωνος, πρέπει να ξεκινήσει αρκετά κοντά στη λύση ώστε να συγκλίνει. Σε σύγκριση με τη μέθοδο του Νεύτωνος, η μέθοδος της τέμνουσας έχει το πλεονέκτημα ότι απαιτεί μόνο μία νέα αποτίμηση συνάρτησης ανά επανάληψη, αλλά έχει τα μειονεκτήματα ότι απαιτεί δύο αρχικές εικασίες και συγκλίνει αρκετά πιο αργά, αν και υπεργραμμικά. Το χαμηλότερο κόστος ανά επανάληψη της μεθόδου της τέμνουσας συχνά αντισταθμίζει περισσότερο το μεγαλύτερο αριθμό των επαναλήψεων που απαιτούνται για την μετατροπή, όμως, ώστε το συνολικό κόστος για την εύρεση της ρίζας να είναι συχνά πιο μικρό για τη μέθοδο της τέμνουσας από ότι για τη μέθοδο του Νεύτωνος.



Manolis Vavalis 2000-03-24