|
| |
|
Слаботочка Книги О при г ф j. Задача интерполирования будет решена, если удастся построить многочлены Фi{x) степени не выше п - 1 такие, что ФД.х) = при i,j = 1,...,п. Многочлен 9п{х) = Х/(х,)Ф.Дх) будет искомым интерполяционным многочленом. В самом деле, 9nixj) = J2fi--)Mi) = ffSi = fix,): i=l i=l кроме того, (ж) - многочлен степени n - 1. Поскольку Фi{xj) = О при j Ф г, то Фг{х) делится на x - Xj при j ф г. Таким образом, нам известны п - 1 делителей многочлена степени п - 1, поэтому Ф.Дж) = const]J[(ж -Xj). Из условия Фг(жг) = 1 получаем X - ж,- КИМ образом, доказано существование и единственность интерполяционного многочлена вида (2). Непосредственное нахождение коэффициентов с помощью решения этой системы уже при сравнительно небольших п, например, при п = 20, приводит к существенному искажению коэффициентов щ вычислительной погрешностью. Кроме того, как мы увидим в гл. 4, уже сама запись многочлена в традиционной форме (2) часто приводит к большой вычислительной погрешности результата. При теоретических исследованиях, например при конструировании алгоритмов решения других задач, эти обстоятельства могут не играть роли. Однако при реальных вычислениях влияние вычислительной погрешности может быть недопустимо большим, и поэтому применяются другие виды интерполяционного многочлена и способы его записи. Можно получить явные представления интерполяционного многочлена (2), не прибегая к непосредственному решению системы (3). Сразу же отметим, что в других случаях, например при интерполирован функций многих переменных, получение интерполяционного многочлена в явном виде затруднительно, и часто приходится прибегать к непосредственному решению системы уравнений типа (1). Пусть есть символ Кронекера, определяемый соотношениями I 1 при i = j, Рп = ( ((а ж -ь а 1)ж + а 2)ж -1----х + Интерполяционный многочлен (2), записанный в форме .9 (х) L4X-) = ffix,) П (4) , , Xi Xj называют интерполяционным многочленом Лагранжа. Существуют другие формы записи того же интерполяционного многочлена (2), например рассматриваемая далее интерполяционная формула Ньютона и ее варианты. При точных (без округлений) вычислениях значения, получаемые по различным интерполяционным формулам, совпадают. Наличие же округлений приводит к различию в получаемых по этим формулам значений интерполягщопных многочленов. Запись ьшого-члена в форме Лагранжа, как правило, приводит к меньшей величине вычислительной погрешности; запись же многочлена в форме Ньютона более наглядна и позволяет лучше проследить аналогию проводимых построений с основными построениями математического анализа. Кроме того, этим различным формам записи соответствует различное количество арифметических операций при вычислении с их помощью значений интерполяционного многочлена. Мы употребили термин количество арифметических операций . Поясним, что имеется в виду. Пусть рассматривается задача вычисления значения многочлена Р (х-) = а. ж -Ь а 1ж -Ь----h oix + ао в точке ж. Вычисления можно проводить различными способами. Например, можно поступить следующим образом. Вычислить значение aix и сложить с ао- Далее вычислить значение а2Ж и сложить с полученным результатом и т.д. На j-ы шаге, таким образом, вычисляется значение ajX и складывается с уже вычисленной суммой ao+aiX-\-----[-gj-iX . Вычисление значения gjx требует j операций умножения. Таким образом, описанный выше алгоритм требует для вычисления значения моно-гочлена {I + 2 + -{- п) = п{п + 1)/2 операций умножения и п операций сложения. Количество арифметических операций (действий) в данном случае будет равно Ф1 = п{п + 1)/2 + п. Ясно, что количество арифметических операций, необходимых для вычисления значения Рп{х), может быть уменьшено. Например, можно последовательно вычислить и запомнить значения х, ж,..., ж . Для этого потребуется п - 1 операций умножения. Далее вычисляем величины ajX {j = l,...,n). Это потребует п операций умножения. Складьшая полученные значения (это требует п операций сложения), получаем Рп{х). В этом случае Ф2 = (2п - I) + п и уже при тг > 2 имеет место неравенство Фг < Фь Можно пойти еще дальше. Запишем Р (ж) в виде Для вычисления значения во внутренних скобках аж + a i требуется одна операция умножения и одна операция сложения. Для вычисления значения в следующих скобках (a j; + a. i)a; + a,i 2 требуется опять одна операция умножения и одна операция сложения, так как а ж + а -1 уже вычислено, и т.д. Таким образом, вычисление Р (ж) при помощи этого алгоритма потребует п операций умножения и п операций сложения, то есть Фз = п + п. Ясно, что Фз < Фг < Ф] при п>2. Таким образом, вычисление Рп{х) по последнему алгоритму потребует меньше арифметических операций и, соответственно, меньше времени ЭВМ. Количество арифметических операций, которое требуется для получения результата, является одной из важнейших характеристик метода, по которой происходит сравнение методов. Иногда до начала вычислений не удается точно оценить требуемое количество арифметических операций, а удается оценить лишь порядок количества арифметических операций по отношению к какому-либо параметру. В рассматриваемом выше примере Ф) = 0{г?), Ф2, Фз = п - степень многочлена. В последнем случае (Ф2, Фз = 0[п)) говорят, что методы имеют одинаковый порядок количества арифметических операций. В тех случаях, когда находится порядок количества арифметических операций, бывает важно найти постоянную в главном члене. Например, Фх = + о{г?), Ф2 = Зп о(п), Фз = 271. Как правило, метод, требующий меньшего количества арифметических операций, является более быстрым, и поэтому считается лучшим. Выбирая метод решения сложных задач, часто ограничиваются лишь сравнением порядков количества арифметических операций для различных методов. Заметим, что значение многочлена Рп{х) определяется параметрами оо, oi,..., On и величиной ж. Поэтому в обгцем случае для вычисления Рп{х) потребуется не менее п арифметических операций, т.е. мы имеем оценку снизу для количества арифметических операций. Таким образом, второй и третий методы вычисления Р (ж) являются оптимальными по порядку, так как Ф2, Фз = 0{п) и для любого метода Ф > п. В связи с появлением многопроцессорных вычислительных комплексов может случиться так, что метод, требующий большего количества арифметических операций, будет быстрее другого метода с меньндам количеством арифметических операций. Поэтому для случая многопроцессорной ЭВМ нельзя оценивать качество метода только по количеству арифметических операций. 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 |