ББК 22.19 БЗО УДК 519.6^075.8) Бахвалов Н. С., Жидков Н. П., Кобельков Г. М. Численные методы: Учеб. пособие.—М.: Наука. Гл. ред. физ.-мат. лит., 1987.—600 с. Написана на основе программы курса численных методов для матема« тических специальностей университетов, отработанной в содружестве педа- гогических коллективов Московского и Братиславского (ЧССР) университетов. Методически последовательное изложение численных методов решения задач на ЭВМ содержит, как правило, их строгое теоретическое обоснование. Наряду с этим подробно определена степень практической применимости ме- тодов при решении различных классов прикладных задач. Существенное вни- мание уделено проблеме отбора и оптимизации алгоритмов, закладываемых в основу стандартных программ решения задач. Для студентов математических факультетов университетов, факультетов прикладной математики, а также для аспирантов и научных работников, свя- занных с решением задач на ЭВМ. Табл. 2. Ил. 70. Рецензенты: кафедра вычислительной математики Ленинградского государственного университета; кандидат физико-математических наук В, Г, Сушко 1702070000—140 g 053 (02)-87 Издательство «Наум». Главная редакция физико-математической литература, 1987 ОГЛАВЛЕНИЕ Предисловие ...... .................. 7 Введение ........ .................. 9 Глава 1. Погрешность результата численного решения задачи ... 17 § 1. Источники и классификация погрешности ......... 17 § 2. Запись чисел в ЭВМ ............... 21 § 3 Абсолютная и относительная погрешности. Формы записи дан- ных . ............... 22 § 4. О вычислительной погрешности ............ 24 § 5. Погрешность функции . ............... 26 § 6. Обратная задача . .................31 Глава 11 Интерполяция и численное дифференцирование . • ... 34 § 1. Постановка задачи приближения функций ....,.., 35 § 2. Интерполяционный многочлен Лагранжа ......... 38 § 3. Оценка остаточного члена интерполяционного многочлена Ла- гранжа . ................... 42 § 4. Разделенные разности и их свойства .......... 42 § 5. Интерполяционная формула Ньютона с разделенными разно- стями . ..................... 44 § 6. Разделенные разности и интерполирование с кратными узлами 47 § 7. Уравнения в конечных разностях ............ 50 § 8. Многочлены Чебышева . . ............. 56 § 9. Минимизация оценки остаточного члена интерполяционной формулы . .................... 60 § 10. Конечные разности . ................ 63 § 11. Интерполяционные формулы для таблиц с .постоянным шагом 66 § 12. Составление таблиц ................. 69 § 13. О погрешности округления при интерполяции ..,,,. 71 § 14. Применения аппарата интерполирования. Обратная интерпо- ляция . ..................... 72 § 15. Численное дифференцирование ............. 73 § 16. О вычислительной погрешности формул численного дифферен- цирования ..................... 80 § 17. Рациональная интерполяция .............. 82 Глава III. Численное интегрирование ..... ........ 83 § 1. Простейшие квадратурные формулы. Метод неопределенных коэффициентов . .................. 83 § 2. Оценки погрешности квадратуры ....»».•»,>. 86 § 3. Квадратурные формулы Ньютона—Котеса ...... i . 91 § 4. Ортогональные многочлены . ............. 96 § 5. Квадратурные формулы Гаусса ............ 102 § 6. Практическая оценка погрешности элементарных квадратурных формул . ..................... 109 § 7. Интегрирование быстро осциллирующих функций ..... 113 § 8. Повышение точности интегрирования за счет разбиения отрез- ка на равные части ........>...(,i.,116 Г 8 § 9. О постановках зада" оптимизации ........... 120 § 10. Постановка задачи оптимизации квадратур ... ... 125 § 11. Оптимизация распределения узлов квадратурной формулы . . 127 § 12. Примеры оптимизации распределения узлов ........ 133 § 13. Главный член погрешности . ........... 136 § 14. Правило Рунге практической оценки погрешности ..... 139 § 15. Уточнение результата интерполяцией более высокого порядка точности ....... ..... ... 144 § 16. Вычисление интегралов в нерегулярном случае . . . . 146 § 17. Принципы построения стандартных программ с автоматическим выбором шага . ........ ......... 153 Глава IV. Приближение функций и смежные вопросы . . ..... 160 § 1. Наилучшие приближения в линейном нормированном простран- стве .................. ... 160 § 2. Наилучшее приближение в гильбертовом пространстве и во- просы, возникающие при его практическом построении . . . 162 § 3. Тригонометрическая интерполяция. Дискретное преобразование Фурье . ..................... 166 § 4. Быстрое преобразование Фурье ............ 170 § 5. Наилучшее равномерное приближение .......... 173 § 6. Примеры наилучшего равномерного приближения .... . . 176 § 7. Итерационный метод построения многочлена наилучшего рав- номерного приближения . .............. 182 § 8. О форме записи многочлена .............. 184 § 9. О способах вычисления элементарных функций . . . ,' . .188 § 10. О скорости приближения функций различных классов . . . .194 § 11. Интерполяция и приближение сплайнами .... . . ... 191 § 12. Энтропия и 8-энтропия ................ 204 Глава V. Многомерные задачи ...... .......... 208 § 1. Метод неопределенных коэффициентов ... ....... 209 § 2. Метод наименьших квадратов и регуляризация ...... 210 § 3. Примеры регуляризации . .............. 213 § 4. Сведение многомерных задач к одномерным ......... 219 § 5. Интерполяция функций в треугольнике .......... 226 § 6. Оценка погрешности численного интегрирования на равномер- ной сетке . .................... 228 § 7. Оценка снизу погрешности численного интегрирования .... 231 § 8. Метод Монте-Карло ................. 238 § 9. Обсуждение правомерности использования недетерминирован- ных методов решения задач ............... 242 § 10. Ускорение сходимости метода Монте-Карло ........ 245 § 11. О выборе метода решения задачи ............ 249 Глава VI. Численные методы алгебры .... ......... 254 § 1. Методы последовательного исключения неизвестных ..... 257 § 2. Метод отражений .................. 265 § 3. Метод простой итерации ............... 269 § 4. Особенности реализации метода простой итерации на ЭВМ . . 271 § 5. б^процесс практической оценки погрешности и ускорения схо- димости ...................... 274 § 6. Оптимизация скорости сходимости итерационных процессов . . 277 § 7. Метод Зейделя ................... § 8. Метод наискорейшего градиентного спуска ..... ... 292 § 9. Метод сопряженных градиентов ............ 296 § 10. Итерационные методы с использованием спектрально-эквива- лентных операторов . ................ 299 § 11. Погрешность приближенного решения системы уравнений и об- условленность матриц. Регуляризация ......... 303 § 12. Проблема собственных значений ............ 309 § 13. Решение полной проблемы собственных значений при помощи Q.R-алгоритма . .................. 314 Глава VII. Решение систем нелинейных уравнений и задач оптимизации 317 § 1. Метод простой итерации и смежные вопросы ....... 319 § 2. Метод Ньютона решения нелинейных уравнений ...... 323 § 3. Методы спуска ................... 329 § 4. Другие методы сведения многомерных задач к задачам мень- шей размерности ................. 334 § 5. Решение стационарных задач путем установления ..... 337 § 6. Что оптимизировать? ................ 345 § 7. Как оптимизировать? ................ 349 Глава VIII. Численные методы решения задачи Коши для обыкновен- ных дифференциальных уравнений .... ..... 357 § 1. Решение задачи Коши с помощью формулы Тейлора .... 358 § 2. Методы Рунге—Кутта . . . . ............ 360 § 3. Методы с контролем погрешности на шаге ........ 365 § 4. Оценки погрешности одношаговых методов ........ 367 § 5. Конечно-разностные методы .............. 372 § 6. Метод неопределенных коэффициентов .......... 375 § 7. Исследование свойств конечно-разностных методов на модель- ных задачах .................... 379 § 8. Оценка погрешности конечно-разностных методов ..... 384 § 9. Особенности интегрирования систем уравнений ...... 392 § 10. Методы численного интегрирования уравнений второго поряд- ка ........................ 398 Глава IX. Численные методы решения краевых задач для обыкновен- ных дифференциальных уравнений .... ...... 403 § 1. Простейшие методы решения краевой задачи для уравнения второго порядка .................. 403 § 2. Функция Грина сеточной краевой задачи ......... 409 § 3. Решение простейшей краевой сеточной задачи . . . . . . .413 § 4. Замыкания вычислительных алгоритмов ......... 422 § 5. Обсуждение постановок краевых задач для линейных систем первого порядка .................. 429 § 6. Алгоритмы решения краевых задач для систем уравнений пер- вого порядка .,••.•.............. 434 § 7. Нелинейные краевые задачи .............. 438 § 8. Аппроксимации специального типа ........... 444 § 9. Конечно-разностные методы отыскания собственных значений 455 § 10. Оптимизация распределения узлов интегрирования ..... 458 § 11. Построение численных методов с помощью вариационных прин- ципов ....................... 461 § 12. Улучшение сходимости вариационных методов в нерегулярном случае . . ............ ........ 471 § 13. Влияние вычислительной погрешности в зависимости от формы записи конечно-разностного уравнения .......... ^73 Глава X. Методы решения уравнения в частных производных . . . 489 § 1. Основные понятия теории метода сеток ......... 481 § 2. Аппроксимация простейших гиперболических задач ..... 490 § 3. Принцип замороженных коэффициентов ......... 504 § 4. Численное решение нелинейных задач с разрывными решения- ми .....,..............;... 508 § 5. Разностные схемы для одномерного параболического уравнения 511 § 6. Разностная аппроксимация эллиптических уравнений .... 526 5 § 7. Решение параболических уравнений с несколькими простран- 548 ственными переменными § 8. Методы решения сеточных эллиптических уравнений .... 561 Глава XI. Численные методы решения интегральных уравнений . . 571 § 1. Решение интегральных уравнений методом замены интеграла квадратурной суммой ............. . 571 § 2. Решение интегральных уравнений с помощью замены ядра на вырожденное ................... 576 § 3. Интегральные уравнения Фредгольма первого рода ..... 580 Заключение .. ...... ................. 588 Список литературы ....... ............... 593 Предметный указатель ........................ 596 ПРЕДИСЛОВИЕ Настоящая книга написана на основе лекций, читавшихся авторами на механико-математическом факультете и на факуль- тете вычислительной математики и кибернетики МГУ. Она воз- никла в результате переработки и расширения учебного пособия «Численные методы», написанного одним из авторов. Как и всякое другое пособие по численным методам, эта книга содержит изложение основных положений теории, в дан- ном случае относящихся к приближению функций, интегрирова- нию, задачам алгебры и оптимизации, решению дифференциаль- ных и интегральных уравнений. Текущий период характерен бурным развитием вычислитель- ной техники; в частности, мощность парка ЭВМ возрастает на порядки в течение десятилетия. Это обстоятельство сопровож- дается усиленным применением ЭВМ и численных методов для решения резко расширяющегося круга задач. В результате про- исходит быстрое изменение взглядов на весь комплекс вопросов, связанных с применением ЭВМ, и требований к численным ме- тодам решения задач. В частности, в связи с вышесказанным нельзя предложить пособия по численным методам, содержа- щего рецепты решения всех возможных задач. При выборе ме- тода решения сложной конкретной задачи всякое пособие зача- стую играет роль лишь общего руководства, отталкиваясь от которого исследователь рассматривает свои проблемы. Работа, связанная с созданием и применением численных ме- тодов, складывается из чисто теоретических исследований мето- дов решения типичных задач, анализа работы алгоритмов при решении модельных задач, вычислительного эксперимента и ряда других моментов. Существенным моментом при построении и анализе методов решения задач является построение вычисли- тельной модели—простейшей задачи рассматриваемого класса, на примере которой можно провести теоретическое и экспери- ментальное исследование свойств метода. Большое значение имеют вопросы выбора направления исследования, построения математических моделей рассматриваемых явлений, организа- ции контактов с представителями других наук. В каждом конкретном случае эти проблемы приобретают свои оттенки и трудно дать какие-либо общие рекомендации, пригодные во всех случаях. Поэтому рассуждения авторов по затрагиваемым вопросам следует рассматривать не как руко- водство к действию, а просто как одну из возможных точек зрения. Эффект от применения ЭВМ и численных методов достигает- ся как в результате решения отдельных трудных задач, так и ва счет расширения круга пользователей ЭВМ путем предостав- ления им больших удобств. Для последней цели важно состав- ление стандартных программ решения типичных математических задач и состоящих из них пакетов и библиотек. Поэтому в рас- сматриваемой книге определенное внимание уделено также во- просам теории численных методов, возникающим при разра. ботке таких стандартных программ. Авторы признательны Т. Н. Галишниковои, И. П. Мысовских. В Г. Сушко, Е. Г. Дьяконову, В. Л. Мирошниченко за полезные обсуждения, способствовавшие улучшению рукописи, ВВЕДЕНИЕ Попытаемся определить место теории численных методов в системе других областей знаний и рассказать о проблемах, воз- никающих в связи с ее применением, прежде чем переходить к непосредственному ее изложению. Математика как наука возникла в связи с необходимостью решения практических задач: измерений на местности, навига- ции и т. д. Вследствие этого математика была численной мате- матикой, ее целью являлось получение решения в виде числа. Численное решение прикладных задач всегда интересовало математиков. Крупнейшие представители прошлого сочетали в своих исследованиях изучение, явлений природы, получение их математического описания, как иногда говорят, математической модели явления, и его исследование. Анализ усложненных моде- лей потребовал создания специальных, обычно численных ме- тодов решения задач. Названия некоторых из таких методов —' методы Ньютона, Эйлера, Лобачевского, Гаусса, Чебышева, Эр- мита — свидетельствуют о том, что их разработкой занимались крупнейшие ученые своего времени. Настоящее время характерно резким расширением приложе- ний математики, во многом связанным с созданием и развитием средств вычислительной техники. В результате появления ЭВМ с программным управлением менее чем за сорок лет скорость выполнения арифметических операций возросла от 0,1 операции в секунду при ручном счете до 107 операций на современных серийных ЭВМ, т. е. примерно в 108 раз. Рост возможностей в связи с созданием вычислительной тех- ники носит качественный характер и иногда сравнивается с про- мышленной революцией, вызванной изобретением паровой ма- шины. Уместно вспомнить, что в итоге промышленной револю- ции и последующего на протяжении двух веков развития науки и техники скорость передвижения возросла от скорости пеше- хода 6 км/ч до скорости космонавта 30000 км/ч, т. е. в 5000 раз. Распространенное мнение о всемогуществе современных ЭВМ часто порождает впечатление, что математики избавились почти от всех хлопот, связанных с численным решением задач, и раз- работка новых методов для их решения уже не столь существен- на. В действительности дело обстоит иначе, поскольку потребно- сти эволюции, как правило, ставят перед наукой задачи, нахо- дящиеся на грани ее возможностей.. Расширение возможностей приложения математики обусловило математизацию различных разделов науки: химии, экономики, биологии, геологии, геогра- фии, психологии, медицины, конкретных разделов техники и др. Процесс математизации состоит в построении математических моделей процессов и явлений и в разработке методов их иссле- дования. В физике или механике, например, построение математиче- ских моделей для описания различных явлений природы и изу- чение этих моделей с целью объяснения старых или предсказа- ния новых эффектов явлений являются традиционными. Однако в целом работа в этом направлении зачастую про- двигалась относительно медленно, поскольку обычно не удава< лось получить решение возникающих математических задач и приходилось ограничиваться рассмотрением простейших моде- лей. Применение ЭВМ и расширение математического образова- ния резко увеличило возможности построения и исследования математических моделей. Все чаще результаты расчетов позво- ляют обнаруживать и предсказывать ранее никогда не наблю- давшиеся явления; это дает основания говорить о математиче- ском эксперименте. В некоторых направлениях исследования до- верие к результатам численных расчетов так велико, что при расхождении между результатами расчетов и экспериментов в первую очередь ищут погрешность в результатах экспериментов. Современные успехи в решении таких важных для общества проблем, как атомные, космические, экономические, вряд ли были бы возможны без применения ЭВМ и численных методов. Требование численного решения новых задач привело к по- явлению большого количества новых методов. Наряду с этим последние тридцать-сорок лет происходило интенсивное теорети- ческое переосмысливание и старых методов, а также система- тизация всех методов. Эти теоретические исследования оказы- вают большую помощь при решении конкретных задач и играют существенную роль в наблюдаемом сейчас широком распростра- нении сферы приложений ЭВМ и математики вообще. Как уже отмечалось, с помощью современных ЭВМ удалось успешно решить ряд важных научно-технических задач. У не- посвященного человека может возникнуть превратное впечатле- ние, что успехи в применении ЭВМ обусловлены только повыше- нием их быстродействия. Реально дело обстоит иначе и сложнее. Правильнее будет сказать, что достижения в области исполь< зования ЭВМ обусловлены сочетанием ряда существенных фак- торов, без пропорционального развития которых они были бы много скромнее: 1) увеличение быстродействия ЭВМ, расширение памяти, со- вершенствование структуры ЭВМ и технических средств обще- ния с ними; 2) разработка программных средств общения с ЭВМ, вклю- чающая создание операционных систем, языков программирова- ния, библиотек и пакетов стандартных программ, создание но- 10 вых программных средств общения с ЭВМ, в частности, в диа- логовом режиме; 3) рост понимания процессов и явлений науки, техники, при- роды и общества и создание их математических моделей; 4) совершенствование методов решения традиционных мате- матических и прикладных задач и создание методов решения новых задач; б) рост понимания возможностей применения ЭВМ среди руководящих работников, ученых, инженеров и, вообще, широ- ких слоев общества; распространение так называемой компью- терной грамотности; координация усилий специалистов разного профиля по использованию вычислительной техники. Достижения, перечисленные в пп. 3), 5), позволяют ответить на вопрос, какие задачи следует решать с помощью ЭВМ, и ор- ганизовать их решение, в пп. 2), 4)—как их решать и в п. 1), 2)-^ дают для этого технические и программные средства. Просмотр методов решения сложных прикладных задач по- казывает, что, как правило, эффект, достигаемый за счет совер- шенствования численных методов, по порядку сравним с эффек- том, достигаемым за счет повышения производительности ЭВМ. Трудно сформулировать критерий, по которому можно было бы оценивать эффект применения новых численных методов, и еще труднее дать его достоверную количественную оценку. Все же, если сказать, что эффект от применения новых численных мето- дов при решении прикладных естественнонаучных задач дает 40 % общего эффекта, достигаемого за счет применения новой вычислительной техники и новых численных методов, то эта оценка не будет завышенной. Рассмотрим пример, иллюстрирующий это утверждение. Ре- шение дифференциальных уравнений в частных производных сводится к решению систем линейных алгебраических уравнений с матрицей, в каждой строке которой имеется 5—10 ненулевых элементов. Накануне появления ЭВМ такие системы уравнений решали в случае числа неизвестных порядка 10—102; сейчас не- редки случаи, когда решаются системы с числом неизвестных порядка 105 — 106. В гипотетическом случае решения этих задач на современных ЭВМ методами, известными тридцать лет назад, пришлось бы ограничиться системами уравнений с числом неиз- вестных порядка 103 — 104 (при тех же затратах времени ЭВМ). Конечность скорости распространения сигнала — 300 000 км/с — ставит уже сейчас существенное ограничение на возможный рост быстродействия однопроцессорных ЭВМ, поэтому значение даль- нейшего развития теории численных методов трудно переоце- нить. Быстрое проникновение математики во многие области зна- ния, в частности, объясняется тем, что математические модели и методы их исследования применимы сразу ко многим явле-i ниям, сходным по своей формальной структуре. Часто матема- тическая модель, описывающая какое-либо явление, появляется 11 при изучении других явлений или при абстрактных математиче- ских построениях задолго до конкретного рассмотрения данного явления. В частности, и в теории численных методов, так же как в «чистой» математике, полезна разработка общих построе- ний. Однако есть разница в подходе «чистого» и «прикладного» математика к решению какой-либо проблемы. На языке пер- вого понятие «решить задачу» означает доказать существова- ние решения и предложить процесс, сходящийся к решению. Сами по себе эти результаты полезны для прикладника, но, кроме этого, ему нужно, чтобы процесс получения приближения не требовал больших затрат, например времени или памяти ЭВМ. Ему важно не только то, что процесс сходится, но и то, как быстро он сходится. При численном решении задач возни- кают также новые вопросы, связанные с устойчивостью резуль- тата относительно возмущений исходных данных и округлений при вычислениях. Наряду с теорией численных методов период бурного разви- тия переживает и ряд других разделов математики, непосред- ственно обязанных ЭВМ своим возникновением. Применение численных методов и ЭВМ к решению естественнонаучных задач оказывает влияние и на традиционные разделы математики. Математика возникла и развивается как часть естествозна- ния, и долгое время ее развитие существенным образом опреде- лялось потребностями физики и механики. Требование матема- тизации новых разделов науки неизбежно приводит к обратному влиянию этих разделов на развитие математики и должно суще- ственно изменить лицо самой математики. Развитие как теоретических, так и прикладных разделов ма- тематики в конечном счете определяется потребностями обще- ства и его материальным вкладом в развитие науки, в частности в образование. Несколько десятилетий назад отношение вложе- ний в науку к общим вложениям в народное хозяйство состав- ляло доли процента. Теперь это отношение настолько велико, что его дальнейший существенный рост невозможен. Поэтому происходит перераспределение вложений в различные направле- ния науки. Это обуславливает еще один канал влияния приклад- ной стороны математики на развитие ее теоретических разде- лов. Прикладные исследования имеют непосредственную отдачу; это усиливает доверие общества к математике, расширяет пони- мание ее проблем и как следствие способствует увеличению вложения средств с целью ее развития. При реальной работе в области приложений математики воз- никает большое количество осложнений самого различного, за- частую нематематического характера. Хотя трудно надеяться, что какие-либо теоретические нраво- учения могут заменить собственный опыт работы, попытаемся обратить внимание на некоторые вопросы общего характера, важные для работы в области приложений математики. Прово- димая ниже систематизация этих вопросов является довольно 12 случайной, условной; по-видимому, можно предложить еще доб- рый десяток подобных классификаций, имеющих не меньшее право на существование. 1. Первостепенное значение имеет выбор направления иссле- дования. Свобода выбора обычно довольно невелика, так как основные контуры направления исследования обычно задаются «извне». При выборе направления исследования в пределах имею- щихся возможностей полезно иметь в виду следующее «правило трех частей», по своему внешнему виду похожее на шутку. Про- блемы делятся на: I—легкие, II—трудные. III—очень труд- ные. Проблемами I заниматься не стоит, они будут решены в ходе событий и без вашего вмешательства, проблемы III вряд ли удастся решить в настоящее время, поэтому стоит обратиться к проблемам II. 2. Нужно уметь сформулировать на языке математики конк- ретные задачи физики, механики, экономики, инженерные за- дачи и т. д., т. е. построить математическую модель рассматри- ваемого явления. В теоретической науке исследователь, умеющий правильно формулировать, как говорят, ставить, новые задачи, ценится выше, чем исследователь, умеющий решать кем-то поставленные задачи. Еще более возрастает роль таких ученых в прикладной науке. Начинающий работу математик часто жалуется на трудности контактов с представителями других наук, которые «даже» не могут сформулировать стоящих перед ними задач. Правильное формулирование задачи—это научная проблема, не менее слож- ная, чем само решение задачи, и не нужно надеяться, что кто-то другой целиком сделает это за вас. При постановке проблемы первостепенное внимание должно быть уделено выяснению цели исследования; принимаемая математическая модель явления не есть что-то однозначное, раз навсегда связанное с этим явле- нием, а зависит от цели исследования. Прежде чем выписывать дифференциальные уравнения, выбирать метод решения и обра- щаться к ЭВМ, стоит подумать, а не будут ли бесполезны все результаты вычислений? В то же время надо воспринимать как должное, что большая часть результатов вычислений будет вы- брошена сразу же после их получения. Дело в том, что произво- димая работа зачастую носит исследовательский характер и трудно заранее предсказать, что и в какой форме следует полу- чить, на каком пути нужно искать численное решение задачи. Цель исследования и описание проблемы обычно уточняются в процессе контактов представителей конкретных наук или руко- водства организаций (заказчиков) и математиков (исследовате- лей или исполнителей). 3. Успех в прикладной науке требует широкой математиче- ской подготовки, поскольку только такая подготовка может обеспечить приспособляемость к непрерывно меняющимся типам 13 задач, предъявляемых к решению. Одной из причин необходи- мости изучения на первый взгляд «бесполезных» для практики разделов математики является достижение более уверенного и более свободного владения «нужными» разделами математики. При построении и анализе математических моделей привычка математика «докапываться до конца», подвергать все сомне- нию, обусловленная его строгим математическим образованием, часто не менее важна, чем интуиция и соображения здравого смысла. Типичное для человека с математическим образованием стремление к общности охвата различных явлений часто помо- гает выделить наиболее существенные черты явления и отбро- сить второстепенные. 4. Не следует думать, что совершенное знание математики, численных методов и навыки работы с ЭВМ позволяют сразу решить любую прикладную математическую задачу. Во многих случаях требуется «доводка» методов, приспособление их к ре- шению конкретных задач. При этом типична обстановка, когда используются методы, применение которых теоретически не обосновано, или теоретические оценки погрешности численного метода неприемлемы для практического использования вслед- ствие их громоздкости; при выборе метода решения задачи и анализе результатов приходится полагаться на опыт предше- ствующего решения задач, на интуицию и сравнение с экспери- ментом и при этом приходится отвечать за достоверность ре- зультата. Поэтому для успеха в работе необходимы развитое неформальное мышление, умение рассуждать по аналогии, даю- щие основания ручаться за достоверность результата там, где с позиций логики и математики, вообще говоря, ручаться нельзя. В рассматриваемом вопросе есть и другая сторона. При чис- ленном решении конкретных трудных задач, возникающих в дру- гих областях знаний, математик зачастую действует как есте- ствоиспытатель, полагаясь во многом лишь на опыт и «правдо- подобные» рассуждения. Крайне желательно, чтобы такая эмпи- рическая работа подкреплялась теоретическими разработками методов, аккуратной проверкой качества методов на контроль- ных задачах с известным решением или частным сравнением с экспериментом. При длительном продвижении в каком-то на- правлении без такого подкрепления может теряться перспектива работы, уверенность в правильности получаемых результатов. Известное высказывание, что хороший теоретик может истолко- вать в желаемом направлении любые результаты как расчетов, так и эксперимента, содержит большую долю истины. 5. После завершения расчетов наступает этап использования результатов вычислений в практической деятельности, или, как часто говорят, этап внедрения результатов. Правильнее будет сказать, что подготовка к использованию результатов начинает- ся уже с анализа постановки задачи и в процессе ее решения и, по существу, все моменты решения задачи и внедрения не' 14 разрывно связаны между собой; в процессе формулирования задачи и ее решения заказчик и исполнитель взаимно уточняют постановку задачи и тем самым подготавливают почву для ее внедрения. Поскольку математика в сочетании с ЭВМ исполь- зуется в самых разнообразных областях, то часто приходится иметь дело с заказчиками, не имеющими опыта применения ЭВМ. В процессе контакта с такими «начинающими» заказчи- ками особенно важно преодолеть их первоначальное недоверие к вторжению математики в их области исследования; резуль- таты вычислений будут использоваться только тогда, когда за- казчик осмыслит их со своих позиций и убедится в том, что их действительно можно и нужно использовать. При правиль- ном подходе к взаимным контактам к концу процесса решения задачи «начинающий» заказчик приходит к пониманию, что ЭВМ и математика могут дать ему не все, но довольно много, а «начинающий» математик—к пониманию того, что он дает заказчику кое-что, но далеко не все нужное для реального ре- шения задачи. Большое значение имеет наглядность, доступность представ- ления заказчику промежуточных и окончательных результатов исследования: таблицы, графики, вывод информации на экран дисплея; нельзя предполагать наличия или требовать от заказ- чика большего объема знаний, чем это требуется существом дела. Целесообразнее, чтобы биолог использовал свое умение дифференцировать для построения и исследования математиче- ской модели, а не для оценки погрешности метода численного интегрирования. Математик должен принять во внимание образование и пси- хологию людей, применяющих разработанные им методы и про- граммы. Например, простейшая программа численного интегри- рования, предназначенная для широкого круга нематематиков, использующих ЭВМ в своих конкретных исследованиях, должна быть рассчитана на человека, потолок математических знаний которого находится на интуитивном понимании того, что интег- рал—это площадь. Чтобы не затруднять пользователя, в описа- нии простейших программ даже ничего не говорится о точности результата. Предполагается, что пользователя удовлетворит не- высокая точность результата и программа реализуется, напри- мер, так, чтобы в большинстве случаев относительная погреш- ность результата не превосходила 1 %. 6. Существенным моментом в прикладной работе является необходимость получения результатов в установленный срок. За- казчик, для которого проводятся исследования, расчеты, часто ограничен сроком завершения исследований и принятия реше- ния на их основе. Если исследования не будут завершены к сроку, то решение все равно будет принято, но на основе более грубого, эмпирического или просто «волевого» подхода. Поте- рянное в таком случае доверие со стороны заказчика часто бы- вает невозможно восстановить. 13 В такой ситуации лучше найти по возможности удовлетво- рительное решение задачи, но в срок, чем получить полное ре" шение задачи к тому времени, когда оно станет бесполезным. В частности, поэтому целесообразно начинать исследование но- вых задач с рассмотрения простейших моделей, применяя при численном решении простейшие испытанные методы. 7. Также существенным моментом в прикладной работе яв- ляется то обстоятельство, что работа, как правило, проводится коллективом. Одна из причин этого состоит в том, что построе- ние математической модели, выбор метода решения, непосред- ственное общение с ЭВМ и анализ результатов требуют раз- личных знаний и'квалификации. Другая причина кроется в упо- мянутой уже необходимости решения задачи в установленный срок. Это требование приводит к необходимости распараллели- вания даже однотипной работы между большим числом испол- нителей, например путем независимого написания различных блоков программы отдельными исполнителями. Параллельно мо- гут идти отработка различных методов на модельных задачах, обсчет упрощенных моделей, подготовительная работа по напи- санию окончательной программы решения задачи. Можно привести много реальных примеров неудачного ре- шения больших вычислительных задач и работ по созданию про- граммного обеспечения, вызванных следующей причиной. Рас- пределение обязанностей между параллельно работающими ис- полнителями не было в достаточной степени формализовано, т. е. не было выдано однозначного описания окончательного результата работы каждого исполнителя. В результате или основная доля времени уходила на непрерывное согласование отдельных частей работы, или после истечения существенного промежутка времени оказывалось, что эти части работы не сты- куются. Поэтому организаторские способности ученого, осуще- ствляющего общее руководство решением задачи, зачастую не менее важны, чем его математические способности. Приведенные выше рассуждения в определенной степени ил- люстрируют специфику работы в области прикладной матема- тики и показывают, что сложность этой работы в комплексе, как правило, превосходит сложность работы в области теоретиче- ской математики, требуя кроме широкой математической эруди- ции также других важных свойств человеческого интеллекта и характера. Глава! ПОГРЕШНОСТЬ РЕЗУЛЬТАТА ЧИСЛЕННОГО РЕШЕНИЯ ЗАДАЧИ В этой главе объясняются источники возникновения погреш- ности решения задачи, даются основные правила задания при- ближенных величин и оценивается погрешность как простей- ших, так и более сложных функций от приближенно заданных величин. Конкретные оценки этой главы по существу в дальнейшем не используются, но сам разговор о них необходим для понимания реальной обстановки, в которой используются рассматриваемые в дальнейшем методы решения задач. § 1. Источники и классификация погрешности Погрешность решения задачи обуславливается следующими причинами: 1) математическое описание задачи является неточным, в ча- стности неточно заданы исходные данные описания; 2) применяемый для решения метод часто не является точ- ным: получение точного решения возникающей математической задачи требует неограниченного или неприемлемо большого числа арифметических операций, поэтому вместо точного реше- ния задачи приходится прибегать к приближенному; 3) при вводе данных в машину, при выполнении арифмети- ческих операций и при выводе данных производятся округления. Погрешности, соответствующие этим причинам, называют: 1) неустранимой погрешностью, 2) погрешностью метода, 3) вычислительной погрешностью. Часто неустранимую погрешность подразделяют на две части: а) неустранимой погрешностью называют лишь погрешность, являющуюся следствием неточности задания числовых данных, входящих в математическое описание задачи; б) погрешность, являющуюся следствием несоответствия ма- тематического описания задачи реальности, называют погреш- ностью математической модели, 17 ЗАКЛЮЧЕНИЕ Мы закончили обсуждение традиционных вопросов теории численных методов. При этом мы, возможно слишком часто, обращали внимание на «подводные камни», встречающиеся при применении того или иного численного метода. У читателя могло возникнуть превратное впечатление, что применение численных методов для решения реальных задач настолько сложная и без- надежная задача, что от него следует отказаться. Чтобы испра- вить такое впечатление, посмотрим на этот же вопрос с опти- мистических позиций. Существует большое число задач, где есть хорошо отрабо- танные численные методы и созданные на их основе стандарт- ные программы решения задач. Например, в НИВЦ МГУ разра- ботана Библиотека программ решения типовых задач числен- ного анализа на стандарте языка фортран [12]. В настоящее время выпущено в свет 5-е издание Библиотеки, состоящее из 1200 весьма эффективных стандартных программ, предназна- ченных для решения широкого круга типичных задач. Сюда от- носятся задачи вычисления значений специальных функций, при- ближения функций, вычисления интегралов не очень высокой кратности, задачи линейной алгебры умеренной размерности, за- дача Коши и линейные краевые задачи для обыкновенных диф- ференциальных уравнений, некоторые задачи обработки резуль- татов наблюдений, задачи минимизации функций и т. д. Данная Библиотека разработана в версиях для ЭВМ БЭСМ-6, ЕС и СМ. Стандартные программы решения многих типов прикладных задач входят в математическое обеспечение, поставляемое вме- сте с ЭВМ. Если Вам впервые встретилась единичная задача, то, как правило, целесообразнее воспользоваться стандартной програм- мой или самому составить программу, основанную на простей- шем методе решения. При решении единичных задач, требую- щих умеренного объема вычислений, часто идут на более чем 100-кратное увеличение объема вычислений по сравнению с наи- более эффективными методами, лишь бы побыстрее получить ре- зультат, воспользовавшись при этом стандартной программой или алгоритмами, для реализации которых можно быстро со- ставить и отладить программу. 688 Нам регулярно встречались задачи минимизации функций большого числа переменных, в которых применение стандартных программ не приводило к положительному результату. Однако мы не теряли оптимизма и обычно при столкновении с пробле- мой решения новых типов задач минимизации начинали именно с попыток использования стандартных программ. Если, напри- мер, в 30 % случаев применение стандартных программ оказы- валось эффективным, то их применение заведомо можно считать оправданным даже и в том случае, когда использование стан- дартной программы не приводит к положительному результату; при обращении к стандартной программе будет составлено боль- шое число блоков окончательной программы и зачастую будет накоплена полезная информация о свойствах минимизируемой функции. Среди «пионеров» использования вычислительной техники встречается убеждение, что чужими стандартными программами пользоваться нельзя и программу всегда следует писать самому, заново. Такое суждение было оправдано на первоначальном этапе использования ЭВМ, когда теория численных методов была развита недостаточно и созданные на ее основе алгоритмы часто были ненадежными. При современном уровне теории чис- ленных методов и жестких требованиях к опробованию, так на- зываемому тестированию, стандартных программ с такой точкой зрения нельзя согласиться. Рассмотрим ситуацию, когда требуется путем численного эксперимента исследовать какой-либо физический процесс. Ча- сто, набив много шишек и потратив иногда годы на расчет слож- ных моделей, начинающий исследователь приходит к пониманию того, что целесообразнее было начинать с расчета простейшей модели и изучать ее с помощью простейших проверенных мето- дов, иногда требующих повышенных вычислительных затрат. Лишь в случае полного доверия к постановке задачи имеет смысл заниматься расчетом сложной модели с применением громозд- ких по своей структуре методов. Таким образом, на первоначальном этапе исследования за- дачи обычно мы имеем дело с простейшей моделью и простей- шими методами решения, часто основанными на использовании стандартных программ. Если же мы начинаем исследование за- дачи с изучения сложных моделей, то скорее всего мы посту- паем в чем-то неправильно. Целесообразнее переходить к рас- смотрению более сложных задач и применению более сложных методов, имея за плечами опыт использования ЭВМ при реше- нии простейших задач простейшими методами, поскольку при такой последовательности действий использование численных ме- тодов и ЭВМ уже не будет казаться чрезмерно трудной про- блемой. Рассмотрение самими математиками постановки прикладной задачи с ее истоков, с простейших моделей, еще важно и в связи со следующим обстоятельством. Часто, стремясь «приспособить» 689 задачу для численного решения, специалист, не знакомый с чис:-' ленными методами и возможностями ЭВМ, исходит лишь из сложности внешнего вида математической постановки. В резуль- тате этого иногда а) происходит замена исходной задачи задачей, не имеющей к ней отношения, б) задача, передающаяся численному решению при возмож- ностях современных ЭВМ, становится задачей, не поддающейся такому решению. Еще один довод в пользу более всестороннего изучения по- становки задачи состоит в следующем. Часто в процессе построе- ния простейшей модели мы получаем представление о том, в каком направлении будет идти усложнение метода и программы решения задачи. В результате этого мы сможем заложить в ис- ходный вариант программы, предназначенной для исследования простейшей модели, возможности для дальнейшего усложнения программы. Во всех случаях целесообразно составлять программу по- блочно. Дело в том, что при решении сколько-нибудь сложных задач мы заранее часто не можем сказать, будет ли выбранный нами метод решения подходящим для решения этой задачи. Например, при решении краевой задачи для дифференциаль- ных уравнений у нас может быть неуверенность в разумности выбора разностной схемы во внутренних точках или вблизи гра- ницы. Вычисления во внутренних точках и вблизи границы ве- дутся по различным формулам и поэтому лучше, чтобы они были выделены в отдельные блоки с тем, чтобы можно было произво- дить независимую отладку методов, с помощью которых ведутся расчеты уравнения и граничных условий. Также важно предусмо- треть возможность быстрого и удобного изменения параметров задачи, например шага сетки при решении дифференциальных уравнений или числа узлов квадратуры. Отладка программы и апробация метода решения задачи при малом числе узлов про- ходят быстрее и позволяют лучше использовать возможности ЭВМ. Например, при малом числе узлов можно быстро прове- рить сходимость итерационного процесса. Иногда профессиональные программисты рекомендуют про- водить отладку программы при помощи тестов. Берется мини- мально допустимое число узлов, при котором включаются в ра- боту все блоки программы (и все циклы). При таком числе уз- лов задача решается без помощи написанной программы, а за- тем результаты расчета сравниваются с результатами расчета с помощью ЭВМ. Для типичных конечно-разностных методов решения дифференциальных уравнений минимальное число узлов по каждой оси, при котором включаются в работу все блоки и циклы, находится в пределах от 2 до 5. В процессе работы над отладкой программы в программу вносятся дополнительно команды выдачи на дисплей или на пе- чать промежуточных данных с целью сравнения их с заранее 590 просчитанным тестом. Такой режим отладки особенно удобен для начинающего программиста. Специалисты, имеющие большой опыт работы с ЭВМ, пред- почитают отлаживать программу крупными модулями, сочетая отладку программы с проверкой качества метода (отладкой ме- тода). Для этого стараются строить программу решения так, чтобы при определенных значениях параметров она превраща- лась в программу решения задачи с известным решением. Например, уравнения движения снежной лавины (7.6.1) при определенных значениях параметров превращаются в уравнения мелкой воды, для которых в случае кусочно-постоянных началь- ных данных известно точное решение (так называемое решение задачи о распаде разрыва). Сравнивая решение, полученное в результате расчетов, с точным решением, можно судить о пра- вильности программы и качестве метода. Построение решения задачи о распаде разрыва само по себе требует относительно большой вспомогательной работы. Вместо непосредственного построения такого решения для заданной си- стемы часто поступают следующим образом. Вместо конкретных значений коэффициентов системы ставят- ся произвольные параметры, производится одновременная под- борка этих параметров и системы функций, которая может быть решением задачи о распаде разрыва. В результате получится некоторая задача с известным решением, отличающаяся от ин- тересующей нас задачи лишь значениями числовых параметров. На такой задаче мы можем отладить все наиболее существен- ные моменты метода и программы. Проиллюстрируем способы построения задач с известным ча- стным решением на примере дифференциальных уравнений, Пусть решается краевая задача W=-^^+^)+^+^)-e^^ в квадрате G: 0 < х, у < 1; на границе квадрата Г ставится краевое условие: {^+au-^=o• Возьмем некоторую функцию и°(х,у) и вычислим функции f (х, у) == L (и° (х, у)), ^ \г=(^г+ о"0 - g) ]^ Краевая задача L(u)-f°(x.y)=0, будет задачей с известным точным решением и == и° (х, у). Часто желательно иметь в распоряжении сеточную задачу с известным точным решением. Если, например, по простейшим 591 явным формулам решается задача Коши, то такое решение лег- ко вычислить непосредственно. В случае краевых задач или при решении задачи Коши по неявным формулам часто целесообразно поступить как и выше. Строим сеточную задачу L/,(u/i)== 0, /д(и,,)==о (с небольшим числом узлов), берем некоторую сеточную функцию ы° и вычис- ляем ^-MO. el==W. Сеточной задачей с известным точным решением и.==и° яв- ляется задача М"/.)-^. W=g°H- Иногда возникает необходимость иметь в распоряжении се- точную задачу с большим числом узлов и с точным решением. В этом случае может оказаться целесообразным поручить ЭВМ вычисление ^ и g°y Часто такую задачу получают, взяв в ка- честве ы^ множество значений в узлах сетки некоторого много- члена невысокой (обычно 1—4-й) степени. Степень многочлена выбирается из условия, чтобы погрешность аппроксимации диф- ференциальной задачи сеточной равнялась нулю. Еще раз выделим основную идею описанного выше приема построения тестов. Вместо непосредственного построения теста для исходной задачи (построение решения по заданной правой части) строится тест для обратной задачи (по заданному реше- нию строится правая часть) и он оказывается тестом для пря- мой задачи с той же структурой, но с другими числовыми дан- ными. Применение этого приема обычно существенно сокращает за- траты на построение теста. СПИСОК ЛИТЕРАТУРЫ 1. А б р а м о в А. А. О численном решении некоторых алгебраических ^задач, возникающих в теории устойчивости//ЖВМ и МФ. — 1984. — 24, J\"s 3.— С1 QOQ__447 2. Бахвалов Н. С. Об оптимальных оценках скорости сходимости квад« ратурных процессов и методов интегрирования типа Монте-Карло на клас- сах функций//Численные методы решения дифференциальных и интеграль- ных уравнений и квадратурные формулы.—М.: Наука, 1964.—С. 5—63. 3. Б а х в а л о в Н. С. Численные методы, — M.i Наука, 1975. 4. Бейкер Дж„ Грейвс—Моррис П. Аппроксимации Паде.—М.: Мир, 1986. Б. Березии И. С., Жидков Н, П. Методы вычислений. Т. 1.—-М.: Наука, 1966. 6. Б е р е з и н И. С., Жидков Н. П. Методы вычислений. Т. 2 — М.: Физ- матгиз, 1962. 7. Васильев Ф. П. Численные методы решения экстремальных задач. — М.: Наука, 1980. 8. Васильев Ф. П. Методы решения экстремальных задач. — М.: Наука, 1981. 9. Воеводин В. В. Численные методы алгебры. Теория и алгоритмы.— М.Е Наука, 1966. Ю.Воеводин В. В. Вычислительные основы линейной алгебры.—М,: Наука, 1977, 11. Воеводин В. В., Кузнецов 10. А. Матрицы и вычисления,—М.: Наука, 1984. 12. Воеводин В. В., Арушанян О. Б. Структура и организация Биб- лиотеки численного анализа НИВЦ МГУ//Численный анализ на фортране. Вычислительные методы и инструментальные системы. — М.: Изд-во МГУ, 1979. 13. Волков Е. А. Численные методы.—М.: Наука, 1982. 14. Годунов С. К., Забродин А. В. О разностных схемах второго по- рядка точности для многомерных задач//ЖВМ и МФ.—1962,—2, № 4. С. 706-708. 15. Годунов С. К., Рябенький В. С. Введение в теорию разностных схем.—М.: Наука, 1962. 16. Годунов С. К., Забродин А. В. и др. Численное решение много- мерных задач газовой динамики. — М.: Наука, 1976. 17. Годунов С. К., Рябенький В, С. Разностные схемы.—М,: Наука, 1977. 18. Годунов С. К. Решение систем линейных уравнений.—Новосибирск: Наука, 1980. 19. Джордж А., Л ю Д. Численное решение больших разреженных систем уравнений. •— М.: Мир, 1984. 20. Д р о б ы ш е в и ч В. И., Д ы м н и к о в В. П., Р и в и н Г, С. Задачи по вычислительной математике.—М.: Наука, 1980. 21. Дьякон о в Е. Г, О построении итерационных методов на основе исполь- зования операторов, эквивалентных по спектру//ЖВМ и МФ,—1966,—6, № 1. С. 12-34. 593 22. Д ь я к о н о в Е. Г. О некоторых модификациях проекционно-разностных методов//Вестник МГУ, Сер. вычислит, мат. и киберн.—1977.—1, № 2, С. 3-19. 23. Завьялов Ю. С., Квасов Б. И., Мирошниченко В, Л. Методы сплайн-функций.—М.: Наука, 1980. 24. 3 енкев и ч О., Морган К. Конечные элементы и аппроксимация,— М.: Мир, 1980. 25. И к р а м о в X. Д. Численное решение матричных уравнений. — М.: Наука, 1984. 26. Карманов В. Г. Математическое программирование.—М.: Наука, 1986. 27. Кобельков Г. М. Решение задачи о стационарной свободной конвен- ЦИИ//ДАН СССР.—1980.—255, № 2. С. 277—282. 28. Кобельков Г. М. Расчет уравнений Навье — Стокса при больших чис- лах Рейнольдса.//ЖВМ и МФ.—1984.—24,№ 2. С. 294—304, 29. Колмогоров А. Н., Тихомиров В. М. е-энтропия и 8-емкость мно- жеств в функциональных пространствах//УМН.—1959.—14. вып. 2. С. 3—86. 30. К о п ч е н о в а Н. В., М а р о н И. А. Вычислительная математика в при- мерах и задачах.—М.: Наука, 1972. 31. Крылов В. И., Б о б к о в В. В., Мон а с т ы р н ы и П. И. Начала тео- рии вычислительных методов. Дифференциальные уравнения. — Минск: Наука и техника, 1982. 32. Крылов В. И., Б о б к о в В. В., М о н а с т ы р н ы и П. И. Начала тео- рии вычислительных методов. Уравнения в частных производных. — Минск: Наука и техника, 1982. 33. К р ы л о в В. И., Б о б к о в В. В., М о н а с т ы р н ы и П. И. Начала теории вычислительных методов. Линейная алгебра и нелинейные уравне- ния. — Минск: Наука и техника, 1982. 34. Крылов В. И., Бобков В. В., Монастыри ы и П. И. Начала теории вычислительных методов. Интегральные уравнения, некорректные задачи и улучшение сходимости.—Минск: Наука и техника, 1984. 85, К р ы л о в В. И., Бобков В. В., М о н а с т ы р н ы и П. И. Начала теории вычислительных методов. Интерполирование и интегрирование. — Минск: Наука и техника, 1983. 36. К р ы л о в В. И., Шульгина А. Т. Справочная книга по численному интегрированию.—М.: Наука, 1966. 37. Крылов В. И., Бобков В. В., М о настырный П. И. Вычисли- тельные методы. Т. I. — М.: Наука, 1976. 88. К р ы л о в В. И., Бобков В. В., М о н а с т ы р н ы и П. И. Вычисли- тельные методы. Т. 2. — М.: Наука, 1977. 39. Ланцош К. Практические методы прикладного анализа.—М.: ГИФМЛ, 1961. 40. Л е б е д е в В. И. Функциональный анализ и вычислительная математи- ка. - М.: Изд-во ВИНИТИ, 1987.— (ОВМ АН СССР), 41. Лоусон Ч., Хентон Р. Численное решение задач метода наименьших квадратов.—М.: Наука, 1986. ^42. Мак-Кракен Д., Дорн У. Численные методы и программирование на фортране. — М.: Мир, 1977. 43. М а р ч у к Г. И. Методы вычислительной математики. — М.: Наука, 1980. 44. М арчу к Г. И., Агошков В. И. Введение в ироекционно-сеточные методы.—М.: Наука, 1981. 45. М а р ч у к Г. И., Лебедев В. И. Численные методы в теории переноса нейтронов.—М.: Атомиздат, 1981. 46. М а р ч у к Г. И., Шайдуров В. В. Повышение точности решений раз» ностных схем. — М.: Наука, 1979. 47. Мысовских И. П. Интерполяционные кубатурные формулы. — М.: Нау< ка, 1981. 48. Никольский С. М. Квадратурные формулы.—М.: Наука, 1979. 49. Никифоров А. Ф., Суслов С. К., Уваров В. Б. Классические ортогональные полиномы дискретной переменной, «-• М,; Наука, 1985. 60. Парлетт Б. Симметричная проблема собственных значений.=-М.: Мир, 1983. Ы.Ракитский Ю. В., Устинов С. М., Черноруцкий И. Г. Чис- ленные методы решения жестких систем.—М.: Наука, 1979. 52. Р я б е н ь к и и В. С., Филиппов А. Ф. Об устойчивости разностных уравнений. — М.: Гостехиздат, 1956. 53. Самарский А. А. Теория разностных схем.—М.: Наука, 1982. 54. С а м а р с к и и А. А., А н д р е е в В. Б. Разностные методы для решения эллиптических уравнений. — М.: Наука, 1976. 55. С а м а р с к и и А. А., Г у л и н А. В. Устойчивость разностных схем. — М.: Наука, 1973. 56. Самарский А. А., Н и к о л а е в Е. С. Методы решения сеточных урав- нений.—М.: Наука, 1&78. 57. Самарский А. А., Попов Ю. П. Разностные методы решения задач газовой динамики, — М.: Наука, 1980. 58. С а у л ь е в В. К. Интегрирование уравнений параболического типа мето- дом сеток. — М.: Физматгиз, 1960. 59. Современные численные методы решения обыкновенных дифференциаль- ных уравнений//Под ред. Дж. Холла, Дж. Уатта.—М.: Мир, 1979. 60. С т е ч к и н С. Б., С у б б о т и и Ю. Н. Сплайны в вычислительной мате- матике. — М.: Наука, 1976. 61 СтрэнгГ.,Фикс Дж, Теория метода конечных элементов.—М.: Мир, ' 1977. 62 Тихонов А. Н., А р с е н и н В. Я. Методы решения некорректных за- дач.—М.: Наука, 1986. 63. Уилкинсон Дж., Р а и н и К. Справочник алгоритмов иа языке Алгол. Линейная алгебра.—М.: Машиностроение, 1976. 64. Фаддеев Д. К., Фаддеев а В. Н. Вычислительные методы линейной алгебры. — М.: Физматгиз, 1963. 65 Форсайт Дж. в др. Машинные методы математических вычислений. — ' М.: Мир, 1980. 66. Я н е н к о Н. Н. Метод дробных шагов решения многомерных задач ма- тематической физики.—Новосибирск: Наука, 1967. 67. Dahlquist Y. Stability and error bounds in the numerical integration of ordinary differential equations.—Uppsala, Almqvist & Wiksells boktr 130 '(1959). P. 5—92. 68. Butcher I. G. A modified multistep method for the numerical integration of ordinary differential equations//J. Assoc. Comput. Math.-1965.-12, N I.—P. 124—135. 69 Stroud A. H. and Secrest D. Gaussian. Quadrature Formulas.—- ' Englewood Cliffs, N, Y.: Prentice-Hall, 1966, ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ Алгоритм ненасыщаемый 62 Аппроксимация 487 — дифференциального уравнения раз- ностной схемой 403 Большое число 22 Валле—Пуссена теорема 174 Вариация 506 Верная цифра 23 Весовая функция 85 Восполнение 541 Выделение весовой функции 147 Гарантированные оценки погрешности на классе функций 238 Главный член погрешности 136 Дивергентность разностной схемы 511 Дискретные коэффициенты Фурье 169 Дифференцирование численное 73 Замыкание алгоритма 422 — — нерегулярное 422 — — регулярное 422 Значащие цифры 23 Интегрирование осциллирующих функций 113 — системы уравнений 392 Интерполирование 35 — с кратными узлами 47 Интерполяционная формула Лагран- жа 40 — — Ньютона 45 ^- — — для интерполирования впе- ред 67 — — — — — назад 67 Интерполяция 35 — квадратичная 69 — линейная 69 — тригонометрическая 169 Итерационные методы построения многочлена наилучшего равномер- ного приближения 182 .— — с использованием спектрально эквивалентных операторов 299 60S Квадратуры Гаусса 103 — Грегори 139 — Лобатто 107 — Ньютона—Котеса 91 — обобщенные 118 — прямоугольников 83 '— Ромберга 145 — Симпсона 85 — составные 118 — трапеций 84 — Филона 114 — Эйлера 108 Количество арифметических операций 40 Конечно-разностное уравнение 50 Конечно-разностные методы 372 — — схемы 372 Ленточная структура 260 Линейная оценка погрешности 27 Линейное разностное уравнение 50 Мажорирующее разностное уравнение 474 Матрица Грама 163 . — ортогонализация 97 — отражений 266 Мера обусловленности матрицы 304 — — системы 304 — погрешности аппроксимации 489 Метод Адамса 374 — вариационно-разностный 465 — вилки 329 — Гаусса 257 — — с выбором главного элемента 261 — градиентного спуска 330 — дробных шагов 561 — исключения Гаусса 257 — квадратного корня 262 — конечных разностей 540 — — элементов 469 — Ланцоша 298 — Монте-Карло 238 — наименьших квадратов 210 — наискорейшего спуска 293 — неопределенных коэффициентов 38, 209 Метод Ньютона решения нелинейных уравнений 323 — оврагов 335 — оптимальный 61 — парабол 329 — покоординатного спуска 290 — пристрелки 414 — прогонки 416 '— проекционно-разностный 544 — простой итерации 269, 319 '— регуляризации 212 — релаксации 291 ^- Ритца 463 — сверхрелаксации 292 '— секущих 327 — сопряженных градиентов 298 — спуска 329 — стрельбы 414 — суммарной аппроксимации 561 — установления 337 — тяжелого шарика 339 — циклической прогонки 419 — штрафа 332 .— Эйлера 360 Методы интерполяционные 373 — Рунге-Кутта 360 — экстраполяционные 372 Многочлен наилучшего равномерного приближения 174 Многочлены Лагерра 101 — Лежандра 100 — наименее уклоняющийся от нуля 58 |— Чебышепа 56 — — второго рода 100 — — первого рода 100 — Эрмита 101 — Якоби 100 Наилучшее равномерное приближение 174 Недетерминированный метод 248 Некорректные задачи 405 Неравенство Бесселя 164 — Чебышева 239 Неустойчивость 34 Неявная схема, метод 373, 513 Норма энергетическая 537 Нормы векторов и матриц 255 — эквивалентные 270 е-неравенство 521 Область зависимости 483 — сходимости метода 318 Обобщенное решение 540 Обратная интерполяция 73 Обратный ход метода Гаусса 258 — — прогонки 416 Обусловленность матрицы системы 304 —— системы 304 Однородные схемы 452 Односторонние формулы численного дифференцирования 78 Одношаговые методы численного ин« тегрирования 367 Оператор расщепляющийся 555 Оптимальные квадратуры 126 Оптимальный линейный итерацион- ный процесс 281, 285 — по порядку итерационный процесс 41, 61 Оптимизация методов 61 — оценки погрешности интерполиро- вания 60 — распределения узлов интегрирова- ния 125 — скорости сходимости итерационно- го процесса 278 Ортогональная система 96 Ортогональные многочлены 98 Ортонормированная система элемен- тов 98 Остаточный член формулы Лагранжа 42 Очень большое число 23 Параметр регуляризации 583 Планирование эксперимента 36 Плохо обусловленные системы 305 Повышение порядка точности раз- ностной схемы 406 Погрешность абсолютная 22 — аппроксимации дифференциально- го уравнения разностной схемой 488, 517 — вычислительная 17 i— квадратуры на классе функций 125 — математической модели 17 — метода 17 — — на классе задач 61 — — на шаге 368, 370 — неустранимая 17 — относительная 26 — предельная 26 Порядок метода 322 — погрешности аппроксимации 377 Почти собственные значения 273 Преобразование Фурье быстрое 171 — — дискретное 169 Принцип замороженных коэффициен- тов 504 Проблема собственных значений пол- ная 309 — — — частичная 309 Прямое произведение формул инте- грирования, интерполирования, дифференцирования 225 Прямой ход метода Гаусса 258 — — — прогонки 416 сопроцесс ускорения сходимости 276 697 Разности вперед 63 — высшего порядка 63 — конечные 63 — назад 63 — разделенные 42 —— центральные 63 Разностная схема 488 — — экономичная 550 Регуляризация 582 Ряд Фурье дискретный, конечный 169 Сеточная функция Грина 409 Сжатое отображение 319 Симметризация системы уравнений 279 Система жесткая 394 Слой 514 Согласованные нормы 486 Спектральный признак устойчивости 491, 499 Сплайн 194 — интерполяционный 200 — локальный 201 Стандартные программы 46 Строго нормированное пространство 161 Схема Эйткена 45 Схемы, точные на решениях специ" ального вида 444 Сходимость 486 Таблица разделенных разностей 44 Теорема Балле—Пуссена 174 — Чебышева 174 Точки чебышевского альтернанса 174 Триангуляции 541 Тригонометрическая интерполяция 169 Узел внутренний 527 —— граничный 527 — нерегулярный 535 — приграничный 528 — регулярный 535 Узел сетки 486 Узлы интерполяции 35 Уравнения в конечных разностях 50 Условие ю 382 — сильной минимальности 547 Устойчивость 488 — безусловная 515 — по начальным данным 518 — условная 515 Формула Абеля 450 — прямоугольников 83 — Ромберга 145 — Симпсона 85 — с кратными узлами 93 — с трапеций 84 — Филона 114 Формулы Адамса 360, 375 >— Грегори 138 i— численного дифференцирования 74 Функция сильно растущая 23 Характеристическое уравнение 53 — — разностной схемы 380 Хорошо обусловленная (поставлен- ная) краевая задача 432 — обусловленные системы 305 Шаблон 517 Шаг таблицы 63 Экстраполяция 35 Элемент наилучшего приближения 160 Элементарный треугольник 541 Энергетическое неравенство 521 —- тождество 520 Энтропия 204 е-энтропия 207 Явная схема 372, 513 Явный метод 372, 513 Николай Сергеевич Бахвалов Николай Петрович Жидков Георгий Михайлович Кобельков .ЧИСЛЕННЫЕ МЕТОДЫ Редактор Т.Н.Галишникова Художественный редактор Г. М. К о р о в и н а Технический редактор В. Н. Кондакова Корректоры Е, Ю, Рычагов а, Л. С. Сомова ИБ К' 12379 Сдано в набор 23.12.88. Подписано в печать 01.07.87. Т-12157. Формат 60Х90/16. Бумага типографская № 2. Гарнитура лите- ратурная. Печать высокая. Усл. печ. л. 37,5. Усл. кр.-отт. 37,5. Уч.-изд. л. 39,22. Тираж 35,600 экз. Заказ 412. Цена 1 р. 60 к. Ордена Трудового Красного Знамени издательство «Наука» Главная редакция физико-математической литературы 117071 Москва В-71, Ленинский проспект, 15 Ленинградская типография № 2 головное предприятие ор< дена Трудового Красного Знамени Ленинградского объеди- нения «Техническая книга» им. Евгении Соколовой Союз- полнграфпрома при Государственном комитете СССР по делам издательств, полиграфии и книжной торговли, 198052 г. Ленинград, Л-52, Измайловский проспект, 29, 598