Добавлен: 06.02.2019
Просмотров: 4131
Скачиваний: 4
6
указанные погрешности являются неустранимыми, поскольку они
неизбежны в рамках данной модели.
При переходе от математической модели к численному методу
возникают погрешности, называемые погрешностями метода. Они связаны с
тем, что всякий численный метод воспроизводит исходную математическую
модель приближенно. Наиболее типичными погрешностями метода являются
погрешность дискретизации и погрешность округления. Поясним причины
возникновения таких погрешностей.
Обычно построение численного метода для заданной математической
модели разбивается на два этапа: а) формулирование дискретной задачи, б)
разработка вычислительного алгоритма, позволяющего отыскать решение
дискретной задачи. Например, если исходная математическая задача
сформулирована в виде системы дифференциальных уравнений, то для
численного решения необходимо заменить ее системой конечного, может
быть, очень большого числа линейных или разностных алгебраических
уравнений. В этом случае говорят, что проведена дискретизация исходной
математической задачи. Простейшим примером дискретизации является
построение разностной схемы, путем замены дифференциальных выражений
конечно-разностными отношениями. В общем случае дискретную модель
можно рассматривать как конечномерный аналог исходной математической
задачи. Ясно, что решение дискретизированной задачи отличается от
решения исходной задачи. Разность соответствующих решений и называется
погрешностью дискретизации. Обычно дискретная модель зависит от
некоторого параметра (или множества параметров) дискретизации, при
стремлении которого к нулю должна стремиться к нулю и погрешность
дискретизации. При этом число алгебраических уравнений, составляющих
дискретную модель, неограниченно возрастает. В случае разностных методов
таким параметром является шаг сетки.
Как уже отмечалось, дискретная модель представляет собой систему
большого числа алгебраических уравнений. Невозможно найти решение
такой системы точно и в явном виде. Поэтому приходится использовать тот
или иной численный алгоритм решения системы алгебраических уравнений.
Входные данные этой системы, а именно коэффициенты и правые части,
задаются в ЭВМ не точно, а с округлением. В процессе работы алгоритма
погрешности округления обычно накапливаются, и в результате решение,
полученное
на
ЭВМ,
будет
отличаться
от
точного
решения
дискретизированной задачи. Результирующая погрешность называется
погрешностью
округления
(иногда
ее
называют
вычислительной
погрешностью). Величина этой погрешности определяется двумя факторами:
точностью представления вещественных чисел в ЭВМ и чувствительностью
данного алгоритма к погрешностям округления.
Алгоритм называется устойчивым, если в процессе его работы
вычислительные погрешности возрастают незначительно, и неустойчивым —
в
противоположном
случае.
При
использовании
неустойчивых
7
вычислительных алгоритмов накопление погрешностей округления приводит
в процессе счета к переполнению арифметического устройства ЭВМ.
Итак,
следует
различать
погрешности
модели,
метода
и
вычислительную. Какая же из этих трех погрешностей является
преобладающей? Ответ здесь неоднозначен. Видимо, типичной является
ситуация, возникающая при решении задач математической физики, когда
погрешность модели значительно превышает погрешность метода, а
погрешностью округления в случае устойчивых алгоритмов можно
пренебречь по сравнению с погрешностью метода. С другой стороны, при
решении, например, систем обыкновенных дифференциальных уравнений
возможно применение столь точных методов, что их погрешность будет
сравнима с погрешностью округления. В общем случае нужно стремиться,
чтобы все указанные погрешности имели один и тот же порядок. Например,
нецелесообразно пользоваться разностными схемами, имеющими точность
6
10 , если коэффициенты исходных уравнений задаются с точностью
2
10 .
3. Требования к вычислительным методам. Одной и той же
математической задаче можно поставить в соответствие множество
различных дискретных моделей. Однако далеко не все из них пригодны для
практической реализации. Вычислительные алгоритмы, предназначенные для
быстродействующих ЭВМ, должны удовлетворять многообразным и
зачастую противоречивым требованиям. Попытаемся здесь сформулировать
основные из этих требований в общих чертах.
Можно выделить две группы требований к численным методам. Первая
группа связана с адекватностью дискретной модели исходной
математической задаче, и вторая группа-с реализуемостью численного
метода на ЭВМ.
К первой группе относятся такие требования, как сходимость
численного метода, выполнение дискретных аналогов законов сохранения,
качественно правильное поведение решения дискретной задачи.
Поясним эти требования. Предположим, что дискретная модель
математической задачи представляет собой систему большого, но конечного
числа алгебраических уравнений. Обычно, чем точнее мы хотим получить
решение, тем больше уравнений приходится брать. Говорят, что численный
метод сходится, если при неограниченном увеличении числа уравнений
решение дискретной задачи стремится к решению исходной задачи.
Поскольку реальная ЭВМ может оперировать лишь с конечным числом
уравнений, на практике сходимость, как правило, не достигается. Поэтому
важно уметь оценивать погрешность метода в зависимости от числа
уравнений, составляющих дискретную модель. По этой же причине
стараются строить дискретную модель таким образом, чтобы она правильно
отражала качественное поведение решения исходной задачи даже при
сравнительно небольшом числе уравнений.
Например, дискретной моделью задачи математической физики может
быть разностная схема. Для ее построения область изменения независимых
переменных заменяется дискретным множеством точек - сеткой, а входящие
8
в исходное уравнение производные заменяются, на сетке, конечно-
разностными отношениями. В результате получаем систему алгебраических
уравнений относительно значений искомой функции в точках сетки. Число
уравнений этой системы равно числу точек сетки. Известно, что
дифференциальные
уравнения
математической
физики
являются
следствиями интегральных законов сохранения. Поэтому естественно
требовать, чтобы для разностной схемы выполнялись аналоги таких законов
сохранения. Разностные схемы, удовлетворяющие этому требованию,
называются консервативными. Оказалось, что при одном и том же числе
точек сетки консервативные разностные схемы более правильно отражают
поведение решения исходной задачи, чем неконсервативные схемы.
Сходимость численного метода тесно связана с его корректностью.
Предположим, что исходная математическая задача поставлена корректно,
т.е. ее решение существует, единственно и непрерывно зависит от
входных данных. Тогда дискретная модель этой задачи должна быть
построена таким образом, чтобы свойство корректности сохранилось. Таким
образом, в понятие корректности численного метода включаются свойства
однозначной разрешимости соответствующей системы уравнений и ее
устойчивости по входным данным. Под устойчивостью понимается
непрерывная зависимость решения от входных данных, равномерная
относительно числа уравнений, составляющих дискретную модель.
Вторая группа требований, предъявляемых к численным методам,
связана с возможностью реализации данной дискретной модели на данной
ЭВМ, т. е. с возможностью получить на ЭВМ решение соответствующей
системы алгебраических уравнений за приемлемое время. Основным
препятствием для реализации корректно поставленного алгоритма является
ограниченный объем оперативной памяти ЭВМ и ограниченные ресурсы
времени счета. Реальные вычислительные алгоритмы должны учитывать эти
обстоятельства, т. е. они должны быть экономичными как по числу
арифметических действий, так и по требуемому объему памяти.
9
Численные методы алгебры и анализа
1 Решение систем линейных алгебраических уравнений
Рассмотрим систему линейных алгебраических уравнений:
m
m
mm
m
m
m
m
m
m
b
х
а
...
х
а
х
а
.
.
.
.
.
.
.
.
.
b
х
а
...
х
а
х
а
b
х
а
...
х
а
х
а
2
2
1
1
2
2
2
22
1
21
1
1
2
12
1
11
(1.1)
или в матричной форме:
Aх=B, (1.2)
где: A={a
ij
} квадратная матрица размерности (m m,); х=(х
1
,….,х
m
)
T
; T –
операция транспонирования; b=(b
1
,….,b
m
)
T
; detA 0.
Предположим, что определитель матрицы A не равен нулю. Тогда
решение х существует и единственно. На практике встречаются системы,
имеющие большой порядок. Методы решения системы (1.1) делятся на две
группы:
1) прямые (точные методы);
2) итерационные методы (приближенные).
1.1 Точные методы
В методах Гаусса решение х находится за конечное число действий, но
из-за погрешности округления и их накопления прямые методы можно
назвать точными, только отвлекаясь от погрешностей округления.
1.1.1 Метод Гаусса
Прямой ход метода
1-й шаг. Предположим, что а
11
0. Поделим первое уравнение на этот
элемент:
1
1
2
12
1
y
x
c
...
x
c
x
m
m
. (1.3)
Остальные уравнений системы (1.1) запишем в виде
10
i
m
im
i
i
b
x
a
...
x
a
x
a
2
2
1
1
, (1.4)
где i=
m
,
2
.
Уравнение (1.3) умножаем на a
i1
и вычитаем из i-го уравнения
системы (1.4).
Получим систему вида:
(1)
m
1
(1)
mm
2
(1)
m2
(1)
2
1
(1)
2m
2
(1)
22
1
m
1m
2
12
1
b
x
a
...
x
a
.
.
.
.
.
.
.
.
.
b
x
a
...
x
a
y
x
c
...
x
c
x
. (1.5)
1
1
1
1
1
1
i
i
)
(
i
i
j
ij
)
(
ij
a
y
b
b
a
c
a
a
.
Система (1.5) имеет матрицу вида:
x
...
x
0
...
...
...
...
x
...
x
0
x
...
x
1
.
Работаем с укороченной системой, т.к. х
1
входит только в 1-ое
уравнение
(1)
m
m
(1)
mm
2
(1)
m2
(1)
2
m
(1)
2m
2
(1)
22
b
x
a
...
x
a
.
.
.
.
.
.
.
b
x
a
...
x
a
.
2-й шаг. Если
0
1
22
)
(
а
, то из укороченной системы аналогично
исключаем неизвестное x
2
и получаем матрицу коэффициентов такого вида: