Наилучшая чебышевская аппроксимация функций одной и многих переменных
Розглянуто проблему найкращої чебишовської апроксимації. Наведено обґрунтування переваг алгоритмів апроксимації, пов’язаних з їх оптимізацією за точністю та швидкодією. The problem of the best Ñhebyshev approximation is discussed. It is justified that approximation algorithms that are optimized for...
Збережено в:
| Опубліковано в: : | Кибернетика и системный анализ |
|---|---|
| Дата: | 2009 |
| Автор: | |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2009
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/44495 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Наилучшая чебышевская аппроксимация функций одной и многих переменных / А.А. Каленчук-Порханова // Кибернетика и системный анализ. — 2009. — № 6. — С. 155-164. — Бібліогр.: 25 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-44495 |
|---|---|
| record_format |
dspace |
| spelling |
Каленчук-Порханова, А.А. 2013-06-02T09:43:42Z 2013-06-02T09:43:42Z 2009 Наилучшая чебышевская аппроксимация функций одной и многих переменных / А.А. Каленчук-Порханова // Кибернетика и системный анализ. — 2009. — № 6. — С. 155-164. — Бібліогр.: 25 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/44495 519.651.2 Розглянуто проблему найкращої чебишовської апроксимації. Наведено обґрунтування переваг алгоритмів апроксимації, пов’язаних з їх оптимізацією за точністю та швидкодією. The problem of the best Ñhebyshev approximation is discussed. It is justified that approximation algorithms that are optimized for accuracy and speed are advantageous. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Новые средства кибернетики, информатики, вычислительной техники и системного анализа Наилучшая чебышевская аппроксимация функций одной и многих переменных Найкраща чебишовська апроксимація функцій однієї та багатьох змінних Best Chebyshev approximation for functions of one and many variables Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Наилучшая чебышевская аппроксимация функций одной и многих переменных |
| spellingShingle |
Наилучшая чебышевская аппроксимация функций одной и многих переменных Каленчук-Порханова, А.А. Новые средства кибернетики, информатики, вычислительной техники и системного анализа |
| title_short |
Наилучшая чебышевская аппроксимация функций одной и многих переменных |
| title_full |
Наилучшая чебышевская аппроксимация функций одной и многих переменных |
| title_fullStr |
Наилучшая чебышевская аппроксимация функций одной и многих переменных |
| title_full_unstemmed |
Наилучшая чебышевская аппроксимация функций одной и многих переменных |
| title_sort |
наилучшая чебышевская аппроксимация функций одной и многих переменных |
| author |
Каленчук-Порханова, А.А. |
| author_facet |
Каленчук-Порханова, А.А. |
| topic |
Новые средства кибернетики, информатики, вычислительной техники и системного анализа |
| topic_facet |
Новые средства кибернетики, информатики, вычислительной техники и системного анализа |
| publishDate |
2009 |
| language |
Russian |
| container_title |
Кибернетика и системный анализ |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| format |
Article |
| title_alt |
Найкраща чебишовська апроксимація функцій однієї та багатьох змінних Best Chebyshev approximation for functions of one and many variables |
| description |
Розглянуто проблему найкращої чебишовської апроксимації. Наведено обґрунтування переваг алгоритмів апроксимації, пов’язаних з їх оптимізацією за точністю та швидкодією.
The problem of the best Ñhebyshev approximation is discussed. It is justified that approximation algorithms that are optimized for accuracy and speed are advantageous.
|
| issn |
0023-1274 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/44495 |
| citation_txt |
Наилучшая чебышевская аппроксимация функций одной и многих переменных / А.А. Каленчук-Порханова // Кибернетика и системный анализ. — 2009. — № 6. — С. 155-164. — Бібліогр.: 25 назв. — рос. |
| work_keys_str_mv |
AT kalenčukporhanovaaa nailučšaâčebyševskaâapproksimaciâfunkciiodnoiimnogihperemennyh AT kalenčukporhanovaaa naikraŝačebišovsʹkaaproksimacíâfunkcíiodníêítabagatʹohzmínnih AT kalenčukporhanovaaa bestchebyshevapproximationforfunctionsofoneandmanyvariables |
| first_indexed |
2025-11-25T13:48:21Z |
| last_indexed |
2025-11-25T13:48:21Z |
| _version_ |
1850516057203146752 |
| fulltext |
ÓÄÊ 519.651.2
À.À. ÊÀËÅÍ×ÓÊ-ÏÎÐÕÀÍÎÂÀ
ÍÀÈËÓ×ØÀß ×ÅÁÛØÅÂÑÊÀß ÀÏÏÐÎÊÑÈÌÀÖÈß
ÔÓÍÊÖÈÉ ÎÄÍÎÉ È ÌÍÎÃÈÕ ÏÅÐÅÌÅÍÍÛÕ
Êëþ÷åâûå ñëîâà: àïïðîêñèìàöèÿ, àëãîðèòìû, ÷åáûøåâñêèé àëüòåðíàíñ, îöåíêè
ïîãðåøíîñòåé, îïòèìèçàöèÿ, ñæàòèå ìàññèâîâ äàííûõ.
ÂÂÅÄÅÍÈÅ
Òðóäíîñòè, âîçíèêàþùèå ïðè îáðàáîòêå ìàññèâîâ äàííûõ ïðè ðåøåíèè òàêèõ ïðè-
êëàäíûõ çàäà÷, êàê ìàòåìàòè÷åñêîå ìîäåëèðîâàíèå è ïðîãíîçèðîâàíèå, õðàíåíèå
áîëüøèõ îáúåìîâ èíôîðìàöèè è èõ ñêîðîñòíàÿ ïåðåäà÷à ïî êàíàëàì ñâÿçè, à òàê-
æå ïîëó÷åíèå íåîáõîäèìûõ äîïîëíèòåëüíûõ äàííûõ î ôóíêöèîíàëüíûõ çàâèñè-
ìîñòÿõ íà «íåîñâåùåííûõ çàìåðàìè ó÷àñòêàõ», îáóñëîâëèâàþò ïîòðåáíîñòü â àíà-
ëèòè÷åñêîé îáðàáîòêå áîëüøèõ ïîòîêîâ èíôîðìàöèè è îïðåäåëÿþò âîñòðåáîâàí-
íîñòü è àêòóàëüíîñòü ýòîé ïðîáëåìû. Åå ðåøåíèå äîñòèãàåòñÿ ïóòåì
èñïîëüçîâàíèÿ ðàçíûõ ñïîñîáîâ àíàëèòè÷åñêîé îáðàáîòêè ìàññèâîâ â öåëÿõ èõ
ïðèáëèæåííîãî ïðåäñòàâëåíèÿ (àïïðîêñèìàöèè) â âèäå àíàëèòè÷åñêèõ âûðàæåíèé
(àïïðîêñèìàíòîâ) ñ íåáîëüøèì êîëè÷åñòâîì ïàðàìåòðîâ. Ïî ñðàâíåíèþ ñ èíòåðïîëÿ-
öèîííûì è ñðåäíåêâàäðàòè÷íûì ïðèáëèæåíèÿìè ñïîñîá íàèëó÷øåé ÷åáûøåâñêîé
àïïðîêñèìàöèè íàèáîëåå ýôôåêòèâåí è óíèâåðñàëåí è îáëàäàåò îñîáåííûì ñâî-
éñòâîì íå òîëüêî ïîëó÷àòü âûñîêóþ òî÷íîñòü àïïðîêñèìàöèè â òî÷êàõ äèñêðåòíî-
ãî ïðåäñòàâëåíèÿ ôóíêöèîíàëüíûõ çàâèñèìîñòåé, íî è îáåñïå÷èâàòü òàêóþ òî÷-
íîñòü âî âñåõ òî÷êàõ íåïðåðûâíîãî èíòåðâàëà èõ çàäàíèÿ. Ýòî ïîçâîëÿåò ðåøàòü
ñ âûñîêîé òî÷íîñòüþ êàê ïðÿìóþ çàäà÷ó ñæàòèÿ ìàññèâîâ äàííûõ ñ áîëüøèìè êî-
ýôôèöèåíòàìè ñæàòèÿ, òàê è îáðàòíóþ çàäà÷ó ïîëó÷åíèÿ íîâûõ çíà÷åíèé äèñêðåò-
íîãî ïðåäñòàâëåíèÿ èñõîäíûõ ôóíêöèîíàëüíûõ çàâèñèìîñòåé.
Îñíîâû òåîðèè íàèëó÷øåãî ðàâíîìåðíîãî ïðèáëèæåíèÿ ôóíêöèé çàëîæåíû
Ï.Ë. ×åáûøåâûì (1821–1894) [1] è ðàçâèòû â íà÷àëå ïðîøëîãî ñòîëåòèÿ â ðàáîòàõ
Ñ.Í. Áåðíøòåéíà, Ï. Êèðõáåðãà, Ø.-Æ. Âàëëå-Ïóññåíà.
Ñèñòåìàòè÷åñêàÿ ðàçðàáîòêà îáùèõ ÷èñëåííûõ ïîäõîäîâ äëÿ ðåøåíèÿ çàäà÷è ÷å-
áûøåâñêîãî ïðèáëèæåíèÿ íà÷àëàñü òîëüêî â 1933–1934 ãã. ñ ïîÿâëåíèåì ôóíäàìåí-
òàëüíûõ ðàáîò Å.ß. Ðåìåçà [2], ïðåäëîæèâøåãî äâà òåîðåòè÷åñêè îáîñíîâàííûõ ìåòî-
äà (ïåðâûé è âòîðîé), îñíîâàííûå íà ñïîñîáå ïîñëåäîâàòåëüíûõ ÷åáûøåâñêèõ ïðèáëè-
æåíèé. Îäíàêî âû÷èñëèòåëüíàÿ ñëîæíîñòü ìîùíîãî àïïàðàòà ÷åáûøåâñêîé
àïïðîêñèìàöèè, êîòîðûé îõâàòûâàë òàêèå ðàçäåëû ÷èñëåííîãî àíàëèçà, êàê ðåøåíèå
ñèñòåì ëèíåéíûõ, íåëèíåéíûõ è äèôôåðåíöèàëüíûõ óðàâíåíèé, àëãåáðó ìàòðèö, äåé-
ñòâèÿ ñ öåïíûìè äðîáÿìè è ìíîãî÷ëåíàìè, áóëåâó àëãåáðó, ñ îäíîé ñòîðîíû, è îãðàíè-
÷åííûå âîçìîæíîñòè ñóùåñòâîâàâøèõ íà òîò ïåðèîä âû÷èñëèòåëüíûõ ñðåäñòâ — ñ äðó-
ãîé, íå ïîçâîëÿëè ïîëó÷àòü íà ïðàêòèêå íàèëó÷øèå àïïðîêñèìàíòû. Âîçìîæíîñòü
÷èñëåííîé ðåàëèçàöèè àïïàðàòà â öåëîì ïîÿâèëàñü òîëüêî ñ ñîçäàíèåì êîìïüþòåðîâ.
 1951 ã. â Êèåâå áûëà ñîçäàíà ïåðâàÿ â Åâðîïå Ìàëàÿ ýëåêòðîííàÿ ñ÷åòíàÿ ìàøèíà
