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

Содержание

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

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

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

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

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

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

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

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

Выводы

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

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

Данные: 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.(x) может иметь степень не больше n.

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

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

где

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

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

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

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

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

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

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

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

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

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

) Дано:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

y = ff(x,c,d,a,b) - построение заданной функции- расчет узлов Чебышеваrav - расчет равномерных узлов

ych - значения в узлах Чебышеваav - значения соответствующие равномерным узлам- количество узлов

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

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

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

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

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

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

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

function kursovaya1

a = 1;

b = -1;

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

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

i = 1:s + 1(i) = c + (i - 1) * (d - c)/s ;% z(i) = c + (i - 1) * (d - c)/s;% абсциссы= ff(z, c, d, a, b);% ординаты

for i = 1:n + 1% цикл(i) = c + (d - c) * (i - 1)/n;% 3) узлы посчитанные методом равномерного шага= ff(xrav, c, d, a, b);% 4) значения узлов равномерного шагаk = 1:length(z)(k) = newton(xrav, yrav, z(k));% 5) значения многочлена Ньютона в узлах

end

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

plot(xrav, yrav, '-о');on;('Равномерный Ньютон');hold on;

pogr = yu1 - yravn;% погрешность равномерных узлов(1, 2, 2)% подграфик(z, pogr, '-о');on;('Погрешность');% 7) погрешность между функцией и полиномом

% 8) переходим к методу Чебышеваi = 1:n + 1(i) = (c + d)/2 + ((d - c)/2) * cos(((2 * i - 1) * pi)/(2 * (n + 1)));% узлы посчитанные методом Чебышева= ff(xch, c, d, a, b);% 9) значения узлов для Чебышева

% 11) график 2(2);(1, 2, 1)%подграфик(z, yu1);on;on;%построение исходной функцииk = 1:length(z)(k) = newton(xch, ych, z(k));% 10) значения многочлена Ньютона в узлах Чебышева

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

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

plot(xch, ych, '-о');on;on;(1, 2, 2)% подграфик(z, pogr, '-о');

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

% исходная функцияy = ff(x, c, d, a, b)i = 1:length(x);(x(i) >= c)(x(i) < 0)(i) = - x(i)^2;;(x(i) >= 0)(x(i) <= d)(i) = x(i)^2;;

end;

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

function r = raznost(x, y)= 1;r = 0;i = 1:length(x);j = 1:length(x);i ~= j= p * (1/(x(i) - x(j)));;= r + p * y(i);p = 1;

% НьютонN = newton(x, y, xn)= 0;w = 1;i = 1:length(x);= N + raznost(x(1:i), y(1:i)) * w;= 1;j = 1:i= w * (xn - x(j));

end;

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

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

n = 1,5,13.

n = 1

n = 5

n = 13

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

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

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

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

Из графиков:

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

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

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

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

Выводы

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

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

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