|
| |
|
Слаботочка Книги § 2. Наилучшее приближение в гильбертовом пространстве 169 Поскольку II/ - 5Р О, то из равенства /-# = (/, /) - ЁК/, следует, в частности, известное неравенство Бесселя (/, /) Ек/, 9i)?- Если исходные элементы не образуют ортонормированной системы, то, вообще говоря, их можно ортогонализовать при помощи рассматривавшегося в гл. 3 алгоритма ортогонализации. Однако применение этого алгоритма довольно часто приводит к неудовлетворительным результатам. Например, при построении на отрезке [-1, 1] ортонормированной с весом р[х) > О системы функций из указанной выше систеьи.1 функ1щй хР будут получены некоторые ортогональные многочлены Pjijx), сумма модулей коэффициентов у которых растет не медленнее чем (л/2-(- 1) п , где а определяется через р{х). Если в дальнейшем значения многочле- нов вычисляются по явной формуле Pj{x) = EA;j3;, то из-за большой А;=0 величины суммы модулей коэффициентов будет большая погрешность в значениях самих многочленов. Для устойчивого вычисления значений многочленов нужно применить какой-то иной алгоритм, например вычислять их по рекуррентным формулам или по явным формулам типа Тп(а;) = cos(/i arccos ж) в случае многочленов Чебышева. Некоторые более детальные сведения но этому вопросу будут приведены в § 8. Пусть нам требуется приблизить функцию двух переменных f{x,y) в некоторой области G на плоскости {х, у). Явный вид ортогональных функций известен только для простейших областей. Можно применить следуюпщй прием. Возьмем некоторую область Г2 G G, для которой известна ортогональная система функций, и продолжим / в области Г2\С Далее будем приближать / в области G с помощью этой системы. Такой прием иногда неэффективен, поскольку не удается легко построить достаточно гладкое продолжение функции / в области U\G, а при недостаточно гладком продолженшг приближение будет плохим. Следствием как этого обстоятельства, так и того, что приближение шцется в большей области, часто является неоправданное увеличение значения п, нужного для достижения заданной точности. Другой возможный прием сведения к известной ортогональной системе функций состоит в следующем. Возьмем некоторую область Q с известной ортогональной системой ipi{C, г]),..., niCi V)- Пусть отображение X = х{С, п), У = vie, п) переводит область Г2 в G; С = С,{х, у), V = vix, у) - обратное отображение. Будем приближать функцию /(а;(С, т]), у{, v)) области fi линейными комбинациями су5((ж, у), г]{х, у)). b - а При приближении функций большого числа переменных не удается указать методов, пригодных во всех случаях. В каждой конкретной ситуации надо учитывать специфику задачи (вид функции, геометрию области и т.п.). Рассмотрим для иллюстрации задачу другого рода, при решении которой используются проводимые выше построения. Пусть требуется построить интерполяционный многочлен степени Л* -1 с узлами интерполяции х,...,х. Пусть эти узлы являются нулями Qn{x) степени N из ортонормированной системы многочленов {Qnix)}, соответствуюш;ей весу р{х). Например, можно строить интерполяционные многочлены по нулям многочленов Чебышева, о которых шла речь в гл. 2. Будем отыскивать интерполяционный многочлен в виде линейной комбинации Рлг 1(.г-) = YaQjix). При m, п < N многочлен Qmix)Qn{x) имеет степень не выше 2N - 2. Поэтому квадратура Гаусса с N узлами точна для этого многочлена: YDQrn{xf)Qn(x:i) = / QMQn{x)p{x) dx с- (7) Таким образом, векторы Q = {QmWi ),, Qm{x)} при m< N образуют ортонормированную систему относрггельно скалярного произведения (У, Z) = у,, (8) и вектор f = {f{x),..., ,1{х)У может быть разложен по этой системе векторов: где dj = (f, Qj). Многочлен Pr,i{x) = JdjQjix) -{9) будет искомым. Таким образом, построение интерполяционного многочлена с узлами интерполяции, соответствуюш,ими корням ортогонального многочлена, сводится к вычислению коэффициентов разложения функцш! dj по системе ортогональных многочленов. После этого искомый интерполяционный многочлен вычисляется по формуле (9). Этот алгоритм будет более устойчив по отношению к погрешностям округления по сравнению с непосредственным построением интерполяционного многочлена Лагранжа. § 3. Тригонометрическая интерполяция. Дискретное преобразование Фурье Дискретное преобразование Фурье применяется при решении многих прикладных задач. К ним относятся тригонометрическая интерполяция, вычисление свертки функций, распознавание образов и многие другие. Дискретное преобразование Фурье стало особенно эффективным методом решения прикладных задач после создания быстрого преобразования Фурье (см. § 4). Пусть f{x)-периодическая функция с периодом 1 - разложена в ряд Фурье /()= Y o,cexp{27riqx}, (1) 9=-оо причем оо q=~oo Здесь i - мнимая единица. Рассмотрим значения этой функции на сетке из точек xi = l/N, где I, N целые, N фиксировано, и обозначим f{xi) = fi. Если §2 ~ Qi = kN, где к целое, то q2Xi - qiXi = kNxi = kl, где kl целое. Следовательно, exp{27riQia;} = exp{27riQ22-} (3) в узлах сетки. Поэтому если функция /(ж) рассматривается лишь в узлах сетки XI, то в соотношении (1) можно привести подобные члены h = ЕАехр{2этдж(}, (4) л = Е <1+N- (5) 5= -оо Лемма. При Aq, определяемых (5), соотношение (4) остлется в силе, если пределы суммирования [О, Л - 1] заменить на [гп, N~\-\-7п\, где т - любое целое. Доказательство. В самом деле, если q = q + kN, то оо m=-оо Принимая к + т за новую переменную суммирования т, получим Aq< = Е q+mN ~ Aq. 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 |