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:
“The middle years are ones in which children increasingly face conflicts on their own,... One of the truths to be faced by parents during this period is that they cannot do the work of living and relating for their children. They can be sounding boards and they can probe with the children the consequences of alternative actions.”
—Dorothy H. Cohen (20th century)
“It used to be said that, socially speaking, Philadelphia asked who a person is, New York how much is he worth, and Boston what does he know. Nationally it has now become generally recognized that Boston Society has long cared even more than Philadelphia about the first point and has refined the asking of who a person is to the point of demanding to know who he was. Philadelphia asks about a man’s parents; Boston wants to know about his grandparents.”
—Cleveland Amory (b. 1917)
“Every writer is necessarily a critic—that is, each sentence is a skeleton accompanied by enormous activity of rejection; and each selection is governed by general principles concerning truth, force, beauty, and so on.... The critic that is in every fabulist is like the iceberg—nine-tenths of him is under water.”
—Thornton Wilder (1897–1975)