Golden Ratio

The function

is unimodal on

, if there exists a unique number

such that

is decreasing on

,
and

is increasing on

Golden Ratio:

is known to be unimodal on

, then it is possible to replace the interval with a subinterval on which

takes on its minimum value. One approach is to select two interior points

. This results in

. The condition that

is unimodal guarantees that the function values

and

are less than

, then the minimum must occur in the subinterval

, and we replace b with d and continue the search in the new subinterval

. If

, then the minimum must occur in the subinterval

, and we replace a with c and continue the search in the new subinterval

. These choices are shown in Figure 1 below.

[Graphics:Images/GoldenRatioSearchMod_gr_26.gif]

If , then squeeze from the right and use the

new interval and the four points .

[Graphics:Images/GoldenRatioSearchMod_gr_27.gif]

If , then squeeze from the left and use the

new interval and the four points .

Figure 1. The decision process for the golden ratio search.

The interior points c and d of the original interval

, must be constructed so that the resulting intervals

, and

are symmetrical in

. This requires that

, and produces the two equations

(1) ,
and
(2) ,

where (to preserve the ordering ).

We want the value of r to remain constant on each subinterval. If r is chosen judicially then only one new point e (shown in green in Figure 1) needs to be constructed for the next iteration. Additionally, one of the old interior points (either c or d) will be used as an interior point of the next subinterval, while the other interior point (d or c) will become an endpoint of the next subinterval in the iteration process. Thus, for each iteration only one new point e will have to be constructed and only one new function evaluation

, will have to be made. As a consequence, this means that the value r must be chosen carefully to split the interval of

into subintervals which have the following ratios:

(3) and ,
and
(4) and .

If and only one new function evaluation is to be made in the interval , then we must have

.

Use the facts in (3) and (4) to rewrite this equation and then simplify.

,

,

,

.

Now the quadratic equation can be applied and we get

.

The value we seek is and it is often referred to as the "golden ratio." Similarly, if , then it can be shown that .

Comments

Runge-Kutta-Fehlberg Method

One way to guarantee accuracy in the solution of an I.V.P. is to solve the problem twice using step sizes h and and compare answers at the mesh points corresponding to the larger step size. But this requires a significant amount of computation for the smaller step size and must be repeated if it is determined that the agreement is not good enough. The Runge-Kutta-Fehlberg method (denoted RKF45) is one way to try to resolve this problem. It has a procedure to determine if the proper step size h is being used. At each step, two different approximations for the solution are made and compared. If the two answers are in close agreement, the approximation is accepted. If the two answers do not agree to a specified accuracy, the step size is reduced. If the answers agree to more significant digits than required, the step size is increased. Each Runge-Kutta-Fehlberg step requires the use of the following six values: Then an approximation to the solution of the I.V.P....

Van Der Pol System

The van der Pol equation is an ordinary differential equation that can be derived from the Rayleigh differential equation by differentiating and setting . It is an equation describing self-sustaining oscillations in which energy is fed into small oscillations and removed from large oscillations. This equation arises in the study of circuits containing vacuum tubes and is given by If , the equation reduces to the equation of simple harmonic motion The van der Pol equation is , where is a constant. When the equation reduces to , and has the familiar solution . Usually the term in equation (1) should be regarded as friction or resistance, and this is the case when the coefficient is positive. However, if the coefficient is negative then we have the case of "negative resistance." In the age of "vacuum tube" radios, the " tetrode vacuum tube " (cathode, grid, plate), was used for a power amplifie...

Newton-Raphson Method

This method is generally used to improve the result obtained by one of the previous methods. Let x o be an approximate root of f(x) = 0 and let x 1 = x o + h be the correct root so that f(x 1 ) = 0. Expanding f(x o + h) by Taylor ’s series, we obtain f(x o ) + hf’(x o ) + h 2 f’’(x o )/2! +-----= 0 Neglecting the second and higher order derivatives, we have f(x o ) + hf’(x o ) = 0 Which gives h = - f(x o )/f’(x o ) A better approximation than x o is therefore given be x 1 , where x 1 = x o – f(x o )/f’(x o ) Successive approximations are given by x 2 , x 3 ,----,x n+1 , where x n+1 = x n – f(x n )/f’(x n ) Which is the Newton-Raphson formula. Example: - Find a real root of the equation x 3 -5x + 3 = 0. Sol n : - Let, f(x) = x 3 -5x + 3 = 0 f’(x) = 3x 2 - 5 Choosing x o = 1 Step-1: f(x o ) = -1 f(x o ) = -2 So, x 1 =1 – ½ = 0.5 Step-2: f(x 1 ) = 0.625 f’(x 1 ) = -4.25 x 2 = 0.5 + 0.625/4.25 = 0.647 S...

Powell's Method

The essence of Powell's method is to add two steps to the process described in the preceding paragraph. The vector represents, in some sense, the average direction moved over the n intermediate steps in an iteration. Thus the point is determined to be the point at which the minimum of the function f occurs along the vector . As before, f is a function of one variable along this vector and the minimization could be accomplished with an application of the golden ratio or Fibonacci searches. Finally, since the vector was such a good direction, it replaces one of the direction vectors for the next iteration. The iteration is then repeated using the new set of direction vectors to generate a sequence of points . In one step of the iteration instead of a zig-zag path the iteration follows a "dog-leg" path. The process is outlined below. Let be an initial guess at the location of the minimum of the function . Let for be the ...

Numerical Analysis

Search This Blog

Golden Ratio

Labels

Comments

Post a Comment

Popular Posts

Runge-Kutta-Fehlberg Method

Van Der Pol System

Newton-Raphson Method

Powell's Method