А. А. Самарский, А. В. Гулин

z i =
4iQj - i z i-2 +
+
i-
Теперь можно подставить сюда выражение для 
zH2,
затем —для 
з и т. д. В результате получим формулу, в которой z, выражается 
через 
Zj-h
I
г,- = QjtZj-t - f
^
Q/.М Ф *. 
1 = 1 , 2 , . . . , / — 1, /,
*=/-/+1
где
1
, 
1
 =
0
,
QiQi
-1 • • • 
Qi-i
н >
<
(14)
(15)
Строго доказать формулу (14) можно индукцией по числу / при 
каждом фиксированном 
I.
Нам потребуется формула (14) при 
l= j,
т. е.
где согласно
2/ — 
Qifi
о "К 2
Qi.f-k^k,
*=i
(15)
Ql.i-k =
1, 
А = /,
QiQi-i ■
• ■
9ь+
1,
/ = 1,2, . . .,п,
(
16
)
(17)
В частности, если (13) является уравнением с постоянными ко­
эффициентами, т. е. 
qj=q
для всех /, то из (16) получим
2/ =
Q'z0
+ 2
/ = 1,2, . . ., 
п.
(18)
1
Явную формулу (16) можно использовать для получения раз­
личных оценок решения 
z}
через начальные данные z„, заданные 
коэффициенты 
qs
и правые части ср,.
Л е м м а 1. 
Если для некоторого q ^ O выполнены неравенства
/ = 1 , 2 , . . . , « ,
(19)
то для решения уравнения
(13) 
справедливы оценки
| z / K ‘7/ l*ol + 2 9М |Ф*1. 
/ = 1, 2, . . . , п.
(20)
k = \
21

---

Д о к а з а т е л ь с т в о . Из (17) и (19) получаем, что 
\Q ij-h \< q ,~h,
£=0,1
Отсюда п из (16) следуют оценки (20).
З а м е ч а н и е . Оценки (20) неулучшаемы в том смысле, что для уравнения
(13) с постоянными коэффициентами и положительными 
го, /„ k = \ , 2, 
J,
неравенства (20) выполняются согласно (18) со знаком равенства.
5. Оценки погрешностей округления. 
Приведем примеры оценок 
погрешностей округления, возникающих в результате выполнения 
вычислительных алгоритмов. Нас будет интересовать в основном 
зависимость результирующей погрешности от числа арифметиче­
ских действий 
п
и от величины е= 2"', определяемой разрядностью 
ЭВМ.
П р и м е р 1. Вычисление произведения
П
2п
= П
У!
1
=1
п
вещественных чисел проводится по формуле
Ъ=У&-и
/= 1,2,. . . , л, 
z„=l. 
(21)
Предположим, что в результате округления вместо точного зна­
чения 
получено приближенное значение Zj_,. Тогда согласно 
(7) вместо 
yjZj-i
получим величину
^
i )
У
( 1 Т" 6 j ) ,
где |е ,- |^ е = 2 ~ ‘. Таким образом, вместо г, получаем
Zj= (1 
-Т е ;-)« /А --|,
т. е. приближенное значение 
zj
удовлетворяет рекуррентному соот­
ношению
21 = у&-1,
/= 1 , 2, 
г0= 1, 
(22)
где 
У] = Уз{
1 + е3). Результирующая погрешность равна
П 
П
2п — ~п =  П У! — Я 0 + е/) 
у
 и
 
/=1 
/=1
поэтому относительная погрешность есть
A Z I n = , _ - f [ ( i + e.).
2;i 
1=1
Для оценки относительной погрешности заметим, что 
I 1+ ei| ^ 1 + Щ /= 1 ,2 , 
е = 2 - ',
поэтому с точностью до величин второго порядка малости относи­
тельно е можно считать, что
-::ф 
пг = п2~‘.
(23)
22

---

При выводе оценки (23) предполагалось, что е = 2 - ', т. е. при 
перемножении не возникает чисел, меньших машинного нуля или 
больших машинной бесконечности. Однако может оказаться, что 
на каком-то этапе вычислений в качестве промежуточного резуль­
тата будет получен либо машинный нуль 
М0,
либо машинная бес­
конечность 
М„.
Поскольку оба указанных случая приводят к не­
верному окончательному результату, необходимо видоизменить вы­
числительный алгоритм. Оказывается, что здесь существенным яв­
ляется порядок действий.
Пусть, например, Л10=
2~р
и 
М „=
2Р при некотором 
р >
0. Пред­
положим, что надо перемножить пять чисел (/,=2р/2, 
у1= 2рП,
у 3=
23р/\
yi=2~p/1,
у5=2~3р/,\ Каждое из этих чисел и их произве­
дение 2р/4 принадлежат допустимому диапазону чисел 
(М0,М Х).
Однако произведение у
1
у2Уз=
2
31,/2>.М„, поэтому при указанном по­
рядке действий дальнейшее выполнение алгоритма становится не­
возможным. Если проводить вычисление в порядке 
уъу^УзУзУи
то 
получим у5У
4
=
2
~5р/4< М 0, следовательно, fl(t/5y4)= 0 и все произ­
ведение окажется равным нулю, т. е. получим неверный результат. 
В данном примере к верному результату приводит вычисление 
произведения в порядке
УьУгУ^кУг.