ÌÝÑÌ, à íà÷èíàÿ ñ êîíöà 1950-õ ãã. áûñòðî óâåëè÷èâàëñÿ ïàðê îòå÷åñòâåííûõ ÝÂÌ —
«Êèåâ», «Ñòðåëà», «Óðàë», Ì-20, Ì-220, ðÿä ÝÂÌ òèïà ÁÝÑÌ è äð. Ê ýòîìó âðåìåíè â
Èíñòèòóòå êèáåðíåòèêè ïîä ðóêîâîäñòâîì Å.Ë. Þùåíêî óæå óñïåøíî ðàáîòàë ñîçäàí-
íûé åþ èç âûïóñêíèêîâ ìåõàíèêî-ìàòåìàòè÷åñêîãî ôàêóëüòåòà Êèåâñêîãî ãîñóäàðñòâåí-
íîãî óíèâåðñèòåòà èì. Ò.Ã. Øåâ÷åíêî ïåðâûé â Óêðàèíå îòäåë ïðîãðàììèðîâàíèÿ, êîòî-
ðîìó ïîðó÷àëîñü âûïîëíåíèå òàêèõ âàæíûõ ãîñóäàðñòâåííûõ çàäà÷, êàê ðàñ÷åòû õàðàêòå-
ðèñòèê ýíåðãîñèñòåì ÑÑÑÐ, òðàåêòîðèé äâèæåíèÿ ïëàíåò, îïòèìèçàöèè ïðîôèëåé
àâòîìîáèëüíûõ è æåëåçíûõ äîðîã, ñåéñìîñòîéêîñòè áàëîê è ïåðåêðûòèé è äð.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 6 155
© À.À. Êàëåí÷óê-Ïîðõàíîâà, 2009
 1958 ã. Å.ß. Ðåìåç îáðàòèëñÿ ñ ïðîñüáîé ê Â.Ì. Ãëóøêîâó ïîäêëþ÷èòü ìàòåìà-
òèêîâ-ïðîãðàììèñòîâ ê ðåøåíèþ çàäà÷ ÷åáûøåâñêîé àïïðîêñèìàöèè. Â.Ì. Ãëóøêîâ
ïîðó÷èë ýòó ðàáîòó îòäåëó Å.Ë. Þùåíêî. Íåïîñðåäñòâåííûìè èñïîëíèòåëÿìè ýòèõ
ðàáîò áûëè íàçíà÷åíû ñîòðóäíèêè îòäåëà ïðîãðàììèðîâàíèÿ Â.À. Àëåêñàíäðåíêî è
àâòîð äàííîé ñòàòüè. Å.Ë. Þùåíêî óäåëÿëà ýòèì ðàçðàáîòêàì áîëüøîå âíèìàíèå,
ïîä÷åðêèâàëà èõ çíà÷èìîñòü è ñïîñîáñòâîâàëà óñïåøíîìó âûïîëíåíèþ.
Ïåðâûå ðåçóëüòàòû ïî ñîçäàíèþ àëãîðèòìîâ ðàâíîìåðíî-íàèëó÷øèõ ïîëèíîìè-
àëüíûõ àïïðîêñèìàíòîâ ôóíêöèé îäíîé ïåðåìåííîé è ïðèáëèæåííîãî ðåøåíèÿ ñèñòåì
íåñîâìåñòèìûõ óðàâíåíèé áûëè äîëîæåíû â 1961 ã. íà IV Ìåæäóíàðîäíîì ìàòåìàòè-
÷åñêîì ñúåçäå â Ëåíèíãðàäå. Ýòè èññëåäîâàíèÿ ðàçâèâàëèñü â íàïðàâëåíèè ðàñøèðåíèÿ
êëàññîâ àïïðîêñèìàíòîâ è èõ êîìïüþòåðíûõ ðåàëèçàöèé íà ÿçûêàõ ïðîãðàììèðîâàíèÿ,
àíàëèçà âñåõ âèäîâ ïîãðåøíîñòåé àëãîðèòìîâ è èõ îïòèìèçàöèè ïî áûñòðîäåéñòâèþ è
òî÷íîñòè. Çíà÷èòåëüíàÿ ýôôåêòèâíîñòü ðàçðàáîòàííûõ àëãîðèòìîâ è ïðîãðàìì íå-
îäíîêðàòíî ïîäòâåðæäåíà ìíîãî÷èñëåííûìè ïðàêòè÷åñêèìè ïðèìåíåíèÿìè.
Îñîáî îòìåòèì, ÷òî âñå âîçðàñòàþùàÿ àêòóàëüíîñòü è âîñòðåáîâàííîñòü ìîùíî-
ãî àïïàðàòà íàèëó÷øåé ÷åáûøåâñêîé àïïðîêñèìàöèè îáóñëîâëåíà òåì, ÷òî ó èñòîêîâ
âûïîëíåíèÿ â Èíñòèòóòå êèáåðíåòèêè ýòèõ ðàáîò ñòîÿëè òàêèå êîðèôåè íàóêè ñ ãåíè-
àëüíîé íàó÷íîé ïðîçîðëèâîñòüþ, êàê Åâãåíèé ßêîâëåâè÷ Ðåìåç, Âèêòîð Ìèõàéëîâè÷
Ãëóøêîâ è Åêàòåðèíà Ëîãâèíîâíà Þùåíêî.
ÏÎÑÒÀÍÎÂÊÀ ÇÀÄÀ×È
Ïðîáëåìà íàèëó÷øåé (ðàâíîìåðíîé) ÷åáûøåâñêîé àïïðîêñèìàöèè ôóíêöèè f x( )
íà èíòåðâàëå [ , ]a b îñíîâàíà íà ÷åáûøåâñêîì ïðèíöèïå ìèíèìèçàöèè âåëè÷èíû
ìåðû ðàâíîìåðíîãî ïðèáëèæåíèÿ L H f x H x An
x a b
n[ ] max | ( ) ( ; ) |
[ , ]
� �
�
è ñîñòîèò â íà-
õîæäåíèè òàêîãî àïïðîêñèìàíòà ñòåïåíè n ñ íàáîðîì êîýôôèöèåíòîâ
A a a an� ( , , , )0 1 � èç âñåé ñîâîêóïíîñòè àïïðîêñèìàíòîâ Hn ñòåïåíè � n, êîòîðûé
óäîâëåòâîðÿåò óñëîâèþ ìèíèìàêñà L Hn[ ] min� , ãäå f x( ) — íåïðåðûâíàÿ íà [ , ]a b
ôóíêöèÿ, min [ ]
H
n
n
L H — íàèìåíüøåå âîçìîæíîå çíà÷åíèå ìåðû ðàâíîìåðíîãî ïðè-
áëèæåíèÿ.
 êà÷åñòâå H x An ( ; ) ðàññìîòðèì êëàññû Pn âñåõ ïîëèíîìîâ ñòåïåíè íå âûøå n
