Разработка программы, выполняющей интерполирование методом Ньютона
Содержание
1. Постановка задачи
. Исследование методов решения
.1 Методы интерполяции
.2 Методы нахождения узлов
. Разработка алгоритма
. Исходный код
. Тестирование программы
. Исследование
Выводы
1.
Постановка задачи
Сравнить графики заданной функции f(x) (см. рис. 1) и
интерполяционных полиномов Pn(x) для n = 2, 6, 14 на интервале при двух вариантах выбора узлов:. Равномерно
с шагом . По Чебышеву
Данные: a = 1; b = -1; c =
-1; d = 1.
Использовать формулу Ньютона
Рис. 1. График заданной функции
2.
Исследование методов решения
2.1 Методы
интерполяции
Интерполяция - один из вариантов аппроксимации, иными словами замены
исходной функции другой, близкой функцией, удобной для проведения расчетов.
1. Метод
Лагранжа
Для построения интерполяционных полиномов Лагранжа используют следующие
расчетные формулы, где Ln(x) - полином Лагранжа степени n:
где
уk - значение исходной функции в узле k, k =
0чn;
;
где
- полином степени n;
;
где
xi- узлы, на которых строится интерполяционный полином, i =
0чn.(x) может иметь степень не больше n.
2. Метод
Ньютона
Интерполяционная формула Ньютона, используемая в дальнейшем в программе:
где
N(x)
может иметь степень не больше n.
2.2 Методы
нахождения узлов
. С
равномерным распределением
Для нахождения узлов с равномерным шагом используется формула:
где i - номер узла, xi - i-ый узел, с - начальная точка
интерполяции, d - конечная точка интерполяции, n -общее количество выбираемых
узлов. i от 1 до n+1
2. По
Чебышёву
Для нахождения узлов Чебышева используется формула:
где i - номер узла, xi - 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.
Исследование
) Исследование зависимости погрешности интерполирования в зависимости от
количества узлов:
Из графиков:
Количество узлов
|
Максимальная погрешность узлов Чебышева
|
Максимальная погрешность равномерных узлов
|
2
|
0.3
|
0.25
|
6
|
0.015
|
0.035
|
14
|
0.22*10-2
|
0.22
|
51
|
-820000
|
8200000
|
В результате тестирования можно сделать вывод, что при 5 и 13 узлах
интерполирования метод Чебышева даёт наиболее точный результат, чем метод
равномерных узлов (погрешность меньше).
) Исследование сходимости метода интерполяции.
Теоретически для чебышевской сетки сходимость (при числе узлов n стремящемся к бесконечности) имеет
место быть. А при равномерной сетке сходимость может отсутствовать.
При увеличении числа узлов для метода Чебышева при количестве узлов,
стремящемся к бесконечности, погрешность стремится к нулю, при этом, при
достаточно большом количестве узлов погрешность больше, чем при маленьком числе
узлов. А для равномерных узлов погрешность стремится к бесконечности. Что
теоретически подтверждается для равномерных узлов и не очень для Чебышева.
Выводы
В ходе работы была реализована программа, выполняющая интерполирование методом
Ньютона.
Также была проведена отладка и тестирование программы, исследованы
результаты тестирования, а именно зависимость погрешности интерполяционного
полинома от количества узлов интерполирования и от способа выбора узлов.
По результатам тестирования можно сделать вывод о большей точности метода
Чебышева, так как при большом количестве узлов, точность метода возрастает.