Наилучшая чебышёвская аппроксимация как эффективный способ обработки информации. Рассматривается проблема наилучшей чебышевской аппроксимации для эффективной обработки инфор-мации.


Чтобы посмотреть этот PDF файл с форматированием и разметкой, скачайте его и откройте на своем компьютере.

«Штучний інтелект»
3
’00
9

53


К

УДК 519.651.


А.А.

Каленчук

Порханова

Институт кибернетики
им. В.М. Глушкова
НАН Украины,
г.
Киев

io
@
pulic
.
icy
.
kiev
.
u


Наилучшая чебышёвская аппроксимация
как
эффективный способ обработки информации


Рассматривается проблема наилучшей чебышевской
аппроксимации
для эффективной обработки
инфо
р

мации
. Дается обоснование преимуществ разработанных алгоритмов аппроксимации, которые св
я
заны

с их оптимизацией по точности и быстродейс
т
вию.


Введ
ение

Решение проблемы информатизационного обеспечения обществ
а является всё бо

лее актуальным и определяющим условием его эффективного развития. Информация о
состояниях исследуемых процессов в природе и обществе как результат проведения
изм
е
рений является, как правило,
дискретным представлением в виде

информационных

масс
и
вов числовых данных
о функциональных зависимостях, характеризующих эти про

цессы. Трудности, а зачастую и невозможность использовать массивы возникают при
решении т
а
ких пр
и
кладных задач, как математическое моделирование и прогно
зи

рование, определен
ие функциональной закономерности природы исследуемого про
цес
са

например, в виде эмп
и
рической формулы, и при решении проблем экономного хра
не

ния больших по объему
ма
с
сивов данных

либо скоростной передаче по каналам связи, а
также при возобновлени
и
зн
а
чений функциональной зависимости на «
неосвещённых
замерами
» участках 
обратная з
а
дача
 и др. Эти трудности преодолеваются путём
замены 
сжатия
 больших массивов ан
а
литическими выражениями с небол
ь
шим коли

чеством параметров 
прямая задача
.

Для решения это
й проблемы применяются средства
аналитической обработки

да
н
ных
на основе методов и алгоритмов аппроксимации приближения функций. Пред

лагается эффективный способ анали
тичес
кой обработки данных, обеспечивающий
высо
кую то
ч
ность приближения и использующи
й аппроксимирующие ан
а
литические
выражения разных типов 1. Этот способ основан на методах и алгоритмах
чебышёв

ской наилучшей аппрокс
и
мации
, который имеет существенное преимущество перед
интерполяционным и средн
е
квадратическим спо
собами приближения. При
чём главное
преимущество этого способа

обеспечение требуемой гарантированной точности приб

ли
жения во всей непрерывной о
б
ласти задания функции позволяет сохранять получен

ную точность во всех точках при р
е
шении обратной зад
а
чи.

Разработанные автором ал
горитмы основаны на методе Е.Я.

Ремеза после
дова

тельных чебышёвских интерполяций п.ч.и.  и, в свою очередь, обладают преим
у

ществами перед алгоритмами других авторов, так как для них проведен анализ всех
видов погрешностей с целью их
о
п
тимизации по
точности и быстродействию
3, 4.

Основные задачи аналитической обработки данных.

В зависимости от цели
ан
а
литической обр
а
ботки массивов числовых данных можно выделить

такие основные
задачи, для решения которых используются методы и алгоритмы аппроксима
ции
функ

Каленчук

Порханова А.А.


«Искусственный интеллект»
3
’00
9

54


К

ций. В то

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

дачи тесно связ
а
ны между собой и решение одной из них часто используется для ре
ше

ния др
у
гих.

Задача аналитичного представления массивов числовых данных
состоит в
прибл
и

жении дискретно заданной функциональной зависимости
f
различными типами анали

тич
е
ских выражений аппроксимантов
F
с целью их эффективного использования при
реш
е
нии различных прикладных проблем.

Задача поиска эмпирических закономерностей процесса
,
выраженного экспери

ме
н
тальными данными
,

с целью построения эмпирических формул состоит в том, что
получе
н
ная таблица значений измеряемых величин
i
x
и
i
y

N
,
i
1

 является прибли

женным пре
д
ставл
ением некоторого эмпирического закона


A
;
x
F
, который характе

ри
зуется н
е
большим количеством параметров
A





0
, 
1
,…, 

 и для определения
которого используется тот или иной способ пр
и
ближения.

Задача сжатия численной информации
в виде
больших по объему массивов
числ
о
вых данных состоит в приближенной замене дискретно заданной функции
f
на
одномерной или многомерной сетке некоторым аналитическим выражением
F
с неболь

шим числом п
а
раметров. Эта задача характеризуется коэффициентом сжатия
С
, кото

рый определяется формулой

С



f
/


F
,

где


f
,


F



число бит, необходимых для сохранения соответственно дискретно
заданной функции
f
и аппро
к
симанта
F
.

