Форсайт Дж., Малькольм М., Моулер К. - Машинные методы математических вычислений (1040536), страница 15
Текст из файла (страница 15)
В конце концов эти точки могут быть интерполированы бесконечным множеством различных функций, и нужно иметь некоторый критерий выбора. Обычно критерии формулируются в терминах гладкости и простоты; например, функция 7 должна быть аналитична и максимальное значение ~("(х)~ по всему интервалу должно быть насколько возможно мало, или 7' должна быть полииомом наименьшей степени, и т. п. Многие интерполирующие функции генерируются линейными комбинациями элементарных функций. Линейные комбинации одночленов (хл) приводят к полиномам.
Линейные комбинации тригонометрических функций (соз ях, ып ях) ведут к тригонометрическим полиномам. Используются также, хотя и реже, линейные комбинации экспонент (ехр(рлх)) или рациональные функции вида аа+ а1х+... + атх р,+ р,х+... + цх" В этой главе мы рассмотрим сначала полиномиальную интерполяцию, а затем один внд кусочно-полнномиальной интерполяции, так называемую сплайн-интерполлцию. лт.
Полиномиальная интеололяция Исторически и прагматически наиболее важным классом интерполирующих функций является множество алгебраических полнномов. Полиномы имеют очевидное достоинство — их значения легко вычислять (5 4.2). Их также легко складывать, умножать, интегрировать или дифференцировать. Еще одно свойство полиномов: если с — константа, а р(х) — полипом, то полиномами будут и р(сх), и р(х+с). Разумеется, класс функций может иметь все вышеуказанные свойства и тем не менее не иметь удовлетворительных аппроксимационных качеств. К счастью, у нас есть веские основания полагать, что любая непрерывная функция 7(х) на замкнутом интервале может быть хорошо приближена некоторым полиномом р„(х). Это следует из раннего результата теории приближений, так называемой аппроксил ационной теоремы Вейерщтрасса: Если à — непрерывная на конечном замкнутом интервале (а, Ы функция, то для любого е)0 существует полипом р„(х) степени п=п(е), такой, что шах ~) (х) — р„(х) ~ < е.
епь Н с ИНТЕРПОЛЯЦИЯ Подробное доказательство можно найти в книгзх Рэлстон (1965) или Вендрофф (1966), Хотя некоторые доказательства теоремы Вейерштрасса имеют конструктивный характер, получаемый полипом р„ обычно столь высокой степени, что пользоваться им непрактично. Далее, тео-, рема Вейерштрасса ничего не говорит о существовании удов..1 летворительного интерполяционного полинома для заданног множества точек ((хь у;)). И хотя утешительно знать, что не который полинам аппроксимирует !(х) с заданной точность на всем интервале (а, б), нет гарантии, что такой полипом можно найти посредством практичного алгоритма.
Полипом степени и можно записать по степеням х: у (х) = а, + а х + а,х'+... + а„х" = ~, агх' о=в (здесь и+1 коэффициентов). Чтобы однозначно определить коэффициенты, нужно задать и+1 корректно поставленных условий. При интерполяции обычно требуют, чтобы полипом проходил через и-!-! точек (х,, д,), 4 =О, 1,..., и, где все х, различны. Это дает и+1 линейных уравнений для неизвестных коэффициентов а4. д, =- ~~' а,х( (4 =О, 1, ..., П).
!=0 Решение, если оио существует, определяется единственным образом, как показывает следующее рассуждение. Зафиксируем множество (х; ), состоящее из различных точек. Если бы имелось два полинома у и г, принимающих одни и те же значения у; в точках х; (!=О, 1, ..., П), то разность у — г обращалась в нуль для и+1 различных значений переменной х. Поскольку степень у — г не превышает и, то у — г обязан быть нулевым полиномом, следовательно, у и г должны совпадать. Это доказывает единственнощпь полинома степени (и, интерполирующего произвольное множество из и+1 точек, но яе его существование.
Вспомним теперь, что и-";! уравнений, определяющих коэффициенты полинома у через заданные (у;), являются липей- ными. Один из главных результатов линейной алгебры состоит в том, что линейная система либо имеет единственное решение для любого набора (у4), либо существуют наборы (у,.), для которых решений много. Поскольку мы только что доказали, что более одного решения не может быть, значит, должен существовать единственный полипом для любой иитерполяционной задачи с и-!-1 различными абсциссами.
Итак, мы можем провести единственный полипом степени ='п через любые и+1 точек с различными абсциссами, и это один из возможных подходов к поставленной в начале этой главы а ь полиномнхльнхя ннтьиполяция 8! задаче интерполирования. Поскольку все множество данных включается в одну полииомиальную функцию, то она может быть, названа глобальпаьи интерполянтом ') этих данных.
После того как мы решили для интерполирования воспользоваться многочленом степени (п, в наших руках еще остается возможность выбора базиса в пространстве таких многочленов. В приведенном выше доказательстве был взят базис из одно- членов 1, х, х', ..., х". Зто приводит, как мы видели, к системе линейных уравнений, которая в принципе может быть решена методами гл. 3.
Однако во многих случаях уравнения чрезвычайно плохо обусловлены. Предположим, например, что абсциссы (х;) распределены приблизительно равномерно на интервале [О, 1[. Оказывается, что последовательные степени 1, х, х', ... почти линейно зависимы на интервале [О, 1[, отчасти потому, что все они положительны и графики всех идут от (О, 0) к (1, !). Именно эта близость к линейной зависимости делает решение линейной системы при нормальной рабочей точности крайне трудным делом для порядка п, превышающего 10. Гораздо более удовлетворительный способ вычисления полниома, который интерполирует точки (хо у;), состоит в использовании базиса так называемых лагранжевых полипомое, ассоциированных с множеством (х;).
Это полиномы (1;(х)) ([=-О, 1, ..., и) степени п, такие, что [ 1, если 1=-), ( О в противном случае. Легко видеть, что полипом степени п (х — ха) (Х вЂ” Ху)...(х — Х/ 1) (х — Х) е1)... (Х хн) 1 (х)— (х — хе) (ау — х )...(х — ху,) (х — луе,)...(х — хн) удовлетворяег этим условиям. По предыдущему 1; определяется единственным образом. Каждый множитель числителя обращает 1,(х;) в нуль при некотором (эь)Ь Соответствующие множители знаменателя нормируют полипом так, что 1)(хэ)=1. Полином 1)(х)у) принимает значение д; в точке х, и равен нулю во всех точках х; ((~1).
Таким образом, интерполяционный полином степени и, который проходит через и+! точек (хь у;), выражается формулой у (х) =- ~ 1, (х) д .. )=е ' Ясно, что число арифметических операций (и, следовательно, время выполнения) для этого метода пропорционально и'-', ') В оригинале — 8)оьа! Ы.— Прим. перев, с интеРполяция 82 Важно подчеркнуть еще раз, что существует один и только один полинам степени (и, который интерполирует заданные и+! точек. В литературе имеется множество различных формул для интерполяционных полиномов, основанных на различном выборе базисов; однако при данном наборе точек все они порождают один и тот же полинам.
Таким образом, полином, получаемый посредством этого подхода, совпадает с полиномом, найденным путем решения линейных уравнений, при условии, что вычисления проводятся в точной арифметике. Ошибки округлений, соображения, связанные с памятью и временем, могут повлиять на выбор метода. Главное соображение при выборе — это конкретное применение иптерполяционного полинома. Коэффициенты такого полинома нужны редко. Обычно лагранжева интерполяция или какой-либо аналогичный метод является лучшим выбором. Часто глобальную полиномиальную интерполяцию лучше не применять вообще. Мы приведем сейчас один довод в пользу этой точки зрения.
Лнтерполяционным массивом на отрезке (а1 о) назовем любой треугольный массив 1 х, х"; х,' хз .1 .Е с тем свойством, что все х'; Е [а, Й и элементы каждой отдельной строки различны. Пусть Р„(!)(х) — интерполяционный полипом, совпадающий с функцией ~(х) в точках п+)-й строки. Теорема Фабера Для любого интерполяционного массива найдутся непрерывная функция д и тонка х ио (а, Ь), такие, что Р„(д) (х) не сходятся к а (х) при п-4-оо. В 5 4.3 мы приведем пример, иллюстрирующий теорему Фабера. Упражнения 4.5 и 4.7 дают другие убедительные образцы особенностей в поведении полиномиальной интерполяции.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
