This shows you the differences between two versions of the page.
Both sides previous revision Previous revision Next revision | Previous revision Next revision Both sides next revision | ||
courses:computational_mathematics:prac4 [2021/04/22 21:52] andrey.suchkov created |
courses:computational_mathematics:prac4 [2022/05/22 12:36] andrey.suchkov ↷ Links adapted because of a move operation |
||
---|---|---|---|
Line 1: | Line 1: | ||
- | ====== Практическая работа №4: Интерполирование функций ====== | + | ====== Практическая работа №4: Аппроксимация функций ====== |
===== Цель работы ===== | ===== Цель работы ===== | ||
- | Научиться применять интерполирование функции для решения практических задач, овладеть навыками применения интерполяционных формул Лагранжа заданной степени, многочленов Ньютона. Научиться оценивать погрешности интерполяционных формул и работать в программных пакетах с целью проверки полученных результатов. | + | Сформировать навыки и умения решения задачи аппроксимации функции с помощью метода наименьших квадратов (МНК) и дискретного преобразования Фурье (ДПФ); освоить реализацию МНК и ДПФ с помощью математического пакета GNU Octave. |
- | + | ||
- | ===== Основные теоретические положения ===== | + | |
- | Пусть значение $ f(x) $ известно в некоторых точках $ X = \{x_j\}_{j=0}^n $, и необходимо найти $ f(x_i) $: $ x_i \notin X $. Для этих целей, функцию $ f(x) $ приближают функцией $ L_n(x) $: | + | |
- | \[ | + | |
- | L_n(x) = \sum_{k=0}^na_k\varphi_k, | + | |
- | \] | + | |
- | где $ \varphi $ -- произвольный базис, удобный для данной $ f(x) $. Задача интерполяции -- найти обобщённый многочлен. Существует несколько способов нахождения, например, метод Лагранжа. Он даёт готовый интерполяционный многочлен Лагранжа: | + | |
- | \[ | + | |
- | L_n(x) = \sum_{i=0}^nf_i\ell_i(x), | + | |
- | \] | + | |
- | где $ f_i = f(x_i) $ -- значение функции в узле $ x_i $, а | + | |
- | \[ | + | |
- | \ell_i(x) = \prod_{\substack{k=0 \\ k \ne i}}^n\frac{x - x_k}{x_i - x_k} | + | |
- | \] | + | |
- | -- $ i $-ый базисный полином. | + | |
- | + | ||
- | Если узлы, в которых определено значение $ f(x_i) $ являются равноотстоящими, т.е. $ x_i = x_0 + ih $, $ x_0 < x_1 \dots < x_n $, $ i = 1..n $, тогда можно воспользоваться интерполяционным многочленом Ньютона: | + | |
- | \[ | + | |
- | N_n(x) = \sum_{k=0}^{n}\frac{\Delta^kf_0}{k!}\prod_{j=0}^{k}(q - j + 1), | + | |
- | \] | + | |
- | где $ \Delta^kf $ -- конечная разность $ k $-го порядка, $ q = (x - x_0)/h $. | + | |
- | + | ||
- | Многочлен Чебышёва первого рода $ T_n(x) $ характеризуется как многочлен степени $ n $ со старшим коэффициентом $ 2^{n-1} $, который меньше всего отклоняется от нуля на отрезке $ [-1, 1] $ | + | |
- | \[ | + | |
- | T_n(x) = \cos(n\arccos x). | + | |
- | \] | + | |
- | Для натурального $ n $ узлы на промежутке $ x \in [-1, 1] $ задаются формулой: | + | |
- | \[ | + | |
- | x_k = \cos\left(\pi\frac{2k-1}{2n}\right),\,k = 1..n. | + | |
- | \] | + | |
- | Это корни многочлена Чебышёва первого рода степени $ n $. | + | |
- | + | ||
- | Для получения узлов на произвольном отрезке $ [a, b] $, можно применить следующую формулу: | + | |
- | \[ | + | |
- | x_k = \frac{a + b}2 + \frac{b - a}2\cos\left(\pi\frac{2k-1}{2n}\right),\,k = 1..n. | + | |
- | \] | + | |
- | После нахождения интерполяционного многочлена, необходимо вычислить и оценить его погрешность. Должно выполнятся следующее неравенство: | + | |
- | \[ | + | |
- | \max\limits_{x \in [a, b]}|R_n(x)| \leqslant \frac{M_{n+1}}{(n+1)!}\max\limits_{x \in [a, b]}|\omega_n(x)| = Q_n(x), | + | |
- | \] | + | |
- | где $ [a, b] $ -- промежуток интерполирования, $ R_n(x) = f(x) - L_n(x) $, $ M_{n+1} = \max\limits_{\eta \in [a, b]}|f^{(n+1)}(\eta)| $, $ \omega_n(x) = \prod\limits_{j=0}^n(x - x_j) $. Левая часть неравенства является практической погрешностью, а правая -- теоретической. | + | |
===== Постановка задачи ===== | ===== Постановка задачи ===== | ||
- | Построить интерполяционный многочлен по 2, 3, 4, 5 и 6 узлам (равноотстоящим и чебышёвским) для функции $ f(x) = \cfrac A{x^2 + px + q} $ на промежутке $ [a, b] $ по равноотстоящим и по чебышёвским узлам. Найти фактическую погрешность и сравнить её с теоретической оценкой. | + | Построить набор случайных данных для функции $ f(x) $ на промежутке $ [0, b] $ разбив его на $ n $ участков при параметре зашумления $ fluc $. Аппроксимировать полученные данные с помощью МНК по трём моделям: полиномиальной, экспоненциальной и ДПФ. |
===== Порядок выполнения работы ===== | ===== Порядок выполнения работы ===== | ||
- | - Реализовать функцию ''f()'' для вычисления значений в функции $ f(x) $. | + | - Реализовать функцию ''f(x)'' для вычисления значений функции $ f(x) $. |
- | - Реализовать функцию ''df()'', вычисляющая $ n $-ую производную функции $ f(x) $. Данную функцию можно реализовать с помощью ''switch'', предварительно посчитав производные в символьном виде, например, в Wolfram. | + | - Реализовать функцию ''mnk()'' для построения модели с помощью МНК. |
- | - Реализовать функцию, вычисляющую интерполяционный многочлен по методу Лагранжа ''lagrange()'' (для нечётных вариантов) или Ньютона ''newti()'' (для чётных вариантов). | + | - Разбить отрезок $ [0, b] $ на $ n $ участков и вычислить значения функции $ f(x) $ для каждого $ x $. |
- | - Построить график полученного интерполяционного многочлена $ n $-го порядка по равномерной сетке и функции $ f(x) $ в одном окне. Отметить на графике узлы интерполяции. Выписать полученный интерполяционный многочлен с точностью коэффициентов до 7 знаков после запятой. | + | - Аппроксимировать полученные данные с помощью функции ''mnk()'' по двум моделям: полиномиальной и экспоненциальной. Построить графики аппроксимационных функций вместе с облаком значений. Вычислить среднеквадратические отклонения для каждой модели. Сделать выводы. |
- | - Аналогично выполнить построение для чебышёвской сетки. | + | - Построить набор случайных данных с параметром зашумления $ fluc $. Рекомендуется использовать следующую функцию (здесь ''stud_num'' -- номер студенческого билета, e.g.: ''stud_num = 130301''): <code octave> |
- | - Заполнить таблицу для каждой сетки и сделать выводы: | + | rand ("state", stud_num) |
- | + | x = 0:b/n:b; | |
- | ^ Значение $ n $ | 1 | 2 | 3 | 4 | 5 | | + | y = f (x) + (2 * rand (1, n) - 1) * fluc; |
- | ^ Значение $ M_{n+1} $ | | | | | | | + | </code> |
- | ^ Значение $ \max|\omega_n(x)| $ | | | | | | | + | - Аппроксимировать полученные данные с помощью функции ''mnk()'' по трём моделям: полиномиальной, экспоненциальной и ДПФ. Построить графики аппроксимационных функций вместе с облаком значений. Вычислить среднеквадратические отклонения для каждой модели. Сделать выводы. |
- | ^ Значение $ (n + 1)! $ | | | | | | | + | - Изменить коэффициент при $ x $ так, чтобы функция $ f(x) $ стала периодической, т.е. $ f(0) = f(b) $. Реализовать периодическую функцию ''f_T(x)''. |
- | ^ Значение $ Q_n(x) $ | | | | | | | + | - Построить набор случайных данных по подвергнутой периодизации функции $ f_T(x) $. |
- | ^ Значение $ \max|R_n(x)| $ | | | | | | | + | - Аппроксимировать полученные данные с помощью функции ''mnk()'' с помощью ДПФ. Построить графики аппроксимационных функций вместе с облаком значений. Вычислить среднеквадратические отклонения для каждой модели. Сравнить результаты аппроксимации с непериодической функцией $ f(x) $, сделать выводы. |
===== Варианты заданий ===== | ===== Варианты заданий ===== | ||
<note important> | <note important> | ||
- | Выполнение работ осуществляется по индивидуальным вариантам заданий (коэффициентам функции). Номер варианта для каждого студента определяется преподавателем. | + | Выполнение работ осуществляется по индивидуальным вариантам заданий (функции и параметры). Номер варианта для каждого студента определяется преподавателем. |
</note> | </note> | ||
- | [[.task4:task4-vars]] | + | [[.task4:task4_vars]] |
- | ===== Содержание отчёта ===== | ||
- | * Цель работы. | ||
- | * Краткое изложение основных теоретических понятий. | ||
- | * Постановка задачи с кратким описанием порядка выполнения работы. | ||
- | * Графики интерполяционных многочленов и их вид. | ||
- | * Таблицы для оценки погрешности. | ||
- | * Общий вывод по проделанной работе. | ||
- | * Код программы. |