Вычислительные методы

Министерство образования и науки Российской Федерации

ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
СИСТЕМ УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ (ТУСУР)

А. А. Мицель

ВЫЧИСЛИТЕЛЬНЫЕ МЕТОДЫ

Учебное пособие

Рекомендовано Сибирским региональным учебно-методическим центром
высшего профессионального образования для межвузовского
использования в качестве учебного пособия для студентов, обучающихся
по направлениям подготовки бакалавров 230100.62 «Информатика
и вычислительная техника» и 230700.62 «Прикладная информатика»

Томск
«Эль Контент»
2013

УДК
519.6(075.8)
ББК
22.19я73
М 701

Рецензенты:
Старченко А. В., докт. физ.-мат. наук, профессор, зав. кафедрой вычислительной
математики и компьютерного моделирования Томского государственного
университета;
Кочегуров А. И., доцент кафедры прикладной математики Томского
политехнического университета.

Мицель А. А.
М 701
Вычислительные методы : учебное пособие / А. А. Мицель. — Томск : Эль
Контент, 2013. — 198 с.

ISBN 978-5-4332-0121-7

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

УДК
519.6(075.8)
ББК
22.19я73

ISBN 978-5-4332-0121-7
©
Мицель А. А., 2013
©
Оформление.
ООО «Эль Контент», 2013

ОГЛАВЛЕНИЕ

Введение
6

1
Погрешности вычислений
11
1.1
Источники погрешностей . . . . . . . . . . . . . . . . . . . . . . . . . . .
11
1.2
Приближенные числа
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
13
1.3
Погрешности арифметических действий . . . . . . . . . . . . . . . . . .
18
1.4
Обратная задача теории погрешностей . . . . . . . . . . . . . . . . . . .
23

2
Корректность и обусловленность вычислительных задач
и алгоритмов
25
2.1
Постановка вычислительной задачи
. . . . . . . . . . . . . . . . . . . .
25
2.2
Обусловленность вычислительной задачи . . . . . . . . . . . . . . . . .
27
2.3
Корректность вычислительных алгоритмов . . . . . . . . . . . . . . . .
28
2.4
Требования к вычислительным алгоритмам . . . . . . . . . . . . . . . .
31
2.4.1
Требования к абстрактным алгоритмам . . . . . . . . . . . . . .
32
2.4.2
Требования к программным реализациям алгоритмов . . . . .
33
2.4.3
Противоречивость требований . . . . . . . . . . . . . . . . . . .
34

3
Приближенное решение нелинейных уравнений с одной переменной
36
3.1
Локализация корней . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
36
3.2
Обусловленность задачи вычисления корня . . . . . . . . . . . . . . . .
38
3.3
Метод дихотомии . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
40
3.4
Метод Ньютона . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
41
3.4.1
Модификации метода Ньютона . . . . . . . . . . . . . . . . . . .
44
3.4.2
Уточнение метода Ньютона для случая кратного корня . . . .
45
3.5
Метод хорд . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
45
3.6
Метод итераций . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
49
3.7
Обусловленность методов вычисления корня . . . . . . . . . . . . . . .
52

4
Численные методы решения систем линейных алгебраических
уравнений
56
4.1
Постановка задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
56
4.2
Нормы векторов и матриц . . . . . . . . . . . . . . . . . . . . . . . . . . .
58
4.3
Абсолютная и относительная погрешности векторов . . . . . . . . . .
60
4.4
Обусловленность задачи решения систем линейных алгебраических
уравнений . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
60
4.5
Прямые методы решения систем линейных алгебраических
уравнений . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
63

Оглавление

