МУ к лабораторным работам, страница 6

(Произвольное расположение узлов интерполяции на отрезке периодичности). Пусть заданы значения f i :i = 1, …, N, периодической с периодом L функции f (x ) в N = 2nнесовпадающих точках xi : i = 1, …, N, принадлежащих отрезку [a , b], b  a  L, f (a)  f1  f N  f (b).Тогда существует один и только один интерполяционныйтригонометрический многочлен2 ( x  a)2 ( x  a ) N 1Q n  cos, sin, f    f k  l k ( x ),LL k 0sinl k ( x)  ( x  x1  a ) sin ( x  xi  a) sin(2.32) ( x  x N 1  a )LLL ( xk  x1 a ) ( xk  xi  a ) ( xk  x N 1  a )sin sin sinLLL.(2.33)(В произведениях отсутствует сомножитель, соответствующий i = k, так что l k ( xk )  1 ).Построенные тригонометрические многочлены обладаютопределенными преимуществами перед алгебраическим многочленом, построенным по значениям функции в узлах xm .Во-первых, при N   погрешность тригонометрической интерполяции2 x2 xR N ( x, f )  f ( x )  Q cos, sin, fLLравномерно стремится к нулю, если f (x ) имеет хотя бы вторуюпроизводную, причем скорость убывания погрешности автоматически учитывает гладкость f (x), т.

е. возрастает с ростомчисла (r+1) производных:ln N max | R N ( x) |  O  M r 1,Nr xM r 1  maxxd r 1 f ( x )dx r 1.(2.34)37Во-вторых, чувствительность тригонометрического интерполяционного многочлена к погрешности задания значений f mв узлах с ростом числа узлов «почти» не возрастает.Эти два положительных свойства тригонометрической интерполяции, а именно, возрастание точности при увеличениигладкости и вычислительную устойчивость, можно придать иалгебраической интерполяции функций на отрезке за счет специального выбора узлов интерполяции и использования алгебраических многочленов Чебышева, обладающих многими замечательными свойствами.2.15.

Многочлены ЧебышёваМногочлены Чебышёва можно ввести по формуле Tk (x )  cos (k arccos x), k  0, 1,  . Функции Tk (x ) суть многочленыстепени k = 0, 1, … При этом T0 ( x)  1, T1  x; T2 ( x), T3 ( x) …вычисляются по рекуррентной формулеTk 1 ( x )  2 x Tk ( x )  Tk 1 ( x ).(2.35)Нули Tk (x ) определяются из уравнения:Tk ( x)  cos (k arccos x)  0,т. е. x m  cos ( 2 m  1)2k(2.36), m = 0, 1,  , k  1.Точки экстремума Tk (x ) определяются как:xl  coslk,1 = 0, 1, …, k.Таким образом, Tk (x ) на интервале 1  x  1 имеет k вещественных нулей и k  1 точку экстремума. На оси x эти точкиполучаются проекцией пересечения полуокружности с множеством лучей, имеющих между собой равные углы.2.16. Алгебраический интерполяционный полиномна сетке из нулей полинома ЧебышёваПри выборе в качестве узлов интерполяции нулей полинома Чебышева интерполяционный полином можно записать в виде:38nPn ( x, f )  ak Tk ( x),(2.37)k 0nгдеa0 nf mT0 ( x m ) /(n  1);ak  2m 0f m Tk ( x m ) /(n  1);m 0n + 1 — число узлов интерполяции.2.17.

Алгебраический интерполяционный полиномна сетке из экстремумов полинома ЧебышёваПри выборе в качестве узлов интерполяции экстремумов полинома Чебышева интерполяционный полином можно записать вследующем виде:nPn ( x, f )  ak Tk ( x),(2.38)k 0гдеa0 ak an 12n1n( f0  fn ) 1 n 1n m 1( f 0  (1) k f n ) 12nfm,2 n 1nf m T k ( x m ),m1( f 0  ( 1) n f n ).Здесь n + 1 — число узлов интерполяции.2.18. Чувствительность интерполяционноготригонометрического многочленак погрешностям задания функциив узлах интерполяцииЧувствительность интерполяционного тригонометрического многочлена к погрешности задания значений f m оценивается следующим образом. Пусть вместо f  [ f m ] задана сеточная функция f  f  { f m  f m }.

