close

Вход

Забыли?

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

?

Обоснование корректности неявного итерационного полинейного рекуррентного метода решения разностных эллиптических уравнений.

код для вставкиСкачать
Вестник КемГУ
№ 1 (45) 2011
УДК 519.632.4
ОБОСНОВАНИЕ КОРРЕКТНОСТИ НЕЯВНОГО ИТЕРАЦИОННОГО ПОЛИНЕЙНОГО
РЕКУРРЕНТНОГО МЕТОДА РЕШЕНИЯ РАЗНОСТНЫХ ЭЛЛИПТИЧЕСКИХ УРАВНЕНИЙ
А. А.Фомин, Л. Н. Фомина
ARGUMENTATION OF CORRECTNESS OF IMPLICIT ITERATION LINE-BY-LINE RECURRENCE
METHOD FOR SOLVING A DIFFERENCE ELLIPTICAL EQUATIONS
А. A. Fomin, L. N. Fomina
Рассматривается матрично-векторная форма записи алгоритма неявного итерационного полинейного
рекуррентного метода решения пятидиагональных систем линейных алгебраических уравнений с матрицами
положительного типа. Путем пошаговых устойчивых преобразований выводится общий вид и структура результирующего оператора. Приводится обоснование корректности метода.
Matrix –vector form of recording the algorithm of implicit iteration line-by-line recurrence method is proposed
for solving five-diagonal matrix systems of linear algebraic equations with a positive type matrixes. Structure of a
resultant operator converting original system to the one with an about upside triangular matrix is deduced by means
of stepwise stable transformations. Argumentation of correctness of the method is given.
Ключевые слова: разностные эллиптические уравнения, итерационный метод решения, корректность
метода.
Keywords: a difference elliptic equations, iteration method, correctness of the method.
Как известно, решение краевых задач тепло- и
массопереноса связано с разностной дискретизацией их исходных дифференциальных постановок, что
в свою очередь, приводит к возникновению систем
линейных алгебраических уравнений (СЛАУ) вида
G
G
(1)
AΦ = f .
G
Здесь A – матрица системы, Φ – искомый векG
тор решения, f – вектор правой части системы.
Подобные матрицы обладают высоким порядком и
ленточной структурой [1]. Для многомерных задач,
полученные таким образом СЛАУ разрешаются, как
правило, итерационными методами.
В работах [2, 3] излагаются различные алгоритмы и рассматриваются результаты тестовых расчетов неявного итерационного полинейного рекуррентного метода для случаев, когда A – матрица положительного типа. Данный метод демонстрирует
свою высокую эффективность, однако в силу того,
что в общем случае записать его в канонической
форме [1]
G
G
G
G
(2)
Pk +1(Φk +1 − Φk ) = f − AΦk
Рис. 1.
Пусть для двумерных задач пятиточечное разностное уравнение имеет следующий вид:
aP Φij = aE Φi +1 j + aW Φi −1 j +
ij
ij
ij
+aN Φij +1 + aS Φij −1 + bij ,
ij
где
1 < i < n,
ij
1< j <m,
причем
aP = aE + aW + aS + aN . Здесь n, m – количество
не представляется возможным, корректность
каждого расчета необходимо фактически доказывать вычислением нормы невязки для очередного
приближения решения с учетом оценки нормы обратной матрицы системы. Поэтому в целях теоретической завершенности изложения этого метода
представляется необходимым в общем случае обосновать его корректность, то есть показать, что в
случае сходимости решения (и, следовательно, выG
G
полнении условия Φk +1 − Φk
→ 0 ), полу-
узлов сеточного разбиения расчетной области по
координатам x, y соответственно. Тогда матрица А
имеет пятидиагональную структуру (рис. 1). Общее
число неизвестных и, следовательно, размерность
матрицы А равно числу N = n×m. Как известно, такая матрица может быть разбита на отдельные
квадратные клетки, количество которых, для определенности, будет n×n, тогда размерность каждой
клетки – m×m. Здесь и далее для наглядности и не в
ущерб общности изложения материала выбрана
разностная сетка 5×5. Понятно, что в рамках рассматриваемого случая только клетки на диагонали и
около диагональные будут отличны от нуля, все остальные – нулевые. Поклеточная структура матрицы А и состав двух клеток (для примера) имеют вид:
k →∞
ченное решение удовлетворяет исходной системе
линейных алгебраических уравнений.
39
Вестник КемГУ
№ 1 (45) 2011
⎛ A11 A12 A13 A14 A15 ⎞
⎜
⎟
⎜ A21 A22 A23 A24 A25 ⎟
A = ⎜ A31 A32 A33 A34 A35 ⎟ ,
⎜
⎟
⎜ A41 A42 A43 A44 A45 ⎟
⎜A A A A A ⎟
⎝ 51 52 53 54 55 ⎠
0
0 ⎞
⎛ aP11 − aN 11 0
⎜
⎟
0 ⎟
⎜ −aS 12 aP12 − aN12 0
⎜
⎟
A11 = ⎜ 0 − aS13 aP13 − aN13 0 ⎟ ,
⎜0
0 − aS14 aP14 − aN14 ⎟
⎜
⎟
⎜0
⎟
0
0
−
a
a
S15
P15 ⎠
⎝
0 ⎞
⎛ −aE 11 0 0 0
⎜
⎟
0 ⎟
⎜ 0 − aE12 0 0
⎜
⎟
0 − aE13 0
0 ⎟.
A12 = ⎜ 0
⎜ 0
0 0 − aE14 0 ⎟
⎜
⎟
⎜ 0
⎟
0
0
0
a
−
E
15 ⎠
⎝
В матричном виде эти же самые первые два шага преобразований полинейного рекуррентного метода (вывод уравнений (6) и (7)) представляют собой воздействие на исходную систему (1) двух не(12)
JG G
(12)
(11)
M (+) M (+) (AΦ − f ) = 0 .
11
(11)
первые клетки в верхнем ряду имеют следующий
вид:
(1 1)
M 11(+)
(12 )
M 11(+)
11
12
12
12
(4)
13
13
11
11
12
11
12
12
+(aE aS / aP )Φ21 + b11aS / aP + b12 .
11
12
11
12
11
Переобозначения коэффициентов позволяют
переписать последнее уравнение в виде:
αP Φ 12 = αN Φ 13 + αE Φ 22 + αSE Φ 21 + β12 ,
12
12
12
12
αN
12
11
= aN , αE
12
12
αSE
12
12
12
12
11
12
11
Подобное преобразование проводится и для
уравнения с центральным узлом (1,3). Для этого в
уравнении (5) исключается слагаемое Ф12, путем
подстановки вместо него правой части (6) умноженной на отношение aS / αP . После приведения
13
12
подобных получается соотношение
(aP − αN aS / αP )Φ13 = aN Φ14 +
13
12
13
12
13
+aE Φ23 + αE aS / αP Φ22 +
13
12
13
(7)
12
+αSE aS / αP Φ21 + β12aS / αP + b13 .
12
13
12
0
0
0
1
0
0
1
0 0 0
⎛1
0
0 0
⎜⎜⎜
1
0 0
⎜⎜ 0
⎜
= ⎜⎜⎜ 0 a S / αP 1 0
13
12
⎜⎜
0
0 1
⎜⎜ 0
⎜⎜
0
0 0
⎝⎜ 0
13
(12)
ставляют собой частный случай так называемых
элементарных нижних треугольных матриц, с помощью которых матрица исходной СЛАУ преобразуется к треугольному виду [4]. Такие матрицы не
вырождены, а само преобразование будет устойчивым в силу свойства строчного диагонального преобладания исходной матрицы A. Следовательно,
клетки произведения имеют следующую структуру:
11
= aE ,
12
0
0 ⎞⎟
⎟⎟
0 ⎟⎟
⎟⎟
0 ⎟⎟⎟ ,
⎟⎟
0 ⎟⎟
⎟⎟
1 ⎟⎟⎠
0 ⎞⎟
⎟⎟
0 ⎟⎟
⎟⎟
0 ⎟⎟⎟
⎟⎟
0 ⎟⎟
⎟⎟
1 ⎠⎟⎟
рицы. Понятно, что матрицы M (+) и M (+) пред-
= aE aS / aP , β12 = b11aS / aP + b12 .
11
1
(11)
(6)
где αP = aP − aN aS / aP ,
12
0
(11)
M 11(+)
ния (4) вместо третьего слагаемого. После приведения подобных получается соотношение
(aP − aN aS / aP )Φ12 = aN Φ13 + aE Φ22 +
12
0
⎛× 0 0 0 0 ⎞⎟
⎜⎜
⎟
⎜×× 0 0 0 ⎟⎟
= ⎜⎜⎜ 0 0 × 0 0 ⎟⎟⎟ ,
⎜⎜ 0 0 0 × 0 ⎟⎟
⎜⎜ 0 0 0 0 × ⎟⎟
⎝⎛
⎠⎞
(9)
⎜⎜× 0 0 0 0 ⎟⎟
⎟
0
0
0
0
×
⎜
(12)
⎟
M 11(+) = ⎜⎜⎜ 0 ×× 0 0 ⎟⎟⎟
⎜⎜ 0 0 0 × 0 ⎟⎟
⎜⎜ 0 0 0 0 × ⎟⎟
⎝
⎠
остальные диагональные клетки – единичные мат-
Уравнение (3) умножается на отношение
/ aP и подставляется в правую часть уравне-
12
0
13
(5)
aS
⎛
1
⎜⎜
⎜⎜ a / a
⎜⎜ S12 P11
= ⎜⎜⎜
0
⎜⎜
0
⎜⎜
⎜⎜
0
⎜⎝
или, более кратко, структуру:
a P Φ 13 = a E Φ 23 + a N Φ 14 + a S Φ 12 + b13 .
13
(12)
операторов M (+) и M (+) отличны от нуля, из них
a P Φ 12 = a E Φ 22 + a N Φ 13 + a S Φ 11 + b12 ;
12
(8)
При этом только диагональные клетки матриц
Преобразования СЛАУ начинаются вдоль направления по координате y для j от 1 до m на линии
i = 1. Первые три уравнения для узлов (1,1), (1,2) и
(1,3) имеют следующий вид
(3)
a P Φ 11 = a E Φ 21 + a N Φ 12 + b11 ;
11
(11)
вырожденных операторов M (+) и M (+) [2]:
12
40
Вестник КемГУ
№ 1 (45) 2011
⎛
⎞⎟
⎜
⎜⎝ M (+) M (+) A ⎟⎠
11
(12)
(11)
⎛ (12) (11) ⎟⎞
⎜
⎜⎝ M (+) M (+) A ⎟⎠
12
(12)
⎛ × × 0 0 0 ⎟⎞
⎜⎜
⎟
⎜ 0 × × 0 0 ⎟⎟
⎜
= ⎜⎜ 0 0 × × 0 ⎟⎟,
⎜⎜ 0 0 × × × ⎟⎟⎟
⎜⎝ 0 0 0 × × ⎟⎟⎠
⎛× 0 0 0 0 ⎞⎟
⎜⎜
⎟
⎜× × 0 0 0 ⎟⎟
⎜
= ⎜⎜× × × 0 0 ⎟⎟ .
⎜⎜ 0 0 0 × 0 ⎟⎟⎟
⎜⎝ 0 0 0 0 × ⎠⎟⎟
(12 )
B 12(+ )
0
0
α SE a S
12
0
0
13
αP
12
0
0
0
0
0
0 ⎞⎟
⎟⎟
0 ⎟⎟
⎟⎟
⎟⎟
0 ⎟⎟⎟
⎟⎟
⎟⎟
0 ⎟⎟⎟
⎟
0 ⎟⎠⎟
или, более кратко, структуру
⎛ 0 0 0 0 0 ⎞⎟
⎜⎜
⎟
⎜ 0 0 0 0 0 ⎟⎟
(12)
B12(+) = ⎜⎜⎜ 0 × ×0 0 ⎟⎟ .
⎜⎜ 0 0 0 0 0 ⎟⎟⎟
⎜⎝ 0 0 0 0 0 ⎟⎠⎟
(11)
Произведение M (+) M (+) A можно представить
(12)
⎛0
0
⎜⎜
0
⎜⎜⎜ 0
⎜⎜
α SE a S
⎜
12
13
= ⎜⎜⎜ 0 − 2
αP
⎜⎜
12
⎜⎜
0
⎜⎜ 0
⎜⎜
0
⎜⎝ 0
(12)
в виде суммы G(+) + L(+) , причем матрица
Все остальные клетки, включая диагональные
(12)
(12)
L(+) состоит из нулей, кроме второй клетки в верх-
Bll (+) , являются нулевыми матрицами. Очевидно,
нем ряду, которая имеет всего лишь один ненулевой
элемент – коэффициент «внешаблонного» узла [2]:
⎛ 0 0 0 0 0 ⎞⎟
⎜⎜
⎟
⎜⎜ 0 0 0 0 0 ⎟⎟
(12)
L12(+) = ⎜⎜×0 0 0 0 ⎟⎟⎟ ,
⎜⎜ 0 0 0 0 0 ⎟⎟
⎟⎟
⎜⎜
⎝ 0 0 0 0 0 ⎠⎟
что то же самое можно сказать и в случае квадратичной экстраполяции [2] с той лишь разницей, что
вид второй клетки в первом ряду будет несколько
иным. А именно:
⎛0
0
0
0
0 ⎞⎟
⎜⎜
⎟⎟
⎜⎜ 0
0
0
0
0 ⎟⎟
⎜⎜
⎟⎟
⎟⎟
⎜⎜
αSE aS
αSE aS
αSE aS
(12)
12
13
12
13
12
13
B12(+) = ⎜⎜⎜ 0 −3
3
0 ⎟⎟⎟
−
⎟⎟
αP
αP
αP
⎜⎜
⎟⎟
12
12
12
⎜⎜
0
0
0
0 ⎟⎟⎟
⎜⎜ 0
⎟
⎜⎜
0
0
0
0 ⎟⎟⎠
⎜⎝ 0
(12)
а матрица G(+) содержит все остальные элементы
(12)
(11)
матрицы M (+) M (+) A . Используя данное представление, система (8) перепишется в виде:
⎡ 1
(12) JG
(12) JG
(1 j ) ⎤ G
(10)
G (+) Φ + L(+) Φ = ⎢⎢ ∏ M(+) ⎥⎥ f .
⎢⎣ j = 2
⎥⎦
При помощи одного из способов аппроксимации значения искомой функции во «внешаблонном»
узле производится замена члена уравнения, содерJG(k +1)
(12) JG
(12) JG (k )
(12)
,
жащего его: L(+) Φ → L(+) Φ + θB(+) ΔΦ
или, более кратко, структуру
⎛ 0 0 0 0 0 ⎞⎟
⎜⎜
⎟
⎜ 0 0 0 0 0 ⎟⎟
(12)
B12(+) = ⎜⎜⎜ 0 × × × 0 ⎟⎟ .
⎜⎜ 0 0 0 0 0 ⎟⎟⎟
⎜⎝ 0 0 0 0 0 ⎟⎟⎠
(12)
Тогда понятно, что комбинация θB(+) , добав-
JG(k +1)
G
G
= ( Φ(k +1) − Φ(k ) ) – приращение решегде ΔΦ
(12)
ленная к матрице G(+) , не изменит содержимое
ния. При этом алгоритм принимает итерационный
диагональных клеток последней. Соответственно
(12)
характер. Структура матрицы B(+) отражает собст-
(12)
элементы матрицы θB(+) и последующих подоб-
венно механизм аппроксимации значения искомой
функции во «внешаблонном» узле (2,1) третьего
уравнения системы, то есть ее ненулевые элементы
являются коэффициентами приближенных преобра-
ных матриц в процессе преобразований с помощью
элементарных нижних треугольных матриц не будут влиять на элементы главной и двух прилегающих побочных диагоналей итоговой матрицы сис-
(12)
зований уравнений системы. Так как B(+) умножа-
(12)
темы. Следовательно, добавление матрицы θB(+)
JG(k +1)
, то при схоется на приращение решения ΔΦ
дящемся решении данное произведение стремится к
нулю.
не изменяет свойство вырожденности (не вырожденности) преобразованной СЛАУ.
В итоге, после произведенной замены, уравнение (10) приобретает следующий вид:
(12)
Вторая клетка в первом ряду матрицы B(+) в
JG(k +1)
(12) JG (k +1)
(12)
G (+) Φ
+ θB(+) ΔΦ
+
случае линейной экстраполяции [2] имеет вид:
⎡ 1
(12) JG (k )
(1 j ) ⎤ G
+L(+) Φ = ⎢⎢ ∏ M (+) ⎥⎥ f .
⎣⎢ j = 2
⎦⎥
41
(11)
Вестник КемГУ
№ 1 (45) 2011
Последующее эквивалентное преобразование
(11) также выражается в виде воздействия невыро-
(1 m −1)
G (+)
(15)
JG(k )
⎡ 1
(1 j ) ⎤ G
Φ = ⎢⎢ ∏ M(+) ⎥⎥ f .
⎣⎢ j =m -1
⎦⎥
При этом структуры первой и второй клеток в
(13)
(1 m −1)
жденного оператора M (+) , построенного по аналогии (9), на обе части (11), а именно
JG(k +1)
(13) (12) JG (k +1)
(13) (12)
M (+) G (+) Φ
+ θM (+) B(+) ΔΦ
+
JG(k )
⎡ 1
(1 j ) ⎤ G
+M (+) L(+) Φ = ⎢⎢ ∏ M(+) ⎥⎥ f .
⎢⎣ j = 3
⎥⎦
(13) (12)
+L(+)
(1m −1)
первом ряду матрицы G(+)
(12)
(1 m −1)
первом ряду матриц L(+)
(12)
(13)
(13)
(13)
M(+) G(+) = G(+) + L(+) , где матрица L(+) имеет
(1 m −1)
G 11(+)
(12)
структуру аналогичную L(+) , то есть
(13)
L12(+)
⎛
⎜⎜
⎜
= ⎜⎜⎜
⎜⎜
⎜⎝
0 0 0 0 0 ⎞⎟
0 0 0 0 0 ⎟⎟⎟
0 0 0 0 0 ⎟⎟ .
0 × 0 0 0 ⎟⎟⎟
0 0 0 0 0 ⎟⎠⎟
L12(+)
(1 m − 1 )
позволяет записать следующее соотношение:
JG(k +1)
(13) JG (k +1)
(13) (12) ⎤
⎡ (13)
+ θ ⎢ B(+) + M (+) B(+) ⎥ ΔΦ
+
G (+) Φ
⎣⎢
⎦⎥
⎡ 1
(13) (12) ⎤ JG (k )
(1 j ) ⎤ G
⎡ (13)
+ ⎢ L(+) + M (+) L(+) ⎥ Φ = ⎢⎢ ∏ M (+) ⎥⎥ f
⎢⎣
⎥⎦
⎢⎣ j = 3
⎥⎦
(13)
при
(13)
(13)
(13)
(13)
B 12 (+ )
(1 m − 1 )
B 12 (+ )
(12)
B(+) = B(+) + M(+) B(+) ,
условии
(13)
В общем случае для произвольного j = J , при
увеличении индекса j, на линии i = 1 будет иметь
место соотношение
JG(k +1)
(1J ) JG (k +1)
(1J )
G (+) Φ
+ θB(+) ΔΦ
+
(14)
⎡ 1
(1J ) JG (k )
(1 j ) ⎤ G
+L(+) Φ = ⎢⎢ ∏ M (+) ⎥⎥ f ,
⎢⎣ j =J
⎥⎦
(1J )
(1J −1)
где M(+) G(+)
(1J )
(1J )
(1J )
(1J )
(1J −1)
(1J )
(1J )
(1J ) (1J −1)
L(+) = L(+) + M(+) L(+)
⎛ 0 0 0 0 0 ⎞⎟
⎜⎜
⎟
⎜ 0 0 0 0 0 ⎟⎟
= ⎜⎜⎜ 0 × × 0 0 ⎟⎟ – линейная экстраполяция,
⎜⎜ 0 0 × × 0 ⎟⎟⎟
⎜⎝ 0 0 0 × × ⎟⎟⎠
⎛ 0 0 0 0 0 ⎞⎟
⎜⎜
⎟
⎜ 0 0 0 0 0 ⎟⎟
= ⎜⎜⎜ 0 × × × 0 ⎟⎟ – квадратичная экстрапо⎜⎜ 0 0 × × × ⎟⎟⎟
⎜⎝ 0 0 0 × × ⎟⎟⎠
(12)
(13)
(12)
(12)
где M(−) G(−) = G(−) + L(−) ,
(12)
(12)
(12)
(13)
B(−) = B(−) + M(−) B(−) ,
(12)
(12)
(12) (13)
L(−) = L(−) + M(−) L(−) .
(1J )
= G(+) + L(+) ,
B(+) = B(+) + M(+) B(+)
⎛ 0 0 0 0 0 ⎞⎟
⎜⎜
⎟
⎜⎜ 0 0 0 0 0 ⎟⎟
= ⎜⎜ × 0 0 0 0 ⎟⎟ ,
⎜⎜ 0 × 0 0 0 ⎟⎟⎟
⎜⎝ 0 0 × 0 0 ⎟⎟⎠
Аналогичным образом рассматривается проход
по локальному направлению на линии i = 1 в сторону уменьшения индекса j. Выполнение подобной
цепочки преобразований по j → 2 приводит, в итоге, к следующему матричному уравнению
JG(k +1)
(12) JG (k +1)
(12)
G (−) Φ
+ θB(−) ΔΦ
+
(16)
⎡ m
(12) JG (k )
(1 j ) ⎤ G
+L(−) Φ = ⎢⎢ ∏ M (−) ⎥⎥ f ,
⎥⎦
⎣⎢ j =2
(13) (12)
⎡ 1
(13) JG (k )
(1 j ) ⎤ G
+L(+) Φ = ⎢⎢ ∏ M (+) ⎥⎥ f .
⎢⎣ j = 3
⎥⎦
будут сле-
ляция.
L(+) = L(+) + M(+) L(+) ,
JG(k +1)
(13) JG (k +1)
(13)
G (+) Φ
+ θB(+) ΔΦ
+
(1 m −1)
и B(+)
⎛ ×× 0 0 0 ⎞⎟
⎛ × 0 0 0 0 ⎞⎟
⎜⎜
⎜⎜
⎟
⎟
(1 m −1)
⎜⎜ 0 ×× 0 0 ⎟⎟
⎜ × × 0 0 0 ⎟⎟
= ⎜⎜ 0 0 × ×0 ⎟⎟ , G 12(+) = ⎜⎜⎜ 0 × × 0 0 ⎟⎟ ,
⎜⎜ 0 0 0 × × ⎟⎟⎟
⎜⎜ 0 0 × × 0 ⎟⎟⎟
⎜⎝ 0 0 0 × × ⎟⎟⎠
⎝⎜ 0 0 0 0 × ⎠⎟⎟
(1 m −1)
JG(k +1)
(13) JG(k +1)
(13) JG(k )
(13)
→ L(+) Φ + θB(+) ΔΦ
Замена L(+) Φ
или,
и вторых клеток в
дующими:
Как и на предыдущем шаге алгоритма пусть
(13)
JG(k +1)
JG(k +1)
(1 m −1)
Φ
+ θB(+)
ΔΦ
+
А в общем случае при обратном проходе для
произвольного j = J имеют место соотношения
(1J )
,
(1J +1)
M(−) G(−)
(1J )
.
(1J )
(1J )
(1J )
= G(−) + L(−) ,
(1J )
(1J +1)
B(−) = B(−) + M(−) B(−)
Окончание прохода по локальному направле-
(1J )
(1J )
(1J ) (1J +1)
L(−) = L(−) + M(−) L(−)
нию j = 1, m − 1 на линии i = 1 приводит к итоговому матричному уравнению:
42
.
,
Вестник КемГУ
№ 1 (45) 2011
позволяет получить систему с «зеркальными» шаблонами [2] на линии i = 1
Структуры первой и второй клеток в первом
(12)
ряду матрицы G(−) и вторых клеток в первом ряду
(12)
⎡ (1 m −1)
⎤ JG(k +1)
⎡ (1 m −1)
(12)
(12) ⎤ JG(k +1)
⎢G
+ G(−) − A⎥ Φ
+ θ ⎢ B(+)
+ B(−) ⎥ ΔΦ
+
⎢⎣ (+)
⎥⎦
⎢⎣
⎥⎦
m
⎡ 1
⎤G
⎡ (1 m −1)
(12) ⎤ JG(k )
(1j )
(1j )
+ ⎢ L(+)
+ L(−) ⎥ Φ = ⎢⎢ ∏ M(+) + ∏ M(−) − E ⎥⎥ f .
⎢⎣
⎥⎦
j =2
⎣⎢ j =m -1
⎦⎥
(12)
матриц L(−) и B(−) будут, соответственно, следующими:
(12 )
G 11(− )
⎛ × 0 0 0 0 ⎞⎟
⎛ × × 0 0 0 ⎞⎟
⎜⎜
⎟
⎜⎜
⎟
⎜ × × 0 0 0 ⎟⎟ , (1 2 )
⎜ 0 × × 0 0 ⎟⎟ ,
⎜
= ⎜⎜ 0 × × 0 0 ⎟⎟ G
= ⎜⎜⎜ 0 0 × × 0 ⎟⎟
⎟
1
2
(−
)
⎜⎜ 0 0 × × 0 ⎟⎟
⎜⎜ 0 0 0 × × ⎟⎟⎟
⎜⎝ 0 0 0 × × ⎟⎟⎠
⎜⎝ 0 0 0 0 × ⎟⎟⎠
(12 )
L 12(−)
(12)
B12(−)
(12)
B12(−)
(17)
⎛ 0 0 × 0 0 ⎞⎟
⎜⎜
⎟
⎜ 0 0 0 × 0 ⎟⎟
= ⎜⎜⎜ 0 0 0 0 × ⎟⎟ ,
⎜⎜ 0 0 0 0 0 ⎟⎟⎟
⎜⎝ 0 0 0 0 0 ⎟⎠⎟
⎛ × × 0 0 0 ⎞⎟
⎜⎜
⎟
⎜ 0 × × 0 0 ⎟⎟
= ⎜⎜⎜ 0 0 ×× 0 ⎟⎟ – линейная экстраполяция,
⎜⎜ 0 0 0 0 0 ⎟⎟⎟
⎜⎝ 0 0 0 0 0 ⎟⎠⎟
Рис. 2.
При этом структура преобразованной матрицы
всей системы (17) примет вид, представленный на
рис. 2. Здесь и далее черными крестиками обозначаются не измененные элементы исходной матрицы, а белыми крестиками – преобразованные. Совпадение структур первых двух клеток первых двух
рядов говорит о возможности их комбинации с целью обнуления первой клетки второго ряда. Действительно, если обозначить
⎛ × × 0 0 0 ⎞⎟
⎜⎜
⎟
⎜ × × ×0 0 ⎟⎟
= ⎜⎜⎜ 0 × × × 0 ⎟⎟ – квадратичная экстраполяция.
⎜⎜ 0 0 0 0 0 ⎟⎟⎟
⎜⎝ 0 0 0 0 0 ⎟⎟⎠
Здесь еще раз следует обратить внимание на
существо переходов
JG(k +1)
(1 j ) JG
(1 j ) JG (k )
(1 j )
L(+) Φ → L(+) Φ + θB(+) ΔΦ
(1)
A
(1 j ) JG
(1 j ) JG(k )
(1 j ) JG (k +1)
,
и L(−) Φ → L(−) Φ + θB(−) ΔΦ
(1 j )
(1m −1)
[G11(+)
(1)
тогда A11
(1 j )
в которых матрицы L(+) и L(−) содержат коэффи-
=
(12)
(1m −1)
+ G11(−) − A11 ] + θ [B(+)
(1m −1)
[G11(+)
(12)
+ B(−) ] ,
(12)
+ G11(−) − A11 ] в силу равен(1m −1)
ства нулю диагональных клеток матриц B(+)
циенты при неизвестном во «внешаблонном» узле, а
(1j )
=
и
(12)
(1j )
матрицы B(+) и B(−) выражают собой механизм
B(−) , причем, как уже отмечалось ранее, клетка
аппроксимации этого неизвестного через неизвестные в узлах основного шаблона. В качестве таких
механизмов ранее были рассмотрены так называемые линейная и квадратичная экстраполяции, хотя
понятно, что они не единственные и могут быть
другие способы выражения неизвестного во «внешаблонном» узле через неизвестные в узлах основного шаблона [3]. Как будет показано далее, с точки
зрения обоснования корректности метода, основным является тот момент, что каков бы не был в
общем случае механизм аппроксимации (компенсации), все коэффициенты этого механизма располагаются только в матрицах В. Поэтому в последующих рассуждениях механизм аппроксимации более
не детализируется.
В силу совпадения верхних наддиагоналей кле-
A11 – диагональная матрица, следовательно к ней
(1 m -1)
ток A11 и G11(+)
(12)
(1)
просто найти обратную матрицу
(1m −1)
Далее
вводится нижняя треугольная матрица преобразования («деления») H
(2)
(2)
, у которой первая клетка вто(1) −1
рого ряда H 21 = − A21[A11
]
, все диагональные
клетки – единичные матрицы, а остальные клетки –
нулевые матрицы. Умножение (17) слева на H
приводит к уравнению вида:
и нижних поддиагоналей клеток
A11 и G 11(−) разность G11(+)
(1)
[A11 ]−1 .
(12)
+ G11(−) − A11 пред-
ставляет собой диагональную клетку с положительными элементами. Тогда понятно, что вычитание из
JG(k +1)
, уравнений (15) и (16)
(1), записанного для Φ
43
(2)
и
Вестник КемГУ
№ 1 (45) 2011
⎡⎛ (2)
(12) ⎞⎤ JG(k+1)
(2) (2) ⎞
(2) (2) ⎛ (1 m−1)
⎟⎟⎥ Φ +
⎢⎜E(0) −E(p) H ⎟⎟A+E(p) H ⎜⎜G
+
G
(−) ⎟
⎢⎣⎝⎜
⎠
⎝⎜ (+)
⎠⎟⎦⎥
(12) ⎞ JG(k+1)
(2) (2) ⎛ (1 m−1)
+θE(p) H ⎜⎜B(+) +B(−) ⎟⎟⎟ΔΦ +
⎜⎝
⎟⎠
J
G
(19)
(
1
m
−
1
)
(12) ⎞ (k)
(2) (2) ⎛
+E(p) H ⎜⎜L(+) +L(−) ⎟⎟⎟Φ =
⎜⎝
⎟⎠
1
m
⎡⎛ (2)
(1j)
(1j) ⎞⎤
(2) (2) ⎞
(2) (2) ⎛
⎟G
⎜
= ⎢⎢⎜⎜E(0) −E(p) H ⎟⎟ +E(p) H ⎜⎜ ∏ M(+) + ∏M(−) ⎟⎟⎟⎥⎥ f
⎝
⎠
⎟⎠⎦⎥
⎜⎝j=m-1
j =2
⎣⎢
Рис. 3.
,
⎡ (2) (1 m −1)
(2) (12)
(2) ⎤ JG (k +1)
⎢H G
+ H G (−) − H A ⎥ Φ
+
(+)
⎢⎣
⎥⎦
JG(k +1)
⎡ (2) (1 m −1)
(2) (12) ⎤
+θ ⎢ H B(+)
+ H B(−) ⎥ ΔΦ
+
⎢⎣
⎥⎦
18)
⎡ (2) (1 m −1)
(2) (12) ⎤ JG (k )
+ ⎢ H L(+)
+ H L(−) ⎥ Φ =
⎢⎣
⎥⎦
m
⎡ (2) 1
(1 j )
(2)
(1 j )
(2) ⎤ G
= ⎢⎢ H
∏ M(+) + H ∏ M(−) − H ⎥⎥ f ,
⎢⎣
⎥⎦
j =m -1
j =2
причем структура матрицы уравнения (18) имеет
вид, представленный на рис. 3. Поскольку цель проведенных преобразований – изменить структуру
клеток во втором ряду по образцу первого со сдвигом на одну клетку вправо и при этом оставить остальные клетки исходной матрицы без изменений,
то для этого необходимо скомпоновать уравнения
JG(k +1)
, с уравнением (18) таким
(1), записанное для Φ
образом, чтобы в (1) второй ряд клеток был заменен
на второй ряд из уравнения (18). Для этого вводятся
(2)
Рис. 4.
представляет собой систему уравнений с матрицей,
структура которой представлена на рис. 4. Из вида
этой структуры сразу следует вывод о том, что исходная система уравнений разделилась на две подсистемы, первая из которых определяется коэффициентами клеток первого ряда матрицы, а вторая –
остальными коэффициентами. При этом, что важно,
решение второй подсистемы находится независимо
от решения первой. Используя переобозначения
(2)
(2)
(2) (2)
G = ⎛⎜⎜⎝ E(0) − E(p) H ⎞⎟⎟⎠ A +
(2) (2) ⎛ (1m −1)
(12) ⎞
+E(p ) H ⎜⎜G (+)
+ G (−) ⎟⎟,
⎝
⎠
(2)
(2) (2) ⎛ (1m −1)
(12) ⎞
B = E(p ) H ⎜⎜⎝ B(+) + B(−) ⎟⎟⎠ ,
(2)
две диагональные матрицы E(0) и E(p ) , причем у
(2)
E(0) почти все диагональные клетки – единичные
(2)
матрицы, кроме E22(0) , которая является нулевой, а
(2)
у E(p ) все наоборот – все диагональные клетки ну-
(12) ⎞
⎛ (1m −1)
⎜⎜ L
+ L(−) ⎟⎟ ,
⎝ (+)
⎠
(2)
(2)
(2) (2)
M = ⎛⎜⎜⎝ E(0) − E(p) H ⎞⎟⎠⎟ +
1
m
(2) (2) ⎛
(1 j )
(1 j ) ⎞
⎟
⎜
+E(p ) H ⎜⎜ ∏ M (+) + ∏ M (−) ⎟⎟⎟,
⎜⎝ j =m -1
⎠⎟
j =2
уравнение (19) окончательно можно переписать
в виде
JG(k +1)
(2) JG (k +1)
(2)
G Φ
+ θB ΔΦ
+
(20)
J
G
G
(
k
)
(2)
(2)
+L Φ = M f .
(2)
(2)
L
левые, кроме E22(p ) , которая является единичной.
(2)
(2)
Понятно, что E(0) + E(p) = E – тождественный
оператор. Полученная при этом сумма:
JG(k +1)
(2) (12)
(2) ⎞ JG(k +1)
(2)
(2) ⎡⎛ (2) (1 m−1)
+ E(p) ⎢ ⎜⎜H G(+)
+ H G(−) − H A⎟⎟⎟Φ
+
E(0) AΦ
⎜
⎟⎠
⎢⎣ ⎝
⎛ (2) (1 m−1)
(2) (12) ⎞ JG(k +1)
⎟
+θ ⎜⎜H B(+)
+ H B(−) ⎟ΔΦ
+
⎟⎠⎟
⎝⎜
⎛ (2) (1 m−1)
(2) (12) ⎞ JG(k ) ⎤
+⎜⎜H L(+)
+ H L(−) ⎟⎟⎟Φ ⎥ =
⎥⎦
⎝⎜
⎠⎟
1
m
⎡ (2)
1
j
)
(
)
(2)
(1j )
(2) ⎞⎤
2
(
(2) ⎛
⎟G
⎜
= ⎢⎢ E(0) + E(p) ⎜⎜H ∏ M(+) + H ∏M(−) − H ⎟⎟⎟⎥⎥ f
⎢⎣
⎝⎜
⎠⎟⎥⎦
j =m -1
j =2
(2)
= E(p ) H
(2)
В заключении выкладок, связанных с линией
i = 1 следует заметить, что все проведенные преобразования исходной системы представляют собой
линейные комбинации уравнений, в которых в качестве сомножителей всегда используются коэффициенты по модулю меньше единицы в силу изна-
или
44
Вестник КемГУ
№ 1 (45) 2011
вид оператора воздействия на первоначальную систему уравнений:
чального свойства построчного диагонального преобладания матрицы СЛАУ. Следовательно, проводимые преобразования: 1) устойчивы; 2) сохраняют
свойство построчного диагонального преобладания;
3) сохраняют противоположность знаков диагональных и внедиагональных элементов. Иными
словами
матрица
системы
(20)
(2 )
(2 ) ⎞
⎛ (2 )
W ( θ ) = ⎜⎜ G + θ B ⎟⎟ (рис. 4) продолжает
⎜⎝
(n) (n)
⎧ (n)
⎫
⎪
⎪
⎪
⎪
E(0) + E(p) H
⎪
⎪
⎪
⎪
⎪
⎪
1
m
⎡⎛
⎞
⎤
(n −1 j )
(n −1j ) ⎟
⎨⎜
⎬×
⎢
⎥
⎪
⎪
⎟
⎜
M
M
E
+
−
⎪
⎪
⎟
∏
∏
(+)
(−)
⎥⎪
⎟⎟
⎪⎪ ⎢ ⎜⎜
⎪
⎢
⎥
⎝
⎠
-1
2
j
m
j
=
=
⎪
⎩⎣
⎦ ⎭⎪
(n −1)
(n −1) (n −1)
⎧
⎫
⎪
⎪
⎪
⎪
+
E
E
H
(0)
(p)
⎪
⎪
⎪
⎪
⎪
1
m
⎞
⎤⎪
(22)
×⎨ ⎡⎛⎜
(n −2 j )
(n −2 j ) ⎟
⎬ × ...
⎢
⎥
⎪
⎟
⎪⎪ ⎢ ⎜⎜ ∏ M(+) +∏ M(−) ⎟⎟ − E ⎥ ⎪
⎪
⎪
⎪⎪ ⎢ ⎜⎝ j =m -1
⎠⎟
j =2
⎪
⎩⎣
⎦⎥ ⎪
⎭
1
m
⎧
⎡⎛
⎤⎫⎪
1
j
(
)
(1j ) ⎞
⎪ (2)
(2) (2) ⎜
⎟
... × ⎪⎨E(0) + E(p) H ⎢⎢ ⎜⎜ ∏ M(+) +∏ M(−) ⎟⎟⎟ − E ⎥⎥ ⎪⎬ ×
⎪
⎢⎣ ⎝⎜ j =m -1
⎥⎦⎭
⎠⎟
⎪⎩
⎪⎪⎪
j =2
⎪
J
G
G
(∗)
⎛
⎞
×⎜⎜AΦ − f ⎟⎟⎟=0.
⎟⎠
⎜⎝
⎠
оставаться невырожденной. Из проведенных рассуждений также следует еще один очень важный вывод: эквивалентные преобразования группируются в
G
матрицах
(2)
,
только в матрице
(2)
L
B
M
,
(2)
(2)
, а приближенные –
.
Понятно, что решение подобной системы является также решением исходной системы (1) поскольку фигурные скобки представляют собой комбинацию невырожденных элементарных нижних и
верхних матриц преобразований, которая не приводит к возникновению других дополнительных решений.
На основании проведенных исследований показано, что алгоритм метода путем пошаговых устойчивых преобразований переводит исходную систему уравнений к виду:
G
G
G
G
(n )
W ( θ ) ( Φk +1 − Φk ) = R ( AΦk − f ) ,
Рис. 5.
где W
линиям i = 2, n − 1 (рядам клеток матрицы СЛАУ)
приводит к тому, что исходная система преобразуется к виду:
JG(k +1)
(n ) JG (k +1)
Φ
+ θ B ΔΦ
+
J
G
G
(
k
)
(n )
(n )
+L Φ = M f ,
(21)
только
W
(n )
в
(n )
,
матрице
(θ ) = G
(n )
(n )
L
+ θB
,
B
(n )
M
(n )
(n )
,
, а приближенные
причем
G
матрица
по свой структуре четы-
(n )
,
(n )
L
и
M
(n )
(θ) и R
вы-
Литература
1. Ильин, В. П. Методы неполной факторизации
для решения алгебраических систем [Текст] /
В. П. Ильин. – М.: Физматлит. – 1995. – 288 c.
2. Фомина, Л. Н. Использование полинейного
рекуррентного метода с переменным параметром
компенсации для решения разностных эллиптических уравнений [Текст] / Л. Н. Фомина // Вычислительные технологии. – ИВТ СО РАН. – 2009. –
Т. 14. – № 4. – C. 108 – 120.
3. Фомин, А. А. Об одном варианте полинейного рекуррентного метода решения разностных эллиптических уравнений [Текст] / А. А. Фомин,
Л. Н. Фомина // Вестник Томского государственного университета. Математика и механика. – 2010. –
№ 2. – С. 20 – 27.
4. Самарский, А. А. Численные методы [Текст] /
А. А. Самарский, А. В. Гулин. – М.: Наука. –1989.
рехдиагональная и положительного типа (рис. 5),
откуда следует последовательно-поклеточная разрешимость полученной системы.
В случае сходимости итерационного процесса
JG(k +1)
→ 0 , в результате
имеет место стремление ΔΦ
которого влияние члена, содержащего приближенные преобразования, становится несущественным.
Поскольку операторы
(n )
писываются явным образом. Нетрудно видеть, что в
этом случае вопрос о корректности метода разрешается естественным образом.
в которой эквивалентные преобразования содержат-
G
– удобно разрешаемый оператор с че-
При этом матрицы операторов W
(n )
ся в матрицах
(θ)
тырехдиагональной почти верхнетреугольной матрицей,
R – оператор невырожденных эквивалентных
преобразований (произведение фигурных скобок в
(22)),
а θ – итерационный параметр компенсации.
Повторение
проведенных
эквивалентноприближенных преобразований по всем расчетным
G
(n )
– суть
чисто эквивалентные преобразования, не меняющие
решение исходной системы, то нетрудно путем обратной цепочки преобразований получить явный
45
1/--страниц
Пожаловаться на содержимое документа