Составители:
Рубрика:
Естественно, подобные разложения в САВ заканчиваются ко-
нечным числом членов, так что фактически приходится работать с
многочленами от α. Отличие состоит в том, что необходимо преду-
смотреть алгоритмы "отбрасывания высших степеней". Например,
при обработке произведения
10
X
i=0
a
i
α
i
·
10
X
i=0
b
i
α
i
естественно сохранить лишь степени не выше 10 (хотя получаются
также степени 11, . . . , 20).
Можно ввести специальные алгоритмы вычисления коэффици-
ентов результирующего разложения. Пусть, например, имеются раз-
ложения
A =
X
i
a
i
α
i
, B =
X
i
b
i
α
i
.
Требуется найти разложения для C
C =
X
i
c
i
α
i
,
где C получено из A и B одной из операций ±, ∗/. Нетрудно полу-
чить формулы
C = A ±B c
i
= a
i
± b
i
C = A ·B c
i
=
i
X
j=0
a
j
b
i−j
C = A/B c
i
=
a
i
−
i−1
P
j=0
c
j
b
i−j
b
0
Последнее равенство написано лишь для случая b
0
6= 0, в других
случаях формула другая.
Метод (восходящий к Норману) состоит в том, что коэффициент
c
i
вычисляется лишь в момент обращения к нему. Это значительно
экономит память. Если запоминать уже проведённые вычисления
c
0
, . . . , c
i−1
, то вычисление c
i
потребует лишь O(i
2
) операций (в слу-
чае деления). Заметим, что если такое запоминание не делать, то
число операций будет расти по показательному закону.
66
Страницы
- « первая
- ‹ предыдущая
- …
- 63
- 64
- 65
- 66
- 67
- …
- следующая ›
- последняя »
