Conte, de Boor - Elementary Numerical Analysis. An Algorithmic Approach (523140), страница 5
Текст из файла (страница 5)
It can then be assumed that thesame accumulation of roundoff will occur in other problems solved withthe same subroutine. This method is extremely costly in machine timesince double-precision arithmetic increases computer time by a factor of 8on some machines, and in addition, it is not always possible to isolateother errors.A second method is interval arithmetic. Here each number is represented by two machine numbers, the maximum and the minimum valuesthat it might have. Whenever an operation is performed, one computes itsmaximum and minimum values.
Essentially, then, one will obtain twosolutions at every step, the true solution necessarily being contained withinthe range determined by the maximum and minimum values. This methodrequires more than twice the amount of computer time and about twice thestorage of a standard run. Moreover, the usual assumption that the truesolution lies about midway within the range is not, in general, valid. Thusthe range might be so large that any estimate of the round-off error basedupon this would be grossly exaggerated.A third approach is significant-digit arithmetic.
As pointed out earlier,whenever two nearly equal machine numbers are subtracted, there is adanger that some significant digits will be lost. In significant-digitarithmetic an attempt is made to keep track of digits so lost. In one version1.6SOME COMMENTS ON CONVERGENCE OF SEQUENCES19only the significant digits in any number are retained, all others beingdiscarded. At the end of a computation we will thus be assured that alldigits retained are significant.
The main objection to this method is thatsome information is lost whenever digits are discarded, and that the resultsobtained are likely to be much too conservative. Experimentation with thistechnique is still going on, although the experience to date is not toopromising.A fourth method which gives considerable promise of providing anadequate mathematical theory of round-off-error propagation is based ona statistical approach. It begins with the assumption that round-off errorsare independent. This assumption is, of course, not valid, because if thesame problem is run on the same machine several times, the answers willalways be the same.
We can, however, adopt a stochastic model of thepropagation of round-off errors in which the local errors are treated as ifthey were random variables. Thus we can assume that the local round-offerrors are either uniformly or normally distributed between their extremevalues. Using statistical methods, we can then obtain the standard deviation, the variance of distribution, and estimates of the accumulated roundoff error. The statistical approach is considered in some detail by Hamming [1] and Henrici [2]. The method does involve substantial analysis andadditional computer time, but in the experiments conducted to date it hasobtained error estimates which are in remarkable agreement with experimentally available evidence.A fifth method is backward error analysis, as introduced in Sec.
1.3. Aswe saw, it reduces the analysis of rounding error effects to a study ofperturbations in exact arithmetic and, ultimately, to a question of condition. We will make good use of this method in Chap. 4.1.6 SOME COMMENTS ON CONVERGENCE OFSEQUENCESCalculus, and more generally analysis, is based on the notion of convergence. Basic concepts such as derivative, integral, and continuity aredefined in terms of convergent sequences, and elementary functions suchas ln x or sin x are defined by convergent series, At the same time,numerical answers to engineering and scientific problems are never neededexactly.
Rather, an approximation to the answer is required which isaccurate “to a certain number of decimal places,” or accurate to within agiven toleranceIt is therefore not surprising that many numerical methods for findingthe answerof a given problem merely produce (the first few terms of) asequencewhich is shown to converge to the desired answer.20NUMBER SYSTEMS AND ERRORSTo recall the definition:of (real or complex) numbers converges to a if and only if, for allA sequencethere exists an integersuch that for allHence, if we have a numerical method which produces a sequenceconverging to the desired answerthen we can calculate a toany desired accuracy merely by calculatingfor “large enough” n.From a computational point of view, this definition is unsatisfactoryfor the following reasons: (1) It is often not possible (without knowing theanswerto know when n is “large enough.” In other words, it is difficultto get hold of the functionmentioned in the definition of convergence.
(2) Even when some knowledge aboutis available, it may turnout that the required n is too large to make the calculation offeasible.Example The numberis the value of the infinite seriesHence, withthe sequenceis monotone-decreasing to its limitMoreover,To calculatecorrect to within 10-6 using this sequence, we would need 106 < 4 n +3, or roughly, n = 250,000. On a computer using eight-decimal-digit floating-pointarithmetic, round-off in the calculation ofis probably much larger than 10-6.Hencecould not be computed to within 10-6 using this sequence (except, perhaps,by adding the terms from smallest to largest).To deal with these problems, some notation is useful.
Specifically, wewould like to measure how fast sequences converge. As with all measuring,this is done by comparison, with certain standard sequences, such asThe comparison is made as follows: one says thatand writesis of order(1.24)in case(1.25)1.6SOME COMMENTS ON CONVERGENCE OF SEQUENCES 21for some constant K and all sufficiently large n. ThusFurther, if it is possible to choose the constant K in (1.25) arbitrarily smallas soon as n is large enough; that is, should it happen thatthen one says thatwritesis of higher order thanand(1.26)Thuswhile sinThe order notation appears customarily only on the right-hand side ofan equation and serves the purpose of describing the essential feature of anerror term without bothering about multiplying constants or other detail.For instance, we can state concisely the unsatisfactory state of affairs inthe earlier example by saying thatbut alsoi.e., the series converges toas fast as 1/n (goes to zero) but no faster.A convergence order or rate of l/n is much too slow to be useful incalculations.Example Ifthen, by definition,is just a fancy way of saying that the sequenceHenceconverges toExample If |r| < 1, then the geometric serieswe haveFurther, ifthensums to 1/(1 - r).
WithThus22NUMBER SYSTEMS AND ERRORSfor some |r| < 1, we say that the convergence is (atHence, whenever a,,least) geometric, for it is then (at least) of the same order as the convergence of thegeometric series.than to know nothing,Although it is better to know thatknowledge about the order of convergence becomes quite useful only whenwe know more precisely thatThis says that for “large enough”To put it differently,is a sequence converging to zero.
Although we cannotwhereprove that a certain n is “large enough,” we can test the hypothesis that n is“large enough” by comparingwithIffor k near n, say for k = n - 2, n - 1, n, then we accept the hypothesisthat n is “large enough” forto be true, and therefore acceptExample Let p > 1. Then the seriesgeometric seriesTo get a more precise statement, considerThenas a good estimate of the errorconverges to its limitlike the1.6 SOME COMMENTS ON CONVERGENCE OF SEQUENCES 23For the ratios, we findwhich is, e.g., within 1/10 of 1 for n = 3 and p = 2. Thus,In fact,good indication of the error ininis therefore 0.12005 · · · .is then athe errorThis notation carries over to functions of a real variable.
Ifwe say that the convergence isprovidedfor some finite constant K and all small enough h. If this holds for allK > 0, that is, ifthen we call the convergence o(f(h)).Example For h “near” zero, we haveHence, for allExample If the function f(x) has a zero of orderthenRules for calculating with the order symbols are collected in the followinglemma.and c is a constant,Lemma 1.1 IfthenIf alsothen(1.27)If, further,then also24NUMBER SYSTEMS AND ERRORSwhile ifthenFinally, all statements remain true ifis replaced by o throughout.The approximate calculation of a number via a sequenceconverging to always involves an act of faith regardless of whether or notthe order of convergence is known.
Given that the sequence is known toconverge to practicing numerical analysts ascertain that n is “largeenough” by making sure that, for small values ofdiffers “littleIf they also know that the convergence isenough” fromthey check whether or not the sequence behaves accordingly near n. If theyalso know that a satisfies certain equations or inequalities— might be thesought-for solution of an equation—they check that satisfies theseequations or inequalities “well enough.” In short, practicing numericalanalysts make sure that n satisfies all conditions they can think of whichare necessary for n to be “large enough.” If all these conditions aresatisfied, then, lacking sufficient conditions for n to be “large enough,”they accepton faith as a good enough approximation toIn a way,numerical analysts use all means at their disposal to distinguish a “goodenough” approximation from a bad one. They can do no more (and shoulddo no less).It follows that numerical results arrived at in this way should not bemistaken for final answers.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