Задача приближенного
восстановления
значений дискретно заданной функции
на «неосвещенных
замерами» участках
обратная задача возникает, как правило,
когда знач
е
ния функции
f
получены только в некоторых точках
N
x
,
,
x
,
x


1
из
области определ
е
ния
S
, и которых оказывается недостаточно для пр
оведения
даль

нейших исследований. В таком случае применяется способ приближенного пред
став

ления
функции
f
аналитич
е
ским выражением с целью его использования для вычис

ле
ния недостающих значений функции в других точках из
S
. На практике необходи

мость решения этой задачи возникает, когда при исследовании соответствующих
процессов и объектов пол
у
чени
е
дополнительных данных затруднено или вообще
невозможно, например, при исследовании природных проце
с
сов, а также п
ри пере

ходе от нерегулярной сетки к регулярной для картографо

математического модели

ро
вания в географических инфор
мационных си
с
темах ГИС’ах.

Задача сглаживания экспериментальных данных
возникает в случаях, к
о
гда
функция
f
задана
на сетке
S
своими значениями, которые могут иметь зн
а
читель

ные случайные погрешности измерений. В случае
,
когда предварительно известны
свойства поведения и
с
ходной функции
,
используется способ сглаживания экспери

ментальных данных с
целью устранения указанных погрешностей.

Чебышевский способ аппроксимации для аналитической обработки дан
ных
.
Наиболее распространенными на практике для аналитической обработки данных
я
в
ляются методы и алгоритмы приближения функций, которые основы
ва
ют
ся на
различных способах аппроксимации, а именно
:
интерполяционном, средне
квадра

тич
ном и равноме
р
но

чебы
шевском.

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

жения
способ наилучшей чебышевской аппроксимации
является
наиболее э
ффектив

ным и униве
р
сальным
и обладает особенным свойством не только получать высокую
Наилучшая чебышёвская аппроксимация к
ак эффективный сп
особ обработки…

«Штучний інтелект»

3
’00
9

55


К

точность аппрокс
и
мации в точках дискретного представления функциональных
зависимостей, но и обеспеч
и
вать
требуемую гарантированную точность
приближе

ния
во всех точках не
пр
е
рывного инте
р
вала их задания 4.

Проблема наилучшей равномерной чебышевской аппроксимации функции


x
f

на интервале




,
основана на чебышевском принципе минимизации величины
меры равн
о
мерного приближения








A
x
H
x
f
H
L



x

;
mx
,



и состоит в нахож

дении такого а
п
проксиманта степени


с набором коэффициентов






A
,
,
,
1
0



из всей совокупн
о
сти аппроксимантов
H

степени


,
который удовлетворяет усло

вию минимакса


mi


H
L
, где


x
f

непрерывная на




,
функция и



H
H
L

mi



наименьшее возмо
ж
ное значение меры равномерного прибл
и
жения.

В качестве


A
x
H

;
будем рассматривать классы


всех полиномов степени
не в
ы
ше

вида




A
x

x

x



i
i
i

;
0




и классы


всех дробно

рациональных
выра

жений п
о
рядка




l

m
вида








B
A
x

x
Q
x

x


m
l

;
;
/


, где

l

x
 и
Q
m

x




поли

номы
степеней
l
и
m

с наборами соответственно коэффициентов


l
i

A
i
,
0
,


и


m


B

,
0
,


.
Тогда пост
а
новка задачи нахождения наилучших чебышевских
аппроксимантов имеет следующий вид
:















x

L
A
x

x
f
mi
;
mx
,




,













x
L

L




mi
,


1















x

L
B
A
x

x
f
mi
;
;
mx
,




,











x
R
L

L




mi
,




где
П


x
 и
R


x


полиномиальный и дробно

рациональный наилучшие чебышев
ские
а
п
проксиманты, а

и



соответственно величины их наилучших пр
и
бли
же
ний.

Существо
вание, единственность и свойства наилучших аппроксимантов выте

кают из классических теорем Э.

Бореля и П.Л.

Чебышева

для полиномиальных и
Н.И.

Ахиезера и П.Л.

Чебышева

для дробно

рациональных аппроксима
н
тов 5. На
основании этих теорем единственные ре
шения задач 1 и  совпадают соответ

ственно с решениями
«
элемента
р
ных
»
задач вида










A
x

x
f

X
x
;
mx
1
,











B
A
x

x
f

X
x
;
;
mx



1’, ’

на таких 



точечных подмножествах



,

X

,
X

1

, для которых величины



и




до
с
тигают свои наибольшие возможные значения, равные

и

.

Каждая из таких 



точечных задач называется
задачей чебышевской интер

пол
я
ции
функции
f

x
 на множестве 



х точек, ко
торые являются соответственно
чебыше
в
ским альтернансом
для полиномиальной задачи 1 и
экстремальным бази

сом
для др
о
бно

рациональной задачи . Именно это
«
замечательное
»
свойство
«чебышевского альтерна
н
са» является теоретической основой для нахождения в
сех
наилучших чебышевских пр
и
ближений.

Все известные способы решения чебышевской задачи можно в основном раз
де

