Η ΜΕΘΟΔΟΣ ΤΗΣ ΓΡΑΜΜΙΚΗΣ ΠΑΡΕΜΒΟΛΗΣ

Όπως διαπιστώσαμε, η μέθοδος της διχοτόμησης συγκλίνει στην ακριβή τιμή της ρίζας αρκετά αργά. Για το λόγο αυτό, έχουν αναπτυχθεί μέθοδοι με τις οποίες επιτυγχάνεται ταχύτερη σύγκλιση. Αρκετά δημοφιλής είναι η μέθοδος της γραμμικής παρεμβολής.

Στηρίζεται στην εξής λογική: Αν στο διάστημα $[x_1,x_2]$ υπάρχει μία ρίζα της $f(x)$, δηλαδή $f(x_1) \cdot f(x_2)< 0$, τότε φέρνω την ευθεία που διέρχεται από τα σημεία $(x_1 ,f(x_1))$ και $\left(x_2 ,f(x_2)\right)$ με εξίσωση:

$$y\left(x\right)=f\left(x_1\right) + \frac{f\left(x_1\right) - f\left(x_2\right)}{x_1 - x_2}\left(x - x_1 \right)$$ (11)

η οποία τέμνει τον άξονα ${Ox}$ έστω στο σημείο $x_{3}$ που υπολογίζεται απο την παρακάτω σχέση:

$$x_3 = \frac{x_2 f(x_1) - x_1 f(x_2)}{f(x_1) - f(x_2)}$$

$$= x_2 - \frac{f(x_2)}{f(x_2) - f(x_1)}\left(x_2-x_1\right)$$ (12)

Επομένως στην πράξη αντικαθιστώ στο διάστημα $\left[x_1,x_2\right]$ την συνάρτηση $f(x)$ με μία ευθεία και θεωρώ προσεγγιστικά ότι η τομή αυτής της ευθείας με τον άξονα $Ox$ είναι η ζητούμενη ρίζα. Το νέο σημείο είναι πλησιέστερα στη ρίζα και ώς εκ τούτου μπορω να χρησιμοποιήσω τη σχέση (1.12) ξανά για την αναζήτηση μιας νέας τιμής που να βρίσκεται πλησιέστερα στη ρίζα $\rho$. Για να χρησιμοποίησουμε όμως τη σχέση (1.12) απαιτείται η κατάλληλη επιλογή ενός εκ των δύο αρχικών σημείων. Μια απλή (αλλά όχι μοναδική) διαδικασία επιλογής είναι να φροντίζουμε το ζεύγος των σημείων που χρησιμοποιούμε να περικλείει τη ρίζα, δηλαδή:

• (I) είτε $f\left( {x_{1}} \right) \cdot f\left( {x_{3}} \right) < 0 \Rightarrow x_{2} = x_{3}$
• (II) είτε $f\left( {x_{2}} \right) \cdot f\left( {x_{3}} \right) < 0 \Rightarrow x_{1} = x_{3}$
• (III) είτε $f\left( {x_{3}} \right) = 0$

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