|
| |
|
Слаботочка Книги 2 j - 1 зна >ajCos 7i; по узлам ij = .1=0 образующим равномерную сетку. 1ци тригонометрического многочлена Uj cos(jt) по узлам tj = тг ,7=0 § 4. Быстрое преобразование Фурье Осугцествление прямого и обратного дискретных преобразований Фурье (/о,..., /л-i) < (Ао,..., Ani) является составной частью решения многих задач. Непосредственное осуществление этих преобра:ований но формулам (3.4), (3.7) требует 0{№) арифметических операций. Рассмотрим вопрос о возможности сокращения этого числа. Для определенности речь пойдет о вычислении коэффициентов Ад по заданным значениям функции. Идея построения алгоритмов быстрого преобразования Фурье опирается на то, что при составном N в слагаемых правой части (3.7) можно выделить группы, которые входят в выражения различных коэффициентов Ад. Вычистшя каждую группу только один раз, можно значительно сократить число операций. Рассмотрим сначала случай N = piP2\ Pi, Р2 ф 1- Представим -j, лежащие в пределах О q, j < N, в виде q = qi + Piq2, j = .72 +P2Ji, где О Qi) ji < Pi, 42, J2 < P2- Имеем цепочку соотношений Ад = Л(ь q2) = Е /i -p{-2i = j=0 1 Y Г .(gl +Plg2)(J2 +P2Jl)l jl=0J2=0 Из равенства (gi +piq2)iJ2 +P2:ii) . , qj2 , jm Следовательно, задача наилучшего приближения /(ж) в норме, соответствующей скалярному произведению (/, g)i, эквивалентна задаче приближения /(cos) в норме, соответствующей скалярному произведению (f,g)2 = / f(cose)д(cose)М. Точно так же существует соответствие ./о в случае задач интерполяции и наилучшего приближения в равномерной метрике. Задача интерполирования функции многочленом по узлам x-i = cosi-K- I -нулям многочлена Чебышева Т ,(.т) - после такой замены сводится к задаче интерполирования функции /(cosб) при помо- и предыдущего соотношения получим А{ди Ч2) = -Т A\qi, i2)exp \ -2ш \ , (?ь J2) = - Е /j2+P-2.n ехр < -27ri- 71 gi 1 Pi J Непосредственное вычисление всех Aqi, J2) требует О (ррг) арифметических операций, а последующее вычисление A{qi, 92)-еще О [pip операций. Поэтому при pi, Р2 = 0{\/N) общее число операций составит 0(iV/). Точно так же при N=p\...pr строится алгоритм вычисления совокупности значений Л, для которого общее число операций не превосходит CN{pi + -\-рг), здесь С - постоянная, не зависящая от N. Выпишем соответствующие расчетные формулы для наиболее употребительного случая р\ = = Pj. = 2. Представим числа q, j в виде q = Qk2-\ j = J2 jV+l-m2 -, k=l m=l где Qk:ir+i-m = 0, 1. Величину qj2 представим в виде m=l m=l \fc=:l r /r-m+1 m=l \ fc=l :ir+l-m >+l-m + S, где .s -целое, равное сумме всех слагаемых вида qkjr+i-m , У которых к+т-г - 2 0. Очевидно, что ехр-27г1 = exp-27ri - , поэтому Л(5Ь--,г) = Л = ]ЕЛ- р1-27г1и = Е-4Е/>-.2У.-.+...+2-лехр -2.iX:( Е 42-.-]. 3г=0 ji=0 I m=l fc=l ) §4. Быстрое преобразование Фурье 177 После перегруппировки слагаемых имеем j,.=0 I fc=l J E exp(-27ri,Vi2--E5/2-A j,. i=0 I fc=l J 2 E exp{-27riji2 qi}fj,.+2j,. ,+-+2r-4i Это соотношение можно записать в виде последовательности рекуррентных соотношений Лдь , Qm; im+l, , ir) = = i Е ехр(-27г;д 2- Е2 4 ~(Ь--.,9п.-1;;п,.-., 3,п=0 I J rn = 1,..., г, °Н.7Ь , л) = / .+2j,-i+-+2-lji, Переход от каждой совокупности A ~ к совокупности А *) требует 0{N) арифметических и логических операций; всего таких шагов г, поэтому общее число операций имеет порядок 0(Nr) = 0(iV log2 Л)- Вычисление при помощи совокупностей А дает меньшее накопление вычислительной погрешности по сравнению с формулами (3.7). Определенные удобства имеются также при вычислении экспонент, входящих в расчетные формулы. При вычислении величин А * используются значения ехр{-27rij2~ }, J = О, 1,..., 2 - 1. В частности, при m = 1 величина ехр{-Trij) принимает значения -Ы или -1. Для вычисления значений ,4( +) потребуются еще значения ехр{-27ri 72~( ~)} при нечетных j, удов.летворяюш;их неравенству О j < 2 +. Их можно вычислить через уже вычисленные до этого величины, в частности, при помощи соотношений {т 2) exp-27ri i2- ] + exp(-27ri 2- j exp{-27rii2-f +i)} =-1-2-J-n-2-£ 2cos(7r2- ) где, в свою очередь, cos(7r2- ) = yi(l-bcos(7r2i- )) при m 1. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 [57] 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 |