лить
на способы, основанные на распространении методов Е.Я.

Ремеза особенно 

го,
и спос
о
бы, использующие аппараты линейного и выпуклого прогр
аммирования. Для
Каленчук

Порханова А.А.


«Искусственный интеллект»
3
’00
9

56


К

решения дробно

рациональной задачи используются также различные приемы после

довательной
дифференциальной линеаризации по параметрам

коэффициентам. Син

тезом многих н
а
правлений в п
о
следние годы явилась также теория сплайновой ап

проксимаци
и 5.

Преимуществами методов Е.Я. Ремеза являются сравнительно быстрая ско

рость их сходимости в некоторых случаях квадратичная и возможность стандар

тизации вычисл
е
ний, что очень важно для эффективности их численных реализаций.

Метод Е.Я.

Ремеза
решени
я задач 1 и  основан на последовательных
чебышев
с
ких интерполяциях п.ч.и.,

шагов которых сводятся к нахождению
п
о
следовательности 



точечных
S

наборов




1
,
0
,




v
x
S

v

, сходящейся к
искомому чебышевскому ал
ь
тернансу или экстремальному б
азису, и решению на
каждом


м шаге систем алгебраиче
с
ких ура
в
нений












v

v



v
x

x
f






1
,
,

3






















v

v

m

v

l

v

v
x
Q
x

x
f
x
w






1
/
,
,

4

соответственно линейных относительно коэффициентов

k

k
,
0
,

полинома


x



,

и вел
и
чины



в задаче 3 и нелинейных относительно коэфф
и
циентов
l
i

i
,
0
,

и
m
i

i
,
0
,

и величины



в задаче 4,
x


S

,
1
,
0




.

Следует заметить, что в отличие от полиномиального случая с
ходимость чебы

ше
в
ских интерполяций в случае задачи 4 теоретически обеспечивается не при лю
бом

начал
ь
ном наборе 



х точек, хотя практика применения известных в литературе
различных численных реализаций даже упрощенных в
а
риантов метода Ремеза пока

за
ла крайне редкую их
«
несходимость
»
.

Основная трудность всех численных реализаций п.ч.и. состоит в выборе 



точечных подмножеств области аппроксимации, на которых осуществ
ляются шаги
чеб
ы
шевских и
н
терполяций. От способа этого выбора зависит не только с
корость
сходимости всего метода, но и сам факт его сходимости. Возможны три класса
ва

риантов последов
а
тельной замены указанных 



точечных наборов:
оптималь
ный
,

полуоптимальный
и
д
о
пустимый
вар
и
анты.

При оптимальном варианте для некоторых классов фун
кций обеспечивается квад

р
а
ти
ч
ная
скорость сходимости, что на практике обеспечивает, как правило, всего
одну

две итерации. В
полуоптимальном
варианте

число итераций для получения
аналогичного э
ф
фекта оказывается в несколько раз больше, а в
допустимом
оно

может быть во много раз бол
ь
шим , с.

79

.

Алгоритмы реализации способа наилучшей чебышевской аппроксимации.
Ра
з
работанные в ИК им. В.М. Глушкова НАНУ алгоритмы основаны на втором м
е

тоде п.ч.и. Е.Я. Ремеза и обладают рядом преимуществ по сравнению с изв
естными в
литературе ан
а
логичными численными реализациями 6. Главным достоинством
этих алгоритмов являе
т
ся то, что в них разработан
оптимальный
способ замены 



точечных наборов при пер
е
ходе к новому
S
набору 7.

Численная реализация разработанных ал
горитмов также имеет ряд допол
ни
тель

ных
преимуществ, связанных с оптимизацией этих алгоритмов по точности и быстро

действию
8. Алгоритмы могут находить либо аппроксимант заданной фиксирован

ной степени вход по степени, либо такой аппроксимант, котор
ый обеспечивает
Наилучшая чебышёвская аппроксимация к
ак эффективный сп
особ обработки…

«Штучний інтелект»

3
’00
9

57


К

заданную точность прибл
и
жений вход по точности, которую не должна превышать
апостериорная оценка полной п
о
грешности аппроксимации по соответствующему алго

ритму. При этом при и
с
следовании поведения функции отклонения








A
;
x
F
x
f
x
w


во всех точках множества
S
на ка
ж
дом шаге чебышевских интерполяций учи
ты

вается как
верхняя
, так и
нижняя
границы в
е
личины наилучшего приближения, что
позволяет получить более точную оценку полной погрешности алгоритмов.

Для решен
ия полиномиальной задачи
разработаны два алгоритма «А» и «Б»,
соо
т
ветствующие записям аппроксимирующего полинома в формах



i
i
i
x

0
для алго

ритма
«
А
»
и





i
i
i
x
T

0
для алгоритма
«
Б
»
.

Алгоритм «Б» возник как модификация алгоритм
а
«
А
»
в связи с работой Н.С.

Бах

в
а
лова
9 и может быть использован как существенное улучшение алгоритма «А»,
так как используемая в алгоритме «А» привычная запись полинома в виде



