ITERATIVE METHODS FOR THE SOLUTION OF EQUATIONS J.F.TRAUB Edwin Howard Armstrong Professor of Computer Science and Professor of Mathematics Columbia University Chelsea Publishing Company New York, N.Y. 1982 Дж.ТРАУБ ИТЕРАЦИОННЫЕ МЕТОДЫ РЕШЕНИЯ УРАВНЕНИЙ Перевод с английского И. А. Глинкина под редакцией А. Г. Сухарева МОСКВА «МИР» 1985 ББК 22.19 Т 65 УДК 518.5 Трауб Дж. Т 65 Итерационные методы решения уравнений: Пер. с англ.— М.: Мир, 1985.— 264 с. Монография известного американского математика, посвященная итерационным методам решения уравнений. Эти методы находят ши- рокое применение в вычислительной практике. Книга отличается боль- шими методическими достоинствами, она дважды издавалась в ори-* гинале. Автор знаком советским читателям по его совместной с Вожь< няковским «Общей теорией оптимальных алгоритмов» (М.: Мир, 1983). Для математиков-вычислителей, студентов и аспирантов универси- тетов. 1702070000—325 ,„ „, , ББК 22.19 041(01)-85 36-85-4-' . 518 Редакция литературы по математическим наукам 1982 by J. F. Traub Перевод на русский язык, «Мир», 1985 ОТ РЕДАКТОРА ПЕРЕВОДА Первое издание предлагаемой вниманию читателя книги по- явилось в 1964 г., а второе (стереотипное)—в 1982 г. Она на- писана известным американским специалистом в области вы- числительной математики, возглавляющим факультет вычисли- • тельных наук Колумбийского университета (Нью-Йорк). Книга посвящена классическому разделу численного анализа—мето- дам решения уравнений и систем уравнений вида f{x}=0. По- строенная в ней общая теория итерационных функций (ИФ) позволяет единообразно исследовать различные существующие алгоритмы и строить новые алгоритмы с заданными свойствами. Для отыскания корня необходимо получать информацию о функции f, т. е. вычислять в различных точках ее значения и значения ее производных.. ИФ можно охарактеризовать этой информацией, а также скоростью (порядком) сходимости к ис- комому корню последовательности приближений, генерируемой данной ИФ. Эти характеристики, позволяющие определить по- нятие эффективности ИФ, и составляют основной предмет ис- следования. Его результатом является построенная в моногра- фии теория оптимальных ИФ, имеющая важное значение не только для задач решения уравнений и систем уравнений, но и для численного анализа в целом. Данная монография носит фундаментальный характер. Она положила начало развитию современной теории итеративной вычислительной сложности, содержит много красивых и глубо- ких результатов. Развиваемые в ней идеи и методы находят применение в различных разделах вычислительной математики. Все это и послужило причиной появления русского перевода. Конечно, два десятилетия принесли много нового, и сегодня книга не отражает в полной мере современного состояния пред- мета. Однако на русском языке до сих пор не было книг, со- держащих столь исчерпывающее описание теории решения од- номерных уравнений. Следует заметить, что по сути дела продолжением данной книги является часть В монографии Дж. Трауба, X. Вожьняковского «Общая теория оптимальных алгоритмов» (М.: Мир, 1983), в которой содержится также до- статочно полная аннотированная библиография. • При переводе были исправлены замеченные неточности и опечатки. Кроме того, при подготовке перевода мы неоднократно консультировались с автором, с согласия которого внесли от- дельные разъясняющие замечания. Выражаем ему за это глу- бокую благодарность. Л, Сухарев ПРЕДИСЛОВИЕ К РУССКОМУ ИЗДАНИЮ Я пишу это предисловие ровно через 20 лет после выхода в свет первого американского издания. Поэтому уместно оста- новиться на перспективах развития излагаемого предмета. Се- годня я озаглавил бы свою книгу «Теория оптимальных итера- ционных методов». Такое название представляется более ин- формативным. Кроме того, вместо вычислительной эффективно- сти я использовал бы понятие вычислительной сложности. Эти понятия являются взаимно обратными и, следовательно, взаимо- зависимыми. В то же время термин «сложность» сегодня ши- роко используется в вычислительной математике. Впервые тер- мин «вычислительная сложность» появился в 1965 г., через год после выхода книги в свет. Изучение сложности предполагает выявление связи между информацией, используемой алгоритмом, и его порядком. Клю- чевая роль в исследованиях по оптимальности итерационных алгоритмов принадлежит тому факту, что максимальный поря- док алгоритмов некоторого класса определяется информацией, используемой алгоритмами, и не зависит от их структуры. Данная монография положила начало исследованиям опти- мальных итерационных алгоритмов, и за прошедшее время в этой области получено немало результатов. В 1975 г. Вожьня- ковский ввел понятие порядка информации, служащее универ- сальным средством нахождения порядка итерационных алгорит- мов. В 1974 г. Кунг и Трауб высказали гипотезу о том, что ите- рационный алгоритм, который вычисляет п значений функции и ее производных и не использует ранее вычисленную информа- цию, имеет порядок не выше 2"-"'. Эта гипотеза доказана для важных частных случаев (например, эрмитовой информации), однако в общем случае вопрос остается открытым. Свежие ре- зультаты, относящиеся к этой проблематике, изложены в частях В и С монографии Дж. Трауба и X. Вожьняковского «Общая теория оптимальных алгоритмов».—М.: «Мир», 1983. Подход, при котором основное внимание уделяется свой- ствам используемой алгоритмами информации, а не структуре алгоритмов, оказался очень плодотворным и в областях, не свя- занных с решением нелинейных уравнений. Теорию оптималь- ных алгоритмов решения задач с неполной информацией мы недавно решили назвать теорией сложности информации (Infor- mation Based Complexity). Помимо указанной выше книги, эти вопросы рассматриваются в монографии J. F. Traub, G. W. Wa- silkowski, H. Wozniakowski, Information, Uncertainty, Comple- xity, Addison-Wesley, 1983 (см. также Information and Computa- tion в книге Advances in Computers, Academic Pess, 1984). В 1985 г. издательство Academic Press начнет издание жур- нала Journal of Complexity, в котором будут широко представ- лены исследования по проблемам сложности информации. Нью-Йорк, ноябрь 1984 Дж. Ф. Трауб Сюзанне ПРЕДИСЛОВИЕ Книга посвящена общей теории итерационных численных алгоритмов решения уравнений и систем уравнений. В частно- сти, изучается связь между количеством и качеством информа- ции, используемой алгоритмом, и его эффективностью. Итера- ционные функции подразделяются на четыре класса в зависимо- сти от того, используют они новую информацию в одной или в нескольких точках и используется ли ими полученная ранее ин- формация. Проводится систематизация известных итерационных функций и вводятся новые классы эффективных в вычислитель- ном отношении итерационных функций. Наш интерес к вопросам эффективного использования информации обусловлен широким распространением ЭВМ. Для математических обоснований полученных результатов характерна строгость, однако она не является самоцелью. Часть результатов допускает более широкое приложение. Это отно- сится, в частности, к гл. 3 («Математика разностных отноше- ний»), приложениям А («Интерполяция») и D («Ускорение сходимости»). Приведенный в гл. 12 перечень итерационных функций позволяет использовать книгу в качестве справочника по данному предмету. В приложении Е представлены резуль- таты проведенных на ЭВМ численных экспериментов. Исследования в области методов решения уравнений имеют давнюю историю. В ее развитие внесли вклад такие известные математики, как Коши, Чебышев, Эйлер, Фурье, Гаусс, Ла- гранж, Лагерр, Ньютон. Классическая работа Шредера по дан- ному предмету датируется 1870 г. Достаточно беглого взгляда. на библиографию, чтобы получить представление об уровне ин- тереса к данной проблематике в настоящее время. По-видимо- му, из недавних работ наиболее весомым вкладом в эту область следует считать монографию Островского. Представленные в книге результаты в большинстве своем являются новыми и ранее не публиковались. Мы пытались сде- лать все возможное, чтобы предмет книги предстал в должной исторической перспективе. Часть результатов докладывалась устно на семинарах Ассоциации вычислительной техники в 1961—63 гг. и Американского математического общества в 1962, 1963 гг., а также на Международном математическом конгрессе в 1962 г. 8 Предисловие Мне хочется выразить искреннюю признательность за по мощь, оказанную моими друзьями и коллегами из фирмы Bell Telephone Laboratories. В большом долгу я перед М. Д. Макил- роем, Дж. Моррисоном и X. О. Поллаком за многочисленные важные предложения, А. Дж. Голдстейном, Р. У. Хэммингом и Е. Н. Гилбертом — за содержательные беседы и ценные за- мечания. Весьма благодарен профессору Станфордского уни- верситета Г. Е. Форсайту за поддержку и полезные обсуждения в период подготовки рукописи и прочтение ее окончательного варианта, профессору А. Ралстону из Стивенского технологи- ческого института, С. П. Моргану и Дж. У. Тьюки за прочтение рукописи, а Дж. Риордану—за многочисленные предложения, способствовавшие улучшению стиля. Хочу поблагодарить Нэнси Моррис за неизменную готов- ность добавить «еще одну самую последнюю» ссылку, Элен Карлсон — за редактирование окончательного варианта ру- кописи и вычитку корректуры, Элизабет Дженкинс—за превос- ходное руководство оформлением сложной рукописи и Джой Катанзаро—за быструю и аккуратную машинопись. Наконец, я пользуюсь случаем выразить особенную призна тельность моей жене как за помощь в редактировании и вы- читке корректуры, так и за неослабную поддержку и вдохно- вение. Дж. Ф. Трауб 1 ГЛАВА ПРЕДВАРИТЕЛЬНЫЕ СВЕДЕНИЯ Основные понятия, изучаемые в книге, и используемые для них обозначения вводятся в § 1.2. 1.1. ВВЕДЕНИЕ Предметную область нашего исследования можно назвать единым термином алгоритмика, под которым мы будем понимать изучение алгоритмов вообще и исследование вопросов сходимо- сти и эффективности вычислительных алгоритмов в частности. Если говорить конкретнее, мы будем изучать алгоритмы ре- шения уравнений. Будет исследоваться связь между количе- ством и качеством информации, используемой алгоритмом, с одной стороны, и его эффективностью—с другой; влияние по- вторного использования ранее вычисленной информации и вы- числения новой информации в подходящих точках. Наше исследование итерационных алгоритмов решения урав- нений будет в достаточной мере систематизировано. В ходе ис- следования мы изучим новые семейства эффективных в вычис- лительном отношении итерационных алгоритмов, выделив как частные случаи некоторые широко известные итерационные ал- горитмы. Мы надеемся, что этот всеохватывающий подход по- зволит исключить или по крайней мере сократит открытие за- ново уже известных алгоритмов. Наш подход приводит к есте- ственным классификационным схемам и позволяет единооб- разно оценивать погрешность, получать критерии сходимости для семейств итерационных алгоритмов. Окончательный вывод о полезности новых методов можно будет сделать только после их проверки на ряде практических задач. В настоящее время, однако, теоретическую оценку погрешности метода принято подкреплять представительными численными экспериментами на тестовых задачах. Хотя мы ограничиваемся проблематикой решения веществен- ных уравнений и систем уравнений, область приложения дан- ной работы значительно шире. В частности, развитая нами тех- ника применима в таких областях, как решение дифференци- альных и интегральных уравнений, вычисление собственных значений. Представляет интерес обобщение полученных резуль- татов на случай абстрактных пространств. Этот вопрос более подробно рассматривается в приложении F. 10 Гл. 1. Предварительные сведения 1.2. ОСНОВНЫЕ ПОНЯТИЯ И ОБОЗНАЧЕНИЯ 1.2.1. Некоторые понятия и обозначения. Вводимые ниже обозначения сохраняют постоянный смысл на протяжении всей книги. В тех редких случаях, когда они будут использоваться для иных целей (например, в качестве индексов суммирования), это будет ясно из контекста. Мы будем заниматься задачей приближенного вычисления нуля функции f(x), или, что то же самое, задачей приближен- ного вычисления корня уравнения f(x)=0. Термины нуль функ- ции f, корень уравнения f(x)=0 и решение уравнения f(x) = О будут использоваться как эквивалентные. По-видимому, у рас- сматриваемой нами задачи нет общепризнанного точного назва- ния. В самом деле, термин решение уравнения охватывает и решение дифференциальных уравнений. Прилагательные алгеб- раическое и трансцендентное обычно используются для разли- чения случаев, когда / соответственно является или не является многочленом. Представляется, что наиболее подходящим тер- мином для обозначения нашей задачи является термин поиск корней {root-finding). Мы ограничимся рассмотрением случая, когда /—веще- ственная однозначная функция вещественного аргумента, про- изводные которой вплоть до некоторого порядка непрерывны в окрестности вещественного нуля к. Условие вещественности нуля не играет принципиальной роли. Всюду, за исключением гл. 11, f является скалярной функцией скалярного аргумента; в гл. 11 функция f—вектор-функция векторного аргумента. Независимая переменная указывается или не указывается явно в зависимости от того, идет ли речь о функции или о зна- чении функции в некоторой точке из области определения. Учи- тываются и соображения удобства чтения формул. Таким обра- зом, обозначения f и f(x) будут использоваться как равноправ- ные (Baas [1.2-1, pp. 67—68]). Производные функции f будут обозначаться либо через /<°, либо через f^f", ..., причем /'"'А/. Если f не обращается в нуль в окрестности точки а и производная /(г) непрерывна в этой окрестности, то у / существует обратная функция У, про- изводная ^"(0 которой непрерывна в некоторой окрестности нуля. Нуль а имеет кратность т, если f(x)==(x—a)mg(x), причем функция g{x} ограничена в окрестности точки о. и ^(oQ^O. Мы будем всегда предполагать, что т—целое поло- жительное число. Случай, когда т не является натуральным, рассматривается в книге Ostrowski [1.2-2, Chap. 5]. Если т = 1, 1.2. Основные понятия и обозначения 11 то к называется простым' нулем; если же т> 1, то ос называ- ется кратным нулем. По-видимому, наиболее примитивным способом аппроксима- ции вещественного нуля является следующий алгоритм бисек- ции. Пусть для некоторой пары точек а, Ь и непрерывной функ- ции f справедливо неравенство f(a}f(b)<0. Тогда f имеет по крайней мере один вещественный нуль в интервале (а,Ь}. Для разъяснения работы алгоритма возьмем интервал (О,1) и пред- положим, что f(0)<0, /'(!)> 0. Вычислим /(1/2); если ^(1/2)= 0, то нуль найден. Если Д1/2)<0, то нуль располо- жен в интервале (1/2, 1), и следует вычислять /(3/4). Если f(l/2)>0, то нуль расположен в (0, 1/2), и следует вычислять f(l/4). В результате ^-кратного повторения бисекции мы либо найдем нуль, либо локализуем его в интервале длиной 2~". Если в качестве приближения к нулю выбрать середину последнего интервала локализации, то максимальная погрешность соста- вит 2-cl-'l, причем для ее достижения потребуется q вычислений значений функции f. Отметим, что достижимая точность аппрок- симации нуля в алгоритме бисекции определяется только точ- ностью вычисления значений функции f, так как для работы ал- горитма необходимо лишь правильное определение знака f(x). Данный алгоритм бисекции является примером одноточеч- ной итерационной функции с памятью (строгие определения приводятся ниже). Поскольку алгоритм не использует данных, характеризующих структуру f (например, значения ее производ- ных), скорость его сходимости невелика. В то же время гаран- тируется сходимость метода. Для ускорения сходимости при- влекаются различные свойства f (см., например, Gross, Jrhnson fl.2-3], Hooke, Jeeves [1.2-4], Lehmer [1.2-5]). В статье Kiefer [1.2-6] приводится оптимальная стратегия поиска максимума унимодальной функции. Использование дополнительной информации об f позволяет добиться существенного ускорения сходимости по сравнению с алгоритмом бисекции. Естественной и легко вычисляемой ин- формацией являются значения самой функции f и значения ее производных. В дальнейшем наряду с термином «информация» будем использовать термины «данные» и «испытание» (sample). Пусть xi,Xi-i, .... xi-n— набор из п + 1 точек, являющихся приближениями к решению к, а выбор xi+\ полностью опреде- ляется информацией, полученной в точках Xi,x.i-\, ..., Xi-n. Обозначим через (р функцию, задающую соответствие между набором Xi,xi-i, ..., Xi-n и точкой очередного приближения л',+1, т. е. Xt+\==(f>{Xi,Xi-l, ..., Xi-n). (1.1) Определенную таким образом функцию (р будем называть ите- рационной функцией. В дальнейшем вместо термина «итвраци- 12 Гл. 1. Предварительные сведения очная функция» как в единственном, так и во множественном числе будет использоваться аббревиатура ИФ. Положим r/l,^f>(^-/) Мы будем также писать г/,_, вместо f(x^_.\ и У^. вместо У^ (г/,-/). Поскольку в точке xi-, используется информация о значениях функции f и ее производных, правомерна и такая запись: у,=т(х f ^1а\ х f ^1) Ч1Ч1 ^"(> 1 г •••> /г > •^t-l' '('-Г '"'' 't-Г "'" . .•.,^„,^,...,Ю. (1.2) Однако мы не будем заниматься ИФ столь общего вида; классы изучаемых в дальнейшем ИФ определены в п. 1.2.2. Вместо (p(xi,Xi-.i, ..., Xi-n) удобнее писать (р{х} или про- сто ф. Отметим, что (р — функционал, зависящий от f, и пра- вильнее было бы писать (p(x,f}. Однако необходимость в таком обозначении возникает лишь в гл. 7. Даже простейший итерационный алгоритм включает началь- ное приближение (приближения), ИФ и численный критерий, позволяющий установить, что сходимость достигнута. Из этих трех компонент мы будем заниматься только ИФ. Широко из- вестны две следующие ИФ: метода Ньютона — Рафсона и ме- тода секущих. Первая ИФ имеет вид а вторая- ^ (Xl, Х,^} = Xi - f, /_'-' , f, ^ fi_i. '1 '1-1 (1.3) (1.4) Первую мы будем в дальнейшем называть ИФ Ньютона. ИФ метода секущих тесно связана с методом regula falsl. При опре- делении последнего предполагается сохранение двух аппрокси- маций, «объемлющих» корень, в то время как ИФ метода се- кущих использует две последние аппроксимации. Во многих случаях мы будем иметь дело не с самой функ- цией /, а с ее нормированным аналогом "==//Г Г^О. (1.5) Если f==0, a f^=0, то и не определено. При f==f'==0 (слу- чай кратного нуля) положим и == 0. В дальнейшем изложении м играет исключительно важную роль. Одна из причин этого со- стоит в том, что в случае кратного нуля lim х-»а Г ч(х} 1 Ь-aJ- (1.6) 1.2. Основные понятия и обозначения 13 Что касается простых нулей, то для них Hnip^-1-l. ^ab-CU Отметим, что при неизвестном а погрешность х—а аппрокси- мации х неизвестна, в то время как и вычисляется на каждом шаге итерации. Для удобства дальнейшего изложения введем дополнитель- ные обозначения: ei=Xi—ст, е=х—а. (1.7) Таким образом, ei—погрешность г'-й аппроксимации. Положим В „W^. Л,(.)=^, . , "/+„.-! W . / , _ ^(/> (У) ч^^^—^^Г' •^1^'- i\y'(y)' (1.8) (_1)/-1у(/> (у) l! [У (У)}' y-f W Величины aj(x) суть коэффициенты ряда Тейлора, Л/(д-)— нормированные коэффициенты ряда Тейлора для функции f. Коэффициенты В/, m суть обобщенные нормированные коэффи- циенты ряда Тейлора, используемые в случае, когда кратность превышает единицу; отметим, что В/, \{х} == А,(х). Коэффи- циенты sf-j{y) представляют собой нормированные коэффициен- ты ряда Тейлора для обратной функции ST, а У/(х)—коэффи- циенты ряда Тейлора для У, полученные при другой норми- ровке подстановкой y==f(x) после дифференцирования. Условимся о следующем использовании символов ->, О и ==. Если \img(Xi)=C, то мы будем писать g(x,)->-C либо г->оо g—^C. Если lim g (х) = С, то будем писать g(x)—>-C либо х->а g->-C. Вид предела всегда будет ясен из контекста. Если f/g->C, где С—ненулевая константа, будем писать f==0(g) или f ~ Cg. Символ = будет обозначать приближенное равен- ство чисел. Так, (l + V^ )/2== 1.618= 1.62. Использование этих символом иллюстрирует Пример 1.1. Пусть „ — лд pi 4- Л/ е4 е^, —lv^^e^ -г- 14 ^, где ei ->• 0, Mi -г К. ^ 0, Ni —>- L ^= 0, причем ei Ф 0 для всех t. Гогда ^ж-^^0^)' поскольку N^e]feз^-> L. Аналогично е^ ~ К,е}, поскольку е^^е\=я ==M,+N,e^K. I 252 Литература THACHER, н. с., JR., An iterative method for quadratures. Argonne National Laboratories Report, 1962. [A.1-19]. THEREMIN, F., Recherches sur la resolution des equations de tous leg degres. J. Reine Angew. Math. 49 (1855), 187-242. THOMPSON, G. т., Characteristic values and vectors of defective matrices. Comm. ACM. 6 (3), (1963), 106-107. TODD, J., Classical numerical analysis. A Survey of Numerical Analysis, 27-118. Edited by J. Todd. McGraw-Hill Book Company, Inc., New York, 1962. [A.2-12]. TRAUB, J. p., Comparison of iterative methods for the calculation of wth roots. Comm. ACM 4 (3), (1961), 143-145. [5.1-18]. ————, On a class of iteration' formulas and some historical notes. Comm. ACM 4 (6), (1961), 276-278. [5.2-4]. ——, On functional iteration and the calculation of roots. Preprints of papers presented at the 16th National Meeting, ACM, 1961, pp. 5A-1 (1-4). ——, The theory of multipoint iteration functions. Digest of Technical Papers, ACM 62 National Conference, 1962, 80-81. ——, On the wth derivative of the inverse function. Amer. Math. Monthly 69 (1962), 904-907. [В-8]. TRAUB, J. F. and SHERMAN, p. м., A macro compiler that counts machine cycles. Unpublished manuscript. [C-4]. TUROWICZ, А. в., Sur les derivees d'ordre superieur d'une fonction inverse. Colloq. Math. 7 (1959), 83-87. [В-6]. ————, Sur 1'approximation des racines de nombres positifs. Ann. Polon. Math. 8 (1960), 265-269. USPENSKY, J. v., Note on the computation of roots. Amer. Math. Monthly 34 (1927), 130-134. [5.2-19]. VAN ORSTRAND, с. Е., Reversion of power series. Philos. Mag. 19 (1910), 366-376. [В-1]. WAADELAND, н., On some transcendental equations. III. Norske Vid. Selsk. Forh., Trondheim 25 (1952), 46-49. WALL, D. D., The order of an iteration formula. MTAC 10 (1956), 167-8. WALL, н. s., A modification of Newton's method. Amer. Math. Monthly 55 (1948), 90-94. [5.2-12]. ————, Analytic Theory of Continued Fractions. D. Van Nostrand Company, Inc., Princeton, N. J., 1948. [5.2-3]. WARD, J. A., The down-hill method of solving /(г) = 0. J. Assoc. Comput. Mach. 4 (1957), 148-150. [11.1-8]. WEISSINGER, J., Zur Theorie und Anwendung des Iterationsverfahrens. Math. Nachr. 8 (1952), 193-212. [F-30]. WHITTAKER, Е. т., A formula for the solution of algebraic or transcendental , equations. Proc. Edinburgh Math. Soc. 36 (1918), 103-106. [5,1-6]. Л итература 253 * WHITTAKER, Е. т. and ROBINSON, G., The Calculus of Observations. Blackie and Sons, London, 1944. WHITTAKER, Е. т. and WATSON, G. N., A Course of Modern Analysis, Third edition. Cambridge University Press, London, 1927. [8.2-2]. WILF, и. s., The numerical solution of polynomial equations. Mathematical Methods for Digital Computers, 233-241. Edited by A. Ralston and H. S. Wilf. John Wiley and Sons, New York, 1960. WILKINSON, J. н., The evaluation of the zeros of ill-conditioned polynomials. Numer. Math. 1 (1959): Part I, 150-166; Part II, 167-180. [F-3]. WILLERS, F. A., Practical Analysis, Graphical and Numerical Methods. Dover Publications, Inc., New York, 1948. WILLIAMS, J. м., Systems and Roots. William Byrd Press, Richmond, 1962. WOLFE, J. м,, A determinant formula for higher order approximation of roots. Math. Mag. 31 (1958), 197-199. WOLFE, P., The secant method for simultaneous nonlinear equations. Comm. ACM 2 (12), (1959), 12-13. [11.1-26]. WYNN, P., On a cubically convergent process for determining the zeros of certain functions. MTAC 10 (1956), 97-100. [С-6]. ZAJTA, A., Untersuchung uber die Verallgemeinerung der Newton-Raph- sonschen Wurzelapproximation. Acta Tech. Acad. Sci. Hungar.: Mitteilung I, 15 (1956), 233-260; Mitteilung II, 19 (1957), 25-60. [2,2-9], [2.3-1], [5.1-12], [7.3-4]. ZURMUHL, R., Praktische Mathematik fur Ingenieure und Physiker, dritte Auflage, Кар. 1. Springer-Verlag, Berlin, 1961. [A.2-4]. СПИСОК РАБОТ, ИЗДАННЫХ НА РУССКОМ ЯЗЫКЕ Белостоцкий А. Я. Итерационные формулы для решения уравнений и их использование для аппроксимации функций —Изв. высш. учеб. заведе- ний, сер. матем, 1962, № 2, с. 23—26. Воеводин В. В. Применение метода спуска для определения всех корней алгебраического многочлена. — ЖВМ и МФ, 1961, 1, № 2, с. 187—195. Гавурин М. К. Применение полиномов наилучшего приближения к улучше- нию сходимости итеративных процессов.—УМН, 1950, вып. 3, 156—160. Гельфонд А. О. Исчисление конечных разностей.—М.: Гостехиздат, 1952. Горнштейн М. С. Численное решение уравнений. — ДАН СССР, нов. сер., 1951, 78, № 2, с. 193—196. Загускин В. Л. Справочник по численным методам решения алгебраических и трансцендентных уравнений.—М.: Физматги.з, 1960. Канторович Л. В. Функциональный анализ и прикладная математика. — Вестник ЛГУ, 1948, № б, с. 13—18. Канторович Л. В. О методе Ньютона для функциональных уравнений. — ДАН СССР, нов. сер., 1948, 59, № 7, 1237-1240. Канторович Л. В. Некоторые дальнейшие применения метода Ньютона для функциональных уравнений. — Вестник ЛГУ, сер. матем., механики и астрономии, 1957, вып. 2, № 7, с. 1237—1240. Коллатц Л. Функциональный анализ и вычислительная математика. Пер. с нем. —М.: Мир, 1969. Крылов В. И. Приближенное вычисление интегралов.—М.: Наука, 1967. 254 Литература Ланс Дж. Численные методы для быстродействующих вычислительных ма- шин. Пер, с англ.—М.: ИЛ, 1962. Марков А. А. Исчисление конечных разностей. — Отд. Спб. тип. имп. Акад наук, 1889. Микеладзе Ш. Е. О некоторых итерациях высших порядков. — Сообщ. Акад наук ГрузССР, 1959, 22, № 3, с. 257—264. Микеладзе Ш. Е. Численные методы математического анализа. — М.: Гостех- издат, 1953. Микеладзе Ш. Е. Метод вариации параметров в решении уравнений. — Сообщ. Акад. наук ГрузССР, 1959, 23, № 1, с. 3—9. Моррей Ч. Б. Нелинейные методы. — В сб.: Современная математика для инженеров. Пер. с англ.—М.: ИЛ, 1958, с. 375—417. Островский А. Решение уравнений и систем уравнений. Пер. с англ. — М.: ИЛ, 1963,- Гиордан Дж. Введение в комбинаторный анализ. Пер. с англ.—М.: ИЛ, 1963. Салехов Г. С. О сходимости процесса касательных гипербол. — ДАН СССР, 1952, 82, № 4, с. 525—528. Стеффенсон И. Ф. Теория интерполяции.—М.—Л.: ОНТИ, 1935. Уиттекер Э., Робинсон Г. Математическая обработка результатов наблюде- ний Пер. с англ.—М.—Л.: ОНТИ, 1935. Хаусхолдер А. Основы численного анализа. Пер. с англ.—М.: ИЛ, 1956. Хемминг Р. В. Численные методы для научных работников и инженеров. Пер. с англ.—М.: Наука, 1972. УКАЗАТЕЛЬ ОБОЗНАЧЕНИЙ а,(х} ==^)/Л 13 Л/(х) =а,{х}/а,(х) 13 ^i!i (0 коэффициент Лагранжа—Эрмита 199 а нуль функции / 10 ^,(У) -f^ 13 В,^х) ^^"—^ 13 '•ffl\ / тат(х) В^ =[<-,"(^, 205 Pfe.a положительный корень уравнения gfe, а(0== О 42 С константа асимптотики погрешности 15 С[х, I] биномиальный коэффициент 108 С;// (t) коэффициент Ньютона 200 d объем информационного запроса 17 Dli =[C?,/(Q]^ 203 е == х — а 13 BI = Xi — а 13 EFF эффективность использования информации 17 Es одно из семейств итерационных функций 66 "En,s семейство итерационных функций, порож- даемых аппроксимацией производной 92 ^Еп, s семейство итерационных функций, порож- даемых аппроксимацией производных 95 ё, ^,(x,f, m)=EЛx,f\"n,l) 106 / функция, нуль которой требуется найти 10 *f^ аппроксимация для ^(5) 91 f[xi, YO; ^-i> Yi'> •••; ^f-n. Y„] разделенная разность с крат- ными узлами 197 / интерполяционная функция специального вида 132 9~ функция,обратная к f 10 ±У^) аппроксимация У^ 95 gk.a(t) =^-a?/ 42 Нц элементы матрицы, обратной к матрице Якоби 177 / класс итерационных функций порядка р 16 д/ класс итерационных функций порядка р с объемом информационного запроса d 17 fij матрицы Якоби 175 256 Указатель обозначений Ki,, (m) S, (x, f, т) == Z ^,. И (х -а-)1 115 те кратность нуля а 10 га число точек, в которых используется ранее вычисленная информация 18 v; u[x}=Y, vi (x — а)1 83 О порядок переменной величины 13 со; (т) ти(х)== Z а; {т)(х —а)' 115 р ' порядок итерационной функции 15 Pn,s(t} интерполяционный многочлен для / 52 (р, Ф, •ф, V обозначения итерационных функций 11 (рп,, семейство итерационных функций, порож- даемых обратной интерполяцией 56 0,t,s семейство итерационных функций, порож- даемых прямой интерполяцией 62 •фд, f, семейство итерационных функций, порож- даемых рациональными аппроксимациями^, 74 Qn,s(t) интерполяционный многочлен для обратной функции 9~ 53 г =s(ra+l) 18 R =5(га+1) 91 .-? р,, / (т) ё^\ (x, f, т) = х — Z р,,, (m) Z/ (x, ^,1) 106 s количество элементов информации, вычис- ляемых итерационной функцией в одной точке 18 S =s-l 91 S[, числа Стирлинга первого рода 108 oi, i (т) Wi (x, f, m) = Z OL / (т} Z, (x, f, 1) 107 Tt,/ числа Стирлинга второго рода 108 т,,, Е,(х)=^^1,Лх-а)1 84 и(х} =f(x)/f/(x) 12 V(x) =[ф(x)-a]/(x-a)p 27 W{x) == [(p (x) - а]/цР (х) 28 ^ Г/(;с, /, m)=Zi{x, f1"", 1) 106 л:, приближение к к 11 У /,) __ (_1)/-1^(/>(у) y/w - Л^'^^ ^f(.) 13 г,(^) =к/(^)и/^) 71 ^/i... ^ == знак приближенного равенства чисел 13 ~ знак эквивалентности роста переменных ве- личин 13 {х\р(х)} множество значений х, для которых выпол- няется условие р(х} 14 ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ Абстрактное пространство 9, 239 Алгоритм бисекции 11 — итерационный 9, 12 Алгоритмика 9 Аппроксимация Es рациональная 74— 76 — матрицы Якоби 186 210 — производной 91,94,145—149,203— 210 — — погрешность 205—210 — — при помощи многочлена Лаг- ранжа — Эрмита 204—205 ————— Ньютона 203—205 — — примеры 97—99, 203—204 Асимптотики погрешности константа см. Константа асимптотики погреш- ности Асимптотические свойства решений разностных уравнений 46—52 Базовая последовательность 18,66,77 Биномиальный коэффициент 35, 104, 133, 136 — — восходящий 108 — — нисходящий 108 Бирмана ряд 69 Бпсекции алгоритм 11 Бэйли метод см. Ламберта метод Вандермонда определитель 40 Векторные итерационные функции см. Итерационные функции вектор- ные Верные цифры 25, 213—216 Вычислительная эффективность 17, 212—216 Геометрическая интерпретация итера- ционных функций 135, 142, 149, 150 Гиперкасательная интерполяции 52, 200 Декарта правило знаков 42 Задача интерполяции 195—199 — о неподвижной точке 19—21 Интерполлционная формула Лагран- жа — Эрмита см. Интерполяцион- ный многочлен Лагранжа — Эрмита — — Ньютона см. Интерполяцион- ный многочлен Ньютона Интерполяционные итерационные функции см. Итерационные функции интерполя- ционные Интерполяционный многочлен 54—56, 170, 196 — — Лагранжа—Эрмита 88, 170, 173, 196, 198, 201, 204—205 — — Ньютона 64, 88, 89, 170—173, 196, 198, 200, 203 — — Тейлора 132 Интерполяция 52—54, 132—135, 195— 210 — в случае стандартной информа- ции 200—202 — гиперкасательная 52, 200 — обратная 53, 172—173, 196 — прямая 52—53, 170—171, 195 Информация 9, 11, 14, 15, 17, 99— 101, 129 — новая 14, 129 — ранее вычисленная 14, 87, 88 — стандартная 55, 200, 201 Итерационная функция (ИФ). См. также Итерационные функции 11 — — метода Ньютона — метода се- кущих 146, 149, 150, 193, 231 — — — секущих 12, 14, 17, 63—65, 76, 89, 90, 91, 101, 146, 152, 189, 214, 229 — — Мюллера 171, 190 258 — — неизмеримого порядка 125— 128, 192 — — Ньютона 12, 14, 17, 23, 29, 64 102, 135, 147, 149, 151, 188, 19L 192, 214, 222, 223 — — Ньютона— Рафсона см. Итера- ционная функция Ньютона — — Островского 150 — — Стеффенсона — Хаусхолдера — Островского 220—221 — — Хэлли 34, 76, 79, 147, 189, 191 — — — разностный аналог 172 Итерационное исчисление 28—36, 135 Итерационные функции. См. также Итерационная функция 12, 14 — — векторные 12, 14, 177—187, 234—238 — — — не используюцгие значений производных 186—187 — — высокого порядка 24—26 — — генерируемые рекуррентно 135—145 — — для кратных корней 102—128, 169 — — — решения систем уравнений 177—178 — — интерполяционные 54—65, 87— 89, 117—122 — — классификация 14—15 — — многоточечные 14, 129—150, 175, 231—234 — — — порождаемые аппроксима- цией производной 145—149 — — — — суперпозицией 149—150 — — — с памятью 15, 150—152, 173, 186—187, 194 — — не использующие всю ранее вычисленную информацию 100—101 — — — — значений производных 165—173 — — одноточечные 14, 63, 66—86, 129, 188, 189, 222—227 — — — с памятью 14, 87—101, 122— 124, 189—191, 225—227 — — — — — порождаемые аппрок- симацией производной 90—99 — — оптимальные 18, 81 Предметный указатель — — порождаемые обратной интер- поляцией 57—64, 90, 172—173 , — — — прямой интерполяцией 54— 57, 64—65, 117—122, 170—172 — — составные 29 ИФ см. Итерационная функция Классификация итерационных функ- ций 14—15 Константа асимптотики погрешности 15, 27 — — — векторной итерационной функции 177 — — — — — — Ньютона 180 — — — вычисление 31—32, 72—73 — — — Е, 68 — — — — в случае кратных нулей 103 — — — интерполяционной итера- ционной функции 54—65 . — — — итерационной функции, по- рождаемой аппроксимацией произ- водной 93—98 — — — многоточечной ИФ второго типа 155—160 — — — — — первого типа 160—165 — — — рациональных аппроксима- ций Es 74—76 — — — рекуррентно генерируемых ИФ 141—143, 145 Корень квадратный 69, 82 — кратный 82, 191, 102—128 — уравнения 10 — характеристического уравнения 37, 38, 42, 49, 118—120 Кратный нуль 11, 26, 27 Кронекера символ 40, 177 Лагранжа — Эрмита интерполяцион- ный многочлен см. Интерполяцион- ный многочлен Лагранжа — Эрмита Лидстона ряд 239 Линейная сходимость 22, 217—218,222 Липшица условие 20, 21 — — сжимающее 20 Лопиталя правило 31 Предметный указатель Метод Бэйли 76 — касательных гипербол 76 — Лагерра 239 — Ламберта 76 Многоточечные итерационные функ- ции см. Итерационные функции многоточечные Монотонная сходимость 60, 65, 79, 172 Мюллера итерационная функция 171, 190 Начальное приближение 12, 61, 100, 238 Неподвижная точка 19—21, 78, 171, 220 Нормированные коэффициенты ряда Тейлора 13 — — — — для обратной функции 13 Нуль кратный 11, 26, 27 — простой 11, 27, 82 Ньютона итерационная функция см. Итерационная функция Ньютона Ньютона — Рафсона итерационная функция см. Итерационная функ- ция Ньютона Ньютона — Херона формула 69 Ньютоново отображение 134, 135, 164 Обратная функция 10, 53, 67, 196 Объем информационного запроса 17, 18, 80, 87 Одноточечные итерационные функции см. Итерационные функции одното- чечные Оператор восходящей разности 72 Оптимальная базовая последователь- ность 18, 68, 106 — итерационная функция см. Итера- ционные функции оптимальные Островского итерационная функция 150 Паде таблицы 74, 75 Погрешность аппроксимации нуля 11, 13 — — производной 205—210 — интерполяции 199, 200 259 Понижение степени алгебраического уравнения 79—80, 172 Порядок итерационной функции 15— 17, 23—25, 27—35, 81—82, 124— 129, 176—177 — — — векторной 176—183 — зависимый от кратности 16 — квадратичный 16 — линейный 16, 103 — независимый от кратности 16, 81 — неизмеримый 125—126, 192 — целый 176 Присоединенная функция 107 Производящая функция 108 Разделенная разность 197, 198 Разностное уравнение 37—42, 47—51 — — асимптотические свойства реше- ний 47—51 — — второго рода 50—51 — — неоднородное 38, 42 — — однородное с постоянными ко- эффициентами 37 — — первого рода 47—49 Рекуррентное построение итерацион- ных функций 141 Решение уравнения 10 Ролля обобщенная теорема 206 Рунге — Кутты система 130, 163 Ряд Бирмана 69 — для погрешности Es 82—86 — — — <Г, 114—117 — Лидстона 239 — Тейлора см. Тейлора ряд Сжимающее условие Липшица 20 Системы уравнений 174—187, 194, 234—237 Сравнения теоремы 30—33, 86—87 Стеффенсона — Хаусхолдера — Ост' ровского ИФ 26, 220 Стирлинга числа 105, 108 Стоимость вычислений 214 — — значений производных 215 Сходимость геометрическая 218 — к неподвижной точке 20—21 260 Предметный укаэчтель — квадратичная, численные примеры 223 — линейная 22, 217—218, 222 — монотонная 60, 65, 79, 172 — решений разностных неравенств 36, 37 — — — уравнений 40—42 — сверхлинейная 23—24 Тейлора ряд 27, 137, 176, 177 Тестовые функции 166, 183—186 Точка отталкивания 22 — притяжения 22 Уравнение алгебраическое 10, 238, 239 — дифференциально-разностное 72, 103 — для погрешности итерационной функции в случае кратного корня 117—118, 120—121 — — — — — дополнительный член 101 — — — — — порождаемой аппрок- симацией производной 93—97 — — — — — — обратной интерпо- ляцией 56, 57 — — — — — — прямой интерполя- цией 60—63, 117—118 — комплексное 178 — разностное см. Разностное урав- нение — трансцендентное 10 — характеристическое 37, 38, 40, 42— 46, 118—120 — — корни 45—46, 118—120 Формулы для многоточечных итера- ционных функций 197, 204 — — Es 66 — — Ss 106, 113, 114, 116 — — j-и производной обратной функ- ции 259 — - У/ 71 — - ^.s{m) 117 — - v, 83 — — co;(w) 115 — — ^>а, ь 75 — — pi,/ 110, 114 — — 6;,/ 110, 113 — - т/,, 84 Фортран 221 Функционал 12, 15 Функция итерационная см. Итера ционная функция . — обратная 10 Фурье условия 60 — — обобщенные 68 Характеристическое уравнение 37, 38, 40, 42—46, 118—120 — — корни 45—46, 118—120 Хаттона метод см. Ламберта метод Хэлли итерационная функция см. Ите- рационная функция Хэлли Чебышёва невязка 239 Чезаро метод 86 Шредера формула 69, 138 Эйткена б^преобразование 105, 132, 143, 217—219 — б^формула см. Эйткена б^преоб- разование Экстраполяционная процедура 143 Эффективности индекс 17, 215 Эффективность вычислительная 17, 213-216 — использования информации 17, 25, 81, 87, 129, 213 — — — многоточечными итерацион- ными функциями 130 — — — одноточечными итерацион- ными функциями 87, 88, 129 — — — — — — с памятью 87, 129 Якоби матрица 175, 177, 178, 183, 186 — — обратная 178, 183, 186 Якобиан 175 ОГЛАВЛЕНИЕ От редактора перевода ................... 5 Предисловие к русскому изданию ............... 6 Предисловие ....................... 7 Глава 1. Предварительные сведения ..... .......... 9 1.1. Введение . ................... 9 1.2. Основные понятия и обозначения .......... 10 Глава 2. Общие теоремы об итерационных функциях . . ...... 19 2.1. Решение задачи о неподвижной точке ......... 19 2.2. Линейная и сверхлинейная сходимость ........ 21 2.3. Итерационное исчисление ............ 26 Глава 3. Математика разностных отношений .... ....... 36 3.1. О сходимости решений разностных неравенств ..... 36 3.2. Теорема о решениях некоторых неоднородных разностных уравнений . ................... 37 3.3. О корнях некоторых характеристических уравнений ... 42 3.4. Асимптотические свойства решений некоторых разностных уравнений ................... 46 Глава 4. Интерполяционные итерационные функции . . ...... 52 4.1. Интерполяция и решение уравнений ......... 52 4.2. Порядок интерполяционных итерационных функций ... 54 4.3. Примеры . ................... 63 Глава 5. Одноточечные итерационные функции ... ....... 66 5.1. Базовая последовательность Es ........... 66 5.2. Рациональные аппроксимации Es • • • ........ 74 5.3. Базовая последовательность итерационных функций, поро- ждаемых прямой интерполяцией ........... 77 5.4. Основная теорема об одноточечных итерационных функциях 80 5.5. Коэффициенты рядов для погрешностей итерационных функций Es ................... 82 Глава 6. Одноточечные итерационные функции с памятью . .... 87 6.1. Интерполяционные итерационные функции ....... 87 6.2. Одноточечные итерационные функции с памятью, порождае- мые аппроксимацией производной .......... 90 6.3. Обсуждение одноточечных итерационных функций с па- мятью . .................... 99 Глава 7. Кратные корни ..... .............. 102 7.1. Введение . ................... 102 7.2. Порядок итерационных функций Ег ........ 103 7.3. Базовая последовательность {Ss} .......... 105 7.4. Коэффициенты рядов для погрешностей итерационных функций Ss .................. 114 262 Оглавление 7.5. Итерационные функции, порождаемые прямой интерполя- цией . ..................... 117 7.6. Одноточечные итерационные функции с памятью . . . .122 7.7. Некоторые общие результаты ............ 124 7.8. Итерационная функция неизмеримого порядка ..... 125 Глава 8. Многоточечные итерационные функции ... ....... 129 8.1. Преимущества многоточечных итерационных функций . . .129 8.2. Одна задача интерполяции ............. 132 8.3. Рекуррентно генерируемые итерационные функции . . . .135 8.4. Многоточечные итерационные функции, порождаемые аппро- ксимацией производной .............. 145 8.5. Многоточечные итерационные функции, порождаемые супер- позицией . ................... 149 8.6. Многоточечные итерационные функции с памятью .... 150 Глава 9. Многоточечные итерационные функции. Продолжение .... 153 9.1. Введение . .................... 153 9.2. Многоточечные итерационные функции первого типа . . .154 9.3. Многоточечные итерационные функции второго типа . . . 160 9.4. Обсуждение критериев выбора итерационной функции . .165 Глава 10, Итерационные функции, не использующие значений производ- ных ........ ................ 169 10.1. Введение . ..........'......... 169 10.2. Интерполяционные итерационные функции ....... 170 10.3. Некоторые другие итерационные функции ....... 173 Глава 11. Системы уравнений ...... ............ 174 11.1. Введение . ................... 174 11.2. Построение векторных итерационных функций при помощи обратной интерполяции .............. 177 11.3. Оценки погрешностей некоторых векторных итерационных функций . ................... 178 11.4. Векторные итерационные функции, не использующие зна- чений производных ................ 186 Глава 12. Перечень итерационных функций ... ......... 188 12.1. Введение . ................... 188 12.2. Одноточечные итерационные функции ......... 188 12.3. Одноточечные итерационные функции с памятью .... 189 12.4. Кратные корни . ................. 191 12.5. Многоточечные итерационные функции ... . . . . . .192 12.6. Многоточечные итерационные функции с памятью . . . 194 12.7. Системы уравнений ................ 194 Приложение А. Интерполяция .................. 195 A.I. Введение . ................... 195 А.2. Задача интерполяции и ее решение .......... 196 А.З. Случай совпадающей информации .......... 200 А.4. Аппроксимация производных ........ .... 203 А.5. Погрешность аппроксимации производных ....... 205 Приложение В. О /-и производной обратной функции . . ..... 211 Приложение С, Верные цифры и вычислительная эффективность, . . . 213 Оглавление 263 Приложение D. Ускорение сходимости ... .......... 217 D.I. Введение . ................... 217 D.2. б^преобразование Эйткена ............. 217 D.3. Итерационная функция Стеффенсона — Хаусхолдера — Островского . .................. 220 Приложение Е. Численные примеры ... ............ 221 E.I. Введение . ................... 221 Е.2. Увеличение количества верных цифр ......... 222 Е.З. Одноточечные итерационные функции и одноточечные ите- рационные функции с памятью ........... 223 Е.4. Кратные корни ................. 228 Е.5. Многоточечные итерационные функции ........ 231 Е.6. Системы уравнений ................ 234 Приложение F. Направления дальнейших исследований . ...... 238 Литература . ....................... 240 Указатель обозначений . . . . ............... 255 Предметный указатель . . . . . .............. 257 Джо Трауб «ИТЕРАЦИОННЫЕ МЕТОДЫ РЕШЕНИЯ УРАВНЕНИЙ» Ст. научи, редактор И. А. Маховая Мл. научн. редактор Л. А. Королева Художник Б. П. Кузнецов Художественный редактор В. И. Шаповалов Технические редакторы И. И. Володина, Л. П. Бирюкова Корректор Н. В. Андреева ИБ № 5103 Сдано в набор 24.09.84. Подписано к печати 08.04.85. Формат 60Х90'/,а. Бумага кн.-журн. Печать высокая. Гарнитура литературная. Объем 8,25 бум. л. Усл. печ. л. 16,50. Усл. кр.-отт. 16,50. Уч.-изд. л."15,11. Изд. № 1/3793. Тираж 10000 экз. Зак. № 367. Цена 1 р. 40 к . ИЗДАТЕЛЬСТВО «МИР» 129820, ГСП, Москва, И-110, 1-й Рижский пер., 2. Ленинградская типография № 2 головное предприятие ордена Трудового Красного Зна- мени Ленинградского объединения «Техническая книгам им. Евгении Соколовой Союз- полиграфпрома при Государственном комитете СССР по делам издательств, полиграфии и книжной торговли. 198052, г. Ленинград, Л-52, Измайловский проспект, 29. Имеется в продаже книга издательства «Мир» X. Трибель ТЕОРИЯ ИНТЕРПОЛЯЦИИ, ФУНКЦИОНАЛЬНЫЕ ПРОСТРАНСТВА, ДИФФЕРЕНЦИАЛЬНЫЕ ОПЕРАТОРЫ Пер. с англ., 1980, 39 л., 3 р. 50 к. Обстоятельное изложение широкого круга вопросов теории пространств дифференцируемых функций с единой точки зрения, основанной на теории интерполяции. Много внимания уделено приложениям к краевым задачам для линейных уравнений, как в классической ситуации, так и в случае вы- рождения соответствующего оператора на границе. Значительная часть ма- териала содержалась ранее только в журнальных статьях, в том числе в ра- ботах автора, внесшего большой вклад в данную область исследований. X. Трибелем дано единое, достаточно полное и содержащее новые подхо- ды изложение самой теории интерполяции и новых областей ее приложений. Впервые систематически изложена теория пространств дифференцируемых функций с точки зрения теории интерполяции. Актуальность и полезность книги подчеркиваются тем обстоятельством, что в 1979 г. в ГДР вышло ее 2-е, стереотипное издание. Четкость и обстоя- тельность, отличающие сталь X. Трибеля, выдержаны на протяжении всей книги и, несомненно, доставят удовольствие читателю. Изложение постоянно сопровождается исчерпывающими замечаниями исторического, обзорного и справочного характера и снабжено обширной библиографией (около 800 наи- менований). Оглавление: 1. Теория интерполяции в банаховых пространствах. 2. Не- весовые пространства Лебега—Бесова в /?, и R\. 3. Весовые пространства Лебега — Бесова в областях. 4. Невесовые пространства Лебега — Бесова в областях. 5. Регулярные эллиптические дифференциальные операторы. 6. Сильно вырождающиеся эллиптические дифференциальные операторы. 7. Дифференциальные операторы Лежандра и Трикоми. 8. Ядерные фукцио- нальные пространства. Книга представляет интерес для специалистов по теории функций, функ- циональному анализу, уравнениям с частными производными. Она доступна студентам-математикам старших курсов университетов. Эту книгу Вы можете приобрести в магазинах книготоргов, распростра- няющих научно-техническую литературу. Если в ближайшем от Вас магазине ее не окажется, заказ можно направить по адресу: 121019 Москва, просп. Калинина, 26, п/я 42, магазин № 200 «Москов- ский Дом книги». 103050 Москва, ул. Петровка, 15, магазин 8 «Техническая книга». 117334 Москва, Ленинский проспект, 40, магазин ,№ 115 «Дом научно- технической книги». 191040 Ленинград, Пушкинская ул., 2, магазин № 5 «Техническая книга». Книга будет выслана наложенным платежом (без задатка)