Бабенко - Основы численного анализа

К. И. БАБЕ11КО ОСНОВЫ ЧИСЛЕННОГО АНАЛИЗА Издание второе, исправленное и дополненное, под редакцией А. Д. Брюно РйС Москва ° Ижевск 2002 УДК 819.0 ББК 22 19 Б 12 Интернет-магазин ° физика ° математика ° биологии ° техника ЫФр:,~~вЬор.гсг1.гп Издание осуществлено при финансовой поддержке Российского фонда фундаментальных исследований по проекту ~1а00-01-14090. Бабенко К. И.

Основы численного анализа. Москва-Ижевск: НИЦ «Регулярная и хаотическая динамика», 2002, 848 стр. Книга написана на основе курса лекций, читавшегося в течении многих лет на механико-математическом факультете Московского государственного университета. В ней содержатся» еоретнческое обоснование н подробное изложение основ численных методов. Каждая глава и почти все параграфы сопровождаются большим числом задач и примеров как теоретического, так и прикладного характера.

Для студентов н аспирантов математических специальностей университетов, а также для научных работников в области прикладной математики. ББК 22.19 1ЯВ1ч 5-93972-162-1 © Г. П. Бабенко, 2002 © НИЦ «Регулярная и хаотическая динамика», 2002 Ы1р:О'гсс1.гп Оглавление Предисловие ко второму изданию Предисловие 13 13 Гл.лвл 2. Математические основы численного анализа . 3 1. Теоремы топологии и функционального анализа 3 2.

Теоремы анализа 33. Ортогонавьные системы в гильбертовых пространствах. Специальные функции 34. Уравнения в конечных разностях и смежные вопросы... 35. Численный пример на метод Ньютона о5 5о 96 11 150 Гллвл 3. Элементы теории приближений 3 1. Некоторые вопросы тоории приближений э 2.

Поперечники компактов 3 3. Интерполяция Ц4. Интерполяциоипый многочлен в форме Ньзотона, ленные разности . э 5. Интерполяция функций многих переменных 3 6. Сплайн-интерполяция э'7. Оценки поперечников . 157 157 194 211 226 234 239 256 Разде- Гллвл 4. Теория табулирования и е-энтропия 3 1. Таблицы функций 3 2. г-энтропия компактов . 3 3.

Табулирование классов аналитических функций и е-энтропия этих классов . 3 4. Табулирование и я-энтропия функции конечной гладкости 3 5. Некоторые практические вопросы работы с таблицами 272 272 275 280 294 301 Гллвл 1. Постановка задач численного анализа. Элементы теории вычислительных алгоритмов . 3 1. Постановка задач численного анализа 3 2. Представление чисел в ЭВМ и анализ погрешностей округления 3 3. Несколько замечаний о понятии алгоритма 3 4. Примеры алгоритмов; анализ алгоритмов.......... Оглавление 312 312 314 333 356 1'.плвл 7. 'Численное решение задачи Коши для обыкновенных дифференциальных уравнений.............

420 420 429 Гплвл 8. Теория итераций и методы решения некоторых задач алгебры . 450 3 5. Итерационные методы репюпия систем линейных уравнений491 3 6. Решение нелинейных уравнений и систем уравнений.... 516 37. Методы решения алгебраической проблемы собственных значений Глава 9. Численное решение краевых задач для дифференциальных уравнений и задач на собственные зна ~ения . 548 3 1.

Общие вопросы теории краевых задач............ 548 568 580 619 638 657 663 Глава 5. Общие свойства вычислительных алгоритмов 3 1. Алгоритмы для приближенного вычисления отображения А:Х- ° У 3 2. Анализ некоторых вычислительных алгоритмов з 3.

Решение некоторых некорректных задач . 3 4. Решение задачи Рэлея — Тейлора . Глана 6. Численное интегрирование 3 1. Общие вопросы теории квадратурпых формул 3 2. Квадратурные формулы интерполяционного типа 33. Оценка погрешности квадратурной формулы на классе 14" (М: 1) 3 4. Составные квадратурные формулы; интегрирование периодических функций.

Сингулярные интегралы .. 3 5. Кубатурные формулы 31. Методы Эйлера и Рунге -Кутта . з 2. Разностные мотоды решения задачи Коши 3 3. Несколько замечаний о численном решении задачи Коши в экстремальных случаях. 3 1. Общие замечания о вычислительных задачах алгебры .. 3 2. Решение линейных алгебраических уравнений методом исключения; вычисление определителей и обратных матриц '3 3.

Итерационное уточнение решения системы линейных урав ненни и элементов обратной матрицы 34. Замечания о решении вырожденных систем уравнений 3 2. Построение разностных аппроксимапий дифференциальных операторов '3 3. О решении краевых задач методом прогонки........ 3 4. О решении краевых задач методом конечных элементов 3 5. Построение алгоритмов без насыщения для решения краевых задач з 6.

О решении задачи на собственные значения .. з 7. О доказательных вычислениях 3 8. Некоторые заключительные замечания 367 367 373 38о 389 403 450 466 476 483 5 Оглавлеяие Глава 10. Некоторые вопросы численного решения краевых задач для уравнений в частных производных....... 665 ~1. О численном решении краевых задач для эллиптических уравнений . 665 э 2. Вариациониые методы решения краевых задач....... 687 я 3.

Несколько замечаний о построении алгоритмов без иасыщепия 733 з 4. О решении краевых задач для эволюционных уравнений . 7о3 3 5. Метод установления 797 Заклитчение. 807 809 Комментарии 816 Литература 834 Список печатнь|х работ К. И. Бабенко . 836 Предметный указатель Предисловие ко второму изданию Во времена холодной войны СШЛ в сотни раз превосходили СССР по мощности компьютеров. Однако, выход вычислительной продукции для нужд науки и техники был примерно одинаковым благодаря превосходству СССР в теории и практике вычислительной математики, что позволяло испгщьзовать компьютеры во столько же раз эффективнее. Эти наивысшие достижения вычислительной математики изложены в этой книге, совмещающей учебник с монографией и трактующей численные методы как глубокую и содержательную математику.