4.5.1
Метод Гаусса . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
63
4.5.2
QR-алгоритм решения СЛАУ . . . . . . . . . . . . . . . . . . . .
66
4.5.3
Метод ортогонализации
. . . . . . . . . . . . . . . . . . . . . . .
69
4.5.4
Метод Халецкого . . . . . . . . . . . . . . . . . . . . . . . . . . . .
71
4.6
Итерационные методы решения СЛАУ . . . . . . . . . . . . . . . . . . .
72
4.6.1
Метод простой итерации решения СЛАУ . . . . . . . . . . . . .
72
4.6.2
Подготовка системы для итерационного процесса . . . . . . .
73
4.6.3
Метод Зейделя . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
74
4.7
Оценка погрешности метода простой итерации и процесса Зейделя .
75
4.8
Процесс Зейделя для нормальной системы . . . . . . . . . . . . . . . .
76
4.9
Метод прогонки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
77
4.10 Решение переопределенной системы линейных уравнений . . . . . .
78
4.11 Вычисление определителей . . . . . . . . . . . . . . . . . . . . . . . . . .
79
4.11.1 Свойства определителей . . . . . . . . . . . . . . . . . . . . . . .
79
4.11.2 Вычисление определителей методом Гаусса . . . . . . . . . . .
80
4.11.3 Вычисление определителей методом Халецкого
. . . . . . . .
81
4.12 Вычисление обратной матрицы . . . . . . . . . . . . . . . . . . . . . . .
81

5
Вычисление собственных значений и собственных векторов матриц
83
5.1
Постановка задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
83
5.2
Преобразование подобия
. . . . . . . . . . . . . . . . . . . . . . . . . . .
85
5.3
Локализация собственных значений . . . . . . . . . . . . . . . . . . . . .
86
5.4
Обусловленность задачи вычисления собственных значений
и собственных векторов . . . . . . . . . . . . . . . . . . . . . . . . . . . .
88
5.5
Степенной метод вычисления максимального собственного числа . .
89
5.6
QR-алгоритм вычисления собственных чисел
. . . . . . . . . . . . . .
90
5.7
Метод обратных итераций вычисления собственных векторов . . . .
91
5.8
Метод Данилевского . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
92
5.8.1
Вычисление собственных чисел
. . . . . . . . . . . . . . . . . .
92
5.8.2
Вычисление собственных векторов
. . . . . . . . . . . . . . . .
96

6
Приближ¨eнное решение систем нелинейных уравнений
99
6.1
Постановка задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
99
6.2
Локализация корней . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
6.3
Метод Ньютона . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
6.3.1
Модифицированный метод Ньютона . . . . . . . . . . . . . . . . 105
6.4
Метод итераций . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
6.4.1
Достаточные условия сходимости процесса итераций . . . . . 106

7
Приближение функций
111
7.1
Постановка задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
7.2
Интерполяция обобщенными многочленами . . . . . . . . . . . . . . . 113
7.3
Полиномиальная интерполяция. Многочлен Лагранжа . . . . . . . . . 116
7.4
Погрешность интерполяции
. . . . . . . . . . . . . . . . . . . . . . . . . 118
7.5
Минимизация оценки погрешности . . . . . . . . . . . . . . . . . . . . . 119
7.6
Интерполяционная формула Ньютона для равномерной сетки . . . . 120
7.7
Интерполяционная формула Ньютона для неравномерной сетки . . . 125

Оглавление
5

7.8
Чувствительность интерполяционного полинома к погрешностям
входных данных . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
7.9
Интерполяция с помощью «скользящего» полинома
. . . . . . . . . . 128
7.10 Кусочно-полиномиальная аппроксимация . . . . . . . . . . . . . . . . . 128
7.11 Тригонометрическая интерполяция . . . . . . . . . . . . . . . . . . . . . 129
7.12 Приближение сплайнами . . . . . . . . . . . . . . . . . . . . . . . . . . . 130
7.12.1 Линейные сплайны . . . . . . . . . . . . . . . . . . . . . . . . . . 130
7.12.2 Параболические сплайны
. . . . . . . . . . . . . . . . . . . . . . 131
7.12.3 Кубические сплайны
. . . . . . . . . . . . . . . . . . . . . . . . . 132
7.13 Интегральное квадратичное аппроксимирование функций на отрезке 134
7.14 Ортогональные системы функций . . . . . . . . . . . . . . . . . . . . . . 136
7.14.1 Ортогональная система тригонометрических функций
. . . . 140
7.14.2 Полиномы Лежандра . . . . . . . . . . . . . . . . . . . . . . . . . 142

