Prentice-Hall Series in Computational Mathematics Numerical Methods for Unconstrained Optimization and Nonlinear Equations J. E. Dennis, Jr. Rice University R. B. Schnabel University of Colorado at Boulder Prentice-.Sail, Inc., Englewood Cliffs, New Jersey 07632 Дж. Дэннис, мл.» Р. Шнабель Численные методы безусловной оптимизации и решения нелинейных уравнений Перевод с английского О. П. Бурдакова под редакцией Ю. Г. Евтушенко Москва «Мир» 1988 ББК 22.193 Д 94 УД К 519.61 Дэннис Дж., мл., Шнабель Р. Д94 Численные методы безусловной оптимизации и решения нелинейных уравнений: Пер. с англ.—М.: Мир, 1988.— 440 с., ил. ISBN 5-03-001102-1 Монография известных американских специалистов, посвященная как теории численных методов оптимизации, так и вопросам реализации этих методов на ЭВМ. Особое внимание уделено наиболее эффективным методам ньютоновского типа. Приведены пакеты программ решения прикладных задач оптимизации. Для математиков-вычислителей, инженеров-исследователей, аспирантов и студентов вузов. Д 1702070000—187 041(01)—88 34—88, ч. 1 ББК 22.193 Редакция литературы по математическим наукам ISBN 5-03-001102-1 (русск.) ISBN 0-13-627216-9 (англ.) 1983 by Prentice-Hall, Inc. перевод на русский язык, с автор- скими исправлениями, «Мир», 1988 Предисловие редактора перевода и переводчика Вниманию читателя предлагается книга американских специа- листов в области численного анализа Джона Дэнниса, мл., и Роберта Шнабеля. Она посвящена двум важным и тесно меж- ду собой связанным разделам: безусловной минимизации и решению нелинейных уравнений. Наряду с серьезным теоре- тическим материалом, отражающим современное состояние исследований в рассматриваемой области, в книге большое внимание уделяется вопросам программной реализации чис- ленных методов и их преподавания в высшей школе. Авторы сознательно ограничились рассмотрением числен- ных методов ньютоновского (квазиньютоновского) типа. Класс этих методов отличает концептуальное единство и до- статочная широта охвата, причем на практике такие мето- ды—одни из наиболее эффективных. Общая идея методов такова: на каждой итерации сначала строится модельная ап- проксимация исходной задачи (линейная в случае нелинейных уравнений и квадратичная для безусловной минимизации), а затем на основе ее решения находится новое приближение. По такой же схеме проводится исследование сходимости. Впервые столь подробно в литературе на русском языке изла- гаются метод доверительной области, квазнньютоновские ме- тоды типа секущих и др. Методы, не вошедшие в указанный класс, в достаточной мере представлены ссылками на литера- туру. В связи с тем что в оригинале имеется только одна ссыл- ка на работу советских авторов, мы решили указать несколько отечественных монографий, содержащих обширные списки ли- тературы. Полагаем, что книга вполне пригодна для форми- рования у читателя целостного представления о современном состоянии численных методов минимизации и решения нели- нейных уравнений. Более четверти книги занимают два приложения, написан- ные Робертом Шнабелем. В отличие от несколько схематич- ного описания алгоритмов в основной части книги, вполне до- 6 Предисловие редактора перевода и переводчика статочного для их теоретического рассмотрения, здесь алго- ритмы представлены уже с той степенью детализации, кото- рая требуется для их непосредственной программной реализа- ции. Они составляют в приложении А целостную систему ал- горитмов безусловной минимизации и решения нелинейных уравнений. Эта система основана на модульном принципе, ориентирована на учет особенностей машинной реализации и хорошо документирована. При ее написании использован условный алгоритмический язык, который вполне естественно реализуется на Фортране, Алголе, Паскале, Си и других язы- ках программирования. Кстати, некоторые конструкции этого псевдоязыка, описанного в разд. 1.3 приложения А, иногда используются и в основной части книги. Приложение В со- ставляют тестовые задачи безусловной минимизации и реше- ния нелинейных уравнений. Как отмечали сами авторы, лю- бая большая система алгоритмов неизбежно содержит опе- чатки и некоторые неточности. В этом авторы оказались, к со- жалению, правы. Вероятно, и мы окажемся" правы, если по- вторим это утверждение. Несколько глав вводного характера делают книгу доступ- ной для тех, кто знаком лишь с основами математического анализа и линейной алгебры. Изложение методически проду- мано и сопровождается упражнениями. Имеются подробные рекомендации по использованию книги в качестве учебного пособия. При этом следует учитывать, что в США учебный семестр длится 12—15 недель, а в неделю проводится 3 лек- ции,- каждая около одного часа. Основная часть книги может быть использована для .чтения лекций студентам и аспиран- там, а упражнения—для проведения семинаров. Приложения могут. составить основу учебных проектов. Однако возможно- сти содержащейся в приложении А модульной системы алго- ритмов гораздо шире и позволяют создавать также пакеты прикладных программ для решения практических задач. . В. процессе работы над переводом возникали всевозмож- ные вопросы, породившие довольно интенсивную переписку с авторами. Все исправления в книге сделаны либо с ведома авторов, либо по их собственной инициативе. Мы выражаем Дж,- Дэннису и Р. Шнабелю глубокую признательность за вни- мание к нашему .труду. Русскому изданию авторы предпослали посвящение «Ти world peace», что можно перевести как «Делу мира во всем мире». Они предложили подписаться под ним и нам, также ра- ботавшим над книгой. Мы с радостью подписываем это посвя- щение, отражающее искреннее стремление наших народов к миру, ^. •:' - Ю. Г. Евтушенко •'- ^-'. '•..: \.::.:.^ .^1 , - О. П. Бурдаков Делу мира во всем мире Дж. Дэннис, мл., Р. Шнабель, О. Бурдаков, Ю. Евтушенко Предисловие к русскому изданию С большим удовольствием мы приветствуем издание этой книги на русском языке. При ее написании мы стремились к тому, чтобы она была полезной для студентов, научных ра- ботников, а также для практиков, инженеров и всех тех, кто использует методы оптимизации. На наш взгляд английский вариант книги соответствует этим целям, и мы надеемся, что русское издание окажется столь же полезным. Хотя прошло уже четыре года со времени выхода в свет первого издания на английском языке, книга на наш взгляд практически не устарела. Основной материал книги по безус- ловной минимизации и решению нелинейных уравнений, как мы считали, стабилизировался в своем развитии в период ее написания, и время, по-видимому, доказало правильность этой оценки. Хотя исследования в этой области продолжались, мы считаем, что за прошедшее время не произошло каких-либо существенных изменений. Вероятно, наиболее важное продви- жение, о котором нам известно, заключалось в разработке усложненных вариантов алгоритмов и программного обеспече- ния для решения задачи «модель—доверительная область» в случае, когда матрица Гессе не является знакоопределенной (см., например, работы More, Sorensen [SIAM Journal on Scientific and Statistical Computing 4, 1983J, Gay [SIAM Journal on Scientific and Statistical Computing 2, 1981]), и кроме того в широком развитии теории исследования таких методов (см. также Shultz, Schnabel, Byrd [SIAM Journal on Numerical Analysis 22, 1985]). Это привело к появлению алго- ритмов, которые обладают более сильными свойствами гло- бальной сходимости по сравнению с приведенными в разд. 6.3.1, и в которых удается избежать априорного возмущения незна- коопределенных матриц Гессе в целях получения положитель- но определенных матриц, как это делается в разд. 5.6. Еще одним интересным достижением являются анализ и вычисли- тельный эксперимент, проведенные в недавних работах Powell 8 Предисловие к русскому изданию [Mathematical Programming 34, 1986] и Byrd, Noceclal, Yuan [SIAM Journal on Numerical Analysis, 1987], которые дают бо- лее удачное объяснение превосходству положительно опреде- ленной формулы секущих (BFGS) над обратной положительно определенной формулой секущих (DFP) при решении задач безусловной оптимизации. Были достигнуты успехи также и в некоторых непосредственно примыкающих областях, включая глобальную оптимизацию, методы решения задач большой размерности со специальной структурой и методы для решения задач безусловной оптимизации и систем нелинейных уравне- ний на параллельных ЭВМ. Приведенное в приложении программное обеспечение полу- чило широкое распространение и было включено в другие па- кеты программ, книги и библиотеки математического программ- ного обеспечения. Мы по-прежнему предоставляем это программ- ное обеспечение в распоряжение научных работников для использования в исследовательских целях. Нам хочется выразить особую благодарность О. Бурда кову за превосходно выполненную работу по переводу. Стремясь как можно точнее перевести книгу, он изучил ее столь тщательно, что выявил большое количество опечаток и неточностей. Мы признательны ему за этот вклад в укрепление международных научных связей. Док. Дэннис, мл. Р. Шнабель Май 1987 Предисловие Книга представляет собой подробное введение в численное ре- шение задач безусловной оптимизации и систем нелинейных уравнений, не требующее от читателя глубоких знаний мате- матических и вычислительных дисциплин. Работа над книгой была начата в 1977 г., поскольку мы считали, что к этому вре- мени алгоритмы и теория решения таких задач малой и сред- ней размерности достигли зрелого состояния и что был бы полезен подробный справочный материал. Книгу можно ис- пользовать при подготовке курса лекций для аспирантов или студентов-старшекурсников, а также ее можно рекомендовать для самостоятельного изучения научным работникам, инжене- рам и всем, кому рассматриваемые задачи интересны с прак- тической точки зрения. Минимальная подготовка, необходимая для чтения книги,— это знание основ математического анализа и линейной алгебры. Читатель, должно быть, в той или иной мере знаком с мате- матическим анализом многих переменных, тем не менее в гл. 4 приводится подробный обзор всей необходимой информации. Несомненную пользу мог бы принести курс вычислитель- ной линейной алгебры или элементов численных методов; часть этого материала кратко представлена в разд. 1.3 и гл. 3. Все рассматриваемые здесь алгоритмы основываются на идее метода Ньютона. Они часто называются методами ньюто- новского типа, однако мы предпочитаем термин квазиньюто- новские методы. К сожалению, этот термин используется спе- циалистами лишь для подкласса методов, представленного гл. 8 и 9. Поскольку этот подкласс состоит из естественных обобщений метода секущих на многомерный случай, мы пред- почитаем называть их методами секущих. Конкретные вари- анты методов секущих обычно носят имена своих создателей, поэтому в тексте неизбежно встречаются соответствующие не всегда понятные аббревиатуры. Вместе с тем мы пытались 4 0 Предисловие предложить для них содержательные названия, отвечающие их месту в общей схеме изложения. Ядро книги составляет материал по численным методам ре- шения многомерных задач безусловной оптимизации и нели- нейных уравнений. Он представлен гл. 5—9. Глава 1 — ввод- ная, она принесет больше пользы студентам, специализирую- щимся в чистой математике и информатике, чем читателям, имеющим некоторый опыт в научных приложениях. Глава 2, которая посвящена одномерному варианту рассматриваемых задач, является иллюстрацией нашего подхода и одновременно его обоснованием. Глава 3 может быть пропущена читателями, уже изучавшими вычислительную линейную алгебру, а гл. 4 — теми, кто обладает основательными познаниями в математиче- ском анализе многих переменных. Глава 10 дает довольно пол- ное изложение алгоритмов решения нелинейной задачи о наи- меньших квадратах, которая относится к важному-классу за- дач безусловной оптимизации и из-за ее специфики решается специальными методами. В ней существенно используется ма- териал предыдущих глав. В гл. 11 указываются некоторые перспективные направления исследований; здесь отдельные разделы сложнее, чем предыдущий материал. Мы использовали эту книгу в учебных курсах для старше- курсников и аспирантов. Для первых из них .гл. 1—9 образуют фундаментальный курс, а для последних может быть исполь- зована вся книга целиком. При этом если гл. 1, 3 и 4 оставить для самостоятельного чтения, то курс займет около половины семестра. Оставшуюся часть семестра легко заполнить указан- ными главами пли другим материалом, не вошедшим в книгу. Наибольшую важность среди опущенного нами материала представляют методы, не связанные с методом Ньютона для решения задач безусловной минимизации и нелинейных урав- нений. Большинство из них важны только в частных случаях. Симплексный алгоритм Нелдера—Мида') [см., например, Ав- риель (1976)], эффективный для задач с менее чем пятью пе- •ременными, может быть изложен за час. Методы сопряженных направлений [см., например, Гилл, Мюррей п Райт (1981)] относятся собственно к курсу вычислительной линейной алгеб- ры, но благодаря малому объему требуемой памяти ЭВМ они оказываются полезными и для задач оптимизации с очень .большим числом переменных. Их можно вкратце изложить за два часа, полное же изложение заняло бы две недели. Наиболее трудным для нас было решение опустить методы Брауна—Брента. Их идея изящна и они поразительно эффек- тивны при хороших начальных приближениях для решения си- '> Он также известен под-названием «алгоритм (демпфируемого) много. гранппка». — П рил. перев. Предисловие 11 етем уравнений, часть из которых линейны. Этим методам в наиболее распространенной форме нельзя отдать безусловное предпочтение в задачах общего вида. Они вряд ли где-либо освещались так же широко, как симплексный алгоритм и ал- горитм сопряженных градиентов. Отсутствие этих методов можно восполнить одной или двумя лекциями (опуская дока- зательства) (см., например, Дэннис (1977)]. Наконец, среди методов, имеющих важное значение, не нашли отражения ме- тоды типа продолжения или гомотопии, работы по которым возобновились с новой силой в 70-х гг. Эти изящные идеи мо- гут пригодиться как крайнее средство в исключительно труд- ных задачах, хотя в целом они все же не конкурентоспособны. На изложение превосходного обзора Алговера и Джорджа (1980) потребуется по крайней мере две недели. Книга снабжена большим количеством упражнений, многие из которых содержат дальнейшее развитие идей, лишь слегка затронутых в тексте. Большое приложение, написанное Р. Шна- белем, имеет целью обеспечить как основами для учебных проектов, так и важным справочным материалом для тех чи- тателей, кто хочет вникнуть в детали алгоритмов и, возможно, разработать свои собственные версии. Рекомендуем читателю на раннем этапе чтения ознакомиться с предисловием к при- ложению. Некоторые вопросы терминологии и обозначения вызвали особенные трудности. Ранее уже упоминалось о смешении по- нятий «квазиныотоновские методы» и «методы секущих». Кро- ме того, в заглавии книги мы использовали термин «безуслов- ная оптимизация», а в тексте—«безусловная минимизация», поскольку в действительности рассматривается только мини- мизация, а задача максимизации очевидным образом сводится к минимизации. Важный термин «глобальный» часто интер- претируется по-разному, поэтому в разд. 1.1 пояснено, как именно он понимается в книге. Наконец, основная проблема в обозначениях состояла в том, чтобы различать между собой г-ю компоненту /г-мерного вектора (скаляр, обычно обозначае- мый как Xi) и t-ю итерацию в последовательности таких век- торов х (вектор, также обычно обозначаемый как д-;). После нескольких неудачных попыток было решено допустить эту не- однозначность в обозначениях, поскольку подразумеваемый смысл всегда понятен из контекста. В действительности это обозначение редко используется в обоих смыслах в одном и том же разделе. Нам хотелось без ущерба для изложения сделать книгу на- столько краткой и недорогой, насколько это возможно. Исходя из этого, безжалостно редактировались некоторые доказатель- ства и целые темы. Мы старались использовать обозначения, отвечающие тонкому вкусу и одновременно лучшему понима- 12 Предисловие нию, и включать доказательства, способствующие хорошему усвоению предмета, опуская те, которые всего лишь устанав- ливают справедливость утверждений. Мы ожидаем больше критики в отношении того, что было опущено, нежели в отно- шении того, что включено. Однако, как известно каждому пре- подавателю, наиболее трудной и важной частью составления учебного курса является решение о том, что следует опустить. Мы искренне благодарим Идалию Келлар, Арлин Хантер и Долорес Пендел за перепечатку многочисленных вариантов рукописи, а также студентов за их поразительную способность отыскивать неясные места. Дэвид Гэй, Вирджиния Клема, Хо- мер Уолкер, Пит Стюарт и Лэйн Уотсон использовали черно- вой вариант книги в курсах лекций в Массачусетском техноло- гическом институте, Лоренцевской лаборатории Ливермора, Университете Хьюстона, Университете Нью-Мексико, Универси- тете Мериленд и Вирджинском политехническом институте и внесли полезные предложения. Тронд Стейхауг и Майк Тодд высказали ряд удачных замечаний по некоторым разделам. Дж. Дэннис, мл. Райсовский университет Р. Шнабель Университет Колорадо в Боулдере Прежде всего одно программное замечание В первых четырех главах книги содержатся вводные сведения и излагаются побудительные мотивы к исследованию многомерных нелинейных задач. В гл. 1 вводятся задачи, которые будут обсуждаться в дальнейшем. Затем в гл. 2 приводятся некоторые алгоритмы решения нелинейных задач только одной переменной. Излагая эти алгоритмы так, чтобы отразить основные идеи всех рассматриваемых далее в книге нелинейных алгоритмов, мы на- деемся тем самым обеспечить читателя доступным и прочным фундаментом для исследования многомерных нелинейных задач. В гл. 3 и 4 содержится материал по основам вычислительной линейной алгебры и многомерного ана- лиза, необходимый для перехода к задачам более чем одной переменной. ЛИТЕРАТУРА Асен (Aasen J. О.) (1971) On the reduction of symmetric matrix to tridiagonal form, BIT 11, 233—242. Авриель (Avriel M.) (1976) Nonlinear Programming: Analysis and Methods, Prentice-Hall, Englewood Cliffs, N. J. Алговер, Джордж (Allgower E., Georg K.) (1980) Simplicial and continuation methods for approximating fixed points and solutions to systems of equations, SIAM Review 22, 28—85. Армийо (Armijo L.) (1966) Minimization of functions having Lipschitz-continuous first partial derivatives, Pacific J. Math. 16, 1—3. Ахо, Хопкрофт, Ульман (Aho A. U., Hopcroft J. E., Ullman J. D.) (1974) The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading, Mass. [Имеется перевод: Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. — M.: Мир, 1979.] Бакли (Buckley A. G.) (1978) A combined conjugate gradient quasi-Newton minimization algo- rithm, Math. Prog. 15, 200—210. Банч, Парлетт (Bunch J. R., Parlett B. N.) (1971) Direct methods for solving symmetric indefinite systems of linear equations, SIAM J. Numer. Anal. 8, 639—655. Бард (Bard Y.) (1970) Nonlinear Parameter Estimation, Academic Press, New York. Барнес (Barnes J.) (1965) An algorithm for solving nonlinear equations based on the secant method, Comput. J. 8, 66—72. Бартелс, Конн (Bartels R., Conn A.) (1982) An approach to nonlinear /i data fitting, in Numerical Analysis, Cocoyoc 1981, ed. by Hennart J. P., Springer-Verlag, Lecture Notes in Math. 909, 48—58. Бейтс, Уоттс (Bates D. M., Watts D. G.) (1980) Relative curvature measures of nonlinearity, J. Roy. Statist. Soc. Ser. В 42, 1—25, 235. Бил (Beale E. M. L.) (1977) Integer programming, in The State of the Art in Numerical Ana- lysis, ed. by Jacobs D., Academic Press, London, 409—448. Битон, Тьюки (Beaton A. E., Tukey J. W.) (1974) The fitting of power series, meaning polynomials, illustrated on hand-spectroscopic data, Technometrics 16, 147—192. Боггс, Дэннис (Boggs P. Т., Dennis J. E., Jr.) (1976) A stability analysis for perturbed nonlinear iterative methods, Math. Сотр. 30, 1—17. Брайян (Вгуап С. А.) (1968) Approximate solutions to nonlinear integral equations, SIAM J. Numer. Anal, 5, 151—155. Брент (Brent R. P.) (1973) Algorithms for Minimization without Derivatives, Prentice-Hall, Englewood Cliffs, N. J. Бродли (Brodlie K. W.) (1977) Unconstrained minimization, in The State of the Art in Numerical Analysis, ed. by Jacobs D., Academic Press, London, 229—268. 426 Литература Бройден (Broyden С. G.) (1965) A class of methods for solving nonlinear simultaneous equations Math. Сотр. 19, 577—593. (1969) A new double-rank minimization algorithm, AMS Notices 16, 670. (1970) The convergence of a class of double-rank minimization algorithms Parts I and II, J. I. M. A. 6, 76—90, 222—236. (1971) The convergence of algorithm for solving sparse nonlinear sys terns, Math. Сотр. 25, 285—294. Бройден, Дэннис, Морэ (Broyden С. G., Dennis J. Е., Jr., More J. J.) (1973) On the local and superlinear convergence of quasi-Newton methods J. I. M. A. 12, 223—246. Вандерграфт (Vandergraft J. S.) (1978) Introduction to Numerical Computations, Academic Press, New York. Вольф (Wolfe P.) (1969) Convergence conditions for ascent methods, SIAM Review 11, 226— 235. (1971) Convergence conditions for ascent methods. II: Some corrections, SIAM Review 13, 185—188. Гандер (Gander W.) (1978) On the linear least squares problem with a quadratic constraint, Stanford Univ. Computer Science Tech. Rept. STAN-CS-78-697, Stanford Calif. (1981) Least squares with a quadratic constraint, Numer. Math. 36, 291— 307. [Это сокращенная версия работы Гандер (1978).] Гарфинкель, Немхаусер (Garfinkel R. S., Nemhauser G. L.) (1972) Integer Programming, John Wiley & Sons, New York. Гилл, Голуб, Мюррей, Сондерс (Gill Р. Е., Golub G. Н., Murray W., Saun- ders M. A.) (1974) Methods for modifying matrix factorizations, Math. Сотр. 28, 505—535. Гилл, Мюррей (Gill Р. Е., Murray W.) (1972) Quasi-Newton methods for unconstrained optimization, J. I. M. A. 9, 91—108. Гилл, Мюррей, Райт (Gill Р. Е., Murray W., Wright M. H.) (1981) Practical Optimization. Academic Press, London. [Имеется перевод: Гилл Ф., Мюррей У., Райт M. Практическая оптимизация. — M.: Мир, 1985.] Голдстейн (Goldstein А. А.) (1967) Constructive Real Analysis, Harper & Row, New York. Голдфарб (Goldfarb D.) (1970) A family of variable metric methods derived by variational means Math. Сотр. 24, 23—26. (1976) Factorized variable metric methods for unconstrained optimization Math. Сотр. 30, 796—811. ' , Голдфельд, Куанд, Троттер (Goldfeldt S. M., Quandt R. Е., Trotter H. F.) (1966) Maximization by quadratic hill-climbing, Econometrica 34, 541—551. Голуб, Ван Лоан (Golub G. H., Van Loan С.) (1983) Matrix Computations, the Johns Hopkins University Press. Голуб, Перейра (Golub G. H., Pereyra V.) (1973) The differentiation of pseudo-inverse and non-linear least squares problems whose variables separate, SIAM J. Numer. Anal. 10, 413—432. Гриванк (Griewank А. О.) (1982) A short proof of the Dennis-Schnabel theorem. B. I. T. 22, 252—256. Гриванк, Тоинт (Griewank А. О., Toint Ph. L.) (1982а) Partitioned variable metric updates for large sparse optimization problems, Numer. Math. 39, 119—137. Литература 427 (1982b) Local convergence analysis for partitioned quasi-Newton updates in the Broyden class, Numer. Math. 39, 429—448. (1982с) On the unconstrained optimization of partially separable functions, in Nonlinear Optimization, ed. by Powell M. J. D. Academic Press, London. Гринстадт (Greenstadt J. L.) (1970) Variations on variable-metric methods, Math. Сотр. 24, 1—22. Гэй (Gay D. M.) (1979) Some convergence properties ol' Broyden's method, SIAM J. Numer. Anal., 16, 623—630. (1981) Computing optimal locally constrained steps, SIAM J. Sci. Stat. Сотр. 2, 186—197. Гэй, Шнабель (Gay D. M., Schnabel R. B.) (1978) Solving systems of nonlinear equations by Broyden's method with projected updates, in Nonlinear Programming 3, ed. by Mangasarian 0., Meyer R., Robinson S., Academic Press, New York, 254—281. Дальквист, Бьёрк, Андерсон (Dahlquist G., Bjorck A., Anderson N.) (1974) Numerical Methods, Prentice-Hall, Englewood Cliffs, N. J. Дембо, Айзенштат, Штанхауг (Dembo R. S., Eisenstat S. C., Steihaug T.) (1982) Inexact Newton methods, SIAM J. Numer. Anal. 19, 400—408. Джонсон, Остриа (Johnson G. W., Austria N. H.) (1983) A quasi-Newton method employing direct secant updates of matrix factorizations, SIAM J. Numer. Anal. 20, 315—325. Диксон (Dixon L. С. W.) (1972a) Quasi-Newton family generate identical points, Parts I and II, Math. Prog. 2, 383—387, 2nd Math. Prog. 3, 345—358. (1972b) The choice of step length, a crucial factor in the performance of variable metric algorithms, in Numerical Methods for Non-linear Optimi- zation, ed. by Lootsma F., Academic Press, New York, 149—170. Диксон, Cere (Dixon L. C. W., Szego G. P.) (1975, 1978) Towards Global Optimization, Vols. 1, 2, North-Holland, Amsterdam. Донгарра, Банч, Моулер, Стюарт (Dongarra J. J., Bunch J. R., Moler С. В., Stewart G. W.) (1979) LINPACK Users Guide, SIAM Publications, Philadelphia. Дэвидон (Davidon W. C.) (1959) Variable metric methods for minimization, Argonne National Labs Report ANL-5990. (1975) Optimally conditioned optimization algorithms without line sear- ches, Math. Prog. 9, 1—30. Дэннис (Dennis J. E., Jr.) (1971) Toward a unified convergence theory for Newton-like methods, in Nonlinear Functional Analysis and Applications, ed. by Rail L. В., Aca- demic Press, New York, 425—472. (1977) Nonlinear least squares and equations, in The State of the Art in Numerical Analysis, ed. by Jacobs D., Academic Press, London, 269—312. (1978) A brief introduction to quasi-Newton methods, in Numerical Ana- lysis, ed. by Golub G. H., Oliger J., AMS, Providence, R. I., 19—52. Дэннис, Гэй, Уэлш (Dennis J. E., Jr., Gay D. M., Welsch R. E.) (198 la) An adaptive nonlinear least-squares algorithm, TOMS 7, 348—368. (1981b) Algorithm 573 NL2SOL—An adaptive nonlinear least-squares al- gorithm [E4], TOMS 7, 369—383. Дэннис, Марвил (Dennis J. E., Jr., Marwil E. S.) (1982) Direct secant updates of matrix factorizations. Math. Сотр. 38, 459—474. Дэинис, Мей (Dennis J. E., Jr., Mei H. H. W.) (1979) Two new unconstrained optimization algorithms which use function and gradient values, J. Optim. Theory Appl. 28- 453—482. 428 Литература Дэниис, Мора (Dennis J. E., Jr., More J. J.) (1974) A characterization of superlinear convergence and its application to quasi-Newton methods. Math. Сотр. 28, 549—560. (1977) Quasi-Newton methods, motivation and theory, SIAM Review 19, 46—89. Дэинис, Тапиа (Dennis J. E., Jr., Tapia R. A.) (1976) Supplementary terminology for nonlinear iterative methods, SIGNUM Newsletter 11:4, 4—6. Дэннис, Уолкер (Dennis J. E., Jr., Walker H. F.) (1981) Convergence theorems for least-change secant update methods, SIAM J. Numer, Anal. 18, 949—987, 19, 443. (1983) Sparse secant update methods for problems with almost sparse Ja- cobians, in preparation. Дэннис, Шнабель (Dennis J. E., Jr., Schnabel R. B.) (1979) Least change secant updates for quasi-Newton methods, SIAM Review 21, 443—459. Зирилли (Zirilli F.) (1982) The solution of nonlinear systems of equations by second order systems of o. d. e. and linearly implicit A-stable techniques, SIAM J. Numer. Anal. 19, 800—815. Канторович Л. В. (1948) Функциональный анализ и прикладная математика. УМН 3, No. 6, 89—185. Кауфман (Kaufman L. С.) (1975) A variable projection method for solving separable nonlinear least squares problems, BIT 15, 49—57. Клайн, Моулер, Стюарт, Уилкинсон (Cline А. К., Moler С. В., Stewart G. W., Wilkinson J. H.) (1979) An estimate for the condition number of a matrix, SIAM. J. Numer. Anal. 16, 368—375. Копт, де Бур (Conte S. D., de Boor С.) (1980) Elementary Numerical Analysis: An Algorithmic Approach, 3d ed., McGraw-Hill, New York. Коулман, Морэ (Coleman Т. F., More J. J.) (1982) Estimation of sparse Hessian matrices and graph coloring problems, Argonne National Labs, Math.-C. S. Div. TM-4. (1983) Estimation of sparse Jacobian matrices and graph coloring prob- lems, SIAM J. Numer. Anal. 20, 187—209. Куртис, Пауэлл, Райд (Curtis A., Powell M. J. D., Reid J. К.) (1974) On the estimation of sparse Jacobian matrices, J. I. M. A. 13, 117—120. Левенберг (Levenberg К.) (1944) A method for solution of certain problems in least squares, Quart. Appl. Math. 2, 164—168. Лоусон, Хенсон, Кинкейд, Крог (Lawsou С. L., Hanson R. J., Kincaid D. R., Krogh F. Т.) (1979) Basic linear algebra subprograms for Fortran usage, ACM TOMS 5, 308—323. , Марвил (Marwil E. S.) (1978) Exploiting sparsity in Newton-type methods, Cornell Applied Math. Ph. D. Thesis. (1979) Convergence results for Schubert's method for solving sparse non- linear equations, SIAM J. Numer. Anal. 16, 588—604. Маркварт (Marquardt D.) (1963) An algorithm for least-squares estimation of nonlinear parameters SIAM J. Appl. Math. 11, 431—441. Морэ (More J. J.) (1977) The Levenberg—Marquardt algorithm: implementation and theory, in Numerical Analysis, ed. by Watson G. A., Lecture Notes in Math. 630' Springer-Verlag, Berlin, 105—116. Литература 429 Морэ, Гарбов, Хиллстром (More J. J., Garbow В. S., Hillstrom К. E.) (1980) User guide for MINPACK-1, Argonne National Labs Report ANL-80-74. (1981a) Testing unconstrained optimization software, TOMS 7, 17—41. (1981b) Fortran subroutines for testing unconstrained optimization soft- ware, TOMS 7 136—140. Морэ, Сорснсен (More J. J., Sorensen D. C.) (1979) On the use of directions of negative curvature in a modified Newton method, Math. Prog. 16, 1—20. Мюррей (Murray W.) (1972) Numerical Methods for Unconstrained Optimization. Academic Press, London. Мюррей, Овертон (Murray W., Overton M. L.) (1980) A projected Ligrangian algorithm for nonlinear minimax optimi- zation, SIAM J. Sci. Statist. Comput. 1, 345—370. (1981) A projected Lagrangian algorithm for nonlinear li optimization, SIAM J. Sci. Statist. Comput. 2. 207—224. Нелдер, Мид (Nelder J. A., Mead R.) (1965) A simplex method for function minimization, Comput. J. 7, 308— 01 Q Орен (Oren S. S.) (1974) On the selection of the parameters in self-scaling variable metric algorithms, Math. Prog. 7, 351—367. Ортега, Рейнболдт (Ortega J. M., Rheinboldt W. C.) (1970) Iterative Solution of Nonlinear Equations in Several Variables. Academic Press, New York. [Имеется перевод: Ортега Дж., Рейнболдт В. Итерационные методы решения нелинейных систем уравнений со мно- гими неизвестными.—M.: Мир, 1975.] Осборн (Osborne M. R.) (1976) Nonlinear least squares—the Levenberg algorithm revisited, J. Austral. Math. Soc. 19 (Series B), 343—357. Пауэлл (Powell M. J. D.) (1970a) A hybrid method for nonlinear equations, in Numerical Methods for Nonlinear Algebraic Equations, ed. by Rabinowitz P., Gordon and Breach, London, 87—114. (1970b) A new algorithm for unconstrained optimization, in Nonlinear Programming, ed. by Rosen J. В., Mangasarian 0. L. and Ritter K., Aca- demic Press, New York, 31—65. (1975) Convergence properties of a class of minimization algorithms, in Nonlinear Programming 2, ed by Mangasarian 0. L., Meyer R. and Robinson S., Academic Press, New York, 1—27. (1976) Some global convergence properties of variable metric algo- rithm without exact line searches, in Nonlinear Programming, ed. by Cottle R. and Lemke C., AMS, Providence, R. I;, 53—72. (1981) A note on quasi-Newton formulae for sparse second derivative matrices, Math. Prog. 20, 144—151. Пауэлл, Тоинт (Powell M. J. D., Toint Ph. L.) (1979) On the estimation of sparse Hessian matrices, SIAM J. Numer. Anal. 16, 1060—1074. Пратт (Pratt J. W.) (1977) When to stop a quasi-Newton search for a maximum likelihood estimate, Harvard School of Business WP 77—16. Райд (Reid J. K.) (1973) Least squares solution of sparse systems of non-linear equations by a modified Marquardt algorithm, in Proc. NATO Conf. at Cam- bridge, July 1972, North-Holland, Amsterdam, 437—445. Райнш (Reinsch C.) (1971) Smoothing by spline functions, II, Numer. Math. 16, 451—454. 430 Литература Соренсен (Sorensen D. С.) (1977) Updating the symmetric indefinite factorization with applications in a modified Newton's method, PH. D. Thesis, U. C. San Diego, Argonne National Labs Report ANL-77-49. (1982) Newton's method with a model trust region modification, SIAM J. Numer; Anal. 19, 409—426. Стренг (Strang G.) (1976) Linear Algebra and Its Applications, Academic Press, New York. [Имеется перевод: Стренг Г. Линейная алгебра и ее приложения. — М.: Мир, 1980.] Стюарт (Stewart G. W., Ill) (1967) A modification of Davidon's method to accept difference ap- proximations of derivatives, J. ACM 14, 72—83. (1973) Introduction to Matrix Computations, Academic Press, New York. Тоиит (Toint Ph. L.) (1977) On sparse and symmetric matrix updating subject to a linear equation, Math. Сотр. 31, 954—961. (1978) Some numerical results using a sparse matrix updating formula in unconstrained optimization, Math. Сотр. 32, 839—851. (1981) A sparse quasi-Newton update derived variationally with a non- diagonally weighted Frobenius norm, Math. Сотр. 37, 425—434. Уилкинсон (Wilkinson J. H.) (1963) Rounding Errors in Algebraic Processes, Prentice-Hall, Engle- wood Cliffs, N. J. (1965) The Algebraic Eigenvalue Problem, Oxford University Press London. [Имеется перевод: Уилкинсон Дж. Алгебраическая проблема собственных значении.—М.: Наука, 1970.] Флетчер (Fletcher R.) (1970) A new approach to variable metric algorithms, Comput. J. 13, 317—322. (1980) Practical Methods of Optimization, Vol. 1, Unconstrained Opti- mization, John Wiley & Sons, New York. Флетчер, Пауэлл (Fletcher R., Powell M. J. D.) (1963) A rapidly convergent descent method for minimization, Comput. J. 6, 163—168. Форд (Ford В.) (1978) Parameters for the environment for transportable numerical software, TOMS 4, 100—103. Фосдик (Fosdick L. ed.) (1979) Performance Evaluation of Numerical Software, North-Holland, Amsterdam. Франк, Шнабель (Frank P., Schnabel 1?. В.) (1982) Calculation of the initial Hessian approximation in secant al- gorithms, in preparation. Хайберт (Hiebert K. L.) (1982) An evaluation of mathematical software that solves systems of nonlinear equations, TOMS 8, 5—20, Хебден (Hebden M. D.) (1973) An algorithm for minimization using exact second derivatives, Rept. TP515, A.E.R.E., Harwell, England. Хемминг (Hamming R. W.) (1973) Numerical Methods for Scientists and Engineers, 2 ed., McGraw- Hill, New York. [Имеется перевод первого издания: Хемминг Р. В. Численные методы для научных работников и инженеров. — М.: Нау- ка, 1979.] Хестенс (Hestenes M. R.) (1980) Conjugate-direction Methods in Optimization, Springer Verlag, New York. Литература 431 Хьюбер (Huber P. J.) (1973) Robust regression: asvmptotics, conjectures, and Monte Carlo, Anals of Statistics 1, 799—821. ' (1981) Robust Statistics, John Wiley & Sons, New York. [Имеется перевод: Хьюбер Дж. П. Робастность в статистике.—М.: Мир, 1984.] Шанно (Schanno D. F.) (1970) Conditioning of quasi-Newton methods for function minimization, Math. Сотр. 24, 647—657. (1978) Conjugate-gradient methods with inexact searches, Math. of Oper. Res. 3, 244—256. (1980) On the variable metric methods for sparse Hessians, Math. Сотр. 34, 499—514. Шанно, Фуа (Schanno D. F., Phua К. H.) (1978a) Matrix conditioning and nonlinear optimization, Math. Prog. 14, 145—160. (1978b) Numerical comparison of several variable metric algorithms, J. Optim. Theory Appl. 25, 507—518. Шнабель (Schnabel R. В.) (1977) Analysing and improving quasi-Newton methods for unconstrai- ned optimization, Ph. D. Thesis, Cornell Computer Science TR-77-320. (1982) Convergence of quasi-Newton updates to correct derivative values, in preparation; Шнабель, Вайс, Кунц (Schnabel R. В., Weiss В. E., Koontz J. E.) (1982) A modular system of algorithms for unconstrained minimization, Univ. Colorado Computer Science, TR CU-CS-240-82. Штайхауг (Steihaug T.) (1981) Quasi-Newton methods for large scale nonlinear problems, Ph. D. Thesis, Yale University. Шуберт (Schubert L. K.) (1970) Modification of a quasi-Newton method for nonlinear equations with a sparse Jacobian, Math. Сотр. 24, 27—30. Шульц, Шнабель, Бирд (Shultz G. A„ Schnabel R. В., Byrd R. H.) (1982) A family of trust region based algorithms for unconstrained minimization with strong global convergence properties, Univ. Colorado Computer Science TR CU-CS-216-82. Добавлено при переводе Бахвалов H. С., Жидков H. П., Кобельков Г. М. (1987) Численные методы: учебное пособие для вузов.—М.: Наука. Васильев Ф. П. (1980) Численные методы решения экстремальных задач.—М.: Наука. Евтушенко Ю. Г. (1982) Методы решения экстремальных задач и их применение в си- стемах оптимизации.—М.: Наука. Марчук Г. И., Лебедев В. И. (1971) Численные методы теории переноса нейтронов. — М.: Атомиздат. Михалевич В. С., Гупал А. М., Норкин В. И. (1987) Методы невыпуклой оптимизации.—М.: Наука. Поляк Б. Т. (1983) Введение в оптимизацию. — М.: Наука. Пшеничный Б. H., Данилин Ю. М. (1975) Численные методы в экстремальных задачах.—М.: Наука. Самарский А. А., Николаев E. С. (1978) Методы решения сеточных уравнений.—М.: Наука. Сухарев А. Г., Тимохов А. В., Федоров В. В. (1986) Курс методов оптимизации.—М.: Наука. ИМЕННОЙ УКАЗАТЕЛЬ Авриель (Avriel M.) 10, 29 Айзенштат (Eisenstat S. С.) 292 Алговер (Allgower E.) 11, 17, 186 Андерсон (Anderson N.) 29 Армийо (Armijo L.) 148 Асен (Aasen J. О.) 70 Axo (Aho A. U.) 26 Бакли (Buckley A. G.) 292 Банч (Bunch J. R.) 70, 71, 88 Бард (Bard Y.) 260, 279 Барнес (Barnes J.) 228 Бартелс (Bartels R.) 279 Бейтс (Bates D. M.) 279 Бил (Beale E. M. L.) 23 Бирд (Byrd R. H.) 7, 8, 189 Битон (Beaton A. E.) 280 Боггс (Boggs P. Т.) 134 Брайян (Bryan С. А.) 136 Брент (Brent R. P.) 29 Бродли (Brodlie К. W.) 242 Бройден (Broyden С. О.) 207, 211, 213, 235, 240, 246, 254, 255, 291 Бур, де (de Boor С.) 29 Бьёрк (Bjorck A.) 29 Вайс (Weiss В. E.) 198, 315, 317 Вандерграфт (Vandergraft J. S.) 316 Ван Лоан (Van Loan С.) 58, 71,292 Вольф (Wolfe P.) 149, 150 Гандер (Gander W.) 167 Гарбов (Garbow В. S.) 199, 422 Гарфинкель (Garfinkel R. S.) 23 Гнлл (Gill P. E.) 10, 79, 128, 226, 292, 334, 360, 362 Голдстейн (Goldstein A. A.) 148 Голдфарб (Goldfarb D.) 79, 240 Голдфельд (Goldfeldt S. M.) 165 Голуб (Golub G. H.) 58, 71, 79, 278, 282, 283, 292 Гриванк (Griewank A. 0.) 292, 306 Гринстадт (Greenstadt J. L.) 236 Гэй (Gay D. M.) 7, 164, 171, 223, 228, 231, 275, 278, 283, 307 Дальквист (Dahlquist G.) 29 Дембо (Dembo R. S.) 292 Джонсон (Johnson G. W.) 307 Джордж (Georg К.) 11, 17, 186 Диксон (Dixon L. С. W.) 17, 242 Донгарра (Dongarra J. J.) 71, 88 Дэвидон (Davidon W. С.) 242, 254 Дэннис (Dennis J. E., Jr.) 11, 118, 134, 152, 174. 203, 211, 213, 217, 234, 235, 246, 254, 255, 275, 278, 283, 293, 297, 299, 305, 306, 307 Зирилли (Zirilli F.) 186 Канторович Л. В. 116 Кауфман (Kaufman L. С.) 278 Кинкейд (Kinkeid D. R.) 324 Клайн (Cline А. К.) 75, 368, 369 Конн (Conn A.) 279 Конт (Conte S. D.) 29 Коулман (Coleman Т. F.) 287, 288 Крог (Krogh F. T.) 324 Куанд (Quandt R. E.) 165 Кунц (Koontz J. E.) 198, 315, 317 Куртис (Curtis A.) 285, 287 Левенберг (Levenberg К.) 165 Лоусон (Lawson С. L.) 324 Марвил (Marwil E. S.) 291 Маркварт (Marquardt D.) 165 Мей (Mei H. H. W.) 174 Морэ (More J. J.) 7, 127, 152, 167, 169, 199, 203, 211, 213, 217, 224, 234, 235, 246, 254, 255, 271, 283, 287, 288, 422 Моулер (Moler С. В.) 71, 75, 88, 36S, 369 434 Именной указатель Немхаусер (Nemhauser G. L.) 23 Носедал (Nocedal) 8 Овертон (Overton M. L.) 279 Орен (Oren S. S.) 250 Ортега (Ortega J. M.) 36, 92, 116 Осборн (Osborne M. R.) 271 Остриа (Austria N. H.) 307 Парлетт (Parlett B. N.) 70 Пауэлл (Powell M. J. D.) 7, 180, 242, 252, 271, 285, 287, 288, 305, 306 Перейра (Pereyra V.) 278, 282, 283 Пратт (Pratt J. W.) 278 Райд (Reid J. К.) 285, 287, 291 Раинш (Reinsch С.) 168 Райт (Wright M. H.) 10, 128, 292, 334, 360, 362 Рейнболдт (Rheinboldt W. С.) 36, 92 116 Cere (Szego G. P.) 17 Сондерс (Saunders M. A.) 79 Соренсен (Sorensen D. С.) 7, 127,171 Стренг (Strang G.) 58, 71 Стюарт (Stewart G. W., Ill) 58, 75, 88, 134, 283, 363, 364, 368, 369 Тапиа (Tapia R. A.) 203 Тоинт (Toint Ph. L.) 288, 291, 292, 305 Троттер (Trotter H. F.) 165 Тьюки (Tukey J. W.) 280 Уилкинсон (Wilkinson J. H.) 24, 58, 73, 75, 368, 369 Ульман (Ullman J. D.) 26 Уолкер (Walker H. F.) 211, 275, 299, 305, 306 Уотс (Watts D. G.) 279 Уэлш (Welsch R. E.) 275, 278, 283 307 Флетчер (Fletcher R.) 165, 203, 240 242, 253, 292 Форд (Ford В.) 28 Фосдик (Fosdick L., ed.) 200 Фуа (Phua К. Н.) 250, 254 Хайберт (Hiebert К. L.) 422 Хебден (Hebden M. D.) 167 Хемминг (Hamming R. W.) 334, 359, 362 Хенсон (Hanson R. J.) 324 Хестенс (Hestenes M. R.) 292 Хиллстром (Hillstrom К. Е.) 199 224 422 Хопкрофт (Hopcroft J. E.) 26 Хьюбер (Huber P. J.) 279, 280 Шанно (Schanno D. F.) 240 250, 254 291, 292 Шнабель (Schnabel R. В.) 7, 189 198, 228, 231, 235, 248, 254 293 297, 306, 315, 317 Штайхауг (Steihaug T.) 189, 292 Шуберт (Schubert L. К.) 291 Шульц (Shultz G. A.) 7, 189 Ян (Yuan) 8 ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ Алгоритм гибридный (hybrid algo- rithm) 42 • — Голуба — Перейры (Golub—Perey- ra) 282 Алгоритмы квазиньютоновские (qua- si-Newton) 139 Антипереполнение (underflow) 26 Аппроксимация конечно-разностная (finit-difference) 45 — с помощью секущей (secant ap- proximation) 44, 203 Вращение Якоби (Jacobi rotation) 76 Гессиан (Hessian) 92 Градиент (gradient) 92 Дифференцируемость по Гато (Ga- teaux differentiability) 107 — — Фреше (Frechet) 107 Дробление ньютоновского шага (back- tracking from the Newton step) 41 Задача безусловной минимизации (unconstrained minimization prob- lem) 15 — нелинейная о наименьших квадра- тах (nonlinear least-squares) 16, 19 — о минимальных поправках (least- change) 288 Исчезновение порядка см. Антипере- полнение Константа Липшица (Lipschitz con- stant) 98 Мажоризация (maJorization) 118 Масштабы (scales) 190 Матриц разложения (matrix factori- zations) 65 Матрица вращения (rotation matrix) 76 — Гессе см. Гессиан — незнакоопределенная (indefinite) 80 — отрицательно определенная (nega- tive definite) 80 — — полуопределенная (negative se- midefinite) 80 — положительно определенная (po- sitive definite) 80 — — полуопределенная (positive se- midefinite) 80 — со строго доминирующей диаго- налью (strictly diagonally domi- nant) 81 — Якобу см. Якобиан Матрицы сингулярное разложение (singular value decomposition) 85 — сингулярные числа (singular va- lues) 85 — собственные векторы (eigenvec- tors) 80 — — значения (eigenvalues) 80 — число обусловленности (condition number) 73 Машинный эпсилон (machine epsi- lon, macheps) 26 Метод Гаусса — Ньютона (Gauss — Newton method) 263 — — — демпфированный (damped) 269 — глобальный (global) 16 — деления пополам (bisection) 40 — локальный (local) 16 — итеративный локально сходящийся (iterative locally convergent) 36 — Левенберга—Маркварта. (Leven- berg—Marquardt) 270 — Ньютона — Рафсона (Newton — 436 Предметный указатель Raphson) 32, 39 — — сходимость (convergence) 36 — секущих (secant) 45, 203, 209 — — обратно положительно опреде- ленный (inverse positive definite) 242 — — положительно определенный (positive definite) 241 — сопряженных градиентов (conjuga- te gradient) 292 Методы спуска (descent) 105 Минимум глобальный (global mini- mizer) 17, 50 — локальный (local) 17, 50 Модель аффинная (affine model) 32 Модель—доверительная область (mo- del—trust region) 161 — локальная (local model) 32 Модульная система алгоритмов (mo- dular system of algorithms) 314 Направление спуска (descent dire- ction) 141 — — наискорейшего (steepest-des- cent) 142 Норма (norm) 59 — евклидова см. Норма наименьших квадратов — матричная (matrix) 61 — наименьших абсолютных разно- стей (least absolut residual) 60 — — квадратов (least-squares) 60 — Чебышёва 60 Область доверительная (trust region) 161 Оператор матричного проектирования (matrix projector operator) 289 — множественного ветвления (mul- tiple branch statement) 320 Ортогональная матрица (orthogonal matrix) 65 Ортогональные векторы (orthogonal vectors) 65 Ортонормальная система векторов (orthonormal set) 65 Ошибка округления (round-off error) 25 — — абсолютная (absolute) 25 — — относительная (relative) 25 Перемасштабирование (rescaling) 190 Переполнение (overflow) 26 Поиск линейный (line search) 145 — — идеальный (perfect) 187 Последовательность сходящаяся (con- vergent sequence) 34 — — с (у-порядком, по меньшей мере равным р (<7-oder at least p) 35 — — у-шагово <7-сверхлинейно (/-step ^-superlinearly) 35 — 9-линейно сходящаяся (i/'linearly) 34 — 9-сверхлинейно сходящаяся (q-su- perlinearly) 35 Представление с плавающей точкой (floating-point representation) 24 Представления точность (precision) 24 Производная по направлению (direc- tional derivative) 93 Система нелинейных уравнений (si- multaneous nonlinear equations) 14 Системы плохо обусловленные (ill- conditioned systems) 72 Скалярное произведение (inner pro- duct) 64 Скорость сходимости ^квадратичная (^-quadratic convergence) 35 — — ^-кубическая ((/-cubic) 35 След матрицы (trace of matrix) 63 Уравнения нормальные (normal equa- tions) 84 Ухудшение ограниченное (bounded deterioration) 213 Формула Дэвидона — Флетчера — Пауэлла (Davidon — Fletcher — Ро- well update) 242 — Ньютона — Лейбница 33 — пересчета Бройдена (Broyden's up- date) 207 — — симметричная одноранговая (symmetric rank-one (SRI)) 253 — проекционная и оптимально обус- ловленная (projected and optimally conditioned) 254 — секущих см. Формула пересчета Бройдена — — положительно определенная (positive definite secant update) 240 — — разреженная (sparse) 290 — — с минимальными поправками (least-change) 293 — — симметричная Пауэлла — Брой- дена (Powell-symmetric-Broyden, PSB) 234 — Шермана — Моррисона — Вудбери (Sherman — Morrison — Woodbury) 225 Функция Вуда (Wood's function) 424 — итерационная сжимающая (contra- ctive iteration) 119 — невязки (residual) 259 Предметный указатель 437 — непрерывная по Липшицу (Lipschitz continuous) 36, 98 — непрерывно дифференцируемая (continuously differentiable) 92 — — — в открытой области (open region) 93 — — — дважды (twice) 94 — Пауэлла обобщенная вырожденная (extended Powell singular) 423 — Розенброка (Rosenbrock) 193 — — расширенная (extended) 423 — типа спиралевидного желоба (he- lical valley) 424 — тригонометрическая 423 Хаусхолдера преобразование (Hous- holder transformation) 69 Холесского разложение (Cholesky decomposition) 70 Шаг криволинейный (hook step) 170 — с двойным изломом (double dog- leg) 171 Шага длина (length) 160 — — минимальная (minstep) 159 — направление (direction) 160 Якобиан (Jacobian) 96 BFGSFAC 418 BFGSUNFAC 416 BFGS-формула см. Формула секущих положительно определенная BROYFAC 415 BROYUNFAC 414 CDGRAD 382 CHOLDECOMP 377 CHOLSOLVE 366 CONDEST 368 DFP-формула см. Формула Дэвидо- на — Флетчера — Пауэлла . DOGDRIVER 395 DOGSTEP 396 FDGRAD 381 FDHESSF 380 FDHESSG 379 FDJAC 373 FN 355 FOR 320 FVEC 357 GRAD 355 — HESS 356 HOOKDRIVER 390 HOOKSTEP 392 IF-THEN 319 IF-THEN-ELSE 320 1NITHESSFAC 421 INITHESSUNFAC 420 JAC 357 JACROTATE 371 LINESEARCH 384 LINESEARCHMOD 387 LSOLVE 367 LTSOLVE 368 <1-норма см. Норма наименьших аб- солютных разностей <г-норма см. Норма евклидова Zp-норма (Ip-norm) 60 /оо-норма см. sup-норма MACHINEPS 363 MODELHESS 374 NEDRIVER 341 NEEXAMPLE 353 NEFN 362 NEINCK 360 NEMODEL 402 NEMODELFAC 405 NESTOP 411 NESTOPO 413 NP-полнота (NP-completeness) 287 (PLU decomposi PLU-разложение tion) 69 QFORM 372 QRDECOMP 363 QRP-разложение (QRP decomposi- tion) 69 QRSOLVE 365 QRUPDATE 370 QR-разложение (QR decomposition) 69 REPEAT 321 RSOLVE 366 SRI-формула см. Формула пересче- та симметричная одноранговая sup-норма 60 TRUSTREGUP 398 UMDRIVER 325 UMEXAMPLE 329 UMINCK 358 UMSTOP 408 UMSTOPO 409 WHILE 321 Оглавление Предисловие редактора перевода и переводчика .......... 5 Предисловие к русскому изданию ............... 7 Предисловие ....................... 9 Глава 1. Введение .................... 14 1.1. Постановки задач . ................ 14 1.2. Характерные особенности встречающихся на практике задач 18 1.3. Арифметика конечной точности и измерение ошибок .... 24 1.4. Упражнения . .................. 27 Глава 2. Нелинейные задачи с одной переменной . . .... ... 29 2.1. О том, чего не следует ожидать ........... 29 2.2. Метод Ньютона решения одного уравнения с одним неиз- вестным . .................... 31 2.3. Сходимость последовательностей действительных чисел . . 34 2.4. Сходимость метода Ньютона ............ 36 2.5. Глобально сходящиеся методы решения одного уравнения с одним неизвестным ................ 40 2.6. Методы для случая, когда производные не заданы .... 44 2.7. Минимизация функции одной переменной ........ 50 2.8. Упражнения . .................. 53 Глава 3. Основы вычислительной линейной алгебры ........ 58 3.1. Векторные и матричные нормы, ортогональность ..... 59 3.2. Решение систем линейных уравнений и разложения матриц 65 3.3. Погрешности при решении линейных систем ....... 71 3.4. Формулы пересчета матричных разложений ....... 76 3.5. Собственные значения и положительная определенность . . 79 3.6. Линейная задача о наименьших квадратах ....... 82 3.7. Упражнения . .................. 88 Глава 4. Основы анализа функций многих переменных ....... 91 4.1. Производные и многомерные модели ......... 91 4.2. Конечно-разностные производные в многомерном случае . . 100 Оглавление 439 4.3. Необходимые и достаточные условия в задачах безусловной минимизации . .................. 103 4.4. Упражнения . .................. 106 Глава 5. Метод Ньютона решения нелинейных уравнений и безусловной минимизации ................... 110 5.1. Метод Ньютона решения систем нелинейных уравнений . .110 5.2. Локальная сходимость метода Ньютона ....... 114 5.3. Теорема Канторовича и теорема о сжимающем отображении 116 5.4. Методы с конечно-разностными производными для решения систем нелинейных уравнений ............ 119 5.5. Метод Ньютона безусловной минимизации ....... 125 5.6. Методы с конечно-разностными производными для безуслов- ной минимизации . ................ 130 5.7. Упражнения . .................. 134 Глава 6. Глобально сходящиеся модификации метода Ньютона .... 138 6.1. Общая квазиньютоновская схема ......... 139 6.2. Направления спуска ................ 140 6.3. Линейный поиск .................. 144 6.3.1. Результаты исследования сходимости при надлежащем выборе шагов . ............... 149 6.3.2. Выбор «шага дроблением ........... 155 6.4. Подход: модель—доверительная область ........ 160 6.4.1. Локально ограниченный оптимальный («криволиней- ный») шаг .................. 165 6.4.2. Шаг с двойным изломом ............ 171 6.4.3. Пересчет доверительной области ......... 176 6.5. Глобальные методы решения систем нелинейных уравнений 180 6.6. Упражнения . .................. 187 ' Глава 7. Критерии останова, масштабирование и тестирование .... 190 ^ 7.1. Масштабирование . ................ 190 7.2. Критерии останова ................. 195 7.3. Тестирование . .................. 198 7.4. Упражнения . .................. 202 Глава 8. Методы секущих для решения систем нелинейных уравнений 204 8.1. Метод Бройдена . ................ 205 8.2. Анализ локальной сходимости метода Бройдена . . . . .211 . 8.3. Реализация квазиньютоновских алгоритмов, использующих формулу пересчета Бройдена ............. 223 8.4. Другие формулы секущих для нелинейных уравнений . . . 227 8.5. Упражнения . .................. 229 Глава 9. Методы секущих для безусловной минимизации ...... 232 9.1. Симметричная формула секущих Пауэлла ........ 233 9.2. Симметричные положительно определенные формулы секущих 237 9.3. Локальная сходимость положительно определенных методов секущих . .................... 243 9.4. Реализация квазиньютоновских алгоритмов, использующих положительно определенные формулы секущих ...... 248 440 Оглавление 9.5. Еще один результат, касающийся сходимости положительно определенных методов секущих ........... 252 9.6. Другие формулы секущих для безусловной минимизации- . . 252 9.7. Упражнения . .................. 254 Глава 10. Нелинейная задача о наименьших квадратах ....... 259 10.1. Постановка нелинейной задачи о наименьших квадратах . . 259 10.2. Методы типа Гаусса—Ньютона ........... 263 10.3. Методы полностью ньютоновского типа ......... 271 10.4. Некоторые другие соображения относительно решения нели- нейных задач о наименьших квадратах ......... 277 10.5. Упражнения . .................. 280 Глава 11. Методы решения задач со специальной структурой .... 284 11.1. Разреженный конечно-разностный метод Ньютона ..... 285 11.2. Разреженные методы секущих ............ 288 11.3. Вывод формул секущих с минимальными поправками . . . 293 11.4. Анализ методов секущих с минимальными поправками . . 299 11.5. Упражнения ................... 305 Приложение А. Модульная система алгоритмов безусловной минимизации и решения нелинейных уравнений (Р. Шнабель) . . . 308 Приложение В. Тестовые задачи (Р. Шнабель) .......... 422 Литература .. ..................... 425 Именной указатель ..................... 432 Предметный указатель . .................. 434 Научное издание Джон Дэннис, мл., Роберт Шнабель ЧИСЛЕННЫЕ МЕТОДЫ БЕЗУСЛОВНОЙ ОПТИМИЗАЦИИ И РЕШЕНИЯ НЕЛИНЕЙНЫХ УРАВНЕНИЙ Заведующий редакцией доктор физ.-мат. наук, профессор [ Б. В. Шабат | Зам. заведующего редакцией А. С. Попов '————————— Ст. науч. редактор И. А. Маховая Мл. редактор Т. Ю. Дехтярева Художник В. А. Медников Худ. редактор В. И. Шаповалов Технический редактор Е. Н. Прохорова Корректор С. А. Денисова ИВ № 6285 Сдано в набор 24.06.87. Подписано к печати 22.03.88. Формат 60Х90/16. Бумага типограф- ская № 2. Печать высокая. Гарнитура литературная. Объем 13,75 бум. л. Усл. печ. л. 27,50. Усл. кр.-отт. 27,50. Уч.-изд. л. 26,20. Изд. № 1/5470 Тираж 14000 экз. Зак. 954Цена^2р. 10 к. ИЗДАТЕЛЬСТВО «МИР» 129820, ГСП, Москва, И-110, 1-й Рижский пер., 2 Отпечатано с набора Ленинградской типографии № 2 головного предприятия ордена Трудового Красного Знамени Ленинградского объединения техническая книга» им. Евгении Соколовой Союзполиграфпрома при Государственном комитете СССР по де- лам издательств, полиграфии и книжной торговли. 198052, г. Ленинград, Л-52, Измай- ловский проспект, 29, в Ленинградской типографии №. 4 ордена Трудового Красного Знамени Ленинградского объединения «Техническая книга» им. Евгении Соколовой Со- юзполиграфпрома при Государственном комитете СССР по делам издательств, поли- графии и книжной торговли, 191126, Ленинград, Социалистическая ул., 14.