Differences

This shows you the differences between two versions of the page.

--- courses:computational_mathematics:prac5 [2022/04/16 17:44]
andrey.suchkov removed
+++ — (current)
@@ Line 1: / Line 1: @@
-====== Практическая работа №5: Алгоритм Ремеза ======
-===== Цель работы =====
-Освоение и реализация алгоритма Ремеза для построения полиномов наилучшего равномерного приближения средствами 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 $ берутся из п/р №4.
-===== Порядок выполнения работы =====
-  - Реализовать функцию ''f()'' для вычисления значений в функции $ f(x) $.
-  - Реализовать функцию ''remez()'', выполняющая алгоритм Ремеза.
-  - Построить полиномы 5-ой и 10-ой степени. Для полинома 5-ой степени построить кривые на графике и указать их вид для 1-ой, 2-ой, 3-ей, 4-ой, 6-ой и последней итерации, а для полинома 10-ой степени -- для 1-ой, 2-ой, 3-ей, 5-ой, 7-ой, 10-ой и последней итерации. Для сравнения полиномы выводить на графике вместе с функцией $ f(x) $.
-  - Для каждого из полиномов заполнить таблицу ниже и сделать выводы (здесь $ \sigma $ -- уровень квазиальтернанса; $ R_{\max} $ -- глобальный максимум погрешности; $ \varepsilon $ -- точность выравнивания; $ i_{after} $ -- номер точки квазиальтернанса, за которой идёт точка максимума):
-^  Номер шага  ^  Значение $ \sigma $  ^  Значение $ R_{\max} $  ^  Значение $ \varepsilon $  ^  Значение $ i_{after} $  ^
-|  1           |                       |                         |                            |                          |
-|  2           |                       |                         |                            |                          |
-|  ...                                                                                                               |||||
-//Примечание:// коэффициенты многочлена необходимо выводить в формате ''long g''; все остальные значения -- в формате ''short g''.
-==== Дополнительное необязательное задание ====
-Оценить фактическую точность выравнивания. Формально мы добиваемся исчерпывания машинной точности, но максимумы ищутся лишь по точкам графиков. Предлагается для каждой точки квазиальтернанса, за исключением совпадающих с концами отрезка (если такие есть), построить квадратичный интерполяционный многочлен с шагом графика для погрешности и найти максимум его модуля. Хорошую оценку фактической точности выравнивания будет давать отношение минимального из этих максимумов к максимальному (включая значения на концах, если они входят в квазиальтернанс).
-===== Содержание отчёта =====
-  * Цель работы.
-  * Краткое изложение основных теоретических понятий.
-  * Постановка задачи с кратким описанием порядка выполнения работы.
-  * Графики интерполяционных многочленов и их вид.
-  * Таблицы для оценки погрешности.
-  * Общий вывод по проделанной работе.
-  * Код программы.

se.moevm.info

User Tools

Site Tools

Differences

Page Tools