8
Численное дифференцирование функций
146
8.1
Простейшие формулы численного дифференцирования
. . . . . . . . 146
8.2
Общий способ получения формул численного дифференцирования . 149
8.3
Численное дифференцирование на основе кубических сплайнов . . . 153
8.4
Обусловленность формул численного дифференцирования . . . . . . 154

9
Численное интегрирование функций
158
9.1
Квадратурные формулы Ньютона—Котеса . . . . . . . . . . . . . . . . . 159
9.2
Формула трапеций . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160
9.3
Формула Симпсона . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162
9.4
Квадратурная формула Гаусса . . . . . . . . . . . . . . . . . . . . . . . . 165
9.5
Квадратурная формула Чебышева . . . . . . . . . . . . . . . . . . . . . . 166
9.6
Формула прямоугольников . . . . . . . . . . . . . . . . . . . . . . . . . . 167
9.7
Обусловленность квадратурных формул . . . . . . . . . . . . . . . . . . 169
9.8
Правило Рунге оценки погрешности квадратурных формул . . . . . . 170

10 Численные методы решения обыкновенных дифференциальных
уравнений
171
10.1 Постановка задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171
10.2 Метод Эйлера . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174
10.3 Методы Рунге—Кутты . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176
10.4 Решение систем дифференциальных уравнений . . . . . . . . . . . . . 178
10.5 Решение дифференциального уравнения n-го порядка . . . . . . . . . 179
10.6 Контроль погрешности . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181

Литература
183

Глоссарий
185

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

ВВЕДЕНИЕ

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Математическое моделирование представляет собой метод исследования объектов и процессов реального мира с помощью их
приближенных описаний на языке математики — математических моделей.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

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

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

Конечность скорости распространения сигнала — 300000 км/с является существенным ограничением роста быстродействия однопроцессорных ЭВМ. Поэтому,
наряду с созданием многопроцессорных ЭВМ, все большую роль в повышении
производительности ЭВМ приобретают численные методы.

Введение
7

Основные этапы решения инженерной задачи

Решение серьезной инженерной задачи с использованием компьютера — довольно длительный и сложный процесс. Условно его можно разбить на ряд последовательных этапов. Выделим следующие этапы [1, 2]:
1) постановка проблемы и построение математической модели;

2) постановка вычислительной задачи и выбор численного метода;

3) алгоритмизация и программирование;

4) счет по программе и интерпретация результатов;

5) использование результатов и коррекция математической модели.
1. Постановка проблемы и построение математической модели. Первоначально прикладная задача бывает сформулирована в самом общем виде: исследовать
некоторое явление, спроектировать устройство, обладающее заданными свойствами, дать прогноз поведения некоторого объекта в определенных условиях и т. д.
На данной стадии происходит конкретизация постановки задачи, и первостепенное
внимание при этом уделяется выяснению цели исследования. Неудачная постановка проблемы может привести к тому, что длительный и дорогостоящий процесс
решения задачи завершится получением бесполезных или тривиальных результатов.
Для последующего анализа исследуемого явления или объекта необходимо
дать его формализованное описание на языке математики, т. е. построить математическую модель. Часто имеется возможность выбора модели среди известных
и принятых для описания соответствующих процессов, но нередко требуется и существенная модификация известной модели, а иногда возникает необходимость
в построении принципиально новой модели.
Удачный выбор математической модели является решающим шагом к достижению цели. Одна из существенных трудностей такого выбора состоит в объективном противоречии между желанием сделать описание явления как можно более
полным (что приводит к усложнению модели) и необходимостью иметь достаточно простую модель (чтобы была возможность реализовать ее на компьютере).
Важно, чтобы сложность математической модели соответствовала сложности поставленной проблемы. Если поставленных целей можно достигнуть с помощью
более простой математической модели, то следует ей воспользоваться.
2. Постановка вычислительной задачи и выбор численного метода. На основе
принятой математической модели формулируют вычислительную задачу и проводят предварительное исследование свойств вычислительной задачи. Большое внимание уделяют анализу корректности ее постановки, т. е. выяснению вопросов существования и единственности решения, а также исследованию устойчивости решения задачи к погрешностям входных данных.
На этом этапе полезным оказывается изучение упрощенных постановок задачи. Иногда для них удается провести исследование, позволяющее понять основные
особенности исходной вычислительной задачи. Особую ценность имеют различные аналитические решения; они оказываются полезными не только для анализа
явления, но и как основа для тестовых испытаний на этапе отладки программы.
Далее, для решения вычислительной задачи на компьютере требуется использование численных методов.

