|
| |
|
Слаботочка Книги EKI = Е 1*1 <, (ЕО (Е4) = л J=0 j=0 \ j=0 .7=0 \ Отсюда заключаем, что (п + 1)Ё4 Если Р - fWc О, то Таким образом, в этом случае величина Ijl рэстет не быстрее, чем л/п. Поскольку Гп(з;) 1, то погрешность в значении многочлена, которая является следствием погрешностей в dj, не превзойдет величины порядка (EHil)2 * = 0(v2*). Такая оценка погрешности оказьшает- ся приемлемой при реальных вычислениях. Конечно, не обязательно представлять многочлены, приближающие функцию, в виде линейной комбинации (3) многочленов Чебышева. В зависимости от конкретной обстановки иногда удобнее представлять многочлен как линейную комбинацию многочленов какой-либо другой ортогональной системы, например многочленов Лежандра. (Мы рассмотрели систему многочленов Чебышева вследствие наибольшей простоты рекуррентных соотношений для вычисления их значений.) Дадим рекомендации по вычислению значений многочлена Р (ж) на отрезке [-1, 1] безотносительно к вопросу о наилучшем приближении функций. п Пусть в обычной форме этот многочлен записывается в виде ajX и погрешность порядка (\Jlji)2 * является допустимой. Тогда имеет смысл воспользоваться схемой Горнера Рп{х) = Go + x{ai -Ь ж(- -f x{an-i -f хап) )) В противном случае этот многочлен целесообразно представлять в виде линейной комбинации ортогональных многочленов, например многочленов Чебышева: Рп(х) = YdjTjix). Воспользуемся неравенством Коши-Буняковского § 8. Интерполяция и приближение сплайнами Для определенности будем говорить о приближении функции /(ж) на отрезке [О, 1]. Разобьем его на части [xq, xi],..., [xn-i, ждг], xq = 0; х-дг = 1, и обозначим это разбиение через Д. Назовем сплайном бд (/, х) порядка тп функцшо, являющуюся многочленом степени m на каждом из отрезков [хп-1, х ], т. е. 5д (/, х) = РппЛх) = а о Ч- + а , ж при Xn-i х .г , (1) и удовлетворяюшую ус;ювиям непрерывности производных до порядка m - 1 в точках xi,..., жд 1: Pixn) = PiSirnin) при к = 0,...,т~1, n==l,...,N-l. (2) Всего имеется в распоряжении Q = N{m+1) неизвестных коэффициентов Опт, И соотношения (2) образуют систему из {N-l)m линейных алгебраических уравнений. Друтпе уравнения для коэффициентов получаются из условия близости сплайна к приближаемой функции и из некоторых дополнительных условий. Рассмотрим простейшую задачу приближения линейными сплайнами (т = 1). Тогда общее число Q свободных параметров равно 2iV. Поставим вопрос о построении сплайна 5д(/, х), совпадающего с функцией /(ж) в точках жо,...,жлг; получится система уравнений PnliXn~l) = fixn-i), n = l,...,N, PnliXn) = f{xn), n = l,...,N. Для уменьшения числа действий при вычислении значений Р (ж) целесообразно поступить следующим образом. Полагаем Do = do-d2/2, Dj = (dj-dj+2)/2, j = l,...,n-2, Dn-i = dn-i/2, vn = dj2. При необходимости вычислить P (.r) находим у = 2х, Vni = yvn + £) i, затем последовательно находим v,i-2-, , Щ = Рп{х) по рекуррентной формуле Vj, = yvk+i - Vk+2 + Dk- Известно, что вычислительная погрешность такого алгоритма есть О (п min In, г- \ шах Р (.г) 2 * . V I WTj [-1,1] J Задача 2. Проверить, что действительно г;о = Рп(а;). Отсюда находим Многочлен Pniix) является многократно рассматривавшимся интерполяционным многочленом первой степени с узлами интерполяции ж ,-1, Широкое распространение сплайнов во многом вызвано тем, что 01ш являются в определенном смысле наиболее гладкими функциями среди функций, принимающих заданные значения. Сплайны степени выше первой в случае гладкой /(ж) хорошо приближают не только саму функцию, но и ее производные. Сплайны первой степени 5д(/, х) возникают из рассмотрения следующей вариационной задачи. Рассмотрим множество Si кусочно-дифференцируемых функций s{x), удовлетворяющих условиям sixn) = fixn), n = О,..., iV; Ii{s)= [\s{x)fdx < cx). Поставим задачу найти функцию Si{x) G 5*1, реализующую inf hi,). seSi Уравнение Эйлера для этого функционала имеет вид s {x) = 0. Таким образом, 5](.г ) линейна на каждом из отрезков [x-i, ж ] и, следователь-но, si{x) = Siif, х). Этот подход к приближению функции, при котором естественным образом возник сплайн 5д(/, .г), допускает различные обобщения. Рассмотрим, например, множество 5*2 непрерывных, непрерывно-дифференцируемых и дважды кусочно ненрерывно-дифференцируемых функций s{x), удовлетворяющих условиям s{xn) = f{xn), n = 0,...,N; h{s)= l\s {x)fdx<oo. Ищется функция S2{x) € 5*2, реализующая inf his). Решением этой за- дачи оказывается сплайн третьей степени, удовлетворяющий условиям РЧхо) = о, P {xn) = 0. Справедливость этого утверждения непосредственно следует из соответствующих результатов вариациош1ого исчисления. Однако для полноты изложения ниже будет приведено его обоснование. Эта система распадается на системы уравнений относительно коэффициентов отдельных многочленов Pnl{Xn-l) = OjiO +an\Xn-l = f{Xn-l), Pnlin) = a,nO + dniXn = f{Xn)- a-nl = Uin) - fiXn-l))/iXn - Xn-l); OnO = f{Xn-l) - dnlXn-l- 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 |