Введение в вычислительную математику

Рябенький В.С.

Введение в

вычислительную

м атем атику

МОСКВА

ФИЗМАТЛИТ ®

УДК 519.6 (075.8)
ББК 22.19
С 32

А в т о р с к и й к о л л е к т и в :
Р я б е н ь к и й В. С.

Введение
в
вычислительную
математику.
—
3-е изд.,
испр.
и
доп. — М.: ФИЗМАТЛИТ, 2008. — 288 с. — (Физтеховский учебник). —
ISBN 978-5-9221-0926-0.

В книге изложены основные понятия и идеи, используемые для преобразования математических моделей к виду, удобному для вычисления с помощью компьютера. Изложение ведется на материале вычислительных задач
математического анализа, алгебры и дифференциальных уравнений. Впервые
в учебной литературе отражен метод разностных потенциалов для численного
решения краевых задач математической физики.
Для студентов и преподавателей механико-математических и физических
факультетов университетов, МФТИ, МИФИ, технических вузов.
Рекомендовано Учебно-методическим объединением высших учебных заведений Российской Федерации по образованию в области прикладных математики и физики в качестве учебного пособия для студентов высших учебных
заведений по направлению «Прикладные математика и физика».

ISBN 978-5-9221-0926-0

c⃝ ФИЗМАТЛИТ, 2000, 2008

c⃝ Коллектив авторов, 2000, 2008

ПРЕДИСЛОВИЕ К ТРЕТЬЕМУ ИЗДАНИЮ

Настоящее издание отличается от двух предыдущих (1994 и 2000)
тем, что добавлено изложение идеи построения вычислительных схем
метода конечных элементов на базе проекционного метода Галёркина
(гл. 11, § 2). Кроме того, полностью переработана гл. 13, дающая представление о методе разностных потенциалов и совпадающая теперь в
основном с введением в монографию [17].
Заметим еще, что цикл сопровождающих учебник компьютерных
учебных демонстрационных работ, о котором говорилось в предисловии
к первому изданию, к настоящему времени существенно развит и издан
в виде книги [29].

2007 г.
В.С. Рябенький

ПРЕДИСЛОВИЕ К ПЕРВОМУ ИЗДАНИЮ

Предлагаемая книга соответствует вводному полугодовому курсу вычислительной математики для студентов Московского физикотехнического института, различные варианты которого более двадцати
лет читает автор. Книга адресована студентам технических вузов различного профиля.
Цель книги — изложить достаточно стабильные и общие понятия и идеи, относящиеся к преобразованию математических моделей
различных прикладных задач к виду, удобному для вычисления их
решений с помощью компьютеров. Изучение книги должно давать возможность сравнительно легко доучиваться для работы в разнообразных
и быстро развивающихся конкретных областях. Общая методология
излагается и иллюстрируется в книге на материале численных методов
математического анализа, алгебры и дифференциальных уравнений,
поскольку эти методы лучше развиты, содержат достаточно совершенные алгоритмы и часто применяются в разнообразных конкретных
прикладных задачах.
Наряду с традиционным для учебной литературы по вычислительной математике материалом книга дает представление о граничных
уравнениях с проекторами и методе разностных потенциалов для их
численного решения, а также содержит изложение локальных формул
гладкого восполнения функций.

Предисловие к первому изданию

