Федоренко Р.П. Введение в вычислительную физику (Федоренко Р.П. Введение в вычислительную физику.djvu), страница 8

Н. Бернштеином было показано, что полиномы, интерполирующие на равномерной сетке функцию /( г) = ~ ! ! с ростом /ч не только не сходятся к интерполнруемой функции, по Рвах ~1.»(!) — ~ г~ ~ — ! при лг ««. -!«!«! Совсем иначе и совершенно замечательно ведут себя интерполяционные полиномы с чебышевской сеткой. Для того чтобы объяснить это их свойство, нам понадобятся некоторые факты из так называемой «конструктивной теории функций». Введем полипом степени л!, наилучшим образом аппроксимирующий данную функцию /(г) на (О, т'ь т,е. полинам, реализующий ш!и (шах ~Р (г) — /(!) ~) =Е»(/).

Р О«!«г Здесь ш1п берется по всем полиномам степени не выше /ч. Полипом наилучшей аппроксимации существует, но его фактическое построение является очень трудной задачей. Такие полиномы находятся только сложными итерационными алгоритмами так называемой Негладкой оптимизации и требуют большого объема вычислений. Таким образом, полипом наилучшего приближения к /(!) на (О, Т) является обьектом по существу не конструктивным, его использование в практической вычислительной работе в общем !ч.с зз основы вычислитвльной млтвмлтики случае просто невозможно.

Однако теоретические его свойства хорошо изучены. В частности, известна асимптотика величины Е,(У) при М- ° . Она оказалась однозначно связанной с гладкостью У(с). Несущественно огрубляя формулировки, приведем основные факты, Если у(с) имеет на (О, Т) ограниченную г-ю производную, то Е„Ц) = О(1/М"). И наоборот, если Е„(У) имеет такую асимптотику, то /„имеет ограниченную г-ю производную.

Хотелось бы иметь конструктивный метод построения полиномов, дающих аппроксимацию функции у(с), близкую к наилучшей. Оказывается, таким является интерполяцнонный полипом иа чебышев- ской сетке! Этот факт мы сейчас докажем. Теорема 4. Пусть Еи( с; (с„), (У„) ) — ннтерполяционный полипом для у(с) на интервале (О, Т) с чебышевской сеткой. Тогда !Е (С) — У(С) ! К (1 + 1п М)Е,(У), С Е (О, Т), т.е.

такой полипом дает почти наилучшую для полиномов степени М аппроксимацию функции с (с) на (О, Т). Доказательство. Пусть Рсс (с) — полипом наилучшей аппроксимации У(с). тогда У„Р„(с„) + ь„, причем погрешности ь„удовлетворяют условиям ! Ь„! к Ел(У). Обозначая р, Рл(с„), имеем Е„(с; (с„), У„)) = Е„(с; (с„), (Р„+ Ь„)) = = Ев(с' (Св)* (Р )) + с-и(с' (С,) (Ь,)). но еи(с; (с„), (Р„)) = Рсс (с), так как интеРполациоиный полипом степени М, построенный для полинома степени не вьппе М, в точности совпадаег с интерполируемым (при любой сетке). Для второго слагаемого имеем оценку !.С.к(С; (С„), (Ь„))! К 1и М !!(Ь„)!! = 1 М Е (/).

используя представление Р (с) = ~(с) + ь(с), где !ь(с) ! к е„(с), получаем Е„(с; (с„), (у„)) = у(с) + Ь(с) + Е„(с; (с„), (Ь„)). Для погрешности аппроксимации имеем оценку !Ь(С)+С.„(С; (С„), (Ь„))! К (!+!и М)Е ®. Теорема доказана.' Таким образом, нитерполяционный полипом на чебышевской сетке (напомним, что он легко выписывается в явном виде, так как корни полиномов Чебышева вычисляются по простым формулам) замечательным образом адаптируется к фактическим свойствам гладкости интерполируемой функции.

ивтзгполяцня «тнкаий зз1 Дифференцирование интерполяциоиного многочлена. Из того, что две функции близки, как известно, еще не следует близость их производных. Однако в рассматриваемом случае ситуация более благополучная: Е(г) аппроксимнрует /(г), а производные Ь(г) — производные /(О, хотя точность аппроксимации, конечно, издает с ростом порядка производной, Ограничимся здесь лишь указанием на следуюпшй факт: производная Е,„(г) является интерполяционным полиномом степени М вЂ” 1 для функции У'(г), построенным на сетке, отличающейся,от исходной.

Это почти очевидно: мехщу каждыми двумя нулями функции У(г) — Е„(г), например между г„н г„„имеется хотя бы один нуль производной. Обозначим его г„'. « Итак, в точках (г„')„".,, 'полипом Ь„' (г) совпадает с У'(г). Точность аппроксимации производных / производными Е„падает как за счет понижения порядка полинома, так и за счет возможного появления в новой сетке неравномерного распределения шагов г„', — 1„'. Сплайн-интерполяция. В последние пщы большое распространение в прикладных исследованиях получил новый, достаточно точный вид интерполяции, требующий, однако, от функции существенно меньшего запаса гладкости, чем интерполяцнонный полином. Происхождение зтого аппарата интерполяции и сам термин «сплайн» связывают с техническим приемом чертежников.

