Н.Н. Калиткин - Численные методы (1133437), страница 10
Текст из файла (страница 10)
Для их получения вычислим первую и вторую производные многочлена (20): др' (х) = Ь; + 2с,(х — хд,) + Зд(д (х — х;,)', др" (х) =- 2с;+ бд(д (х — л д,) при х~ „:.== х =. хо и потребуем непрерывности этих производных (т. е. гладкости л1шейкн) во всех точках, включая узлы. Приравнивая во внутреннем узле х, правые и левые пределы производных, получим Ьдэд =-Ьд+ 2сд)дд+Зс(д)д), 1 » д ~ М вЂ” 1, (23) сад — — с1 + Зс(~Ь о 1~д =М вЂ” 1.
(24) Недостающие два условия обычно получают из естественного предположения о нулевой кривизне графика на концах: ~!ддс (х0) = сд —— -О, ~дддг (хл) = см+ Зс(ч)ду =- О, что соответствует свободно отпущенным концам линейки. Но если есть дополнительные сведения об асимптотнке функции, то можно записать другие краевые условия.
Уравнения (21) — '(25) образуют систему линейных уравнений для определения 4М неизвестных коэффициентов. Эту систему можно решить методом исключения Гаусса, описанным в главе Ч. Но гораздо выгоднее сначала привести ее к специальному виду. Уравнение (21) сразу дает нам все коэффициенты а,. Из уравнений (24) и (25) следует с(;= — (с;„— сд)~'3)дд при 1 =-д~.й( — 1, (26) д( = — сх,'З)д Подставим соотношение (26) в (22), одновременно исключая оттуда а~=у;,; тогда получим Ьг = [(Гп — Уг-д)!Ьд) — дlзйд (сад+ 2сд), 1 -=. д ~ дУ вЂ” 1, (27) Ья = [(Ул — Ум-дУ~Ы тайлсм, Исключим теперь из (23) величины Ь, и Ьцм при помощи (27), соответственно увеличивая во втором случае индекс на единицу, а величину с(д — на основании (26).
Останется система линейных уравнений для коэффициентов со легко приводящаяся к следующему виду: сд — — О, Ьь,с, д+ 2 (йод+ Ь~) с;+Ь,с„д =- = 3 [(у, — уд д) 1)д, — (у,, — уд э)А д) при 2 ~ д ~ Ф, см„д = О. (28) 46 АППРОКСИМАЦИЯ ФУНКЦИЙ 1гд. !1 Матрица этой системы трехдиагональна, т. е. ненулевыми в ней являются только элементы главной диагонали и двух соседних. Такие системы экономно решаются методом прогонки, изложенным в главе и'.
После нахождения коэффициентов с; остальные коэффициенты нетрудно вычислить по формулам (21), (26) и (27). Можно рассмотреть более общую задачу интерполяции функции сплайыом — многочленом п-й степени: п 5(х) = ~ а;ьхь, х, т~х=-хы а=о коэффициенты которого кусочно-постоянны и который в узлах интерполяции принимает заданные значения н непрерывен вместе со своими и — 1 производными.
При нечетной степени многочлена п=2р — 1 можно рассматривать сплайновую интерполяцию как решение задачи лангранжевой интерполяции при дополнительном условии ~ [5'Р' (х) 1' с(х = пип. а Из этого условия следует уравнение 5"Р'(х) =О для интерполирующей функции, условия непрерывности 2р — 2 производных во внутренних узлах н естественные ограничения на производные в крайних узлах. На практике употребительны два случая. Один — подробно рассмотренный здесь случай и =-3. Второй — п = 1, когда сплайн совпадает с многочленом Ньютона первой степени и соответствует аппроксимации графика ломаной, построенной по узлам; опреде.
ление коэффициентов прн этом очевидно. Онлайновая интерполяция напоминает лагранжеву тем, что она требует знания в узлах только значений функции, но не ее производных. По области применения она занимает промежуточное положение между линейной и нелинейной лагранжевой интерполяцией. Ее целесообразно применять тогда, когда сетка недостаточно подробна для интерполяции многочленом Ньютона, но еще не настолько редка, чтобы необходимо было прибегать к нелинейной интерполяции. Если функция так же резко меняется за один шаг сетки, как в таблице 5, то сплайновая интерполяция не гарантирует хорошей точности.
Наиболее успешно применяют сплайновые интерполяции при разностном решении краевых задач для эллиптических уравнений в частных производных с гладкими коэффициентами. 1О. Монотонная интерполяция. Монотонность — важное свойство функций. Например, возьмем таблицы синусов с шагом аргумента 1', тогда на каждые 89 интервалов, в которых функция будет моногонна, придется всего 1 интервал, содерзкащий экстремум. Поэтому при интерполнции нередко желательно сохранять монотонность функции. 47 интеРполиРОВАние 4 и Если интерполяционная функпия гр(х; п) монотонна по л, тб интерполяция будет монотонной.
Классический пример — двухточечная интерполяция миогочленом Ньютона К', (х]=о,бгпгх. Другим примером покет служить двухточечная квазнлпнейная интерполяция (19). Очевидно, если интерполяция квазилннейная двухточечная, а преобразования з) (у), $ (х) монотонны, то интерполяция будет монотонной. Ппьн трехтсжсчпой интерполяции монотонность может нарушиться. В таблице о (п. 8) функция, по-видимому, монотонна. Но если использовать многочлен Ньютона с тремя узлами, т. е. оставить в формуле Ньютона только три члена, то получим у (гуз) — 6,5, что нарушает монотонность, Очевидно, это результат использования незюнотониой интерполяционной функции — параболы (ыз (х) ==ш+агх+азхз.
Двухточечная йнтерполяция имеет погрешность 0(йз), и ее точность не всегда достаточна; а увеличение числа узлов может внести немонотонность. Коне|но, сели интерполяцпонный ряд Ньютона (8) хорошо сходится, а монотонность все-таки нарушена, то это означает, что функция на самом деле пеягонотонна. Но нередко лгы вынуждены ограничиваться задвинью а формуле (нли программе для ЭВМ) числом узлов, Если при этом надо сохранить монотонностгч то можно поступать следующим образом.
Найдем такие соседние точки сегкн, чтобы выполнялось хг--х=хг„г. Проведем вычислеяия по заданной многоточечной интерполяцнонной формуле и получим уч=ф(х). Если это значеяие лежит между значениями уь уг,г, то считаем ответ правильным. Если ог'о выходит за пределы и|порвала, определяемого значснвями уг, уг„„то вмесго у* в качестве ответа берем ближайшее из этих двух значении, т. е. полагаем у(х).=у* =ш (х) при пни (уь угы) ( у* (шах (уг, угы), у(т)=ш(п(уг, угы) при у* (шит (уь угы), (29) у(х).=шах(уь уыд) при у" ) шах(уг, уыт). Эта монотоннпл интерполяция бывает полезна, например, при составлении разностных схем для уравнений в частных пройзаодных (глава Х, б 1, п.
6). 11. Многомерная интерполяция. Двумерные таблицы широко распространены в физике и технике; например, таковыми являются таблицы термодинамических функций газов, где независимыми переменными обычно являются температура и плотность. Трехмерные таблицы составляют и используют значительно реже, но ие потому, что таких зависимостей нет, а потому, что таблицы слишком громоздки. Четырехмерных таблиц практически нет, хотя в физике немало задач с большим числом параметров; так, проводимость плазмы а(Т, р, Е, О) зависит от ее температуры и плотности, и напряженностей электрического (если сказываются нелинейные эффекты) и магнитного полей. Огметим некоторые существенные стороны многомерной интерполяции. Для простоты ограничимся двумерными таблицами а(х, у); обобщить все результаты на большее число измерений нетрудно.
1) Чтобы объем таблиц был приемлем, приходится шаги по аргументам брать довольно большими. Это предъявляет жесткие требования к способу интерполяции. Часто приходится пользоваться методом выравнивания, т. е. подбирать замену перемен- лппгоксимлция Функции !гл и ных ь (г), ~ (х), т! (у), преобразующую описываемую функцией поверхность в плоскость.
Например, законы зависимости давления горячих газов от температуры и плотности Р (Т, р) близки к степенным. Поэтому при составлении таблиц свойств газов выгодно табулировать ь=-1яР при аргументах $==!я 7, 7) = !ар и сетки по новым аргументам брать равномерными (к сожалению, физики редко это делают). Сходные закономерности справедливы для других термодинамических функций, коэффициентов теплопроводности и электропроводности и еще многих свойств веществ. В дальнейшем мы будем предполагать, что выравнивающие переменные уже подобраны, н таблицы составлены в новых переменных.
Тогда в качестве интерполирующей функции можно использовать многочлеи невысокой степени. 2) Не любое число узлов интерполяции выгодно: Если для одной переменной степень миогочлепа была взаиМно однозначно связана с числом 'узлов,' то для двух переменных многочлен и-ой степени д'„(х, у) = 'У, 'а„„х'у'" имеет (и+1) (и+2)!2 узлов. л-ьт =.О Если число узлов не соответствует этой формуле, то часть коэффициентов прп высших степенях должна задаваться принудительно (в частности, нулями); для выбора этих коэффициентов редко есть разумные основания.
3) В многомерном случае иначе определяется понятие экстра)(оляции. Возьмем узлы интерполяции и соединим их попарно о прямыми (в случае большего числа измере- ний — гиперплоскостями). Крайние отрезки рис. 7. ограничивают выпуклую область (рис. 7). Если искомая точка попадает в эту область, то имеет место интерполяция; если не попадает, то экстраполяция. 4) Не всякое расположение узлов допустимо. В одномерном случае узлы не должны были совпадать. Теперь же для интерполяции многочленом д',(х, у) необходимо, чтобы узлы не лежали на одной прямой в плоскости (х, у).
В самом деле, система трех уравнений а+ Ьх, +су, = г~ имеет определитель ! х, у, Ь(г, гм гз)= ! х, у,)=х (у,— уэ)+хэ(уа — у1)+хэ(уг — уэ), (30) хз уз! который обращается в нуль, если узлы лежат на одной прямой. При интерполяции многочленом Уэ(х, у) требуется, чтобы узлы ие лежали на кривой второго порядка и т. д. АППРОКСИМАЦИЯ ФУНКЦИЙ !Гл. и интерполяции, изображенную на рис. 9 или повернутую на угол, кратный 90', то число узлов будет равно (а+1) (д!+2)!2. Это число однозначно определяет многочлен и-й степени, который удобно записать в форме Ньютона, вводя разделенные разности функции двух переменных. г(ло х,; у)=(г(хо у) — г(хг, у))!(хо — х!), г (х; у„ у,) = (г (х* уо) — г (х УЛ/(уо — у ) и т. д. Такими же рассуждениями, как в одномерном случае, можно показать, что интерполяционный многочлен лагранжева типа имеет следующий вид: У!„(х, у) = л л — 1 ! — 1 ! — ! г (хо хд! уо у!) Ц (л хр) Ц (у уд) (33) -о!=.о р=о д=о В одномерном стучае переменная у и индексы 1, а исчезают, так что форл!ула (33) переходит в обычную формулу Ньютона.
Многомерная интерполяция настолько громоздка, что обычно используется только многочлен первой или второй степени; читателям предлагается записать формулы (31) — (ЗЗ) для этих случаев. Многочлены более высоких степеней используются много реже. По той же причине интерполяция эрмитова типа для многих переменных практически не употребляется. Сплайновая интерполяция используется в основном при разностном решении уравнений в частных производных. Иногда мы вынуждены работать с функцией, заданной на нерегулярной сетке (иапример, с функцией, измеренной экспериментально). Тогда обычно ограничиваются интерполяциопным многочленом первой степени; его коэффициенты находят по трем выбранным узлам, приравнивая в них многочлеи табличным значениям функции: г — а+ Ьх+ су, г! = а+ Ьх1+ суь ! = 1, 2, 3.