This shows you the differences between two versions of the page.
Both sides previous revision Previous revision Next revision | Previous revision | ||
courses:computational_mathematics:prac4 [2021/04/22 20:57] andrey.suchkov removed |
courses:computational_mathematics:prac4 [2022/07/04 05:39] andrey.suchkov removed |
||
---|---|---|---|
Line 1: | Line 1: | ||
- | ====== Практическая работа №4: Алгоритм Ремеза ====== | + | ====== Практическая работа №4: Аппроксимация функций ====== |
===== Цель работы ===== | ===== Цель работы ===== | ||
- | Освоение и реализация алгоритма Ремеза для построения полиномов наилучшего равномерного приближения средствами GNU Octave. | + | Сформировать навыки и умения решения задачи аппроксимации функции с помощью метода наименьших квадратов (МНК) и дискретного преобразования Фурье (ДПФ); освоить реализацию МНК и ДПФ с помощью математического пакета GNU Octave. |
- | + | ||
- | ===== Основные теоретические положения ===== | + | |
- | Алгоритм Ремеза (алгоритм замены Ремеза) -- это итеративный алгоритм равномерного аппроксимирования функций $ f \in C[a, b] $, основанный на теореме П. Л. Чебышёва об альтернансе. Предложен Е. Я. Ремезом в 1934 году. | + | |
- | + | ||
- | Теоретической основой алгоритма Ремеза является следующая теорема: | + | |
- | + | ||
- | **Теорема.** //Для того, чтобы некоторый многочлен $ P^*(x) $ степени не выше $ n $ был многочленом, наименее уклоняющимся от $ f \in C[a,b] $, необходимо и достаточно, чтобы на $ [a,b] $ нашлась по крайней мере одна система из $ n + 2 $ точек $ x_i $, $ a \leqslant x_0 < x_1 < \dots < x_{n+1} \leqslant b $, в которых разность $ f(x) - P^*(x) $:// | + | |
- | - //поочерёдно принимает значения разных знаков,// | + | |
- | - //достигает по модулю наибольшего на $ [a,b] $ значения.// | + | |
- | //Такая система точек называется чебышёвским альтернансом.// | + | |
- | + | ||
- | Пусть $ E_n $ -- величина наилучшего приближения функции $ f(x) $ многочленами степени $ n $. Оценку $ E_n $ снизу даёт следующая теорема: | + | |
- | + | ||
- | **Теорема Валле-Пуссена.** //Если для функции $ f \in C[a,b] $ некоторый многочлен $ P(x) $ степени $ n $ обладает тем свойством, что разность $ f(x) - P(x) $ на некоторой системе из $ n + 2 $ упорядоченных точек $ x_i $ принимает значения с чередующимися знаками, то// \[E_n(f) \geqslant \min|f(x_i) - P(x_i)|.\] | + | |
===== Постановка задачи ===== | ===== Постановка задачи ===== | ||
- | С помощью алгоритма Ремеза найти многочлены наилучшего равномерного приближения 5-й и 10-й степени для функции $ f(x) = \cfrac A{x^2 + px + q} $ на отрезке $ [a, b] $. Значения $ a $, $ b $, $ A $, $ p $, $ q $ берутся из п/р №3. | + | Построить набор случайных данных для функции $ f(x) $ на промежутке $ [0, b] $ разбив его на $ n $ участков при параметре зашумления $ fluc $. Аппроксимировать полученные данные с помощью МНК по трём моделям: полиномиальной, экспоненциальной и ДПФ. |
===== Порядок выполнения работы ===== | ===== Порядок выполнения работы ===== | ||
- | - Реализовать функцию ''f()'' для вычисления значений в функции $ f(x) $. | + | - Реализовать функцию ''f(x)'' для вычисления значений функции $ f(x) $. |
- | - Реализовать функцию ''remez()'', выполняющая алгоритм Ремеза. | + | - Реализовать функцию ''mnk()'' для построения модели с помощью МНК. |
- | - Построить полиномы 5-ой и 10-ой степени. Для полинома 5-ой степени построить кривые на 1-ой, 2-ой, 3-ей, 4-ой, 6-ой и последней итерации, а для полинома 10-ой степени -- 1-ой, 2-ой, 3-ей, 5-ой, 7-ой, 10-ой и последней итерации. Для сравнения полиномы выводить на графике вместе с функцией $ f(x) $. | + | - Разбить отрезок $ [0, b] $ на $ n $ участков и вычислить значения функции $ f(x) $ для каждого $ x $. |
- | - Для каждого из полиномов заполнить таблицу, сделать выводы: | + | - Аппроксимировать полученные данные с помощью функции ''mnk()'' по двум моделям: полиномиальной и экспоненциальной. Построить графики аппроксимационных функций вместе с облаком значений. Вычислить среднеквадратические отклонения для каждой модели. Сделать выводы. |
+ | - Построить набор случайных данных с параметром зашумления $ fluc $. Рекомендуется использовать следующую функцию (здесь ''stud_num'' -- номер студенческого билета, e.g.: ''stud_num = 130301''): <code octave> | ||
+ | rand ("state", stud_num) | ||
+ | x = 0:b/n:b; | ||
+ | y = f (x) + (2 * rand (1, n) - 1) * fluc; | ||
+ | </code> | ||
+ | - Аппроксимировать полученные данные с помощью функции ''mnk()'' по трём моделям: полиномиальной, экспоненциальной и ДПФ. Построить графики аппроксимационных функций вместе с облаком значений. Вычислить среднеквадратические отклонения для каждой модели. Сделать выводы. | ||
+ | - Изменить коэффициент при $ x $ так, чтобы функция $ f(x) $ стала периодической, т.е. $ f(0) = f(b) $. Реализовать периодическую функцию ''f_T(x)''. | ||
+ | - Построить набор случайных данных по подвергнутой периодизации функции $ f_T(x) $. | ||
+ | - Аппроксимировать полученные данные с помощью функции ''mnk()'' с помощью ДПФ. Построить графики аппроксимационных функций вместе с облаком значений. Вычислить среднеквадратические отклонения для каждой модели. Сравнить результаты аппроксимации с непериодической функцией $ f(x) $, сделать выводы. | ||
- | ^ Номер шага ^ Значение $ \sigma $ ^ Значение $ R_{\max} $ ^ Значение $ \varepsilon $ ^ | + | ===== Варианты заданий ===== |
- | | 1 | | | | | + | <note important> |
- | | 2 | | | | | + | Выполнение работ осуществляется по индивидуальным вариантам заданий (функции и параметры). Номер варианта для каждого студента определяется преподавателем. |
- | | ... |||| | + | </note> |
+ | [[.task4:task4_vars]] | ||
- | ===== Содержание отчёта ===== | ||
- | * Цель работы. | ||
- | * Краткое изложение основных теоретических понятий. | ||
- | * Постановка задачи с кратким описанием порядка выполнения работы. | ||
- | * Графики интерполяционных многочленов и их вид. | ||
- | * Таблицы для оценки погрешности. | ||
- | * Общий вывод по проделанной работе. | ||
- | * Код программы. |