Математические основания
Теорема Чебышёва
Теоретической основой алгоритма Ремеза является следующая теорема[3].
Для того, чтобы некоторый многочлен P*(x) степени не выше n был многочленом, наименее уклоняющимся от f ∊ C[a,b], необходимо и достаточно, чтобы на [a,b] нашлась по крайней мере одна система из n + 2 точек xi, a ≤ x0 < x1 < … < xn+1 ≤ b, в которых разность f(x) - P*(x):
- поочерёдно принимает значения разных знаков,
- достигает по модулю наибольшего на [a,b] значения.
Такая система точек называется чебышёвским альтернансом.
|
Теорема Валле-Пуссена
Пусть En — величина наилучшего приближения функции f(x) многочленами степени n. Оценку En снизу даёт следующая теорема[4]:
Если для функции f ∊ C[a,b] некоторый многочлен P(x) степени n обладает тем свойством, что разность f(x) - P(x) на некоторой системе из n + 2 упорядоченных точек xi принимает значения с чередующимися знаками, то
|
Алгоритм
Рассмотрим систему n + 1 функций Φ = {φ0,…,φn}, последовательность n + 2 точек X = a ≤ x0 < x1 < … < xn+1 ≤ b и будем искать аппроксимирующий многочлен
.
- Решаем систему линейных уравнений относительно aj и d:
- Находим точку ξ такую, что D = |f(ξ) — P(ξ)| = max.
- Заменяем в X одну из точек на ξ таким образом, чтобы знак f — P чередовался в точках новой последовательности. На практике следят только за тем, чтобы точки xi были упорядочены на каждой итерации[5].
- Повторяем все шаги с начала до тех пор, пока не будет |d| = D.
На втором шаге мы можем искать не одну точку ξ, а множество Ξ точек, в которых достигаются локальные максимумы |f — P|. Если все ошибки в точках множества Ξ одинаковы по модулю и чередуются по знаку, то P — минимаксный многочлен. Иначе заменяем точки из X на точки из Ξ и повторяем процедуру заново.
Выбор начальных точек
В качестве начальной последовательности X можно выбирать точки, равномерно распределённые на [a,b]. Целесообразно также брать точки[6]:
Модификация
Если аппроксимирующая функция ищется в виде многочлена, то вместо решения системы на первом шаге алгоритма, можно воспользоваться следующим методом[7]:
- Находим многочлен q(x) степени n+1 такой, что q(xi) = f(xi) (задача интерполяции).
- Находим также многочлен q*(x) степени n+1 такой, что q*(xi) = (-1)i.
- Выбирая d так, чтобы многочлен P(x) ≡ q(x) — d q*(x) имел степень n, получаем P(xi) + (-1)id = f(xi).
Дальше повторяются шаги по основной схеме.
Условие остановки
Так как по теореме Валле-Пуссена |d| ≤ En(f) ≤ D, то условием остановки алгоритма может быть D — |d| ≤ ε для некоторого наперёд заданного ε.
Сходимость
Алгоритм Ремеза сходится со скоростью геометрической прогрессии в следующем смысле[8]:
Для любой функции f ∊ C[a,b] найдутся числа A > 0 и 0 < q < 1 такие, что максимальные уклонения от функции f(x) полиномов
, построенных по этому алгоритму, будут удовлетворять неравенствам
где En(f) — величина наилучшего приближения на [a,b] функции f(x) при помощи полиномов Pn(x).
|
Пример
- f(x) = ex, n = 1, P(x) = a x+b.
Шаг 1. |
X1 | −1 | 0 | 1 |
f(xi) | 0.368 | 1.000 | 2.718 |
|
|
Решение системы даёт P = 1.175x + 1.272, d = 0.272. D = max|eξ-P(ξ)| = 0.286 при ξ = 0.16. |
Шаг 2. |
X2 | −1 | 0.16 | 1 |
f(xi) | 0.368 | 1.174 | 2.718 |
|
|
Решение системы даёт P = 1.175x + 1.265, d = 0.279. D = max|eξ-P(ξ)| = 0.279 при ξ = 0.16. |
Так как в пределах данной точности получили ту же самую точку, то найденный многочлен следует рассматривать как наилучшее приближение первой степени функции ex.
Примечания
- ↑ E. Ya. Remez (1934). Sur le calful effectif des polynômes d’approximation de Tschebyscheff. C.P. Paris 199, 337—340; Ch. 3:78
- ↑ Рабинер, 1978, с. 157.
- ↑ Дзядык, 1977, с. 12.
- ↑ Дзядык, 1977, с. 33.
- ↑ Лоран, 1975, с. 117.
- ↑ Дзядык, 1977, с. 74.
- ↑ Лоран, 1975, с. 112.
- ↑ Дзядык, 1977, с. 76-77.
Литература
- DeVore R. A., Lorentz G. G. Constructive Approximation. — 1993.
- Бронштейн И. Н., Семендяев К. А. Справочник по математике для инженеров и учащихся ВТУЗов. — 1980.
- Дзядык В. К. Введение в теорию равномерного приближения функций полиномами. — 1977.
- Лоран П.-Ж. Аппроксимация и оптимизация. — 1975.
- Рабинер Л., Гоулд Б. Теория и применение цифровой обработки сигналов. — 1978.
- Ремез Е. Я. Основы численных методов чебышёвского приближения. — 1969.
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .