c10-3 (779541)

Файл №779541 c10-3 (Numerical Recipes in C)c10-3 (779541)2017-12-27СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

10.3 One-Dimensional Search with First Derivatives405}CITED REFERENCES AND FURTHER READING:Brent, R.P. 1973, Algorithms for Minimization without Derivatives (Englewood Cliffs, NJ: PrenticeHall), Chapter 5. [1]Forsythe, G.E., Malcolm, M.A., and Moler, C.B. 1977, Computer Methods for MathematicalComputations (Englewood Cliffs, NJ: Prentice-Hall), §8.2.10.3 One-Dimensional Search with FirstDerivativesHere we want to accomplish precisely the same goal as in the previoussection, namely to isolate a functional minimum that is bracketed by the triplet ofabscissas (a, b, c), but utilizing an additional capability to compute the function’sfirst derivative as well as its value.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).etemp=e;e=d;if (fabs(p) >= fabs(0.5*q*etemp) || p <= q*(a-x) || p >= q*(b-x))d=CGOLD*(e=(x >= xm ? a-x : b-x));The above conditions determine the acceptability of the parabolic fit. Here wetake the golden section step into the larger of the two segments.else {d=p/q;Take the parabolic step.u=x+d;if (u-a < tol2 || b-u < tol2)d=SIGN(tol1,xm-x);}} else {d=CGOLD*(e=(x >= xm ? a-x : b-x));}u=(fabs(d) >= tol1 ? x+d : x+SIGN(tol1,d));fu=(*f)(u);This is the one function evaluation per iteration.if (fu <= fx) {Now decide what to do with our funcif (u >= x) a=x; else b=x;tion evaluation.SHFT(v,w,x,u)Housekeeping follows:SHFT(fv,fw,fx,fu)} else {if (u < x) a=u; else b=u;if (fu <= fw || w == x) {v=w;w=u;fv=fw;fw=fu;} else if (fu <= fv || v == x || v == w) {v=u;fv=fu;}}Done with housekeeping.

Back for}another iteration.nrerror("Too many iterations in brent");*xmin=x;Never get here.return fx;406Chapter 10.Minimization or Maximization of Functions#include <math.h>#include "nrutil.h"#define ITMAX 100#define ZEPS 1.0e-10#define MOV3(a,b,c, d,e,f) (a)=(d);(b)=(e);(c)=(f);float dbrent(float ax, float bx, float cx, float (*f)(float),float (*df)(float), float tol, float *xmin)Given a function f and its derivative function df, and given a bracketing triplet of abscissas ax,bx, cx [such that bx is between ax and cx, and f(bx) is less than both f(ax) and f(cx)],this routine isolates the minimum to a fractional precision of about tol using a modification ofBrent’s method that uses derivatives.

The abscissa of the minimum is returned as xmin, andSample 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).In principle, we might simply search for a zero of the derivative, ignoring thefunction value information, using a root finder like rtflsp or zbrent (§§9.2–9.3).It doesn’t take long to reject that idea: How do we distinguish maxima from minima?Where do we go from initial conditions where the derivatives on one or both ofthe outer bracketing points indicate that “downhill” is in the direction out of thebracketed interval?We don’t want to give up our strategy of maintaining a rigorous bracket on theminimum at all times.

The only way to keep such a bracket is to update it usingfunction (not derivative) information, with the central point in the bracketing tripletalways that with the lowest function value. Therefore the role of the derivatives canonly be to help us choose new trial points within the bracket.One school of thought is to “use everything you’ve got”: Compute a polynomialof relatively high order (cubic or above) that agrees with some number of previousfunction and derivative evaluations.

For example, there is a unique cubic that agreeswith function and derivative at two points, and one can jump to the interpolatedminimum of that cubic (if there is a minimum within the bracket). Suggested byDavidon and others, formulas for this tactic are given in [1].We like to be more conservative than this. Once superlinear convergence setsin, it hardly matters whether its order is moderately lower or higher. In practicalproblems that we have met, most function evaluations are spent in getting globallyclose enough to the minimum for superlinear convergence to commence.

So we aremore worried about all the funny “stiff” things that high-order polynomials can do(cf. Figure 3.0.1b), and about their sensitivities to roundoff error.This leads us to use derivative information only as follows: The sign of thederivative at the central point of the bracketing triplet (a, b, c) indicates uniquelywhether the next test point should be taken in the interval (a, b) or in the interval(b, c). The value of this derivative and of the derivative at the second-best-so-farpoint are extrapolated to zero by the secant method (inverse linear interpolation),which by itself is superlinear of order 1.618.

