c9-1 (779531)
Текст из файла
350Chapter 9.Root Finding and Nonlinear Sets of Equationsfor (i=1;i<=ISCR;i++) printf("%c",scr[i][1]);printf("\n");printf("%8s %10.3f %44s %10.3f\n"," ",x1," ",x2);}}Stoer, J., and Bulirsch, R. 1980, Introduction to Numerical Analysis (New York: Springer-Verlag),Chapter 5.Acton, F.S. 1970, Numerical Methods That Work; 1990, corrected edition (Washington: Mathematical Association of America), Chapters 2, 7, and 14.Ralston, A., and Rabinowitz, P. 1978, A First Course in Numerical Analysis, 2nd ed. (New York:McGraw-Hill), Chapter 8.Householder, A.S.
1970, The Numerical Treatment of a Single Nonlinear Equation (New York:McGraw-Hill).9.1 Bracketing and BisectionWe will say that a root is bracketed in the interval (a, b) if f(a) and f(b)have opposite signs. If the function is continuous, then at least one root must lie inthat interval (the intermediate value theorem). If the function is discontinuous, butbounded, then instead of a root there might be a step discontinuity which crosseszero (see Figure 9.1.1). For numerical purposes, that might as well be a root, sincethe behavior is indistinguishable from the case of a continuous function whose zerocrossing occurs in between two “adjacent” floating-point numbers in a machine’sfinite-precision representation. Only for functions with singularities is there thepossibility that a bracketed root is not really there, as for examplef(x) =1x−c(9.1.1)Some root-finding algorithms (e.g., bisection in this section) will readily convergeto c in (9.1.1).
Luckily there is not much possibility of your mistaking c, or anynumber x close to it, for a root, since mere evaluation of |f(x)| will give a verylarge, rather than a very small, result.If you are given a function in a black box, there is no sure way of bracketingits roots, or of even determining that it has roots. If you like pathological examples,think about the problem of locating the two real roots of equation (3.0.1), which dipsbelow zero only in the ridiculously small interval of about x = π ± 10−667.In the next chapter we will deal with the related problem of bracketing afunction’s minimum. There it is possible to give a procedure that always succeeds;in essence, “Go downhill, taking steps of increasing size, until your function startsback uphill.” There is no analogous procedure for roots. The procedure “go downhilluntil your function changes sign,” can be foiled by a function that has a simpleextremum.
Nevertheless, if you are prepared to deal with a “failure” outcome, thisprocedure is often a good first start; success is usual if your function has oppositesigns in the limit x → ±∞.Sample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5)Copyright (C) 1988-1992 by Cambridge University Press.Programs Copyright (C) 1988-1992 by Numerical Recipes Software.Permission is granted for internet users to make one paper copy for their own personal use.
Further reproduction, or any copying of machinereadable files (including this one) to any servercomputer, is strictly prohibited. To order Numerical Recipes books,diskettes, or CDROMsvisit website http://www.nr.com or call 1-800-872-7423 (North America only),or send email to trade@cup.cam.ac.uk (outside North America).CITED REFERENCES AND FURTHER READING:bax1(a)(b)(c)ab(d)Figure 9.1.1. Some situations encountered while root finding: (a) shows an isolated root x1 bracketedby two points a and b at which the function has opposite signs; (b) illustrates that there is not necessarilya sign change in the function near a double root (in fact, there is not necessarily a root!); (c) is apathological function with many roots; in (d) the function has opposite signs at points a and b, but thepoints bracket a singularity, not a root.Sample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5)Copyright (C) 1988-1992 by Cambridge University Press.Programs Copyright (C) 1988-1992 by Numerical Recipes Software.Permission is granted for internet users to make one paper copy for their own personal use.
Further reproduction, or any copying of machinereadable files (including this one) to any servercomputer, is strictly prohibited. To order Numerical Recipes books,diskettes, or CDROMsvisit website http://www.nr.com or call 1-800-872-7423 (North America only),or send email to trade@cup.cam.ac.uk (outside North America).a x2 x3 bx1 dcfe3519.1 Bracketing and Bisection352Chapter 9.Root Finding and Nonlinear Sets of Equations#include <math.h>#define FACTOR 1.6#define NTRY 50if (*x1 == *x2) nrerror("Bad initial range in zbrac");f1=(*func)(*x1);f2=(*func)(*x2);for (j=1;j<=NTRY;j++) {if (f1*f2 < 0.0) return 1;if (fabs(f1) < fabs(f2))f1=(*func)(*x1 += FACTOR*(*x1-*x2));elsef2=(*func)(*x2 += FACTOR*(*x2-*x1));}return 0;}Alternatively, you might want to “look inward” on an initial interval, ratherthan “look outward” from it, asking if there are any roots of the function f(x) inthe interval from x1 to x2 when a search is carried out by subdivision into n equalintervals. The following function calculates brackets for up to nb distinct intervalswhich each contain one or more roots.void zbrak(float (*fx)(float), float x1, float x2, int n, float xb1[],float xb2[], int *nb)Given a function fx defined on the interval from x1-x2 subdivide the interval into n equallyspaced segments, and search for zero crossings of the function.
nb is input as the maximum number of roots sought, and is reset to the number of bracketing pairs xb1[1..nb], xb2[1..nb]that are found.{int nbb,i;float x,fp,fc,dx;nbb=0;dx=(x2-x1)/n;Determine the spacing appropriate to the mesh.fp=(*fx)(x=x1);for (i=1;i<=n;i++) {Loop over all intervalsfc=(*fx)(x += dx);if (fc*fp <= 0.0) {If a sign change occurs then record values for thexb1[++nbb]=x-dx;bounds.xb2[nbb]=x;if(*nb == nbb) return;}fp=fc;}*nb = nbb;}Sample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5)Copyright (C) 1988-1992 by Cambridge University Press.Programs Copyright (C) 1988-1992 by Numerical Recipes Software.Permission is granted for internet users to make one paper copy for their own personal use. Further reproduction, or any copying of machinereadable files (including this one) to any servercomputer, is strictly prohibited. To order Numerical Recipes books,diskettes, or CDROMsvisit website http://www.nr.com or call 1-800-872-7423 (North America only),or send email to trade@cup.cam.ac.uk (outside North America).int zbrac(float (*func)(float), float *x1, float *x2)Given a function func and an initial guessed range x1 to x2, the routine expands the rangegeometrically until a root is bracketed by the returned values x1 and x2 (in which case zbracreturns 1) or until the range becomes unacceptably large (in which case zbrac returns 0).{void nrerror(char error_text[]);int j;float f1,f2;3539.1 Bracketing and BisectionBisection Methodn+1 = n /2(9.1.2)neither more nor less.
Thus, we know in advance the number of iterations requiredto achieve a given tolerance in the solution,0(9.1.3)n = log2where 0 is the size of the initially bracketing interval, is the desired endingtolerance.Bisection must succeed. If the interval happens to contain two or more roots,bisection will find one of them. If the interval contains no roots and merely straddlesa singularity, it will converge on the singularity.When a method converges as a factor (less than 1) times the previous uncertaintyto the first power (as is the case for bisection), it is said to converge linearly. Methodsthat converge as a higher power,n+1 = constant × (n )mm>1(9.1.4)are said to converge superlinearly.
In other contexts “linear” convergence would betermed “exponential,” or “geometrical.” That is not too bad at all: Linear convergencemeans that successive significant figures are won linearly with computational effort.It remains to discuss practical criteria for convergence. It is crucial to keep inmind that computers use a fixed number of binary digits to represent floating-pointnumbers. While your function might analytically pass through zero, it is possible thatits computed value is never zero, for any floating-point argument. One must decidewhat accuracy on the root is attainable: Convergence to within 10−6 in absolutevalue is reasonable when the root lies near 1, but certainly unachievable if the rootlies near 1026.
One might thus think to specify convergence by a relative (fractional)criterion, but this becomes unworkable for roots near zero. To be most general, theroutines below will require you to specify an absolute tolerance, such that iterationscontinue until the interval becomes smaller than this tolerance in absolute units.Usually you may wish to take the tolerance to be (|x1 | + |x2 |)/2 where is themachine precision and x1 and x2 are the initial brackets. When the root lies near zeroyou ought to consider carefully what reasonable tolerance means for your function.The following routine quits after 40 bisections in any event, with 2−40 ≈ 10−12.Sample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5)Copyright (C) 1988-1992 by Cambridge University Press.Programs Copyright (C) 1988-1992 by Numerical Recipes Software.Permission is granted for internet users to make one paper copy for their own personal use.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
