The analytic approach to finding paths that meet minimum (or extremum) conditions makes use of the calculus of variations to get differential equations that can be solved for the functional forms of the paths. The approach taken here to two famous old problems varies trial paths directly. The two problems, the brachistochrone and the hanging chain, are usually grouped with energy problems because gravitational potential energy is either minimized or used to relate velocity to position. The hanging chain is used here to introduce the simplex algorithm, an organized method of varying parameters in minimization problems.
The brachistochrone problem is usually stated thus: "Let A and B be two points connected by a smooth wire, A being higher than B. A bead being free to slide on the wire is released from A; what must be the form of the wire in order that the bead may take the shortest possible time to reach B?" The applet first shows a straight line connecting A and B and prints the travel time, T(0), where '0' is the power of 2 that gives the number of line segments in the path. When the applet is run, the first thing that appears is the analytic solution (a cycloid) and travel time, T(A), then the path variation begins. What is plotted at each stage is the fastest path with 2^n line segments. At each stage, segments from the previous stage are bisected and the midpoints are moved up or down to minimize travel time. This minimization is a local process, and several interleaved iterations are required to minimize travel time for the entire path. With 256 segments, the travel time is within 0.1% of the analytic value.
A hanging rope or chain takes the shape that minimizes its gravitational potential energy. The applet, however, uses a force algorithm rather than an energy algorithm. The model spaces 64 beads at equal intervals along a light string 400 units long. The supports for the string are separated 240 units horizontally and 120 units vertically. The variational procedure uses the fact that, when one passes a bead, the vertical component of the tension changes by the weight of the bead (and the horizontal component does not change). Hence, if the tension in the string and its angle with the horizontal are known at the left support, the shape of the entire string can be traced out. The tension and angle are, of course, unknown, but trial values can be used, and the problem is then to vary these values to bring the right end of the string to the right support. This is the procedure used in the applet. The algorithm is the same one used in the 'homerun' problem in Projectile Motion I. For initial trial values of 60 degrees for the angle and the weight of 48 beads for the tension, the right end of the string ends up off-scale to the right in the figure. As with the brachistochrone, when the applet is run the first thing plotted is the analytic curve. For a continuous rope the curve is a catenary, here plotted with integer constants. The algorithm proceeds in the same way as in the homerun problem, optimizing the angle at each trial value of the tension (only optimum-angle trajectories are shown). The variation continues until the end of the string is within 1/10th of a unit (pixel) of the support.
The parameter variation sequence can be displayed graphically as points on a tension versus angle plot, as in the next applet. The homerun algorithm ("Vary" button) requires only a simple program and gets the job done, but is not very efficient. An algorithm known as the simplex algorithm ("Simp" button), on the other hand, provides an efficient procedure for parameter variation, but requires a more elaborate program. In general, a simplex is an (n+1)-vertex figure in an n-dimensional space. Here parameter space is two-dimensional, and the simplex is a triangle. One vertex of the starting triangle is given by the initial trial values, and the other two are displaced along the axes by the initial trial increments. The algorithm tries to replace the vertex with the highest deviation by projecting it through the middle of the opposite side. As the applet shows, this procedure continues for some time, each new triangle lying outside and sharing one side with the previous one. Eventually the replacement vertex falls inside the previous triangle, and the simplex begins to shrink. When a minimum is being sought, the process is continued until the separation between vertices reaches a specified minimum, but here the deviation can be made as small as we wish, so the magnitude of the deviation is used as the cutoff. Both variational procedures use time delays to make it easier to follow the process visually. (The homerun algorithm uses 10 ms, the simplex algorithm uses 100 ms.) The versitility of the simplex algorithm is demonstrated by using it to find accurate values for the three catenary constants ("Catc" button). In this case, the simplex has four vertices in a three-dimensional parameter space. The function being minimized is the sum of three squared terms: the y-deviations at the endpoint x-values, and the deviation in length (from the specified 400 units).