i
i
i
x

0
в
случаях бол
ь
шого «разброса» значений коэффициенто
в
i

может стать источником
большой погрешн
о
сти округлений при вычислении значений полинома в точках по
схеме Горнера. Предлага
е
мый Н.С.

Бахваловым алгоритм использует запись много
чле

нов в виде линейной комбин
а
ции многочленов Чебышев
а, а именно









i
i
i

x
T

x
Q
0
,

и позволяет существенно умен
ь
шить указанную погрешность при вычислений зна
че

ний полинома.

В результате анализа полных погрешностей алгоритмов «А» и «Б» установ
ле
но,

что преимущество алгоритма «Б» становится ощутимым
при степенях
0


; при
0



оба эти алгоритма примерно равносильны.

Алгоритмы могут работать как для случая аналитически заданной, так и для
случая дискретно заданной функции


x
f
.
В обоих случаях п
роцедура выбора 



точечного н
а
бора на каждом шаге ч.и. предполагает дискретизацию, поэтому отли

чие этих случаев тол
ь
ко в том, что во втором из них значения функции в нужных
точках известны, а в первом предусматривается процедура их вычи
с
ления.

Дробно

рациональную аппроксимацию

целесообразно использовать для повы

шения точности приближения функции


x
f
, природа которой такова, что она на
некоторых учас
т
ках имеет
«
всплески
»
. В этом случае удается более точно учитывать
особенности поведе
ния фун
к
ции.

В силу того, что переход от полиномов к дробно

рациональным выражениям
расш
и
ряет класс чебышевских аппроксимантов, очевидно, что





, где


и





соо
т
ветственно величины наилучше
го дробно

рационального и полиномиального
приближений той же функции на том же с
а
мом отрезке аппроксимации
E
.

Несмотря на то, что переход от полиномиальных аппроксимантов к дро
б
но

рациональным не позволяет увеличить порядок стремления
к нулю велич
и
ны



для
всего класса функций, можно утверждать, что благодаря этому пер
е
ходу расши

ряется класс функций, для которых величина наилучшего прибл
и
жения будет того
же порядка, что и для
«
хороших
»
функций.

Каленчук

Порханова А.А.


«Искусственный интеллект»
3
’00
9

58


К

Следует заметить,
что в отличие от полиномиального случая сходимость п.ч.и.
пр
и
чем, как правило, квадратическая для дробно

рациональной задачи согласно ра
б
о

там
А.

Ральстона 5 может быть обеспечена только при условии наличия началь
ного
пр
и
ближения




x
R

0
,
«
бли
з
кого
»
к наилучшему дробно

рациональному аппрокси

манту


x
R

.

В некоторых частных случаях для многих математических функций, в
осо
бен

ности при малых значениях
k
m



, в качестве начального набора точек для на
хож

дения




x
R

0
можно применять точки уклонения полинома Чебышева, но для общего
случая ч
е
быше
в
ской рациональной задачи нет никаких практических рекомендаций
относительно выбора
«
близкого
»





x
R

0
. Этот недостаток устранен
работами Вер

нера 5, который предложил метод, всегда сходящийся с любого начального
при

ближения. Однако громоз
д
кость вычи
с
лений и низкая скорость сходимости линей
ная

,

по утверждению самого автора
,
не позв
о
ляют использовать его эффективно на прак
тик
е
.

Учитывая сказанное выше, а также то, что даже упрощенные варианты п.ч.и.
зача
с
тую сходятся, автором был разработан сочетающий в себе преимущества
методов Ремеза и Вернера
комбинированный алгоритм
к.а. 5. И
дея этого
алгоритма состоит в том, что на пр
актике часто желательно получить приближение,
модуль

максимум уклонения котор
о
го не превышает некоторое заданное число
0


. Поэтому естественно вычислять последов
а
тельность аппроксимантов, начиная
с более малых значений степеней
l
и
m
и
повышая эти значения до получения при

ближения с желаемой точностью. Таким образом, будем предп
о
лагать, что всегда
пе
ред
началом вычисления


x
R
m
,
l
уже получен наилучший аппрокс
и
мант


x
R
m
,
l
1
1


.

Для получения аппроксимантов к
аждой новой степени вначале использ
у
ется м
е
тод
п.ч.и. с обязательной проверкой сходимости алгоритма на каждом шаге ч.и. В
случаях, когда сходимость не нарушается, метод п.ч.и. работает до конца, т.е. до
п
о
лучения наилучшего аппроксиманта текущей степени. Е
сли же на каком

то шаге
п.ч.и. сх
о
димость наруш
а
ется например, число участков перемены знака уклонений
меньше



m
l
, то для получения начального приближения




x
R
m
,
l
0
, имеющего не
меньше



m
l

экстремума,
вступает в работу
начальный алгоритм
н.а. мет
о
да
Вернера. После этого снова работает метод п.ч.и. Если не учитывать случаи вы

рождения, сходимость мет
о
да п.ч.и. обеспечена и абсолютное значение макси
маль

