close

Вход

Забыли?

вход по аккаунту

Вакансия: Главный бухгалтер;pdf

код для вставкиСкачать
6. И. А. Ш и ш м а р е в. О некоторых оценках для эллиптического оператора
с гладкими и разрывными коэффициентами. Дисс. канд. физ.-матем. н., М., МГУ,
1962.
"
' • .
7. В. А. И л ь и н ,
И. А. Ш и ш м а р е в . Свойства гладкости обобщенных по­
тенциалов эллиптического оператора. Докл. АН СССР, 1961, 141, № 3, 547—550.
8. К. М и р а н д а . Уравнения с частными производными эллиптического типа. М..,
Изд-во ин. лит., 1957.
9 . В а н Т у н . Повышающее свойство прямых значений обобщенных потенциалов
для функции сравнения и главного фундаментального решения общего эллип; тического уравнения Nвторого порядка. Докл. АН СССР, 1963, 152, № 6, 1288—
1291. '
УДК
518.517.9/.94
ОБ ОДНОМ ЭКОНОМИЧНОМ АЛГОРИТМЕ ЧИСЛЕННОГО РЕШЕНИЯ
СИСТЕМ ДИФФЕРЕНЦИАЛЬНЫХ И АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ
А.
А.
САМАРСКИЙ
(Москва)
Для решения системы обыкновенных дифференциальных уравнений первого по­
рядка по аналогии с [1], [2], [3] предлагается экономичная (по числу действий) раз­
ностная схема второго порядка точности (попеременно-треугольная схема). Эта
схема может быть использована в качестве итерационной схемы для решения си­
стемы линейных алгебраических уравнений. Все результаты переносятся на случай
линейных операторных уравнений.
,
1. Рассмотрим задачу Коши для системы уравнений
. . . • ^ . + ..4ii = f (0,
0 < * < Т ,
u(0j = u „
(1)
где u = и (t) = ( М О , • • u (t)), f (t) = (Д (0, . . ., f (0) - векторы,: Л — A (t) =
== (a (t)) — квадратная матрица
пХп.
Пусть со = {tj = /х} — сетка с шагом х на отрезке [0, Т]. Для решения задачи
(1) можно использовать ряд разностных схем. Будем сравнивать их по числу арифме­
тических операций q, затрачиваемых при переходе со слоя t- на слой
т. е. при
определении вектора у
по заданному у . Для явной схемы у
= у +
— АуУ
имеем q = 2п + 2п; она имеет первый порядок точности. Неявная схема y
+
+ 0.5 т (Ay)
= у — 0.5 т (АуУ -f- 0.5 т (F + f ) имеет второй порядок точности,
но для нее q = О (п ). Будем называть схему экономичной, если для нее, так же
как и для явной схемы, q = О (га ).
2. Будем предполагать, что матрицу А можно представить в виде суммы двух
треугольных положительно определенных матриц:
n
n
ik
т
; + 1
;
3 + 1
3
2
J + 1
J+1
0
J + 1
3
2
А ±А
г
+ А,
А
2
= (о^),
х
2
(А 1, l)>ci||i||2,
а
п
где (v, |) = ^
аТ = 0,
+
А
= (a ),
к
ik
с = const > 0,
х
к > £; 7. + + =
fl
а = 1,2,
fl
(2)
( 3 )
•
u
i
IIS II
=
"К"(1» I) — скалярное произведение и норма, § — произ-
,• ^=1
вольный вещественный вектор. Если А —симметричная
положить а7 =
(|, А у)
г
580
матрица,
то естественно
= Д||/2;. тогда условие симметрии дает
= (А §, v ) , т. е. А* = Л , А\ = A
2
г
v
2
v
(4)
Рассмотрим следующую двухшаговую разностную схему:
У-У
+ A y+A y
1
= t'(t),
i
.JLZ-L+Atf
•
где « = *
,
2 j + 1
и ,)
0
+ л у = f (г),
'
2
I
у
т -
t=
у = у (0,
У(0) =
t
t = *
2ji
^ - ^ ( г ) ,
2 j + 2
, у = у (i),
Л = Л (г),
2
У = У .(0.
Л =л (*).
2
а
а
Для определения у при заданном у надо обратить треугольную матрицу Е + чА
а для определения у — обратить треугольную матрицу Е + iA . Это возможно при
любом % > 0, если
> 0 , и требует О (га ) операций, т. е. схема (5) экономична.
Напишем расчетные формулы в виде
1У
2
2
У1-~
, .
V
1 + tflj
.
a
2j
ik
Ук'
f = l , - . . . , л,
[ (6>
i—1
2/i =
A
, _
!
y
'
+
i =
а
Zj
0
гЛ>
2/г( ) = »oi-
Если, кроме вектора у , запоминать вектор yt, то для определения у (на одном шаге>
надо затратить д = п + 7га арифметических действий; запоминая ь>7 и y найдем уь
тоже с затратой лишь q = га + 7га действий. Один шаг по явной схеме требует
q = 2га + 2га операций. Таким образом, предлагаемая двухшаговая схема при
га > 5 требует меньшего числа действий даже по сравнению с явной схемой с шагом i.
Кроме того, как будет показано ниже, схема (5) имеет второй порядок точности.
3 . Найдем погрешность аппроксимации схемы. П у с т ь ' и р е ш е н и е задачи (1)>.
у — решение задачи (5). Для z = у — и имеем
{
х
2
v
2
2
z + хА ъ — z — xA v—тг^,
х
z + хА г = z — хА г — тл|?, z (0) = 0,
2
2
х
2
(7>
где Фи ^ 2 — локальные погрешности аппроксимации. Полная погрешность аппрокси­
мации схемы (15) равна
* =
+ Ч> = (А и2
2А и
2
+А и)
2
Если Л ' й и , А б С
2
( 1 , 1 )
2
.+ 2 (
U
~
Ц
- f
1
2
[ 0 , Г ] , то ч|>= 0 ( х ) .
(8>
При этом i|) , a = 1, 2, можно представить в виде
a
1>a=U + <>
a
2
%= О Ы ,
< = 0(т ),
a-1,2,
]
В дальнейшем будем предполагать, что условия (8) выполнены.
4. Перейдём к выводу априорных оценок для решения задачи (7). Пусть (z, | ) —
скалярное произведение и || z |] = l ^ ( z , z) — связанная с ним норма. Введем норму
j | z | | | = ||z|p + T 2 | | ^
Л е м м а 1.
a
Z
p,
a =1,2.
(9>
Справедливы неравенства
2х(А
а
'
z, z ) > a | | z | g ,
<V=
a
' '
'
t
нЛ^^р
•
•
(10>
'
58%
II z + ъА
z f > (1 + o ) I z |£ ,
а
xA- z | P < (1 _ a„) || z |||,
|| z -
a
a = 1,2.
a
(11)
„Достаточно доказать (10). Из (3) и (9) следует
2
2
2
|| z t < (1 + т | | Л И) || z |? < ( 1 + т И
а
а
|Р) J_ (А
а
z, г).
Переписывая первое из уравнений (7) в виде z + T^4 Z +
z — хА г,
числяя квадраты норм от обеих частей и пользуясь леммой 1, получим
x
%
( l + o , ) | | « | g < i ; i - - o ^ | | a ^ - x » [ - * i | p - - 2 x ( * , « + x^ z),
1
2
2
(l+«J2)l|2||^(l-a )||z||2+T HII -2x(4
1
1
Шусть Л* — сопряженный к А
(12)
1
,z-x^ z).
(13)
1
оператор; тогда
х
(А^,
2
вы­
%) = (z, А[%)
^ \\ z\\\\Al%l
.'
(14)
Ш р о су ммир уем (12) и (13) и воспользуемся неравенством
,
-
с т || z | p + -Lt.il ^ + ^ ' | | ,
#i+
2х (z,
в
.• 2<*(Е,А[
0
(+2 -
Со
2
2
>где с = 2с /(1 + т M i l l ) — Oifa.
0
х
_^-"|| J g
| ^,^^L__ичг р
| ^ н i (g-ь -г и^IP,.
|| S g
| ^
2
и=
[т || ъ
(15)
:
1
II - Y
Тогда получим
-f- о
+ь
1
2
р
| +
тз ||
-f-
о
2
^ № - ,м ||2]L±LLLI + %
2
i
и ih р
| -м
|л
Cl
Шз (15) и начального условия z (0) = 0 следует
2j
• \\z h<
f, * * | | ,
.
,
7 = 0, 1,
, i
\V
= (2 x 11^"II ) , .
2
2
.
(17)
j'=i
Тем самым доказана
Т е о р е м а 1. Для решения задачи (7) га/ж дополнительном условии (3) верна
-оценка (17).
Т е о р е м а 2.
выполнены условия (3) и (8), т о ся&ма (5) имеет второй поря­
док точности:
2
IMKMx ,
7=1,2,...,
-где М — положительная постоянная, не зависящая от х.
Для доказательства теоремы 2 достаточно показать, что из условий (8') следует
ЩЧ? || = О ( х ) , и воспользоваться теоремой 1.
5. Все предыдущие результаты (кроме формул (6)) сохраняют силу, если
А и А — произвольные линейные операторы в гильбертовом пространстве Н, удов»
летворяющие (3). Если А — самосопряженные операторы, то схема (5) является
обобщением известного алгоритма переменных направлений для двухмерного урав­
нения теплопроводности. Несколько изменяя рассуждения, можно изложенным вы­
ш е методом показать, что алгоритм [4] сходится и для произвольной области со ско»
ростью О (h + х h~ ), где h— шаг пространственной сетки.
Пользуясь теоремой 1, можно, в частности, показать, что перемежающийся ме­
тод [5] для одномерного уравнения теплопроводности сходится со скоростью
О (х //г + h ).
' '
' '
2
Х
2
А
2
2
,582
2
2
/2
2
1
В [1] был предложен экономичный метод для решения системы уравнений пара­
болического типа
•
*
•
(18>
v
У
~
х
У
+ Ау + А у
г
2
= 0,
Л у = -
+
(а~у-)х, А у = -
х
(а у-) .
2
х
2
2
2
Алгоритм (5) в этом случае дает более высокий порядок точности О (x h~^ + Л ).
Для решения задачи (1) можно также пользоваться схемой
V
А
t, I^ZJ.
+ 2АУ =
4
X
= f,
+ 2AJ
у (0) = u
(19)
0 )
X
являющейся аналогом локально-одномерной схемы [6]. Эта схема имеет первый
рядок точности и является экономичной.
Следует отметить, что условие (3) не является ограничением общности, если
иметь в виду преобразование и = ve^\ где (Л = -const > 0 произвольно. Достаточно
лишь потребовать, чтобы (А %, | ) > — const || 11[ , а = 1, 2, const > 0 Для пп. 6 и 7 условие (3) необходимо.
6. Пусть дана система п линейных алгебраических уравнений
Аи = А и +А и
= /,
А = (a ),
(20)
2
а
х
2
ik
где А и Л -п- треугольные положительно определенные матрицы.
Схему (5) можно использовать как итерационную процедуру для решения урав­
нений (20), считая у итерацией номера / .
Рассмотрим следующую итерационную схему:
г
2
1
(Р +А )
Х
у = (D -А )
2
(D + Л ) у = (D-AJ
у +
у + f
2
у(0) = у ,
1,
(21)
е
£>=^-^-),
Т«>0,
(22)
где у© — произвольное начальное
приближение, D — диагональная
матрица,
у = у ^ — итерация номера 2/, у = у ' , у = y ' . Если итерации находить по
схеме (21), считая у = y ,
у = у , / = 0, 1, . . ., то при Цх = а /2 мы получим
метод Некрасова — Зейделя [7] (алгоритм «вниз»). Наряду с (21) можно рассмат­
ривать алгоритм «вверх» (22) (считая у = у
, у — у\
/* = 0 , 1 , . . . ) . Из аналога
формулы (6) следует, что попеременно-.треугольный алгоритм (21) — (22) является
более экономичным, чем каждый из алгоритмов (21) и (22) в отдельности.
Если А и У ! — линейные, самосопряженные операторы в гильбертовом про­
странстве Я , то метод (21) — (22) есть обобщение итерационного метода [4] решения
разностной задачи Дирихле.
•
7. Для доказательства сходимости итераций надо оценить решение задачи Коши
2
23
j+1
+1
2j
+2
3
и
н
х
и
1
2
(D + А ) z = (D ~А )
х
2
для погрешности z = у
ров 2/ + 2, 2/ + 1 и 2/
будем пользоваться для
диагональная матрица,
'
-
z,
(D + A )z
= (D - А ) z,
2
х
z (0) = z
(23)
9
— и, где и — точное решение (20), у, у, у — итерации номе­
(/ = 0, 1, . . . . . ) соответственно. Если
.= const = т, то мы
оценки z нормой (9); в общем случае, когда D = (l/x ) —
под || z|| понимается выражение
ik
2
2
llzlg^l^zip+ll^^zll ,
а = 1,2,
.
(24)
Т е о р е м a 3. Если А и А удовлетворяют условию (3), то попеременно-треуголь­
ная схема (21) — (22) сходится со скоростью геометрической прогрессийх
2
l l y ^ ' - u ^ p l l y ^ - u l b ,
при
0 < р < 1 ,
/=1,2,...,
(25)
любой положительно определенной диагональной матрице D.
583
(23)
Доказательство достаточно провести для т - = const = т . В силу леммы 1 и »
получим
2
2
(i + ( T ) [ | z | | < ( l - a ) U z §
1
(1 + a ) | | z | | ; < ( l - 0 ) J | z | |
2
2
1
2
1
(26>
>
2
где G дается формулой (10), Исключаем отсюда || z | | :
K
2
Так как 0 < а ^ 1 при г > 0, то р < 1 всегда. Вводя с = шах (|| А ||, ||Л ||),
получим
к
2
^ 1 —а
Р - < Р = Г + 7 /
г
2
2ЙТ
г
еg
«
^
!
+
с
2
т 2
•
;
(28>
Минимум р достигается при
т = т = Vc
0
и равен p
(29)
2
= (1 — rj)/(l + п), где rj = с - ^ . Условие (29) удобно для
m i n
ского использования.
В общем
случае
2
2
а = 2с т*/(1 + т*) с , где
практиче­
= min
1
x
iiy
т* = max т^; для доказательства уравнения (23) записываются в виде
г
1
г
77=^
Ъ
+
1
г
гг \ ^ 1 - /
А
( ^г=
у—
г
—г=
*i - K ^ M i Z ) . ,
-1=1,
и,
вычисляется квадрат обычной нормы от обеих частей и используется аналог леммы li
2^(z,^ z)>a [|z|g„
a
2
a
a
a
2
= 2 ^ / ( 1 + ||AJ| V) ),
. a = 1, 2.
8. 3 а м e ч а н и e 1. Для каждого из алгоритмов (21) и (22) в отдельности полу­
чается оценка вида || z|| < P || z || , где
= (1 - a ) / ( l + a ) ,
a = 1, 2. Отсюда,,
в частности, следует сходимость метода Некрасова — Зейделя для любой матрицы А,
представимой в виде суммы двух положительно определенных треугольных матриц/
у которых
= at. = а /2. Метод Некрасова сходится, вообще говоря, с той же ско­
ростью, что и соответствующий попеременно-треугольный алгоритм (21)—(22) (ср. [ 7 ] .
гл. II, § 34), однако метод (21) — (22) экономичнее, так как для вычисления одной,
итерации в этом случае требуется п + In операций вместо 2д + 5тг.
З а м е ч а н и е 2. Теорема 3 верна, если А и А — произвольные положитель­
но определенные линейные операторы в гильбертовом пространстве Н.
2
2
a
P
a
a
a
и
2
2
х
З а м е ч а н и е 3. «Пусть А
(a = 1, 2) — самосопряженный конечномерный ли­
а
нейный оператор в Н,
значения,
2
^4Jtll >
a
AJ ^ и % ^ — его наименьшее
Я = min (*,<« ,
х
и
w
a
2
и наибольшее
) Д = max (Я*, ', % ^ ) . Тогда
п
получим а = 2Х. т/(1 + r ^ X J ,
х
max а = Yr\,
= (1 - ^г))/(1 + Vn)В частности, для разностной задачи Дирихле в квадрате
^ =
4sin 4?M
2
2 /
7
'П —К/^ <
п
( 0 < х ^1,
а
т
*
п
Р
=
а = 1,2>
k =Acos*J&-/h'n
п
2
nh \
/
' и итерации
собственные-
1
! I
Tih\
[4] сходятся со скоростью р = 1 1 — tg^-^-l / 11 + tg - у 1, так что числа
итераций—-- i/h. Это совпадает с оценкой [8], полученной другим методом. Можно*
показать, что итерационная схема [4] обобщается на произвольную область.
9. Для системы уравнений второго порядка
' ^ *2 + Л ( * ) п = / • ( * ) ,
dt
584
u(0) = u ,
e
dt
(0) = u
e
(30>
оопеременно-трехугольная схема имеет вид
У„ + Aiy + А у
2
А
y-ft + гУ
= F,
у (0) = и ,
у (т) =
0
+
А
2У
=
\
(
3 1
)
и ,
9
еде
у « *= ^
=
*«
2j
y = y ~\
y
2
t'
у*
1 =
y
i
+
1
-
2
y
i
+
y
i
"
1
)
/
t
2
'
2
щ = щ +
Если Л — симметричная матрица,
(
хщ+<0.Ъх {А(0)щ-1(0)).
= А , то схема имеет второй порядок точности.
2
Поступила в редакцию
9.01.1964
Цитированная
литература
1. А. А. С а м а р с к и й . Однородные разностные схемы на 'неравномерных сетках
для уравнений параболического типа. Ж. вычисл. матем. и матем. физ., 1963, 3,
№ 2, 266—298.
2 . А. N. T i k b o n o v , A. A. S a m а г s к у. On the theory of homogeneous diffe­
rence scheihes. Outlines of the Joint Soviet-American Symposium on Partial Dif­
ferential Equations, 1963, August, Novosibirsk, 266—274.
3. A. A. S a m ia r s к у. On numerical methods of solving multi-dimensional problems.
Outlines of,the Joint Soviet-American Symposium on Partial Differential Equations,
1963, August, Novosibirsk, 236—240.
4 . D. W. P e а с e m a n, H. H. R а с h f о>r d. The numerical solution of parabolic
and elliptic differential equations. J. Industr. Math. S o c , 1955, 3, № 1, 28—41.
-5. В. К. С а у л ь е в . Интегрирование уравнений параболического типа методом се­
ток. М., Физматгиз, 1960.
6. А. А. С а м а р с к и й . Об одном экономичном разностном методе решения много­
мерного параболического уравнения в произвольной области. Ж. вычисл. ма­
тем. и матем. физ., 1962, 2, № 5, 787—811.
7. Д. К. Ф а д д е е в , В. Н. Ф а д д е е в а. Вычислительные методы линейной ал­
гебры. М . — Л . , Гостехиздат, 1963.
8. М. L е е s. A note on the convergence of alternating direction methods. Math. Comput.,
1962, 16, № 7, 70—75.
УДК 518:517.944/.Э47
ПРИБЛИЖЕННОЕ РЕШЕНИЕ МЕТОДОМ ПРЯМЫХ
ОДНОГО ДИФФЕРЕНЦИАЛЬНОГО УРАВНЕНИЯ
В ЧАСТНЫХ ПРОИЗВОДНЫХ ЭЛЛИПТИЧЕСКОГО ТИПА I
Е.
О.
ОМАРОВ
(Караганда)
В данной статье рассматривается решение краевой задачи
2
Аи
+ аАи + Ъи =
/ \
ди
дп
/ (аг,
у),
(1)
(s)
()
2
в некоторой плоской прямоугольной области G методом прямых (функции g (s), g (s)
и их производные на контуре считаются непрерывными); предполагается, что данная
задача имеет единственное решение. Многие задачи математической физики сводятся
x
2
585
1/--страниц
Пожаловаться на содержимое документа