âèäà P x a x P x An i
i
i
n
n( ) ( ; )� �
�
�
0
è êëàññû rn âñåõ äðîáíî-ðàöèîíàëüíûõ âûðàæåíèé ïî-
ðÿäêà n l m� � âèäà r x P x Q x r x A Bn l m n( ) ( ) / ( ) ( ; ; )� � , ãäå P xl ( ) è Q xm( ) — ïîëèíîìû
ñòåïåíåé l è m ñ íàáîðàìè ñîîòâåòñòâåííî êîýôôèöèåíòîâ A ai� { }, i l� 0, , è
B b j� { }, j m� 0, . Òîãäà ïîñòàíîâêà çàäà÷è íàõîæäåíèÿ íàèëó÷øèõ ÷åáûøåâñêèõ àï-
ïðîêñèìàíòîâ èìååò âèä
max | ( ) ( ; ) | [ ] min
[ , ]x a b
n n
P
f x P x A L P
n�
� � � , min [ ] [ ( )]
P
n n
n
L P L x� � � , (1)
max | ( ) ( ; ; ) | [ ] min
[ , ]x a b
n n
r
f x r x A B L r
n�
� � � , min [ ] [ ( )]
r
n n
n
L r L R x� � � , (2)
ãäå n x( ) è R xn ( ) — ïîëèíîìèàëüíûé è äðîáíî-ðàöèîíàëüíûé íàèëó÷øèå ÷åáû-
øåâñêèå àïïðîêñèìàíòû, à � è � — ñîîòâåòñòâåííî âåëè÷èíû èõ íàèëó÷øèõ ïðè-
áëèæåíèé.
Ñóùåñòâîâàíèå, åäèíñòâåííîñòü è ñâîéñòâà íàèëó÷øèõ àïïðîêñèìàíòîâ âûòåêà-
þò èç êëàññè÷åñêèõ òåîðåì Ý. Áîðåëÿ è Ï.Ë. ×åáûøåâà [3, ñ. 49, 50–56] — äëÿ ïîëè-
íîìèàëüíûõ àïïðîêñèìàíòîâ è Í.È. Àõèåçåðà è Ï.Ë. ×åáûøåâà [4, ñ. 64, 66] — äëÿ
äðîáíî-ðàöèîíàëüíûõ. Íà îñíîâàíèè ýòèõ òåîðåì åäèíñòâåííûå ðåøåíèÿ çàäà÷ (1) è
(2) ñîâïàäàþò ñîîòâåòñòâåííî ñ ðåøåíèÿìè «ýëåìåíòàðíûõ» çàäà÷ âèäà
max | ( ) ( ; ) | �
x X
nf x P x A
�
� �
1
� , (1')
max | ( ) ( ; ; ) | �
x X
nf x r x A B
�
� �
2
� (2')
156 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 6
íà òàêèõ ( )n � 2 -òî÷å÷íûõ ïîäìíîæåñòâàõ X X a b1 2,
[ , ] , äëÿ êîòîðûõ âåëè÷èíû ��
è �� äîñòèãàþò ñâîèõ íàèáîëüøèõ âîçìîæíûõ çíà÷åíèé, ðàâíûõ � è �.
Êàæäàÿ èç òàêèõ ( )n � 2 -òî÷å÷íûõ çàäà÷ íàçûâàåòñÿ çàäà÷åé ÷åáûøåâñêîé èíòåð-
ïîëÿöèè ôóíêöèè f x( ) íà ìíîæåñòâå n � 2 òî÷åê, êîòîðûå ÿâëÿþòñÿ ñîîòâåòñòâåííî
÷åáûøåâñêèì àëüòåðíàíñîì äëÿ ïîëèíîìèàëüíîé çàäà÷è (1) è ýêñòðåìàëüíûì áàçèñîì
äëÿ äðîáíî-ðàöèîíàëüíîé çàäà÷è (2). Èìåííî ýòî çàìå÷àòåëüíîå «ñâîéñòâî ÷åáûøåâ-
ñêîãî àëüòåðíàíñà» ñëóæèò òåîðåòè÷åñêîé îñíîâîé äëÿ íàõîæäåíèÿ âñåõ íàèëó÷øèõ
÷åáûøåâñêèõ ïðèáëèæåíèé.
Âñå èçâåñòíûå ñïîñîáû ðåøåíèÿ ÷åáûøåâñêîé çàäà÷è ìîæíî â îñíîâíîì ðàçäå-
ëèòü íà ñïîñîáû, îñíîâàííûå íà ðàñïðîñòðàíåíèè ìåòîäîâ Å.ß. Ðåìåçà (îñîáåííî
âòîðîãî), è íà ñïîñîáû, èñïîëüçóþùèå àïïàðàòû ëèíåéíîãî è âûïóêëîãî ïðîãðàììè-
ðîâàíèÿ. Äëÿ ðåøåíèÿ äðîáíî-ðàöèîíàëüíîé çàäà÷è ïðèìåíÿþòñÿ è ðàçëè÷íûå ïðèå-
ìû ïîñëåäîâàòåëüíîé äèôôåðåíöèàëüíîé ëèíåàðèçàöèè ïî ïàðàìåòðàì-êîýôôèöèåí-
òàì. Ñèíòåçîì ìíîãèõ íàïðàâëåíèé â ïîñëåäíèå ãîäû ÿâèëàñü òàêæå òåîðèÿ
ñïëàéíîâîé àïïðîêñèìàöèè [5].
Ïðåèìóùåñòâà ìåòîäîâ Ðåìåçà ñîñòîÿò â ñðàâíèòåëüíî áûñòðîé ñêîðîñòè ñõîäè-
ìîñòè (â íåêîòîðûõ ñëó÷àÿõ êâàäðàòè÷íîé) è âîçìîæíîñòè ñòàíäàðòèçàöèè âû÷èñëå-
íèé, ÷òî î÷åíü âàæíî äëÿ ýôôåêòèâíîñòè èõ ÷èñëåííûõ ðåàëèçàöèé.
Ìåòîä Ðåìåçà ðåøåíèÿ çàäà÷ (1) è (2) îñíîâàí íà ïîñëåäîâàòåëüíûõ ÷åáûøåâ-
ñêèõ èíòåðïîëÿöèÿõ (ï.÷.è.), r øàãîâ êîòîðûõ ñâîäÿòñÿ ê íàõîæäåíèþ ïîñëåäîâàòåëü-
íîñòè ( )n � 2 -òî÷å÷íûõ S -íàáîðîâ S xr
r� { }�
( ) , � � �0 1, n , ñõîäÿùåéñÿ ê èñêîìîìó ÷å-
áûøåâñêîìó àëüòåðíàíñó èëè ýêñòðåìàëüíîìó áàçèñó, è ðåøåíèþ íà êàæäîì j-ì
øàãå ñèñòåì àëãåáðàè÷åñêèõ óðàâíåíèé
f x P xj
n j
j
j( ) ( ) ( )( )
,
( )
� �
� �� � � �1 , (3)
w x f x P x Q xj j
l j
j
m j
j( )[ ( ) ( ) / ( )] ( )( ) ( )
,
( )
,
( )
� � � �
� �� � � �1 j , (4)
ñîîòâåòñòâåííî ëèíåéíûõ îòíîñèòåëüíî êîýôôèöèåíòîâ ak , k n� 0, , ïîëèíîìà
P xn j, ( ) è âåëè÷èíû ��j â çàäà÷å (3) è íåëèíåéíûõ îòíîñèòåëüíî êîýôôèöèåíòîâ ai ,
i l� 0, , bi , i m� 0, , è âåëè÷èíû �� j â çàäà÷å (4), x S j� , � � �0 1, n .
Çàìåòèì, ÷òî â îòëè÷èå îò ïîëèíîìèàëüíîãî ñëó÷àÿ ñõîäèìîñòü ÷åáûøåâñêèõ èí-
òåðïîëÿöèé â çàäà÷å (4) òåîðåòè÷åñêè îáåñïå÷èâàåòñÿ íå ïðè ëþáîì íà÷àëüíîì íàáîðå
n � 2 òî÷åê, õîòÿ ïðèìåíåíèå èçâåñòíûõ â ëèòåðàòóðå ÷èñëåííûõ ðåàëèçàöèé (äàæå óïðî-
ùåííûõ âàðèàíòîâ ìåòîäà Ðåìåçà) ïîêàçàëî êðàéíå ðåäêóþ èõ «íåñõîäèìîñòü».
Îñíîâíàÿ òðóäíîñòü âñåõ ÷èñëåííûõ ðåàëèçàöèé ï.÷.è. ñîñòîèò â âûáîðå ( )n � 2 -
òî÷å÷íûõ ïîäìíîæåñòâ îáëàñòè àïïðîêñèìàöèè, íà êîòîðûõ âûïîëíÿþòñÿ øàãè ÷åáû-
øåâñêèõ èíòåðïîëÿöèé. Îò ñïîñîáà ýòîãî âûáîðà çàâèñèò íå òîëüêî ñêîðîñòü ñõîäè-
ìîñòè âñåãî ìåòîäà, íî è ñàì ôàêò åãî ñõîäèìîñòè. Âîçìîæíû òðè êëàññà âàðèàíòîâ
ïîñëåäîâàòåëüíîé çàìåíû óêàçàííûõ ( )n � 2 -òî÷å÷íûõ íàáîðîâ: îïòèìàëüíûé, ïîëó-
îïòèìàëüíûé è äîïóñòèìûé.
 îïòèìàëüíîì âàðèàíòå äëÿ íåêîòîðûõ êëàññîâ ôóíêöèé îáåñïå÷èâàåòñÿ êâàäðà-
òè÷íàÿ ñêîðîñòü ñõîäèìîñòè, ÷òî íà ïðàêòèêå äàåò, êàê ïðàâèëî, âñåãî îäíó-äâå èòåðà-
öèè, â ïîëóîïòèìàëüíîì — ÷èñëî èòåðàöèé äëÿ ïîëó÷åíèÿ àíàëîãè÷íîãî ýôôåêòà
îêàçûâàåòñÿ â íåñêîëüêî ðàç áîëüøå, à â äîïóñòèìîì — ìîæåò áûòü âî ìíîãî ðàç
áîëüøå [2, ñ. 79]. Ïðåäëîæåííûå àëãîðèòìû îñíîâàíû íà âòîðîì ìåòîäå ï.÷.è. Ðåìåçà
è îáëàäàþò ïðåèìóùåñòâàìè ïî ñðàâíåíèþ ñ àíàëîãè÷íûìè ðåàëèçàöèÿìè [6, 7]. Äîñ-
òîèíñòâîì ýòèõ àëãîðèòìîâ ÿâëÿåòñÿ ðàçðàáîòêà îïòèìàëüíîãî ñïîñîáà çàìåíû
( )n � 2 -òî÷å÷íûõ íàáîðîâ ïðè ïåðåõîäå ê íîâîìó S -íàáîðó [8].
ÏÎËÈÍÎÌÈÀËÜÍÀß ÀÏÏÐÎÊÑÈÌÀÖÈß
Ïóñòü çàäàíà ôóíêöèÿ f x
�
( ), íåïðåðûâíàÿ íà îòðåçêå E a b� [ , ] , è Hn — ìíîæåñò-
âî âñåõ ïîëèíîìîâ P xn ( ) ñòåïåíè � n. Ïóñòü òàêæå n nx H( ) � — ïîëèíîì íàèëó÷-
øåé ÷åáûøåâñêîé àïïðîêñèìàöèè f x( ) íà âñåì îòðåçêå E, äàþùèé ìàêñèìàëüíîå
óêëîíåíèå �, ò.å.
� � � � �
� �
� �
min max | ( ) ( ) | max | ( ) ( ) |
H x E
n
x E
n
n
f x P x f x x . (5)
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 6 157
Åñëè çàìåíèòü îòðåçîê E íåêîòîðîé ñåòêîé E EN
, òî ïî àíàëîãèè ïóñòü n x( )
— ïîëèíîì íàèëó÷øåé ÷åáûøåâñêîé àïïðîêñèìàöèè f x( ) íà ñåòêå EN , äàþùèé ìàê-
ñèìàëüíîå óêëîíåíèå �, ò.å.
� � � � �
� �
min max | ( ) ( ) | max | ( ) ( ) |
H x E
n
x E
n
n N N
f x P x f x x . (6)
Äëÿ íåïðåðûâíîé çàäà÷è (5) îáåñïå÷èâàåòñÿ êâàäðàòè÷åñêàÿ ñêîðîñòü ñõîäèìîñ-
òè.  ñëó÷àå ñåòî÷íîé çàäà÷è (6) êîíå÷íîñòü âñåãî ïðîöåññà ï.÷.è. ãàðàíòèðîâàíà òåì,
÷òî ñïîñîá çàìåíû îáåñïå÷èâàåò íåïîâòîðÿåìîñòü íàáîðà { }xi
j
i
n( )
�
�
0
1 äëÿ ðàçëè÷íûõ j, à
çíà÷èò, ÷èñëî âñåõ âîçìîæíûõ ( )n � 2 -òî÷å÷íûõ íàáîðîâ íà ñåòêå EN êîíå÷íî.
Ïðè âûáîðå êàæäîãî ïîñëåäóþùåãî íàáîðà S j�1 ïðîèñõîäèò ïîëíàÿ çàìåíà ïðåä-
ûäóùåãî, ïðè÷åì áåðóòñÿ òî÷êè, ñîîòâåòñòâóþùèå n � 2 ñàìûì áîëüøèì óêëîíåíèÿì
àïïðîêñèìàíòà îò ôóíêöèè ñ ó÷åòîì ÷åðåäîâàíèÿ çíàêîâ, è â ðåçóëüòàòå âûáèðàåòñÿ
èñêîìûé íàáîð ÷åáûøåâñêîãî àëüòåðíàíñà, íà êîòîðîì èùåòñÿ íàèëó÷øèé ïîëèíîì
P xn j, ( ) ñ âåëè÷èíîé íàèëó÷øåãî ïðèáëèæåíèÿ �.
Äëÿ ðåøåíèÿ ïîëèíîìèàëüíîé çàäà÷è ðàçðàáîòàíû äâà àëãîðèòìà («À» è «Á»),
ñîîòâåòñòâóþùèå çàïèñÿì àïïðîêñèìèðóþùåãî ïîëèíîìà â ôîðìàõ a xi
i
i
n
�
�
0
äëÿ àëãî-
ðèòìà «À» è b T xi i
i
n
( )
�
�
0
äëÿ àëãîðèòìà «Á».
Àëãîðèòì «Á» ñîçäàí êàê ìîäèôèêàöèÿ àëãîðèòìà «À» â ñâÿçè ñ ðàáîòîé
Í.Ñ. Áàõâàëîâà [9] è ïðèìåíåí äëÿ ñóùåñòâåííîãî óëó÷øåíèÿ àëãîðèòìà «À», ïîñêîëü-
êó èñïîëüçóåìàÿ â àëãîðèòìå «À» ïðèâû÷íàÿ çàïèñü ïîëèíîìà â âèäå a xi
i
i
n
�
�
0
ïðè áîëü-
øîì «ðàçáðîñå» çíà÷åíèé êîýôôèöèåíòîâ ai ìîæåò ñòàòü èñòî÷íèêîì áîëüøîé ïîãðåø-
íîñòè îêðóãëåíèé ïðè âû÷èñëåíèè çíà÷åíèé ïîëèíîìà â òî÷êàõ ïî ñõåìå Ãîðíåðà.
 ïðåäëîæåííîì Í.Ñ. Áàõâàëîâûì àëãîðèòìå èñïîëüçîâàíà çàïèñü ìíîãî÷ëåíîâ â âèäå
ëèíåéíîé êîìáèíàöèè ìíîãî÷ëåíîâ ×åáûøåâà Q x b T xn i i
i
n
( ) ( )�
�
�
0
. Ýòî ïîçâîëÿåò ñóùåñ-
òâåííî óìåíüøèòü óêàçàííóþ ïîãðåøíîñòü ïðè âû÷èñëåíèè çíà÷åíèé ïîëèíîìà.  ðå-
çóëüòàòå àíàëèçà ïîëíûõ ïîãðåøíîñòåé àëãîðèòìîâ «À» è «Á» óñòàíîâëåíî, ÷òî ïðåèìó-
ùåñòâî àëãîðèòìà «Á» ñòàíîâèòñÿ îùóòèìûì ïðè ñòåïåíÿõ n � 0; ïðè n � 0 îáà àëãîðèòìà
ïðèìåðíî ðàâíîñèëüíû.
Àëãîðèòìû ìîãóò ðàáîòàòü êàê äëÿ àíàëèòè÷åñêè çàäàííîé, òàê è äëÿ äèñêðåòíî
çàäàííîé ôóíêöèè f x( ).  îáîèõ ñëó÷àÿõ ïðîöåäóðà âûáîðà ( )n � 2 -òî÷å÷íîãî íàáîðà
íà êàæäîì øàãå ÷.è. ïðåäïîëàãàåò äèñêðåòèçàöèþ, ïîýòîìó èõ îòëè÷èå ñîñòîèò òîëü-
êî â òîì, ÷òî âî âòîðîì èç íèõ çíà÷åíèÿ ôóíêöèè â íóæíûõ òî÷êàõ èçâåñòíû, à â ïåð-
âîì ïðåäóñìàòðèâàåòñÿ ïðîöåäóðà èõ âû÷èñëåíèÿ.
ÄÐÎÁÍÎ-ÐÀÖÈÎÍÀËÜÍÀß ÀÏÏÐÎÊÑÈÌÀÖÈß
Êîãäà «ïðèðîäà» ïðèáëèæàåìîé ôóíêöèè f x( ) òàêîâà, ÷òî îíà íà íåêîòîðûõ ó÷àñ-
òêàõ èìååò «âñïëåñêè», òî äëÿ ïîâûøåíèÿ òî÷íîñòè ïðèáëèæåíèÿ öåëåñîîáðàçíî
èñïîëüçîâàòü àïïðîêñèìàöèþ ðàöèîíàëüíûìè äðîáÿìè, êîòîðûå íàèáîëåå òî÷íî
îòîáðàæàþò îñîáåííîñòè ïîâåäåíèÿ ôóíêöèè.
Ïóñòü
n — êëàññ âñåõ ðàöèîíàëüíûõ äðîáåé âèäà
r x P x Q x a x b xn l m i
i
i
l
j
j
j
m
( ) ( ) / ( ) /� �
� �
� �
0 0
, (7)
ãäå l è m — çàäàííûå ñòåïåíè, à n l m� � — ïîðÿäîê r xn ( ) .
Çàäà÷à íåëèíåéíîé íàèëó÷øåé ÷åáûøåâñêîé àïïðîêñèìàöèè ñîñòîèò â íàõîæäå-
íèè òàêèõ ïàðàìåòðîâ { }ai i
l
�0 è { }bj j
m
�0 âûðàæåíèÿ (7), ÷òîáû
min max | ( )[ ( ) ( )] | max | ( ) ( ) |
� �
� � � �
n x E
n
x E
nw x f x r x f x R x �n . (8)
158 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 6
Òîãäà R xn ( ) — íàèëó÷øèé äðîáíî-ðàöèîíàëüíûé ÷åáûøåâñêèé àïïðîêñèìàíò ñ âå-
ëè÷èíîé íàèëó÷øåãî ïðèáëèæåíèÿ �n.
Âåñîâàÿ ôóíêöèÿ w x( ) , èìåþùàÿ âàæíîå çíà÷åíèå ïðè áîëüøèõ êîëåáàíèÿõ f x( )
íà ñåòêå, ïðåäïîëàãàåòñÿ ïîëîæèòåëüíîé.  ÷àñòíîñòè, êîãäà l � 0 è w x( ) � 1, èìååì
ïîëèíîìèàëüíûé ñëó÷àé.
Ïîñêîëüêó ïåðåõîä îò ïîëèíîìîâ ê äðîáíî-ðàöèîíàëüíûì ôóíêöèÿì ðàñøèðÿåò
êëàññ ÷åáûøåâñêèõ àïïðîêñèìàíòîâ, î÷åâèäíî, ÷òî � �n n� , ãäå �n — âåëè÷èíà íàè-
ëó÷øåãî ïîëèíîìèàëüíîãî ïðèáëèæåíèÿ òîé æå ôóíêöèè íà òîì æå ñàìîì îòðåçêå E .
Íåñìîòðÿ íà òî ÷òî ïåðåõîä îò ïîëèíîìèàëüíûõ àïïðîêñèìàíòîâ ê äðîáíî-ðàöè-
îíàëüíûì íå ïîçâîëÿåò óâåëè÷èòü ïîðÿäîê ñòðåìëåíèÿ ê íóëþ âåëè÷èíû �n äëÿ âñåãî
êëàññà ôóíêöèé, ìîæíî óòâåðæäàòü, ÷òî áëàãîäàðÿ ýòîìó ïåðåõîäó ðàñøèðÿåòñÿ êëàññ
ôóíêöèé, äëÿ êîòîðûõ âåëè÷èíà íàèëó÷øåãî ïðèáëèæåíèÿ áóäåò òîãî æå ïîðÿäêà, ÷òî
è äëÿ «õîðîøèõ» ôóíêöèé.
Çàìåòèì, ÷òî â îòëè÷èå îò ïîëèíîìèàëüíîãî ñëó÷àÿ ñõîäèìîñòü ï.÷.è. (ïðè÷åì,
êàê ïðàâèëî, êâàäðàòè÷åñêàÿ) äëÿ çàäà÷è (7), (8) ñîãëàñíî ðàáîòàì À. Ðàëüñòîíà [10]
ìîæåò áûòü îáåñïå÷åíà òîëüêî ïðè óñëîâèè íàëè÷èÿ íà÷àëüíîãî ïðèáëèæåíèÿ
R xn
( ) ( )0 , «áëèçêîãî» ê íàèëó÷øåìó äðîáíî-ðàöèîíàëüíîìó àïïðîêñèìàíòó R xn ( ).
 íåêîòîðûõ ÷àñòíûõ ñëó÷àÿõ äëÿ ìíîãèõ ìàòåìàòè÷åñêèõ ôóíêöèé, â îñîáåí-
íîñòè ïðè ìàëûõ çíà÷åíèÿõ n m k� � , â êà÷åñòâå íà÷àëüíîãî íàáîðà òî÷åê äëÿ íàõîæ-
äåíèÿ R xn
( ) ( )0 ìîæíî ïðèìåíÿòü òî÷êè óêëîíåíèÿ ïîëèíîìà ×åáûøåâà, íî äëÿ îáùåãî
ñëó÷àÿ ÷åáûøåâñêîé ðàöèîíàëüíîé çàäà÷è íåò íèêàêèõ ïðàêòè÷åñêèõ ðåêîìåíäàöèé îò-
íîñèòåëüíî âûáîðà «áëèçêîãî» R xn
( ) ( )0 . Ýòîò íåäîñòàòîê óñòðàíåí ðàáîòàìè Õ. Âåðíåðà
[11], êîòîðûé ïðåäëîæèë ìåòîä, âñåãäà ñõîäÿùèéñÿ ñ ëþáîãî íà÷àëüíîãî ïðèáëèæåíèÿ.
Îäíàêî ãðîìîçäêîñòü âû÷èñëåíèé è íèçêàÿ ñêîðîñòü ñõîäèìîñòè (ëèíåéíàÿ), ïî óòâåð-
æäåíèþ ñàìîãî Âåðíåðà, íå ïîçâîëÿþò èñïîëüçîâàòü åãî ýôôåêòèâíî íà ïðàêòèêå.
Ó÷èòûâàÿ ñêàçàííîå âûøå, à òàêæå òî, ÷òî äàæå óïðîùåííûå âàðèàíòû ï.÷.è. çà-
÷àñòóþ ñõîäÿòñÿ, àâòîðîì ñòàòüè ðàçðàáîòàí ñî÷åòàþùèé â ñåáå ïðåèìóùåñòâà ìåòî-
äîâ Ðåìåçà è Âåðíåðà êîìáèíèðîâàííûé àëãîðèòì. Èäåÿ ýòîãî àëãîðèòìà ñîñòîèò â
òîì, ÷òî íà ïðàêòèêå ÷àñòî æåëàòåëüíî ïîëó÷èòü ïðèáëèæåíèå, ìîäóëü-ìàêñèìóì
óêëîíåíèÿ êîòîðîãî íå ïðåâûøàåò íåêîòîðîãî çàäàííîãî ÷èñëà � � 0. Ïîýòîìó åñòåñ-
òâåííî âû÷èñëÿòü ïîñëåäîâàòåëüíîñòü àïïðîêñèìàíòîâ, íà÷èíàÿ ñ áîëåå ìàëûõ çíà÷å-
íèé ñòåïåíåé l è m è ïîâûøàÿ ýòè çíà÷åíèÿ äî ïîëó÷åíèÿ ïðèáëèæåíèÿ ñ æåëàåìîé
òî÷íîñòüþ. Òàêèì îáðàçîì, áóäåì ïðåäïîëàãàòü, ÷òî âñåãäà ïåðåä íà÷àëîì âû÷èñëå-
íèÿ R xl m, ( ) óæå ïîëó÷åí íàèëó÷øèé àïïðîêñèìàíò R xl m� �1 1, ( ) . Äëÿ ïîëó÷åíèÿ
àïïðîêñèìàíòîâ êàæäîé íîâîé ñòåïåíè âíà÷àëå èñïîëüçóåòñÿ ìåòîä ï.÷.è. ñ îáÿçàòåëü-
íîé ïðîâåðêîé ñõîäèìîñòè àëãîðèòìà íà êàæäîì øàãå èòåðàöèè.  ñëó÷àÿõ, êîãäà ñõî-
äèìîñòü íå íàðóøàåòñÿ, ìåòîä ï.÷.è. ðàáîòàåò äî êîíöà, ò.å. äî ïîëó÷åíèÿ íàèëó÷øåãî
àïïðîêñèìàíòà òåêóùåé ñòåïåíè. Åñëè íà êàêîì-òî øàãå ï.÷.è. ñõîäèìîñòü íàðóøàåòñÿ
(íàïðèìåð, ÷èñëî ó÷àñòêîâ ïåðåìåíû çíàêà óêëîíåíèé ìåíüøå l m� � 2), òî äëÿ ïîëó÷å-
íèÿ íà÷àëüíîãî ïðèáëèæåíèÿ R xl m,
( ) ( )0 , èìåþùåãî íå ìåíüøå l m� � 2 ýêñòðåìóìà, âñòó-
ïàåò â ðàáîòó íà÷àëüíûé àëãîðèòì (í.à.) ìåòîäà Âåðíåðà. Ïîñëå ýòîãî ñíîâà ðàáîòàåò
ìåòîä ï.÷.è. Áåç ó÷åòà ñëó÷àåâ âûðîæäåíèÿ, åñëè ñõîäèìîñòü ìåòîäà ï.÷.è. îáåñïå÷åíà è
àáñîëþòíîå çíà÷åíèå ìàêñèìàëüíîãî óêëîíåíèÿ íàèëó÷øåãî àïïðîêñèìàíòà íå ïðåâû-
øàåò âåëè÷èíó æåëàåìîé òî÷íîñòè, òî àëãîðèòì çàêàí÷èâàåò ðàáîòó. Èíà÷å ñòåïåíü àï-
ïðîêñèìàíòà ïîâûøàåòñÿ è ñíîâà íà÷èíàåò ðàáîòàòü ìåòîä ï.÷.è.
 êîìáèíèðîâàííîì àëãîðèòìå ó÷èòûâàþòñÿ ñëó÷àè âûðîæäåíèÿ, êîãäà ó íàèëó÷-
øåãî àïïðîêñèìàíòà ïðåäûäóùåé ñòåïåíè óêëîíåíèé ðàâíîé âåëè÷èíû è ÷åðåäóþ-
ùèõ çíàê áîëüøå l m� � 2, è ïî÷òè âûðîæäåíèÿ, êîãäà ó÷àñòêîâ ïåðåìåíû çíàêà áîëü-
øå l m� � 2, à ìîäóëü-ìàêñèìóìîâ óêëîíåíèé ðàâíîé âåëè÷èíû òî÷íî l m� � 2.
Íåñìîòðÿ íà òî ÷òî ñëó÷àè âûðîæäåíèÿ, è îñîáåííî ïî÷òè âûðîæäåíèÿ, êðàéíå
ðåäêè, î÷åíü âàæíî ñ âû÷èñëèòåëüíîé òî÷êè çðåíèÿ óìåòü èõ ðàñïîçíàâàòü äî íà÷àëà
âû÷èñëåíèÿ âûðîæäåííîãî àïïðîêñèìàíòà. Ñ ýòîé öåëüþ â àëãîðèòìå ïðåäïîëàãàåò-
ñÿ, ÷òî ïåðåä âû÷èñëåíèåì R xl m, ( ) èìååòñÿ íàèëó÷øèé àïïðîêñèìàíò R xl m� �1 1, ( ) . Ýòî
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 6 159
ðàâíîñèëüíî òîìó, ÷òî âû÷èñëåíèÿ ñëåäóåò íà÷èíàòü âñåãäà ñ íåâûðîæäåííûõ àï-
ïðîêñèìàíòîâ R xl m� , ( )0 äëÿ l m� èëè R xm l0, ( )� äëÿ l m� .
Èñõîäíàÿ ôóíêöèÿ f x( ) ïðåäïîëàãàåòñÿ çàäàííîé íà [ , ]a b êàê àíàëèòè÷åñêè, òàê
è äèñêðåòíî, îäíàêî ïðè ïîèñêå íîâûõ ýêñòðåìóìîâ óêëîíåíèé èñïîëüçóåòñÿ äèñêðåò-
íàÿ ïðîöåäóðà âû÷èñëåíèÿ çíà÷åíèé f x( ) â òî÷êàõ.
 îòëè÷èå îò ïîëèíîìèàëüíîãî ñëó÷àÿ, êîãäà âõîä â àëãîðèòì ìîæåò íà÷èíàòüñÿ
ëèáî ïî çàäàííîé òî÷íîñòè, ëèáî ïî ñòåïåíè, â ñëó÷àå äðîáíî-ðàöèîíàëüíîé àïïðîêñèìà-
öèè âõîä â êîìáèíèðîâàííûé àëãîðèòì îñóùåñòâëÿåòñÿ òîëüêî ïî çàäàííîé òî÷íîñòè � .
Îòëè÷èå òàêæå ñîñòîèò â òîì, ÷òî â ýòîì ñëó÷àå ñèñòåìà l m� � 2 àëãåáðàè÷åñêèõ óðàâíå-
íèé ñ n � 2 íåèçâåñòíûìè ÿâëÿåòñÿ íåëèíåéíîé. Åå ëèíåàðèçàöèÿ îòíîñèòåëüíî n � 1 íå-
èçâåñòíûõ êîýôôèöèåíòîâ îñóùåñòâëÿåòñÿ ïîñðåäñòâîì èñêëþ÷åíèÿ îäíîãî íåèçâåñò-
íîãî ��. Ó÷èòûâàÿ ëåãêî óñòðàíèìóþ íåëèíåéíîñòü ñèñòåìû, åå ðåøåíèå íàõîäèì ñëå-
äóþùèì îáðàçîì. Ïîñëåäíåå óðàâíåíèå (ïðè � � �n 1) ðàññìàòðèâàåì êàê ôóíêöèþ îò
�� è èùåì �� êàê êîðåíü ôóíêöèè F a a b b Fl m[� , (� ), , (� ), (� ), , (� )] (� )� � � � � �0 1� � � , ðåøàÿ
óðàâíåíèå F (� )� � 0 ïî ìåòîäó ñåêóùåé [12]. Çàòåì, çàäàâàÿ íà÷àëüíûå çíà÷åíèÿ � ( )� 1
è � ( )� 2 , ðåøàåì ñèñòåìó ïåðâûõ l m� � 1 óðàâíåíèÿ îòíîñèòåëüíî { }ai i
l
�0 è { }bj j
m
�1.
Ïîäñòàâëÿÿ ýòè çíà÷åíèÿ ïîî÷åðåäíî â ïîñëåäíåå óðàâíåíèå, ïîëó÷àåì F (� )( )� 1 è
F (� )( )� 2 . Èòåðàöèîííûé ïðîöåññ ïðîäîëæàåòñÿ äî âûïîëíåíèÿ óñëîâèÿ
| � � | / | � � |( ) ( ) ( ) ( )� � � � �i i i i� �� � �1 1 , ãäå � — çàäàííîå ÷èñëî.
Êîãäà äëÿ òåêóùåãî R xl m, ( ) ï.÷.è. íå ñõîäÿòñÿ, ò.å. ÷èñëî NN ìîäóëü-ìàêñèìóìîâ
ýêñòðåìóìîâ, ÷åðåäóþùèõ çíàê è ðàâíûõ ïî âåëè÷èíå, ìåíüøå l m� � 2, èëè íå ñõîäèòñÿ
ìåòîä ñåêóùèõ, òî íà÷èíàåò ðàáîòàòü í.à. Âåðíåðà ñ íàèëó÷øåãî àïïðîêñèìàíòà
R xl m� �1 1, ( ) , ïîñëåäîâàòåëüíî ïîâûøàÿ åãî ñòåïåíè äî ñòåïåíåé òåêóùåãî àïïðîêñèìàíòà
äî òåõ ïîð, ïîêà íå áóäåò ïîëó÷åíî íå ìåíåå l m� � 2 òî÷åê, â êîòîðûõ ýêñòðåìóìû óêëî-
íåíèé ÷åðåäóþò çíàê. Ïîñëå ýòîãî ñíîâà íà÷èíàåò ðàáîòàòü ìåòîä ï.÷.è. äî ïîëó÷åíèÿ àï-
ïðîêñèìàíòà, èìåþùåãî l m� � 2 ðàâíûõ ïî ìîäóëþ è ÷åðåäóþùèõ çíàê ýêñòðåìóìîâ
óêëîíåíèé. Ýòîò àïïðîêñèìàíò ïðèíèìàåòñÿ çà íà÷àëüíîå ïðèáëèæåíèå R xl m,
( ) ( )0 ìåòîäà
ï.÷.è. äëÿ íàõîæäåíèÿ íàèëó÷øåãî ïðèáëèæåíèÿ R xl m, ( ), è ðàáîòà êîìáèíèðîâàííîãî àë-
ãîðèòìà ïðîäîëæàåòñÿ äî ïîëó÷åíèÿ íàèëó÷øåãî àïïðîêñèìàíòà òðåáóåìîé òî÷íîñòè.
ÀÏÏÐÎÊÑÈÌÀÖÈß ÔÓÍÊÖÈÈ ÌÍÎÃÈÕ ÏÅÐÅÌÅÍÍÛÕ
Çàäà÷à àïïðîêñèìàöèè ôóíêöèè ëþáîãî ÷èñëà ïåðåìåííûõ f X( ) � f x x xm( , , , )1 2 �
ïîñðåäñòâîì îáîáùåííûõ ïîëèíîìîâ F X a Xn i i
i
n
( ) ( )�
�
� �
0
, à èìåííî
max ( ) ( ) ( , , , ) min
x E
i i
i
n
nf X a X L a a a
� �
� � �� �
0
0 1 � , (9)
ãäå X x x xm� ( , , , )1 2 � — òî÷êà m -ìåðíîãî ïðîñòðàíñòâà íà òî÷å÷íîì ìíîæåñòâå
E X X X N� { }( ) ( ) ( ), , ,1 2
� , ðåøàåòñÿ êàê ÷àñòíûé ñëó÷àé çàäà÷è ïîñòðîåíèÿ ðàâíî-
ìåðíî-íàèëó÷øåãî â ÷åáûøåâñêîì ñìûñëå ïðèáëèæåíèÿ ê ðåøåíèþ ñèñòåìû íå-
ñîâìåñòíûõ ëèíåéíûõ óðàâíåíèé
�i ij j i
j
n
Z a z b( ) � �
�
�
1
( , ,... , , )i N N n� �1 2 . (10)
Äðóãèìè ñëîâàìè, çàäà÷à ñîñòîèò â îïðåäåëåíèè òàêèõ ïàðàìåòðîâ z z zn1 2, , ,� ,
÷òîáû çíà÷åíèå âåëè÷èíû
max | ( ) | max ( , , ,
, ,i N
i
i N
ij j i
j
n
z a z b L z z z
� � �
� � ��
1 1 2 1
1 2� � n ) (11)
áûëî íàèìåíüøèì âîçìîæíûì, ò.å.
max ( | ( ) | , | ( ) | , , | ( ) | ) ( )� � �1 2Z Z Z L ZN� � ( ) min� �� .
160 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 6
Àëãîðèòì ðåøåíèÿ çàäà÷è (9) ÿâëÿåòñÿ ðåàëèçàöèåé àíàëîãà ìåòîäà ï.÷.è. Ðåìåçà
äëÿ ñëó÷àÿ ñâåäåíèÿ ê çàäà÷å ëèíåéíîãî ïðîãðàììèðîâàíèÿ ñ íåîòðèöàòåëüíûìè êî-
ýôôèöèåíòàìè, à èìåííî: ïðèñîåäèíÿÿ â (10) ê êàæäîé ôóíêöèè �i Z( ) åå «ñèììåòðè-
÷åñêóþ êîïèþ» � �N i i ij j i
j
n
Z Z a z b�
�
� � � � ��( ) ( )
1
, çàäà÷ó (10), (11) ïðåäñòàâëÿåì â
âèäå çàäà÷è àëãåáðàè÷åñêîãî ìèíèìàêñà
�i ij j i
j
n
Z a z b( ) � � �
�
�
1
0 ( , ; ; ),i N a a b bi N j ij i N i� � � � �� �1 2 , (12)
max ( ) max ( )
, ,i N
i
i N
ij j
j
n
iZ a z b L Z
� � �
� �
�
�
�
�
�
�
�
�
��
1 2 1 2 1
� � �min ( )� . (13)
Çàäà÷è (10), (11) è (12), (13) ýêâèâàëåíòíû çàäà÷å ëèíåéíîãî ïðîãðàììèðîâàíèÿ
� � min , � i i ij j i
j
n
Z a z b� � � � � � �
�
�� � �( )
1
0 ( , )i N� 1 2 .
Âïåðâûå ñâåäåíèå ê çàäà÷å ëèíåéíîãî ïðîãðàììèðîâàíèÿ äëÿ äèñêðåòíûõ ÷åáû-
øåâñêèõ ïðèáëèæåíèé ïðåäëîæåíî Å. Øòèôåëåì [13] äëÿ ñëó÷àÿ âûïîëíåíèÿ «áîëü-
øîãî äåòåðìèíàíòíîãî óñëîâèÿ» (îòëè÷èÿ îò íóëÿ âñåõ îïðåäåëèòåëåé n-ãî ïîðÿäêà)
äëÿ ñèñòåìû ôóíêöèé �i ij j i
j
n
X a x b( ) � �
�
�
1
, i N� 1 2, , è ðàçâèòî Å.ß. Ðåìåçîì.
×àñòíûì ñëó÷àåì ñôîðìóëèðîâàííîé çàäà÷è ÿâëÿåòñÿ íàèëó÷øåå ðàâíîìåðíîå ïðè-
áëèæåíèå ôóíêöèè îäíîé ïåðåìåííîé f x( ) íà êîíå÷íîì ìíîæåñòâå òî÷åê
E x x x N� { , , , }( ) ( ) ( )1 2
� îáûêíîâåííûìè ïîëèíîìàìè (1). Îäíàêî ñâåäåíèå ýòîé çàäà÷è ê
çàäà÷å ëèíåéíîãî ïðîãðàììèðîâàíèÿ íåöåëåñîîáðàçíî, òàê êàê ïðèìåíÿåìûé äëÿ åå ðå-
øåíèÿ â ÷åáûøåâñêîé ïîñòàíîâêå ìåòîä ï.÷.è. îáëàäàåò áåçóñëîâíûìè ïðåèìóùåñòâàìè.
 ðàçðàáîòàííîì àëãîðèòìå [14] ðåàëèçîâàíà ïðÿìàÿ è äâîéñòâåííàÿ çàäà÷è ëè-
íåéíîãî ïðîãðàììèðîâàíèÿ, ïðè÷åì âåäóùàÿ — äâîéñòâåííàÿ, êîòîðàÿ ðåøàåòñÿ ìî-
äèôèöèðîâàííûì ñèìïëåêñ-ìåòîäîì (ì.ñ.-ì.) ñ ó÷åòîì òîãî, ÷òî íà ïðàêòèêå ÷èñëî
óðàâíåíèé N çíà÷èòåëüíî áîëüøå ÷èñëà íåèçâåñòíûõ n è òàáëèöà «ðàñøèðåííîãî áà-
çèñà» ðàçìåðà ( )( )n n� �2 4 ïðè ì.ñ.-ì. ñóùåñòâåííî ìåíüøå îïîðíîé òàáëèöû
( )n N� 2 ïðè ïðÿìîì ñèìïëåêñ-ìåòîäå.
 àëãîðèòìå ïðèìåíåíû òàêæå ïðèåìû, ïîçâîëÿþùèå ñîêðàòèòü áîëüøå ÷åì íà-
ïîëîâèíó ñèìïëåêñ-òàáëèöó (ñ.-ò.) è â ïðîöåññå ðåøåíèÿ äâîéñòâåííîé çàäà÷è ì.ñ.-ì.
ïðåîáðàçîâûâàòü òîëüêî ìîäèôèöèðîâàííóþ (ñæàòóþ) ñ.-ò., îñòàâëÿÿ ïðè ýòîì íåèç-
ìåííîé îïîðíóþ òàáëèöó. Êðîìå òîãî, àëãîðèòì èìååò òàêèå îñíîâíûå îñîáåííîñòè:
1) ïðèìåíåíèå äëÿ äâîéñòâåííîé çàäà÷è ì.ñ.-ì., â ïðîöåññå êîòîðîãî ñòðîèòñÿ
îïîðíàÿ ñ.-ò. ðàçìåðíîñòè ( )n N� 2 è íà÷àëüíàÿ ìîäèôèöèðîâàííàÿ (ñæàòàÿ) ñ.-ò., ñî-
äåðæàùàÿ îáðàòíóþ ìàòðèöó «ðàñøèðåííîãî» áàçèñà ðàçìåðíîñòè ( )( )n n� �2 2 , êëþ-
÷åâîé ñòîëáåö ïåðâîé æîðäàíîâîé çàìåíû è ñòîëáåö çíà÷åíèé áàçèñíûõ ïåðåìåííûõ
(â òîì ÷èñëå è öåëåâóþ ôóíêöèþ �);
2) ïðåîáðàçîâàíèå ïî îáùèì ïðàâèëàì æîðäàíîâîé çàìåíû òîëüêî ìîäèôèöèðî-
âàííîé ñ.-ò. ðàçìåðíîñòè ( )( )n n� �2 4 , à íå ðàçìåðíîñòè ( )n N� 2 , êàê ïðè ïðÿìîì
ñèìïëåêñ-ìåòîäå;
3) íåèçìåííîñòü îïîðíîé òàáëèöû â ïðîöåññå ðåøåíèÿ çàäà÷è.
Òàêèì îáðàçîì, ïðèìåíÿÿ ì.ñ.-ì., ïîëó÷àåì îïòèìàëüíîå ðåøåíèå çàäà÷ è âû÷èñ-
ëÿåì çíà÷åíèÿ èñêîìûõ ïàðàìåòðîâ z z zn1 2, , ,� èñõîäíîé çàäà÷è (12), (13). Ïîäñòà-
âèâ ïîëó÷åííûå çíà÷åíèÿ z j â ëèíåéíûå ôóíêöèè �i Z
�
( ) ( , )� � �1 1n , ïîëó÷èì çíà÷å-
íèÿ �
i
Z
1
( ), � �i iZ Z
n2 1
( ), , ( )�
�
. Íàèìåíüøàÿ è íàèáîëüøàÿ ïî ìîäóëþ ñðåäè ýòèõ
çíà÷åíèé âåëè÷èíû A è L ÿâëÿþòñÿ ñîîòâåòñòâåííî íèæíåé è âåðõíåé ãðàíèöàìè âå-
ëè÷èíû íàèëó÷øåãî ïðèáëèæåíèÿ �, ò.å. A L� �� . Çà êðèòåðèé êîíöà ðàáîòû àëãî-
ðèòìà ïðèíèìàåòñÿ âûïîëíåíèå óñëîâèÿ L L A� � �� .
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 6 161
ÎÏÒÈÌÈÇÀÖÈß ÀËÃÎÐÈÒÌÎÂ
Äëÿ ðàçðàáîòàííûõ àëãîðèòìîâ îñóùåñòâëåí àíàëèç âñåõ âèäîâ ïîãðåøíîñòåé, ñî-
ïðîâîæäàþùèõ ðåøåíèå çàäà÷ íàèëó÷øåé ÷åáûøåâñêîé ïîëèíîìèàëüíîé è äðîá-
íî-ðàöèîíàëüíîé àïïðîêñèìàöèè, à èìåííî ïîãðåøíîñòè ïîñòàíîâêè çàäà÷è çà ñ÷åò
äèñêðåòíîãî ïðåäñòàâëåíèÿ àïïðîêñèìèðóåìîé ôóíêöèè, íåóñòðàíèìîé è âû÷èñëè-
òåëüíîé ïîãðåøíîñòåé àëãîðèòìîâ, à òàêæå ïîëíîé àáñîëþòíîé ïîãðåøíîñòè ðåøå-
íèÿ ýòèõ çàäà÷. Òàêîé àíàëèç ïðîâîäèòñÿ ïî äâóì ðàçëè÷íûì ñõåìàì, ïåðâàÿ èç
êîòîðûõ óäîáíà ïðè ìèíèìàëüíîé èíôîðìàöèè î ïîâåäåíèè äèñêðåòíî çàäàííîé
àïïðîêñèìèðóåìîé ôóíêöèè, à âòîðàÿ — ïðè íàëè÷èè äîïîëíèòåëüíîé èíôîðìà-
öèè î åå ñòðóêòóðíûõ ñâîéñòâàõ. Ïðè ýòîì ïîëó÷åíû íåóëó÷øàåìûå äëÿ íåêîòî-
ðûõ êëàññîâ ôóíêöèé êàê àïðèîðíûå, òàê è àïîñòåðèîðíûå ìàæîðàíòíûå äåòåðìè-
íèðîâàííûå îöåíêè âñåõ âèäîâ ïîãðåøíîñòåé, ðàñ÷åòû êîòîðûõ âêëþ÷åíû â âû-
÷èñëèòåëüíûå ñõåìû àëãîðèòìîâ è ïðîãðàìì, ÷òî ïîçâîëèëî çíà÷èòåëüíî ïîâûñèòü
òî÷íîñòü ðåçóëüòàòîâ âû÷èñëåíèé (â íåêîòîðûõ ñëó÷àÿõ íà ïîðÿäîê). Äëÿ îïðåäå-
ëåíèÿ çíà÷åíèé óêàçàííûõ îöåíîê ïîëíîé ïîãðåøíîñòè ðåøåíèÿ ÷åáûøåâñêîé çà-
äà÷è ïîëó÷åíû ïðåäñòàâëÿþùèå ñàìîñòîÿòåëüíûé èíòåðåñ âñïîìîãàòåëüíûå ðåçóëü-
òàòû èç êîíñòðóêòèâíîé òåîðèè ôóíêöèé, â òîì ÷èñëå óòî÷íÿþùèå èçâåñòíûå
îöåíêè âåíãåðñêèõ àâòîðîâ Ã. Àëåêñè÷à, Ä. Êðàëèêà è Ë. Ëåéíäëåðà.  öåëÿõ ñó-
ùåñòâåííîãî ïîâûøåíèÿ ýôôåêòèâíîñòè ðàçðàáîòàííûõ âû÷èñëèòåëüíûõ àëãîðèò-
ìîâ îñóùåñòâëÿëèñü òàêæå ðàçëè÷íûå ïðîöåäóðû äëÿ èõ ìîäèôèêàöèè, â ÷àñòíîñ-
òè, ðåàëèçîâàí ïîäõîä, îñíîâàííûé íà ïðèìåíåíèè ñåãìåíòíîé (êóñî÷íîé) àïïðîê-
ñèìàöèè ðàçíûìè êëàññàìè àïïðîêñèìàíòîâ.
Ïðåèìóùåñòâî ýòèõ àëãîðèòìîâ çàêëþ÷àåòñÿ â òîì, ÷òî â öåëÿõ ïîâûøåíèÿ ýô-
ôåêòèâíîñòè ïðîâåäåíà èõ îïòèìèçàöèÿ ïî áûñòðîäåéñòâèþ è ïî òî÷íîñòè.
Îïòèìèçàöèÿ ïî áûñòðîäåéñòâèþ äîñòèãàåòñÿ çà ñ÷åò ñëåäóþùèõ ôàêòîðîâ:
— àëãîðèòìû îñíîâàíû íà ìåòîäå ïîñëåäîâàòåëüíûõ ÷åáûøåâñêèõ èíòåðïîëÿ-
öèé Ðåìåçà è îòíîñÿòñÿ ê àëãîðèòìàì ïîäúåìà, ïðè ðàáîòå êîòîðûõ íèæíÿÿ ãðàíèöà
âûáðàííûõ íà êàæäîì øàãå n � 2 ìàêñèìàëüíûõ óêëîíåíèé îò ôóíêöèè àïïðîêñèìàí-
òà ïîðÿäêà n íå óìåíüøàåòñÿ íà ïîñëåäóþùèõ øàãàõ, ÷òî ïðåäïî÷òèòåëüíåå ïî ñêî-
ðîñòè ñõîäèìîñòè;
— â àëãîðèòìàõ ðåàëèçóåòñÿ íà ïðàêòèêå îäèí èç òðåõ âîçìîæíûõ âàðèàíòîâ ïî-
ñëåäîâàòåëüíîé çàìåíû ( )n � 2 -òî÷å÷íûõ íàáîðîâ, íà êîòîðûõ îñóùåñòâëÿþòñÿ øàãè
÷.è., à èìåííî îïòèìàëüíûé, ÷òî îáåñïå÷èâàåò êâàäðàòè÷íóþ ñêîðîñòü ñõîäèìîñòè âñå-
ãî èòåðàöèîííîãî ïðîöåññà è ïîçâîëÿåò ïîëó÷àòü ðåçóëüòàò çà äâå-òðè èòåðàöèè;
— êîìáèíèðîâàííûé àëãîðèòì ðåàëèçàöèè äðîáíî-ðàöèîíàëüíîé àïïðîêñèìà-
öèè ïîçâîëÿåò îáåñïå÷èòü ñõîäèìîñòü ï.÷.è. òàêæå äëÿ äðîáíî-ðàöèîíàëüíîãî ñëó÷àÿ,
ïðè ýòîì ñîõðàíÿþòñÿ äåéñòâèÿ ôàêòîðîâ îïòèìèçàöèè ïï. 1) è 2).
Îïòèìèçàöèÿ ïî òî÷íîñòè îñóùåñòâëÿåòñÿ áëàãîäàðÿ ñëåäóþùèì äåéñòâèÿì:
— âêëþ÷åíèþ â âû÷èñëèòåëüíóþ ñõåìó àëãîðèòìîâ ðàñ÷åòà êàê àïðèîðíûõ, òàê è
àïîñòåðèîðíûõ îöåíîê ïîëíîé ïîãðåøíîñòè, ÷òî ïîçâîëÿåò êîððåêòèðîâàòü ðåçóëüòàòû,
à èìåííî, â çàâèñèìîñòè îò òðåáóåìîé òî÷íîñòè ìåíÿòü ñòåïåíü ïîëèíîìà, ÷èñëî òî÷åê
ñåòêè, ïàðàìåòð êðèòåðèÿ îñòàíîâà è îáîñíîâàííî âûáèðàòü âèä àïïðîêñèìàíòà;
— ïðîñìîòðó íà êàæäîì øàãå èòåðàöèè ïðè ïåðåõîäå ê ñëåäóþùåìó øàãó âñåõ òî-
÷åê ñåòêè ïðè èññëåäîâàíèÿõ ïîâåäåíèÿ óêëîíåíèé ïîëèíîìà îò ôóíêöèé, ïðè ýòîì ó÷è-
òûâàþòñÿ êàê âåðõíÿÿ, òàê è íèæíÿÿ ãðàíèöû âåëè÷èíû íàèëó÷øåãî ïðèáëèæåíèÿ;
— èñïîëüçîâàíèþ íà êàæäîì øàãå ÷åáûøåâñêèõ èíòåðïîëÿöèé äëÿ ðåøåíèÿ ñèñ-
òåì ëèíåéíûõ àëãåáðàè÷åñêèõ óðàâíåíèé ìåòîäà Êðàóòà, îïòèìèçèðîâàííîãî ïî
òî÷íîñòè [15];
— ïðèìåíåíèþ â àëãîðèòìå äðîáíî-ðàöèîíàëüíîé àïïðîêñèìàöèè íà êàæäîì
j-ì øàãå ÷.è. äëÿ ðåøåíèÿ íåëèíåéíîé ñèñòåìû óðàâíåíèé îòíîñèòåëüíî êîýôôèöè-
åíòîâ è âåëè÷èíû íàèëó÷øåãî ïðèáëèæåíèÿ ñïåöèàëüíîãî ïîäõîäà, îñíîâàííîãî íà
ëèíåàðèçàöèè ñèñòåìû è èñïîëüçîâàíèè ìåòîäà ñåêóùåé;
— èñïîëüçîâàíèþ ñõåìû Áàõâàëîâà âìåñòî ñõåìû Ãîðíåðà äëÿ óìåíüøåíèÿ ïî-
ãðåøíîñòè îêðóãëåíèé ïðè âû÷èñëåíèÿõ â òî÷êàõ çíà÷åíèé ïîëèíîìîâ ñòåïåíè,
áîëüøåé 10;
162 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 6
— ïðèìåíåíèþ êóñî÷íî-ïîëèíîìèàëüíîé àïïðîêñèìàöèè äëÿ ñæàòèÿ áîëüøèõ è
ñâåðõáîëüøèõ ìàññèâîâ ÷èñëîâûõ äàííûõ, ÷òî çíà÷èòåëüíî ïîâûøàåò òî÷íîñòü ïðè-
áëèæåíèÿ è îáåñïå÷èâàåò âûñîêèå êîýôôèöèåíòû ñæàòèÿ ïî ñðàâíåíèþ ñ àïïðîêñèìà-
öèåé áåç ðàçáèåíèÿ íà ñåãìåíòû.
 àëãîðèòìàõ èñïîëüçîâàíû äîïîëíèòåëüíûå ïðèåìû ïîâûøåíèÿ èõ ýôôåê-