При изложении метода конечных разностей использована книга
С.К. Годунова и В.С. Рябенького «Разностные схемы».
Структура книги допускает различную глубину изучения материала. Это достигается расположением материала и подбором задач.
Для более полного и глубокого изучения многих вопросов, освещенных в учебнике, можно воспользоваться книгами К.И. Бабенко [1],
Н.С. Бахвалова, Н.П. Жидкова и Г.М. Кобелькова [2], С.К. Годунова
и В.С. Рябенького [5, 6], Н.Н. Калиткина [9], О.В. Локуциевского
и М.Б. Гаврикова [11], Г.И. Марчука [13], А.А. Самарского [19],
А.А. Самарского и Е.С. Николаева [21], а также другими книгами и
журнальной литературой, указанными в тексте.
Отметим еще, что изучение книги можно сделать более наглядным и увлекательным, если воспользоваться предназначенным для
этого циклом компьютерных учебных демонстрационно-лабораторных
работ [29]. Этот цикл создан сотрудниками кафедры вычислительной
математики МФТИ В.Д. Ивановым, П.Н. Коротиным, В.И. Косаревым,
И.Б. Петровым (руководитель работ), В.Б. Пироговым, В.С. Рябеньким
(научный руководитель), Д.С. Северовым, А.Г. Тормасовым, С.В. Устюжниковым. В программной реализации цикла участвовали студенты
В.В. Бойков, Д.Л. Будько, К.Б. Бухаров, А.Ю. Езерский, А.Б. Константинов, С.А. Корытник, Ю.П. Кравченко, Ю.Д. Крикунов, Д.В. Лунев,
В.А. Торгашов, А.А. Терехин, Г.Л. Химичев.
В заключение автор сердечно благодарит академика О.М. Белоцерковского, который в момент создания кафедры вычислительной
математики МФТИ поручил ему чтение первого обязательного общего
курса вычислительной математики. Олег Михайлович неоднократно
обсуждал с автором цели курса в условиях физтеха и соответствующий
этим целям характер курса. Подготовка и чтение лекций оказались
началом работы автора над предлагаемой книгой.
Автор сердечно благодарит также всех своих коллег по работе
в МФТИ и особенно В.В. Демченко, В.Д. Иванова, В.И. Косарева,
В.Я. Митницкого,
Н.П. Онуфриеву,
И.Б. Петрова,
В.Б. Пирогова,
Л.М. Стрыгину,
Р.П. Федоренко,
А.С. Холодова
и
Л.А. Чудова
за
многолетнее сотрудничество, оказавшее влияние на книгу.
Автор сердечно благодарит своего коллегу К.В. Брушлинского, прочитавшего книгу в рукописи, за ряд полезных замечаний.
Автор выражает глубокую благодарность профессору К.И. Бабенко
и профессору О.В. Локуциевскому, с которыми также плодотворно обсуждал вопросы преподавания.

1987 г.
В.С. Рябенький

ВВЕДЕНИЕ

Современная вычислительная математика ориентирована на использование компьютеров для прикладных расчетов. Любые математические приложения начинаются с построения модели явления (изделия,
действия, ситуации или другого объекта), к которому относится изучаемый вопрос. Классическими примерами математических моделей
могут служить определенный интеграл, уравнение колебаний маятника, уравнение теплообмена, уравнения упругости, уравнения электромагнитного поля и другие уравнения математической физики. Назовем еще для контраста модель формальных рассуждений — алгебру
Буля.
Основополагающими средствами изучения математических моделей
являются аналитические методы: получение точных решений в частных
случаях (например, табличные интегралы), разложения в ряды. Определенную роль издавна играли приближенные вычисления. Например,
для вычисления определенного интеграла использовались квадратурные формулы.
Появление в середине XX века электронных вычислительных машин (компьютеров) радикально расширило возможности приложения
математических методов в традиционных областях (механике, физике,
технике) и вызвало бурное проникновение математических методов в
нетрадиционные области (управление, экономику, химию, биологию,
психологию, лингвистику, экологию и т. п.).
Компьютер дает возможность запоминать большие (но конечные)
массивы чисел и производить над ними арифметические операции и
сравнения с большой (но конечной) скоростью по заданной вычислителем программе. Поэтому с помощью компьютера можно реализовывать
только те математические модели, которые описываются конечными
наборами чисел, и использовать конечные последовательности арифметических действий, а также сравнений чисел по величине (для
автоматического управления дальнейшими вычислениями).
В
традиционных
областях
математическими
моделями
служат
функции, производные, интегралы, дифференциальные уравнения. Для
использования компьютеров эти исходные модели надо приближенно
заменить такими, которые описываются конечными наборами чисел
с
указанием
конечных
последовательностей
действий
(конечных
алгоритмов) для их обработки. Например, функцию следует заменить
таблицей; производную

0

6
Введение

заменить приближенной формулой

;

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

§ 1. Дискретизация
7

Благодаря компьютерам стало возможным рассматривать вероятностные модели, требующие большого числа пробных расчетов, имитационные модели, которые отражают моделируемые свойства объекта
без упрощений (например, функциональные свойства телефонной сети).
Разнообразие задач, где могут быть использованы компьютеры, очень
велико. Для решения каждой задачи нужно знать многое, связанное
именно с этой задачей. Естественно, этому нельзя научиться впрок.
Целью этой книги является сообщение тех основных понятий,
идей и методов, владение которыми позволяет сравнительно быстро
научиться работать в конкретных областях. Это реализуется на материале вычислительных задач алгебры, математического анализа, дифференциальных уравнений, поскольку здесь методы хорошо развиты и
употребляются в далеких друг от друга областях.
Назовем некоторые общие понятия и идеи, которые требуют внимания и наполняются конкретным содержанием в зависимости от задачи,
которую предстоит решать с помощью компьютера. Это — дискретизация задачи; обусловленность задачи; погрешность численного метода;
вычислительная устойчивость алгоритма; сравнение алгоритмов по
полноте используемой ими входной информации, по объему используемой памяти и числу арифметических действий. Алгоритмы могут обладать возможностью распараллеливания для одновременного проведения
вычислений на многопроцессорном компьютере. Среди основных методов вычислительной математики одним из плодотворных является комбинированное использование аналитических и компьютерных средств.
Здесь, во введении, мы предварительно познакомим читателя с перечисленными понятиями. Это даст некоторое общее представление о
предмете вычислительной математики и подготовит к изучению дальнейшего материала.