ного уклонения полученного на
и
лу
чшего аппроксиманта не превышает величину
желаемой точности, то алгоритм заканчивает свою работу. В пр
о
тивном случае сте

пень аппроксиманта повышается и снова начин
а
ет работать метод п.ч.и.

В разработанном к.а. учитываются случаи
вырождения
, когда у наилуч
шего
аппро
к
симанта пред
ы
дущей степени уклонений равной величины и чередующих
знак больше



m
l
,
и
почти

вырождения
,
когда участков перемены знака больше



m
l
, а модуль

максимумов уклонений равной величины точно



m
l
.

Несмотря на то, что случаи вырождения и особенно почти вырождения крайне
ре
д
ки, очень важно с вычислительной точки зрения уметь их распознавать до начала
вычисл
е
ния вырожденного аппроксиманта. С этой целью в алгоритме предпо

лагается, что
перед вычислением


x
R
m
,
l
всегда имеется наилучший аппроксимант


x
R
m
,
l
1
1


. Это равносильно тому, что вычисления следует н
а
чинать всегда с невырож

денных
аппроксимантов


x
R
,
m
l
0

для
m
l

, или


x
R
l
m
,

0
для
m
l

.

Наилучшая чебышёвская аппроксимация к
ак эффективный сп
особ обработки…

«Штучний інтелект»

3
’00
9

59


К

В случае дробно

рациональной аппроксимации исходная функция


x
f
пред

по
лаг
а
ется заданной на




,
как аналитически, так и дискретно, однако при поиске
новых эк
с
трему
мов уклонений используется дискретная процедура вычисления зна

чений


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

вляется
тольк
о по заданной то
ч
ности


. Отличие также состоит в том, что в этом
случае система



m
l

алгебраических уравнений является
нелинейной.
Для ее ре

ш
е
ния используется прием линеаризации и метод секущих.

Когда для текущег
о


x
R
m
,
l
п.ч.и. не сх
о
дится, т.е. число
NN
модуль

макси

мумов экстремумов, чередующих знак и равных по в
е
личине, меньше



m
l
; или
не сходится метод секущих, то начинает работать н.а. с наилучшего аппроксиманта


x
R
m
,
l
1
1


, послед
о
вательно повышая его степени до степеней текущего аппрокси

манта до тех пор пока не б
у
дет получено не менее



m
l

точек, в которых
экстремумы уклонения чередуют знак. После этого снова начинает работать метод
п.ч.и.
до получения аппроксиманта, име
ю
щего



m
l
равных по модулю и чере

дующих знак
экстремумов

уклонений. Этот аппрокс
и
мант принимается за начальное
приближение




x
R
m
,
l
0
метода п.ч.и. для нахождения на
и
лучшего приближения


x
R
m
,
l
,

и работа к.а. продолжается до получения наилучшего а
п
проксиманта требуемой точ

ности.

Следует добавить, что использование описанных выше алгоритмов полино

миальн
о
го приближения позволяет находить также наилучшие равномерные прибли

жения
некот
о
рыми нелинейными выражениями, например,
экспоненциальными





x

x

exp




1
0
,
лог
а
рифмическими





0
1

1


x

x

l








и др., для
которых доказаны соответству
ю
щие обменные теоремы и получены формулы для
пересчета п
а
раметров приближения 10.

Дл
я построения наилучшего равномерного приближения функции многих 
k
 пе

р
е
менных




X
f


k
x
,
,
x
f

1
, которая задана на множестве
N
точек






N
X
,
,
X

1
,
обо
б
щенными полиномами









i
i
i

X

X
F
1

используется метод, который явля

ется анал
о
гом метода п.ч.и. Е.Я. Ремеза решения задачи наилучшего чебышевского
приближения п
у
тем сведения этой задачи к
задаче линейного программирования
с
неотрицательными коэфф
и
циентами 5
,
11
.
В соответствующем алгоритме
реализуются
прямая
и
двойственная

з
а
дачи
линейного программирования. При этом
главная задача


двойственная
, решается м
о
дифицированным симплекс

методом с
учетом того, что на практике количество уравн
е
ний
N
значительно больше
коли

чества неизвестных

, и таблица
«
расширенного базиса
»
ра
з
мера


4




,

при
мо

ди
фицированном

симплекс

методе
существенно меньше опорной таблицы


N
,




прямого симплекс

метода.
Для большего повышения эффективности а
л
горитма и его
оптимизации по точности и скорости симплекс

таблица заменяется
сж
а
той
более
чем вдвое, но равноценной по поданной информации таблицей, которая уже соде
р

жит д
о
пустимое базисное решение. Кроме этого, в
процессе решения двойственной
за
дачи реал
и
зуется полуоптимальный вариант перехода от одного допустимого базис

ного
решения к следующему.

Каленчук

Порханова А.А.


«Искусственный интеллект»
3
’00
9

60


К

В некоторых случаях, особенно при приближении на больших отрезках, целе

со
о
б
разно использовать
кусочные приближения
. П
ри таком приближении, благодаря
разби
е
нию всего отрезка аппроксимации




