Практическая работа №4: Алгоритм Ремеза

Цель работы

Освоение и реализация алгоритма Ремеза для построения полиномов наилучшего равномерного приближения средствами GNU Octave.

Основные теоретические положения

Алгоритм Ремеза (алгоритм замены Ремеза) -- это итеративный алгоритм равномерного аппроксимирования функций , основанный на теореме П. Л. Чебышёва об альтернансе. Предложен Е. Я. Ремезом в 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] $ значения.

Такая система точек называется чебышёвским альтернансом.

Пусть -- величина наилучшего приближения функции многочленами степени . Оценку снизу даёт следующая теорема:

Теорема Валле-Пуссена. Если для функции $ f \in C[a,b] $ некоторый многочлен $ P(x) $ степени $ n $ обладает тем свойством, что разность $ f(x) - P(x) $ на некоторой системе из $ n + 2 $ упорядоченных точек $ x_i $ принимает значения с чередующимися знаками, то

Постановка задачи

С помощью алгоритма Ремеза найти многочлены наилучшего равномерного приближения 5-й и 10-й степени для функции на отрезке . Значения , , , , берутся из п/р №3.

Порядок выполнения работы

Реализовать функцию f() для вычисления значений в функции .

Реализовать функцию remez(), выполняющая алгоритм Ремеза.

Построить полиномы 5-ой и 10-ой степени. Для полинома 5-ой степени построить кривые на 1-ой, 2-ой, 3-ей, 4-ой, 6-ой и последней итерации, а для полинома 10-ой степени -- 1-ой, 2-ой, 3-ей, 5-ой, 7-ой, 10-ой и последней итерации. Для сравнения полиномы выводить на графике вместе с функцией .

Для каждого из полиномов заполнить таблицу, сделать выводы:

Номер шага	Значение	Значение	Значение
1
2
...

Содержание отчёта

Цель работы.

Краткое изложение основных теоретических понятий.

Постановка задачи с кратким описанием порядка выполнения работы.

Графики интерполяционных многочленов и их вид.

Таблицы для оценки погрешности.

Общий вывод по проделанной работе.

Код программы.