Компьютерная графика / МАШ_ГРАФИКА

§2. Аппроксимация алгебраическими многочленами по критерию наилучшего равномерного приближения

Допустим, на отрезке х[a,b] задана некоторая кривая y=f(x). Необходимо аппроксимировать ее алгебраическим многочленом заданной степени n таким образом, чтобы максимальное отклонение  величины  f (x) - P_n(x) на отрезке [a,b] было минимальным.

101

Определение. Многочлен , при котором достигает-ся минимум величины максимального отклонения  модуля разности f(x)-P_n(x), называется многочленом наилучшего равномерного приближения функции f(x) на отрезке [a,b].

Обозначим минимально возможное отклонение (для фик-сированной степени n) через _min. В математической форме его связь с можно представить в виде:

_min =min maxf(x)-P_n(x) = max f(x)- P⁰_n(x)

х[a,b] х[a,b]

Необходимые и достаточные условия на многочлен наи-лучшего равномерного приближения P⁰(x) (при котором достигается _min) задает

Теорема Чебышева

Для того, чтобы многочлен P⁰_n(x) был многочленом наи-лучшего приближения для непрерывной функции f(x) на отрезке [a,b], необходимо и достаточно, чтобы сущест-вовали по крайней мере (n+2) точки а x₀ < x₁ < . . . < x_n₊₁  b, в которых

f(x_i ) - P⁰_n(x_i)=(-1)ⁱ_min, i=0,1,...,n+1,

где  = (+1) либо (-1) одновременно для всех точек x_i (i = 0,1,...,n+1),

_min - минимально возможное отклонение.

По Теореме многочлен P⁰_n(x) должен по крайней мере (n+2) раз отклоняться по оси y на величину  _minот функции f(x), причем знак отклонения при последовательном прохождении точек x₀ , . . ., x_n₊₁ каждый раз изменяется на противоположный.

102

Определение. Набор точек (x₀ , . . ., x_n₊₁ ), в которых раз-ность f(x_i ) - P⁰_n(x_i) попеременно достигает величины (+_min) и (-_min), называется чебышевским альтернансом .

На Pис.5.1, 5.2 показаны примеры наилучших равно-мерных приближений при n=0 (горизонтальный отрезок прямой) и n=1 (наклонный отрезок прямой) для некоторой функции f(x).

Рис.5.1 (n=0)

В общем случае (для произвольных f(x)) задача опреде-ления многочлена наилучшего равномерного приближения аналитического решения не имеет.

Для функции f(x)=0 на отрезке [-1,+1] аналитическое ре-шение для многочленов P_n(x)со старшим коэффициентом (при x), равным 2, дано Чебышевым.

103

Рис.5.2 (n=1)

Среди всех рассмотренных многочленов наилучшее рав-номерное приближение дают многочлены T(x), которые определяются рекуррентной формулой

n=0; Т₀(x) =1;

n =1; Т₁(x) =x; ( 5.9)

n 2; Т_n(x)=2x Т_n_-1(x) - Т_n_-2(x).

Поскольку функция cos(n arccos x) также удовлетворяет соотношениям (5.9), то в тригонометрической форме многочлены Чебышева можно представить в виде:

Т_n(x) =cos(n arccos x). ( 5.10)

Используя рекуррентную формулу (5.9) и выражение (5.10), многочлены Чебышева при n2, можно найти в алгебраическом и тригонометрическом виде:

104

T₂(x) = 2x² –1 = cos(2 arccos x);

T₃(x) = 4x³ –3x = cos(3 arccos x);

T₄(x) = 8x⁴ – 8x² + 1 = cos(4 arccos x);

T₅(х) = 16x⁵ – 20x³ +5x = cos(5arccos x) и т.д.

Несложно заметить, что при четном n полином Т_n явля-ется четной функцией (как сумма четных степеней х). При нечетном n Т_n(x) является нечетной функцией. При –1  x  1выполняется ограничение Т_n(x) = cos(n arccos x),по-этому максимальное отклонение _min у всех Т_n(x) равно1. Графики многочленов Т₀(x), Т₁(x), Т₂(x)показаны на Рис.5.3.

Рис.5.3

Координаты точек альтернанса являются реше-ниями уравнения