Тогда возникающая погрешность392 x2 xQ n  Q n  cos, sin, f LL(2.39)и, следовательно, мерой чувствительности интерполяционноготригонометрического многочлена к возмущению f входныхданных могут служить числа L n , называемые константамиЛебега (см. п. 2.8):(2.40)max | Qn |  Ln max | f m | .xmТ еор ем а 13. Константы Лебега тригонометрическогоинтерполяционного многочлена удовлетворяют оценке L n  2n.Интерполяционный полином на сетке из нулей или экстремумов полиномов Чебышёва наследует от тригонометрическойинтерполяции слабый рост константы Лебега при увеличении n.Для этого случая справедлива оценкаLn 2ln n  1.2.19.

Контрольные вопросы1. Докажите, что при выборе в качестве узлов интерполяции нулей полинома Чебышева, алгебраический интерполяционныйполином можно записать в видеnPn ( x, f ) a k Tk ( x ),k 0гдеa0 1n 1nm 0f m T0 ( x m ),ak 2n 1nf mTk ( x m ) .m 0Здесь n + 1 — число узлов интерполяции.2.

Докажите, что при выборе в качестве узлов интерполяцииэкстремумов полинома Чебышева алгебраический интерполяционный полином можно записать в виде40nPn ( x, f )  ak Tk ( x),k 0где коэффициентыa0 ak an 12n1n1n( f0  fn ) 1 n 1nf m T0 ( x m ),m1( f 0  (1) k f n ) ( f0  (1)n f n ) 2 n 1n1 n 1nf m Tk ( x m ),m 1f m (1)m Tn ( xm ).m 1Здесь n + 1 — число узлов интерполяции.3. Выведите формулы для интерполяции табличной функциикубическим сплайном (Шонберга):а) на равномерной сетке;б) на неравномерной сетке.У ка з а ние. Пусть mi — значение второй производной в i-м узле,mi 1 — значение второй производной в i + 1-м узле. На отрезке[ xi , xi 1] P3( x) — линейная функция. На этом отрезке P3 ( x) —непрерывная функция, которую можно получить, дважды интегрируя P3( x) по x.

При этом возникают две константы интегрирования. Они находятся из условий: P3 ( xi )  f i , P3 ( xi 1)  f i 1.Для значения вторых производных mi строится система алгебраических уравнений из условия P3 ( xi  0)  P3 ( xi  0).2.20. Порядок выполнения работы1. Войдите в меню «Параметры/Таблица» и выберите из предложенного списка функций в пункте «Функции» какую-нибудьгладкую (т.

е. имеющую непрерывные производные) функцию.В меню «Сетка» выберите пункт равномерная, число узлов,равное двум. Алгебраический интерполяционный полином какой степени может быть построен по этим данным?Выберите в подменю «Метод/Глобальная» строку «Ин41терполяционный полином в форме Лагранжа», степень которого 3, 4, 5, 6, 7, , 50. Постройте интерполяционный полином.Теоретически оцените погрешность интерполяции и сравнитеее с фактической (т. е.

разностью между исходной функцией иее интерполянтом по данной таблице) погрешностью, выбравпункт меню «Окна/Ошибка». Сформируйте таблицу, выбравфункцию, имеющую:а) только две непрерывных производных ( y  sign ( x ) x 3 / 3);б) одну непрерывную производную ( y  sign ( x) x 2 / 2);в) не имеющую непрерывной производной ( y = | x | ).Как будет меняться фактическая погрешность восстановленияфункции с ростом степени полинома для равномерной сетки?Почему в пункте a) для нечетных степеней k интерполяционногополинома ошибка меньше, чем для k – 1 и k + 1? То же для сеткииз нулей полинома Чебышева.

Чем объяснить существенное различие в поведении погрешности?2. Выберите целую (разлагающуюся в сходящийся степенной2ряд для любого конечного x) функцию (например, y  e  x ) ипостройте на сетке из равноотстоящих узлов глобальный алгебраический интерполянт. Сравните различные способы вычисления интерполяционного полинома:находя его коэффициенты по базису {x k }, решая соответствующую линейную систему;б, в) записывая интерполяционный многочлен в формеЛагранжа; в форме Ньютона.Какой способ требует меньшего числа арифметическихдействий?Выберите число узлов n = 10, 20, 30,  , 90. Объяснитепроблемы, возникающие при численном решении линейнойсистемы.