При необходимости провести непрерывную кривую через сеточный график (г„,,г„)„" е на бумаге наносят точки (г„„г„), около каждой из которых втыкают рядом друг с другом две булавки, и через образовавшийся «коридор» пропускают тонкую, гибкую и упругую стальную линейку («сплайн»). Форма, которую принимает эта линейка (вдаль нее и проводят требуемую линию) решает, кик мы увидим, задачу гладкой интерполяции. Математическое исследование обьясннло популярность описанного приема, заменяющего работу с лекалом.

Полученная кривая оказывается дважды непрерывно дифференцнруемой, а это свойство очень ценится в технике. Пример, который приводили в годы учебы автора и, верно, приводят сейчас: железнодорожный путь должен быть кривой с непрерывной второй производной. В противном случае в местах разрыва второй производной при движении поезда возникает «удар», разрушающий и рельсы, и колеса.

упомянутое исследование читатель без труда проведет сам. Пусть у(1) — форма, которую принял «сплайн»: Теория упругости определяет эту форму требованием минимума энергии упругого со- ОСНОВЫ ВЫЧНСЛНТЕЛЬНОЙ МАТЕМАТНКН стояния. Таким образом, у(г) определяется решением вариационной задачи т нпп ~ [у"(~)]В»й при у(Г„) =~„, Н=О, 1, ..., М. го> О Здесь у(') — функция у(г), рассматриваемая целиком как точка функционального пространства, а у(~) — в данном случае число, являющееся значением функции в точке и Элементарное вариационное исчисление сразу дает результат: внутри интервалов [»„, г„+1) функция у(г) удовлетворяет «уравнению Эйлераь В(«у/~й~ = О и условиям трансверсальности, которые во внутренних узлах г«п гз, ..., гя, сводятся к непрерывности первых 'и вторых производных. Из уравнения Эйлера следует, что у(г) является кубическим миогочленом: на каждом интервале [г„, г„+,[ имеется свой кубический многочлен, н все оии гладко сопрягаются друг с другом.

Итак, с алгоритмической точки зрения сплайн у(г) определяется таблицей ТН-~ [Н„«пм й«+пз С„+ьв „НВТВ и формулой вычисления у(г) о«+пя г + ь«+пз г + с«+1й г+»(и+им г е [г« г«+1[ Построение сплайна по таблице [~„, У„)„'» В требует, таким образом, вычисления 4М коэффициентов, Для этого мы имеем следующие уравнения. Каждый кубический полином иа концах своего интервала [г„, г«+,) принимает заданные значения /„и 1„г Это, очевидно, дает 2М линейных уравнений. В каждой внутренней точке сетки г„8м ..., Тн ~ имеем два условия, приравнивая правые и левые значения первой и второй производных, т.е. еще 2(Ф вЂ” 1) линейных уравнений. Оставшиеся два уравнения получаем из условий трансверсальиости при г = О и » = Т.

Мы не будем здесь выписывать конкретного вида уравнений, не будем излагать и метода их решения (при больших Ф это самостоятельнан проблема, требующая применения специфического алгоритма). Соответствующие вопросы давно решены, алгоритмы разработаны, описаны в многочисленных руководствах и включены в математическое обеспечение ЭВМ как стандартные программы. Мы ограничимся лишь общими сведениями о сплайнах. Этот аппарат был существенно обобщен и развит. В частности, разработаны методы двумерного гладкого восполнения функций, т.е. построения на основе таблицы (у„„), заданной на 41 ИНТЕРПОЛЯЦИЯ ФУНХЦНй 1З1 двумерной сетке узлов (х, у ) (Я=О, 1, ..., К, т О, 1, ..., л«), гладкой интерполирующей поверхности 7(х, у), точки которой достаточно легко вычисляются.

Сплайны нашли широкое применение при описании пространственных форм разных изделий. Они часто сообщаются (из конструкторских бюро на производства) таблицами (сеточными функциями) с указанием, что недостающие точки поверхности можно получить сплайн-интерполяцией. Интерполяция конечными элементами.

Опишем аппарат восполнения функции, заданной на сетке, до некоторой непрерывной функции той илн иной степени гладкости (т.е. имеющей заданное число непрерывных производных). Первойачально интерполяция рассматривалась как способ приближенного (но достаточно «дешевого» по затратам вычислительной работы) вычисления функций, «точные» значения которых в узлах сетки можно было найти каким-либо очень «дорогим» алгоритмом.

В настоящее время методы интерполяции рассматривакпся и используются в несколько ином аспекте — как способы конечиомерной аппроксимации тех нли иных функциональных пространств. Поясним сказанное. Многие задачи математической физики ставятся следующим образом. В некоторой заданной области изменения независимых переменных (для определенности, х и у) надо найти функцию из заданного функционального пространства ИР, удовлетворяющую некоторым уравнениям (включая краевые условия).

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

Возникает задача аппроксимации различных функциональных пространств, причем требуется именно хорошая аппроксимация, определяемая возможно меньшим количеством информации. В этом смысле классическая теорема Вейерштрасса о возможности сколь угодно точно аппроксимировать произвольную («измеримую») функцию полиномом достаточно высокой степени практически мало полезна. Если функция не слишком гладкая, такая аппроксимация требует слишком высокой степени полннома и оказывается нерациональной. Теперь рассмотрим одну, интересную саму по себе задачу математической физики — задачу Пуассона, В некоторой заданной об- 42 основы вычнслнтвльноя млтвмАтнкн ласти О в плоскости (х, у) нужно найти функцию и(х, у), удовлетворяющую уравнению ави а»и + =У(х «) ах' ау' где г — заданная «правая часть».