Παρασκευή, 6 Μαρτίου 2015

Ταχύτητα σύγκλισης αριθμητικών μεθόδων επίλυσης εξισώσεων

Σε προηγούμενες αναρτήσεις έχουν παρουσιαστεί τέσσερις μέθοδοι επίλυσης μη γραμμικών εξισώσεων. Αυτές είναι οι μέθοδοι:
  1. των απλών συναρτησιακών επαναλήψεων
  2. Newton-Raphson
  3. της διχοτόμησης
  4. της τέμνουσας
Όμως ποια μας δίνει σύγκλιση στις λιγότερες επαναλήψεις;

Ας ρίξουμε μια ματιά στην θεωρία της αριθμητικής ανάλυσης. Κάθε μέθοδος χαρακτηρίζεται από μία τιμή ταχύτητας σύγκλισης. Έτσι
  • η μέθοδος των απλών συναρτησιακών επαναλήψεων έχει γραμμική σύγκλιση (ταχύτητα=1)
  • η μέθοδος Newton-Raphson έχει τετραγωνική σύγκλιση (ταχύτητα=2)
  • η μέθοδος της διχοτόμησης έχει γραμμική σύγκλιση (ταχύτητα=1)
  • η μέθοδος της τέμνουσας έχει σχεδόν τετραγωνική σύγκλιση (ταχύτητα=1.6)
Πρέπει να σημειωθεί πως υπάρχει η περίπτωση η μέθοδος της τέμνουσας σε κάποια σημεία να είναι γρηγορότερη από την μέθοδο Newton-Raphson.

Τώρα θα επιχειρήσουμε να λύσουμε μία εξίσωση και με τις τέσσερις μεθόδους για να δούμε ποια μας δίνει την γρηγορότερη σύγκλιση. Πρέπει να θυμόμαστε πως η ταχύτητα σύγκλισης εξαρτάται όχι μόνο από την μέθοδο επίλυσης της εξίσωσης αλλά και από τις επιλεγμένες αρχικές τιμές. Οπότε δεν είναι απίθανο σε κάποιες από τις μεθόδους να επιλέξουμε καταλάθος καλύτερες αρχικές τιμές από τις άλλες ώστε να έχουμε αποτέλεσμα που διαφέρει από το θεωρητικό (πχ η μέθοδος των απλών συναρτησιακών επαναλήψεων να συγκλίνει πιο γρήγορα από την μέθοδο της τέμνουσας). Το παράδειγμα που αναφέραμε είναι ακραία περίπτωση απλώς επιλέχθηκε έτσι ώστε να δείξει την αξία των αρχικών τιμών. Θα προσπαθήσουμε λοιπόν να επιλέξουμε "φυσιολογικές" αρχικές τιμές και για τις τέσσερις μεθόδους.

Η εξίσωση που θα λύσουμε είναι η

Αρχικά, ας δοκιμάσουμε την μέθοδο των απλών συναρτησιακών επαναλήψεων. Επιλέγουμε ως αρχική τιμή το 0 και ως μέγιστο αριθμό επαναλήψεων το 50 . Έτσι τρέχοντας τον κώδικα έχουμε

επανάληψη  τιμή

αρχική τιμή    0
 1            -1
 2            -0.54030230586814
 3            -1.1059289399881
 4            -0.331154384655862
 5            -1.16715880114091
 6            -0.197665275665335
.
.
.
 46           -0.232535694306994
 47           -1.15154802928453
 48           -0.232559132226104
 49           -1.15155516491357
 50           -0.23254331610545 

Βλέπουμε πως αυτή η μέθοδος δεν συγκλίνει ούτε μετά από 50 επαναλήψεις.

Έπειτα, δοκιμάζουμε την μέθοδο Newton-Raphson. Επιλέγουμε ως αρχική τιμή πάλι το 0 και ως μέγιστο αριθμό επαναλήψεων το 20 . Οπότε εκτελώντας τον κώδικα παίρνουμε

επανάληψη  τιμή

αρχική τιμή              0 
 1             1 
 2             0.620015952247299 
 3             0.552465034764084 
 4             0.550012619600538 

Συνεπώς η ρίζα είναι το 0.55 και η μέθοδος αυτή συγκλίνει στις 4 επαναλήψεις.

Επόμενη είναι η μέθοδος της διχοτόμησης. Επιλέγουμε ως αρχικό διάστημα το [0,1] και αριθμό μέγιστων επαναλήψεων το 20 . Εκτελώντας τον κώδικα έχουμε

επανάληψη  τιμή

 1             0.5
 2             0.75
 3             0.625 
 4             0.5625 
 5             0.53125 
 6             0.546875 
 7             0.5546875 
 8             0.55078125
 9             0.548828125 
 10            0.5498046875 
 11            0.55029296875 
 12            0.550048828125 
 13            0.5499267578125
 14            0.54998779296875

Έτσι μετά από 14 επαναλήψεις βρίσκουμε πως η ρίζα είναι 0.55 .

Τέλος θα δοκιμάσουμε την μέθοδο της τέμνουσας. Ως τις δύο αρχικές τιμές θα πάρουμε το -0.5 και το 0. Ως μέγιστο αριθμό επαναλήψεων θα επιλέξουμε το 20 . Τρέχοντας τον κώδικα παίρνουμε

επανάληψη  τιμή

πρώτη αρχική τιμή           -0.5 
δεύτερη αρχική τιμή          0 
 1             3.91903088158421 
 2             0.186704563877183 
 3             0.323586373778644 
 4             0.618515458163277 
 5             0.540689741293372 
 6             0.549674184919799 
 7             0.550011058551833 
 8             0.550009349615774 

Πάλι βλέπουμε πως η ρίζα είναι το 0.55 την οποία βρίσκουμε με 8 επαναλήψεις.

Οπότε επαληθεύεται η θεωρία. Η πιο γρήγορη μέθοδος είναι η Newton-Raphson (4 επαναλήψεις), μετά ακολουθεί η μέθοδος της τέμνουσας (8 επαναλήψεις), έπεται η μέθοδος της διχοτόμησης (14 επαναλήψεις) και τελευταία είναι η μέθοδος των απλών συναρτησιακών επαναλήψεων (δεν έχουμε σύγκλιση).

Δεν υπάρχουν σχόλια:

Δημοσίευση σχολίου