book1989

С а м а р с к и й

А. А., Г у л и н А.

В. Численные методы: Учеб, пособие для

вузов,— М.: Наука.

Гл. ред. физ-мат.

лит., 1989.— 432 с.— ISBN 5-02-013996-3.

-------------------------053(02) - 89

52-89

) Издательство «Н аука*.

П р ед и сл о в и е .........................................................................................................................

8

§

1. Математическое моделирование и вычислительный эксперимент .

.

11

1.

Схема вычислительного эксперимента

(11). 2. Вычислительный алгоритм

(12).

3.

Требования к вычислительным методам

(14).

§

2. Погрешности о к р у г л е н и я ......................................................................................

16

§ 3. Разностные уравнения второго п о р я д к а

.........................................................

25

1. Задача Коши

и краевые

задачи

для разностных уравнений

(25). 2. Однород­

ное разностное

уравнение

второго

порядка с

постоянными

коэффициентами

(26). 3. Однородное разностное уравнение второго порядка с переменными коэф ­

фициентами (28).

4. Неоднородное

разностное

уравнение второго порядка (31).

§

4.

Разностная

аппроксимация

дифференциальных

уравнений . .

.

34

1.

Сетки

и

сеточные

функции

(34).

2.

Разностная

краевая

задача (35). 3. Н е ­

которые разностные тождества (38). 4. Разностная задача на собственные

зн а ­

чения (39). 5.

Свойства собственных

значений

и

собственных

функций

(41).

6. Разрешимость

и

сходимость

разностной задачи

(43).

7. Метод

прогонки

(45).

ЧАСТЬ

II

ЧИСЛЕННЫЕ МЕТОДЫ АЛГЕБРЫ И АНАЛИЗА

Г л а в а

1. Прямые методы решения систем линейных алгебраических урав­

48

нений

.......................................................................................................................................

§

1.

Метод

Гаусса

численного

решения

систем

линейных

алгебраических

49

у р а в н е н и й

.............................................................................................................................

1. Основная

идея

методч

(49).

2. Расчетные

формулы

(51).

3.

Подсчет

числа

действий

(53).

§

2.

Условия

применимости

метода

Г а у с с а .........................................................

54

1. Связь метода Гаусса с

разложением

матрицы

на

множители

(54). 2. Теорема