§ 1. Дискретизация

Пусть требуется найти приближенное решение какой-либо задачи,
в которой в качестве входных данных участвует какая-либо функция

, определенная на всем (бесконечном) множестве точек отрезка
0
1. Значения этой функции при каждом фиксированном
можно получить измерениями или вычислениями. Для запоминания
этой функции в памяти компьютера необходимо приближенно описать
ее таблицей значений на некотором конечном множестве отдельных
точек
0,
1,
,
. Это — простейший пример дискретизации задачи: от задачи запоминания функции на отрезке
0, 1мы перешли к
задаче запоминания таблицы значений на дискретном множестве точек

0,
1,
,
из этого отрезка.
Пусть функция
имеет достаточное число производных, а нам
требуется вычислить ее производную
в данной точке
. Задачу
отыскания

0

,

Введение

содержащую предельный переход, можно заменить приближенно задачей вычисления по одной из формул

,
(1)

,
(2)

2 (3)

Для замены производной
можно воспользоваться формулой

2 2

4Все эти формулы уточняются при уменьшении
, а при каждом фиксированном
определены для конечных наборов значений функции и
используют только арифметические операции. Эти формулы — примеры
дискретизации задачи о вычислении производных
,
.
Рассмотрим краевую задачу

2

2

2

,
0
1,

02,
13,

5об отыскании функции
, определенной на отрезке 0
1. Для
построения приближенной дискретной модели этой задачи осуществим
следующие два шага.
1) Разобьем отрезок 0
1 на
равных частей длины
1,
а вместо функции
будем искать набор значений
0,
1, ...,
этой
функции в точках
(0, 1,
,
). В точках
(1, 2,
,
1) заменим производную
приближенно по формуле (4) и
получим

1

2 1

2

2

,
1, 2,
,
162) Кроме того, в силу граничных условий (5) положим

0

2,
37Система
1линейных уравнений (6), (7) относительно того же
числа неизвестных
0,
1,
,
является дискретным аналогом задачи (5).
Есть основания полагать, что с ростом
решение задачи (6), (7)
есть все более точная таблица значений решения задачи (5) (в дальнейшем это будет показано).
Обозначим исходную (континуальную) краевую задачу через
,
а дискретную краевую задачу (6), (7) через
. Тогда можно сказать,
что задаче
мы сопоставили бесконечную последовательность дискретных задач
(2, 3,
).

§ 2. Обусловленность
9

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

— какие-нибудь две последовательности таких моделей, причем вычисление решений дискретных задач
,
требует равных
затрат. Тогда предпочтение надо отдать тому способу дискретизации,
при котором решение дискретной задачи может служить решением
исходной задачи с заданной точностью при меньшем значении
.
Бывает, что из двух, казалось бы, равноценных способов дискретизации
и
один при возрастании
дает все более точное приближение к решению континуальной задачи
, а другой
приводит к «приближенному решению» задачи, которое с ростом
теряет какое-либо сходство с искомым решением. С этой ситуацией и
способами ее преодоления мы встретимся в части III книги.

Задача

Пусть
имеет ограниченные производные до требуемого порядка.
Показать, что погрешности приближенных формул (1)–(4) суть величины
соответственно
,
,
2

,
2

.

§ 2. Обусловленность

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

100Фиксируем произвольно
0

0
0

1и делаем приближенное
измерение
0 концентрации
0

0

, получив

0

0

10
Введение

Задача состоит в определении концентрации
в произвольный
момент времени
из отрезка 0
1.
Если бы число
0

0

было известно точно, то можно было бы
указать точную формулу

0

0

для концентрации. Но мы знаем лишь приближенное значение
0

0
числа
0. Поэтому вместо
0

100

мы можем указать лишь
приближенную формулу
0

100

. Очевидно, что погрешность

выражается формулой

0

0

100

,
0
1Допустим, нам нужно произвести замер
0 с такой точностью
Æ,

0

0

Æ, чтобы гарантировать некоторую заданную точность
0
всюду на отрезке 0
1, т. е. гарантировать оценку

,
0
1Очевидно,
01

110

0

1010

.

Отсюда получаем следующее требование к точности
Æ измерения
0:

Æ
1010