òèâíîñòè:
— ðåøåíèå çàäà÷ àïïðîêñèìàöèè êàê äëÿ äèñêðåòíî, òàê è àíàëèòè÷åñêè çàäàí-
íûõ ôóíêöèé, ïðè ýòîì äîïîëíèòåëüíî ââîäèòñÿ ïðîöåäóðà âû÷èñëåíèÿ çíà÷åíèé
ôóíêöèè â òî÷êàõ äèñêðåòèçàöèè;
— ïðîâåäåíèå ïðåäâàðèòåëüíîé àïïðîêñèìàöèè â öåëÿõ ïîâûøåíèÿ òî÷íîñòè
çíà÷åíèé äèñêðåòíûõ äàííûõ â ñëó÷àÿõ, êîãäà èçâåñòíû ñâîéñòâà èñõîäíîé àïïðîêñè-
ìèðóåìîé ôóíêöèè;
— îáåñïå÷åíèå äâóõ «âõîäîâ» â àëãîðèòìû, ÷òî ïîçâîëÿåò íàõîäèòü ëèáî àï-
ïðîêñèìàíò çàäàííîé ôèêñèðîâàííîé ñòåïåíè («âõîä» ïî ñòåïåíè), ëèáî òàêîé, êîòî-
ðûé îáåñïå÷èâàåò çàäàííóþ òî÷íîñòü ïðèáëèæåíèÿ («âõîä» ïî òî÷íîñòè);
— èñïîëüçîâàíèå ðàçëè÷íûõ êëàññîâ àïïðîêñèìèðóþùèõ âûðàæåíèé, íàèáîëåå
ñîîòâåòñòâóþùèõ õàðàêòåðó ïîâåäåíèÿ («ïðèðîäå») ïðèáëèæàåìîé ôóíêöèè;
— îáåñïå÷åíèå ïîñòðîåíèÿ ïîëèíîìèàëüíîãî ïðèáëèæåíèÿ ñ ïðîèçâîëüíûì âå-
ñîì w x( ) � 0;
— ïðîâåðêà â êîìáèíèðîâàííîì àëãîðèòìå ðåøåíèÿ äðîáíî-ðàöèîíàëüíîé çàäà-
÷è ïåðåä íà÷àëîì êàæäîé ñëåäóþùåé èòåðàöèè âîçìîæíîñòè ïîÿâëåíèÿ ñëó÷àåâ âû-
ðîæäåíèÿ èëè ïî÷òè âûðîæäåíèÿ, êîãäà íå óäàåòñÿ ïîëó÷èòü íóæíîå êîëè÷åñòâî òî-
÷åê ýêñòðåìàëüíîãî áàçèñà, ïðè÷åì ýòè ñëó÷àè â àëãîðèòìå ðàñïîçíàþòñÿ äî íà÷àëà
âû÷èñëåíèé âûðîæäåííîãî àïïðîêñèìàíòà, ïîñëå ÷åãî ïîäêëþ÷àþòñÿ ñðåäñòâà äëÿ èõ
óñòðàíåíèÿ;
— ïðèìåíåíèå äëÿ àïïðîêñèìàöèè ôóíêöèé ìíîãèõ ïåðåìåííûõ ì.ñ.-ì. è íåêî-
òîðûõ ïðîöåäóð, êîòîðûå îáåñïå÷èâàþò çíà÷èòåëüíîå óìåíüøåíèå êîëè÷åñòâà âû÷èñ-
ëåíèé è ïîâûøåíèå òî÷íîñòè ðåçóëüòàòîâ.
ÇÀÊËÞ×ÅÍÈÅ
Àïïàðàò àïïðîêñèìàöèè íà ïðîòÿæåíèè ìíîãèõ ëåò èñïîëüçîâàëñÿ â ñîñòàâå ïðè-
êëàäíîãî ïðîãðàììíîãî îáåñïå÷åíèÿ îòå÷åñòâåííûõ êîìïüþòåðîâ è äëÿ ñæàòèÿ
ìàññèâîâ äàííûõ â ðàñ÷åòàõ ñëîæíûõ äèíàìè÷åñêèõ ñèñòåì, íàïðèìåð ïðî÷íîñ-
òíûõ õàðàêòåðèñòèê ëåòàòåëüíûõ àïïàðàòîâ äëÿ ÍÈÈ èì. À.Í. Òóïîëåâà, òðàåêòî-
ðèé äâèæåíèÿ êîñìè÷åñêèõ îáúåêòîâ, òðàíññåêò è êðèâûõ òðàíñêîíòèíåíòàëüíûõ ïå-
ðåíîñîâ çàãðÿçíåíèé âîçäóøíîé ñðåäû, òîêîâûõ ñîñòîÿíèé âîäíûõ ñèñòåì (âîäîå-
ìîâ, âîäîòîêîâ, ×åðíîãî ìîðÿ) â ñâÿçè ñ ïîñëåäñòâèÿìè ×åðíîáûëüñêîé êàòàñòðîôû
è áûëà ïîäòâåðæäåíà åãî âûñîêàÿ ýôôåêòèâíîñòü. Áîëåå ïîäðîáíî îá ýòîì èçëîæå-
íî â ðàáîòàõ [16–23].
Àïïàðàò ÷åáûøåâñêîé àïïðîêñèìàöèè â ïîñëåäíåå âðåìÿ ïðèìåíåí â ðàìêàõ íà-
ó÷íî-òåõíè÷åñêîãî ïðîåêòà äëÿ ðåøåíèÿ ðàñ÷åòíûõ çàäà÷ ÀÍÒÊ «Àíòîíîâ», à òàêæå
äëÿ ñæàòèÿ áîëüøèõ îäíîìåðíûõ ìàññèâîâ-âåêòîðîâ (ñ âîçìîæíûì êîëè÷åñòâîì çíà-
÷åíèé äî 10 ìëí ÷èñåë) â öåëÿõ ïîëó÷åíèÿ íåáîëüøîãî ÷èñëà ïàðàìåòðîâ àïïðîêñè-
ìàíòîâ; äîñòèãíóòû áîëüøèå çíà÷åíèÿ êîýôôèöèåíòîâ ñæàòèÿ (â ñðåäíåì áîëåå äâóõ
ïîðÿäêîâ) [24].
 ñîñòàâ ïðîãðàììíîãî îáåñïå÷åíèÿ êëàñòåðíîãî êîìïëåêñà ÑÊÈÒ âêëþ÷åíû
