О последовательностях двухчастотных разложений

64

И.Е. Захаренкова, А.Ф. Лаговский, И.И. Шагимуратов

Список литературы

1. Larkina V.I., Nalivayko A. V., Gershenzon N.I. et al. Observation of VLF emission related with seismic activity on the Intercosmos-19 satellite // Geomagn. Aeron. 1983. Vol. 23. P. 684-687.

2. Гайворонская Т.В., Зеленова Т.И. Анализ вариаций критических частот foF2 во время землетрясений 1976 и 1984 гг. в Средней Азии: Препринт № 5 (831). М.: ИЗМИРАН, 1989.

3. Липеровский В.А., Похотелов О.А., Шалимов С.А. Ионосферные предвестники землетрясений. М.: Наука, 1992.

4. Пулинец С.А., Легенька А.Д., Зеленова Т. И. Зависимость сейсмо-ионосфер-ных вариаций в максимуме слоя от местного времени // Геомагнетизм и аэрономия. 1998. Т. 38. № 3. С. 178.

5. Pulinets S.A., Legen'ka A.D., Gaivoronskaya T.V., Depuev V.Kh. Main phenomenological features of ionospheric precursors of strong earthquakes // Journal of Atmospheric and Solar-Terrestrial Physics. 2003. Vol. 65. P. 1337-1347.

6. Pulinets S.A., Boyarchuk К.А. Ionospheric Precursors of Earthquakes. Springer, 2004.

7. Краткосрочный прогноз катастрофических землетрясений с помощью радиофизических наземно-космических методов: Тез. докл. конф. / Под ред. В.Н. Страхова, В. А. Липеровского. М.: Изд-во ОИФЗ, 1998.

8. Houminer Z., Soicher H. Improved short-term predictions of f0F2 using GPS time delay measurements // Radio Science. 1996. Vol. 31. № 5. Р. 1099-1108.

9. Krankowski A., Baran L.W., Shagimuratov I.I. Modeling and forecasting of TEC obtained with IGS Network over Europe // Proceed. Workshop&Simposium, 10 years IGS, March 01-05, 2004. Berne, Switzerland, 2004.

10. Ruzhin Yu.Ya., Oraevsky V.N., Shagimuratov I.I., Sinelnikov V.M. Ionospheric precursors of earthquakes revealed from GPS data and their connection with "sea-land" boundary // Proceed. 16th Wroclaw EMC Symposium, 2002.

11. Baran L.W., Shagimuratov I.I., Tepenitsina N.J. The Use of GPS for Ionospheric Studies // Artificial Satellites. 1997. Vol. 32. № 1. P. 49 — 60.

12. Dobrovolsky I.R., Zubkov S.I., Myachkin V.I. Estimation of the size of earthquake preparation zone // Pure and Applied Geophisics. 1979. Vol. 117. P. 1025-1044.

Об авторах

И.Е. Захаренкова — асп., РГУ им. И. Канта.

А.Ф. Лаговский — канд. техн. наук, проф., РГУ им. И. Канта.

И.И. Шагимуратов — канд. физ.-мат. наук, ЗО ИЗМИРАН.

УДК 519.615.5

А.А. Буздин, Е.А. Васильева, К.С. Латышев

О ПОСЛЕДОВАТЕЛЬНОСТЯХ ДВУХЧАСТОТНЫХ РАЗЛОЖЕНИЙ

Предлагается метод решения больших систем линейных уравнений, основанный на неполном блочном разложении блочных трехдиагональных матриц, обладающий следующим свойством: пусть N — число неизвестных в блоке матрицы системы. Тогда при выборе логарифмической последовательности раз-

Вестник РГУ им. И. Канта. 2006. Вып. 10. Физико-математические науки. С. 64 — 69.

ложений k = O(log N) оценка для энергетической нормы оператора перехода не будет зависеть от числа блоков.