T_n(x)=cos(n arccos(x)=1.

105

Решением являются значения

х_i= cos(i/n); i=0,...,n. ( 5.11)

Если функция f(x)=0 задана на произвольном интервале [a,b], то точки альтернанса и сам многочлен Чебышева можно получить для нее с помощью линейной замены

x = 0,5[(b+a)+(b-a)x],

переводящей точки из отрезка [-1,1] в точки отрезка [a,b]. Применяя замену к значениям (5.11), получим что координаты точек альтернанса функции f(x)=0 на отрезке [a, b] равны

x_i = 0,5[(b+a)+(b-a) cos(i/n)], , i=0,...,n (5.12)

В случае произвольного задания кривых y = f(x) для опре-деления многочленов наилучшего равномерного прибли-жения применяют численные итерационные алгоритмы. Наиболее употребительны алгоритмы, в которых искомый полином P_n(x) и отклонение _min определяются следую-щим образом.

ШАГ 1. Задаются начальные приближения точек альтер-нанса х⁰_i ( i=0,...,n+1). Если по характеру приближаемой функции нельзя сделать никаких предположений о зна-чениях х⁰_i, то в их качестве принимают значения x_i для функции f(x)=0 для степени n+1:

х⁰_i = 0,5[(b+a)+(b-a) cos(i/(n+1))], i=0,...,n+1.

ШАГ 2. Допустим, осуществляется итерация с некоторым номером j (j=1,2,…). К началу ее известно очередное при-ближенное значение точек альтернансах⁽^j^-1)_i (i=0,...,n+1). Необходимо построить многочлен P^j_n(х)=, кото-рый в точкахх⁽^j^-1)_i знакопеременно отклоняется от f(x) на неизвестную постоянную по модулю величину ⁽^j⁾).Неиз-вестными в этой задаче являются коэффициенты a⁽^j⁾₀, . . . , a⁽^j⁾_n многочлена P^j_n(х) и ⁽^j⁾.В математической форме

106

отклонения в точках альтернанса можно представить в следующем виде:

P^j_n(х^(j-1)_i) - f(х^(j-1)_i)=(-1) ⁱ^(j), i=0,...,n+1.

Перенося слагаемые, содержащие неизвестные, в левые части уравнений, а известные значения функций - вправо, получаем систему линейных уравнений относительно (a⁽^j⁾₀, . . . , a⁽^j⁾_n, ⁽^j⁾):

; i=0,...,n+1.

Поскольку определитель системы всегда отличен от нуля, то решение ее (a⁽^j⁾₀,..., a⁽^j⁾_n, ⁽^j⁾)существует и единственно.

В силу того, что значения точек альтернанса (х⁽^j^-1)_i) извест-ны приближенно, то найденное отклонение ⁽^j⁾будет по модулю меньше искомого, ещё не известного равно-мерного отклонения _min (Рис.5.4)

Рис.5.4

Это условие можно использовать для коррекции положе-ния точек альтернанса.

107

ШАГ 3. Коррекция альтернанса Задается некоторое постоянное число q, такое что 0<q<1. В окрестности каждой точки альтернанса (х⁽^j^-1)_i)определяется ближайшая точка х_imax ,в которой разность

P^j_n(х_imax) – f(х_imax)= _imax

максимальна по модулю,
имеет тот же знак, что и ⁽^j⁾.

Последующее положение точки альтернанса х⁽^j⁾_iвыбирается между х⁽^j^-1)_iи х_imaxиз условия:

P^j_n(х^(j)_i)-f(х^(j)_i)=^(j)+ q(_imax - ^(j) ).

После коррекции всех точек альтернанса их новые положения (х⁽^j⁾_i)сравниваются с предыдущими х⁽^j^-1)_i. Если у всех точек

 _i =x^(j-1)_i- x^(j)_i  ; i=0,...,n+1,

где  - некоторое малое наперед заданное число, то процесс заканчивается. При этом найденный многочлен при-нимается в качестве искомого:

P_n(х)= P^j_n(х),

а оптимальное равномерное отклонение:

_min = ⁽^j⁾ .

Если хотя бы одна разность  _i >, т.е. имела место значи-тельная корректировка альтернанса, то переходим на ШАГ 2 и осуществляем следующую итерацию.

Содержание