Побудова найкращих рівномірних наближень функцій багатьох змінних

Запропоновано алгоритм найкращого рівномірного наближення функції багатьох змінних узагальненим поліномом. В алгоритмі використано зведення задачі наближення до максимумзадачі лінійного програмування. Наведені приклади наближень....

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2007
Автори:	Каленчук-Порханова, А.О., Вакал, Л.П.
Формат:	Стаття
Мова:	Ukrainian
Опубліковано:	Інститут кібернетики ім. В.М. Глушкова НАН України 2007
Онлайн доступ:	http://dspace.nbuv.gov.ua/handle/123456789/6483
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Побудова найкращих рівномірних наближень функцій багатьох змінних / А.О. Каленчук-Порханова, Л.П. Вакал // Комп’ютерні засоби, мережі та системи. — 2007. — № 6. — С. 141-148. — Бібліогр.: 10 назв. — укр.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-6483
record_format	dspace
spelling	irk-123456789-64832010-03-05T12:01:24Z Побудова найкращих рівномірних наближень функцій багатьох змінних Каленчук-Порханова, А.О. Вакал, Л.П. Запропоновано алгоритм найкращого рівномірного наближення функції багатьох змінних узагальненим поліномом. В алгоритмі використано зведення задачі наближення до максимумзадачі лінійного програмування. Наведені приклади наближень. An algorithm for the best uniform approximation of a manyvariables functions by a generalized polynomial is proposed. The algorithm is based on leading the approximation problem to the maximum problem of linear programming. Some approximation results are given. 2007 Article Побудова найкращих рівномірних наближень функцій багатьох змінних / А.О. Каленчук-Порханова, Л.П. Вакал // Комп’ютерні засоби, мережі та системи. — 2007. — № 6. — С. 141-148. — Бібліогр.: 10 назв. — укр. 1817-9908 http://dspace.nbuv.gov.ua/handle/123456789/6483 004.421.2:519.651.2 uk Інститут кібернетики ім. В.М. Глушкова НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Ukrainian
description	Запропоновано алгоритм найкращого рівномірного наближення функції багатьох змінних узагальненим поліномом. В алгоритмі використано зведення задачі наближення до максимумзадачі лінійного програмування. Наведені приклади наближень.
format	Article
author	Каленчук-Порханова, А.О. Вакал, Л.П.
spellingShingle	Каленчук-Порханова, А.О. Вакал, Л.П. Побудова найкращих рівномірних наближень функцій багатьох змінних
author_facet	Каленчук-Порханова, А.О. Вакал, Л.П.
author_sort	Каленчук-Порханова, А.О.
title	Побудова найкращих рівномірних наближень функцій багатьох змінних
title_short	Побудова найкращих рівномірних наближень функцій багатьох змінних
title_full	Побудова найкращих рівномірних наближень функцій багатьох змінних
title_fullStr	Побудова найкращих рівномірних наближень функцій багатьох змінних
title_full_unstemmed	Побудова найкращих рівномірних наближень функцій багатьох змінних
title_sort	побудова найкращих рівномірних наближень функцій багатьох змінних
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate	2007
url	http://dspace.nbuv.gov.ua/handle/123456789/6483
citation_txt	Побудова найкращих рівномірних наближень функцій багатьох змінних / А.О. Каленчук-Порханова, Л.П. Вакал // Комп’ютерні засоби, мережі та системи. — 2007. — № 6. — С. 141-148. — Бібліогр.: 10 назв. — укр.
work_keys_str_mv	AT kalenčukporhanovaao pobudovanajkraŝihrívnomírnihnabliženʹfunkcíjbagatʹohzmínnih AT vakallp pobudovanajkraŝihrívnomírnihnabliženʹfunkcíjbagatʹohzmínnih
first_indexed	2025-07-02T09:24:40Z
last_indexed	2025-07-02T09:24:40Z
_version_	1836526633098412032
fulltext	Комп’ютерні засоби, мережі та системи. 2007, № 6 141 A. Kalenchuk-Porkhanova, L. Vakal CONSTRUCTING THE BEST UNIFORM APPROXIMATIONS FOR MANY-VARIABLES FUNCTIONS An algorithm for the best uniform approximation of a many-variables functions by a generalized polynomi- al is proposed. The algorithm is based on leading the approximation problem to the maximum problem of linear programming. Some appro- ximation results are given. Запропоновано алгоритм найкра- щого рівномірного наближення функції багатьох змінних узагаль- неним поліномом. В алгоритмі використано зведення задачі на- ближення до максимум-задачі лі- нійного програмування. Наведені приклади наближень.  А.О. Каленчук-Порханова, Л.П. Вакал, 2007 УДК 004.421.2:519.651.2 А.О. КАЛЕНЧУК-ПОРХАНОВА, Л.П. ВАКАЛ ПОБУДОВА НАЙКРАЩИХ РІВНОМІРНИХ НАБЛИЖЕНЬ ФУНКЦІЙ БАГАТЬОХ ЗМІННИХ Вступ. На практиці часто виникає необхід- ність дослідження складних процесів, що характеризуються багатопараметричними за- лежностями, дискретне представлення яких виражається багатовимірними масивами да- них. Задача заміни таких масивів даних ана- літичними виразами зводиться до задачі по- будови наближень функцій багатьох змінних. У роботі для розв’язання цієї задачі про- понується спосіб найкращого рівномірного наближення і наводиться алгоритм побудови такого наближення функції багатьох змінних узагальненим поліномом. Цей спосіб має суттєві переваги за точністю порівняно з ін- шими способами наближення [1]. Постановка задачі. Задача найкращого рі- вномірного наближення функції f (X) k змін- них X = (x1,..., xk) узагальненим поліномом за системою n лінійно незалежних базисних функцій  Xj       n j jjn XzZ;XF 1 , (1) де  nz,,zZ 1 , на множині N точок {X(1),…, X(N)} (N > n) полягає у знаходженні такого набору коефіцієнтів  * n ** z,,zZ 1 апроксиманта  Z;XFn , який задовольняє умову чебишовського мінімаксу:    ZLZL Z * min ,         1 1 max φ . n i i j j i N j L Z f X z X      (2) А.О. КАЛЕНЧУК-ПОРХАНОВА, Л.П. ВАКАЛ Комп’ютерні засоби, мережі та системи. 2007, № 6 142 Найбільш поширений спосіб знаходження узагальненого полінома найкра- щого рівномірного наближення полягає у зведенні задачі (1)  (2) до задачі лі- нійного програмування [27]. Якщо ввести функції           n j ii jji XfXzZ 1 ,    ZiN  Zi ( N,i 1 ), (3) то задачу найкращого рівномірного наближення (1)(2) можна представити у вигляді задачі лінійного програмування з n  1 невідомими і 2N обмеженнями: min , (4)   0 Zii  N,i 21 . (5) Нехай для базисних функцій  Xj , n,j 1 , на множині N точок викону- ється мала детермінантна умова, тобто хоча б один з детермінантів n-го порядку не дорівнює нулю. Тоді в (5) серед системи 2N функцій i є не менше, ніж n  1 лінійно незалежних. Якщо їх вибрати за нові незалежні змінні 1i  ,…, 1  ni (як це можна зробити практично – описується далі в алгоритмі), то задача (4)  (5) запишеться у більш звичному вигляді задачі лінійного програмування з не- від’ємними коефіцієнтами       1 1 min n iС ; (6)  nN,s,kk n sn,isn,i sn       22 1 1 0 ;  N,ii 210  . (7) Для знаходження оптимального розв’язку задачі (6)  (7) можна застосувати загальні методи лінійного програмування, наприклад симплекс-метод. Але ура- хування специфіки задачі наближення дозволяє розробляти більш ефективні ал- горитми найкращого рівномірного наближення функцій багатьох змінних. Алгоритм. Алгоритм побудови узагальненого полінома найкращого рівно- мірного наближення функції багатьох змінних, який описується далі, базується на зведенні задачі наближення (1)  (2) до задачі лінійного програмування, коли головною є двоїста до (6)  (7) максимум-задача: max 2 2 0      nN s isn, / sn k ; (8)        nN s isn,i n,,Ck sn 2 2 11 ;  N,ii 210  . (9) Вибір як головної двоїстої задачі (8)  (9) має ряд переваг, зокрема, число обмежень n  1 двоїстої задачі значно менше числа обмежень 2N  n  1 прямої задачі (6)  (7), відсутнє виродження при виконанні певних умов та інші [8]. ПОБУДОВА НАЙКРАЩИХ РІВНОМІРНИХ НАБЛИЖЕНЬ ФУНКЦІЙ БАГАТЬОХ ЗМІННИХ Комп’ютерні засоби, мережі та системи. 2007, № 6 143 Алгоритм складається з трьох етапів: перший – зведення задачі наближення (1)  (2) до максимум-задачі лінійного програмування (8)  (9), другий – знахо- дження оптимального розв’язку максимум-задачі, третій – визначення коефіці- єнтів узагальненого полінома найкращого наближення на основі отриманого оп- тимального розв’язку задачі (8)  (9) та оцінка точності наближення. Для підвищення ефективності алгоритму проведено його оптимізацію за то- чністю та швидкодією за рахунок таких факторів. 1. В алгоритмі застосовується запропонована в [4] спеціальна процедура зведення задачі (1)  (2) до задачі лінійного програмування (8 )  (9), внаслідок якої за рахунок відповідного вибору змінних 1i  ,…, 1  ni формується симплекс- таблиця, що вже містить допустимий базисний розв’язок. Це дозволяє розпочати симплекс-процес для двоїстої максимум-задачі (8)  (9) одразу з основної фази. 2. Стандартна симплекс-таблиця замінюється значно меншою, але рівноцін- ною за поданою інформацією симплекс-таблицею, в якій на основі співвідно- шення 2i i N     [2, с. 486], залишено замість 2Nn1 всього Nn1 стов- пців (кількість рядків у цих таблицях однакова). 3. В алгоритмі реалізується пряма і двоїста задачі лінійного програмування, причому головною є двоїста максимум-задача, яка розв’язується модифікованим симплекс-методом з урахуванням того, що на практиці кількість рівнянь N знач- но більше числа невідомих n і таблиця „розширеного базису” розмірністю    42  nn при модифікованому симплекс-методі суттєво менша, ніж опорна таблиця розмірністю   Nn  2 при прямому симплекс-методі. 4. Застосовується високонадійний прийом проти можливого зациклювання модифікованого симплекс-методу та проводиться контроль правильності вико- наних жорданових перетворень. Оскільки в алгоритмі при розв’язанні максимум-задачі (8)  (9) модифікова- ним симплекс-методом відбувається послідовне підвищення величини L(Z), то цей алгоритм є аналогом поліноміального алгоритму підвищувальної дії Є.Я. Ремеза для наближення функції однієї змінної у випадку зведення до задачі лінійного програмування [2]. Вхідними даними для алгоритму побудови узагальненого полінома найкра- щого рівномірного наближення функції k змінних є: n – кількість шуканих коефіцієнтів zj узагальненого полінома вигляду (1); N – кількість точок       j k jj x,,xX 1 k-вимірної сітки ( N,j 1 );   jXf , N,j 1 – значення функції f у точках сітки або процедура для їх обчислення;   j i X , N,j;n,i 11  – значення базисних функцій у точках сітки або процедури для їх обчислення. Перший етап алгоритму. 1. Виконується початкове заповнення матриці Т розмірністю   Nn  2 за А.О. КАЛЕНЧУК-ПОРХАНОВА, Л.П. ВАКАЛ Комп’ютерні засоби, мережі та системи. 2007, № 6 144 формулами:   j iji Xt  ,   j j,n Xft 1 , 02  j,nt  N,j;n,i 11  . 2. Покладаються j,nj tp 1 , jd j   N,j 1 та it = 0 (it  лічильник числа кроків алгоритму). 3. Для кожного і-го  n,i 1 рядка матриці Т визначається номер  стовпця, в якому знаходиться найбільший за модулем елемент цього рядка j,n nN,j ,n tt 2 1 2 max     , покладається id і виконується процедура Jordan жорданового перетворення матриці T з елементом it як ключовим. 4. Стовпці матриці Т переставляються в порядку розташування індексів dn+1,…, dN , d1,…,dn. 5. Обчислюються елементи (n+2)-го рядка матриці Т за формулою ijn d n i ijdj,n ptpt      1 2  nN,j 1 , після чого визначається номер стовпця  , в якому розташований максимальний за модулем елемент цього рядка j,n nN,j ,n tmaxt 2 1 2     . Якщо таких елементів декілька, то вибирається номер  , для якого додатково  ,nt 2 > 0. 6. Якщо  ,nt 2 > 0, то перехід до п. 7, інакше – до п. 8. 7. У кожному і-му рядку  n,i 1 матриці Т, в якому елемент it > 0, знаки усіх елементів цього рядка змінюються на протилежні, покладається Ndd ii  і здійснюється перехід на п. 10. 8. Змінюється на протилежний знак елемента  ,nt 2 і покладається Ndd nn   . 9. Якщо в деякому і-му рядку  n,i 1 матриці Т елемент 0it   , то знаки всіх інших елементів цього рядка змінюються на протилежні та покладається Ndd ii  ; якщо ж 0t i  , то змінюється на протилежний тільки знак it . 10. Виконуються перетворення елементів матриці Т , а саме:  обчислюються перші Nn елементів (n+1)-го рядка  nN,jtt n i ijj,n     11 1 1 ;  змінюються на протилежні знаки елементів j,nt 2  nN,j 1 ;  визначаються інші елементи (n+1)-го рядка  j,nt 1   n i ijt 1 ПОБУДОВА НАЙКРАЩИХ РІВНОМІРНИХ НАБЛИЖЕНЬ ФУНКЦІЙ БАГАТЬОХ ЗМІННИХ Комп’ютерні засоби, мережі та системи. 2007, № 6 145  N,nNj 1 ;  обчислюються останні n елементів (n+2)-го рядка  j,nt 2    n i iijqt 1 , N,nNj 1 , де idi pq  для Ndi  і Ndi i pq  для Ndi  ;  змінюються на протилежні знаки елементів на перетині перших n рядків і останніх n стовпців  N,nNj,n,itt ijij 11  . 11. До матриці Т застосовується одна операція перетворення Жордана з ключовим елементом  ,nt 1 (з використанням процедури Jordan). 12. Обчислюються елементи допоміжних векторів B та R та елементи hij ма- триці H розмірністю   nn  2 , яка буде використовуватися на третьому етапі алгоритму для визначення коефіцієнтів узагальненого полінома: bi = 2 tik, krk  , jnN,iij th   N,k,n,j,n,i 1121  . 13. Визначаються елементи матриці C розмірністю    42  nn , в якій формується початкова стиснена таблиця модифікованого симплекс-методу  1 , 4 1, 1 , 0, , 1, 2, 2, 3 0, 1 i i i n i j j i c t c c i n j n j i              . 14. Обчислюються елементи матриці Т, в якій формується опорна таблиця модифікованого симплекс-методу    1121 0 1 2211         n,j,n,i, ji, ji, t,N,nj,n,itt jinj,iij . Внаслідок виконаних дій елементи  111  n,ici у стисненій симплекс- таблиці будуть невід’ємними. Отже, наявний у цій таблиці базисний розв’язок  1101  n,jc jj ,  nN,kkn   220 буде і допустимим. Другий етап алгоритму. У зв’язку зі специфікою опорної таблиці  відсут- ність в явному вигляді майже половини стовпців  модифікований симплекс- метод має певні особливості реалізації порівняно зі стандартною схемою. 15. Покладається it = it +1 та     2 1 12 n l l,nr,lr ctp kk ( N,nk 2 ). 16. Якщо для всіх N,nk 2 виконується умова  kr p0 bn+2 , то здійсню- ється перехід до п. 23, інакше – визначається номер  ключового стовпця мат- риці Т з умови   2 2 : 0 : max max , max k k k r k r nk k r n r r p r p b p p b p        , ( N,nk 2 ). 17. Якщо N1 , то  ,ii tf , інакше   ,iii tbf , 21  n,i . А.О. КАЛЕНЧУК-ПОРХАНОВА, Л.П. ВАКАЛ Комп’ютерні засоби, мережі та системи. 2007, № 6 146 18. Обчислюються елементи ключового стовпця матриці С за формулою 4n,ic = 2 , 1 1 n k i k k f c     . 19. Визначається номер  ключового рядка матриці С, для якого 4 1 04 1 4 min     n,i ,i c:in, , c c c c n,i . Якщо таких номерів декілька, то для усунення неви- значеності й запобігання зациклювання вибирається найменший [2, с. 295]. 20. Виконується жорданове перетворення матриці С з ключовим елементом 4 n,c за допомогою процедури Jordan. 21. Якщо для елементів матриці С виконуються рівності 1 1 1    n i jic ,  211 1 1 4     n,j,c n i n,i , то здійснюється перехід на п. 22, інакше – видається повідомлення про помилку в обчисленнях і алгоритм закінчує роботу. 22. Здійснюється підготовка до наступного кроку модифікованого симплекс- методу. Для цього в масивах індексів міняються місцями індекс змінної, яка ви- водиться з базису, та індекс змінної, яка вводиться з нього. Спочатку поклада- ється  dk . Якщо 0p , то   dd , інакше – Ndd   для Nd  і Ndd   для d >N . Далі послідовно виконуються присвоєння: kd  ,  rk ,   rr , kr  і здійснюється перехід на п. 15. 23. Запам’ятовуються номери змінних останнього базису. Якщо Nd  1 , то покладається   di , інакше – Ndi   ( n,1 ). На цьому другий етап алгоритму закінчено. Оптимальний розв’язок задачі (8)(9) знаходиться у масиві P, а значення цільової функції дорівнює значенню елемента cn+2,1. Третій етап алгоритму. 24. Обчислюються коефіцієнти узагальненого полінома і величина  1 nz за формулами:   121 1 1 2 1 ,nn n k jkkj,nj cz,n,jhphz       . 25. Визначаються величини A і L       1 1 1 min n i i j j n j A z X f X           ;           n j ii jj n XfXzL 1 11 max . 26. Обчислюється похибка  у визначенні величини наближення  за фор- мулою  = L – А. ПОБУДОВА НАЙКРАЩИХ РІВНОМІРНИХ НАБЛИЖЕНЬ ФУНКЦІЙ БАГАТЬОХ ЗМІННИХ Комп’ютерні засоби, мережі та системи. 2007, № 6 147 27. Виводяться на друк такі результати: z1,…, zn – коефіцієнти узагальненого полінома; zn+1 – величина наближення  ;  – похибка у визначенні величини найкращого рівномірного наближення  ; ni,,i 1 – номери змінних останньої базисної системи. В описаному алгоритмі для виконання перетворення Жордана довільної ма- триці А розмірністю nm з відомим ключовим елементом kla служить проце- дура Jordan. У цій процедурі послідовно виконуються перетворення ключового елемента lk lk a a 1  , елементів ключового рядка lkljlj aaa   kj,n,j 1 , клю- чового стовпця lkikik aaa   li,m,i 1 та елементів поза ключовим хрестом ljikijij aaaa   kj,li,n,j,m,i  11 . Приклади обчислень. Для оцінки ефективності розробленого алгоритму наближення функцій багатьох змінних узагальненими поліномами було прове- дено порівняння з іншими аналогічними алгоритмами на тестових прикладах. Приклад 1. За розробленим алгоритмом знайдено поліном найкращого рів- номірного наближення  y,xP4 вигляду:    yxzxzyzxyzxzyzxzzy,xP 2 8 3 7 2 65 2 43214 4 15 3 14 22 13 3 12 4 11 3 10 2 9 yzxyzyxzyxzxzyzxyz  , (10) який апроксимує функцію ysinxcos  на сітці S= ii y,x ( ;j.y;i.x ii 1010  100100 ,j;,i  ) з абсолютною похибкою = 0.0002732. Для порівняння, похи- бка наближення цієї функції поліномом вигляду (10), побудованим за алгорит- мом [9], дорівнює = 0.0002735. Гірше наближення дає також поліном  y,xP4 , знайдений за алгоритмом [7], причому для цього виявилося необхідним 43 кроки алгоритму, водночас як у нашому алгоритмі – 25 кроків. Приклад 2. Алгоритм застосовувався для наближення залежності квадрату щільності В (в умовних одиницях) від температури t (в °C) і концентрації C (в г/л) солі в розчині за допомогою узагальненого полінома за системою трьох ба- зисних функцій 7361 1 .C , t2 , tC 3 [10]. Отримана емпірична форму- ла tC.t.C.B .  0069120035470026180 73612 дозволила наблизити дані експерименту з абсолютною похибкою 0.073 (відносна похибка  5 %). Зазначи- мо, що знайдена за методом середніх емпірична формула tC.t.C.B .  006999003520026440 73612 дає гірші результати, а саме, аб- солютна похибка наближення становить 0.0924 (відносна  14 %) [10]. Висновки. У порівнянні з іншими алгоритмами наближення функцій бага- тьох змінних запропонований алгоритм дозволяє отримати найкращі рівномірні наближення таких функцій узагальненими поліномами з меншою похибкою та, А.О. КАЛЕНЧУК-ПОРХАНОВА, Л.П. ВАКАЛ Комп’ютерні засоби, мережі та системи. 2007, № 6 148 як правило, за значно меншу кількість ітерацій. Це вдалося досягти за рахунок удосконалення обчислювальної схеми алгоритму за такими основними напрямками: - процес зведення задачі наближення до максимум-задачі лінійного програ- мування проводиться з орієнтацією на отримання початкової симплекс-таблиці з якомога більшим значенням цільової функції, завдяки чому оптимальний розв’язок максимум-задачі знаходиться за відносно малу кількість кроків; - для розв’язання задачі лінійного програмування застосовується модифіко- ваний симплекс-метод, в ході якого жорданові перетворення застосовуються тільки до стисненої таблиці, при цьому опорна таблиця залишається незмінною. У порівнянні зі стандартною симплекс-таблицею стиснена таблиця є майже удвічі меншою, але рівноцінною за представленою інформацією, і вже містить допустимий базисний розв’язок; - у процесі проведення розрахунків додатково здійснюється контроль пра- вильності виконання обчислень. Запропонований алгоритм також може ефективно використовуватись для визначення параметрів емпіричних формул, які є представленнями відповідних залежностей між експериментальними даними. 1. Вакал Л.П., Каленчук-Порханова А.О. Аналітична обробка даних на основі чебишовської апроксимації // Математичні машини і системи.  2006.  № 2. – С. 1524. 2. Ремез Е.Я. Основі численных методов чебышевского приближения. – К.: Наук. думка, 1969. – 623 с. 3. Stiefel E. Note on Jordan elimination, linear programming and Tschebyscheff approximation // Numerische Math. – 1960. – 2. – N 1. – P. 117. 4. Александренко В.Л. Алгоритм построения приближѐнного равномерно-наилучшего ре- шения системы несовместных линейных уравнений // Алгоритмы и алгоритмические языки.  М.: ВЦ АН СССР, 1968. – Вып. 3.  С. 5774. 5. Каленчук-Порханова А.А. Аппроксимация функций одной и многих переменных // Чис- ленные методы для многопроцессорного вычислительного комплекса ЕС. – М.: Изд-во ВВИА им. Н.Е. Жуковского, 1987. – С. 366–395. 6. Демьянов В.Р., Малозѐмов В.Н. Введение в минимакс. – М.: Наука, 1972. – 368 с. 7. Кондратьев В.П. Алгоритм наилучшего приближения функций многих переменных // Программы оптимизации (приближение функций). – Свердловск: ИММ УНЦ АН СССР. – 1972. – Вып. 3.  С. 2048. 8. Каленчук-Порханова Ж., Вакал Л. Найкраще рівномірне наближення функцій багатьох змінних // Тези доповідей Міжнарод. математ. конф. ім. В.Я. Скоробогатька.– Дрогобич- Львів: ІППММ НАН України.  2004. – С. 90. 9. Петрак Л.В. Программа построения приближающего полинома для функций многих переменных // Программы оптимизации (приближение функций).– Свердловск: ИММ УНЦ АН СССР. – 1975. – Вып. 6.  С. 145157. 10. Батунер Л.М., Позин М.Е. Математические методы в химической технике. – Л.: Химия, 1968.  823 с. Отримано 10.04.2007

Побудова найкращих рівномірних наближень функцій багатьох змінних

Репозитарії

Схожі ресурси