А. А. САМАРСКИЙ ТЕОРИЯ РАЗНОСТНЫХ СХЕМ ИЗДАНИЕ ВТОРОЕ, ИСПРАВЛЕННОЕ Допущено Министерством высшего и среднезо специального образования СССР в качестве учебного пособия для студентов высших учебных заведений, обучающихся по специальности «Прикладная математика» МОСКВА «НАУКА» / ГЛАВНАЯ РЕДАКЦИЯ ФИЗИКО-МАТЕМАТИЧЕСКОЙ ЛИТЕРАТУРЫ 1983 22.19 С 17 УДК 519.6 Теория разностных схем. Самарский А. А.: Учебное пособие.— М.: Наука. Главная редак- ция физико-математической литературы. 1983.— 616 с. Эта книга содержит систематическое изло- жение основных вопросов теории разностных схем, возникающих при решении задач для уравнений математической физики. Главное внимание уделяется изложению принципиаль- ных вопросов теории, иллюстрируемых на про- стых задачах математической физики для урав- нений второго порядка, имеющих в основном параболический или эллиптический тип. Книга предназначена для студентов, обу- чающихся по специальностям «Прикладная ма- тематика» и «Физика», а также для научных работников — математиков, физиков и механиков. Рис. 19. Табл. 6. Библ^ 15 назв. Первое издание выходило в 1977 году. Александр Андреевич Самарский ТЕОРИЯ РАЗНОСТНЫХ СХЕМ Редактор: И. В. Викторенко в а • Техиич. редактор: И. III. Лксельрод. Корректоры: Е. И. Сидоркина, В. П. Сорокина ИБ М 12110 Сдано в набор 10.05.82. Подписано к печати 28.01.83. Формат 60Х90'/]». Бумага тип. .№ 3. Обыкновенная гарнитура. Высокая печать. Условн. печ. л. 38,5. Уч.-изд. л. 38,99. Тираж 12 500 экз. Заказ № 174. Цена 1 р. 60 к. Издательство «Наука» Главная редакция физико-математической литературы 11707), Москва, В-71, Ленинский проспект, 15 4-я типография издательства «Наука» 630077, Новосибирск, 77, Станиславского, 25 r. 1702070000—039 or oq c 053(02)-83 s5"83 Главная редакция физико-иатематачеокой литературы издательства «Наука», 1977 ОГЛАВЛЕНИЕ Предисловие . . .............. 5 Введение ...'....."...,.,.... 9 Глава I. Предварительные сведения . . -. . . . . . . 18 § 1. Типичные задачи математической физики . .~ . . . . 18 § 2. Разностные уравнения ............ 29 Глава II. Основные понятия теории разностных схем .... 60 § 1. Разностная аппроксимация простейших дифференциальных операторов ............... 60 § 2. Устойчивость разностной схемы ......... 88 § 3. Некоторые сведения о математическом аппарате теории раз- ностных схем . . . . . . . . . . . . . . 97 § 4. Разностные схемы как операторные уравнения. Общие фор- мулировки . . ............. 113 Глава III. Однородные разностные . схемы . ...... 136 § 1. Однородные схемы для уравнения второго порядка с пере- менными коэффициентами . . . . . . . . ... 136 § 2. Консервативные схемы . .......... 141 § 3. Сходимость и точность однородных консервативных схем 150 § 4. Однородные разностные схемы на неравномерных сетках 157 § 5. Другие задачи .............. 165 § 6. Разностная функция Грина .......... 181 § 7. Схемы повышенного порядка точности . . . . . . . 187 § 8. Методы построения разностных схем ....... 193 § 9. Коэффициентная устойчивость ......... 205 Глава IV. Разностные схемы для уравнений эллиптического типа 211 § 1. Разностная задача Дирихле для уравнения Пуассона . . . 211 § 2. Принцип максимума ............. 226 § 3. Устойчивость и сходимость разностной задачи Дирихле . . 232 § 4. Некоторые свойства разностных эллиптических операторов 236 § 5. Схема повышенного порядка точности для уравнения Пуассона 250 Глава V. Разностные схемы для нестационарных уравнений с по- стоянными коэффициентами ........... 257 § 1. Одномерное уравнение теплопроводности с постоянными ко- эффициентами . . . ........... 257 § 2. Асимптотическая устойчивость . . ....... 279 § 3. Схемы для уравнения теплопроводности с несколькими про- странственными переменными . ........ 289 § 4. Нестационарное уравнение Шредингера . . . . . . 296 § 5. Уравнение переноса . ............ 300 § 6. Разностные схемы для уравнения колебаний струны . , . 307 Глава VI. Теория устойчивости разностных схем ..... 320 § 1. Операторно-разностные схемы . . ....... 320 § 2. Классы устойчивых двухслойных схем . . . . . . .331 § 3. Классы устойчивых трехслойных схем ....... 353 I* ОГЛАВЛЕНИЕ Глава VII. Однородные схемы для нестационарных уравнении ма- тематической физики с переменными коэффициентами . . . 378 § 1. Однородные разностные схемы для уравнения теплопроводно- сти с переменными коэффициентами ....... 378 § 2. Однородные разностные схемы для уравнений гиперболиче- ского типа . . . ............ 407 Глава VIII. Разностные методы решения нелинейных уравнений математической физики . ........... 413 § 1. Разностные методы решения квазилинейного уравнения теп- лопроводности . . ............ 413 § 2. Консервативные разностные схемы нестационарной газовой динамики . . .....'........ 427 Глава IX. Экономичные разностные схемы для многомерных задач математической физики ............ 442 § 1. Метод переменных направлений (продольно-поперечная схе- ма) для уравнения теплопроводности ....... 442 § 2. Экономичные факторизованные схемы ....... 458 § 3. Метод суммарной аппроксимации ........ 477 Глава X. Методы решения сеточных уравнений . . . . . . 515 § 1. Прямые методы ............. 515 § 2. Двухслойные итерационные схемы ........ 523 § 3. Попеременно-треугольный метод . . ....... 540 § 4. Итерационные методы переменных направлений .... 567 § 5. Другие итерационные методы . ......... 580 Дополнение ................. 592 § 1. Некоторые сведения из функционального анализа . . . 592 § 2. Некоторые варианты метода прогонки ... . . . . 597 § 3. Задачи ................ 601 Библиографические комментарии . . ......... 609 Литература .' . . .............. 612 Основные обозначения, принятые в книге ........ 613 Предметный .указатель .... ......... 615 ПРЕДИСЛОВИЕ КО ВТОРОМУ ИЗДАНИЮ За время, прошедшее после выхода первого издания этой кни- ги, в теории разностных методов получен ряд важных результа- тов, относящихся: 1) к разработке методов построения разност- ных схем для линейных и нелинейных многомерных задач мате- матической физики (вариационно-разностные методы, метод опорных операторов и др.); 2) к изучению точности разностных схем на негладких (обобщенных) решениях; 3) к. разработке но- вых методов численного решения разностных эллиптических уравнений и др. Однако, поскольку сначала предполагалось стереотипное пере- издание книги непосредственно с матриц, то автор вынужден был ограничиться -лишь внесением минимального числа исправлений для устранения опечаток и неточностей. Для обеспечения учебного процесса по специальностям «При- кладная математика» и «Вычислительная математика» необходи- мы учебные пособия разного типа и уровня. В последние 5 лет автором вместе с сотрудниками подготовлен ряд книг. Вопросы, связанные с решением систем линейных алгебраических уравне- ний вообще и разностных уравнений в особенности, детально рассматриваются в книге А. А. Самарского и Е. С. Николаева «Методы решения сеточных уравнений» (М.: Наука, 1978), где изложены прямые методы и дана общая теория итерационных методов решения систем линейных уравнений, а также различные специальные методы для разностных уравнений. В книге А. А. Самарского и И. П. Попова «Разностные мето- ды решения задач газовой динамики» (второе переработанное издание, М.: Наука, 1980) излагаются методы построения и ис- следования разностных схем для одномерных и двумерных задач газовой динамики и магнитной гидродинамики, а также методы решения нелинейных уравнений для неявных схем. Она идейно опирается на книгу «Теория разностных схем» и иллюстрирует особенности численного решения нелинейных задач математиче- ской физики. Находится в печати книга А. А. Самарского «Введение в чис- ленные методы»; она написана на основе лекций автора, читав- шихся в течение ряда лет для студентов 2-го курса факультета вычислительной математики и кибернетики Московского государ- ственного университета им. М. В. Ломоносова. 5 мая 1982 г. Москва А. А. Самарский ПРЕДИСЛОВИЕ К ПЕРВОМУ ИЗДАНИЮ Быстрое развитие численных методов решения задач матема- тической физики вызывает необходимость изложения теории раз- постных (или сеточных) методов на современном уровне в форме, доступной для широкого круга читателей. Данная книга, являю- щаяся учебным пособием, содержит изложение основ теории раз- ностных схем и применения этой теории для изучения числен- ных алгоритмов решения на ЭВМ' типичных задач математиче- ской физики. В ней дается по возможности элементарное и систематическое изложение основных принципиальных вопросов теории, иллюстрируемых на прдстейших задачах для обыкно- венных дифференциальных уравнений, для уравнений парабо- лического, эллиптического и гиперболического типов. Рассмат- риваются прежде всего те схемы (или их простейшие модели), которые представляют практический интерес, т. е. пригодны для решения конкретных задач па ЭВМ. Основное внимание уделяется написанию разностной схемы и теоретическому (априорному) исследованию ее свойств (погреш- ности аппроксимации, устойчивости, сходимости и точности), а также вычислительным алгоритмам для решения разностных уравнений, получающихся при сеточной аппроксимации. Форму- лируются конструктивные принципы (такие, как требования од- нородности и консервативности, суммарной аппроксимации и др.), которые теоретически обоснованы для линейных и проверены на практике для нелинейных задач. Эффективность общей теории разностных схем, в особенности теории устойчивости (гл. VI), проиллюстрирована на большом числе примеров, причем даже для простейших уравнений с постоянными коэффициентами об- щая теория дает неулучшаемые результаты. Поскольку мы рас- сматриваем лишь схемы для дифференциальных уравнений второ- го порядка, то при решении получающихся разностных уравнений (как в одномерном, так- и многомерном случаях) используется лишь алгоритм одномерной прогонки (для систем алгебраических уравнений с трехдиагональной матрицей). Следует отметить, что для теории разностных схем типично предположение о том, 'что решение исходной задачи для диф- ференциального уравнения существует и имеет нужное по ходу изложения число производных, обеспечивающих максимальный порядок аппроксимации. Мы не останавливаемся на перечне ус- ловий, обеспечивающих требуемую гладкость решения. Предполагается, что читатель знаком с основами универси- тетского курса теории -уравнений в частных производных (на- ПРЕДИСЛОВИЕ К ПЕРВОМУ ИЗДАНИЮ •7 пример, по книге А. Н. Тихонова и А. А. Самарского «Уравнения математической физики»), точнее, с постановками типичных задач, а также с элементами функционального анализа (перечень некоторых сведений дан в Добавлении к книге). Коротко о содержании книги. Глава I является вводной. В § 1 гл. I даны сведения справочного характера о типичных задачах математической физики, а в § 2 изучаются разностные уравнения, в основном второго порядка, и даны алгоритмы про- гонки. Основные понятия теории разностных схем, иллюстрируе- мые большим числом примеров, излагаются в гл. II. Глава III посвящена теории однородных консервативных разностных схем для краевых задач в случае обыкновенного дифференциального уравнения второго порядка. Здесь демонстрируются различные методы исследования и построения разностных схем. Разностная задача Дирихле для уравнения Пуассона, а также для эллип- тических уравнений общего вида изучается в гл. IV. В главе V рассматриваются разностные схемы для уравнений теплопровод- ности, колебаний струны, уравнения Шредингера и уравнений переноса; здесь изучаются только уравнения с постоянными коэф- фициентами. В главе VI излагается общая теория устойчивости двухслойных и трехслойных операторно-разностных схем. При- менение этой теории к однородным разностным схемам для па- раболических и гиперболических уравнений 2-го порядка с переменными коэффициентами дано в гл. VII. Глава VIII по- священа нелинейным задачам теплопроводности и газовой ди- намики. Экономичные методы решения многомерных уравнений мате- матической физики изложены в гл. IX, а в гл. Х даны методы решения сеточных уравнений, получающихся, в частности, при аппроксимации эллиптических уравнений. По ходу изложения обращается внимание читателя на вопросы, касающиеся прак- тического использования алгоритмов. При написании данной книги использовалась монография автора «Введение в теорию разностных схем». Переход от моно- графии к учебному пособию потребовал существенной переработ- ки. В частности, за последние пять лет появился ряд новых численных методов и теоретических работ, приведших к пере- оценке некоторых популярных методов. Так, например, полно- стью переработан материал главы X. В последние годы появилось много работ, посвященных ме- тоду конечных элементов (МКЭ) — одному из видов вариационно- разностных методов. Его изложение громоздко, и в книге дан пример вывода разностной схемы с помощью МКЭ для одномер- ной задачи (§ 8 гл. III), причем схема совпадает с той, что по- лучена интегро-интерполяционным методом. Подчеркнем, что МКЭ — это только один из методов получения разностных схем., возможно, нестандартного типа. 8 ПРЕДИСЛОВИЕ К ПЕРВОМУ ИЗДАНИЮ Характер книги как учебного пособия вынудил отказаться от обзора работ по отдельным разделам теории разностных схем и ограничиться краткими библиографическими сведениями в конце книги. Отметим также, что в книге «Введение в теорию разност- ных схем» дана подробная библиография вплоть до 1971 года. На основе материала книги можно построить лекционные кур- сы по теории разностных схем, рассчитанные на один, два или три семестра. Отбор соответствующего материала не представляет труда. В частности, материал § 2 гл. II, частично гл. III, VIII (§ 1, п. 1) и гл. Х (общая теория итерационных методов, модель- ный пример — трехточечная схема для уравнения и" (х) = —/(ж), 0<а"<1, и(0) = ц(1) = 0) составил большую часть содержания лекций по численным методам, прочитанных автором в весеннем семестре 1976 года для студентов 2-го курса факультета вычисли- тельной математики и кибернетики Московского государственного университета. Данную книгу следует рассматривать как первую в цикле, к которому относятся также книги: Самарский А. А., Г у л и н А. В. Устойчивость разност- ных схем.— М., 1973. Самарский А. А., Попов Ю. П. Разностные схемы га- зовой динамики.— М., 1975. Самарский А. А., Андреев В. Б. Разностные методы решения эллиптических уравнений.— М., 1976. По материалам, вошедшим в эту книгу, автор в 1960—1976 гг. читал в Московском государственном университете им. М. В. Ло- моносова лекции для студентов физического, механико-математи- ческого факультетов и факультета вычислительной математики и кибернетики. Считаю своим приятным долгом выразить благодарность мо- ему учителю Андрею Николаевичу Тихонову, многолетняя сов- местная работа с которым способствовала определению содержа- ния и характера изложения теории разностных схем. При подготовке книги автор учел замечания В. Б. Андреева, А. В. Гулина, И. В. Фрязинова н др. Особенно большую помощь оказали автору А. В. Захаров при подготовке рукописи к печати и Е. С. Николаев — при работе над гл. X. Всем им я выражаю глубокую благодарность. Я благодарен также В. М. Марченко за помощь при оформлении рукописи, Р. А. Волковой и Д. А. Голь- диной за проведение методических расчетов. Москва, октябрь 1976 г. А. А. Самарский ВВЕДЕНИЕ Бурное развитие численных методов и становление новой науки — вычислительной математики — в последние два-три деся- тилетия связано с необходимостью решения крупных научно- технических проблем и появлением быстродействующих электрон- но-вычислительных машин (ЭВМ или компьютеров). Достаточно указать такие проблемы, как 1) овладение ядерной энергией, создание ядерных реакторов, 2) проектирование летательных аппаратов (самолетов и ракет), 3) динамика космических полетов, 4) изучение физики плазмы в связи с проблемой управляемого термоядерного синтеза и др. Решение этих задач было бы невозможно без применения численных методов. Успехи в области вычислительной матема- тики и ее приложений способствовали повышению интереса к математике вообще и привели к созданию новых ее разделов. В настоящее время можно говорить, что появился новый спо- соб теоретического исследования сложных процессов, допускаю- щих математическое описание или математическое моделирова- ние,— вычислительный эксперимент, т. е. исследование реальных процессов средствами вычислительной математики. В чем заключается вычислительный эксперимент (ВЭ)? (См.: Самаре к и и А. А. Математическое моделирование и вычисли- тельный эксперимент.— Вестник АН СССР, 1979, № 5, с. 38—49.) Пусть требуется изучить некоторый физический процесс. Будем исследовать его методом ВЭ. Первый этап — математическая формулировка задачи или вы- бор математической модели. Этому предшествует выбор физиче- ского приближения, т. е. того, какие факторы надо учесть, а ка- кими можно пренебречь. Это — привилегия физиков. Что такое математическая модель? Указываются группа иско- мых физических величин и группа заданных величин: между ними есть связь, т. е. уравнения (алгебраические или дифферен- циальные), написание которых вместе со всей необходимой ин- формацией (о коэффициентах уравнений, о начальных и краевых условиях) и есть выбор математической модели. Изучением математических моделей физики занимается мате- матическая физика. Уравнениями математической физики, в основ- ном, являются дифференциальные уравнения с частными произ- водными, а также интегральные и интегро-дифференциальные- уравнения. Эти уравнения обычно выражают законы сохране- ния основных физических величин (энергии, количества движе- ния, массы и др.) и, как правило, являются нелинейными. 10 ВВЕДЕНИЕ После того как написана система уравнений, описывающих процесс, надо исследовать полученную математическую модель методами общей теории дифференциальных и интегральных уравнений. Надо установить, правильно ли поставлена задача, хватает ли данных, не противоречат ли они друг другу, найти условия, при которых задача разрешима и имеет единственное решение, выяснить, нельзя ли написать решение задачи в явном виде, можно ли построить частные решения. Частные решения важны для получения первичной информации о характере физи- ческого процесса, а также как тесты для проверки качества чис- ленных методов. Второй этап — построение приближенного (численного) мето- да решения задачи, написание вычислительного алгоритма. Третий этап — программирование для ЭВМ вычислительного алгоритма. Четвертый этап — проведение расчетов на ЭВМ. Пятый этап — анализ полученных численных результатов и уточнение математической модели. Может оказаться, что математическая модель слишком груба— результат вычислении не согласуется с физическим эксперимен- том, или что модель слишком сложна, и решение с достаточной точностью можно получить при более простых моделях. Тогда следует начинать работу с первого этапа и снова пройти все этапы и т. д. Здесь показаны этапы вычислительного эксперимента при теоретическом исследовании физических задач. Речь идет о но- вом методе теоретического исследования с использованием слож- ных математических моделей. На первом этапе используются классические методы матема- тической физики. Следует отметить, что многие задача приводят к таким математическим моделям физики, -разработка теории которых находится в начальной стадии. На практике Приходится численно решать такие нелинейные задачи математической физи- ки, для которых еще не доказаны даже теоремы существования и единственности. Здесь мы остановимся лишь на втором этапе вычислительного эксперимента. Под вычислительным алгоритмом обычно понимают последовательность операций (логических и арифметических), при помощи которых находится решение задачи. Требуется, что- бы вычислительный алгоритм давал решение задачи с любой степенью точности е > 0 за конечное число действий Q(e,). Это общее требование. Но уже оно вызывает много вопросов матема- тического характера. Что значит: «с любой точностью»? Должна быть показана принципиальная возможность получить решение с любой точностью, однако возможен случай, когда ()(е) при некотором е конечно, но настолько велико, что нереально на практике получить решение с такой точностью е. Для любой ВВЕДЕНИЕ 11 задачи можно построить бесчисленное множество вычислитель- ных алгоритмов, которые обладают, например, одинаковыми асимптотическими свойствами, так что для них - 0. Изучать надо не все такие методы, а лишь те из них, которые пригодны для работы на ЭВМ. Естественно выбирать такие методы, которые для решения задачи с заданной точностью требуют минимального машинного време- ни. Время решения задачи должно быть разумным, измеряться • минутами или, если речь идет о единичных расчетах, несколь- кими часами. Расчет должен стоить возможно дешевле. Время решения задачи зависит от алгоритма, от вычислительной маши- ны и качества программы. Последнее учесть при априорных оценках качества алгоритма очень трудно. Число логических . действий тоже трудно оценить независимо от машины. Поэтому сравнение вычислительных алгоритмов при теоретическом иссле- довании проводят обычно по числу арифметических операций (Зц(е). Поиск экономичного алгоритма, для которого число опе- раций минимально, осуществляется в классе допустимых алго- ритмов (например, имеющих одну и ту же асимптотику для Q»(s)' при е^-0). В этом и состоит основная задача теории численных- методов. При теоретических исследованиях алгоритмов обычно сначала предполагается, что вычислительный процесс является идеаль- ным, т. е. вычисления ведутся с бесконечным числом знаков. Однако на ЭВМ вычисления ведутся с конечной скоростью к с конечным числом знаков, допустимы не все числа, есть машин- ный нуль и машинная бесконечность. Если в процессе вычисле- ний получается машинная бесконечность, то происходит аварий- ный останов (авост). Вычислительный процесс может оказаться неустойчивым, т. е. ошибки округления могут неограниченно- нарастать, что делает алгоритм непригодным для практических расчетов (примеры таких неустойчивых алгоритмов приводятся в гл. II данной книги). Реальный (т. е. пригодный для ЭВМ) вычислительный алгоритм должен быть устойчивым и не допу- скать в процессе вычислений слишком больших промежуточных значений (приводящих к авосту). Из сказанного ясно, что иде- альный вычислительный алгоритм может быть оптимальным по числу Qa{e) и совершенно непригодным для вычислений на ЭВМ. Поэтому надо искать оптимальные реальные вычислительные алгоритмы. Вычислительный эксперимент — это не разовый счет по стан- дартным формулам, а прежде всего расчет серии вариантов для различных математических моделей. Пусть, например, надо найти оптимальные условия некоторого химического процесса, 'т., е. найти условия, при которых быстрее всего идет реакция. Реше- ние задачи зависит от ряда параметров (например, от темпера- туры, давления, от состава реагирующей смеси и др.). Чтобы 12 ВВЕДЕНИЕ найти оптимальный режим работы, надо провести расчеты для различных значений этих параметров, т. е. решить ряд вариан- тов. Конечно, возможны ситуации, когда алгоритм нужен для одиночных расчетов. Постановка задачи об оптимальном алгоритме зависит от ха- рактера его использования (в одновариантном или многовариант- ном режиме). Мы не останавливаемся здесь на вопросах, связанных с про- граммированием, организацией и проведением вычислений па ЭВМ. Отметим лишь, что деятельность по программированию должна быть тесно связана с разработкой численных алгорит- мов. Задачи математической физики сложны и алгоритмы для их решения—громоздки. Их надо делить на блоки, «модули». Далее, процессы разной физической природы часто описываются одними и теми же уравнениями (например, процессы диффузии, теплопроводности и намагничивания). Разные физические задачи могут иметь одну и ту же математическую модель, хотя у каж- дой задачи есть своя физическая специфика. С другой стороны, математическая модель в процессе проведения вычислительного эксперимента может существенно меняться несколько раз, и это требует изменения алгоритма (точнее, отдельных его частей) и, следовательно, программы. Отсюда возникает необходимость со- здания комплекса программ (пакета программ), построенного на модульном принципе и позволяющего оперативно проводить вы- числительный эксперимент и решать классы задач разной физи- ческой природы. Это — актуальное направление в программирова- нии и решении больших задач математической физики, оказы- вающее воздействие на работу по созданию численных методов. Для численного решения задач математической физики обыч- но применяется метод конечных разностей или метод сеток. Он позволяет свести решение дифференциальных уравнений в част- ных производных к решению систем алгебраических уравнений. Данная книга посвящена теории разностных методов (схем) для решения типичных задач математической физики. В теории численных методов есть два главных вопроса: 1) построение дискретных (разностных) аппроксимаций для уравнений математической физики и исследование априорных характеристик качества этих аппроксимаций, что сводится преж- де всего к изучению погрешности аппроксимации, устойчивости и связанной с ними точности полученной разностной схемы; 2) решение разностных уравнений прямыми или итерацион- ными методами, выбираемыми из соображений экономичности вычислительного алгоритма. Характерная черта численных методов — их множественность. Каждому уравнению можно сопоставить бесчисленное множество разностных аппроксимаций, имеющих одни и те же асимптоти- ческие (т. е. по порядку относительно шага сетки h) характе- ВВЕДЕНИЕ 13 ристики (один и тот же порядок точности, одинаковый по по- рядку объем вычислений и т. д.). В этом состоит основная при- чина появления большого числа разных схем для основных уравнений математической физики. Естественно стремление найти наилучший метод, который позволял бы получить искомое решение с заданной точностью за минимальное машинное время. Поиск таких численных мето- дов на некотором множестве допустимых методов и есть основ- ная цель теории. Для поиска наилучшего (оптимального) метода (выбор которого зависит от класса решаемых задач) применяется постепенное сужение множества допустимых методов путем по- следовательного включения требований аппроксимации, устой- чивости, экономичности и др. Важную роль играет общее требо- вание: разностная схема (дискретная модель) должна как можно лучше моделировать (приближать) свойства исходного дифферен- циального уравнения. Для практики необходимо формулировать общие принципы, эвристические приемы и правила для получения разностных схем заданного качества. Такими принципами прежде всего являются принципы однородности (единообразия) и консерва- тивности разностной схемы. Консервативность означает, что раз- ностная схема выражает некоторый закон сохранения (уравнение баланса) на сетке. Консервативность однородных схем является необходимым условием сходимости в классе разрывных коэффи- циентов для стационарных и нестационарных задач математи- ческой физики. Для линейных уравнений свойство консервативности разност- ной схемы обычно эквивалентно требованию самосопряженности разностного оператора (см. гл. III и IV). Для нелинейных урав- нений, например уравнений газовой' динамики, эффективным конструктивным принципом является принцип полной консерва- тивности разностной схемы (см. § 2 гл. VIII). Основные понятия теории разностных схем — погрешность аппроксимации, устойчивость, сходимость и точность разностной схемы—вводятся в гл. II данной книги. Эти понятия иллюстри- руются на примерах схем для обыкновенных дифференциальных уравнений. Уже здесь намечается переход к общим формулиров- кам, не использующим информации о конкретном виде разност- ного оператора. Основной вопрос теории — о точности схемы — сводится к изучению погрешности аппроксимации и устойчивости схемы. Изучение устойчивости схемы сводится к получению априорных оценок решения разностной задачи через входные данные зада- чи, что является большой самостоятельной проблемой, требую- щей специального рассмотрения. С другой стороны, и вопрос о погрешности аппроксимации не является тривиальным. Уже простейший пример схемы на 14 ВВЕДЕНИЕ неравномерной сетке для уравнения второго порядка показыва- ет, что погрешность аппроксимации желательно оценивать не в норме С, а в более слабой норме специального вида (в нега- тивной норме). Отсюда возникает необходимость получения ап- риорных оценок для решения разностной задачи через правую часть в слабой норме. Такого вида оценки получены в гл. III и использованы для доказательства сходимости однородных раз- ностных схем в классе разрывных коэффициентов. С необходимостью пересмотра понятия погрешности аппрок- симации и, тем самым, понятия таемы мы сталкиваемся в гл. IX в связи с построением экономичных схем для многомерных задач математической физики. Введенное в § 3 гл. IX понятие сум- марной (по t) аппроксимации носит конструктивный характер и позволяет легко написать экономичные схемы для различ- ных задач. В книге есть примеры, показывающие различные подходы к понятию устойчивости разностных схем. Так, в гл. V, посвя- щенной разностным схемам для нестационарных уравнений с постоянными коэффициентами, изучается асимптотическая устой- чивость разностных схем для уравнения теплопроводности — свойство, присущее дифференциальному уравнению. Теоретические вопросы возникают в гл. II—V в связи с изу- чением конкретных разностных схем для уравнений эллиптиче- ского, параболического и гиперболического типов. В гл. III, в связи с изучением однородных разностных схем для обыкно- венного дифференциального уравнения, ставится типичная задача теории разностных схем: задано исходное семейство разностных схем (в данном случае семейство задано, если заданы шаблон- ные функционалы), требуется найти в . этом семействе схемы нужного качества. Эта задача решается в гл. III с использова- нием конкретного вида схемы, и ее решение приводит нас к консервативным однородным схемам. В гл. VI излагается общая теория разностных схем. Для построения общей теории разностных схем естественно освобо- диться от предположений о структуре разностных операторов, об их явном представлении. Это приводит к определению раз- ностных схем как операторных уравнений (аналогу сеточных аппроксимаций для эллиптических и интегральных уравнений) и операторно-разностных уравнений (разностных по аргументу t с операторными коэффициентами), которые являются аналогами разностных схем для нестационарных (эволюционных) уравнений Математической физики (например, параболического и гипербо- лического типа). Операторы схем являются линейными опера- торами, заданными в некотором абстрактном линейном нормиро- ванном пространстве Нь, зависящем от векторного параметра h (аналога шага сетки по a:=(a:i, х^, ..., Жр)) с нормой |/г1>0. Итак, рассматриваются два типа схем: ВВЕДЕНИЕ 15 ' Операторная схема имеет вид последовательности (по пара- метру h) операторных уравнений первого рода Ay=f, где А = Ah. Hh ->- Hh (оператор Ah зависит от h и действует из. И,, в Ни), f= fh e If,, — заданный вектор, у = уь е Нь — искомый вектор. Операторно-разностная двухслойная схема записывается в следующем каноническом виде: В „3+1. + Ay} = (рэ, ; = 0,1, ..., задан г/° : Hh, где т—шаг сетки по t: ^=/т, /=0, 1, ..., А, В: Hi, -> Нь и зависят от /i, т и, вообще говоря, от t„ у' = г//,, ,(<,-) е Hh — иско- мая, а <р' = <рл, ,(t,) e Hh — заданная функции дискретного аргу- мента t,==ji со значениями в Нь (индексы h, т ниже опускаем). Многослойные схемы (т. е. схемы содержащие значения yW для нескольких моментов t = t„ t,+i, ^-+2, ...) могут быть све- дены к двухслойным схемам, у которых Л и В являются опе- раторными матрицами. Центральным разделом теории разностных схем является тео- рия устойчивости. Исследованию устойчивости разностных схем посвящено огромное количество работ, значительная часть ко- торых основана на применении спектральных методов и содержит трудно сопоставимые и малоэффективные результаты, как пра- вило, использующие предположения о структуре разностных операторов. В. случае схем с несамосопряженными операторами спектральная теория дает необходимые условия устойчивости, в то время как основной интерес_ представляют достаточные условия и априорные оценки. Между тем энергетический подход, использующий введенные выше определения схемы, позволяет дать исчерпывающее исследование устойчивости схемы с опера- торами в гильбертовом пространстве Hh. Очевидно, что устойчивость есть внутреннее свойство схемы, не зависящее от аппроксимации и связи схемы с каким-либо дифференциальным уравнением; поэтому условие устойчивости должно формулироваться в виде некоторой связи между опера- торами А и В. Задача ставится так. Задано исходное семейство схем при по- мощи условий на Л и В: Л=Л*>0 или (Ay, v) = (у, Av), (Ay, у) > 0 для любых у, У е Я, где (,) — скалярное произведение в H, В > О, В^В* (В не является самосопряженным). Требуется вы- делить из этого семейства множество устойчивых по начальным данным схем В „5+1 Г-У_ + Ау5 == 0, /=0,1,...,^ ;Я, 16 ВВЕДЕНИЕ для которых выполнено неравенство l^ll^lly0^, где \\у\\^=ПАу,у) (устойчивость здесь означает выполнение этой оценки). Необходимое и достаточное условие устойчивости двухслой- ных схем имеет вид операторного неравенства В ^ 0,5тА или (5у, у) > 0,5т(Ау, у) для любых у <= Н. Это условие удобно для проверки в случае разностных схем для уравнений математической физики. Оно выделяет из исход- ного семейства схем множество устойчивых схем, в котором и следует искать схемы нужного качества по точности, объему вычислений и т. д; Следствием теории устойчивости является общий метод регуляризации в классе устойчивых схем (путем изменения операторов А и В}, для получения схем заданного качества. Важную роль играет каноническая форма записи схем. В аналогичной форме записываются итерационные схемы для операторных уравнений Аи == f. Это позволяет применять ре- зультаты общей теории устойчивости операторно-разностных схем к изучению итерационных методов (гл. X). В гл. VI получено большое число априорных оценок, выра- жающих устойчивость двухслойных и трехслойных схем по на- чальным данным и по правой части. Эти оценки широко исполь- зуются в гл. VII, IX и X. Отметим, что в теории разностных схем фактически исполь- зуются элементарные понятия функционального анализа и ли- нейной алгебры, такие как норма оператора, сопряженный опе- ратор, операторное неравенство и т. п. Для удобства читателя эти сведения даны в конце книги, в виде дополнения. В книге приводится много примеров практического исполь- зования для конкретных схем общей теории устойчивости, изло- женной в гл. VI. Основная часть книги посвящена разностным методам реше- ния линейных уравнений математической физики. В гл. VIII рассматриваются нелинейные задачи теплопроводности и газовой динамики. Гл. IX -посвящена экономичным методам решения многомерных задач математической физики. Экономичные схемы для нестационарных задач делятся на две группы: 1) факторизованные схемы, обладающие аппроксимацией в обычном смысле; 2) аддитивные схемы, которые представляют собой цепочку обычных схем, осуществляющих переход от слоя /" на слой ; + 1, и аппроксимируют исходное дифференциальное уравнение в сум- марном смысле. ВВЕДЕНИЕ 17 Для каждого типа схем указаны методы исследования ап- проксимации и устойчивости. Устойчивость факторизованных схем исследована на основе общей теории устойчивости, а для адди- тивных схем развит свой метод исследования устойчивости, использующий свойство суммарной аппроксимации. В частности, оценки в равномерной метрике в случае аддитивной (локально- одномерной) схемы для уравнения теплопроводности удается по- лучить при помощи принципа максимума, общая формулировка ' которого дана в гл. IV. Для большинства экономичных методов решения многомер- ных задач типично использование на каждом этапе вычислений алгортимов решения одномерных задач. Методы решения разностных уравнений, получающихся при аппроксимации дифференциальных уравнений эллиптического типа, изучаются в последней, десятой,, главе. Сначала излагаются прямые методы (декомпозиции и разделения переменных), при- годные для решения разностной задачи Дирихле в случае урав- нения Пуассона в прямоугольнике. Они являются более эконо- мичными, чем метод переменных направлений с оптимальным набором итерационных параметров. Общая теория итерационных методов излагается для уравне- ния первого рода Аи = /, где А — линейный оператор в гиль- бертовом пространстве. Теория итерационных методов трактуется как раздел общей теории устойчивости операторно-разностных схем. Найден оптимальный набор параметров и получены оценки скорости сходимости для двухслойной итерационной схемы. Большое внимание уделяется попеременно-треугольному методу с оптимальным набором чебышевских параметров. Этот универ- сальный метод является весьма эффективным для решения эл- липтических уравнений с переменными коэффициентами в про- извольной области. Соответствующие алгоритмы приведены в § 3 гл. X. . Г л а в а, 1 ПРЕДВАРИТЕЛЬНЫЕ СВЕДЕНИЯ В этой главе содержатся некоторые предварительные сведедая исполь- зуемые в дальнейшем. В § 1 рассматриваются типичные стационарные и не- •стационарные задачи математической физики. В § 2 проводится изучение простейших представителей сеточных уравиеаий — рааностных уравнений второго порядка, которые являются .важным элементом рассматриваемых в книг® вычислительиых алгоритмов для одномерных и многомерных задач математической физики. § 1. Типичные задачи математической физика 1. Стационарные задачи. Основная цель книги -- изучение численных методов решения уравнений математическое физики. Чтобы подчеркнуть связь с обычным университетским курсом уравнений математической физики, выпишем типичны^ -уоавне- яия математической физики и постановки краевых йадач для яих. Не имея возможности останавливаться подробно ад физи- ческих задачах, приводящих к тем или иным уравнения^ д так- же на теории краевых задач математической физика ограни- чимся ссылками на книги по уравнениям математической физики *). Основное изложение мы проводим для линейных Уравнений второго порядка. . Различают два типа процессов — нестационарные (меняю- щиеся во времени) и стационарные (не меняющиеся во времени). Нестационарные процессы описываются прежде в^его урав- нениями параболического и гиперболического типов, а стацио- нарные процессы — уравнениями эллиптического типо^. Начнем со стационарных задач. Простейшим представителем уравнения эллиптического типа является уравнение Лапласа , у д^и „ , , , ли = 2^ ~g~T = °» и = " (•г)' х == (^г х^ • • •' ^р) (1) (р = 1, 2, . .., ро, р — число измерений). Неоднородное уравне- ние АУ = -/(а-) (2) называют уравнением Пуассона. *) Ом. Тихонов А. Н., С а м а р с к и и А. А. Уравнения Математиче- ской физики.— М.: Наука, 1972. § 1. ТИПИЧНЫЕ ЗАДАЧИ МАТЕМАТИЧЕСКОЙ ФИЗИКИ > Щ К уравнениям Лапласа и Пуассона приводят задачи о ста- ционарном распределении тепла, задачи диффузии, электроста- тики и др. , Стационарное распределение температуры и — u(Xi, Ts, Хз1' в однородной среде описывается уравнением Пуассона &.u=-f, f=F/k, где F = F(x) — плотность тепловых источников (источник^ a k = coast > 0 — коэффициент теплопроводности. Если среда неоднородна, то коэффициент теплопроводности k ' зависит от точки ж, k = k(x), и вместо уравнения Пуассона по- лучаем уравнение div (k grad u) = Jg -^- (k ^ -^-} = - F ^' k (ж) > 0- (3) а=1 " \ ° В анизотропной среде температура и == и(х) удовлетйоряег уравнению Р _Р_ „ , д /, ди (4) F{x). Эхе дх., a=i |j=l Это уравнение является эллиптическим при условии положитель-. ности квадратичной формы (во всех точках х == (xi, х^, ..., Хр)}. •Р S /cap (ж) ^р > О, а, Р=1 где ti, 'S,2, . • ; ^р — координаты произвольного вектора | такого^ что 1|1 ^ 0. Если р Р 2 ^ар (а') S^P > ^ S ^, с\ = cons1 > б. с»,р=-1 »=1 то уравнение (4) называют сильно эллиптическим. Если имеются источники (или стоки) тепла, пропорциональ". ные температуре, то стационарное уравнение теплопроводности. принимает вид div {k grad и) — q(x)u == -F(,x) (5) (при q{x) > 0 имеется сток, а при q{x) < 0 — источник тепла). При высоких температурах коэффициент теплопроводности зависит от температуры: k == k{u, х), и мы получаем квазили- нейное уравнение теплопроводности, например, div (k(u, х) grad и) == —F{x, и), если мощность источников тепла также зависит от температуры (что имеет место, например, в случае тепловыделения за счет- 2* Литература 91 альтернативой для обсуждавшегося в гл. 1 метода конечных разностей. Полезность метода очевидна, поскольку было показано, что в ряде задач при одном и том же числе неизвестных он дает решение более точное, чем метод конечных разностей. К сожалению, использование метода взвешенных невязок применительно к аппроксимациям базисными функциями еще не снимает основных трудностей. Для двух- и трехмерных областей метод конечных разностей представляется более гибким, так как использование здесь базисных функций естественно ограничило бы нас рассмотрением прямоугольников, параллелепипедов и дру- гих областей простой формы, если мы хотим точно учесть крае- вые условия. Кроме того, матрица К системы алгебраических уравнений, получающейся при применении метода взвешенных невязок (см. уравнение (2.55)), с увеличением числа используемых для аппроксимации элементов в ряде случаев может стать плохо обусловленной. Такая ситуация имела место в примере 2.6, где матрица К подобна хорошо известной матрице Гильберта. Проблему, связанную с выбором системы базисных функций, обычно удается решить путем использования базисных функций с более сильными свойствами ортогональности [8]. В частности, если в примере 2.6 базисные функции должны быть многочленами, то наиболее приемлемым выбором могли бы быть многочлены Лежандра (обсуждаемые в другом контексте в гл. 4) или много- члены Чебышева [9]. В следующей главе указанные недостатки метода базисных функций будут устранены, и тогда станет ясно, что такие про- цедуры, применяемые надлежащим образом, обладают широчай- шим кругом возможностей. Литература [1] Courant R. Differential and integral calculus. Vol. I.—2nd ed.—London: Blackie and Son, 1937. [Имеется перевод: Курант Р. Курс дифференциального и интегрального исчисления. Том 1.—4-е изд.—М.: Наука, 1967.] [2] Подробное обсуждение различных имеющихся возможностей можно найти в книге Finlayson В. A. The method of weighted residuals and variational prin- ciples.—New York: Academic Press, 1972. [3] Вывод этой формулы имеется в книге Zienkiewicz О. С. The finite element method.—3rd ed.—New York: McGraw-Hill, 1977. [4] Такие процедуры использования пробных функций впервые были пре- дложены Треффцем в 1926 г. (см., например, Михлин С. Г. Вариационные методы в математической физике.—2-е изд.—М.: Наука, 1970) и часто называ- ются его именем. [5] Подробное обсуждение таких процедур можно найти в книге Zienkie- wicz О. С., Kelly D. W., Bettess P. Marriage a la mode—The best of both worlds ^(finite elements and boundary integrals).—In: Energy methods in finite element analysis. Ed. by R. Glowinski, E. Y. Rodin, О. С. Zienkiewicz.—New York: Wiley-Interscience, 1979. 16] Timoshenko S., Goodier J, N, Theory ol elasticity,—2nd ed.—New 92 Гл. 2. Методы взвешенных невязок York: McGraw-Hill, 1951. [Имеется перевод: Тимошенко С. П., Гудьер Дж., Теория упругости.—2-е изд.—М.: Наука, 1979.] [7] Этот принцип обсуждается в книге Richards Т. Н. Energy methods in stress analysis.—Chichester: Ellis-Horwood, 1977. [8] Strang G., Fix G. J. An analysis of the finite element method.—Eng- lewood Cliffs: Prentice-Hall, 1973. [Имеется перевод: Стренг Г., Фикс Дж. Теория метода конечных элементов.—М.: Мир, 1977.] [9] Fox L., Parker I. B., Chebyshev polynomials in numerical analysis.— New York: Oxford University Press, 1968. Рекомендуемая литература Brebbia С. A., Walker S., Boundary element techniques in engineering.— London: Newnes-Butterworths, 1980. [Имеется перевод: Бреббиа К., Уокер С. Применение метода граничных элементов в технике.—М.: Мир, 1983.] Collatz L. The numerical treatment of differential equations.—Berlin: Springer, 1960. [Имеется перевод нем. изд. 1951 г.: Коллатц Л. Численные методы решения дифференциальных уравнений.—М.: ИЛ, 1953.] Crandall S. H., Engineering analysis.—New York: McGraw-Hill, 1956.