,
на сегменты


i
i
t
,
t
1



,
i
1

,








t
t
t

1
0
 и приближении отдельно на каждом из них заданной функ

ц
ии
f
наилучшим равномерным аппроксимантом
*
F
, желаемая точность прибли
же

ния может быть обеспечена при мен
ь
ших значениях степени этого ап
п
роксиманта 10.

На протяжении многих лет автором в Институте кибернетики НАН Украины
ведутся
работы по алгоритмизации методов Е.Я. Ремеза, оценке всех видов погреш

ностей этих а
л
горитмов и по созданию соответствующих программных средств 1,
3

8, 10, 1.

Для разработанных алгоритмов и их программных реализаций автором полу

чены
оценки всех в
идов погрешностей
, а именно погрешности постановки задачи за
счет ди
с
кретного представления аппроксимируемой функции, неустранимой и вы

чис
лительной п
о
грешностей алгоритмов, а также по
л
ной абсолютной погрешности
решения этих задач. Это позволило значитель
но повысить точность результатов
вычислений в нек
о
торых случаях на порядок 8. Наряду с общепринятой схемой
оценки полной погрешности п.п. 13 а
в
тором предложена также
вторая схема
оценки
п.п., которая использует известные априо
р
ные сведения о структ
урных свойст

вах
функции, в частности о ее принадлежности к опр
е
деленному классу. При этом
получены
неулучшаемые
для некоторых классов функций
как априорные, так и
апостериорные мажорантные детерминированные оценки
всех видов погреш
нос

тей, расчеты которы
х включены в вычислительные схемы алгоритмов и пр
о
грамм.

Для определения значений указанных оценок п.п. решения чебышевской за

дачи а
в
тором были получены представляющие самостоятельный интерес вспомога

тельные
резул
ь
таты из ко
н
структивной теории функций
,
в том числе уточняющие
известные оценки венгерских авторов.

С целью существенного повышения эффективности разработанных в
ы
числи

тельных алгоритмов осуществлялись также различные процедуры для их моди

фик
а
ции, в том числе реализован подход, основанный на п
рименении сегментной
кусочной аппроксимации ра
з
ными классами аппроксимантов.

Главное преимущество разработанных автором алгоритмов заключается в том,
что с целью повышения их эффективности проведена
оптимизация по быстродей

ствию и по точности
.

Оптимиз
ация по быстродействию
достигается за счет следующих факторов:



алгоритмы основаны на методе последовательных чебышевских интерполяций
п.ч.и. Е.Я.

Ре
меза и относятся к алгоритмам подъема, при работе которых нижняя
граница выбранных на каждом шаге 



х
максимальных уклонений от функции
аппроксиманта порядка

не уменьшается на последующих шагах, что делает их
предпочтительнее по ск
о
рости сх
о
димости;



в алгоритмах также реализуется на практике один из трех возможных, а именно
опт
и
мальный вариант последов
ательной замены 



точечных наборов, на ко
то

рых осуществляются шаги ч.и., что обеспечивает квадратичную скорость сходи
мос

ти всего ит
е
рационного процесса и позволяет получать результат за 



3 ит
е
рации;



комбинированный алгоритм реализации дробно

ра
циональной аппроксимации п
о
з

воляет обеспечить сходимость п.ч.и. также и для дробно

рационального случая, при
этом сохраняются действия факторов опт
и
мизации для полиномиального случая.

Наилучшая чебышёвская аппроксимация к
ак эффективный сп
особ обработки…

«Штучний інтелект»

3
’00
9

61


К

Оптимизация по точности
осуществляется благодаря:



включению в вычислите
льную схему алгоритмов расчета как априорных, так и
ап
о
стериорных оценок полной погрешности, что позволяет корректировать получен

ные
р
е
зультаты, а именно в зав
и
симости от требуемой точности менять степень поли

нома
, число точек сетки, параметр критерия ос
танова и обоснованно выбирать вид
ап
проксиманта;



просмотру при исследованиях поведения уклонений полинома от функций на
ка
ж

дом шаге итерации при переходе к следующему шагу всех точек сетки, при этом учи

тыв
а
ются

как верхняя, так и нижняя
границы величины
наилучшего приближения;



использованию на каждом шаге чебышевских интерполяций для решения систем
линейных алгебраических уравнений метода Краута, для которого проведена опти

мизация по точности;



применению в алгоритме дробно

рациональной аппроксимации на
каждом


м шаге

ч
.и. для решения нелинейной системы уравнений относительно коэффициентов и
вели

чины наилучшего приближения специ
а
льного подхода, основанного на линеари
за
ции

системы и использовании метода с
е
кущей;



использование схемы Н.С. Бахвалова вмес
то схемы Горнера для уменьшения п
о
г

реш
ности округлений при вычислениях в точках значений полиномов степени боль

ше 10;



применению кусочно

полиномиальной аппроксимации для сжатия больших и
сверхбольших массивов числовых данных, что значительно повышает то
чность при

