Nonlinear Opt.: Gold section search 1: Unterschied zwischen den Versionen
| [unmarkierte Version] | [unmarkierte Version] |
Iacob (Diskussion | Beiträge) |
Iacob (Diskussion | Beiträge) |
||
| Zeile 1: | Zeile 1: | ||
Interval reduction methods usually use the function value of two interior points in the interval to decide the direction in which to reduce it. One elegant way is to recycle one of the evaluated points and to use it in the nextiterations. This can be done by using the so-called '''Golden Section rule'''. | Interval reduction methods usually use the function value of two interior points in the interval to decide the direction in which to reduce it. One elegant way is to recycle one of the evaluated points and to use it in the nextiterations. This can be done by using the so-called '''Golden Section rule'''. | ||
| − | This method uses two evaluated points l (left) and r (right) in the interval <math>[a_k, b_k]</math> that are located in such a way that one of the points can be used again in the next iteration. The idea is sketched in Figure | + | This method uses two evaluated points l (left) and r (right) in the interval <math>[a_k, b_k]</math> that are located in such a way that one of the points can be used again in the next iteration. The idea is sketched in Figure 1. The evaluation points l and r are located with fraction τ in such a way that <math>l=a+(1-\tau)(b-a)</math> and <math>r=a+\tau(b-a)</math>. |
| + | Equating in the Figure 1 the next right point to the old left point gives the equation <math>\tau^2=1-\tau</math>. | ||
| + | The solution is the so-called Golden Section number <math>\tau=\frac{\sqrt{5}-1}2</math> <math>\approx </math> 0.618. | ||
| + | [[Datei:Unbenannt.jpg]] | ||
| + | |||
| + | Algorithm '''Golden Section rule'''<math>([a, b], f,\epsilon)</math> | ||
| + | |||
| + | Set k := 1, a1 := a and b1 := b, <math>\tau := \frac{\sqrt{5}-1}2</math> | ||
| + | |||
| + | l := <math>x_0</math> := a + (1 − <math>\tau</math>)(b − a); r := <math>x_1</math> := a + <math>\tau</math> (b − a) | ||
| + | |||
| + | Evaluate f(<math>x_1</math>) := f(<math>x_0</math>) | ||
| + | |||
| + | '''repeat''' | ||
| + | |||
| + | |||
| + | ''Evaluate f(<math>x_k</math>)'' | ||
| + | |||
| + | if (f(r) < f(l)) | ||
| + | |||
| + | <math>a_{k+1}</math> := l; <math>b_{k+1}</math> := <math>b_k</math>; l := r | ||
| + | |||
| + | r := <math>x_{k+1}</math> := <math>a_{k+1}</math> + <math>\tau</math>(<math>b_{k+1}</math> − <math>a_{k+1}</math>) | ||
| + | |||
| + | else | ||
| + | |||
| + | <math>a_{k+1}</math> := <math>a_k</math>, <math>b_{k+1}</math> := r; r := l | ||
| + | |||
| + | l := <math>x_{k+1}</math> := <math>a_{k+1}</math> + (1 − <math>\tau</math> )(<math>b_{k+1}</math> − <math>a_{k+1}</math>) | ||
| + | |||
| + | k := k + 1 | ||
| + | |||
| + | '''until''' (<math>b_k</math> − <math>a_k</math> < <math>\epsilon</math>) | ||
Version vom 11. Juni 2013, 18:28 Uhr
Interval reduction methods usually use the function value of two interior points in the interval to decide the direction in which to reduce it. One elegant way is to recycle one of the evaluated points and to use it in the nextiterations. This can be done by using the so-called Golden Section rule.
This method uses two evaluated points l (left) and r (right) in the interval that are located in such a way that one of the points can be used again in the next iteration. The idea is sketched in Figure 1. The evaluation points l and r are located with fraction τ in such a way that Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): l=a+(1-\tau)(b-a)
and Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): r=a+\tau(b-a)
. Equating in the Figure 1 the next right point to the old left point gives the equation Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \tau^2=1-\tau . The solution is the so-called Golden Section number Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \tau=\frac{\sqrt{5}-1}2
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \approx 0.618.
Algorithm Golden Section rule
Set k := 1, a1 := a and b1 := b, Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \tau := \frac{\sqrt{5}-1}2
l := := a + (1 − Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \tau
)(b − a); r := := a + Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \tau
(b − a)
Evaluate f() := f()
repeat
Evaluate f()
if (f(r) < f(l))
:= l; := ; l := r
r := := + Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \tau
( − )
else
:= , := r; r := l
l := := + (1 − Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \tau )( − )
k := k + 1
until ( − < )
