|
F p = C w p P + q P ,
(17)
где векторы
р Р , qP
подлежат определению. Подставляя (17) в
(9), получим
c < V ' + qt
,<*) __ £<*-1)
Ak-1)
,
(k-i) ,
Pc-
2*-l + ?;_aA-l +
'(*-1) //-(*-1) _(*—
!)
I
l
Я -1 1
.
( 6 - l K
/ - 1 Я - 1 J
( « - И
I
(
+ L
(C
Pi
+qi
) + Б
Pc+2k-
1 + 9,
JA-1)
„*+!•
Отсюда, учитывая, что
Cw =
(C1*- ' 1) 2—
2E,
придем к уравнению
<С(А-1))3 (pf >
pi*'1’)
'*) _о„(И
Цс
= Д*-1)
_ l _
I
+ Pi-2*-l + ^/+2fe- l +
(*—
i)
, /-.(A-l) c №-l)
,
<*—0
,
Ak-X)\
+
L
\Pi
—
2
^ l +
Pi+2k-i + qi )■
Выберем теперь вектор
qP
таким, чтобы выполнялось соотно
шение
^ = 2 р ? » + « й 2 .1 + о
(18)
Тогда предыдущее уравнение после умножения на
мет вид
С 1
-1)с(А-1) _ П(*-Ч
■Jf.
*
— Р,-аА-1 +
Pi+^-l
+
Qi
П р
И .
(19)
где
=р.(М-
Pi (h~ l ) .
Таким образом, вычисление векторов
F p
можно заменить нахож
дением векторов
p f \ q f ’
из системы уравнений (17) — (19). Сначала,
обращая матрицу
C(k' l),
находим вектор
затем вычисляем
рр —
—
Р?~"
+
st~1]
и затем по формуле (18) вычисляем
qp.
Правую часть
Ff~l)
уравнения (7) надо заменить согласно (17) выражением
_№-1) ! _(*—
и
1 L
-- ^
^4
“Г
ЧС
Тогда придем к уравнению
ь
г,
—
7,-
+
У
L_ 2u -i
+
y iV2k - u
(
20
)
гд
е t f — ус— р(к 1).
Из этого уравнения, обращая матрицу С(А 11,
находим / f -0 и затем вычисляем
y i = pp'1)~ t f ~ 1]■
423
4.
Формулировка и обсуждение алгоритма. Сформулируем бо
лее детально алгоритм метода редукции.
Вычисления ведутся в цикле по индексу
k.
Сначала осуществля
ется прямой ход, т. е. для
k = \,
2,
т
—1 решаются уравнения
£ (ft-l) ч
I k-D
Pi-
2*-1 +
Pi+2k~l
,№-i)
(21)
и находятся векторы
РТ
=
pf~l\ + s r i),
J k )
,
Ik-1)
,
Ik-
1)
где i = 2 \ 2 -2 \ 3-2 \
2т—2к.
Вычисления ведутся, начиная
k = l ,
причем при
k=
1 задаются начальные значения
„ (
0
)
= О,
До)
■■Ft,
* = 1 , 2 .......
N — \.
с
Решение систем (21) сводится, как это было показано в п.
2,
к решению более простых систем уравнений
где
Ck-i,i^l,i
—
V l-i,it
»' = 2 \ 2 -2\
1 =
1 ,2 ....... 2й ,
. ,
2т
—2\
_ _(*—
1)
I „(*-1)
I „(*-1)
,i —
Pi-2k-i
i -
рi+2k-i
+ <7<
,
(
22
)
V -
j k - D
■>
[
Системы (22) решаются при фиксированном
I
для каждого
i = 2 \ 2-2\ . . . , 2т—2\ Поскольку матрица
Ск- 1ш
1
не зависит от
i,
вычисления целесообразно организовать так, чтобы матрица
Ск- i,t
обращалась один раз.
Подсчитаем число действий, необходимых для решения всех си
стем вида (22). Предположим, что для решения системы (22) с
фиксированными
k, I, i
гпебуется
q
арифметических действий. Тог
да при фиксированных
k, I
для решения систем (22) с
i =
2 \ 2 -2 \ .. .
2 ^ _
2к
. . . , 2™—
2к
требуется----------
q = (2
т~к—1
)q
арифметических дей-
2k
ствий. При фиксированном
k
и для
1=
1, 2, .. ., 2s-1, i = 2 \ 2-2*,
. . . , 2m—2 \ требуется
2к~1(2т~к
—
\ ) q = { 2 m~'
—
2h~l)q
действий. На
конец, для всех
k =
1, 2, . . . ,
т
—1 необходимо выполнить
т
- 1
(
2
- 1 _ 2*-1) = (1 +
(т -
2)
2т~1) q
k=i
арифметических действий. Самое существенное здесь то, что при
больших
N
число действий является величиной
О (qN
log2 Лг).
После того как все векторы р)4', <7;е) найдены, осуществляется
обратный ход метода редукции, т. е. начиная с
k = m
решаются
424
у р а в н е н и я
(23)
Ык-V f'k-1)
_ №-i) I
_i_
fj
.
Ь
f i
—
Qi
-+-
У (_21г-
1
i
t/ i+ ik -i
и вычисляются искомые векторы
, , _n(*-o I
£/£ — P i
T ‘ i
’
где fe
= m,
m
—
1,
... .
1,
t' =
2*-‘, 3-2*-1, . . . , М -2*-', M
=
2m.
Система (23) при фиксированных
i, k
решается, как и ранее,
путем последовательного решения систем уравнений
C k — i ' i W i ' i
—
W i - i i ,
I
—
1
,
2
.......
2
,
I = 24- 1, 3-2*-1,
5-2к~\
2т—2к~\
(24)
где
wllU = q
{
! 0 +
y ^ k- i
+
yi+2k-u
4 г)-
Решение
системы
(23) также требует
О (qN
log2
N)
действий.
Рассмотрим применение метода редукции к решению разност
ного уравнения Пуассона (4), (5) из § 5. Предположим, что сетка
содержит
N
1 = 2"1 точек по направлению
х х
и
N2
точек — по
х2.
Со
гласно
(9)
из § 5, это разностное уравнение можно записать в век
торном виде (1), (2), где
N = Nl
и
С = 2Е2
—
h\A2 —
трехдиагональ
ная матрица порядка
N2
—1. Поэтому системы вида (22), (24) ре
шаются методом прогонки, что требует
q = 0 ( N z)
действий. Таким
-образом, решение разностного уравнения Пуассона осуществляется
методом редукции за число действий
0 ( N 2N l \og2N i).
На квадрат
ной сетке, когда
N t = N2 = N,
число действий является величиной
О {Nz \og2 N ) ,
т. е. имеет тот же порядок, что и в методе быстрого
дискретного преобразования Фурье. В отличие от последнего, ме
тод редукции не требует знания собственных функций, что позво
ляет применять его и в более общих случаях, например в случае
краевых условий третьего рода.
Метод редукции выгодно отличается от метода матричной про
гонки не только числом действий, но и требуемой памятью ЭВМ.
В тс же время следует еще раз подчеркнуть, что метод редукции
можно применять только для решения относительно простых си
стем уравнений, а именно систем, которые можно записать в виде
(1) с постоянной матрицей
С.
Например, разностные задачи для
уравнения
£
(ki (х,
0) ^
^
( h (х,
(М
У)
можно решать методом редукции только в том случае, если коэф
фициенты
k u k2
не зависят от
х.
СПИСОК ЛИТЕРАТУРЫ
1. Б а б е н к о К- И. Основы численного анализа.— М.: Наука, 1986.
2. Б а х в а л о в Н. С. Численные методы.— М.: Наука, 1975.
3. Б а х в а л о в Н. С., Ж и д к о в Н. П., К о б е л ь к о в Г. М. Численные мето
ды.— М.: Наука, 1987.
4. Б е р е з и н И. С., Ж и д к о в Н. П. Методы вычислений — Ч. I,— М.: Наука,
1966. То же.— Ч. 2.— Физматгиз, 1962.
5. Б о б к о в В. В., Г о р о д е ц к и й Л. М. Избранные численные методы решения
на ЭВМ инженерных и научных задач.— Минск: Изд-во «Университетское»,
1985.
6. В о е в о д и н В. В. Вычислительные основы линейной алгебры.— М.: Наука,
Do'stlaringiz bilan baham: |