We present a method for solving large systems of linear equations, which is based on the incomplete block decomposition for block tridiagonal matrices and has the following property: let N be a number of unknowns in the block of the system matrix. Then if we choose a logarithmical sequence of decompositions k = O(log N), the estimate for the energy norm of the iteration operator will be independent of the number of blocks.

1. Введение

Пусть блочная матрица Ke Rnmxnm системы уравнений

K y = f, y, fe Rnm;

K = blockdiag {Li-1, Di, Li}.

Полное блочное разложение для матрицы K имеет вид

K =

где L, U — соответственно нижняя и верхняя блочнотреугольные матрицы, а T — блочнодиагональная матрица T = blockdiag {Ti, ..., Tn},

T1 = D1, Ti = Di - Lia1 Ti-11 Li-1, i > 1.

Неполное блочное разложение получается, если в (1.3 —1.4) заменить Ti-i или Li-1 Ti-1 Li-1 их некоторой аппроксимацией. Существуют

различные возможности аппроксимации Ti. Рассмотрим одну из них

[7].

Матрица M3 легко обратима, если система линейных уравнений

М3 y = х, где вектор x e Rn, решается за O(n) арифметических действий.

Определение 1.1. Пусть задана система линейных уравнений (1.1) с регулярной матрицей K. Назовем легкообратимую матрицу М3 (сильным) фильтром, где 3 с Rn, если справедливо равенство М3 e = K e, V e e 3, а 3 называется тестовым подпространством.

Для блочнодиагональных матриц вида (1.2) можно построить фильтры М3 при помощи неполных блочных разложений (см. [7]). Эти разложения имеют вид, аналогичный полному разложению K:

М3 = (L + T) T1 (LT + T), где L и U соответственно нижняя и верхняя блочнодиагональные матрицы; T = blockdiag{ T}; T1 = D1, Ti = Di - 0i_1, i > 1. При этом ленточная k x k матрица 0i.1 удовлетворяет условию фильтра

i-i qj = Li-1 ¥¿1 Ui-1 q

для тестовых векторов q/ еЭТ, j = 0, ... , p, с Rk.

Построенные таким образом матрицы М3 удовлетворяют условию фильтра (1.5) на тестовом подпространстве

3 := span {e0, ... , ep}, e/ = x  q/, где x e Rm,

x  y = (X1y1, X1y2, ... , X1yk, X2y1, X2y2, ... , Xmy1, Xmy2, ... , Xmyk ) .

65

66

А.А. Буздин, Е.А. Васильева, К.С. Латышев

При выборе тестовых векторов qí в виде Цу = эт (V/ п х), где 1 ^ V/ 5 ^ к, V' е М получаем метод, который при V' и 1 сильно подавляет гладкие части ошибки, а при V' и к приобретает сглаживающие свойства.

В работах [1; 2] были построены и исследованы упрощенные фильтры М3, названные касательным и двухчастотным разложениями. Хотя они и не удовлетворяют точечным условиям фильтрации (1.5), но обладают фильтрующими свойствами в слабом смысле.

Определение 1.2. Будем называть легкообратимую матрицу M3 слабым е- фильтром по отношению к 3 с Ип, если

То что двухчастотное разложение является слабым е-фильтром, позволяет, как это будет доказано в дальнейшем, по аналогии с [1; 6; 7], построить последовательность двухчастотных разложений MV со следующими характеристиками сходимости. Пусть т — число неизвестных в блоке матрицы К. Тогда, если выбрать, как и в работе [7], логарифмическую последовательность разложений к = 0(1^ т), энергетическая норма составного оператора перехода ограничена и не зависит от числа блоков.

2. Двухчастотное разложение

Пусть блочная матрица K системы уравнений Ku = f имеет вид

K = Ь1оскШШа^{^, D, -Ь},

где ^ L е Ит т; L = ЬТ; D = БТ; ^ L > 0; D > 2L.

Приведем определение и основные свойства двухчастотного раз-