Почему результаты использования формы Ньютона иЛагранжа в начале совпадают, а затем начинают различаться?Проанализируйте накопление погрешности при вычисленииполинома в форме Ньютона при перенумерации в порядке возрастания и в порядке убывания (интерполяция вперед и назад)?Как изменятся результаты, если вычисления производить сдвойной (мантисса 52 бита) и стандартной (мантисса 24 бита)точностью?а)3.

Проанализируйте влияние погрешности задания функции в42узлах на величину фактической погрешности восстановленияфункции. В силу линейности интерполяции эти эффекты удобно изучать на функции у = 0. Как задать распределение погрешности для получения максимального отклонения междуузлами интерполяции? Рассмотрите случай равноотстоящихузлов и сетку из нулей полинома Чебышева. Сравните с теоретической оценкой.4. Сравните фактическую погрешность интерполяции функций2y  exи y  1 /(1  25 x 2 ) (функция Рунге) на отрезке5  x  5 на равномерной сетке при числе узлов n = 11, 21, 31,41, 51. В чем причина отсутствия сходимости интерполяционного процесса для функции Рунге? Задайте теперь отрезок интерполяции 0  x  5 и повторите вычисления. Попытайтесь объяснить полученный результат.У ка з а ние. Обратите внимание на то, что функция y  e  xцелая, а функция Рунге имеет полюсы при x  0,2i.25. Посмотрите, как ведет себя глобальный интерполянт вне отрезка, на котором расположены узлы интерполяции.

Для этого вменю «Окно» установите соответствующие границы измененияаргумента x для отображения f (x ) и Pn ( x, f ). Что лучше использовать для экстраполяции: глобальный интерполянт или кусочно-многочленный?6. Сравните ошибку при алгебраической интерполяции и интерполяции сплайнами на равномерной сетке из 3, 4, …, 25 узлов наотрезке [–1, 1] следующих функций:а)x33sign x;2б) e  x ;в) функции Рунге.Объясните результаты.7.

Интерполирующим кубическим сплайном (Шонберга) приближается функция0, x  0;y ( x)  1, x  0.на отрезке x  [1, 1].Почему в окрестности разрыва возникают осцилляции? Как43меняется их амплитуда в зависимости от изменения числа узловсетки? Объясните эффект. Ответьте на те же вопросы для локального сплайна.8. Исследуйте, как изменяется ошибка интерполяции какой-либогладкой функции при кусочно-линейном восполнении и приглобальной интерполяции с увеличением числа узлов.9. Выбирая функции, имеющие одну, две и т. д.

непрерывные наотрезке производные, убедитесь, что кусочно-линейная интерполяция насыщается гладкостью, в то время как ошибка глобальной интерполяции на сетке из нулей полинома Чебышеватем меньше, чем больше непрерывных производных имеет f (x )(не насыщающийся гладкостью алгоритм).2.20. Библиографическая справкаТеория интерполяции — обширный раздел вычислительной математики. В данной работе изложение ведется по книге [1]. Другие аспекты тории изложены в [9, 10], в частности, подробнорассмотрено свойство насыщаемости алгоритмов. О построенииглобального сплайна см. [11]. О локальных сплайнах, кроме [1],см.

также [12].В связи с развитием алгоритмов машинной графики бурноразвивается теория сплайн-интерполяции. О применении сплайнов и кривых Безье см. также [5]. Различным приложениямсплайнов посвящены книги [13–15]. В [5, 14]дается понятие оВ-сплайнах, нашедших широкое применение как в алгоритмахмашинной графики, так и в развитии численных методов. Оприменении В-сплайнов в инженерных расчетах см. в [16]. В[15] описаны алгоритмы построения сглаживающих сплайнов,находящие применение, в частности, в обработке экспериментальных данных.44Л АБОР АТ ОРН АЯ РАБОТ А 3ЧИСЛЕННОЕ ИНТЕГРИРОВАНИЕ3.1. ВведениеРабота предоставляет возможность наглядно исследовать свойства основных квадратурных формул для вычисления определенного интегралаbI   f ( x) dx.aПоясняются способы конструирования квадратурных формул,методы оценки погрешности, к которым они приводят. Демонстрируются приемы вычисления несобственных интегралов.3.2.