Буслов, Яковлев - Введение в численный анализ (947494), страница 3
Текст из файла (страница 3)
Задача интерполяции состоит в отыскании (построении) интерполирующей функции (т.е. принимаюшей в заданных узлах интерполяции х, заданные значения г, ) н принадлежащей заданному классу функций. Разумеется задача интерполяции может иметь нли не иметь решение (и при том не единственное), все зависит от "заданного класса функций".
Необходимо выяснить условия, при которых задача интерполяции была бы корректно поставлена. Один из способов интерполяции состоит в том, что интерполирующая функция ищется в виде линейной комбинации некоторых конкретных функций. Такая интерполяция называется линейной. Только линейные интерполяции мы и будем рассматривать в дальнейшем. 2.1.2 хХебышевские системы функций Пусть (у,(х));~ о — некоторый набор функций иа (а,б), скажем ~р,(х) Е С!юе! .
Рассмотрим линейную оболочку Н = 1( у,(х), она по определению состоит из функций представимых в виде ~ асу,(х), где а, — некоторые числа. =о .=о Будем искать решение задачи интерполяции в классе функций, принадлежащих Н . Можно считать, что у,(х) — линейно независимые функции (в противном случае, если задача интерполяции разрешима, то ее решение заведомо не единственно). Однако одного этого ограничения для однозначной разрешимости недостаточно.
х, О 1 Примеры. Пусть задана таблица 13 1. Возьмем в качестве Н оболочку сииусоидальных функций Н = ~/ зш(ялх). о=о Всякая функция нз Н представляется в виде г(х) = ) аь шп я)ех и, следовательно, для нее у'(0) = О, у(1) = 0 э=о и она не удовлетворяет второму условию таблицы: у (1) = 0 ~ 1, таким образом решений нет. 2. Пусть теперь Н вЂ” линейная оболочка степенных функций Н = у' х~ н гг' > 2, скажем Х = 2 . Тогда /=о 1 (х) = ао -г агх+ агх Поскольку у(0) = О, то ао = О. Далее, у(1) = 1 и значит аг + аг = 1, то есть решений бесконечно много.
Нетрудно вцдеть. что во втором примере для существования и единственности решения можно использовать в качестве Н функции вида во+ аьх . То есть, для единственности решения задачи интерполяции естественно исполье зовать следующее ограничение: число узлов должно равняться размерности интерполирующего пространства. Однако, как показывает первый пример, для разрешимости задачи интерполяции и этого ограничения недостаточно. Выясним условия, при которых задача интерполяции разрешима однозначно. Задача линейной интерполяции выглядит следующим образом: пусть у б Н, где Н вЂ” линейная оболочка некоторых функций егг(х), г = О, 1,2,, Х, необходимо удовлетворить системе равенств У(хг) = У, = ~~~ аеуге(х,) .
То есть, требуется найти набор чисел (аь)е о таких, чтобы функция у(х) удовлетворяла заданной таблице (х„у,) . Слово "линейнаяов формулировке означает, что функции ~р, входят в (1) линейным образом (или, что то же самое, функция у принадлежит линейной оболочке функций р,). Обозначим матрицу (угь(х,)) через Ф.
Пусть г" — вектор с компонентами у,, и а = (ао, ам..., ал)т, тогда система (1) эквивалентна задаче Фта=г". Если с)ее Ф ф О, то эта система разрешима единственным образом. Определение. Система функций (уг,), для которой с1ех Ф ~ О, называется еебмшевской. Заметим, что любая чебышевская система функций автоматически линейно независима. Важным примером чебышевских систем являкпся многочлены. 2.1.3 Интерполяция многочленами Особое место мпогочленов Выделенность многочленов (полиномов) обусловлена целым рядом обстоятельств. 1) Полиномы р„(х) легко вычислять; 2) Множество полиномов плотно в пространстве непрерывных функций С~„Н, в силу теоремы Вейерштрасса, формулировку которой мы приведем.
Теорема Вейерштрасса. Длл любой ебункции у" 0 Се, и и длл любого е > 0 существует такое п и такой поливом р„(х), с)еб р (х) = п, гто 'О)' — р Цс,. „, < е. 3) Полиномы являются чебышевской системой для любой системы несовпэдаюшнх узлов. В самом деле, пусть (гг,(х))л о = (1, х, хг, ..., х~), тогда с)ее Ф совпадает с определителем Вандермоида 1 хо хо . Хо 2 л! х хг! ... Тг~ гз(хо, ты..., хи) = = П (хй х!ч) л!>й>ш>0 1 хлг хк ...
х';„ который, очевидно, не равен нулю если хй ~ х при Ь ф т. Убедимся в справедливости представления определителя Вандермонда по инггукции 16). Действительно, пусть дгйя индекса равного 1!' — 1 последняя формула верна. Вычтем в определителе !.'2(хо! хг,..., Хн) из каждого столбца предшествующий, умноженный на хо, тогда О О 1 О 1 х! — хо х! — Хгхо .. х, — х, хо 2 М Л вЂ” ! гз(хо!, Хл ) = 1 хл — хо хгя — хл хо .. Тл — тлг ха н л — ! 2 И-! х! х! н — ! т! . Тг Х2 = (х! — Хо)(хг — хо)...
(Хн — хо) 2 гг- ! 1 хл хк ... Хлг = (х! — хо)(х! — хо) . (тл — хо) П (хй — х ) = П (хй — х ). л!>й> >! л!>й»о Таким образом, задача интерполяции для таблицы (х„,г",)~о разрешима единственным образом в линейной оболочке степенных функций Н = ~/ х . Возникает вопрос: как строить интерполяцнонный полипом рн(х), ведь есть свой й=о бода выбора базиса в Н шш, что то же самое, свобода формы записи. Врать в качестве ггй(х) собственно степени хй зачастую оказывается неудобным.
В частности, например, на отрезке [а,Ь] = (0,1) степенные функции высоких порядков ведут себя весьма схожим образом: степени х' и х' "почти линейно зависимы" (они очень похожи друг на друга) и при этом получается почти вырожденная матрица Ф. Задача нахождения коэффициентов ай при степенях х оказывается плохо обусловленной. Небольшое варьированне входных даных (значений у,) приводит к знайительным изменениям величин ай.
Если же в Н = у' х! выбрать другой базис, то это будет отвечать тому, что вместо .=о определителя Вацдермонда ( с)ей Ф) и самой матрицы Ф, необходимой для отыскания коэффициентов ай в задаче у(хй) = по+ агхй+ агх„+... + алхй~, Ь = О, 1,, гУ, мы будем иметь некоторую другую задачу у(хй) = Ьоро(хй) + Ьйрй(х!) +... +Ьлрл(хй), Ь = О, 1, ..., йг, (2) где рй б Н. Коэффициенты Ьй определяются из равенства 1(х) = ~! Ьйрй(т) = ~~! а т при этом р,(х) = 2 Сшхй, то есть 1(т) =~Ь,~> С,йхй =~ ~ (Ь,С,й) тй =~ ~айх =о й=о й=о г=о или в матричной форме Ст Ь = а 15 Таким образом, если с)есС ф О, то новая задача (2) так же разрешима единственным образом.
Невырожденность С эквивалентна тому, что (рь(х))ь о образуют базис в Н (следствие линейной алгебры). В частности, если полиномы (рэ(х)Д о С Н таковы, что дея рэ = (г, то оии автоматически линейно независимы и образуют базис в Н и, следовательно, задача интерполяции разрешима едииственым образом. Интерполяционный полипом в форме Лагранжа Один из возможных подходов к решению задачи интерполяции многочленамн, состоит в том, чтобы матрица Ф имела по возможности простой вцд. Именно, рассмотрим задачу интерполяции: пусть дана интерполяционная таблица (хю Яь~ о . Требуется найти полипом рэ(х) степени М удовлетворяющий этой таблице.
Введем базис в Н = ~/ х', в котором матрица Ф предс1авляет собой единичную, обозначим его (Еь(х))ь е, то Еэ(х;) = б„; Ф = 1 . и Отсюда рл (х) = ) аешь(х), и к=о ~, =рл(х,) = ~~~ оэбэ(х;) = а, к=о или р(х) = ~ Уэбь(х) . э=о Как построить легранжевы полиномы бэ(х)? Поскольку бь(х,) = О при )ф х, то такой полипом Еь(х) имеет Х корней и следовательно является поливомом степени Дг, Таким образом Сэ(х) = Сэ П (х — х,), причем бь(хь) = 1, хэ поэтому Сь = П „, ', , следовательно ,фь '"' Окончательно, решение задачи интерполяции принимает вид Интерполяционный полином в форме Ньютона Интерполяционный полипом степени Х, проходящий через заданные (%+ 1) точку (х„у,) ~ е единственнен. Однако запись его в форме Лагранжа может для некоторых задач оказаться неудобной.
Это связано с тем обстоятельством, что все Лагреижевы полиномы Еь(х) имеют одну и ту же степень — йг . В частности, если к интерполяционной сетке (хь Я добавлять новые точки, то нельзя воспользоваться ранее построенными лагранжевыми полииомами, и приходится для более высоких степеней их строить заново. Будем репгать задачу интерполяпии выбрав в Н новый базис (Л'ь(х))~~ е . "(.)='"(х)=П(х-х) "=' В том, что это действительно базис в Н легко убедиться, поскольку с)ееЛ'э(х) = к, и тем самым иьютоновы многочлеиы Лг, линейно независимы. Итак, будем искать интерполяциоиный полипом р(х) в виде 16 р(х) = ~аьЛь(х) .
к=о Такое предсшвление и является записью интерполяционного полинома в форме Ньютона. Заметим, что Ага(х,) = О при у ( к . Сами коэффициенты аь находим из системы: р(х,) = Д~, у = О, ..., Х или ао =Хо, ао+ а~(х~ — хо) = Х~ 2, азЛэ(х~) = У ь=о озЛ'э(хл) = Ул к=о Это треугольная система. Из первого уравнения определяется ао, затем, зная ао,из второго уравнения определяем а~,и так далее.
Можно решить ту же задачу и более "элегантно". Введем так называемые разделенные разности. Разделенные разности О-го порядка — это просто значения функции ~; = у(х,) . Разделенные разности более высоких порядков определяются рекурентно: 1 порядка Д~ = у'(х„х,) = —;* — -~-; 2 порядка ума = У'(хо хз, хь) = ~*': — ~~~"- Ьв„щ в„, -Ув,в, й порядка.
(Лодь дз = . е ые разности имеют размерность соответствующ~ Р " д терполяции дается следующим выражением р(х) = ~~~ зош.оьЛэ(х) к=о Чтобы убедиться в справедливости этого представления, рассмотрим разделенные разности интерполяционного поли- нома, р(х), в которых в качестве первого из аргументов выступает сама переменная х, а остальными являются точки интерполяции. Степень этого полинома равна А' . Разность р(х) — р(хо) = р(х) — уо обращается в ноль в точке хо и, следовательно, делится на х — хо Таким образом разделенная разность р о = г~'~ "~*"~, рассматриваемая как функ- ция х, является полиномом степени Ж вЂ” 1.
Аналогично, вторая разделенная разность р,о~ = вгк:-~'- есть полипом по х степени Х вЂ” 2, разделенная разность Х-го порядка р,.ош...л-~ уже не зависит от х и является константой и разности более высокого порядка тождественно равны нулю. Таким образом, р(х) = ро + (х — хе)р*о = ро + (х — хо)(ро~ + (х — х~)р*о~) = ро + (х — хо)ро~ + (х — хо)(х — х~)[рош + (х — хз)р*о~з] = рош.
з П(х — х,) . Осталось заметить, что поскольку в узлах интерполяции х, мгачения интерполяционного полвнома равны табличным значениям у',, топ Зоь.я = рок.я . 17 2.1.4 Погрешность интерполяции Пусть у(х) — некоторая функция и пусть (хс, Я~ о — ннтерполяциоиная таблица, которой эта функция удовлетворяет (то есть 1(х;) = ?1). По этой все интерполяционной сетке можно построить и интерполяцнониый полинам рн(х). Возникает естественный вопрос: насколько различаются межлу собой функция у(х) и полинам рн(х), удовлетворяющие одной и той же таблице? Если никаких свойств гладкости не потребовать от функции У, то и сказать ничего определенного нельзя.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
