c9-3 (779533)
Текст из файла
9.3 Van Wijngaarden–Dekker–Brent Method359}else {if (fl == 0.0) return x1;if (fh == 0.0) return x2;nrerror("root must be bracketed in zriddr.");}return 0.0;Never get here.}CITED REFERENCES AND FURTHER READING:Ralston, A., and Rabinowitz, P. 1978, A First Course in Numerical Analysis, 2nd ed. (New York:McGraw-Hill), §8.3.Ostrowski, A.M.
1966, Solutions of Equations and Systems of Equations, 2nd ed. (New York:Academic Press), Chapter 12.Ridders, C.J.F. 1979, IEEE Transactions on Circuits and Systems, vol. CAS-26, pp. 979–980. [1]9.3 Van Wijngaarden–Dekker–Brent MethodWhile secant and false position formally converge faster than bisection, onefinds in practice pathological functions for which bisection converges more rapidly.These can be choppy, discontinuous functions, or even smooth functions if the secondderivative changes sharply near the root. Bisection always halves the interval, whilesecant and false position can sometimes spend many cycles slowly pulling distantbounds closer to a root. Ridders’ method does a much better job, but it too cansometimes be fooled.
Is there a way to combine superlinear convergence with thesureness of bisection?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).for (j=1;j<=MAXIT;j++) {xm=0.5*(xl+xh);fm=(*func)(xm);First of two function evaluations per its=sqrt(fm*fm-fl*fh);eration.if (s == 0.0) return ans;xnew=xm+(xm-xl)*((fl >= fh ? 1.0 : -1.0)*fm/s);Updating formula.if (fabs(xnew-ans) <= xacc) return ans;ans=xnew;fnew=(*func)(ans);Second of two function evaluations perif (fnew == 0.0) return ans;iteration.if (SIGN(fm,fnew) != fm) {Bookkeeping to keep the root bracketedxl=xm;on next iteration.fl=fm;xh=ans;fh=fnew;} else if (SIGN(fl,fnew) != fl) {xh=ans;fh=fnew;} else if (SIGN(fh,fnew) != fh) {xl=ans;fl=fnew;} else nrerror("never get here.");if (fabs(xh-xl) <= xacc) return ans;}nrerror("zriddr exceed maximum iterations");360Chapter 9.Root Finding and Nonlinear Sets of Equationsx=[y − f(a)][y − f(b)]c[y − f(b)][y − f(c)]a+[f(c) − f(a)][f(c) − f(b)] [f(a) − f(b)][f(a) − f(c)][y − f(c)][y − f(a)]b+[f(b) − f(c)][f(b) − f(a)](9.3.1)Setting y to zero gives a result for the next root estimate, which can be written asx = b + P/Q(9.3.2)where, in terms ofR ≡ f(b)/f(c),S ≡ f(b)/f(a),T ≡ f(a)/f(c)(9.3.3)we haveP = S [T (R − T )(c − b) − (1 − R)(b − a)]Q = (T − 1)(R − 1)(S − 1)(9.3.4)(9.3.5)In practice b is the current best estimate of the root and P/Q ought to be a “small”correction.
Quadratic methods work well only when the function behaves smoothly;they run the serious risk of giving very bad estimates of the next root or causingmachine failure by an inappropriate division by a very small number (Q ≈ 0).Brent’s method guards against this problem by maintaining brackets on the rootand checking where the interpolation would land before carrying out the division.When the correction P/Q would not land within the bounds, or when the boundsare not collapsing rapidly enough, the algorithm takes a bisection step. Thus,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).Yes.
We can keep track of whether a supposedly superlinear method is actuallyconverging the way it is supposed to, and, if it is not, we can intersperse bisectionsteps so as to guarantee at least linear convergence. This kind of super-strategyrequires attention to bookkeeping detail, and also careful consideration of howroundoff errors can affect the guiding strategy. Also, we must be able to determinereliably when convergence has been achieved.An excellent algorithm that pays close attention to these matters was developedin the 1960s by van Wijngaarden, Dekker, and others at the Mathematical Centerin Amsterdam, and later improved by Brent [1].
For brevity, we refer to the finalform of the algorithm as Brent’s method. The method is guaranteed (by Brent)to converge, so long as the function can be evaluated within the initial intervalknown to contain a root.Brent’s method combines root bracketing, bisection, and inverse quadraticinterpolation to converge from the neighborhood of a zero crossing. While the falseposition and secant methods assume approximately linear behavior between twoprior root estimates, inverse quadratic interpolation uses three prior points to fit aninverse quadratic function (x as a quadratic function of y) whose value at y = 0 istaken as the next estimate of the root x.
Of course one must have contingency plansfor what to do if the root falls outside of the brackets. Brent’s method takes care ofall that. If the three point pairs are [a, f(a)], [b, f(b)], [c, f(c)] then the interpolationformula (cf. equation 3.1.1) is9.3 Van Wijngaarden–Dekker–Brent Method361Brent’s method combines the sureness of bisection with the speed of a higher-ordermethod when appropriate.
We recommend it as the method of choice for generalone-dimensional root finding where a function’s values only (and not its derivativeor functional form) are available.Maximum allowed number of iterations.Machine floating-point precision.float zbrent(float (*func)(float), float x1, float x2, float tol)Using Brent’s method, find the root of a function func known to lie between x1 and x2. Theroot, returned as zbrent, will be refined until its accuracy is tol.{int iter;float a=x1,b=x2,c=x2,d,e,min1,min2;float fa=(*func)(a),fb=(*func)(b),fc,p,q,r,s,tol1,xm;if ((fa > 0.0 && fb > 0.0) || (fa < 0.0 && fb < 0.0))nrerror("Root must be bracketed in zbrent");fc=fb;for (iter=1;iter<=ITMAX;iter++) {if ((fb > 0.0 && fc > 0.0) || (fb < 0.0 && fc < 0.0)) {c=a;Rename a, b, c and adjust bounding intervalfc=fa;d.e=d=b-a;}if (fabs(fc) < fabs(fb)) {a=b;b=c;c=a;fa=fb;fb=fc;fc=fa;}tol1=2.0*EPS*fabs(b)+0.5*tol;Convergence check.xm=0.5*(c-b);if (fabs(xm) <= tol1 || fb == 0.0) return b;if (fabs(e) >= tol1 && fabs(fa) > fabs(fb)) {s=fb/fa;Attempt inverse quadratic interpolation.if (a == c) {p=2.0*xm*s;q=1.0-s;} else {q=fa/fc;r=fb/fc;p=s*(2.0*xm*q*(q-r)-(b-a)*(r-1.0));q=(q-1.0)*(r-1.0)*(s-1.0);}if (p > 0.0) q = -q;Check whether in bounds.p=fabs(p);min1=3.0*xm*q-fabs(tol1*q);min2=fabs(e*q);if (2.0*p < (min1 < min2 ? min1 : min2)) {e=d;Accept interpolation.d=p/q;} else {d=xm;Interpolation failed, use bisection.e=d;}} else {Bounds decreasing too slowly, use bisection.d=xm;e=d;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).#include <math.h>#include "nrutil.h"#define ITMAX 100#define EPS 3.0e-8362Chapter 9.Root Finding and Nonlinear Sets of Equations}a=b;fa=fb;if (fabs(d) > tol1)b += d;elseb += SIGN(tol1,xm);fb=(*func)(b);Move last best guess to a.Evaluate new trial root.}CITED REFERENCES AND FURTHER READING:Brent, R.P. 1973, Algorithms for Minimization without Derivatives (Englewood Cliffs, NJ: PrenticeHall), Chapters 3, 4.
[1]Forsythe, G.E., Malcolm, M.A., and Moler, C.B. 1977, Computer Methods for MathematicalComputations (Englewood Cliffs, NJ: Prentice-Hall), §7.2.9.4 Newton-Raphson Method Using DerivativePerhaps the most celebrated of all one-dimensional root-finding routines is Newton’s method, also called the Newton-Raphson method.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
