04 - Сеточные методы

4 Сеточные методы.
4.1 Основные понятия.
Для решения многих численных задач требуется введение дискретных
функций, определенных в точках. Пространством, в котором определены данные
функции, будет являться множество точек – расчетная (вычислительная)
сетка, а сами функции сеточными.
При этом операции интегрирования и дифференцирования для сеточных
функций преобразуются к нахождению частичных сумм и конечных разностей и
разностных производных.
Точки, в которых определена сеточная функция, являются узлами сетки, а
расстояние между узлами – шагом сетки.
4.2 Расчетная сетка.
Расчетная сетка определяется как преобразование области определения
исходной задачи к более простой, дискретной задаче. Сама расчетная сетка
подбирается таким образом, чтобы лучше соответствовать исходной задаче, и при
этом обеспечить наиболее простое вычисление сеточной функции.
После нахождения сеточной функции ее, как правило, преобразуют назад в
исходное непрерывное пространство, чтобы получить решение задачи между
узлами сетки. Для этого используют методы аппроксимации.
Выделяют
несколько
признаков,
по
которым
можно
разделить
вычислительные сетки.
4.2.1 Классификация по размерности пространства
Существуют одно- двумерные сетки и сетки высших размерностей.
Размерность сетки совпадает с размерностью пространства, в котором определена
исходная задача. Для решения обыкновенных дифференциальных уравнений
используют одномерные расчетные сетки, для решения уравнений в частных
производных двух и более мерные. Для задач аппроксимации/интерполяции чаще
всего используют одномерные сетки.
1
4.2.2 Классификация по структуре сетки
Сетки размерностью выше первой по структуре делятся на упорядоченные
(регулярные) и неупорядоченные (нерегулярные). Одномерные сетки можно
принять регулярными по умолчанию.
Регулярные сетки (рис. 4.1) имеют упорядоченный набор узлов, который
можно представить n-мерным массивом, где n совпадает с размерностью
пространства. Набор узлов нерегулярной сетки внешне выглядит хаотично (рис.
4.2).
Рисунок 4.1. Регулярная сетка в
Рисунок 4.2. Нерегулярная сетка в
декартовых координатах
декартовых координатах
Регулярные сетки делятся на сетки с фиксированным (постоянным)
шагом и с переменным шагом. Причем шаг может быть постоянным по одной из
координат и переменным по другой.
Также можно выделить многоблочные сетки, где область определения
исходной задачи разбита на отдельные блоки, для каждого из которых определена
собственная сетка.
4.3 Конечные разности.
Конечные разности представляют собой приращения зависимой функции
меж узлами сетки. Различают правые (нисходящие), левые (восходящие) и
центральные конечные разности.
Для
одномерной
таблично
заданной
функции
yi = f(xi)
определены
следующие конечные разности 1-го порядка в точке xi:
правая –
Δy i = y i+1− y i
(4.1)
левая –
Δy i = y i − y i−1
(4.2)
центральная –
Δy i = y i+1 /2− y i−1 /2
(4.3)
2
1
центральная средняя – Δy i = ( Δy i+1/2 + Δy i−1/2 )
2
(4.4)
Для разностей высших порядков существуют рекурсивные формулы
вычисления через разности более низких порядков, так для разностей порядка k
имеем формулы:
правые –
Δ k y i= Δk−1 y i+1−Δ k−1 y i
(4.5)
левые –
Δ k y i= Δk−1 y i− Δk−1 y i−1
(4.6)
центральные –
Δ k y i= Δk−1 y i+1/2− Δk−1 y i−1/2
(4.7)
1 k
Δ y i+1/2 + Δk y i−1 /2)
(
2
(4.8)
k
центральные средние – Δ y i=
Количество разностей зависит от количества узлов сетки, с ростом порядка
конечной разности их число уменьшается, если n – число узлов сетки, то
количество разностей k-го порядка равно (n – k). Отсюда можно сделать вывод,
что порядок разностей не может превышать число узлов сетки минус единица.
Это наглядно представлено на рис. 4.3.
Правые разности
x1
y1
x2
y2
x3
y3
x4
y4
x5
y5
Δy1
Δy2
Δy3
Δy4
Δ2y1
2
Δ y2
Δ2y3
Δ3y1
3
Δ y2
Δ4y1
Левые разности
x1
y1
x2
y2
x3
y3
x4
y4
x5
y5
Δy2
Δy3
Δy4
Δy5
Δ2y3
2
Δ y4
Δ2y5
Δ3y4
3
Δ y5
Δ4y5
Центральные разности
x1
y1
x2
y2
x3
y3
x4
y4
x5
Δy1.5
Δy2.5
Δy3.5
Δ2y2
2
Δ y3
Δ2y4
Δ3y2.5
3
Δ y3.5
Δ4y3
Δy4.5
y5
Рисунок 4.3. Диагональная таблица конечных разностей
3
С оператором конечной разности связан оператор разностной производной,
который является аналогом производной для табличной функции. Для сетки с
постоянным шагом разностная производная вычисляется через конечную
разность по зависимости:
(k)
y (x i )=
Δk y i
h
(4.9)
k
В зависимости от типа взятой конечной разности, разностные производные
так же бывают правые, левые и центральные.
Для примера вычислим центральную разностную производную второго
порядка, которая часто применяется при численном решении уравнений в
частных производных:
''
y (x i )=
Δ2 y i
h
=
2
Δ y i+1/2− Δ y i−1 /2 ( y i+1− y i )−( y i − y i−1 ) y i+ 1−2 y i + y i−1
(4.10)
=
=
h2
h2
h2
Выделим несколько основных свойств конечных разностей.
1) Конечные разности постоянной равны нулю.
2) Оператор конечной разности линеен.
3) Если табличная функция задана точными числами, и конечные разности
вычисляются без погрешности, то при увеличении порядка конечной разности
уменьшаются абсолютные значения вычисляемых величин конечных разностей.
4) Если табличная функция есть полином степени k, то конечные разности
k-го порядка такой функции константы, разности порядка выше k равны нулю.
Последнее свойство используется при интерполяции табличных функций.
Основываясь на этом свойстве можно утверждать, что если конечные разности
k-го порядка известной табличной функции постоянны, то эта функция есть
полином k-й степени. Таким образом находится порядок интерполирующего
полинома.
Реальные
табличные
функции
заданы
не
точными
числами,
а
приближенными. В связи с этим, даже если использовать сколь угодно большую
точность вычисления, свойство (3) будет выполняться только до определенного
порядка. Это связано с нарастающим влиянием погрешности округления с
возрастанием порядка конечной разности. Если на каком-то этапе вычисления
конечных разностей при возрастании порядка абсолютные значения начали
4
увеличиваться, смысла в вычислении разности такого порядка не имеется, т. к.
основной вклад в значения их величин вносят погрешности округления
вычислений и исходных величин.
Основываясь на вышесказанном порядок интерполирующего полинома
находят исходя из сопоставления известной погрешности исходных величин
абсолютных значений величин конечных разностей
Пусть исходная табличная функция задана с абсолютной погрешностью Δtf.
При вычислении конечных разностей, при увеличении порядка конечной разности
производится одна операция вычитания, что дает увеличение абсолютной
погрешности в 2 раза (вычислительной погрешностью пренебрегаем, т. к. она
должна быть много меньше погрешности исходных величин). На этом основании
абсолютная погрешность вычисления конечной разности k-го порядка, если не
имеется систематических погрешностей будет составлять
максимальный
порядок
конечной
разности
можно
2k · Δtf / √ k . Отсюда
задать
как
условие
Δ k y≥ A⋅2k⋅Δtf / √ k , т. е. вычисления ведут пока абсолютная величина превышает
погрешность в A раз, значение A можно взять порядка 10.
Рассмотрим следующий пример. Пусть табличная функция sin(ln(x)) с
точностью до 3-го знака. Тогда Δtf = 0.0005. Возьмем девять точек в интервале
x∈[0.2 ;1.8] , максимальный порядок конечных разностей для данной табличной
функции равен 8. Построим диагональную таблицу правых конечных разностей
(рис. 4.4).
Δyi
Δ2yi
Δ3yi
Δ4yi
Δ5yi
Δ6yi
Δ7yi
Δ8yi
0.206
0.304
0.268
0.221
0.181
0.149
0.123
0.102
0.098
-0.134
-0.036
0.123
-0.011
-0.105
-0.047
0.018
0.007
-0.017
-0.04
0.001
0.008
-0.003
-0.032
-0.002
0.006
0.001
-0.026
-0.001
0.005
-0.021
0.088
0.014
0.004
-0.074
-0.001
0.064
xi
yi
0.2
-0.999
0.4
-0.793
0.6
-0.489
0.8
-0.221
1.0
0.0
1.2
0.181
1.4
0.33
1.6
0.453
1.8
0.555
Error
0.0005 0.001 0.0014 0.0023 0.004 0.0072 0.0131 0.0242 0.0453
Рисунок 4.4. Диагональная таблица правых конечных разностей
5
Мы видим, что ошибка округления начинает иметь существенную роль при
порядке конечных разностей равном 3, отсюда можно сделать вывод, что для
аппроксимации данной табличной функции достаточно полинома 2-й степени.
Список литературы
1. Вержбицкий, В.М. Основы численных методов / В.М. Вержбицкий. – М.:
Высшая школа, 2002. – 840 с.
2. Корн, Г. Справочник по математике (для научных работников и
инженеров) / Г. Корн, Т Корн. – М.: Наука, 1973. – 832 с.
6