Heath - Scientific Computing (523150), страница 43
Текст из файла (страница 43)
This property makes sense, because the two problems areinverses of each other: if y = f (x), then finding x given y has the opposite conditioningfrom finding y given x.5.1.2Convergence Rates of Iterative MethodsUnlike linear equations, most nonlinear equations cannot be solved in a finite number ofsteps. Thus, we must usually resort to an iterative method that produces increasinglyaccurate approximations to the solution, and we terminate the iteration when the resultis sufficiently accurate. The total cost of solving the problem depends on both the costper iteration and the number of iterations required for convergence, and there is often atrade-off between these two factors.To compare the effectiveness of iterative methods, we need to characterize their convergence rates.
We denote the error at iteration k by ek , and it is usually given by ek = xk −x∗ ,where xk is the approximate solution at iteration k, and x∗ is the true solution. Some methods for one-dimensional problems do not actually produce a specific approximate solutionxk , however, but merely produce an interval known to contain the solution, with the lengthof the interval decreasing as iterations proceed.
For such methods, we take ek to be thelength of this interval at iteration k. In either case, a method is said to converge with rater ifkek+1 klim=Ck→∞ kek krfor some finite nonzero constant C. Some particular cases of interest are these:154CHAPTER 5.
NONLINEAR EQUATIONS• If r = 1 and C < 1, the convergence rate is linear.• If r > 1, the convergence rate is superlinear.• If r = 2, the convergence rate is quadratic.One way to interpret the distinction between linear and superlinear convergence is that,asymptotically, a linearly convergent sequence gains a constant number of digits of accuracyper iteration, whereas a superlinearly convergent sequence gains an increasing number ofdigits of accuracy with each iteration.
Specifically, a linearly convergent sequence gains− logβ (C) base-β digits per iteration, but a superlinearly convergent sequence has r times asmany digits of accuracy after each iteration as it had the previous iteration. In particular,a quadratically convergent method doubles the number of digits of accuracy with eachiteration.5.2Nonlinear Equations in One DimensionWe first consider methods for nonlinear equations in one dimension.
Given a functionf : R → R, we seek a point x such that f (x) = 0.5.2.1Bisection MethodIn finite-precision arithmetic, there may not be a floating-point number x such that f (x)is exactly zero. One alternative is to look for a very short interval [a, b] in which f has achange of sign, since the corresponding continuous function must be zero somewhere withinsuch an interval. An interval for which the sign of f differs at its endpoints is called abracket.
The bisection method begins with an initial bracket and successively reduces itslength until the solution has been isolated as accurately as desired. At each iteration, thefunction is evaluated at the midpoint of the current interval, and half of the interval canthen be discarded, depending on the sign of the function at the midpoint. More formally,the algorithm is as follows, where sign(x) = 1 if x ≥ 0 and sign(x) = −1 if x < 0:Initial input: a function f , an interval [a, b] such that sign(f (a)) 6= sign(f (b)), and anerror tolerance tol.while ((b − a) > tol) dom = a + (b − a)/2if sign(f (a)) = sign(f (m)) thena=melseb=mendend......................................................................................................................................................ambExample 5.4 Bisection Method.
We illustrate the bisection method by finding a rootof the equationf (x) = x2 − 4 sin(x) = 0.For the initial bracketing interval [a, b], we take a = 1 and b = 3. All that really mattersis that the function values differ in sign at the two points. We evaluate the function at the5.2. NONLINEAR EQUATIONS IN ONE DIMENSION155midpoint m = a + (b − a)/2 = 2 and find that f (m) has the opposite sign from f (a), sowe retain the first half of the initial interval by setting b = m.
We then repeat the processuntil the bracketing interval isolates the root of the equation as accurately as desired. Thesequence of iterations is shown here.a1.0000001.0000001.5000001.7500001.8750001.8750001.9062501.9218751.9296881.9335941.9335941.9335941.9335941.9335941.9337161.9337161.9337461.9337461.9337461.9337501.9337521.933753f (a)−2.365884−2.365884−1.739980−0.873444−0.300718−0.300718−0.143255−0.062406−0.021454−0.000846−0.000846−0.000846−0.000846−0.000846−0.000201−0.000201−0.000039−0.000039−0.000039−0.000019−0.000009−0.000004b3.0000002.0000002.0000002.0000002.0000001.9375001.9375001.9375001.9375001.9375001.9355471.9345701.9340821.9338381.9338381.9337771.9337771.9337621.9337541.9337541.9337541.933754f (b)8.4355200.3628100.3628100.3628100.3628100.0198490.0198490.0198490.0198490.0198490.0094910.0043200.0017360.0004450.0004450.0001220.0001220.0000410.0000010.0000010.0000010.000001The bisection method makes no use of the magnitudes of the function values, only theirsigns.
As a result, bisection is certain to converge but does so rather slowly. Specifically,at each successive iteration the length of the interval containing the solution, and hence abound on the possible error, is reduced by half. This means that the bisection method islinearly convergent, with r = 1 and C = 0.5. Another way of stating this is that we gain onebit of accuracy in the approximate solution for each iteration of bisection. Given a startinginterval [a, b], the length of the interval after k iterations is (b − a)/2k , so that achieving anerror tolerance of tol requiresb−alog2toliterations, regardless of the particular function f involved.5.2.2Fixed-Point IterationGiven a function g: R → R, a value x such thatx = g(x)is called a fixed point of the function g, since x is unchanged when g is applied to it.Fixed-point problems often arise directly in practice, but they are also important because156CHAPTER 5.
NONLINEAR EQUATIONSa nonlinear equation can often be recast as a fixed-point problem for a related nonlinearfunction. Indeed, many iterative algorithms for solving nonlinear equations are based oniteration schemes of the formxk+1 = g(xk ),where g is a suitably chosen function whose fixed points are solutions for f (x) = 0. Such ascheme is called fixed-point iteration or sometimes functional iteration, since the function gis applied repeatedly to an initial starting value x0 .For a given equation f (x) = 0, there may be many equivalent fixed-point problemsx = g(x) with different choices for the function g.
But not all fixed-point formulationsare equally useful in deriving an iteration scheme for solving a given nonlinear equation.The resulting iteration schemes may differ not only in their convergence rates but also inwhether they converge at all.Example 5.5 Fixed-Point Problems. For the nonlinear equationf (x) = x2 − x − 2 = 0,any of the choicesg(x) = x2 − 2,√g(x) =x + 2,g(x) = 1 + 2/x,x2 + 2g(x) =2x − 1is a function whose fixed points are solutions to the equation f (x) = 0. Each of thesefunctions is plotted in Fig.
5.3, where we see that the intersection of the curve y = g(x)with the line y = x is what we seek. By design, each of the functions passes through thepoint (2, 2), and indeed f (2) = 0.The corresponding iteration schemes are depicted graphically in Fig. 5.4. A verticalarrow corresponds to evaluation of the function at a point, and a horizontal arrow pointingto the line y = x indicates that the result of the previous function evaluation is used asthe argument for the next.
For the first of these functions, even with a starting point verynear the solution, the iteration scheme diverges. For the other three functions, the iterationscheme converges to the fixed point even if it is started relatively far from the solution,although the apparent rates of convergence vary somewhat.As one can see from Fig. 5.4, the behavior of fixed-point iteration schemes can varywidely, from divergence, to slow convergence, to rapid convergence.
What makes the difference? The simplest (though not the most general) way to characterize the behavior ofan iterative scheme xk+1 = g(xk ) for the fixed-point problem x = g(x) is to consider thederivative of g at the solution x∗ , assuming that g is smooth. In particular, if x∗ = g(x∗ )and|g 0 (x∗ )| < 1,5.2. NONLINEAR EQUATIONS IN ONE DIMENSION3157................................
............. ............ ......... .......................x2 +2 ....... .................. ....2x−1 .......... .................. ........... ..................................... ........ ......... ..............................................................................................................................................................
. .................... ...... ... .................................................... .................................. ...... .................................................................2................................................y=2y=10√x+2y = 1 + 2/xy=x0y =x −2123Figure 5.3: A fixed point of some nonlinear functions.3............... ...........
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
