Численные методы. Корнюшин П.Н. - 7 стр.

UptoLike

ВУЗ: 

ДВФУ | Владивосток

Составители: 

Рубрика: 

7
3-й способ. Перемешаем эти числа, полагая, q
1
=10
-3p/4
, q
2
=10
p/2
, q
3
=10
3p/4
, q
4
=10
-p/2
, q
5
=10
p/4
.
Тогда последовательно найдем: S
2
=q
1
q
2
=10
-p/4
, S
3
=S
2
q
3
=10
p/2
, S
4
=S
3
q
4
=10
0
, S
5
=S
4
q
5
=10
p/4
, т.е. в
процессе вычислений не появляются числа, большие 10
p/2
и меньшие 10
-p/4
. Такой алгоритм
является безавостным.
При каждом акте вычислений появляются погрешности округления. В зависимости от
алгоритма эти погрешности округления могут либо нарастать, либо затухать. Если в процессе
вычислений погрешности округления неограниченно нарастают, то такой алгоритм называют
неустойчивым (вычислительно неустойчивым). Если же погрешности округления не
накапливаются, то алгоритм называется устойчивым.
Пример 2. Пусть требуется найти y
i
(0<i
≤
i
0
) по формуле y
i+1
=y
i
+d (i ≥ 0) при заданных y
0
,
d. Предположим, что при вычислении y
i
внесена погрешность (например, погрешность
округления), имеющая величину δ
i
, т.е. вместо точного значения y
i
получено приближенное
значение
ii
i
yy
δ
+=
~
. Тогда вместо точного значения y
i+1
получим приближенное значение
iiii
i
ydyy
δδ
+=++=
+
+
1
1
~
)(
. Таким образом, погрешность, допущенная на любом
промежуточном шаге, не увеличивается в процессе вычислений. Алгоритм устойчив.
Пример 3. Рассмотрим уравнение y
i+1
=qy
i
(i≥0, y
0
и q заданы). Пусть, как и в примере 2,
вместо y
i
получено значение
ii
i
yy
δ
+=
~
. Тогда вместо y
i+1
получим приближенное значение
.)(
1
1
~
iiii
i
qyyqy
δδ
+=+=
+
+
Таким образом, погрешность δ
i+1
=
1
1
~
+
+
−
i
i
yy , возникающая при
вычислении y
i+1
, связана с погрешностью δ
i
уравнением δ
i+1
=qδ
i
, i=0,1,2,…. Следовательно, если
1>q , то в процессе вычислений абсолютное значение погрешности будет возрастать (алгоритм
неустойчив). Если же
1≤q , то погрешность не возрастает, т.е. алгоритм устойчив.
Неустойчивость обычно связывают со свойством экспоненциального нарастания ошибки
округления. Если же погрешность округления нарастает по степенному закону при переходе от
одной операции к другой («от шага к шагу»), то алгоритм считают условно устойчивым
(устойчивым при некоторых ограничениях на объем вычислений и требуемую точность). Процесс
вычислений можно трактовать так: при переходе от шага к шагу происходит искажение (за счет
погрешностей округления) последних значащих цифр (от последних значащих цифр справа налево
движется «волна погрешности округления»). Нам нужно обычно сохранить верными несколько
первых значащих цифр (4-5 знаков), и поэтому вычисления должны быть закончены до того, как
до них дойдет «волна погрешности округления». Если погрешность округления ε
0
нарастает от
шага к шагу по экспоненциальному закону, то это приводит, как правило, к авосту на
промежуточном этапе вычислений, если (как в примере 3)
∞
≥ Mq
i
0
ε
.
Если М
∞
=10
р
, ε
0
=10
-k
0
, то авост наступает при i
0
>(p+k
0
)/lg q . Иначе обстоит дело при
степенном росте погрешности округления. Пусть
≈
i
y
δ
i
n
ε
0
(n≥1); тогда авост наступит при
∞
≥ Mi
n
00
ε
, т.е. при i
0
n
M
/1
0
1
≥
∞
ε
=10
(p+k
0
)/n
. Ясно, что при n=1 авоста не будет в силу
очевидного ограничения i<М
∞
=10
р
. Неравенство
εδ
≤
i
y , где ε=10
-k
– заданная точность,
справедливо при i
0
/)(
/1
0
0
10 i
nkk
n
==
≤
−
ε
ε
. Если заданы ε и ε
0
, то это неравенство означает
ограничение на число уравнений i≤i
0
. Так, при k
0
=12, k=6 имеем i≤10
6/n
, так что i≤10
3
при n=2.
Ясно, что можно указать такое большое n, что допустимое число уравнений i
0
очень мало. Однако
на практике обычно встречаются случаи небольшого n.
При решении любой задачи необходимо знать какие-то входные (исходные) данные –
начальные, граничные значения искомой функции, коэффициенты или правую часть уравнения и
др. Для каждой задачи ставятся одни и те же вопросы: существует ли решение задачи, является ли
оно единственным и как зависит решение от входных данных? Возможны два случая. В первом 
                                                                    7


       3-й способ. Перемешаем эти числа, полагая, q1=10-3p/4, q2=10p/2, q3=103p/4, q4=10-p/2, q5=10p/4.
Тогда последовательно найдем: S2=q1q2=10-p/4, S3=S2q3=10p/2, S4=S3q4=100, S5=S4q5=10p/4, т.е. в
процессе вычислений не появляются числа, большие 10p/2 и меньшие 10-p/4. Такой алгоритм
является безавостным.
       При каждом акте вычислений появляются погрешности округления. В зависимости от
алгоритма эти погрешности округления могут либо нарастать, либо затухать. Если в процессе
вычислений погрешности округления неограниченно нарастают, то такой алгоритм называют
неустойчивым (вычислительно неустойчивым). Если же погрешности округления не
накапливаются, то алгоритм называется устойчивым.
       Пример 2. Пусть требуется найти yi (0 1 , то в процессе вычислений абсолютное значение погрешности будет возрастать (алгоритм
неустойчив). Если же                    q ≤ 1 , то погрешность не возрастает, т.е. алгоритм устойчив.
Неустойчивость обычно связывают со свойством экспоненциального нарастания ошибки
округления. Если же погрешность округления нарастает по степенному закону при переходе от
одной операции к другой («от шага к шагу»), то алгоритм считают условно устойчивым
(устойчивым при некоторых ограничениях на объем вычислений и требуемую точность). Процесс
вычислений можно трактовать так: при переходе от шага к шагу происходит искажение (за счет
погрешностей округления) последних значащих цифр (от последних значащих цифр справа налево
движется «волна погрешности округления»). Нам нужно обычно сохранить верными несколько
первых значащих цифр (4-5 знаков), и поэтому вычисления должны быть закончены до того, как
до них дойдет «волна погрешности округления». Если погрешность округления ε0 нарастает от
шага к шагу по экспоненциальному закону, то это приводит, как правило, к авосту на
                                                                                i
промежуточном этапе вычислений, если (как в примере 3) q ε 0 ≥ M ∞ .
         Если М∞=10р, ε0=10-k 0 , то авост наступает при i0>(p+k0)/lg q . Иначе обстоит дело при
степенном росте погрешности округления. Пусть δy i ≈ inε0 (n≥1); тогда авост наступит при
                                                     1/ n
                             1   
i ε 0 ≥ M ∞ , т.е. при i0 ≥  M ∞ 
 n
                                                            =10(p+k 0 )/n. Ясно, что при n=1 авоста не будет в силу
 0                          ε    
                             0   
очевидного ограничения i<М∞=10р. Неравенство δy i ≤ ε , где ε=10-k – заданная точность,
                                       1/ n
                     ε           
справедливо при i ≤                       = 10 ( k 0 − k ) / n = i 0 . Если заданы ε и ε0, то это неравенство означает
                     ε0           
ограничение на число уравнений i≤i0. Так, при k0=12, k=6 имеем i≤106/n, так что i≤103 при n=2.
Ясно, что можно указать такое большое n, что допустимое число уравнений i0 очень мало. Однако
на практике обычно встречаются случаи небольшого n.
       При решении любой задачи необходимо знать какие-то входные (исходные) данные –
начальные, граничные значения искомой функции, коэффициенты или правую часть уравнения и
др. Для каждой задачи ставятся одни и те же вопросы: существует ли решение задачи, является ли
оно единственным и как зависит решение от входных данных? Возможны два случая. В первом

Страницы