|
| |
|
Слаботочка Книги § 7. о форме записи многочлена 187 многих точках. В этом случае часто полезно вместо непосредственного вычисления значений функции воспользоваться интерполяцией ее значений по таблице или приблизить функцию многочленом. Иногда для этой цели используют многочлены наилучшего приближения в норме L2 или наилучшего равномерного приближения. Конечно, в каждом конкретном случае полезно посмотреть, оправдают ли себя затраты по построению приближающего многочлена. § 7. О форме записи многочлена Одна из стандартных программ наилучпюго равнолюрного приближения была отлал<;ена в случае приближения функций многочленами невысокой степени и включена в пакет стандартных программ. Однако при практическом использовании программы для приближения функции многочленами высокой степени в ряде случаев оказывалось, что программа выдает приближение к функции, не обеспечивающее ожидаемой точности, или итерационный процесс не сходился, продолжаясь неограниченно долго, так что приходилось прекращать вычисления. После практического и теоретического анализа возникшей ситуации удалось установить притину происходящего. Для определенности будем говорить о приближении функции па отрезке [-1, 1]. Было установлено, что в случае недостаточно гладкой функции коэффициенты многочлена, приближающего ее с высокой точностью, обязательно будут очень большими. За исключением редко встречающегося случая, когда эти коэффициенты записываются в ЭВМ без округлений, в этот многочлен вносится погрешность, и он плохо приближает рассматриваемую функцию. Если эти коэффициенты и записаны в машине без округлений, то все равно значения многочлена при а;, близком к 1, будут находиться с большой вычислительной погрешностью. Сформулируем соответствующие утверждения более строго. Предположим, что существует последовательность многочленов п{т) удовлетворяющих условию /(а;)-Р-(жЖ2- на [-1,1] (1) (Р (я;)-не обязательно многочлены наилучшего равномерного приближения); предположим также, что коэффициенты этих многочленов растут не очень сильно: n(m) = Ё 2 90. (2) Обозначим через dp открытую область, ограниченную дугами, из любой точки которых отрезок [-1, 1] врзден под углом ip. Известна Теорема. Пусть последовательность многочленов Р {х) удовлетворяет соотношениям (1), (2). Тогда функция f{x) может быть аналитически продолжена в открытую область комплексного переменного G, ip = n{2q + l)l{2q + 2). Примечание. Если вместо условия (1) имеем условие - Р {х)\ 1/т, то можно показать, что max \fHx)\ < оо при любом > 0. Какие практические следствия вытекают из этой теоремы? Если число а записывается в системе с плавающей запятой с t двоичными разрядами, то его погрешность может оказаться больше 1012 * ; в худшем случае, когда погрешности коэффициентов а одного знака, погрешность значения п{т) являющаяся следствием этих погрешностей, может превзойти величину п{т) \ YK\W-=lrn2--\ 3=0 ) Чтобы качественно представить характер влияния этой погрешности, будем считать, что число т, входящее в условия (1), (2), и число t велики. Пусть функция /(z) аналитична в некоторой области Gj, и не аналитична ни в какой области Gp при ip < р. Пусть qo выбирается из соотношения до = \2ipQ - 7г]/2(7г - ipu)\. Возьмем произвольное q < qo- Если предположить, что для всех т выполняется неравенство Z 2 , то, согласно выше сформулированной теореме, /(г) будет аналитична в соответствующей области G при у? < jq и получается противоречие с предположением о свойствах функции /(z). Таким образом, будут встречаться сколь угодно большие т, для jcoto-рых > 2 . Следовательно, при неблагоприятном стеченрш обстоятельств погрешность от округления значений может оказаться больше, чем 2 2*~. В то же время нельзя рассчитывать на оценку погрешности, лучшую, чем (1). Для суммарной погрешности, получающейся от замены /(ж) на Р{х) и от погрешностей в коэффициентах многочлена, мы не можем предложить оценки лучшей, чем е{т) = 2(zm2-<-i 2- . Уравнение для точки экстремума т функции е(т) имеет вид е{т) = gln2 - 2 2-*- - 1п2 2~. 2 U; Таким образом, при вычислениях на ЭВМ с /. разрядами нельзя надеяться на получение более точных приближений к значениям функции, чем с t/{q + l) разрядами. Например, для функции /(а;) = (1 + 253;) нижней гранью (р, при которой f{z) аналитична в области G,, будет (fo = arctg0,2; соответствующее значение q + 1 3,2. Таким образом, на ЭВМ с 60 двоичными разрядами мы в лучгпем случае можем рассчитывать на получение приближений к значениям функции примерно с 20 верными двоичными разрядами. Если производная f\x) не существует в некоторой внутренней точке отрезка при не очень большом I, то согласно примечанию к теореме имеет место еще ббльшая потеря точности результата. Можно привести следующий довод об исключительности подобной обстановки. Обычно приходится приближать целые функции или такие, особенности которых лежат далеко за единичным кругом. Тогда из проведенных выше рассмотрений столь уд1эучающие выводы не следуют. Формально это верно, однако такого рода функции часто, являясь целыми аналитическими функциями, очень быстро возрастают при увеличении мнимой части у аргумента. Хотя для таких функций величины / остаются равномерно ограниченными по 71, они могут принимать сталь большие значения, что величина j/ 2 ~ окажется существенно больше допустимой погрешности. Примером подобных функций является функция {х) = / exp{iXt} dt для больших Л. Эти обстоятельства побуждают к отысканию иных простых форм записи и вычисления значений многочленов. Обратимся к форме записи многочленов наилучшего приближения в виде суммы значений многочленов Чебышева Рп{х) = Y.djTj{x). (3) 2 Тп{х)Тт{х) г 2 3-0 3=1 3=0 Имеем поэтому Tn{x)Tm{x) J /2 при n = m = 0, прип -f > 0, Отсюда следует, что 2 = -j 2/(+. Подставив это значение в выражение для е{т), получим 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 |