ВУЗ:
Составители:
18
η
+=
+ ii
yqy
~
1
~
, где
η
– погрешность округления. Для погрешности
δ
y
i
=
i
i
yy −
~
получим уравнение
δ
y
i+1
=q
δ
y
i
+
η
(i=0, 1,…,
δ
y
0
=
η
). Из формулы
δ
y
i
=q
i
η
+
η
(q
1
-1)/(q-1) следует, что погрешность
δ
y
i
при
q>1 экспоненциально растет с ростом i.
Вернемся к методу прогонки и покажем, что при
1≤
i
α
погрешность
δ
y
i
не нарастает. В
самом деле, из
,
1
1
~
1
~
+
+
+
+=
i
i
i
i
yy
βα
y
i
=
α
i+1
y
i+1
+
β
i+1
следует
δ
y
i
=
α
i+1
δ
y
i+1
,
111 +++
≤≤
iiii
yyy
δδαδ
,
так как
.1
1
≤
+i
α
Если учесть, что в ходе вычислений возмущаются и коэффициенты
α
i+1,
β
i+1
, то можно
показать, что погрешность
δ
y
i
пропорциональна квадрату числа узлов N:
2
0
1
max Ny
i
Ni
εδ
≤
≤≤
, где
ε
0
–
погрешность округления. Отсюда видна связь между требуемой точностью
ε
решения задачи,
числом N уравнений и числом значащих цифр компьютера, поскольку
ε
0
N
2
.
ε
≈
1.1.3.3. Другие варианты метода прогонки
Рассмотренный выше метод прогонки (8) – (10), при котором определение y
i
производится
последовательно справа налево, называют правой прогонкой. Аналогично определяются формулы
левой прогонки:
,,1,2,...,2,1,
2
1
λξ
ξ
ξ
=−−=
−
=
+
←
N
iii
i
NNi
bc
a
(13)
,,1,2,...,2,1,
2
1
1
µη
ξ
η
η
=−−=
−
+
=
+
+
←
N
iii
iii
i
NNi
bc
fb
(14)
.
1
,1,...,1,0,
11
111
011
1
λξ
η
λ
µ
ηξ
−
+
=−=+=
++
+
→
yNiyy
iii
i
(15)
В самом деле, предполагая, что y
i+1
=
ξ
i+1
y
i
+
η
i+1
и исключая из (1) y
i+1
, получим -f
i
=a
i
y
i-
1
+(b
i
ξ
i+1
-c
i
)y
i
+b
i
η
i+1
или
1
1
1
1 +
+
−
+
−
+
+
−
=
iii
iii
i
iii
i
i
bc
bf
y
bc
a
y
ξ
η
ξ
. Сравнивая с формулой y
i
=
ξ
i
y
i-1
+
η
i
,
получим (13) и (14). Значение y
0
находим из условия y
0
=
λ
1
y
1
+
µ
1
и формулы y
0
=
ξ
1
y
1
+
η
1
. Из
неравенств
),1(
111 +++
−+≥−≥−
iiiiiiiii
babcbc
ξξξ
1111
11
λξλξ
−≥− следует, что условия
(11) гарантируют применимость формул левой прогонки и их вычислительную устойчивость, т.к.
1≤
i
ξ
(i=1, 2,…, N).
Комбинация левой и правой прогонок дает метод встречных прогонок. В этом методе в
области
10
0
+≤≤ ii по формулам (8), (9) вычисляются прогоночные коэффициенты
α
i
,
β
i
, а в
области
Nii ≤≤
0
по формулам (13), (14) находятся
ξ
i
и
η
i
. При i=i
0
производится сопряжение
решений в форме (10) и (15).
Из формул
,
111
0000
+++
+
=
iiii
yy
β
α
111
0000
+++
+
=
iiii
yy
η
ξ
находим
11
111
00
000
0
1
++
+++
−
+
=
ii
iii
i
y
ξα
η
α
β
. Эта
формула имеет смысл, т.к. хотя бы одна из величин
1
0
+i
ξ
или
1
0
+i
α
в силу (11) меньше
единицы, и, следовательно,
01
11
00
>−
++ ii
ξ
α
. Зная
0
i
y , можно по формуле (10) найти все y
i
при
i<i
0
, а по формуле (15) – значения y
i
при i>i
0
. Вычисления при i>i
0
и i<i
0
проводятся автономно
(имеет место распараллеливание вычислений). Метод встречных прогонок особенно удобен, если,
например, требуется найти y
i
лишь в одном узле i=i
0
.
18
~ ~ ~
y i +1 = q y i + η , где η – погрешность округления. Для погрешности δyi= y i − yi получим уравнение
δyi+1=qδyi+η (i=0, 1,…, δy0=η). Из формулы δyi=qiη+η(q1-1)/(q-1) следует, что погрешность δyi при
q>1 экспоненциально растет с ростом i.
Вернемся к методу прогонки и покажем, что при α i ≤ 1 погрешность δyi не нарастает. В
~ ~
самом деле, из y i = α i +1 y i +1 + β i +1 , yi=αi+1yi+1+βi+1 следует δyi=αi+1δyi+1, δyi ≤ α i +1 δyi +1 ≤ δyi +1 ,
так как α i +1 ≤ 1.
Если учесть, что в ходе вычислений возмущаются и коэффициенты αi+1, βi+1, то можно
показать, что погрешность δyi пропорциональна квадрату числа узлов N: max δyi ≤ ε 0 N 2 , где ε0 –
1≤i ≤ N
погрешность округления. Отсюда видна связь между требуемой точностью ε решения задачи,
числом N уравнений и числом значащих цифр компьютера, поскольку ε0N2 ≈ ε .
1.1.3.3. Другие варианты метода прогонки
Рассмотренный выше метод прогонки (8) – (10), при котором определение yi производится
последовательно справа налево, называют правой прогонкой. Аналогично определяются формулы
левой прогонки:
← ai
ξ = , i = N − 1, N − 2,...,2,1,ξ N = λ2 , (13)
ci − biξ i +1
← bη + f
η i = i i +1 i , i = N − 1, N − 2,...,2,1,η N = µ 2 , (14)
ci − biξ i +1
→ µ +λη
y i +1 = ξ i +1 yi + η i +1 , i = 0,1,..., N − 1, y0 = 1 1 1 . (15)
1 − ξ1λ1
В самом деле, предполагая, что yi+1=ξi+1yi+ηi+1 и исключая из (1) yi+1, получим -fi=aiyi-
ai f + biη i +1
1+(biξi+1-ci)yi+biηi+1 или yi = y i −1 + i . Сравнивая с формулой yi=ξiyi-1+ηi,
ci − biξ i +1 ci − biξ i +1
получим (13) и (14). Значение y0 находим из условия y0=λ1y1+µ1 и формулы y0=ξ1y1+η1. Из
неравенств ci − biξ i +1 ≥ ci − bi ξ i +1 ≥ ai + bi (1 − ξ i +1 ), 1 − ξ1λ1 ≥ 1 − ξ1 λ1 следует, что условия
(11) гарантируют применимость формул левой прогонки и их вычислительную устойчивость, т.к.
ξ i ≤ 1 (i=1, 2,…, N).
Комбинация левой и правой прогонок дает метод встречных прогонок. В этом методе в
области 0 ≤ i ≤ i0 + 1 по формулам (8), (9) вычисляются прогоночные коэффициенты αi, βi, а в
области i0 ≤ i ≤ N по формулам (13), (14) находятся ξi и ηi. При i=i0 производится сопряжение
решений в форме (10) и (15).
β i +1 + α i +1η i +1
Из формул yi0 = α i0 +1 yi0 +1 + β i0 +1 , yi0 +1 = ξ i0 +1 yi0 + η i0 +1 находим yi0 = 0 0 0
. Эта
1 − α i +1ξ i +1
0 0
формула имеет смысл, т.к. хотя бы одна из величин ξi 0 +1 или α i0 +1 в силу (11) меньше
единицы, и, следовательно, 1 − α i0 +1ξ i0 +1 > 0 . Зная yi0 , можно по формуле (10) найти все yi при
ii0. Вычисления при i>i0 и i 
Страницы
- « первая
- ‹ предыдущая
- …
- 16
- 17
- 18
- 19
- 20
- …
- следующая ›
- последняя »
