c9-0 (779530)
Текст из файла
9.0 IntroductionWe now consider that most basic of tasks, solving equations numerically. Whilemost equations are born with both a right-hand side and a left-hand side, onetraditionally moves all terms to the left, leavingf(x) = 0(9.0.1)whose solution or solutions are desired.
When there is only one independent variable,the problem is one-dimensional, namely to find the root or roots of a function.With more than one independent variable, more than one equation can besatisfied simultaneously. You likely once learned the implicit function theoremwhich (in this context) gives us the hope of satisfying N equations in N unknownssimultaneously. Note that we have only hope, not certainty. A nonlinear set ofequations may have no (real) solutions at all. Contrariwise, it may have more thanone solution. The implicit function theorem tells us that “generically” the solutionswill be distinct, pointlike, and separated from each other.
If, however, life is sounkind as to present you with a nongeneric, i.e., degenerate, case, then you can geta continuous family of solutions. In vector notation, we want to find one or moreN -dimensional solution vectors x such thatf(x) = 0(9.0.2)where f is the N -dimensional vector-valued function whose components are theindividual equations to be satisfied simultaneously.Don’t be fooled by the apparent notational similarity of equations (9.0.2) and(9.0.1).
Simultaneous solution of equations in N dimensions is much more difficultthan finding roots in the one-dimensional case. The principal difference between oneand many dimensions is that, in one dimension, it is possible to bracket or “trap” a rootbetween bracketing values, and then hunt it down like a rabbit.
In multidimensions,you can never be sure that the root is there at all until you have found it.Except in linear problems, root finding invariably proceeds by iteration, andthis is equally true in one or in many dimensions. Starting from some approximatetrial solution, a useful algorithm will improve the solution until some predeterminedconvergence criterion is satisfied. For smoothly varying functions, good algorithms347Sample 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).Chapter 9.
Root Finding andNonlinear Sets of Equations348Chapter 9.Root Finding and Nonlinear Sets of EquationsSample 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).will always converge, provided that the initial guess is good enough. Indeed one caneven determine in advance the rate of convergence of most algorithms.It cannot be overemphasized, however, how crucially success depends onhaving a good first guess for the solution, especially for multidimensional problems.This crucial beginning usually depends on analysis rather than numerics.
Carefullycrafted initial estimates reward you not only with reduced computational effort, butalso with understanding and increased self-esteem. Hamming’s motto, “the purposeof computing is insight, not numbers,” is particularly apt in the area of findingroots. You should repeat this motto aloud whenever your program converges, withten-digit accuracy, to the wrong root of a problem, or whenever it fails to convergebecause there is actually no root, or because there is a root but your initial estimatewas not sufficiently close to it.“This talk of insight is all very well, but what do I actually do?” For onedimensional root finding, it is possible to give some straightforward answers: Youshould try to get some idea of what your function looks like before trying to findits roots.
If you need to mass-produce roots for many different functions, then youshould at least know what some typical members of the ensemble look like. Next,you should always bracket a root, that is, know that the function changes sign in anidentified interval, before trying to converge to the root’s value.Finally (this is advice with which some daring souls might disagree, butwe give it nonetheless) never let your iteration method get outside of the bestbracketing bounds obtained at any stage.
We will see below that some pedagogicallyimportant algorithms, such as secant method or Newton-Raphson, can violate thislast constraint, and are thus not recommended unless certain fixups are implemented.Multiple roots, or very close roots, are a real problem, especially if themultiplicity is an even number. In that case, there may be no readily apparentsign change in the function, so the notion of bracketing a root — and maintainingthe bracket — becomes difficult. We are hard-liners: we nevertheless insist onbracketing a root, even if it takes the minimum-searching techniques of Chapter 10to determine whether a tantalizing dip in the function really does cross zero or not.(You can easily modify the simple golden section routine of §10.1 to return earlyif it detects a sign change in the function.
And, if the minimum of the function isexactly zero, then you have found a double root.)As usual, we want to discourage you from using routines as black boxes withoutunderstanding them. However, as a guide to beginners, here are some reasonablestarting points:• Brent’s algorithm in §9.3 is the method of choice to find a bracketed rootof a general one-dimensional function, when you cannot easily computethe function’s derivative. Ridders’ method (§9.2) is concise, and a closecompetitor.• When you can compute the function’s derivative, the routine rtsafe in§9.4, which combines the Newton-Raphson method with some bookkeeping on bounds, is recommended. Again, you must first bracket your root.• Roots of polynomials are a special case.
Laguerre’s method, in §9.5,is recommended as a starting point. Beware: Some polynomials areill-conditioned!• Finally, for multidimensional problems, the only elementary method isNewton-Raphson (§9.6), which works very well if you can supply a9.0 Introduction349#include <stdio.h>#define ISCR 60#define JSCR 21#define BLANK ’ ’#define ZERO ’-’#define YY ’l’#define XX ’-’#define FF ’x’Number of horizontal and vertical positions in display.void scrsho(float (*fx)(float))For interactive CRT terminal use. Produce a crude graph of the function fx over the promptedfor interval x1,x2.
Query for another plot until the user signals satisfaction.{int jz,j,i;float ysml,ybig,x2,x1,x,dyj,dx,y[ISCR+1];char scr[ISCR+1][JSCR+1];for (;;) {printf("\nEnter x1 x2 (x1=x2 to stop):\n");Query for another plot, quitscanf("%f %f",&x1,&x2);if x1=x2.if (x1 == x2) break;for (j=1;j<=JSCR;j++)Fill vertical sides with character ’l’.scr[1][j]=scr[ISCR][j]=YY;for (i=2;i<=(ISCR-1);i++) {scr[i][1]=scr[i][JSCR]=XX;Fill top, bottom with character ’-’.for (j=2;j<=(JSCR-1);j++)Fill interior with blanks.scr[i][j]=BLANK;}dx=(x2-x1)/(ISCR-1);x=x1;ysml=ybig=0.0;Limits will include 0.for (i=1;i<=ISCR;i++) {Evaluate the function at equal intervals.y[i]=(*fx)(x);Find the largest and smallest valif (y[i] < ysml) ysml=y[i];ues.if (y[i] > ybig) ybig=y[i];x += dx;}if (ybig == ysml) ybig=ysml+1.0;Be sure to separate top and bottom.dyj=(JSCR-1)/(ybig-ysml);jz=1-(int) (ysml*dyj);Note which row corresponds to 0.for (i=1;i<=ISCR;i++) {Place an indicator at function height andscr[i][jz]=ZERO;0.j=1+(int) ((y[i]-ysml)*dyj);scr[i][j]=FF;}printf(" %10.3f ",ybig);for (i=1;i<=ISCR;i++) printf("%c",scr[i][JSCR]);printf("\n");for (j=(JSCR-1);j>=2;j--) {Display.printf("%12s"," ");for (i=1;i<=ISCR;i++) printf("%c",scr[i][j]);printf("\n");}printf(" %10.3f ",ysml);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).good first guess of the solution. Try it. Then read the more advancedmaterial in §9.7 for some more complicated, but globally more convergent,alternatives.Avoiding implementations for specific computers, this book must generallysteer clear of interactive or graphics-related routines.
We make an exception rightnow. The following routine, which produces a crude function plot with interactivelyscaled axes, can save you a lot of grief as you enter the world of root finding.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.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
