Часть 1: Интерполяция (стр. 2 )

i =

где i – номер узла, xi – i-ый узел, с – начальная точка интерполяции, d – конечная точка интерполяции, n –общее количество выбираемых узлов.

3.2.2 По Чебышеву

Для нахождения узлов Чебышева используется формула:

i =

где i – номер узла, xi – i-ый узел, c – начальная точка интерполяции, d – конечная точка интерполяции, n –общее количество выбираемых узлов.

Пусть число узлов (n+1) фиксировано и о функции y(x) известно лишь, что она имеет (n+1) ограниченных производных. Тогда единственным средством уменьшить погрешность является выбор узлов сетки. Этот выбор должен удовлетворять решению характерной задачи на минимакс

Из всех возможных стандартных полиномов ωn+1(x) путем выбора корней нужно подобрать такой, чтобы модуль его максимального значения на заданном интервале был минимальным. Эта задача, известная как задача о построении полинома, наименее уклоняющегося от нуля, была решена (по другому поводу) , который доказал, что такими свойствами обладают нормированные полиномы, известные под его именем.

Таким образом, наилучшей является сетка, узлы которой совпадают с корнями нормированного полинома Чебышева степени (n+1) на интервале [a, b].

Свойства полиномов Чебышева.

1. Полином Чебышева n – ой степени Tn(t)=cos(n*arccos(t)) (t∈[-1,1]) можно рассчитать по рекурсивным формулам T0(t)=1; T1(t)=t;

Tn(t)=2tn-1(t)-Tn-2(t); n=2,3,… .

2. На отрезке [-1,1] полином Tn(t) имеет n вещественных корней

3. Коэффициент при tn равен 2n-1.

4. При n≥0

Если n≥1, то этот максимум достигается ровно в n+1 точках, которые находятся по формуле:

При этом Tn(tm)=(-1)m, т. е. максимумы и минимумы многочленов Чебышева чередуются.

Предположим, интерполяционный полином строится на отрезке [-1,1] . Тогда для минимизации погрешности нужно выбрать узлы, совпадающие с корнями полинома Чебышева. То есть:

Произвольный отрезок [a, b] приводится к стандартному [-1,1] заменой переменных ;

При этом оказывается:

ti - корни Чебышевского полинома Tn+1;

,

Таким образом, выбор Чебышевских узлов приводит к следующему результату

3.  Разработка алгоритма

В данной работе согласно заданию необходимо использовать метод Лагранжа.

1)  Исходные данные;

1.1)  построить исходную функцию;

1.2)  построить сеточную функцию;

1)  построить Ln(x) – интерполяционный полином Лагранжа;

2)  Вывод графиков.

4.  Разработка программы

5.1 Структура, исходные функции

Основные функции и переменные, использованные в реализованной программе:

1.  n-количество узлов;

2.  plot(x, y) – построение графиков;

3.  Команды subplot(mnp) или subplot(m, n, p), где mnp - 3 цифры, производит разбивку графического окна на несколько подокон, создавая при этом новые объекты axes; значение m указывает, на сколько частей разбивается окно по горизонтали, n - по вертикали, а p - номер подокна, куда будет выводиться очередной график. Эти же команды могут использоваться для перехода от одного подокна к другому;

4.  grid on - rоманда grid on наносит координатную сетку на текущие оси;

5.  hold on - Команда hold on включает режим сохранения текущего графика и свойств объекта axes, так что последующие команды приведут к добавлению новых графиков в графическом окне.

5.2 Листинг

%начальные условия

a=3;

b=1;

c=-4;

d=3;

%количество узлов

n=20;

%узлы при равномерном выборе и при выборе методом чебышева

for i=1:n+1

x(i)=c+(d-c)*(i-1)/n;%равномерные узлы

%чебышевские узлы

end

y=linkus(x, c,d, a,b);

%Равномерный случай

% Реализация формулы Лагранжа Ln(x)

m=200; % число отрезков при построении Ln(x)

% строим массив значений аргумента Ln(x)

