ΚΡΙΤΙΚΗ

Η μέθοδος της γραμμικής παρεμβολής :

• Συγκλίνει ταχύτερα από τη μέθοδο διχοτόμησης
• Δεν είναι υποχρεωτικό η ρίζα να εσωκλείεται μεταξύ των δύο αρχικών τιμών.

Η διαδικασία εύρεσης της ρίζας με την μεθοδολογία που αναπτύξαμε περιγράφεται από τον ακόλουθο αλγόριθμο:

Table: Πρώτη παραλλαγή της μεθόδου γραμμικής παρεμβολής.

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

Υποθέτει ότι η ρίζα περικλείεται στο αρχικό διάστημα $(x_1,x_2)$

REPEAT

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

IF $f(x_3) \cdot f(x_1) < 0$

SET$x_2=x_3$

ELSE

SET$x_1=x_3$

ENDIF

UNTIL$\vert f(x_3)\vert<E$

Στη διαδικασία που μόλις περιγράψαμε (Πίνακας 1.3) υπάρχει κάποιο αδύνατο σημείο, γιατί, όπως γίνεται αντιληπτό, η τιμή $x_2$ παραμένει σταθερή. Άρα πλησιάζουμε τη ρίζα « μονόπλευρα » και αυτό έχει ως συνέπεια, μερικές φορές, η σύγκλιση να είναι αρκετά αργή, βλ. Σχήμα 1.2

Υπάρχουν δυο εναλλακτικές διαδικασίες για τη διόρθωση της μονόπλευρης σύγκλισης. Η πρώτη διαδικασία αλλάζει την επιλογή των τιμών για το επόμενο βήμα, δηλαδή, αν από δυο τιμές $x_1$ και $x_2$ έχουμε υπολογίσει με τη χρήση της εξίσωσης (1.13) μια τιμή $x_{3}$, χρησιμοποιούμε για το επόμενο βήμα την $x_{3}$ και αυτήν από τις $x_{1}$, $x_{2}$, για την οποία η $\left\vert f(x)\right\vert$ είναι μικρότερη. Επομένως, ο τροποποιημένος αλγόριθμος θα είναι:

Table: Δεύτερη παραλλαγή της μεθόδου γραμμικής παρεμβολής.

ΑΛΓΟΡΙΘΜΟΣ (ΙΙ) ΓΙΑ ΤΗΝ ΓΡΑΜΜΙΚΗ ΠΑΡΕΜΒΟΛΗ

H ρίζα δεν περικλείεται στο αρχικό διάστημα $\left( {x_{1} ,x_{2}} \right)$

REPEAT

SET $x_{3} = x_{2} - f\left( {x_{2}} \right) \cdot \frac{{x_{2} - x_{1}} }{{f\left( {x_{2}} \right) - f\left( {x_{1}} \right)}}$

IF $\vert f\quad \left( {x_{1}} \right)\vert < \vert f\left( {x_{2}} \right)\vert$

SET $x_{2}=x_{3}$

ELSE SET $x_{1}=x_{3}$

ENDIF

UNTIL $\left\vert {f\left( {x_{3}} \right)} \right\vert < E$

Η δεύτερη διαδικασία που βελτιώνει την ακρίβεια και την ταχύτητα σύγκλισης είναι η αντικατάσταση της τιμής της $f(x)$ στο σταθερό σημείο $x_{2}$ με την τιμή $f(x_2)/2$ κοκ. Η διαδικασία αυτή περιγράφεται στον παρακάτω τροποποιημένο αλγόριθμο:

Table: Εναλλακτικός αλγόριθμος για τη γραμμική παρεμβολή

ΑΛΓΟΡΙΘΜΟΣ (II) (τροποποιημενος )

$F_{1} = f(x_{1})$

$F_{2} = f(x_{2})$

$S = f(x_1)$

REPEAT

SET $x_3=x_2-F_2\cdot \frac{x_2-x_1}{F_2 - F_1 }$

IF $f(x_3) \cdot F_{1} < 0$

SET $x_{2}=x_{3}$

SET $F_{2} = f(x_3)$

IF $f\left( {x_{3}} \right) \cdot S > 0$

SET $F_{1} = F_1/2$

ENDIF

ELSE

SET $x_{1}=x_{3}$

SET $F_{1} = f\left( {x_{3}} \right)$

IF $f\left( {x_{3}} \right) \cdot S > 0$

SET $F_{2} = F_2/2$

ENDIF

ENDIF

SET save = $f(x_3)$

UNTIL $\left\vert f(x_3) \right\vert < E$