Heath - Scientific Computing (523150), страница 45
Текст из файла (страница 45)
A better idea is tobase the finite difference approximation on successive iterates, where the function must beevaluated anyway. This approach gives the secant method :xk+1 = xk − f (xk )xk − xk−1.f (xk ) − f (xk−1 )The secant method can be interpreted as approximating the function f by the secant linethrough the previous two iterates, and taking the zero of the resulting linear function to bethe next approximate solution, as illustrated in Fig. 5.6.Example 5.8 Secant Method. We illustrate the secant method by again finding a rootof the equationf (x) = x2 − 4 sin(x) = 0.5.2.
NONLINEAR EQUATIONS IN ONE DIMENSION161.... ...... ........................................ ....... ........... ..... ......... ..................................... ..................................................................... ................ ... .............................................................................................................................................................................................................................kk−1.........................................................↑ xxk+1xFigure 5.6: Secant method for solving a nonlinear equation.We take x0 = 1 and x1 = 3 as our two starting guesses for the solution. We evaluate thefunction at each of these two points and generate a new approximate solution by fitting astraight line to the two function values according to the secant formula. We then repeat theprocess using this new value and the more recent of our two previous values.
Note that onlyone new function evaluation is needed per iteration. The sequence of iterations is shownnext, where h denotes the change in x at each iteration.x1.0000003.0000001.4380701.7248052.0298331.9220441.9331741.9337571.933754f (x)−2.3658848.435520−1.896774−0.9777060.534305−0.061523−0.0030640.0000190.000000h−1.5619300.2867350.305029−0.1077890.0111300.000583−0.0000040.000000Because each new approximate solution produced by the secant method depends on twoprevious iterates, its convergence behavior is somewhat more complicated to analyze, so weomit most of the details.
It can be shown that the errors satisfy|ek+1 |=ck→∞ |ek | · |ek−1 |limfor some finite nonzero constant c, which implies that the sequence is locally convergentand suggests that the rate is superlinear. For each k we definesk = |ek+1 |/|ek |r ,where r is the convergence rate to be determined. Thus, we have2|ek+1 | = sk |ek |r = sk (sk−1 |ek−1 |r )r = sk srk−1 |ek−1 |r ,so that2sk srk−1 |ek−1 |r|ek+1 |2== sk sr−1|ek−1 |r −r−1 .k−1r|ek | · |ek−1 |sk−1 |ek−1 | |ek−1 |162CHAPTER 5. NONLINEAR EQUATIONSBut |ek | → 0, whereas the foregoing ratio on the left tends to a nonzero constant; so wemust have r2 − r − 1 = 0, which implies that the√ convergence rate is given by the positivesolution to this quadratic equation, r = (1 + 5 )/2 ≈ 1.618.
Thus, the secant methodis normally superlinearly convergent, but, like Newton’s method, it must be started closeenough to the solution in order to converge.Compared with Newton’s method, the secant method has the advantage of requiringonly one new function evaluation per iteration, but it has the disadvantages of requiringtwo starting guesses and converging somewhat more slowly, though still superlinearly. Thelower cost per iteration of the secant method often more than offsets the larger number ofiterations required for convergence, however, so that the total cost of finding a root is oftenless for the secant method than for Newton’s method.5.2.5Inverse InterpolationAt each iteration of the secant method, a straight line is fit to two values of the functionwhose zero is sought.
A higher convergence rate (but not exceeding r = 2) can be obtainedby fitting a higher-degree polynomial to the appropriate number of function values. Forexample, one could fit a quadratic polynomial to three successive iterates and use one ofits roots as the next approximate solution.
There are several difficulties with this idea,however: the polynomial may not have real roots, and even if it does they may not beeasy to compute, and it may not be easy to choose which root to use as the next iterate.(On the other hand, if one seeks a complex root, then a polynomial having complex roots isdesirable; in Muller’s method , for example, a quadratic polynomial is used in approximatingcomplex roots.)An answer to these difficulties is provided by inverse interpolation, in which one fits thevalues xk as a function of the values yk = f (xk ), say, by a polynomial p(y), so that the nextapproximate solution is simply p(0). This idea is illustrated in Fig.
5.7, where a parabolafitting y as a function of x has no real root (i.e., it fails to cross the x axis), but a parabolafitting x as a function of y is merely evaluated at zero to obtain the next iterate.y.................... ................. .... .......... .......................
............ ..... ........... ........................................... ............ .. ....... ... ................ .... ................................................................................................................................. ........................ ...... ......................................................................................................................................................................................................................................................................................•quadratic fit•inverse fit•0↑next iteratexFigure 5.7: Inverse interpolation for finding a root.Using inverse quadratic interpolation, at each iteration we have three approximate solution values, which we denote by a, b, and c, with corresponding function values fa , fb , andfc , respectively.
The next approximate solution is found by fitting a quadratic polynomial5.2. NONLINEAR EQUATIONS IN ONE DIMENSION163to a, b, and c as a function of fa , fb , and fc , and then evaluating the polynomial at 0. Thistask is accomplished by the following formulas, whose derivation will become clearer afterwe study Lagrange interpolation in Section 7.2.2:u = fb /fc ,v = fb /fa ,p = v(w(u − w)(c − b) − (1 − u)(b − a)),w = fa /fc ,q = (w − 1)(u − 1)(v − 1).The new approximate solution is given by b + p/q. The process is then repeated with breplaced by the new approximation, a replaced by the old b, and c replaced by the olda. Note that only one new function evaluation is needed per iteration. The convergencerate of inverse quadratic interpolation for root finding is r ≈ 1.839, which is the same asfor regular quadratic interpolation (Muller’s method). Again this result is local, and theiterations must be started close enough to the solution to obtain convergence.Example 5.9 Inverse Quadratic Interpolation.
We illustrate inverse quadratic interpolation by again finding a root of the equationf (x) = x2 − 4 sin(x) = 0.Taking a = 1, b = 2, and c = 3 as starting values, the sequence of iterations is shown next,where h = p/q denotes the change in x at each iteration.x1.0000002.0000003.0000001.8863181.9395581.9337421.9337545.2.6f (x)−2.3658840.3628108.435520−0.2443430.030786−0.0000600.000000h−0.1136820.053240−0.0058150.000011Linear Fractional InterpolationThe zero-finding methods we have considered thus far may have difficulty if the functionwhose zero is sought has a horizontal or vertical asymptote.
A horizontal asymptote mayyield a tangent or secant line that is almost horizontal, causing the next approximatesolution to be far afield, and a vertical asymptote may be skipped over, placing the approximation on the wrong branch of the function. Linear fractional interpolation, which uses arational fraction of the formx−u,φ(x) =vx − wis a useful alternative in such cases. This function has a zero at x = u, a vertical asymptoteat x = w/v, and a horizontal asymptote at y = 1/v.In seeking a zero of a nonlinear function f (x), suppose that we have three approximatesolution values, which we denote by a, b, and c, with corresponding function values fa , fb ,164CHAPTER 5. NONLINEAR EQUATIONSand fc , respectively. Fitting thesystem of linear equations111linear fraction φ to the three data points yields a 3 × 3afabfbcfc −faua−fbv = b ,−fcwcwhose solution determines the coefficients u, v, and w.
We now replace a and b with b andc, respectively, and take the next approximate solution to be the zero of the linear fraction,c = u. Since v and w play no direct role, the solution to the foregoing system is mostconveniently implemented as a single formula for the change h in c, which is given byh=(a − c)(b − c)(fa − fb )fc.(a − c)(fc − fb )fa − (b − c)(fc − fa )fbLinear fractional interpolation is also effective as a general-purpose one-dimensional zerofinder, as the following example illustrates. Its asymptotic convergence rate is the sameas that given by quadratic interpolation (inverse or regular), r ≈ 1.839. Once again thisresult is local, and the iterations must be started close enough to the solution to obtainconvergence.Example 5.10 Linear Fractional Interpolation. We illustrate linear fractional interpolation by again finding a root of the equationf (x) = x2 − 4 sin(x) = 0.Taking a = 1, b = 2, and c = 3 as starting values, the sequence of iterations is shown next.x1.0000002.0000003.0000001.9069531.9333511.9337561.9337545.2.7f (x)−2.3658840.3628108.435520−0.139647−0.0021310.0000130.000000h−1.0930470.026398−0.000406−0.000003Safeguarded MethodsRapidly convergent methods for solving nonlinear equations, such as Newton’s method, thesecant method, and other types of methods based on interpolation, are unsafe in that theymay not converge unless they are started close enough to the solution.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
