|
| |
|
Слаботочка Книги у,...;хп) = ;; р,(. .)-) п при 1=П, ЩХ0,...,Хп)-< п при Кп при любых ЖО, - . , Хп- Предположим, что точки Ж1,...,ж пронумерованы в порядке возрастания: Ж1 < Ж2 < < ж . Вследствие (4) имеем т! f{xk;...] Xk+m) = / (й), где Sk Ск Хк+т-Поэтому величина М = sup m! \f{xk;...; Хк+т)\ 1<к<п-к Пусть (ж)-интерполяционный многочлен Лагранжа с узлами интерполяции XI,..., Хт- Интерполяционный многочлен Лагранжа Ln{x) можно представить в виде Lnix) = Ых) + {L2{x) - L,{x)) + + (Lnix) - Ln-iix)). (2) Разность Ljn{x) - L i-iix) есть многочлен степени m - 1, обращающийся в нуль в точках xi,..., х,п-1, поскольку Lm-i{xj) = Ljn{x,) = f{xj) при 1 j m - 1. Следовательно, Lm{x) - L.,n-lix) = Arn-1 COm-lix), U).,n-i{x) = (x - Xi) . . . (x - X,n-l), где Am-i = const. Полагая x = Хщ, получим f{Xjii) Lm-\{Xjn) = Afra-Xm-XXni)- С другой стороны, полагая в (1) п = m - 1 и х = Хт, имеем !{Хт) - Lm-X {Хт) = f{Xm\ Xi\ . . . ; Xjn-l) т-Лх-т). Таким образом, Am-i = f{xi; и поэтому Lrnix) - Lm-i{x) = /(зм; ...; х) ujrn-i(x). Подставляя эти величины в (2), получим Lnix)=f{xi) + f{xi;x2)ix-Xi) + --- + f(xi;...;xn)(x-xi)...{x-Xn-i}- (3) Интерполяционный многочлен, записанный в такой форме, называется интерполяционным многочленом Ньютона с разделенными разностями. Из сравнения (1) с (3.1) следует важное равенство f{x;xi;...;xn) = !-, yi < С У2- (4) В частности, если f{x) - многочлен Pi{x) = Y}x степени I п, то на основании этой формулы имеем (з)(ж) 1(п~1,п){х) Эта схема положена в основу стандартной программы решения следующей задачи. Дана таблица значений некоторой функции /(.г); требуется при каждом значении х вычислить значение /(ж) с заданной точностью е или с наилучшей возможной точностью при имеющейся информации. Трудно дать четкое определение термина стандартная программа. По установившейся традиции стандартной программой решения задач некоторого класса называют квалифицированно написанную программу, содержащую описание алгоритма решения задач данного класса. Решение конкретной задачи осуществляется подсоединением к стандартной программе информации об этой конкретной задаче. От стандартной программы также требуется, чтобы допускалось ее использование как элемента программы, предназначенной для решения более сложных задач. Рассматриваемое ниже построение алгоритма решения задачи является довольно типичным для ситуации, возникающей в реальной практике. может использоваться в качестве приближенной оценки для величины М( )= sup f Hx) Задача 1. Доказать неравенство где hjn = max {х+т - Xk)- Для упрощения вычислений интерполяционного многочлена иногда используется так называемая схема Эйткена. Пусть L(jt,:-j-i..)(ж)-интерполяционный многочлен с узлами интерполяции Xk,---,xi, в частности =/(a;.). Справедливо равенство , %-+1,...,/+1)(ж)(ж-.гА:)-L(;t,... )(.x)(x-x,+i) fk,k+i,...,i+i)\X) =-----(о) действительно, правая часть является многочленом степени I - к + \ и совпадает с /(ж) в точках жд,-,..., x+j. Схема Эйткена вычисления значения L(i .)(ж) заключаетс;я в последовательном вычислении с помощью формулы (5) элементов таблищл значений иптерполяционн1Лх многочленов /(1)(Ж) (1,2) (ж) (2)(а) (1,2,3) (ж) (2,3)Н . 1(1,2,...,п){х) § 6. Разделенные разности и интерполирование с кратными узлами Пусть требуется построить многочлен gsix) степени s - 1, удовлетворяющий условиям gsixi) = fixi}, gh-4xi)=/-Hi), .................................................... (1) gsiXn) = f{Xn), . . . , 5 -)(ж ) = f --\xn), Невозможно предложить обоснованный алгоритм решения поставленной задачи для всех функций, поскольку про функцию ничего не известно, кроме ее значений в заданных точках. Однако, предполагая функцию гладкой, мы выводим практический критерий оценки погрешности и, основываясь на нем, строим алгоритм решения задачи. Пусть X фиксировано; перенумеруем узлы интерполяции в порядке возрастания а:. Интерполяционные многочлены будем обо- значать, как обычно, L;n{x). Выше получено представление погрешности (1) /(х) - L.,n{x) = /(ж; жх;...; ж) с., (ж), а также равенство Lrn+\{x) - Lm{x) = /(xi;...; ж, +1) (ж). (6) Так как при малых ж - х} fix; xi;...; ж) и --j- и /(xi;...; x., +i), то отсюда следует /(ж) - L (x) L +] (ж) - Lm{x). (7) Поэтому величину £т = \Lm+i{x) - Ljn{x)\ можно рассматривать как приближенную оценку погрешности интерполяционной формулы /(ж) и Lrnix). Последовательно вычисляют значения Ьо(ж), Li(x), £i, L2(x), £2,...; если при некотором т будет Sm £, то вычисления прекращают и полагают fix) и Lraix). Если это неравенство не выполняется ни при каком т, то находят ео = min £ и полагают /(ж) Lmo(a;). Если этот минимум достигается при нескольких т, то среди них выбирают наименьшее. Если величины Ет, начиная с некоторого т, имеют устойчивую тенденцию к увеличению, то с этого момента вычисление значений 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 |