1

ложения. Отметим, что матрицы Т можно записать в виде Т = Ь2 ^

1 11 Ь2, где С = Ь2 D Ь2, а £(Х) — некоторые рациональные функции.

Определение 2.1. Для блочной трехдиагональной симметричной матрицы К вида

М =

Т =b1ockdiag{Т}, Т = С, Т = £

V _ V

Параметры С (А,(г)) при I = 1, 2 удобно вычислять по формулам: £1(Х(г)) = Х(г), С(Х(г)) = Х(г) _ 1Д-1(Х(г)), I > 1.

Определение и доказательство существования двухчастотного разложения для матриц более общего вида можно найти в работах [2 — 4].

В [2] была получена оценка скорости сходимости двухчастотного разложения для задачи (2.2 — 2.3). Приведем основные лемму и теорему.

Л 1 1 ^ 1 1

Обозначим через § = Ь2 Б Ь2, К = Ь2 К Ь2 модифицированные опера-

тор перехода и матрицу системы соответственно.

Лемма 2.1. Пусть Vа) = Х(1) - 2, v(2) = Х(2) - 2, С = С - 21, С = Ьіоск-diagonal{ С }. Тогда для модифицированного оператора перехода Б ЦБи

^ ||Б1 иК, где Б1 = (С -V(1)I) (С -V(2)I) ^С + Л(1У2)I^ 2.

Норма оператора перехода удовлетворяет неравенству

Нк^ (с-у0)ї) (с - у(2)і) [с+т

Для того чтобы получить наилучшую скорость сходимости, мы должны выбрать параметры v(1) и v(2) таким образом, чтобы

ч-2

(С -v(1)I) (С -v(2)I) ) + •/

V(1)V(2) I

= Ш1П .

Пусть vmin/ vmax — соответственно минимальное и максимальное собственные значения (или их оценки) матрицы С . Тогда задача минимизации (2.4) эквивалентна поиску параметров V(1), V(2), при которых

тах Ги^іу,) = т1п,

vm1n — V — Vmax

rv

,<2)(У)|:

і2

Теорема 2.1. Пусть у0 =-

-, 8о =

1 -тІУо V1 + л/ь ,

^0 = 0 + ^/Ро — 1 ) , V = VVт1пVтах .

, во =

2-5п

Тогда оптимальные параметры для задачи минимизации (2.5) равны

Орі = а

= а 0 v 0, <рі =v о/а о.

Минимизируемая величина є = тах

*т1п — v — vm

Поэтому для нормы оператора перехода справедлива следующая оценка:

5о

