Самарский А.А. Гулин А.В. - Численные методы (1078412), страница 26
Текст из файла (страница 26)
(ко — кд («о — «о) ... (ко — к„) ... +Е(ко) "' " ' + (к — к,) (х — «,) ... (« — к„,) (к„— «.1 (к. — кд ". (к. - «.,) + (х — х,) (х — х,) ... (х — х,) Е(х, х„х„..., х„) = =Е.а(х)+ (х — х,) (х — х,) ... (х — хп) Е(х, х„..., хл). !ЗЗ Таким образом, погрешность иптериоляцюнной формулы можно представить в виде (5) !(х) — (.„(х) =ы(х)) (х, х„, х„..., х„). Сопоставляя (3) и (5), видим, что существует точка йеи[а, Ь], для которой 1(х, х„х„..., х„) =- )1«-О («) (6) Формула (б) устанавливает связь между разделенной разностью порядка и+! и (и+1)-й производной функции )(х).
2. Оптимальный выбор узлов интерполирования. Величину [а(х) [, входящую в оценку (4), можно минимизировать за счет выбора узлов интерполирования. Задача состоит в том, чтобы подобрать узлы х„с=[а, Ь], /г=0, 1, ..., п, так, чтобы минимизировать величину пах !(х — х,)(х — х,) ...
(х — х„) [. «=1а Л) Эта задача уже рассматривалась в примере 1 из 9 5 гл. 2. Она решается, как мы знаем, с помощью мпогочлена Чебышева а)ам 7'„„(х) = —,„, соз ((п+ 1) агссоз ), (7) причем в качестве узлов интерполирования надо взять корни многочлена (7), т. е. точки х« = — + — соз а+Ь Ь вЂ” а (2Ь+1)л й = О, 1. .. и, (8) 2 2 2(л+ 1) При этом )а ак п1ах )ы(х)] = «м!ам) 2«" ~ и оценка (4) примет вид а)аы ]7(х) — 7.„(х) / = (9) 3. О сходимости интерполяционного процесса. Возникает вопрос, будет ли стремиться к нулю погрешность интерполирования )'(х) — 7.„(х), если число узлов и неограниченно увеличивать. Ответ, вообще говоря, отрицательный.
Сформулируем определение скодимости интерполяционного процесса. Множество точек хь 1=0, 1,..., и, таких, что а<х,<х,«...х. Ь назовем сеткой на отрезке [а, Ь] и обозначим через О„. До сих пор предполагалось, что число узлов интерполяции фиксировано. Переходя к изучению сходнмости интерполяционного процесса, необхо- 134 димо рассмотреть последовательность сеток с возрастающим числом узлов, а именно последовательность О„=[х, ), 4), = [х,, х, ), ..., й„=(х,, х,, ..., х„), ... ел и) а! ьв (л) м) Пусть функция )(х) определена н непрерывна на [а, Ь]. Тогда можно задать последовательность иитерполяционных многочленов Е„[[(х) ], построенных для функции [(х) по ее значениям в узлах сетки 41„.
Говорят, что интерполяционный процесс для функции )(х) сходится в точке х'ев [а, 6], если существует 1пп Е,[7(х')] =7(х'). л- Кроме поточечпой сходимости рассматривается сходимость в различных нормах. Например, равномерная сходимость на отрезке [а, 6] означает, что шах /[(х) — Е„[)(х)]]-э-0 к =[ал1 при п-эоо, Свойство сходнмости или расходнмости ннтерполяцнонного процесса зависит как от выбора последовательности сеток, так и от гладкости функции 1(х). Известны примеры несложных функций, для которых интерполяционный процесс расходится. Так, последовательность интерполяционных многочленов, построенных для непрерывной функции [(х) = ]х~ по У равноотстоящим узлам на отрезке [ — 1, 1], не сходится к функции ]х] ни в одной точке отрезка [ — 1, 1], кроме точек — 1, О, ! (пример С.
Н. Бернштейна, см. [24, с. 519]). На рис. 4 в качестве иллюстрации изображен график многочлена Е,(х) при О(х»1, построенного для функции ]х] по равноотстоящим узлам на отрезке [ — 1, 1]. Более общее утверждение содержится в теореме Фабера (дока- зательство см. в [24, с. 515)): какова бы ни была последовательность сеток Ркс.
4. ГРафкк ввтерполвавокьг„, найдется непрерывная на [а, 6] функция [(х) такая, что последовательность интерполяционных много- членов 1,„[[(х) ] не сходится к 1(х) равномерно на отрезке [а, 6]. Для заданной непрерывной функции [(х) можно добиться сходимости за счет выбора расположения узлов интерполяции. Справедлива теорем а Марцинкевича (см. [24, с. 519]): если [(х) непрерывна на [а, Ь], то найдется такая последовательность 135 сеток, для которой соответствующий интерполяционный процесс сходится равномерно на [а, Ь!.
Заметим, что построить такие сетки чрезвычайно сложно и, кроме того, для каждой функции требуется своя сетка. В практике вычислений избегают пользоваться ннтерполяцнониыми многочлеиами высокой степени. Вместо этого приметшется кусочнополиномиальная интерполяция, пример которой будет рассмотрен в $ 4. 5 3.
Интерполирование с кратными узлами 1. Интерполяциониый миогочлен Эрмита. В предыдущих параграфах предполагалось, что в узлах интерполяции заданы только значения функции [(х). Более общая постановка задачи иптерпо пирования состоит в следующем. В узлах х,~[а, Ь), н=О, 1, ..., тп, среди которых яет совпадающих узлов, заданы значения функции 1(х,) и ее производных [гв(х,) до порядка У,— 1 включительно, 1=1, 2, ..., Л',— 1. Таким образом, в каждой точке х„, н=О, 1, ..., т, известны [(х„), 1'(х„), ..., 1" -"(х„) и, следовательно, всего известно У,+У,+...+У величин.
Требуется построить алгебраический многочлен Н„(х) степени и= = У„+У, +... + У,„— 1, для которого Н,',и (х,) =["'(х,), й=О, 1, ..., тп, 1=0, 1, ..., У,— 1. (1) Многочлен Н„(х), удовлетворяющий условиям (!), называется интерполяционным многочленом Эрмита для функции )(х). Число У, называется кратностью узла х,.
Докажем, что интерполяционный многочлен Эрмита существует и единствен. Условия интерполяции (1) представляют собой систему линейных алгебраических уравнений относительно коэффипиеитов а„а„..., а„многочлена Н„(х) = а, + а,х+... + а„х". Число уравнений этой системы равно числу неизвестных и равно Л',+У,+...+У .
Поэтому достаточно показать, что однородная система Н",,'(х»)=0, я=О, 1, ..., т, 1=0, 1, ..., У» — 1, (2) имеет только тривиальное решение а,=а,=...=а„=0. Группа условий (2) при фиксированном я и 1=0, 1, ..., У,— 1 означает, что число х, является корнем кратности У„многочлена Н„(х). Таким образом, многочлен Н.(х) имеет всего с учетом кратности не менее У,+У,+...+У„=п+1 корня на [а, Ь). Поскольку степень Н„(х) равна и, этот многочлен тождественно равен нулю, следовательно, равны нуеао его коэффициенты и однородная система уравнений (2) имеет единственное решение а,=-а,=...=а„=О. Неоднородная система (1) однозначно разрешима при любых правых частях.
Поскольку значения !иО(х,), й=О, 1, ..., Оп, !=О, 1, ..., Л"» — 1, входят только в правую часть системы (1), коэффициенты сч мно- гочлена Н„(х) выражаются линейно через значения !оО(х»), и этот многочлен можно представить в виде линейной комбинации »О~»» Н„(х) = '~~ '~~~ с», (х) 1" (х»), »=О О=О где с„(х) — многочлены степени и. Ввиду громоздкости выражений для с„(х) мы их не приводим. Получим представление для погрешности интерполирования г„(х) =!(Х) — Н„(х). Для этого рассмотрим, как и в 1 2, вспомогательную функцию д(5) =!(5) — Н„(5) — Кв»(5), (3) где К вЂ” постоянная и Ы (5) = (5 — ХО) "(5 — Х») ' ...
(5 — Х„,) (4) Постоянную К выберем так, чтобы в точке интерполирования х выполнялось условие п(х) =О, т. е. положим К= ! (к) — Н» (х) ОО (Х) Узлы х, являются корнями кратности Л', функции п(5), й= =1, 2, ..., т. Кроме того, точка х~(а, Ь] является корнем у(5). Таким образом, функция д(5) имеет с учетом кратности Ж,+Л1,+... ...+Л'„+ ! =а+2 корня на отрезке (а, Ь]. По теореме Ролла производная и'(5) имеет по крайней мере один нуль между двумя соседними корнями функции д(5). следовательно, гО'(5) имеет не менее гп+1 корня на (а, Ь] в точках, пе совпадающих ни с одной из точек х,, х„..., х„, х, Кроме того, д'(5) имеет в точке х, корень кратности У» — 1, /г=О, 1, ..., т.
Таким образом, и'(5) имеет с учетом кратности не менее (Л'Π— 1)+...+(У.— 1) 1-(гп+1) =ЛАЛО+У,+...+Л'.=и+1 корней на (а, Ь]. Аналогично 5("(5) имеет не менее и корней и т. д. Производная д'"+"(5) по крайней мере один раз обращается в нуль на (а, Ь], т. е. существует точка ~ен(а, Ь], в которой д'"+о(с) =О.
Из (3) имеем к О»о (5) ОО»»О (5) К О»о (5) Так как ы(5) — многочлен степени п+1 со старшим коэффициентом !, имеем ы'"+о(5)=(п+1)! Поэтому из условия й'"Оо($)=О получаем, учитывая выражение для К, следующее представление для погрешности интерполирования: !<»О»О ОО Дх) — Н„ (х) = = — (х — х,) ' (х — х.) ' ... (х — х„,) '". (О) 15+ !)! гвт 2. Пример, Пусть хо(х,<хо — точки, в которых заданы значения ) (х„) =)„1(х,) =1„)'(х,) =~„1(х,) =)г. Требуется построить многочлен третьей степени Н,(х) такой, что Но(хо) =1о Нг (хг)=Тг, Н,(х,) =)гг Но(х,) =~о. (6) Будем искать его в виде Н, (х) = с, (х) г'о + сг (х) г'г + с, (х) г'о + Ьг (х) ~ь где с,(х), с,(х), с,(х), Ь,(х) — многочлены третьей степени.
Ясно, что Н,(х) будет искомым ннтерполяционным многочленом, если, потребовать со(хо)=1 с (.о)=0 с.(.о) =О, Ьг(хо)=0. с,(х,) =О, с,(х,) =1, с,(х,)=0, Ь,(х,) =О, со(хД = О, с,(х,) =О, с,(х,) =1, Ь,(х,) =О, с,(х,)=0, с,(х,) =О, с.,(х,) =О, Ь,(х,) =1. Найдем многочлены третьей степени, удовлетворяющие перечисленным требованиям. Поскольку многочлен с,(х) имеет кратный корень в точке х, и простой корень в точке х„его можно искать в ниде с,(х) =К(х — х,)'(х — х,). Из условия с,(х,) =1 находим 1 К= (хо — х,) (хо — хг) Таким образом, (х — х,)г (х — хо) с, (х) = (хо — х,)г (хо — хо) Аналогично получаем (х — х,) (х — хг)' с,(х) =— (хо — х,) (хо — х,)' Ь, (х) = (х — хо)(х — х,) (х — хо) (хг — хг) (хг — хо) Далее, многочлен с,(х) будем искать в виде сг (х) = (х — хо) (х — хг) (ах+ б), где а н р — постоянные, подлежащие определению.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
