Елементи комп’ютерного моделювання
Лекція № 2. Метод скінчених різниць
2. Методскінченихрізниць
План.
Скінчені
різниці,
різницева схема,
похибка апроксимації, порядокапроксимації, помилкарозв’язку,
порядокточності, збіжність, стійкість, коректність.
теоремаЛаксапроеквівалентність, прикладисхем.
Наприкінці попередньої лекції ми зазначили, що основною складовою комп’ютерного моделювання є дискретизація моделі, і назвали чотири основних методи дискретизації:
метод скінчених різниць, метод зважених нев’язок, метод скінчених елементів і спектральний метод.
В цій лекції ми розглянемо один із найпоширеніших методів дискретизації математичних моделей — метод скінченних різниць. Зауважимо, що на практиці дискретизацію за часом здійснюють майже винятково методом скінченних різниць, а для дискретизації просторових похідних використовуються метод скінчених різниць, метод зважених нев’язок, метод скінчених елементів і спектральний метод
[
див. Флетчер].
Для
ілюстрації розглянемо одновимірне рівняння нестаціонарної теплопровідності
(
)
2 2
,
c
c
c
D
v
x t
t
x
x
∂
∂
∂
=
+
+
∂
∂
∂
ϕ
(2.1)
на відрізку 0 1
x
< < , із крайовими умовами Діріхле
(
)
( )
0,
,
1,
,
c
t
a c
t
b
=
=
(2.2)
і початковою умовою
(
)
( )
0
, 0
,
0 1
c x
c
x
x
=
≤ ≤
(2.3)
Існує багато різноманітних способів заміни похідних їх дискретними аналогами. Розглянемо найпростіший спосіб —
безпосередню заміну похідних скінчено-різницевими
2
виразами. Для цього розіб’ємо відрізок
[ ]
0,1
на N однакових відрізків з кроком
1 1
i
i
h
x
x
N
+
=
−
=
(
як бачимо, цей крок можна робити і змінним, якщо точки
i
x розташувати нерівномірно), а
інтервал розрахункового часу — на рівномірні відрізки з кроком
1
n
n
t
t
+
τ =
−
У такому випадку рівняння (2.1)
перетвориться на різницеве рівняння
(
)
(
)
1 1
1 1
1 1
2 2
2
n
n
n
n
n
n
n
i
i
i
i
i
n
i
i
i
D u
u
u
v u
u
u
u
h
h
+
−
+
+
−
+
−
+
−
−
=
+
+
ϕ
τ
,
(2.4)
де
(
)
,
n
n
i
i
u
c x t
=
, а крайові умови і початкова умова набудуть вигляду:
0
,
n
u
a
=
n
N
u
b
= ,
(2.5)
( )
0 0
,
0,1, 2,...,
i
i
u
c
x
i
N
=
=
(2.6)
Множина точок розбиття
(
)
,
n
i
x t
називається різницевою сіткою, а дискретна задача, отримана у такий спосіб —
різницевоюсхемою.
Різницеві схеми розділяються на явні і неявні. Якщо на кожному кроці за часом різницевий розв’язок знаходиться шляхом обчислення виразів, що залежать лише від розв’язків,
отриманих на попередніх кроках, схема називається явною.
Якщо ж вона зводиться до системи рівнянь відносно розв’язку на поточному кроці, то схема називається неявною. З цієї точки зору схема (2.4) є явною.
Запишемо неявну різницеву схему
(
)
(
)
1 1
1 1
1 1
1 1
1 1
1 2
2 2
n
n
n
n
n
n
n
i
i
i
i
i
n
i
i
i
D u
u
u
v u
u
u
u
h
h
+
+
+
+
+
+
−
+
+
−
+
−
+
−
−
=
+
+
ϕ
τ
(2.7)
і перепишемо її так, щоб ліворуч стояли всі невідомі значення,
а праворуч — відомі:
3 1
1 1
1 1
1 2
2 2
2 1
2 2
n
n
n
n
n
i
i
i
i
i
D
v
D
D
v
u
u
u
u
h
h
h
h
h
+
+
+
+
−
+
+
−
+
+
+
=
+
τ
τ
τ
ϕ
Якщо розташувати значення невідомого розв’язку у вигляді
вектору-стовпчика
(
)
1 1
1 0
1
,
,...,
T
n
n
n
N
u
u
u
u
+
+
+
=
, то різницеву схему
(2.7)
із урахуванням умов (2.5) і (2.6) можна подати як систему лінійних алгебраїчних рівнянь
Au
f
=
,
де
2 2
2 1
1 2
2 2
1 1
2 2
,
1 2
2 1
n
n
N
a
D
v
D
D
v
u
h
h
h
h
h
A
f
D
v
D
D
v
u
h
h
h
h
h
b
−
+
+
+
=
=
+
+
+
τ
τ
τ
τ
τ
τ
Аналогічно можна подати різницеву схему будь-якої
розмірності, певним чином упорядкувавши значення розв’язку у вузлах різницевої сітки.
Таким чином, початково-крайова задача
(2.1)—(2.3)
перетворюється на задачу відносно множини дискретних значень
(
)
1 1
,
n
n
i
i
u
c x t
+
+
=
і зводиться до розв’язання системи лінійних алгебраїчних рівнянь. В результаті виникають два види похибок: похибкаапроксимації та похибкарозв’язку.
Розглянемо абстрактний випадок і припустимо, що ми дискретизували диференційний оператор
( )
L u
і отримали різницевий оператор
( )
h
h
L u
4
Похибкаапроксимації, абонев’язка, — це сіткова функція,
( )
( )
( )
h
h
h
h
h
u
L u
L u
ψ
=
−
, що виникає внаслідок дискретизації
рівняння і характеризує різницю, яка виникає, якщо в різницеву схему підставити точний розв’язок. Кажуть, що різницевий оператор
h
L апроксимує диференційний оператор
L , якщо
( )
0
h
h
u
ψ
→ при
0
h
→ .
Різницева норма i
зазвичай задається як дискретний аналог чебишовської норми
( )
0,...,
max
h
h
i
i
N
u
u
x
=
=
Якщо
( )
k
h
h
u
Mh
ψ
≤
при
0
h
→ ,
де константа M не залежить від h , то кажуть, що різницева схема має k-й порядокапроксимації.
Похибкарозв’язку — це різниця між точним і наближеним розв’язками
(
)
(
)
(
)
,
,
,
n
n
n
h
i
i
h
i
z
x t
u x t
u
x t
=
−
в точках різницевої
сітки. Кажуть, що розв’язок дискретної задачі збігається до розв’язку диференційної задачі, якщо
0
h
z
→
при
0
h
→ .
Якщо
k
h
z
Mh
≤
,
де константа M не залежить від h , то кажуть, що різницева схема має k-йпорядокточності.
Різницева схема називається стійкою (абсолютно, або безумовно) якщо
h
h
u
M
ϕ
≤
,
де константа M не залежить від h , а
h
ϕ
— різницева апроксимація функції
ϕ
Якщо ця нерівність має місце лише
5
за певних умов (як правило, при деяких обмеженнях на h і
τ
),
то схема називається умовностійкою.
Різницева схема називається коректною, якщо її розв’язок
існує і вона є стійкою.
Система лінійних алгебраїчних рівнянь, отримана в результаті дискретизації,
є узгодженою з первинним диференційним рівнянням з частинними похідними, якщо при
0
h
→
і
0
τ
→ система алгебраїчних рівнянь стає
еквівалентною диференційній задачі.
Узгодженість дозволяє зв’язати один з одним поняття стійкості і збіжності за допомогою теореми Лакса про еквівалентність: якщо лінійна диференційна задача
є
коректною,
а
її
скінчено-різницева апроксимація
є
узгодженою, тостійкістьєнеобхідноюідостатньою умовоюзбіжності.
Коректність диференційної задачі означає, що
1) розв’язок задачі існує,
2) розв’язок задачі є єдиним,
3) розв’язок задачі неперервно залежить від вхідних даних.
В наші наміри не входить детально розбирати методи побудови різницевих схем або досліджувати питання їхньої
стійкості. Втім, деякі практичні рекомендації були б корисними.
Зокрема, явні різницеві схеми є умовно стійкими і
вимагають використання дуже маленьких кроків за часом,
тому, незважаючи на відносну простоту, часто
є
неприйнятними з міркувань витрат комп’ютерного часу
(
повільно обчислюються). Неявні різницеві схеми завжди є
абсолютно (безумовно) стійкими. Завдяки цьому, а також їх алгоритмічній простоті, вони де факто стали технологічним стандартом розв’язання багатьох задач.
6
Наведемо для прикладу кілька відомих різницевих схем,
використовуючи відомі скорочені форми запису різницевих виразів:
1
i
i
x
u
u
u
h
+
−
=
— права різницева похідна,
1
i
i
x
u
u
u
h
−
−
=
— ліва різницева похідна,
0 1
1 2
i
i
x
u
u
u
h
+
−
−
=
— центральна різницева похідна.
• Схема центральної різниці
0
_
1 1
1
k
k
k
t
x
x x
u
vu
u
+
+
+
+
=
(2.8)
• Модифікована схема центральної різниці
0
_
1 1
1 1 0.5
k
k
k
t
x
x x
D
u
vu
u
PeCu
+
+
+
+
=
+
,
(2.9)
де
vh
Pe
D
=
— сіткове число Пекле,
v
Cu
h
τ
=
— сіткове число Куранта.
• Монотонна схема
_
1 1
1 1 0.5
k
k
k
t
x
x x
D
u
vu
u
Pe
+
+
+
+
=
+
(2.10)
• Модифікована монотонна схема
(
)
_
1 1
1 1 0.5 1
k
k
k
t
x
x x
D
u
vu
u
Pe
Cu
+
+
+
+
=
+
+
(2.11)
• Схема односторонньої різниці
_
1 1
1
k
k
k
t
x
x x
u
vu
Du
+
+
+
+
=
(2.12)
• Схема Кранка-Николсона
(
)
(
)
0 0
_
_
1 1
1 2
2
k
k
k
k
k
t
t
t
x x
x x
v
D
u
u
u
u
u
+
+
+
+
+
=
+
(2.13)
7
Висновки. В результаті застосування методу скінчених різніць задача зводиться або до умовно стійкої явної
різницевої схеми, або до абсолютно стійкої неявної схеми.
Неявна схема еквівалентна системі лінійних алгебраїчних рівнянь із розрідженою матрицею. Це робить метод універсальним і простим для реалізації. З іншого боку, для зберігання матриці потрібен великий об’єм пам’яті. Крім того,
метод скінчених різниць, як правило, орієнтований на прямокутні області і не дозволяє точно урахувати геометричні
особливості області розв’язання. Для більш гнучкого урахування геометрії області слід застосовувати метод скінчених елементів.
Література
1.
Самарский А.А. Теория разностных схем. — М., Наука,
1989.
2.
Самарский А.А., Николаев Е.С. Методы решения сеточных уравнений. — М., Наука, 1978.
3.
Самарский А.А., Гулин А.В. Устойчивость разностных схем. — М., Наука, 1973.
4.
Самарский А.А., Андреев В.Б. Разностные методы для эллиптических уравнений. — М., Наука,
1976.
5.
Самарский А.А., Гулин А.В. Численные методы. — М.,
Наука, 1989.