Замечание 2.1. Пусть N — число неизвестных в блоке матрицы системы К. Тогда для модельной задачи (уравнение Пуассона) оценка скорости сходимости |5|к = 0(1 / N имеет тот же порядок, что и для методов переменных направлений и последовательной верхней релаксации.

Замечание 2.2. Двухчастотное разложение — это слабый є-фильтр: позволяющий аналогично работам [1; 6; 7] построить последовательность двухчастотных разложений М^, с такими же свойствами сходимости.

3. Последовательности двухчастотных разложений

Построим последовательность двухчастотных разложений М^, и получим оценки для скорости сходимости исследуемой составной итерации.

67

2

2

2

г

А.А. Буздин, Е.А. Васильева, К.С. Латышев

68

Лемма 3.1. Пусть М^",М^ М^1^24

х<!>

последователь-

ность двухчастотных разложений. Обозначим через Б оператор перехода,

соответствующий М

я(2!-1)д(2! >

. Тогда для нормы оператора Бп = П;=1 Б

П (с -v(2г-1)I) (с -^ Г С + лМ2г-1У2г) I У ;=1 Г у

, где V(^ = Х( і) - 2 .

Теорема 3.1. Пусть Vmin, Vmax — соответственно минимальное и максимальное собственные значения (или их оценки) матрицы С . Пусть далее

Л. л1/к

5о =

1 -Уго~ 1 +^

Vо = Vmin/ У о =

л2

ч

п У о

, во =

2

2-5о

(Тр0 /, V? =7^(і=о,1,кк -1).

Если в качестве параметров выбрать = а^ги, vУ,opt = V0 / а0, то

для минимизируемой величины е из (3.2) справедлива следующая оценка:

Д2) - л,о

2-50

= 1 - О

Тогда норму оператора перехода можно оценить следующим образом:

Л 1 л

= 1 - О

Эта теорема описывает качественное поведение нормы операторов перехода в зависимости от числа применяемых разложений. Более реалистичную количественную оценку дает следующая теорема, которую мы приведем без доказательства.

Теорема 3.2. Пусть X тіп Хтах — соответственно минимальное и максимальное собственные значения (или их оценки) обобщенной проблемы собственных значений Би = X Ь и и "^тіп Хтіп 2 Vітах Хтах 2, а к = 2р . Тогда оптимальные параметры Х^ можно вычислить по следующему алгоритму:

V •

1. Вычисляем цр = т1п .

2. Вычисляем Ці по формуле ц =

2л/^

7+1

1 + Ці+1

3. Вычисляем 50 =

1 -УЙ-о~

1+ УІЦ0

4. Вычисляем в0 = 2/(2 - 50).

5. Вычисляем Т = УІ(во - 1)/во.

(і = р -1, р - 2,к ,0).

2

2

. V

Г тах у

ао =

2

V

ь =

V

V тах у

V

V

V тах у

V

тах

2

6. Вычисляем а10) = V^+f} ^ = ^Т+Т) “ НЙХ°д“м 2^ метров а(1+1),b(l+1) при помощи 21 параметров а(1+1),b(l+1) (I = 1, 2, ... , 21):

af+v =1 + «!') (1 + 2W ‘t) ' 2 -^ i+1,

+ + W ÎN « =1 + 2M »!')+, fi1 + 2"M *(° j - H- i+1 ,

bf+1) =1 + bf -J (1+ H- i+1 b(i ) ^ 2 -^ i+1,

b(i+1) 2' +1-1 =1 + 2Й M bf) +1 l(1 + 2M b Г) j - Ц i+1 .

7. Вычисляем оптимальные параметры v<2-1> =vmaxa(p),

v<21>=v bip),

max 1 7

1 = 1,2,... ,2p.

В этом случае энергетическая норма оператора перехода Sn удовлетворяет оценке ||Sn||K =5 Cpß(), где константаС « 1.

Список литературы

1. Buzdin A. Tangential decomposition // Computing. 1998. Vol. 61: Р. 257 —

276.

2. Buzdin A., Wittum G. Two-Frequency Decomposition: Preprint / Universität Heidelberg. 2000.

3. Буздин А.А., Васильева Е.А. Об одном варианте метода неполного блочного разложения // Вестник КГу. Вып. 1 — 2. Сер. Информатика и телекоммуникации, 2005. С. 70 — 76.

4. Они же. Неполное блочное разложение, основанное на аппроксимациях Паде // Математическое моделирование (в печати).

5. Самарский А.А., Николаев Е.С. Методы решения сеточных уравнений. М.: Наука, 1978.

6. Wagner C. Tangential frequency filtering decompositions for symmetric matrices // Numer. Math. 1997. Vol. 78: Р. 143 — 163.

7. Wittum G. Filternde Zerlegungen Schnelle Löser für grosse Gleichungssysteme // Teubner Skripten zur Numerik. B. 1. Stuttgart: Teubner-Verlag, 1992.

Об авторах

69

А. А. Буздин — канд. физ.-мат. наук, доц., РГУ им. И. Канта. Е.А. Васильева — ассист., РГУ им. И. Канта.

К.С. Латышев — канд. физ.-мат. наук, проф., РГУ им. И. Канта.