об /.{/-разложении (55). 3.

Элементарные треугольные матрицы (58).

§ 3. Метод Гаусса

с выбором главного

э л е м е н т а .............................................

60

1. Основная

идея

метода (60). 2. Матрицы перестановок (61). 3. Пример

(62).

4.

Общий

вывод

(65).

5. Д оказательство

теоремы

1

(66). 6.

Вычисление опреде­

лителя (67).

§ 4.

Обращение м а т р и ц ы ........................................................................................................

68

§ 5.

Метод квадратного

к о р н я ...........................................................................................

69

1. Факторизация эрмитовой матрицы (69). 2. Пример (70). 3. Общие расчетные

формулы

(71).

4.

Подсчет числа действий (72).

§ 6.

Обусловленность

систем линейных

алгебраических

уравнений

. .

74

1.

Устойчивость

системы

линейных

алгебраических уравнений

(74). 2. Число

обусловленности

(76).

3.

Полная

оценка

относительной

погрешности

(77).

4. Влияние погрешностей

округления

при

решении

систем

линейных алгебраи ­

Г л а в а

2.

Итерационные

методы

решения

систем линейных

алгебраиче­

ских

у р а в н е н и й ..................................................................................................

......

82

§

1. Примеры и канонический вид итерационных методов решения систем

линейных

алгебраических у р а в н е н и й ................................................................

82

1. Итерационные методы

Якоби

и

Зейделя

(82).

2. Матричная запись методов

Якоби и Зейделя (83). 3. Каноническая форма одношаговых итерационных ме ­

тодов (84)

§ 2.

Исследование сходимости итерационных м е т о д о в ..............................................

86

§ 3. Необходимое и достаточное условие сходимости стационарных итера­

ционных м е т о д о в ..............................................................................................................

90

1.

Введение

(90). 2. Норма матрицы (91). 3. Теорема о сходимости итерацион-

ного метода (92). 4. Продолжение

доказательства

(93).

§

4. Оценки скорости сходимости

стационарных

итерационных

методов .

95

I. Скорость сходимости итерационного метода

(95). 2. Оценки скорости сходи ­

мости в случае симметричных матриц А и В (96). 3. Правила действий с

м ат ­

ричными

неравенствами

(98).

4.

Доказательство

теоремы 1 (100) . 5. Оценка п о ­

грешности в случае несимметричной матрицы

В

(102).

§ 5.

Многочлены Ч е б ы ш е в а

................................................................................................

103

1. Многочлен Чебышева на отрезке [—1,

1] (103).

2. Случай произвольного отрез­

ка

(105).

3.

Д ругая нормировка

многочленов Чебышева (106). 4.

Примеры

при­

менения многочленов Чебышева (107).

§ 6. Итерационные методы с чебышевским

набором параметров .

. .

10&

1.

Явный

итерационный

метод

(109). 2. Численная устойчивость итерационного

метода

с

чебышевским

набором

параметров (112). 3. Неявный

чебышевекпй

итерационный метод (113). 4. Случай, когда точные границы спектра неизвестны

(П4).

§ 7. Итерационные методы вариационного

т и п а ..............................................

115

1.

Метод

минимальных

невязок

(116). 2. Метод минимальных поправок

(118).

3.

Метод

скорейшего

спуска

(119). 4.

Метод

сопряженных градиентов

(120).

5. Минимизация погрешности (121). 6. Выбор итерационных параметров в методе

сопряженных градиентов (122). 7. Оценка погрешности в методе сопряженных

градиентов

(126).

Г л а в а

3.

Интерполирование

и

приближение

ф у н к ц и й ...............................

127

§

1.

Интерполирование

алгебраическими м н огоч л ен ам и ........................................

127

1.

Интерполяционная

формула Л агранж а (127).

2. Интерполяционная

формула

Ньютона

(129).

§ 2. Погрешность и н терполирования

.............................................................................

132

1. Остаточный член интерполяционной формулы (132). 2. Оптимальный выбор

узлов интерполирования

(134).

3.

О сходимости интерполяционного

процесса

(134).

§ 3.

Интерполирование с кратными у з л а м и ..........................................................

136

1.

Интерполяционный

многочлен

Эрмита

(136). 2. Пример (138).

§

4.

Интерполирование

с п л а й н а м и ..................................................................................

140

1. Построение кубического сплайна (141). 2. Сходимость процесса интерполиро­

вания кубическими сплайнами (143).

§ 5.

Другие

постановки

задач

интерполирования и приближения

функций

148

1.

Примеры

(148). 2. О бщая постановка

задачи

интерполирования

(151). 3.

Наи­

лучшее приближение функции, заданной таблично (152) . 4 . Сглаживание сеточ­

ных функций (154).

§ 6. Наилучшие приближения в

гильбертовом

пространстве . . .

.

156

1. Постановка задачи

(156). 2. Сведение

к

алгебраической задаче о

минимуме

квадратичного функционала (157). 3. Следствия (159).

Г л а в а

4.

Численное

интегрирование

и

дифференцирование

.

161

§

1. Примеры

формул численного интегрировани я ............................................

161

1. Введение

(161). 2.

Формула

прямоугольников

(162). 3- Формула

трапеций

(164). 4. Формула Симпсона (165). 5. Апостериорная оценка погрешности мето­

дом Рунге. Автоматический выбор шага интегрирования (168). 6. Экстраполяция

§

2.

Ричардсона

(169).

.

172

Квадратурные формулы интерполяционного тина . . . . .

1. Вывод формул (172). 2. Оценка погрешности

(174). 3. Симметричные форму­

лы (175). 4. Формулы

Ньютона — Котеса. Численная устойчивость

квадратурных

формул

(178).

определенных

и н т е г р а л о в

180

§ 3. Метод

Гаусса вычисления

§ 4. Численное диф ф еренцирование..........................................................................

186

1. Некорректность операции численного дифференцирования (186). 2. Примене­

ние

интерполирования

(188).

Г л а в а

5. Решение

нелинейных

уравнений

и систем

уравнений

.

.

190

§

1. Примеры

итерационных

методов

решения нелинейных

уравнений

.

190

1.

Введение

(190).

2.

Метод

простой итерации

(191).

3.

Метод

Ньютона

(193).

4. Метод секущих (194). 5. Интерполяционные

методы

(194).

6.

Использование

обратной интерполяции

(195).

§ 2. Сходимость

метода

простой

и т е р а ц и и ...........................................................

195

1. Теорема

о

сходимости (195). 2. Метод Эйткена ускорения сходимости (198).

§ 3. Сходимость

метода

Н ь ю т о н а ............................................................................

199

1. Простой вещественный корень (199). 2. Кратные корни (202). 3. Односторон­

ние приближения (203). 4. Комплексный

корень

(205).

§

4.

Итерационные методы

для

систем

нелинейных

уравнений .

.

.

207

1. Общие понятия (207). 2. Сходимость

стационарного

метода

(208).

3. Примеры

итерационных методов

(209).

Г л а в а

6. Численные

методы решения

задачи

Коши

для

обыкновенных

214

дифференциальных

у р а в н е н и й ..................................................................................

§

1.

Исходная

задача

и

примеры численных

методов

ее

решения

.

.

214

1.

Постановка исходной

задачи

(214).

2. Примеры

численных

методов (214).

§ 2.

Методы

Рунге— К у т т а ...............................................................................................

218

1.

О бщая

формулировка

методов. Семейство

методов

второго

порядка

(218).

2. Доказательство сходимости (221). 3.

Методы

третьего

порядка точности

(224).

4. Методы четвертого порядка точности (226).

§ 3.

Многошаговые разностные

м е т о д ы ........................................................................

230

1. Формулировка методов (230). 2. Погрешность аппроксимации многошаговых

методов (231). 3. Устойчивость и сходимость разностных методов (233). 4. При ­

меры многошаговых разностных методов (235).

§

4. Сходимость и оценка погрешности

многошагового разностного метода

236

1. Уравнение

для погрешности (236). 2.

Однородное разностное

уравнение

с по­

стоянными коэффициентами. Частные решения (238). 3. Однородное разностное

уравнение с постоянными коэффициентами. Устойчивость по начальным

д а н ­

ным (240). 4. Оценка решения неоднородного уравнения (213). 5. Оценки по­

грешности разностного метода (244).

§ 5. Численное интегрирование жестких систем обыкновенных дифференци­

альных у р а в н е н и и .....................................................................................................

247

1.

Условно

устойчивые

и

абсолютно

устойчивые

разностные

методы

(247).

2.

Понятие жесткой

системы дифференциальных уравнений (249).

3. Нелиней­

ные

системы

дифференциальных уравнений (251). 4. Специальные определения

устойчивости

(252). 5.

Чисто

неявные разностные методы (255).

ЧАСТЬ

III

РАЗНОСТНЫЕ МЕТОДЫ РЕШЕНИЯ ЗАДАЧ

МАТЕМАТИЧЕСКОЙ ФИЗИКИ

Г л а в а

1. Вводные п о н я т и я ..............................................................................

259

§

1. Примеры

разностных

ап п р ок си м ац и й .............................................................

259

§

2.

Построение

разностных

схем интегро-интерполяционным методом

.

262

1.

Построение разностной

схемы

(262).

§

3.

Исследование аппроксимации и с х о д и м о с т и ..............................................

265

1. Аппроксимация

дифференциального

уравнения (265). 2. Аппроксимация

гра ­

ничного условия (267). 3. Уравнение для погрешности (268) . 4 . Разностные

тож

-

дества и неравенства

(269).

5. Д оказательство

сходимости

(270).

§ 4.

Разностные схемы

для

уравнения

теп л оп роводн ости ..............................

272

1.

Исходная

задача

(272).

2.

Явная

схема

(272).

3.

Неявные

схемы

(276).

4. Уравнения с переменными коэффициентами и нелинейные уравнения (279).

§ 5.

Трехслойные разностные

с х е м ы

......................................................................

283

1. Разностные схемы для уравнения колебаний (283). 2. Трехслопные схемы для

уравнения

теплопроводности

(285).

§ 6.

Основные

понятия

теории

разностных

схем:

аппроксимация, сходи­

286

мость, устойчивость

................................................................................................

1.

Введение

(286).

2.

Погрешность аппроксимации

и

погрешность

схемы

(287).

и

3.

Корректность

разностной схемы. Сходимость. Связь

меж ду

устойчивостью

сходимостью

(290).

5

Г л а в а 2. Принцип максимума для разностных с х е м .....................................

291

§

1. Разностная

аппроксимация задачи Дирихле

для уравнения Пуассона

291

1. Постановка разностной задачи (291). 2. Канонический вид разностного урав ­

нения (292).

§ 2.

Принцип максимума для

разностных схем. Основные теоремы

. .

294

1. Исходные

предположения

(294). 2. Принцип максимума и его

следствия

(295).

3. Теорема сравнения. Устойчивость по граничным

условиям

(298). 4. П риме­

ры (299).

§ 3. Доказательство устойчивости и сходимости разностной задачи Дирих­

300

ле для уравнения П у а с с о н а ....................................................................................

1. Устойчивость по граничным условиям (300). 2.

Устойчивость

по правой

части

и сходимость (302).

§ 4. Примеры применения принципа м а к с и м у м а ..............................................

304

§ 5. Монотонные разностные схемы для уравнений второго порядка, содер­

жащих первые производные ..............................................................................

308

Г л а в а 3. Метод разделения

п ер е м е н н ы х ...................................................................

310

§

1.

Разностная

задача на собственные значения

.............................................

311

1. Оператор

второй разностной производной (311).

2.

Задача на

собственные зн а ­

чения (312).

3. Свойства собственных значений

и

собственных

функций

(313).

ратора Л а п л а с а

.....................................................................................................

317

1. Самосопряженность (317). 2. Оценка собственных чисел. Положительность

оператора (318).

§

3.

Исследование

устойчивости и сходимости схемы с весами для урав­

нения теплопроводности ......................................................................................

320

1. Исходная задача и разностная схема (320). 2. Устойчивость схемы по

н ачаль ­

ным данным (322). 3.

Устойчивость по правой части и сходимость (324).

4.

С хе­

ма с весами для двумерного уравнения теплопроводности (326). 5. Асимптотиче­

ская устойчивость

(328).

§ 4.

Решение разностного

уравнения второго порядкаметодом

Фурье .

332

§ 5.

Быстрое дискретное преобразование Ф у р ь е ..............................................

334

§ 6.

Решение разностного уравнения Пуассона с использованием быстрого

преобразования

Ф у р ь е ......................................................................................

337

Г л а в а

4. Теория

устойчивости разностных с х е м .............................................

339

§

1.

Разностные схемы

как операторные у р а в н е н и я ..................................

339

1. Представление разностных схем в

виде операторных уравнений (339).

2.

Кор-

ректность операторных уравнений (342). 3. Операторы первой разностной произ­

водной (347).

§

2.

Канонический

вид

и

условия

устойчивости

двуслойныхразностных

с х е м ............................................................................................................................

349

1.

Канонический

вид

двуслойных

разностных схем

(349). 2, Устойчивость

р а з ­

ностных схем

(351),

3.

Теоремы

об

устойчивости

по

начальным данным

(354).

4. Несамосопряженные разностные схемы (359).

§ 3.

Канонический

вид

и

условия

устойчивости трехслойных

разностных

с х е м ..........................................................................................................................

362

1. Канонический вид (362). 2. Эквивалентность трехслойной схемы двуслойной

(363). 3. Устойчивость

по

начальным

данным (364). 4. Примеры (366).

§

4. Об экономичных методахрешениямногомерных нестационарных

задач

математической

физики ...................................................................................

369

I.

Недостатки

обычных

разностных

методов (369). 2. Пример метода перемен­

ных направлений (372). 3. Абсолютная устойчивость продольно-поперечной

схе­

мы (373). 4. Понятие суммарной аппроксимации (376).

Г л а в а

5. Прямые

и итерационные

методы решения сеточных

уравнений

378

§

1. Модельная з а д а ч а

............................................................................................

378

1. Введение (378). 2.

Модельная задача (379). 3.

Применение методов

Якоби и

Зейделя (381). 4. Метод

верхней релаксации (384).

§

2. Применение

явного

итерационного метода

с

оптимальнымнабором

п а р а м е т р о в ............................................................................................................

389

§ 3.

Попеременно-треугольный

итерационный м е т о д ........................................

394

1. Алгебраическая теория (394). 2. Применение к модельной задаче (398).

3. П о ­

переменно-треугольный метод с чебышевскими

итерационными

параметрами

§ 4.

(401). 4. Модифицированный попеременно-треугольный итерационный метод (402).

Итерационный

методпеременных

н а п р а в л ен и й ...............................................

404

1. Формулировка

метода и

исследование сходимости (404). 2.

Пример

(406).

§ 5.

3. Случай прямоугольной области (408).

411

Метод матричной п р о г о н к и ................................................................................

1. Введение (411). 2. Запись разностного уравнения Пуассона в виде системы

векторных уравнений (412). 3. Алгоритм матричной прогонки (414). 4. Устойчи­

§ 6.

вость матричной прогонки (415).

418

Метод р е д у к ц и и .............................................................................................................

1. Вывод основных

формул

(418). 2.

Обращение

матриц (421).

3. Вычисление

правых частей (423). 4. Формулировка

и обсуждение алгоритма (424).

Список литературы

. . . .

.

.................................................... 426

Предметный у к а з а т е л ь ...........................................................................................................

428

Ти х о н о в А.

Н.,

К о с т о м а р о в Д. П. Вводные лекции по

прикладной математике.— М.: Наука, 1984.

С а м а р с к и й

А. А. Введение в численные методы.— 2-е изд.—

М.: Наука, 1987.

Предполагается, что одновременно с изучением данного курса

читатель овладевает

навыками решения задач с помощью ЭВМ,

найти в книгах:

А. А. Теория

разностных схем,—2-е изд.—М.:

С а м а р с к и й

Наука, 1983.

А. А., Н и к о л а е в Е. С. Методы

решения

се­

С а м а р с к и й

точных уравнений,—М.: Наука, 1978.

методы

ре­

С а м а р с к и й

А. А., По п о в

Ю. П. Разностные

шения задач газовой динамики,—2-е изд.—М.: Наука, 1980.

Авторы приносят глубокую благодарность декану факультета

вычислительной

математики и

кибернетики МГУ

академику