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

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

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

101

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

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

min =min maxf(x)-Pn(x) = max f(x)- P0n(x)

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

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

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

Для того, чтобы многочлен P0n(x) был многочленом наи-лучшего приближения для непрерывной функции f(x) на отрезке [a,b], необходимо и достаточно, чтобы сущест-вовали по крайней мере (n+2) точки а x0 < x1 < . . . < xn+1 b, в которых

f(xi ) - P0n(xi)=(-1)imin , i=0,1,...,n+1,

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

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

По Теореме многочлен P0n(x) должен по крайней мере (n+2) раз отклоняться по оси y на величину min от функции f(x), причем знак отклонения при последовательном прохождении точек x0 , . . ., xn+1 каждый раз изменяется на противоположный.

102

Определение. Набор точек (x0 , . . ., xn+1 ), в которых раз-ность f(xi ) - P0n(xi) попеременно достигает величины (+min) и (-min), называется чебышевским альтернансом .

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

Рис.5.1 (n=0)

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

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

103

Рис.5.2 (n=1)

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

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

n =1; Т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), многочлены Чебышева при n2, можно найти в алгебраическом и тригонометрическом виде:

104

T2(x) = 2x2 –1 = cos(2 arccos x);

T3(x) = 4x3 –3x = cos(3 arccos x);

T4(x) = 8x4 – 8x2 + 1 = cos(4 arccos x);

T5(х) = 16x5 – 20x3 +5x = cos(5arccos x) и т.д.

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

Рис.5.3

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

Tn(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] равны

xi = 0,5[(b+a)+(b-a) cos(i/n)], , i=0,...,n (5.12)

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

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

х0i = 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). Необходимо построить многочлен Pjn(х)=, кото-рый в точкахх(j-1)i знакопеременно отклоняется от f(x) на неизвестную постоянную по модулю величину (j)).Неиз-вестными в этой задаче являются коэффициенты a(j)0 , . . . , a(j)n многочлена Pjn(х) и (j) .В математической форме

106

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

Pjn(х(j-1)i) - f(х(j-1)i)=(-1) i (j), i=0,...,n+1.

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

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

Поскольку определитель системы всегда отличен от нуля, то решение ее (a(j)0 ,..., a(j)n , (j))существует и единственно.

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

Рис.5.4

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

107

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

Pjn(хimax) – f(хimax)= imax

  1. максимальна по модулю,

  2. имеет тот же знак, что и (j).

Последующее положение точки альтернанса х(j)iвыбирается между х(j-1)iи хimaxиз условия:

Pjn(х(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,

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

Pn(х)= Pjn(х),

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

min = (j) .

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