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

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

Σε προηγούμενη ανάρτηση ασχοληθήκαμε με την μέθοδο Newton-Raphson ώστε να μπορέσουμε να λύσουμε μη γραμμικές εξισώσεις. Η μέθοδος αυτή έχει πολύ γρήγορη σύγκλιση αλλά το ελάττωμα της είναι το εξής: χρειάζεται να βρεθεί η παράγωγος της συνάρτησης για την οποία ψάχνουμε την ρίζα. Σε μερικές περιπτώσεις αυτό είναι δύσκολο και ως εκ τούτου χρησιμοποιούμε μία άλλη μέθοδο που ονομάζεται η μέθοδος της τέμνουσας.

Ο τύπος της Newton-Raphon είναι ο εξής:
Για να αντιμετωπίσουμε το πρόβλημα με την παράγωγο αντικαθιστούμε το f ' με την προσέγγιση της. Δηλαδή
Οπότε συνδυάζοντας αυτές τις δύο εξισώσεις έχουμε πως
Έτσι αν έχουμε δύο αρχικές τιμές x0 και x1 με την παραπάνω εξίσωση μπορούμε να υπολογίσουμε μία τιμή x2 (θέτουμε i=1). Έπειτα γνωρίζοντας τα x1 και x2 μπορούμε να υπολογίσουμε το x3 (θέτουμε i=2). H διαδικασία συνεχίζεται μέχρι να υπάρξει σύγκλιση, δηλαδή τα xi+1 που υπολογίζουμε να μην διαφέρουν σημαντικά από τα xi.

Ας δούμε όμως αυτή την διαδικασία σε εφαρμογή. Έστω ότι θέλουμε να λύσουμε την εξίσωση

Για την εύρεση της ρίζας μπορούμε να δημιουργήσουμε ένα αλγόριθμο. Ένας πιθανός κώδικας που υλοποιεί τον αλγόριθμο αυτό είναι ο εξής:

Private Sub Command1_Click()

'δήλωση των τύπων των μεταβλητών
Dim x0 As Double, x1 As Double, flag As Boolean, n As Integer, i As Integer

'εισαγωγή των δεδομένων από την φόρμα
'x0 είναι η πρώτη αρχική τιμή
'x1 είναι η δεύτερη αρχική τιμή
'n είναι το μέγιστο πλήθος επαναλήψεων
x0 = Text1.Text
x1 = Text2.Text
n = Text3.Text

i = 1

'flag είναι η μεταβλητή που μας δείχνει αν υπάρχει σύγκλιση ή όχι
flag = False

'ανοίγουμε ένα αρχείο για την εξαγωγή των αποτελεσμάτων
Open "results.txt" For Output As #1

'τυπώνουμε στο αρχείο τις δύο αρχικές τιμές
Print #1, "πρώτη αρχική τιμή", x0
Print #1, "δεύτερη αρχική τιμή", x1

'ακολουθεί επαναληπτική διαδικασία μέχρι να έχουμε σύγκλιση ή μέχρι να ξεπεράσουμε τον μέγιστο
'αριθμό επαναλήψεων
Do Until i > n Or flag = True

'υπολογίζουμε το επόμενο xi+1
X2 = x1 - (f(x1) * (x1 - x0)) / (f(x1) - f(x0))

'τυπώνουμε στο αρχείο το xi+1
Print #1, i, X2

'αν το xi+1 και το xi διαφέρουν λιγότερο από 0.0001 τότε έχουμε σύγκλιση
If Abs(X2 - x1) < 0.0001 Then
flag = True
End If

'θέτουμε όπου xi-1 το xi και όπου xi το xi+1
x0 = x1
x1 = X2

i = i + 1
Loop

'κλείνουμε το αρχείο
Close

'εμφανίζεται στην φόρμα η ρίζα της εξίσωσης με ακρίβεια 4 δεκαδικών
Text4.Text = Format(X2, "0.0000")

End Sub

'δηλώνουμε την συνάρτηση της οποίας την ρίζα θέλουμε να βρούμε
Function f(x As Double) As Double
f = x ^ 3 - 0.18 * (x ^ 2) + 4 * (10 ^ -4)
End Function

εικόνα 1, η φόρμα εισαγωγής δεδομένων
στον κώδικα.
Συνεπώς για να λύσουμε την εξίσωση αυτή επιλέγουμε ως αρχικές τιμές τα 0.01 και 0.04 και ως μέγιστο αριθμό επαναλήψεων βάζουμε n=20 . Εκτελώντας τον κώδικα παίρνουμε ως ρίζα το 0.0570 (εικόνα 2).
εικόνα 2, βλέπουμε το αποτέλεσμα της εκτέλεσης
του κώδικα.
Στο αρχείο έχουμε τα ακόλουθα αποτελέσματα:

i                                          x 
πρώτη αρχική τιμή             0.01 
δεύτερη αρχική τιμή          0.04 
 1                                        6.55072463768116E-02 
 2                                        5.67941893278604E-02 
 3                                        5.70344970987629E-02 
 4                                        5.70346226240339E-02 


Παρατηρούμε πως είχαμε σύγκλιση σε 4 επαναλήψεις.

Για να ελέγξουμε την αξιοπιστία του αποτελέσματος κάνουμε αντικατάσταση το 0.057 στην συνάρτηση
Συνεπώς έχουμε
Οπότε η ρίζα που βρήκαμε είναι αξιόπιστη.


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

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