z=c:(d-c)/m:d; % Ln(z)

for j=1:m+1

L(j)=0;

for k=1:n+1

P=1;

for i=1:n+1

if k~=i

P=P*(z(j)-x(i))/(x(k)-x(i));

end

end

L(j)=L(j)+P*y(k);

end

end

%plot (z, linkus (z, c, d, a, b), 'r');

%xlabel('x');

%ylabel('y');

%title('Исходная функция')

%grid on

% построение графиков

subplot (2, 1, 1);

plot(x, y, ' * ', 'MarkerSize', 8)

grid on; % маркеры

hold on; % несколько графиков на одних осях

xlabel('x');

ylabel('y');

plot (z, L, ' r '); % интерполяционный полином Pn(x), r-red

xlabel('x');

ylabel('y');

plot (z, linkus (z, c, d, a, b), 'b'); % исходная функция

subplot (2, 1, 2);

plot (z, L-linkus(z, c, d, a, b)); % погрешность

max(L-linkus(z, c, d, a, b))

function y=linkus(x, c,d, a,b)

for i=1:length(x)

if x(i)<0

y(i)=3/2;

else if x(i)>=0

y(i)=-1/3*x(i)+1.5;

end

end

end

5.  Тестирование

Целью тестирования является подтверждение того, что написанная программа работает правильно. Для того, чтобы доказать, что программа функционирует так, как положено, необходимо, чтобы соблюдалось выполнение тестового критерия. В этой задаче тестовым критерием является следующее:

Исходная функция и полученный полином должны совпадать в узлах интерполирования при любом количестве узлов.

Для проверки выполнения тестового критерия рассмотрим несколько случаев с различными узлами: n=2, 6, 14, 20.

n=2
Равномерные узлы	Узлы по Чебышеву

n=6
Равномерные узлы	Узлы по Чебышеву

n=14
Равномерные узлы	Узлы по Чебышеву

n=20
Равномерные узлы	Узлы по Чебышеву

Из графиков видно, что полином и сама исходная функция совпадают в узлах интерполирования. Это означает, что выполнен тестовый критерий, что подтверждает правильность проведенных вычислений.

6.  Исследование

6.1  Программа исследования

1) Исследование зависимости погрешности интерполирования от количества узлов;

2) Исследование сходимости метода интерполяции.

7.2 Методика исследования

1) Необходимо выявить зависимость погрешности от количества узлов. Для этого необходимо исследовать максимальную погрешность для разного количества узлов, как при равномерном распределении, так и при выборе узлов по Чебышеву, после чего сравнить полученные результаты;

2) Необходимо исследовать сходимость метода интерполяции. Для этого нужно заметить, как изменяется погрешность при большом количестве узлов, после чего отметить стремиться ли она к бесконечности, что будет означать сходимость метода, либо же погрешность стремиться к нулю, что означает обратное.

7.3 Теоретически ожидаемый результат

Теоретически выбор в качестве узлов интерполирования корней полинома Чебышева является наилучшим из данных двух. На графиках должна прослеживаться ситуация, когда при интерполяции с равноотстоящими узлами ошибка интерполяции больше на краях промежутка, а при интерполяции с чебышевскими узлами ошибка более равномерно распределена на интервале интерполирования.

Исследуя сходимость метода интерполяции, будем говорить, что при заданной стратегии выбора узлов метод интерполяции сходится, если ΔPn = при n.

При n→∞ в случае использования чебышевской сетки ΔPn→0 для равномерной сетки в аналогичных условиях ΔPn→∞.

Рассмотренная выше ситуация обобщается следующими теоремами:

Теорема 1. Какова бы не была стратегия выбора узлов, найдется непрерывная на интервале [a, b] функция такая, что метод интерполяции расходится, то есть

En(y)→∞ при n→∞.

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

Теорема 2. Пусть в качестве узлов интерполяции выбирают чебышевские узлы. Тогда для любой функции, обладающей ограниченными производными на [a, b], метод интерполяции сходится.