Введение

Часто решение инженерной задачи сводится к последовательному решению
стандартных вычислительных задач, для которых разработаны эффективные численные методы. В этой ситуации происходит либо выбор среди известных методов,
либо их адаптация к особенностям решаемой задачи. Однако если возникающая
вычислительная задача является новой, то не исключено, что для ее решения не
существует готовых методов.
Для решения одной и той же вычислительной задачи обычно может быть использовано несколько методов. Необходимо знать особенности этих методов, критерии, по которым оценивается их качество, чтобы выбрать метод, позволяющий
решить проблему наиболее эффективным образом.
3. Алгоритмизация и программирование. Этап поиска и разработки алгоритма
решения называют алгоритмизацией. Здесь могут использоваться как математические формулы и блок-схемы, так и словесные описания алгоритмов. Во многих
случаях вслед за построением алгоритма выполняют так называемый контрольный
просчет — грубую прикидку ожидаемых результатов, которые используются затем
для анализа полученного решения.
Затем алгоритм решения задачи записывается на языке, понятном ЭВМ. Это —
этап программирования. В настоящее время для вычислительных задач наиболее
широко используются алгоритмические языки СИ++ и ФОРТРАН. В простейших
случаях может оказаться, что на этом этапе вовсе и не составляется новая программа для ЭВМ, а дело сводится, например, к использованию имеющегося математического обеспечения ЭВМ.
Вопросы разработки программного продукта выходят за рамки данного пособия. Подчеркнем лишь, что большинство пользователей справедливо предпочитает
строить свои программы из готовых модулей и использовать стандартные программы, реализующие те или иные алгоритмы.
После написания программы с помощью компьютера выявляют и исправляют
ошибки в программе.
Как правило, начинающий пользователь компьютера убежден, что ошибок
в составленной им программе нет или же они могут быть легко обнаружены и исправлены. Однако совершенно неожиданно для него отладка программы и доведение ее до рабочего состояния нередко оказывается длительным и весьма трудоемким процессом. Приобретая определенный опыт в составлении и отладке сравнительно сложных программ, пользователь убеждается в справедливости популярного афоризма: «В любой программе есть по крайней мере одна ошибка».
После устранения ошибок программирования необходимо провести тщательное тестирование программы — проверку правильности ее работы на специально
отобранных тестовых задачах, имеющих известные решения.
4. Счет по программе и интерпретация результатов. На этом этапе происходит решение задачи на компьютере по составленной программе в автоматическом
режиме. Этот процесс, в ходе которого входные данные с помощью компьютера
преобразуются в результат, называют вычислительным процессом. Как правило,
счет повторяется многократно с различными входными данными для получения
достаточно полной картины зависимости от них решения задачи.
Первые полученные результаты тщательно анализируются, для того чтобы убедиться в правильности работы программы и пригодности выбранного метода ре

Соглашения, принятые в книге
9

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

Соглашения, принятые в книге

Для улучшения восприятия материала в данной книге используются пиктограммы и специальное выделение важной информации.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Эта пиктограмма означает определение или новое понятие.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

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

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

Введение

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Эта пиктограмма означает цитату.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Эта пиктограмма означает теорему.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Эта пиктограмма означает лемму.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . .. . . . . . . . . . . . . . . . . . . . . .
Пример
. . .. . . . . . . . . . . . . . . . . . . . . .

Эта пиктограмма означает пример. В данном блоке автор может привести практический пример для пояснения и разбора основных моментов, отраженных в теоретическом материале.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Контрольные вопросы по главе
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .