Вычислительная математика лекции. Конспект лекций. Санкт петербург 2011 2 Оглавление
 Скачать 3.86 Mb.
|
|
Теорема о существовании и единственности алгебраического интерполяционного полинома. Пусть заданы узлы x 0 ,…,x n , среди которых нет совпадающих, и значения y 0 ,…,y n функции y(x) в этих узлах . Существует один и только один алгебраический многочлен P m (x) степени m n, принимающий в заданных узлах x k значения y k =y(x k ). Из теоремы в частности следует, что если y(x)=P m (x) и m n, то интерполяционный полином P n (x), построенный на n+1 узлах совпадает с P m (x). В дальнейшем ограничимся анализом алгебраической интерполяции. 3.2. Формулы алгебраической интерполяции. Ниже приводятся формулы, позволяющие записать алгебраический интерполяционный полином без составления и решения системы алгебраических уравнений. Полагаем, что задана сеточная функция с n+1 узлами 0 { , ( ) } n k k k k x y x y 3.2.1 Интерполяционный полином в форме Лагранжа. L n (x)= 0 ( ) n k k k w x y 23 Полином w k (x) будем искать в следующей форме 0, ( ) ( ). n k k i i i k w x c x x Потребуем 1, если x=x ( ) 0, если x=x , i k, i=0, . k k i w x n Константа c k определяется из условия w k (x k )=1.Откуда 0, 1 ( ) k n k i i i k c x x Таким образом, 0, ( ) n i k i i k k i x x w x x x Нетрудно убедится, что w k (x i )=0, когда i ≠k, 0, . i n Окончательный вид интерполяционного полинома в форме Лагранжа 0 0, ( ) n n i n k k i i k k i x x L x y x x L n (x) – интерполяционный полином, построенный на n+1 узлах. Действительно, L n (x) есть полином степени не выше n, так как w k (x) – полином n – ой степени, а, кроме того, L n (x k )=y k ( 0, k n ). Эквивалентный вариант записи формулы Лагранжа: 0 0 ( ) ( ) , ( ) ( ). ( ) '( ) n n k i k i k k x L x y x x x x x x Упражнения. 1.Записать интерполяционный полином a)L 1 (x); b)L 2 (x). 2.Дана таблица функции y=ln(x) i 0 1 2 3 4 x 1.0 1.1 1.2 1.3 1.4 y 0.000000 0.095310 0.182322 0.262364 0.336472 24 Вычислить приближенное значение ln(1.23) для а) линейной интерполяции; б)квадратичной интерполяции. Оценить погрешности. 3.Построить L 3 (x) для табличной функции x 0 2 3 4 y 2 0 1 6 3. 2.2. Интерполяционный полином в форме Ньютона. 0 0 0 1 0 1 0 1 2 0 1 0 1 0 1 0 1 0 0 ( ) ( ) ( ) ( , ) ( ) ( , , ) ... ( )...( ) ( , ,..., ) ( , ,..., ) ( ); ( ) 1; ( ) ( ). n n n n k k k k k i i N x y x x x y x x x x x x y x x x x x x x y x x x y x x x x x x x x Докажем, что N n (x) есть интерполяционный полином. Действительно это полином не выше n – ой степени. Кроме того, для любого x i ( 0, i n ) 0 0 0 1 0 1 0 1 2 0 1 0 1 ( ) ( ) ( ) ( , ) ( ) ( , , ) ... ( )...( ) ( , ,..., ) ( ) n i i i i i i i i i N x f x x x y x x x x x x y x x x x x x x y x x x y x Последнее равенство следует из формулы, связывающей значения сеточной функции с разделенными разностями. В отличие от формы Лагранжа при добавлении узла в сеточной функции форма Ньютона не требует пересчета всех её слагаемых: N n+1 (x)=N n (x)+y(x 0 ,x 1 ,…,x n ,x n+1 )ω n+1 (x). В силу теоремы о существовании и единственности алгебраического интерполяционного полинома при любом способе вычисления получают идентичные полиномы. 25 3. 3.Остаточный член интерполяционного полинома. Оценка погрешности интерполирования. Назовем остаточным членом интерполяционного полинома функцию r n (x)=y(x)-P n (x). Если для y(x) известны только значения в узлах, то никаких суждений о r(x) сделать невозможно. Дополнительную информацию можно получить, если предположить y(x) 1 [ , ] n a b C Рассмотрим расширенную систему узлов x 0 ,x 1 ,…x n ,x n+1 =x (x [a,b]). Для вычисления y(x) применим формулу, связывающей значения сеточной функции с разделенными разностями y(x)=y 0 +(x-x 0 )y(x 0 ,x 1 )+…+(x-x 0 )…(x-x n-1 )y(x 0 ,…x n )+(x-x 0 )…(x- x n )y(x 0 ,…,x)= =N n (x)+(x-x 0 )…(x-x n )y(x 0 ,…,x). Отсюда r n (x)=y(x)-N n (x)=(x-x 0 )…(x-x n )y(x 0 ,…,x n ,x). Учитывая, что ( 1) 0 1 ( ) ( , ,..., , ) , [a,b], ( 1)! n n y y x x x x n получаем ( 1) 1 ( ) ( ) , [a,b]. ( 1)! n n n y r x n Задача оценки погрешности состоит в отыскании [ , ] max | ( ) | . n x a b r x ( 1) 1 1 1 [ , ] [ , ] [ , ] max | ( ) | max | ( ) | , где M max | ( ) |. ( 1)! n n n n n x a b x a b x a b M r x x y x n 3.4. Минимизация погрешности интерполирования. Пусть число узлов (n+1) фиксировано и о функции y(x) известно лишь, что она имеет (n+1) ограниченных производных. Тогда единственным средством уменьшить погрешность является 26 выбор узлов сетки. Этот выбор должен удовлетворять решению характерной задачи на минимакс 0 1 , ,..., 0 min max | ( ) | . n n i x x x a x b i x x Из всех возможных стандартных полиномов ω n+1 (x) путем выбора корней нужно подобрать такой, чтобы модуль его максимального значения на заданном интервале был минимальным. Эта задача, известная как задача о построении полинома, наименее уклоняющегося от нуля, была решена (по другому поводу) П.Л. Чебышевым, который доказал, что такими свойствами обладают нормированные полиномы, известные под его именем. Таким образом, наилучшей является сетка, узлы которой совпадают с корнями нормированного полинома Чебышева степени (n+1) на интервале [a,b]. Свойства полиномов Чебышева. 1. Полином Чебышева n – ой степени T n (t)=cos(n arccos(t)) (t [- 1,1]) можно рассчитать по рекурсивным формулам T 0 (t)=1; T 1 (t)=t; T n (t)=2t n-1 (t)-T n-2 (t); n=2,3,… . 2. На отрезке [-1,1] полином T n (t) имеет n вещественных корней (2 1) cos ; k=0, 1. 2 k k t n n 3. Коэффициент при t n равен 2 n-1 4. При n ≥0 1 1 max | ( ) | 1. n t T t Если n ≥1, то этот максимум достигается ровно в n+1 точках, которые находятся по формуле cos , m=0, . m m t n n При этом T n (t m )=(-1) m , т. е. максимумы и минимумы многочленов Чебышева чередуются. Предположим, интерполяционный полином строится на отрезке [-1,1] . Тогда для минимизации погрешности нужно 27 выбрать узлы, совпадающие с корнями полинома Чебышева. То есть 1 1 1 ( ) ( ). 2 n n n t T t Тогда 1 1 1 max | ( ) | ( 1)!2 n n n t M r t n Произвольный отрезок [a,b] приводится к стандартному [-1,1] заменой переменных 2 ; t= 2 2 2 a b b a a b x t x b a При этом оказывается 1 1 0 0 0 ( ) ( ) 2 2 2 2 t = ; 2 2 2 n n n n n i i i i i i i i i i b a a b b a x x x t x t t a b x b a a b b a x t Для минимизации погрешности значения t i должны совпадать корнями T n+1 полинома Чебышева : (2 1) cos ; k=0, . 2 i i t n n Таким образом, выбор чебышевских узлов приводит к следующему результату 1 1 max | ( ) | ( 1)!2 2 n n n n a x b M b a r t n Можно показать, что выигрыш по сравнению с равномерным выбором узлов составляет 4 n e раз. 3.5. Сходимость интерполяционного метода. Будем говорить, что при заданной стратегии выбора узлов метод интерполяции сходится, если ΔP n = max ( ) ( ) 0 , n n y x P x x a b 28 Из конструктивной теории функций известно, что для заданной степени n существует полином Q n (x) наилучшего приближения такой, что min max ( ) ( ) ( ) Q , n n n y x Q x E y x a b . Здесь E n (y) наименьшая достижимая погрешность. Алгоритм построения такого полинома настолько сложен, что его практическое использование нецелесообразно. Известна асимптотика E n (y): E n (y)=o(1/n r ), где r наибольший порядок ограниченной производной y(x). В этом случае E n (y) →0 при n→∞. Интересно выяснить, насколько близка погрешность интерполяции к E n (y). Теорема. Пусть P n (x) интерполяционный полином для y(x) на интервале [a,b] с чебышевской сеткой. Тогда ΔP n (1+ln n) E n (y). Таким образом, погрешность интерполяционного полинома с чебышевской сеткой близка E n (y). Для интерполяционного полинома с равномерной сеткой аналогичная оценка будет иметь величину порядка 2 n При n →∞ в случае использования чебышевской сетки ΔP n →0 даже, если r=1; для равномерной сетки в аналогичных условиях ΔP n →∞. Рассмотренная выше ситуация обобщается следующими теоремами: Теорема1. Какова бы не была стратегия выбора узлов, найдется непрерывная на интервале [a,b] функция такая, что метод интерполяции расходится, то есть ΔP n (y) →∞ при n→∞. Однако для функций, обладающих ограниченными производными, стратегия, обеспечивающая сходимость, существует. 29 Теорема2. Пусть в качестве узлов интерполяции выбирают чебышевские узлы. Тогда для любой функции, обладающей ограниченными производными на [a,b], метод интерполяции сходится. Ниже приведен пример функции с несуществующей первой производной внутри заданного интервала. 3.6. Устойчивость интерполяционного полинома относительно погрешности вычисления y(x). Пусть y i вычисляются с погрешностью y* i =y i + δ i , причем | δ i | δ. Используем лагранжеву форму интерполяционного полинома L n (x)= 0 n i i i y w . Тогда * * [ , ] 0 | ( ) ( ) | ( | ( ) |) max max [ , ] n n n n i x a b i L L x L x w x x a b Величина Λ n = [ , ] 0 | ( ) | max n i x a b i w x называется константой Лебега Она не зависит от [a,b], но только от расположения узлов Для чебышевской сетки Λ n =(2/π) ln(n+1)+1 Для 30 равномерной сетки Λ n > 1 2 (2 1) n n n (n≥4 Из формул следует, что интерполяционный полином с чебышевскими узлами малочувствителен к вычислительным ошибкам. 3.7. Интерполяция сплайнами. Как следует из анализа сходимости и вычислительной погрешности метода интерполяции, попытки уменьшить методическую погрешность путем увеличения числа узлов не всегда оправданы. Иногда бывает целесообразней использовать кусочно-- полиномиальную интерполяцию, когда общее число узлов разбивается на небольшие группы и строят ряд интерполяционных полиномов малой степени на узлах каждой группы. Широкое распространение получил метод интерполяции сплайнами, реализующий одну из модификаций указанной идеи. Пусть отрезок [a,b] разбит точками a=x 0 < x 1 < … x n =b на частичные отрезки [x i-1 ,x i ] i=1,2,…,n. Сплайном степени m называется функция S m (x), обладающая следующими свойствами: 1. S m (x) непрерывна на [a,b] со всеми своими производными до некоторого порядка p. 2.На каждом частичном отрезке [x i-1 ,x i ] функция S m (x) совпадает с некоторым алгебраическим полиномом P mi (x) степени m. Разность m-p называется дефектом сплайна. Наибольшее распространение получили сплайны 3-ей степени (кубические) с дефектом 1 или 2. Сплайн называется интерполяционным, если S m (x i ) =y i для i=0,1,…,n. 31 3.7.1. Обсуждение способа построения кубического интерполяционного сплайна с дефектом 1 . Пусть отрезок [a,b] разбит точками a=x 0 < x 1 < … x n =b на n частичных отрезков [x i-1 ,x i ], i=1,2,…,n . P 3i (x) =a i +b i (x-x i-1 )+c i (x-x i-1 ) 2 +d i (x-x i-1 ) 3 Всего n кубических полиномов и соответственно 4n неизвестных коэффициентов a i , b i , c i , d i . Для их однозначного определения необходимо сформулировать 4n условий. Первая группа условий следует из равенства значений сплайна и сеточной функции в узлах: P 3i (x i )=y i ; P 3i (x i-1 )=y i-1 i=1,2,…,n. Всего 2n условий Вторая группа следует из непрерывности 1-ой и 2-ой производных во внутренних узлах: P (1) 3i (x i )= P (1) 3i+1 (x i ); P (2) 3i (x i )= P (2) 3i+1 (x i ); i=1,2,…,n-1. Всего 2(n-1) условий. В сумме получаем 4n-2 условия. Недостающие два условия нужно задать в паре внешних узлов x 0 и x n . Возможны следующие варианты: а) P (1) 3i (x 0 )=γ 0 ; P (1) 3i (x n )=γ n ; γ 0 , γ n заданные числа. б) P (2) 31 (x 0 ) =η 0 ; P (2) 3n (x n )=η n ; η 0 , η n заданные числа. в) P (2) 31 (x 0 ) =0; P (2) 3n (x n )=0. В двух первых случаях γ 0 , γ n , η 0 , η n совпадают с значениями производных y(x) в соответствующих точках. 32 При выполнении условий а) или в) сплайн называют фундаментальным или естественным соответственно. Существуют другие способы задания граничных условий. В результате имеем линейную систему из 4n уравнений для 4n неизвестных коэффициентов. С целью экономии машинной памяти осуществляют редукцию системы путем исключения некоторых переменных. В результате можно получить размер матрицы , равным n, и сделать ее трехдиагональной. При использовании дополнительных условий в форме а) или б) погрешность оценивается по формуле 3 [ , ] | ( ) ( ) | max x a b y x S x CM 4 h max Для k-ой производной справедливо соотношение ( ) ( ) 3 [ , ] | ( ) ( ) | max k k x a b y x S x CM 4 h 4-k max Для естественного сплайна порядок точности понижается с 4 до 2. |