Многие методы, излогкенные в книге (особенно алгоритмы без насыщения)., до сих пор неизвестны на западе и остаются актуальными, ибо всегда имеются задачи, требующие максимального использования всех возможностей компьютера. В книге часто упоминается ЭВМ БЭСМ-6, которая была примерно эквивалентна РС ЛТ-386 с частотой 16 МГЦ.

В настоящем переиздании исправлены опечатки и неточности первого издания, даны комментарии, добавлена литература, даны названия пунктам, окончания доказательств и примеров отмечены знаком Ц а задач -- ° . Кроме того, дополнен список печатных работ К.И.Бабенко. Все это сделано коллективом редакторов, ответственных за определенные участки книги. А именно: предисловие и гл.

1 -- А. Д. Брюно: гл. 2 -- В. М. Тихомиров; гл. 3 — М. Б. Гавриков; гл 4 и 5 Л. Х. Пергамент; гл. 6 —. В. Н. Белых и Р. 3. Даутов; гл. 7 —. С. С. Филиппов и Р. 3. Даутов; гл. 8 -- А. Л. Афендпков: гл. 9 Л. Р. Волевич Я 1), И. Л. Софро|юя Я 2 и 4), Ю. Б. Радвогип Я 3), В. П. Варин Я5), А.Д.Брюно Яб) и А.Л.Лфендиков Я7 и 8), а также А. В. Забродин; гл. 10 1. Р.

Волевич Я 1 и 2), В. П. Варин Я 3) и Ю.Б.Радвогин Я4 и 5); литература В.Ю.Петрович. Кроме того, В. И, Лебедев, В. И. Парусников и А. И. Аптекарев помогли своими замечаниями. Переиздание осуществлено при финансовой поддержке Российского фонда фун,чаментальных исследований, проект 00-01-14090. О всех замечаниях, предложениях и пожеланиях относительно этого издания прошу сообщать мне по е-п1а11: Ьгпповврр.1ге16уэ1ьгп А.Д.

Брюно Москва, апрель 2001 г. Предисловие 1. Специфика книги. В течение 13 лет автор читал на механико-математическом факультете МГУ годичный курс «Основы методов вычнсленийм Почти 30 лет автор занимается практической деятельностью в области численного анализа, Продумывание различных вопросов численного анализа как в процессе практической деятельности по решению на ЭВМ задач механики сплопшой среды, так н в процессе преподавания способствовало выработке представлений автора на предмет численного анализа и на его место в современной математике и естествознании.

Эти взгляды автора нашли отражение в предлагаемой книге. Построение нашего курса основ численного анализа нетрадиционно. В разделах численного анализа, посвященных решению краевых задач для дифференциальных (псевдодифференциальных) уравнений, решению функциональных и интегральных уравнений и т. и., огромное значение имеют вопросы дискретизации элементов функциональных компактов.

В самом деле, когда мы строим численный метод решения какой-лнбо краевой задачи, а затем па его основе конструируем алгоритм (программу для ЭВЫ), то можем решить пе одну задачу для конкретных исходных данных, а серию однотипных задач. в чем и выражается массовость алгоритма. 11о мы получим алгоритм лишь при усювни, что исходные данные являются не элементами щ>оизвольного множества, а элементами некоторого компакта. Поэтому вопросы дискретизации функциональных компактов имеют в численном анализе первостепенное значение. От принятого способа дискретизации компактов данных и результатов зависит эффективность алгоритма, а точнее его оптимальная временная сложность при заданной величине погрешности.

Процесс дискретизации двухступенчатый: вначале мы переходим от бесконечномерных компактов, образованных возможнымн входными данными задачи и возможными решениями задачи, к конечномерпым компактам, т. е., как правило, к компактам в К~ (и ( ос); затем кодируем элементы компактов из К", т.е, наборы п вещественных параметров, с помощьк> конечного числа битов. Второй этап дискретизации имеется во всех задачах численного анализа, потому что он сводится к машинному представлению тех об ьектов, с которыми мы оперируем. Известно, какие эффекты могут при этом проистекать н сколь скрупулезно нужно подходить к вопросам интерпретации результатов, полученных на ЭВМ. Эффективность способа дискретизации, принятого на первом этапе, характеризуется величиной соответствующего поперечника. Поэтому в курсе рассмотрены вопросы о поперечниках различного типа, выделен один из ннх, характеризующий наиболее оптимальный способ дискретизации, и изучена асимптотика поперечников наиболее важных функциональных компактов.

Переход к машинному представлению величин Првдислоьве и способ принятого табулирования элементов функциональных компактов имеют количественные характеристики в виде .-энтропии и -емкости. Став на почву фипитности, мы уже можем связать такие характеристики численного алгоритма, как объем данных (на входе в алгоритм) и величина погрешности. Эта связь устанавливается с помошью е-энтропии, .и при этом часто получаются оценки для временной сложности алгоритма. Понятно, что вопросы дискретизации функциональных компактов это вопросы теории приближений, и, стало быть, она, по существу, является тем фундаментом, на котором покоятся разделы численного анализа, посвященные решению краевых задач. Традиционно в курсах численных методов теории приближения фу.нкций уделяется мало внимания, в настоящей книге сделана попытка исправить этот дефект. Сколько-нибудь содержательное построение основ численного анализа невозможно без понятии яалгорятм» и «вычислимость».