Probe Point Selection
From the diagram above, it is seen that the new search interval will be either between and with a length of a+c, or between and with a length of b . The golden section search requires that these intervals be equal. If they are not, a run of "bad luck" could lead to the wider interval being used many times, thus slowing down the rate of convergence. To ensure that b = a+c, the algorithm should choose .
However there still remains the question of where should be placed in relation to and . The golden section search chooses the spacing between these points in such a way that these points have the same proportion of spacing as the subsequent triple or . By maintaining the same proportion of spacing throughout the algorithm, we avoid a situation in which is very close to or, and guarantee that the interval width shrinks by the same constant proportion in each step.
Mathematically, to ensure that the spacing after evaluating is proportional to the spacing prior to that evaluation, if is and our new triplet of points is, and then we want:
However, if is and our new triplet of points is, and then we want:
Eliminating c from these two simultaneous equations yields:
or
where φ is the golden ratio:
The appearance of the golden ratio in the proportional spacing of the evaluation points is how this search algorithm gets its name.
Read more about this topic: Golden Section Search
Famous quotes containing the words probe, point and/or selection:
“Y’know scientists are funny. We probe and measure and dissect. Invent lights without heat, weigh a caterpillar’s eyebrow. But when it comes to really important things we’re as stupid as the caveman.... Like love. Makes the world go ‘round, but what do we know about it? Is it a fact? Is it chemistry? Electricity?”
—Martin Berkeley, and Jack Arnold. Helen Dobson (Lori Nelson)
“The whole point about the true unconscious is that it is all the time moving forward, beyond the range of its own fixed laws or habits. It is no good trying to superimpose an ideal nature upon the unconscious.”
—D.H. (David Herbert)
“Judge Ginsburg’s selection should be a model—chosen on merit and not ideology, despite some naysaying, with little advance publicity. Her treatment could begin to overturn a terrible precedent: that is, that the most terrifying sentence among the accomplished in America has become, “Honey—the White House is on the phone.””
—Anna Quindlen (b. 1952)