Пусть измерение
0 производится в момент
0

0. Тогда требование
к точности
Æ измерения будет в
10 раз, т. е. в тысячи раз, выше,
чем требуемая гарантированная точность
результата. Ответ весьма
чувствителен к погрешности задания входных данных, т. е.
0, и задача
плохо обусловлена.
Если измерение производить при
0

1, то можно взять
Æ
,
т. е. достаточно измерения с гораздо меньшей точностью, чем в случае

0

0, и задача хорошо обусловлена.

Задачи

1. На каком из двух отрезков,
1 2, 1 или
1, 0 , задача вычисления
1
1
по заданному
лучше обусловлена?

2. Пусть
2
1. Можно написать также
2
1 1. Какая из
двух формул чувствительнее к погрешности при приближенном задании

2 в
виде конечной десятичной дроби?
У к а з а н и е. Сравнить модули производных функций
1 и
 1 1.

§ 3. Погрешность

Во всякой вычислительной задаче по некоторым входным данным
задачи требуется найти ответ на поставленный вопрос. Если ответ на
вопрос задачи можно дать с абсолютной точностью, то погрешность
отсутствует. Но обычно удается найти ответ лишь с некоторой погрешностью. Погрешность вызывается тремя причинами.

§ 3. Погрешность
11

Первая причина — некоторая неопределенность при задании входных данных, которая приведет к соответствующей неопределенности
в ответе: ответ может быть указан лишь с некоторой погрешностью,
которая носит название неустранимой погрешности.
Вторая причина: если мы ликвидируем неопределенность в задании
входных данных, фиксировав какие-либо входные данные, а затем
будем вычислять ответ с помощью какого-нибудь приближенного метода, то найдем не в точности тот ответ, который соответствует этим
фиксированным входным данным. Возникает погрешность, связанная
с выбором приближенного метода вычислений.
Третья причина: сам выбранный нами приближенный метод реализуется неточно из-за погрешностей округлений при вычислениях на
реальном компьютере.
Погрешность результата складывается, таким образом, из неустранимой погрешности, погрешности метода и погрешности округлений.
Проиллюстрируем эти понятия.
1. Неустранимая погрешность. Пусть задача состоит в вычислении значения
некоторой функции
при некотором
.
Число
и функция
служат входными данными задачи, а число

— решением.
Пусть
функция
известна
лишь
приближенно,
например,

, причем известно лишь, что
отличается от
не
более, чем на некоторую величину
0:

1Пусть значение аргумента
получается приближенным измерением, в результате которого получаем некоторое
, причем известно
лишь, что
лежит в пределах

Æ
Æ,
2где
Æ
0 — число, характеризующее точность измерения.
Из рис. 1 видно, что величиной
может оказаться любая
точка отрезка
,
, где
Æ
,
Æ
. Понятно,

O

y

x
t*å
x
sin

t*+t*

b

a

å
x
sin

x
sin

Рис. 1

Введение

что, приняв за приближенное значение числа
любую точку
отрезка
,
, можно гарантировать оценку погрешности

3Эту оценку погрешности нельзя существенно уменьшить при имеющихся неполных входных данных. Самая малая погрешность, которую
можно гарантировать, получается, если принять за
середину отрезка

,
, положив

опт

2

Из рис. 1 видно, что гарантирована оценка

опт

2

4Это неравенство станет точным равенством, если
или
.
Таким образом,
2 и есть та неустранимая (неуменьшаемая)
погрешность, которую можно гарантировать при имеющихся неопределенных входных данных в случае самого удачного выбора приближенного решения
опт.
Оптимальная оценка (4) ненамного лучше оценки (3). Поэтому мы
не отступим от здравого смысла, если о любой точке
,
, а не
только о точке
опт, условимся говорить, что она есть приближенное
решение задачи вычисления числа
, найденное с неустранимой
погрешностью, а вместо
2 из (4) за величину неустранимой
погрешности примем (условно) число
.
2. Погрешность метода. Положим
. Число
принадлежит отрезку
,
и является неулучшаемым приближенным решением
задачи, погрешность которого удовлетворяет оценке (3) и неустранима.
Точка
выбрана среди других точек отрезка
,
, потому что
она задается удобной для дальнейшей работы формулой.
Для вычисления числа
на компьютере воспользуемся
разложением функции
в ряд:

3

3 5

5 5Для вычисления
можно воспользоваться одним из приближенных выражений

1

,

2

3

3 ,
. . . . . . . . . . . . . . . . . . . . . . .

1

11

2 1

2 1 6Выбирая для приближенного вычисления
одну из формул (6), мы
тем самым выбираем метод вычисления.
Величина
есть погрешность метода вычислений.