3 2 1 N 0

, здесь :.

По формуле рассчитаем:

, для различных значений k при 0 ≤ k ≤ N-1 получим:

;

;

.

Процесс вычисления сумм в квадратных скобках можно представить в виде направленного графа «бабочки»:

Для того чтобы вычислить x-катое нужно построить такую схему:

Х(0)=А+С; Х(1)=B+W^-1 D; X(2)=A-C; X(3)=B- W^-1 D.

ПРИЛОЖЕНИЕ 4.3