ΜΕΘΟΔΟΣ NEWTON - RAPHSON

Αν στην περιοχή μιας ρίζας $\rho$ της συνάρτησης $f(x)$ η $f'(x)$ και η ${f}''\left( {x} \right)$ είναι συνεχείς, τότε μπορούμε να αναπτύξουμε αλγορίθμους, οι οποίοι συγκλίνουν στη ρίζα της εξίσωσης $f\left( {x} \right) = 0$ ταχύτερα από όλες τις μεθόδους που εξετάσαμε ως τώρα.

Η μέθοδος Newton-Raphsonείναι ευρύτατα διαδεδομένη και η δημοφιλέστερη από όλες τις προηγούμενες μεθόδους, απαιτεί όμως τη γνώση της συναρτησιακής μορφής της 1ης παραγώγου της συνάρτησης $f(x)$.

Figure: Γραφική απεικόνιση της διαδικασίας που αναπτύχθηκε για τη μέθοδο Newton-Raphson.

Έστω ένα σημείο $x_{0}$, το οποίο θεωρούμε ως την πρώτη προσέγγιση στη ρίζα. Παίρνοντας την εφαπτομένη της καμπύλης στο σημείο $\left(x_0 ,f(x_0)\right)$ και προσδιορίζουμε ένα νέο σημείο $x_1$ από την τομή της εφαπτομένης με τον άξονα $Ox$ (άρα $f(x_1)=0$). Οπότε, από το ορθογώνιο τρίγωνο $x_{1} x_{0} A$ (βλ. Σχήμα 1.5 βρίσκουμε:

$$\tan\theta = f'(x_0)=\frac{f(x_0)}{x_1-x_0}$$ (30)

και λύνοντας ως προς $x_1$ δημιουργούμε την αναδρομική σχέση:

$$x_1 = x_0 - \frac{f(x_0)}{f'(x_0)} \, .$$ (31)

Αυτή η διαδικασία μπορεί να επαναληφθεί για το $x_1$ και να βρεθεί ένα νέο σημείο $x_2$ κοκ.

Table: Εφαρμογή της μεθόδου Newton-Raphsonγια το λογιστικό πρόβλημα.

επαναλήψεις	$x_0$	$x_1$	$f(x_1)$
1	0.15	0.1247	-132.475
2	0.1247	0.1237810	-0.01681
3	0.12378	0.1237798	-0.00101

Ας προσπαθήσουμε τώρα να δημιουργήσουμε τη σχέση (1.31) με πιο αυστηρό τρόπο. Αν υποθέσουμε ότι $x_{n+1}$ είναι η ακριβής λύση της εξίσωσης και μια τιμή $x_{n}$ βρίσκεται σχετικά κοντά στην $x_{n+1}$ και έστω $x_{n + 1} = x_{n} + \varepsilon _{n}$. Τότε:

$$f\left( {x_{n + 1}} \right) = f\left( {x_{n} + \varepsilon ... ...repsilon _{n}^{2}} }{{2}}{f}''\left( {x_{n}} \right) + \cdots$$

Αλλά, επειδή υποθέσαμε ότι η $x_{n+1}$ είναι ρίζα της $f\left( {x} \right)$, θα ισχύει $f\left( {x_{n + 1}} \right) = 0$, και έτσι αναγόμαστε στη σχέση

$$0 = f\left( {x_{n}} \right) + \varepsilon _{n} {f}'\left( {x_{n}} \right)$$

δηλαδή

$$\varepsilon_n=-\frac{f(x_n)}{f'(x_n)}$$ (32)

οπότε καταλήγουμε στην αναδρομική σχέση:

$$x_{n + 1} = x_{n} - \frac{f(x_n)}{f'(x_n)}$$ (33)

που προφανώς προγραμματίζεται πολύ εύκολα.