Амосов А.А., Дубинский В.А., Копченова Н.В. Вычислительные методы для инженеров (1994) (1095853), страница 62

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 62)

Однако для гладких функций (а именно такие функции чаще всего и интерполируются) такая стратегия существует, о чем говорит следующая теорема. Т е о р е и а 11.8. Пусть в качестве узлов интерполяции на отрезке [а, Ц выбираются чебышевские узлы (11.43). Тоьда для любой непрерывно дифференцируелой на отрезке [а, 6] функции ~ метод интерполяции сходится. Воспользуемся тем, что ~4о(х) ~ + ]!п(х) ] = 1 для х Е [хо, х1]. Следова- тельно, тах ]Р|(х) — Р,*(х)~ < шах 1~со], ]е1~).

(хо, х1] Таким образом, при линейной интерполяции погрешность, возникающая вследствие погрешности значений функции, не превосходит верхней границы погрешности этих значений. Рассмотрим теперь общий случай. Пусть известно, что верхняя граница погрешности значений у,'. равна Ь(у'), т. е.

~е,~ 4 Ь(у') для всех ~ = О, 1, ..., и. Тогда для верхней границы соответствующей пог- решности многочлена Ь(Р„') = тпах ~ Р„(х) — Р„'(х) ~ в силу равенства [а,6] (11.60) справедлива оценка Ь(Р ) 4Л Ь(у ) (11.61) 3 а м е ч а н и е. В случае, когда ] е;] = Ь(у~) для всех ~, выбором знаков погрешностей е, можно добиться выполнения равенства Ь(Р„') = Л„Ь(у').

Это означает, что в самом неблагоприятном случае погрешность входных данных при интерполяции может возрасти в Л„раз. Таким образом, в задаче интерполирования константа Лебега играет роль абсолютного числа обусловленности. Величина Л„не зависит от длины отрезка ~а, о], а определяется лишь относительным расположением узлов на нем. Для того чтобы 1 Анри Леон Лебег (1875 — 1941) — фраяцузский математик, один из создателей современной теории функций вещественной переменной и теории интегрирования. 328 Здесь Л„= шах ~», ~ 4,~(х) ! — величина, которую называют хомстам- ': 1а,о]~ о адой Лебе1а1.

показать зто, приведем отрезок [а, Ц к стандартному отрезку [ — 1, 1) с а+ЬЬ-а помощью линейного преобразования х = 2 2 + — 3. Тогда х, = а + Ь Ь вЂ” а 2 — + 1; и константа Лебега приводится к виду 2 п Л„= шах Е Д,Я~) [, где ) у*О (Я- ХЬ) 1„(ю) = й йфу (11.62) Р„(х) = Е аууу,(х).

Здесь [щ(х))~~ — некоторый набор базисных многочленов <рЬ(х), обла- дающий тем свойством, что всякий многочлен Рп(х) степени и может быть однозначно представлен в виде (11.62). Например, можно ис- 329 Естественно поставить задачу о таком оптимальном выборе узлов интерполяции, чтобы величина Л„оказалась минимально возможной. Для малых значений в эту задачу решить нетрудно. При а = 1 выбор 1а = -1, $1 — — 1 дает Л1 —— 1. При и = 2 оптимальное значение Л2 — 5/4 достигается, например, при 10 — -1, $1 — — О, $р — — 1. В общем случае оптимальный выбор узлов неизвестен.

Установлено, однако, что почти оптимальным является выбор в качестве узлов интерполяции нулей 2 многочлена Чебышева Т„+1. При таком выборе Л„~ — 1п (и + 1) + 1. С рассматриваемой точки зрения крайне неудачным при больших и является выбор равноотстоящих узлов интерполяции. При таком выбо- 2" ~ ре Л„> для л 1 4 и обусловленность задачи резко ухудша(2в — 1)~/и ется с ростом а. Сказанное позволяет сделать важный вывод: в вычислениях не следует использовать интерполяционные многочлены высокой степени с равноотстоящими узлами. 3. Обусловленность задачи вычисления многочлена с приближенно заданными кшффш~иентаии Обратим внимание на еще один потенциальный источник потери точности при использовании многочленов Р„(х) высокой степени.