áèáëèîòåêè ÷åáûøåâñêîé àïïðîêñèìàöèè ôóíêöèé îäíîé è ìíîãèõ ïåðåìåííûõ è âû-
÷èñëåíèÿ ñ ïîâûøåííîé òî÷íîñòüþ çíà÷åíèé ýëåìåíòàðíûõ è ñïåöèàëüíûõ ôóíêöèé.
 íàñòîÿùåå âðåìÿ äëÿ ÑÊÈÒ ðàçðàáàòûâàåòñÿ ïàêåò ïðîãðàìì àïïðîêñèìàöèè
ôóíêöèé ðàçíûìè ñïîñîáàìè ïðèáëèæåíèÿ: èíòåðïîëÿöèîííûì, ñðåäíåêâàäðàòè÷íûì
è ÷åáûøåâñêèì, êîòîðûé âîéäåò â ñîñòàâ åãî Áàçîâîãî ïðèêëàäíîãî ïðîãðàììíîãî îá-
åñïå÷åíèÿ. Ýòîò ïàêåò èìååò ðÿä ñóùåñòâåííûõ ïðåèìóùåñòâ ïî ñðàâíåíèþ ñ èçâåñ-
òíûìè àíàëîãè÷íûìè ïàêåòàìè è ñïåöèàëèçèðîâàííûìè áèáëèîòåêàìè, òàêèìè, íà-
ïðèìåð, êàê Mathcad, Maple, MATLAB, Mathematica, MATHLIB, NETLIB [25].
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. × å á û ø å â Ï . Ë . Ïîëíîå ñîáðàíèå ñî÷èíåíèé. — Ì.: Èçä-âî ÀÍ ÑÑÑÐ, 1947. — Ò. 2, 3.
2. Ð å ì å ç Å . ß . Îñíîâû ÷èñëåííûõ ìåòîäîâ ÷åáûøåâñêîãî ïðèáëèæåíèÿ. — Êèåâ: Íàóê. äóìêà, 1969.
— 623 ñ.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 6 163
3. Í à ò à í ñ î í È . Ï . Êîíñòðóêòèâíàÿ òåîðèÿ ôóíêöèé. — Ì.-Ë.: Ãîñòåõèçäàò, 1949. — 688 ñ.
4. À õ è å ç å ð Í . È . Ëåêöèè ïî òåîðèè àïïðîêñèìàöèè. — Ì.: Íàóêà, 1965. — 408 ñ.
5. Ñ ò å ÷ ê è í C . Á . , Ñ ó á á î ò è í Þ . Í . Ñïëàéíû â âû÷èñëèòåëüíîé ìàòåìàòèêå. — Ì.: Íàóêà,
1976. — 248 ñ.
6. Ä å ì ü ÿ í î â Â . Ô . , Ì à ë î ç å ì î â Â . Í . Ââåäåíèå â ìèíèìàêñ. — Ì.: Íàóêà, 1972. — 368 ñ.
7. Á å ð ä û ø å â  . È . , Ï å ò ð à ê Ë .  . Àïïðîêñèìàöèÿ ôóíêöèé, ñæàòèå ÷èñëåííîé èíôîðìàöèè,
ïðèëîæåíèÿ. — Åêàòåðèíáóðã: ÓðÎ ÐÀÍ, 1999. — 297 ñ.
8. Ê à ë å í ÷ ó ê - Ï î ð õ à í î â à À . À . Íàèëó÷øàÿ ÷åáûøåâñêàÿ àïïðîêñèìàöèÿ — àëãîðèòìû è èõ
ïðèìåíåíèå // Ïð. ì³æíàð. ñèìïîç. «Ïèòàííÿ îïòèì³çàöi¿ îá÷èñëåíü (ÏÎΖÕÕÕV)». — Ê.: ²í-ò
ê³áåðíåòèêè ³ì. Â.Ì. Ãëóøêîâà ÍÀÍ Óêðà¿íè, 2009. — Ñ. 279–284.
9. Á à õ â à ë î â Í . Ñ . ×èñëåííûå ìåòîäû. — Ì.: Íàóêà, 1973. — 631 ñ.
10. R a l s t o n A . Rational Chebyshev approximation by Remes’ algorithm // Numerische Mathematik. —
1965. — 7, N 4. — P. 322–330.
11. W e r n e r H . , S t o e r J . , B o m m a s W . Rational Chebyshev approximation // Ibid. — 1967. — 10,
N 4. — P. 342–352.
12. Î ñ ò ð î â ñ ê è é À . Ì . Ðåøåíèå óðàâíåíèé è ñèñòåì óðàâíåíèé. — Ì.: Èçä-âî èíîñòð. ëèò., 1963. —
219 ñ.
13. S t i e f e l E . Note on Jordan elimination, linear programming and Chebysheff approximation // Nume-
rische Mathematik. — 1960. — 2. — P. 1–17.
14. À ë å ê ñ à í ä ð å í ê î Â . Ë . Àëãîðèòì ïîñòðîåíèÿ ïðèáëèæåííîãî ðàâíîìåðíî-íàèëó÷øåãî ðåøåíèÿ
ñèñòåìû íåñîâìåñòíûõ ëèíåéíûõ óðàâíåíèé // Àëãîðèòìû è àëãîðèòìè÷åñêèå ÿçûêè. — Ì.: ÂÖ ÀÍ
ÑÑÑÐ, 1968. — Âûï. 3. — Ñ. 57–74.
15.  î å â î ä è í  .  . Îøèáêè îêðóãëåíèÿ è óñòîé÷èâîñòü â ïðÿìûõ ìåòîäàõ ëèíåéíîé àëãåáðû. —
Ì.: Èçä-âî ÌÃÓ è ÂÖ, 1969. — 153 ñ.
16. À ë å ê ñ à í ä ð å í ê î Â . Ë . , Ï î ð õ à í î â à À . À . Àëãîðèòìû ïðèáëèæåíèÿ ôóíêöèè îäíîé ïåðå-
ìåííîé ïîëèíîìàìè ïî âòîðîìó ìåòîäó Å.ß. Ðåìåçà // Âû÷èñë. è ïðèêë. ìàòåìàòèêà. — Êèåâ:
Èçä-âî ÊÃÓ, 1967. — Âûï. 3. — 116 ñ.
17. Ê à ë å í ÷ ó ê - Ï î ð õ à í î â à À . À . Îá îäíîì àëãîðèòìå ïîëèíîìèàëüíîé ÷åáûøåâñêîé àïïðîêñè-
ìàöèè // Îïòèìèçàöèÿ âû÷èñëèòåëüíûõ ìåòîäîâ. — Ê.: Èí-ò êèáåðíåòèêè ÀÍ ÓÑÑÐ, 1974. —
Ñ. 45–51.
18. Ï î ð õ à í î â à À . À . ×åáûøåâñêàÿ àïïðîêñèìàöèÿ äðîáíî-ðàöèîíàëüíûìè âûðàæåíèÿìè // Âû-
÷èñë. ìàòåìàòèêà â ñîâð. íàó÷.-òåõí. ïðîãðåññå. — Êèåâ: Çíàíèå, 1974. — Ñ. 300–308.
19. Ê à ë å í ÷ ó ê - Ï î ð õ à í î â à À . À . Àëãîðèòìû è àíàëèç ïîãðåøíîñòè íàèëó÷øåé ÷åáûøåâñêîé àï-
ïðîêñèìàöèè îäíîé ïåðåìåííîé // Òåîðèÿ ïðèáëèæåíèÿ ôóíêöèé: Òð. Ìåæäóíàð. êîíô. ïî òåîðèè
ïðèáëèæåíèÿ ôóíêöèé, Êàëóãà, 1975. — Ì.: Íàóêà, 1977. — Ñ. 213–218.
20. È â à í î â Â . Â . , Ê à ë å í ÷ ó ê À . À . Îá ýôôåêòèâíîñòè àëãîðèòìîâ ïîëèíîìèàëüíûõ è äðîáíî-ðà-
öèîíàëüíûõ ÷åáûøåâñêèõ ïðèáëèæåíèé // Òð. ìåæäóíàð. êîíô. ïî êîíñòðóêòèâíîé òåîðèè ôóíêöèé.
— Ñîôèÿ: Èçä-âî Áîëãàð. ÀÍ, 1983. — Ñ. 72–77.
21. Ê à ë å í ÷ ó ê - Ï î ð õ à í î â à À . À . Àïïðîêñèìàöèÿ ôóíêöèé îäíîé è ìíîãèõ ïåðåìåííûõ // ×èñ-
ëåííûå ìåòîäû äëÿ ìíîãîïðîöåññîðíîãî âû÷èñëèòåëüíîãî êîìïëåêñà ÅÑ. — Ì.: Èçä-âî ÂÂÈÀ
èì. Í.Å. Æóêîâñêîãî, 1987. — Ñ. 366–395.
22. Ê à ë å í ÷ ó ê - Ï î ð õ à í î â à À . À . Àïïàðàò àïïðîêñèìàöèè äëÿ àíàëèçà è ñèíòåçà ñëîæíûõ ñèñòåì
// Ïð. ̳æíàð. êîíô. «50 ðîê³â ²íñòèòóòó ê³áåðíåòèêè ³ì. Â.Ì. Ãëóøêîâà ÍÀÍ Óêðà¿íè». — Êè¿â,
2008. — Ñ. 354–361.
23. Ê à ë å í ÷ ó ê - Ï î ð õ à í î â à À . À . Àëãîðèòìû ðåàëèçàöèè íàèëó÷øåé ÷åáûøåâñêîé àïïðîêñèìà-
öèè — ïîâûøåíèå èõ ýôôåêòèâíîñòè // Ïð. ì³æíàð. ñèìïîç. «Ïèòàííÿ îïòèì³çàöi¿ îá÷èñëåíü
(ÏÎΖÕÕÕV)». — Ê.: ²í-ò ê³áåðíåòèêè ³ì. Â.Ì. Ãëóøêîâà ÍÀÍ Óêðà¿íè, 2009. — Ñ. 285–290.
24. Ê à ë å í ÷ ó ê - Ï î ð õ à í î â à À . À . ,  à ê à ë Ë . Ï . Íàèëó÷øàÿ ÷åáûøåâñêàÿ àïïðîêñèìàöèÿ äëÿ
ñæàòèÿ ÷èñëåííîé èíôîðìàöèè // Êîìïüþòåðíàÿ ìàòåìàòèêà. — 2009. — ¹ 1. — Ñ. 3–9.
25. Ê à ë å í ÷ ó ê - Ï î ð õ à í î â à À . À . , Â à ê à ë Ë . Ï . Àïïàðàò àïïðîêñèìàöèè â ñîñòàâå ïðîãðàì-
ìíîãî îáåñïå÷åíèÿ ñóïåðêîìïüþòåðà ñ êëàñòåðíîé àðõèòåêòóðîé // Èñêóññòâ. èíòåëëåêò. — 2009. —
¹ 1. — Ñ. 52–60.
Ïîñòóïèëà 30.06.2009
164 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 6
|