Глава 2. ИНТЕРПОЛИРОВАНИЕ И ЭКСТРАПОЛИРОВАНИЕ ФУНКЦИЙ

Предположим, что задано некоторое упо­ря­до­чен­­­­­ное множество вещественных абcцисс х1, х2, ..., хn и свя­зан­ное с ним множество вещественных ор­ди­­нат у1, у2, ..., уn. Пусть х1< х2< ...< хn и каждое уi есть некоторое ве­щес­т­венное число, отвечающее хi, которое определяется ма­тематически или в результате каких-либо на­блю­де­ний (рис. 2.1). Точ­ки (xi,yi) называются узлами ин­тер­поляции. Кривая, которая точно проходит через эти уз­лы, называется интерполяционной кривой.

При решении задач на ЭВМ достаточно час­то воз­ни­кает обратная задача, т.е. необходимо по­до­брать не­ко­торую простую функцию, кото­рая, с од­ной стороны, име­ла бы в известных точ­ках за­дан­ные значения, а с дру­гой — вы­чис­лялась бы бы­стрee и проще исходной.

Исходя из изложенного можно сфор­му­ли­ро­вать (не строго) следующие определения. Задача одно­мер­­­ной ин­тер­­­по­ля­ции за­клю­ча­ет­ся в по­­строении та­­кой не­пре­рыв­ной функ­ции f, при которой f(хi) º уi для всех хi, т.е. функ­ция f обя­за­тельно должна про­хо­дить абсолютно точ­но че­­рез за­дан­ные узлы ин­тер­поляции. Однако при этом f(xk) долж­на при­нимать "ра­зумные" зна­че­ния для всех xk, ле­жа­­щих между за­данными точ­ка­ми хi. Кро­­ме того, на ин­тер­­по­ли­ру­ющую функ­цию на­кла­ды­ва­ет­ся еще ряд оче­вид­ных ог­ра­ни­че­ний: не иметь особых точек на ин­тер­ва­ле ин­­тер­по­лирования; быть дос­таточно глад­кой; иметь не­­об­ходимое ко­ли­­­чест­­во про­из­вод­ных и пр. Если функ­ция определена и не­пре­рыв­на на [y1, y2], ее ин­­тер­по­ля­ци­­онные узлы рас­по­ложены на [х1, х2], а точка x Ï [х1, х2] или f(x) Ï [y1, y2], то тогда говорят о задаче экст­ра­по­ли­ро­ва­ния функции.

Таким образом, задачи интерполирования и экст­ра­по­лирования возникают в следующих случаях:

  1. если решаются прогнозные задачи (экстра­по­ли­ро­­ва­ние);

  2. практически всегда при решении эко­но­ми­чес­ких за­дач (интерполирование и экстра­по­ли­ро­ва­ние);

  3. при обработке данных, полученных в экспе­ри­мен­­тах (ин­терполирование);

  4. всегда при решении задач на ЭВМ (интер­по­ли­ро­ва­ние и экстра­по­ли­ро­ва­ние);

  5. при задании функции графиком или таблицей (ин­тер­­­по­ли­ро­вание и экстра­по­ли­ро­ва­ние);

  6. во всех остальных не описанных здесь случаях, ес­ли это необходимо.

§ 1. ПОСТРОЕНИЕ ИНТЕРПОЛЯЦИОННОГО ПОЛИНОМА ЛАГРАНЖА ПО ЗАДАННЫМ ЗНАЧЕНИЯМ ФУНКЦИИ

Пусть теперь функция f(x) известна лишь в х1, х2, ..., хn уз­лах некоторой сетки. Попытаемся по­стро­ить та­кую дру­гую функцию j(х; a), которая пол­нос­тью сов­па­­да­ла бы с за­­данной f(x) в этих узлах, т.е. j(х; a) = j(х, а1, а2, ..., ат) º ºf(xк). Тогда из по­след­не­го равенства мож­но будет опре­де­лить компоненты a. При k £ т, а в част­ном случае k = т, ком­поненты a определяются из ре­шения системы

, (*)

которая в указанных случаях имеет единственное ре­ше­ние, если ее главный определитель отличен от ну­ля:

.

Система функций, удовлетворяющая условию (*), является Чебышевской [Бахвалов, 1973а].

Одним из самых важных классов среди ин­тер­по­ли­ру­­ю­щих функций является множество ал­геб­ра­и­чес­ких по­линомов вида

,

где аi - некоторые неизвестные коэффициенты. Для то­го что­бы их определить однозначно, не­об­хо­ди­мо иметь n+1 точек для построения системы из n ли­нейных урав­не­ний относительно аi:

, (j = 0, 1, ..., N+1).

При этом потребуем, чтобы построенный по­ли­ном в заданных узлах хi О {Х} в точности сов­па­дал со зна­че­ни­ями f(хi) в указанных точках. Если сре­ди множества хi нет совпадающих, тогда сис­те­ма ли­ней­ных урав­не­ний, полученная относительно аi,

определена, имеет решение и это ре­шение един­ствен­ное. Заметим, что главный опре­де­литель сис­те­мы - это оп­ре­де­литель Ван­дер­мон­да:

,

который при вы­полнении названных ус­­ло­вий всегда отличен от 0. Значит система имеет решение и это ре­ше­ние будет един­ствен­ное. Очевидно, что решением сис­те­мы будет по­ли­ном n-й степени, который называют по­ли­номом Ла­гран­жа и за­пи­сы­ва­ют

. (2.1)

Важно отметить, что существует один и только один полином степени меньше n, который ин­тер­по­ли­ру­ет за­данные n + 1 точки. При ис­поль­зо­ва­нии всего из­вест­но­го набора точек ин­тер­по­ли­ру­ю­щий по­ли­­ном на­­зывают гло­­баль­ным интер­по­ли­ру­ю­­щим по­­ли­но­мом. Од­нако по те­о­ре­ме Фа­бера при специальном расположении узлов ин­тер­по­ля­ции n всегда можно найти такой полином Рn, не­пре­рыв­ный на за­дан­ном отрезке [х0, хn], ко­то­рый не сходится к f, несмотря на то, что Рn(хi) º уi . Поэтому на практике редко поль­зуются гло­бальным ин­тер­по­ли­ру­ю­щим по­ли­­но­мом, за­ме­няя его полиномом степени не вы­ше 5. Тог­­да го­во­рят о скользящей интерполяции.

Процедура-функция L вы­пол­няет интерполиро­ва­ние по заданным зна­че­ни­­ям х и у. Следует от­ме­тить, что ee эф­­фек­тивно использовать, если ко­ли­чес­т­­во точек не пре­вышает 10, в противном случае не­об­­ходимо при­­менять интерполяцию сплайнами (для умень­­ше­ния по­греш­ности интерполирования).

Формальные параметры про­цедуры. Вход­ные: b (тип real) - точка на оси Ох, для ко­то­рой ищутся значение функ­­ции; n (тип integer) - ко­ли­чество точек, по которым стро­­ится ин­тер­по­ли­ру­­ющий полином. Степень поли­но­ма долж­на быть на единицу меньше n; x, y (тип real) - мас­­­сивы, в которых находятся за­дан­ные зна­чения то­чек. Выходные: L (тип real) - зна­че­ние функции в точ­ке b.

function L ( b : real; n : integer;

x, y : mas ) : real;

var sum, pr : real; i, j : integer;

(* функция возвращает значение "у" в заданной

точке "В", если известны массивы "Х" И "Y" *)

begin

sum := 0.0;

for j:=1 to n do

вegin

pr := 1.0;

for i := 1 to n do

if i<>j тhen

pr:=pr*(b-x[i])/ (x[j]-x[i]);

sum := sum + y[j] * pr;

end;

L := sum;

end.

При большом количестве точек n могут ока­зать­ся ре­ша­ющими ошибки, связанные с округлением при вы­числении высших степеней х, что приведет к рас­хож­де­нию решения. Кроме то­го, ошибки ок­руг­ле­ния на­кап­ли­ваются на каждом очередном шаге, по­э­тому оценка ошибки ин­тер­по­ли­ро­ва­ния должна обя­зательно вы­чис­лят­ь­ся в каждом кон­крет­ном слу­чае на каждом рас­чет­ном шаге.

Один из возможных способов оценки ошибки при ин­терполировании заключается в следую­щем. Во-пер­вых, пред­полагают, что заданные чис­ла уi являются в дейст­ви­тель­ности значениями не­­ко­то­рой функции f(хi). Во-вторых, что f(хi) имеет n +1 не­пре­рыв­ную про­из­вод­ную для всех хi. В-третьих, что Pn - един­ственный по­ли­ном сте­пе­ни < n, ин­тер­по­ли­ру­ю­щий заданные точки {(хi , уi)}. Тогда мож­­но до­ка­зать, что для любого дей­стви­тель­ного хi вы­пол­ня­ет­ся

,

где x - некоторая неизвестная точка на ин­тер­ва­ле, оп­­ре­де­ля­емом точками х0, х1, ..., хn и хn+1. Когда из­вест­­ны гра­ни­цы для f(х), эта разность дает оцен­ку ошибки.

Приводимые результаты были получены на пер­со­наль­ном компьютере IBM386 DX2 фир­мы “R-Style”. Для под­твер­ждения корректности про­це­­дуры L бы­ли ис­поль­зо­ва­ны два набора зна­­че­ний Х и Y для не­рав­но­от­сто­ящих (ва­ри­­ант А) и рав­­но­от­сто­я­щих (ва­ри­ант Б) уз­лов. Ре­зуль­таты вы­­числений и исходные дан­ные при­ведены в табл. 2.1.

Таблица 2.1

Вариант А

Вариант Б

Параметр

i

Х

Y

X

Y

1

0.11

9.0

0.1

2.0

Исходные

2

0.15

6.6

0.2

4.0

данные

3

0.21

4.7

0.3

5.0

4

0.29

3.4

0.4

5.2

5

0.35

2.7

0.5

3.8

6

0.40

2.4

0.6

1.5

Заданная точка

0.263

?

0.253

?

55

Соседние файлы в папке GLAVA2~1