бли
ж
е
ния и обеспечивает высокие коэффициенты сжатия по сравнению с аппрокси

мацией без разбиения на сегме
н
ты.

В алгоритмах применялись также дополнительные приемы повышения их эф

фекти
в
ности:



решение задач аппроксимации как для дискретно, так и
для аналитически задан

ных функций, при этом дополнительно вводится процедура вычисления значений
функции в точках дискрет
и
зации;



проведение предварительной аппроксимации с целью повышения точности зна
ч
е

ний дискретных данных в случаях, когда известны с
войства исходной аппро
к
си
ми

руемой функции;



обеспечение двух «входов» в алгоритмы, что позволяет находить либо аппрокс
и

мант заданной фиксированной степени «вход» по степени, либо такой, который
обеспеч
и
вает заданную точность пр
и
ближения «вход» по точн
ости;



использование различных классов аппроксимирующих выражений, наиболее соо
т

ветствующих
х
а
рактеру поведения «природе» приближаемой функции;



постро
е
ние полиномиального приближения с произвольным весом


0

x
w
;



проверка в комбинированн
ом алгоритме решения дробно

рациональной задачи
п
е
ред началом каждой следующей итерации возможности появления случаев в
ы
рож

дения или почти вырождения, когда не удается получить нужное количество т
о
чек
экстремального базиса. Эти случаи в алгоритме распозна
ются до начала вычислений
вырожденного аппро
к
симанта, после чего подключаются средства для их устр
а

нения;



применение для аппроксимации функций многих переменных
модифи
цирован

ного симплекс

метода
и некоторых процедур, которые обеспечивают значительное
ум
еньшение количества вычи
с
лений и повышение точности результатов.

Каленчук

Порханова А.А.


«Искусственный интеллект»
3
’00
9

6


К

Выводы

Аппарат аппроксимации на протяжении многих лет использовался в сост
а
ве
прикладного программного обеспечения отечественных ЭВМ и применялся для сжа

тия массивов данных при решении разли
чных прикладных задач в том числе для
об
о
ронных целей, при расчётах характеристик сложных динамических систем,
например, при расчёте прочностных характеристик летательных аппаратов для НИИ
им. Туполева, расчетах трае
к
торий движения искусственных спутнико
в, транссект и
кривых трансконтинентальных п
е
реносов загрязнений воздушной среды, токовых
состояний водных систем водоемов, вод
о
токов, Черного моря в связи с послед
ст

виями Чернобыльской катастрофы и др.

В процессе применения аппарата наилучшей чебышев
ской аппроксимации бы
ла

не только подтверждена его высокая эффективность, но и проводилось даль
нейшее
усове
р
шенствование. Более подробная информация о работах содержится в приво

димых ссылках.

В результате численной реализации алгоритмов аппроксимации бы
ли разра

ботаны программные комплексы на языках программирования ФОРТРАН, А
л
гол,
Паскаль, а также на С для отечественного суперкомпьютера с кластерной архи

тектурой СКИТ. В состав прикладного программного обеспечения СКИТ включены
две библиотеки программ
: би
б
лиот
е
ка чебышевской аппроксимации функций одной
и многих переменных и библиотека для вычисления с повышенной точностью
значений элементарных и специальных фун
к
ций.

Аппарат чебышевской аппроксимации в последнее время применялся для сжа

тия
бол
ь
ших одно
мерных массивов

векторов
с возможным количеством значений
до 10 млн чисел с целью получения
небольшого числа параметров
аппроксимантов.
В результате расчётов были получены большие значения к
о
эффициентов сжатия в
среднем более двух порядков. Эти работы
выполнялись в рамках создания Под

системы аппроксимации для сжатия больших массивов числовых данных в составе
Информационно

аналитической си
с
темы «Бю
д
жетный комитет», а также в рамках
научно

технического проекта по разработке программно

технических комплек
сов для

решения расчётных задач АНТК «Ант
о
нов».

В настоящее время для СКИТ разрабатывается
пакет программ аппроксим
а
ции

функций одной и многих переменных разными способами приближения: интерпо
ля

цио
н
ным, среднеквадратичным и чебышевским 1, который вой
дет в состав его
Базового пр
и
кладного программного обеспечения. Этот пакет имеет ряд существен

ных преимуществ по сравнению с известными аналогичными п
а
кетами и специали

зи
рованными библиотеками, такими, например, как Mthc, Mple, MATLAB, Mth
e

mtic
,
MATHLIB, NETLIB.

Алгоритмы и соответствующие им программные реализации построения наи

луч
ших чебышёвских пр
и
ближений функций одной и нескольких переменных
исполь
зовались на протяжении многих лет для аналитической обработки массивов
данных в разных напра
вл
е
ниях науки и техники, в том числе для оборонной тема

тики. В последние годы аппарат ч
е
бышёвской аппроксимации широко применяется
в рамках научно

технического проекта по разработке программно

технических комп

лексов
для решения расчётных задач АНТК «А
н
т
онов», а также для сжатия больших
и сверхбольших массивов