(The golden mean again: see [1], p. 57.)We impose the same sort of restrictions on this new trial point as in Brent’s method.If the trial point must be rejected, we bisect the interval under scrutiny.Yes, we are fuddy-duddies when it comes to making flamboyant use of derivativeinformation in one-dimensional minimization. But we have met too many functionswhose computed “derivatives” don’t integrate up to the function value and don’taccurately point the way to the minimum, usually because of roundoff errors,sometimes because of truncation error in the method of derivative evaluation.You will see that the following routine is closely modeled on brent in theprevious section.10.3 One-Dimensional Search with First Derivatives407the minimum function value is returned as dbrent, the returned function value.{int iter,ok1,ok2;Will be used as flags for whether profloat a,b,d,d1,d2,du,dv,dw,dx,e=0.0;posed steps are acceptable or not.float fu,fv,fw,fx,olde,tol1,tol2,u,u1,u2,v,w,x,xm;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).Comments following will point out only differences from the routine brent. Read thatroutine first.a=(ax < cx ? ax : cx);b=(ax > cx ? ax : cx);x=w=v=bx;fw=fv=fx=(*f)(x);dw=dv=dx=(*df)(x);All our housekeeping chores are doufor (iter=1;iter<=ITMAX;iter++) {bled by the necessity of movingxm=0.5*(a+b);derivative values around as wellas function values.tol1=tol*fabs(x)+ZEPS;tol2=2.0*tol1;if (fabs(x-xm) <= (tol2-0.5*(b-a))) {*xmin=x;return fx;}if (fabs(e) > tol1) {d1=2.0*(b-a);Initialize these d’s to an out-of-bracketd2=d1;value.if (dw != dx) d1=(w-x)*dx/(dx-dw);Secant method with one point.if (dv != dx) d2=(v-x)*dx/(dx-dv);And the other.Which of these two estimates of d shall we take? We will insist that they be withinthe bracket, and on the side pointed to by the derivative at x:u1=x+d1;u2=x+d2;ok1 = (a-u1)*(u1-b) > 0.0 && dx*d1 <= 0.0;ok2 = (a-u2)*(u2-b) > 0.0 && dx*d2 <= 0.0;olde=e;Movement on the step before last.e=d;if (ok1 || ok2) {Take only an acceptable d, and ifif (ok1 && ok2)both are acceptable, then taked=(fabs(d1) < fabs(d2) ? d1 : d2); the smallest one.else if (ok1)d=d1;elsed=d2;if (fabs(d) <= fabs(0.5*olde)) {u=x+d;if (u-a < tol2 || b-u < tol2)d=SIGN(tol1,xm-x);} else {Bisect, not golden section.d=0.5*(e=(dx >= 0.0 ? a-x : b-x));Decide which segment by the sign of the derivative.}} else {d=0.5*(e=(dx >= 0.0 ? a-x : b-x));}} else {d=0.5*(e=(dx >= 0.0 ? a-x : b-x));}if (fabs(d) >= tol1) {u=x+d;fu=(*f)(u);} else {u=x+SIGN(tol1,d);fu=(*f)(u);if (fu > fx) {If the minimum step in the downhill*xmin=x;direction takes us uphill, thenreturn fx;we are done.408Chapter 10.Minimization or Maximization of Functions}nrerror("Too many iterations in routine dbrent");return 0.0;Never get here.}CITED REFERENCES AND FURTHER READING:Acton, F.S.

1970, Numerical Methods That Work; 1990, corrected edition (Washington: Mathematical Association of America), pp. 55; 454–458. [1]Brent, R.P. 1973, Algorithms for Minimization without Derivatives (Englewood Cliffs, NJ: PrenticeHall), p. 78.10.4 Downhill Simplex Method inMultidimensionsWith this section we begin consideration of multidimensional minimization,that is, finding the minimum of a function of more than one independent variable.This section stands apart from those which follow, however: All of the algorithmsafter this section will make explicit use of a one-dimensional minimization algorithmas a part of their computational strategy.

This section implements an entirelyself-contained strategy, in which one-dimensional minimization does not figure.The downhill simplex method is due to Nelder and Mead [1]. The methodrequires only function evaluations, not derivatives. It is not very efficient in termsof the number of function evaluations that it requires. Powell’s method (§10.5) isalmost surely faster in all likely applications. However, the downhill simplex methodmay frequently be the best method to use if the figure of merit is “get somethingworking quickly” for a problem whose computational burden is small.The method has a geometrical naturalness about it which makes it delightfulto describe or work through:A simplex is the geometrical figure consisting, in N dimensions, of N + 1points (or vertices) and all their interconnecting line segments, polygonal faces, etc.In two dimensions, a simplex is a triangle. In three dimensions it is a tetrahedron,not necessarily the regular tetrahedron.

Характеристики

Тип файла
PDF-файл
Размер
75,31 Kb
Материал
Тип материала
Высшее учебное заведение

Тип файла PDF

PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов книги

Свежие статьи
Популярно сейчас
Как Вы думаете, сколько людей до Вас делали точно такое же задание? 99% студентов выполняют точно такие же задания, как и их предшественники год назад. Найдите нужный учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
6476
Авторов
на СтудИзбе
304
Средний доход
с одного платного файла
Обучение Подробнее