Для определенности будем считать, что много- член вычисляется на отрезке [а, Ь], где ~ а~ ~ Ь, причем предварительно он представлен в виде пользовать степенной базис (хЬЦ о, нормированный степенной базис < Их — а1Ь1" ц ~, локальный степенной базис ~ ~ ~ ~, чебышевский '[Ь~ 1Ь-,' Ь вЂ” в~ Ьао Гх - (а + Ь)/211" базис ТЬ )), лагранжев базис (1„Ь(х))ь~ (см.

Ь 11.3) н т. д. При вычислении коэффициентов аЬ неизбежны погрешности, приводящие к приближенным значениям а~. Поэтому. в действительности будет вычисляться многочлен Р„*(х) = Е а ь~рЬ(х). Примем за относительную погрешность вектора ° ' = (а,'„а,', ..., а„')т величину б(а') =-. (щах [а, — а,'.~)/пьах ~ а;[, 04 южан 0<~<в а за относительную погрешность многочлена Р„*(х) — величину Ь(РР) =( шах [Р„(х) — Р~~(х) [)/ шах ~ Р„(х) ~. [а, Ь] [а, Ь| Числом обусловленности задачи вычисления ино~очлена с приближенно эаданны.ии коэффициентами назовем величину сопй„, равную минимальной из постоянных К„, для которых выполняется неравенство 6(Р„') < К„б(а'). Величина сопд„, характеризующая чувствительность вычисляемых значений многочлена к погрешностям в коэффициентах аЬ существен- но зависит от выбора базиса (щ(х))" . Неудачный выбор базиса мо- жет сделать эту, казалось бы, элементарную задачу очень плохо обусловенной.

Доказано, например, что даже для вполне "разумного" а1 Й1 н локального степенного базиса ~ ~ ~ ~ число обусловленнос- Ь- 1Ь=. ти оценивается снизу величиной Т„(3). Как видно из табл. 11.11, использование указанного базиса для представления многочленов высокой степени сопряжено с опасностью значительной потери точности. 330 Таблица 1111 а 1 2 3 4 5 6 7 8 9 Т (3) 3 17 99 577 3363 19601 114243 665857 3880899 Отметим, что для чебышевского базиса сош1„< ~~2 (и + 1). Для лагранжева базиса число обусловленности совпадает с константой Лебега Л„. Напомним, что при почти оптимальном выборе узлов ин- 2 терполяции Л„м — 1п (п + 1) + 1.

Итак, глобальная полиноми альп ая интерполяция многочленом высокой степени может привести к неудаче или оказаться неэффективной. Альтернативный подход состоит в Локальной интерполяции, когда. функция 1 аппроксимируется интерполяционным многочленом Р„,(х) невысокой степени тп на содержащемся в [а, Ц отрезке [а, Д малой длины. Естественно, что при этом используется лишь часть табличных значений. Рассмотрим два подхода к приближению функции, основанные на локальной интерполяции. 4. Интерполирование с помощью "двилсущегося" полинома. Строят набор полиномов Р~о1 ...

„1, Р,1г ... ~11, ..., Р<„„„~,1,. „~ фикс~ированной степени т, каждый из которых совпадает с табличными значениями в ш + 1 последовательных точках. Каждый такой полипом используют для приближения функции в тех точках х из отрезка [а, 6], для которых выбранные узлы таблицы являются ближайшими. Пример 11.11. Пусть функция задана следующей таблицей: Т а б л и ц а 11.12 1 0 1 2 3 4 0 1 2 3 4 у; 1.0 1.8 2.2 1.4 1.0 Для интерполяции этой функции воспользуемся "движущимся" полиномом второй степени. Заметим, что при х Е [0.0, 1.5] для приближения используется многочлен Р~о12~(х), при х Е [1.5, 2.5] — многочлен Р<12з~(х), при х Е Е [2.5, 4.0] — многочлен Р~ т з ~1(х). Соответствующая геометрическая иллюст— рация приведена на рис.

11.6. Заметим, что полученная таким способом аппроксимирующая функция имеет разрывы в точках х = 1.5 и х = 2.5. 331 Рис. П.7 5. Кусочно-полииомиальная интерполяция. Исходный отрезок [а, $] разбивают на несколько отрезков меньшей длиньг, на каждом из которых функция интерполируется своим многочленом. Пример 11.12.

Для интерполяции функции из примера 11.11 используем кусочно-полиномиальную интерполяцию. На отрезке ~0, 2~ аппроксимируем функцию многочленом Р, о 1 21 (х), а на отрезке [2, 4] — многочленом Р( 2 3 4) (х). Соответствующая геометрическая иллюстрация приведена на рис. 11.7. Заметим, что результирующая аппроксимирующая функция непрерывна, но в точке х = 2 график ее имеет излом, соответствующий разрыву первой производной. Заметим, что интерполяцию "движущимся" полиномом можно рассматривать как частный случай кусочно-полиномиальной интерполяции.

Как следует из оценки (11.30), метод кусочно-полиномиальной интерполяции при использовании многочленов фиксированной степени т имеет (т + 1)-й порядок точности относительно Ь 332 З 11.11. Интерполяция сплайнами 1. Определение сплайна. Проведенное выше обсуждение интерполяции показывает, что повышение точности приближения гладкой функции благодаря увеличению степени интерполяционного многочлена возможно (см. теорему 11.8), но связано с существенным повышением сложности вычислений.

К тому же использование многочленов высокой степени требует специальных мер предосторожности уже при выборе формы их записи, и вычисления сопровождаются накоплением ошибок округления. Поэтому на практике предпочитают кусочн~полиномиальную интерполяцию с использованием многочленов невысокой степени. Однако этот способ приближения имеет недостаток: в точках "стыка" двух соседних многочленов производная, как правило, имеет разрыв (см. пример 11.12). Часто это обстоятельство не играет существенной роли. Вместе с тем нередко требуется, чтобы аппроксимирующая функция была гладкой и тогда простейшая кусочно-полиномиальная интерполяция становится неприемлемой. Естественная потребность в наличии аппроксимирующих функций, которые сочетали бы в себе локальную простоту многочлена невысокой степени и глобальную на всем отрезке [а, 5] гладкость, привела к появлению в 1946 г.

так называемых сплайн-функций или сплайнов— специальным образом построенных гладких кусочно-многочленных функций. Получив в 60-х годах распространение как средство интерполяции сложных кривых, сплайны к настоящему времени стали важной составной частью самых различных вычислительных методов и нашли широчайшее применение в решении разнообразных научнотехнических и инженерных задач. Дадим строгое определение сплайна. Пусть отрезок [а, а] разбит точками а = хо < х1 « ...

Характеристики

Список файлов книги