век
торов с возможным к
о
личеством значений до 10 млн
Наилучшая чебышёвская аппроксимация к
ак эффективный сп
особ обработки…

«Штучний інтелект»

3
’00
9

63


К

чисел, что позво
ляет получать на практике большие знач
е
ния коэффициентов сжатия
в среднем два порядка. Программные комплексы на основе разрабо
тан
ных алго

ритмов включены в состав прикладного програм
много обеспечения с
у
перкомпью

тера СКИТ с кластерной архитектурой 3.

Литература

1.

Каленчук

Порханова А.А.
Аппарат аппроксимации для анализа и синтеза сложных систем
/
А.А.

Кален

чук

Порханова
// Пр.
Мі
ж
нар. конф.
«
50 років Інституту кібернетики ім.

В.М.

Глушкова НАН Украї
ни
».


Київ, 008.

С.

354

361.

.

Ремез Е.Я. Основы численных методов чебышевского приближения
/ Ремез

Е.Я.

К.

: Наук. думка,
1969.

63 с.

3.

Каленчук

Порханова А.А. Об одном алгори
тме полиномиальной чебышевской а
п
проксимации
/
А.А. Каленчук

Порханова
// Оптимиз
а
ция вычислительных методов.

К.

: Ин

т кибернетики АН
УССР, 1974 .

С. 45

51.

4.

Иванов В.В.
Об эффективности алгоритмов полиномиальных и дробно

рациональных чебышевских
прибл
ижений
/ В.В.

Иванов, А.А.

Каленчук
// Конструктивная теория функций.

София, 1983.



С. 7

77.

5.

Каленчук

Порханова А.А. Аппроксимация функций одной и многих переменных
/ А.А.

Каленчук

Порханова
// Численные методы для мн
о
гопроцессорного вычислительного к
омплекса ЕС.

М.

:
Изд

во ВВИА им. Н.Е.

Жуковского, 1987.

С. 366

395.

6.

Каленчук

Порханова А.А. Алгоритмы и анализ погрешности наилучшей чебыше
в
ской аппрокси
ма

ции о
д
ной переменной
/ А.А.

Каленчук

Порханова
// Теория приближения функций

:
т
р. Междунар.
к
онф. теории прибл
и
жения функций,

Калуга, 1975

.

М.
,

1977.

С.

13

18.

7.

Каленчук

Порханова А.А. Наилучшая чебышевская аппроксимация

алгоритмы и их применение
/
А.А. Каленчук

Порханова
// Сб. трудов Международного симп. «Питання оптим
і
зац
ії
обчислень»
.



Киев, 009.

8.

Каленчук

Порханова А.А. Алгоритмы реализации наилучшей чебышевской а
п
проксимации

повы

шение их эффективности

// Сб. трудов Международного симп. «Пита
н
ня оптим
і
зац
ії
обчислень»



К
и
ев, 009.

9.

Бахвалов Н.С. Численные методы
/
Бахвалов Н.С.


М.

: Наука, 1973.

631с.

10.

Кале
нчук

Порханова А.А.
Аппарат аппроксимации в составе пр
о
граммного обеспечения суперком

пьютера с кластерной архитектурой
/ А.А. Каленчук

Порханова, Л.П. Вакал
// Искусственный
и
н
те
л
лект.

009.

№ 1.

С. 158

165.

11.

Александрен
ко В.Л. Алгоритм построения приближённого равномерно

наи
лучшего решения систе

мы несовместных линейных уравнений
/ В.Л. Александренко
// Алгоритмы и алгоритм
и
ческие
языки.

М.

: ВЦ АН СССР, 1968.


Вып. 3.

С. 57

74.

1.

Каленчук

Порха
нова А.А.
Пакет програ
мм аппроксимации функций
/ А.А.

Каленчук

Порханова,
Л.П.

Вакал
// Ко
м
п

ютерні засоби, мережі і системи.

008.



7.

13.

Воеводин В.В. Ошибки округления и устойчивость в прямых методах линейной алгебры
/ В.В.

Вое

во
дин.



М. :
ВЦ МГУ, 1969.



А.О. Каленчу
к

Порханова


Н
айкраща

чебишовська апроксимація

як ефективний спосіб обробки інформації


Розглядається проблема найкращої чебишовської апроксимації для ефективної обробки інформації.
Нав
о
дяться об
ґ
рунтування переваг алгоритмів апроксимації, що пов’язано з ї
х оптимізацією
за
точн
і
ст
ю

та шви
д
коді
єю
.



А
.
Klechuk

okhov


The
Best
Cheyshev
’s

A
ppoximtio
fo
E
ffective
T
etmet of
I
fomtio

The polem of the est
C
heyshev
’s
ppoximtio fo effective tetmet of ifomtio
is

cosi

ee
. The


v
tes of the loithms elote
which e
coecte
with thei 
c
cucy  pefomce optimiztio

e pesete.


Статья поступила в редакцию 30.07.009.


Приложенные файлы

  • pdf 10996786
    Размер файла: 522 kB Загрузок: 0

Добавить комментарий