|
| |
|
Слаботочка Книги Показать, что для их нахождения достаточно OiNlogN) операций. § 5. Наилучшее равномерное приближение Если норма в линейном нормированном пространстве определяется не через скалярное произведение, то нахождение элемента наилучшего приближения существенно усложняется. Рассмотрим типичную задачу, встречающуюся, в частности, при составлении стандартных программ вычисления функций. Пусть jR - пространство ограниченных вещественных функций, определенных на отрезке [а, Ь] вещественной оси, с нормой 11/11= sup laj>] Ищется наилучшее приближение вида Qnix) = YUjxK Согласно теореме из §1 существует элемент наилучшего приближения, т.е. многочлен Qnix) такой, что Enif)=\\f-Q\\\\f-Qn\\ при любом многочлене Qnix) степени п. Такой многочлен Qnix) называют многочленом наилучшего равномерного приблимсени.я. Далее будут установлены необходимые и достаточные условия того, чтобы многочлен В ряде случаев удается еще уменьшить число операций. Один из таких случаев упоминался выше: дана вещественная функция f{t) = g{cost), известная в точках ti = 7г(2/ - l)/(2iV); требуется найти коэффициенты интерполяционного многоч.лена Aj cos jt. Другой случай: при четно.м N заданы значения функции N12-1 Aj sin 2т;jt .(=1 в точках t - l/N, О < I < N/2: нужно опреде.лить коэффициенты Aj. Задача 1. Найти коэффициенты Cj произведения двух многочленов /w-i \ /n-1 \ 2N-2 являлся многочленом наилучшего равномерного приближения для непре-рьюной функции. Теорема Балле-Пуссена. Пусть cyw,ecmeywm п + 2 точки хо < < Хп+1 отрезка [а, Ь] такие, что sign{f{xi) - Qnixi)) ЫУ = const, m. е. при переходе от точкой Xi к точке Xi\ величина f{x) - Qn{x) меняет знак. Тогда Enif) > Р = min fixi) - Qnixi) . (1) г=0,...,я+1 Доказательство. В случае = О утверждение теоремы очевидно. Пусть > 0. Предположим противное, т.е. что для многочлена наилучшего приближения Qnix) \\Q4-f\\ = Enif)<f. Имеем signQnix) - Qlix)) = sign((Q (-) - /Н) - (Qlix) - fix))). В точках Xi первое слагаемое превосходит по модулю второе, поэтому sign(Qnixi) - (3°(.T-j)j = sign((5 (.T.i) - Следовательно, многочлен - Q°(a;) степени п меняет знак п-Ы раз. Получили противоречие. Теорема Чебышева. Чтобы многочлен Qnix) был многочленом наилучшего равномерного приблиэ/сени.я непрерывной функции f{x), необходимо и достаточлю суш,ествовани.я на [а, Ь] по крайней .мере п + 2 точек xq < < Хп-\-\ таких, что f{xi) - Qnix,) = a{-iy II/ - QnW, где г = О,..., ri + 1, = 1 [или а = - одновременно дл.я всех г. Точки Хо,..., Хп+1, удовлетворяющие условиям теоремы, принято называть точками чебышевского альтернанса. Доказательство. Достаточность. Обозначим через L величину / - Qnll- Применяя (1), имеем L = fi Eif), но Я (/) / - QW = L вследствие определения величины Eif). Следовательно, En(f) = L а данный многочлен является многочленом наилучшего равномерного приближения. Необходимость. Пусть данный многочлен Qn{x) является многочленом наилучшего равномерного приближения. Обозначим через yi нижнюю грань точек х G [а, Ь], в которых \f(x) - Qn{x)\ = L; из определения L следует существование такой точки. Вследствие непрерывности fix) - Qnix) имеем \f{yi) - Qn{yi)\ = L. Для определенности далее рассматриваем случай, когда fiyi)-Qn{yi) = +L. Обозначим через у2 нижнюю грань всех точек х G [уг, Ь], в которых /(ж) - Qn{x) = -L, последовательно через Ук+1 обозначим нижнюю грань точек х 6 (у, Ь], в которых f{x) - Qn{x) = {-l)L,... Вследствие непрерывности f{x) - Qn{x) при всех к имеем f{yk+i) - QniVk+i) = Продолжаем этот процесс до значения = Ь или ут такого, что /(х) - Qn(x)\ < L при ?/, < ж Ь. Если т > п + 2, то утверждение теоремы выполнено. Предположим, что оказалось т < п + 2. Вследствие непрерывности f{x) - Qn{x), при любом к {1<кт) можно указать точку Zk-i такую, что \f{x) - Qa{x)\ < L при ггд.--1 ж < УА-; положим zq = а, z, = b. Согласно проведенным выгпе построениям, на отрезках [гг 1, z,], i = l,...,m, имеются точки, в частности точки (/./, где f{x) - Qn{x) = (-1)~L, и нет точек, где /(ж) - Qnix) = (-1)*L. Положим тп- 1 v{x) - JJ (zj - ж), Qfix) = Qnix) + dvix), d>Q и рассмотрим поведение разности fix) - Qiix) = fix) - Qnix) - dv{;x) на отрезках z]. Для примера обратимся к отрезку [zq, zi]. На [zo, zi) имеем > О, поэтому fix)-Qi,{:x)L-dvix) <L. Кроме того, на этом отрезке выполняется неравенство f(x) - Qnix) > -L; поэтому при достаточно малых d, например при min /(ж) - Qnix) + L\ . / . 10, zi] d < di =---- на [zq, zi) имеем fix) - Qnix) > -L. В то же время \fizi)~Qiizi)\ = \fizi)~Qnizi)\<L. Таким образом, \fix) - Qnix)\ < L на этом отрезке при достаточно малом d. После проведения аналогичных рассуждений относительно остальньгх отрезков [zi-i, Zi] мы сможем указать малое do такое, что на всех отрезках выполняется неравенство /(ж)-(5*(ж) < L. Мы получили протигоре-чие с предположением, что Q (ж)-многочлен наилучшего приближения, а т < п + 2. Теорема доказана. Теорема единственности. Многочлен наилучшего равномерного приближения непрерывной функции единствен. Доказательство. Предположим, что существуют два многочлена степени п наилучшего равномерного приближения: Qiix) ф Qlix), II/ - QiW = II/ - QlW = Enif). 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 |