- 1 курс
- 2 курс
- 3 курс
- 4 курс
- 5 курс
- 6 курс
Old
Old
This is an old revision of the document!
Освоение и реализация алгоритма Ремеза для построения полиномов наилучшего равномерного приближения средствами 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) $:
Такая система точек называется чебышёвским альтернансом.
Пусть $ 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()
для вычисления значений в функции $ f(x) $.remez()
, выполняющая алгоритм Ремеза.Номер шага | Значение $ \sigma $ | Значение $ R_{\max} $ | Значение $ \varepsilon $ |
---|---|---|---|
1 | |||
2 | |||
… |