Разработка программы, выполняющей интерполирование методом Ньютона

1. Постановка задачи

2. Исследование методов решения

2.1 Методы интерполяции

2.2 Методы нахождения узлов

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

4. Исходный код

5. Тестирование программы

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

Выводы

1. Постановка задачи

Сравнить графики заданной функции f (x) (см. рис. 1) и интерполяционных полиномов P_n(x) для n = 2, 6, 14 на интервале при двух вариантах выбора узлов:

a. Равномерно с шагом

b. По Чебышеву

Данные: a = 1; b = -1; c = -1; d = 1.

Использовать формулу Ньютона

Рис. 1. График заданной функции

2. Исследование методов решения

2.1 Методы интерполяции

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

1. Метод Лагранжа

Для построения интерполяционных полиномов Лагранжа используют следующие расчетные формулы, где L_n(x) — полином Лагранжа степени n:

где у_k — значение исходной функции в узле k, k = 0чn;

;

где — полином степени n;

;

где x_i— узлы, на которых строится интерполяционный полином, i = 0чn.

L (x) может иметь степень не больше n.

2. Метод Ньютона

Интерполяционная формула Ньютона, используемая в дальнейшем в программе:

где

N (x) может иметь степень не больше n.

2.2 Методы нахождения узлов

1. С равномерным распределением

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

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

2. По Чебышёву

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

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

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

В данной работе мы будет использовать метод Ньютона.

1) Дано:

2) Построение заданной функции посредством matlab

3) Формирование массива узлов через равномерный шаг

4) Нахождение соответствующих значений функции для узлов

5) Расчет значений полинома Ньютона в узлах через равномерный шаг

6) Построение графика функции для равномерного шага

7) Построение графика погрешности между функцией и полиномом

8) Формирование массива узлов Чебышева

9) Расчет значений функции в узлах Чебышева

10) Расчет полинома Ньютона в узлах Чебышева

11) Построение графика функции для узлов Чебышева

12) Построение графика погрешности между функцией и полиномом

13) Вывод полученных графиков на экран

Описание функций программы:

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

r = raznost (x, y) — функция расчета разделённых разностей для полинома Ньютона

newton (x, y, xn) — функция расчета полинома Ньютона

y = ff (x, c, d, a, b) — построение заданной функции

xch — расчет узлов Чебышева

xrav — расчет равномерных узлов

ych — значения в узлах Чебышева

yrav — значения соответствующие равномерным узлам

n — количество узлов

plot (x, y) — построение графика

subplot (1,2,1) — подграфик номер один (из двух в окне)

`*' - отмечаем звездочками узлы полинома

pogr = yu1- yravn — погрешность метода равномерных узлов

pogr = yu1-ychn — погрешность метода Чебышева

4. Исходный код

интерполяционный полином ньютон график

function kursovaya1

a = 1;

b = -1;

c = -1;

d = 1;% начальные условия

n = 35;% количество узлов

s = 50;

for i = 1: s + 1

z (i) = c + (i — 1) * (d — c)/s ;% z (i) = c + (i — 1) * (d — c)/s;% абсциссы

end

yu1 = ff (z, c, d, a, b);% ординаты

for i = 1: n + 1% цикл

xrav (i) = c + (d — c) * (i — 1)/n;% 3) узлы посчитанные методом равномерного шага

end

yrav = ff (xrav, c, d, a, b);% 4) значения узлов равномерного шага

for k = 1: length (z)

yravn (k) = newton (xrav, yrav, z (k));% 5) значения многочлена Ньютона в узлах

end

% 6) график 1

figure (1);

subplot (1, 2, 1);% подграфик

plot (z, yu1);

grid on;

hold on;% построение исходной функции

plot (xrav, yrav, '-о');

grid on;

title ('Равномерный Ньютон');hold on;

pogr = yu1 — yravn;% погрешность равномерных узлов

subplot (1, 2, 2)% подграфик

plot (z, pogr, '-о');

grid on;

title ('Погрешность');% 7) погрешность между функцией и полиномом

% 8) переходим к методу Чебышева

for i = 1: n + 1

xch (i) = (c + d)/2 + ((d — c)/2) * cos (((2 * i — 1) * pi)/(2 * (n + 1)));% узлы посчитанные методом Чебышева

end

ych = ff (xch, c, d, a, b);% 9) значения узлов для Чебышева

% 11) график 2

figure (2);

subplot (1, 2, 1)%подграфик

plot (z, yu1);

grid on;

hold on;%построение исходной функции

for k = 1: length (z)

ychn (k) = newton (xch, ych, z (k));% 10) значения многочлена Ньютона в узлах Чебышева

end

grid on; title ('Ньютон по Чебышёву');hold on;

pogr = yu1 — ychn;% погрешность метода Чебышева

plot (xch, ych, '-о');

hold on;

grid on;

subplot (1, 2, 2)% подграфик

plot (z, pogr, '-о');

grid on;

title ('Погрешность');% 12) погрешность между функцией и полиномом

% исходная функция

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

for i = 1: length (x);

if (x (i) >= c)

if (x (i) < 0)

y (i) = - x (i)^2;

end;

end

if (x (i) >= 0)

if (x (i) <= d)

y (i) = x (i)^2;

end;

end;

end

% разделённые разности для Ньютона

function r = raznost (x, y)

p = 1;r = 0;

for i = 1: length (x);

for j = 1: length (x);

if i ≅ j

p = p * (1/(x (i) — x (j)));

end;

end

r = r + p * y (i);p = 1;

end

% Ньютон

function N = newton (x, y, xn)

N = 0;w = 1;

for i = 1: length (x);

N = N + raznost (x (1:i), y (1:i)) * w;

w = 1;

for j = 1: i

w = w * (xn — x (j));

end;

end

5. Тестирование программы

Проведём отладку и тестирования для следующего количества узлов интерполирования:

n = 1,5,13.

n = 1

n = 5

n = 13

Возьмём количество узлов n = 51, чтобы понять, как ведёт себя функция и ее погрешность при больших количествах узлов интерполирования.

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

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

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

Из графиков:

В результате тестирования можно сделать вывод, что при 5 и 13 узлах интерполирования метод Чебышева даёт наиболее точный результат, чем метод равномерных узлов (погрешность меньше).

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

Теоретически для чебышевской сетки сходимость (при числе узлов n стремящемся к бесконечности) имеет место быть. А при равномерной сетке сходимость может отсутствовать.

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

Выводы

В ходе работы была реализована программа, выполняющая интерполирование методом Ньютона.

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

По результатам тестирования можно сделать вывод о большей точности метода Чебышева, так как при большом количестве узлов, точность метода возрастает.