Метод формування оптимального " насиченого блоку " у задачі локалізації розв’язків інтервальної системи лінійних алгебричних рівнянь

Запропоновано новий метод формування набору базових рівнянь у задачі локалізації розв’язків інтервальної системи лінійних алгебричних рівнянь (ІСЛАР) на основі «насичено-го блоку», який ґрунтується на розв’язуванні оптимізаційної задачі. За критерій обрано мінімізацію максимальної похибки прогнозува...

Повний опис

Збережено в:
Бібліографічні деталі
Дата:2016
Автори: Дивак, М.П., Олійник, І.С.
Формат: Стаття
Мова:Ukrainian
Опубліковано: Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України 2016
Назва видання:Індуктивне моделювання складних систем
Онлайн доступ:http://dspace.nbuv.gov.ua/handle/123456789/125050
Теги: Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:Метод формування оптимального " насиченого блоку " у задачі локалізації розв’язків інтервальної системи лінійних алгебричних рівнянь / М.П. Дивак, І.С. Олійник // Індуктивне моделювання складних систем: Зб. наук. пр. — К.: МННЦ ІТС НАН та МОН України, 2016. — Вип. 8. — С. 79-99. — Бібліогр.: 18 назв. — укр.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine
id irk-123456789-125050
record_format dspace
spelling irk-123456789-1250502017-10-14T03:04:03Z Метод формування оптимального " насиченого блоку " у задачі локалізації розв’язків інтервальної системи лінійних алгебричних рівнянь Дивак, М.П. Олійник, І.С. Запропоновано новий метод формування набору базових рівнянь у задачі локалізації розв’язків інтервальної системи лінійних алгебричних рівнянь (ІСЛАР) на основі «насичено-го блоку», який ґрунтується на розв’язуванні оптимізаційної задачі. За критерій обрано мінімізацію максимальної похибки прогнозування інтервальними моделями, параметри яких на-лежать області локалізації розв’язків ІСЛАР. Досліджено властивості запропонованого методу. Показано його ефективність та переваги (з точки зору обчислювальної складності та збіжності), у порівнянні з методами формування набору базових рівнянь, що базуються на плануванні інтервальних експериментів. Предложен новый метод формирования набора базовых уравнений в задаче локализации решений интервальной системы линейных алгебраических уравнений (ИСЛАУ) на основе «насыщенного блока», который основывается на решении оптимизационной задачи. За критерий выбрано минимизацию максимальной погрешности прогнозирования интервальными моделями, параметры которых пренадлежат области локализации решений ИСЛАУ. Исследованы свойства предложенного метода. Показаны его эффективность и преимущества (с точки зрения вычислительной сложности и сходимости), в сравнении с методами формирования набора базовых уравнений, базирующихся на планированию интервальных экспери-ментов. A new method formation of the set of basic equations in the problem of localization the solutions of interval systems of linear algebraic equations (ISLAE) on the basis of the "saturated block", which is based on the solution of the optimization problem. The criterion chosen to minimize the maximum error of prediction interval models, whose parameters belong to the area of localization of solutions ISLAE. We investigated the properties of the proposed method. Shown its effectiveness and benefits (from the point of view of computational complexity and convergence), in comparison with the methods forming the set of basic equations based on the planning interval of the experiments.. 2016 Article Метод формування оптимального " насиченого блоку " у задачі локалізації розв’язків інтервальної системи лінійних алгебричних рівнянь / М.П. Дивак, І.С. Олійник // Індуктивне моделювання складних систем: Зб. наук. пр. — К.: МННЦ ІТС НАН та МОН України, 2016. — Вип. 8. — С. 79-99. — Бібліогр.: 18 назв. — укр. XXXX-0044 http://dspace.nbuv.gov.ua/handle/123456789/125050 519.876.5 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 2016
url http://dspace.nbuv.gov.ua/handle/123456789/125050
citation_txt Метод формування оптимального " насиченого блоку " у задачі локалізації розв’язків інтервальної системи лінійних алгебричних рівнянь / М.П. Дивак, І.С. Олійник // Індуктивне моделювання складних систем: Зб. наук. пр. — К.: МННЦ ІТС НАН та МОН України, 2016. — Вип. 8. — С. 79-99. — Бібліогр.: 18 назв. — укр.
series Індуктивне моделювання складних систем
work_keys_str_mv AT divakmp metodformuvannâoptimalʹnogonasičenogoblokuuzadačílokalízacíírozvâzkívíntervalʹnoísistemilíníjnihalgebričnihrívnânʹ
AT olíjnikís metodformuvannâoptimalʹnogonasičenogoblokuuzadačílokalízacíírozvâzkívíntervalʹnoísistemilíníjnihalgebričnihrívnânʹ
first_indexed 2025-07-09T02:28:57Z
last_indexed 2025-07-09T02:28:57Z
_version_ 1837134656939491328
fulltext Метод формування оптимального «насиченого блоку» у задачі локалізації розв’язків і Індуктивне моделювання складних систем, випуск 8, 2016 79 УДК 519.876.5 МЕТОД ФОРМУВАННЯ ОПТИМАЛЬНОГО «НАСИЧЕНОГО БЛОКУ» У ЗАДАЧІ ЛОКАЛІЗАЦІЇ РОЗВ’ЯЗКІВ ІНТЕРВАЛЬНОЇ СИСТЕМИ ЛІНІЙНИХ АЛГЕБРИЧНИХ РІВНЯНЬ М.П. Дивак, І.С. Олійник Тернопільський національний економічний університет mdy@tneu.edu.ua, ois@tneu.edu.ua Запропоновано новий метод формування набору базових рівнянь у задачі локалізації розв’язків інтервальної системи лінійних алгебричних рівнянь (ІСЛАР) на основі «насичено- го блоку», який ґрунтується на розв’язуванні оптимізаційної задачі. За критерій обрано міні- мізацію максимальної похибки прогнозування інтервальними моделями, параметри яких на- лежать області локалізації розв’язків ІСЛАР. Досліджено властивості запропонованого мето- ду. Показано його ефективність та переваги (з точки зору обчислювальної складності та збі- жності), у порівнянні з методами формування набору базових рівнянь, що базуються на пла- нуванні інтервальних експериментів. Ключові слова: ідентифікація, інтервальний аналіз, локалізація розв’язків, еліпсоїдне оцінювання, «насичений блок» інтервальної системи лінійних алгебричних рівнянь. A new method formation of the set of basic equations in the problem of localization the solutions of interval systems of linear algebraic equations (ISLAE) on the basis of the "saturated block", which is based on the solution of the optimization problem. The criterion chosen to minimize the maximum error of prediction interval models, whose parameters belong to the area of localization of solutions ISLAE. We investigated the properties of the proposed method. Shown its effectiveness and benefits (from the point of view of computational complexity and convergence), in comparison with the methods forming the set of basic equations based on the planning interval of the experiments.. Keywords: identification, interval analysis, localization solutions, elipsoid estimation, "satu- rated block" of interval system of linear algebraic equations. Предложен новый метод формирования набора базовых уравнений в задаче локализации решений интервальной системы линейных алгебраических уравнений (ИСЛАУ) на основе «насыщенного блока», который основывается на решении оптимизационной задачи. За кри- терий выбрано минимизацию максимальной погрешности прогнозирования интервальными моделями, параметры которых пренадлежат области локализации решений ИСЛАУ. Иссле- дованы свойства предложенного метода. Показаны его эффективность и преимущества (с точки зрения вычислительной сложности и сходимости), в сравнении с методами формиро- вания набора базовых уравнений, базирующихся на планированию интервальных экспери- ментов. Ключевые слова: идентификация, интервальный анализ, локализация решений, эллипсо- идное оценивание, «насыщенный блок» интервальной системы линейных алгебраических уравнений. Дивак М.П., Олійник І.С. Індуктивне моделювання складних систем, випуск 8, 2016 80 Вступ. Задачу ідентифікації параметрів моделей статичних систем на основі інтервальних даних переважно формулюють у вигляді задачі розв’язування інтервальної системи лінійних алгебричних рівнянь (ІСЛАР) [13,16]. Розв’язками цієї задачі є множина оцінок параметрів статичної системи, або її деяка наближена гарантована (зовнішня) локалізаційна оцінка [2,5-6,14]. Серед ряду існуючих методів локалізації ІСЛАР, виділяють метод, який передбачає вибір із ІСЛАР з m невідомими m – інтервальних рівнянь, тобто «насиченого блоку», які називають базовими. На основі вибраних базових рівнянь конструюють локалізаційну область розв’язків усієї ІСЛАР [3,5-6]. У роботі [3] наведено детальний алгоритм реалізації вище зазначеного методу і відзначено, що вибір «насиченого блоку» з ІСЛАР, який забезпечить оптимальні множинні оцінки параметрів статичної системи, є складною обчислювальною задачею з комбінаторною складністю [3,13]. Зважаючи на зазначене вище, завданням даної праці є теоретичне обґрун- тування та розробка простішого методу формування такого «насиченого блоку» (набору з m базових рівнянь) з ІСЛАР, який би забезпечував високу точність параметрів інтервальної моделі та задовільні її прогностичні властивості. 1. Постановка задачі Нехай залежність між «виходом» та «входами» для деякої статичної сис- теми має вигляд алгебричного рівняння: 0 1 1( ) ( ),m my x x        (1) де 0y - істинне невідоме значення «виходу» системи; mx R - вектор вхідних змінних; 1( , , )T m   - вектор невідомих параметрів, 1( ) ( ( ), ( ))T T mx x x   - вектор відомих базисних функцій. Представимо результати спостережень за «входами» та «виходами» у ви- гляді матриці значень вхідних змінних X та вектором інтервалів значень для вихідної змінної [ ]Y , тобто у такому вигляді: 11 1 1 1 n i in N Nn x x X x x x x                 ; 1 1; ; ; i i N N y y Y y y y y                                 . (2) Припустимо також, що істинне невідоме значення виходу 0y для кожного із N спостережень знаходиться в інтервалах: 0 , 1,...,i i iy y y i N    . (3) Метод формування оптимального «насиченого блоку» у задачі локалізації розв’язків і Індуктивне моделювання складних систем, випуск 8, 2016 81 Спираючись на умови представлені виразами (1-3), для оцінювання век- тора невідомих параметрів  отримуємо ІСЛАР: 1 1 1 1 1 1 1 1 1 1 ( ) ( ) ( ) ( ) ( ) ( ) m m i i m m i i N N m m N N y b x b x y y b x b x y y b x b x y                                . (4) Розв’язком ІСЛАР (4) є множина  :  mb R Y F b Y      , (5) де { ( ), 1,..., , 1,... }T j iF x i N j m   - відома матриця значень базисних функцій,  , 1, ,iY y i N   та  , 1, ,iY y i N   - вектори, сформовані з верхніх та нижніх меж інтервалів [y , ]i iy  . Із ІСЛАР (4), якщо вона є невиродженою, бачимо, що геометрично її об- ласть розв'язків є опуклим многогранником [3,16]. Обравши будь-який вектор b  , отримуємо математичну модель стати- чної системи у вигляді: ˆ( ) ( ) T y x x b  (6) Усі розв'язки з множини  породжують множину рівнозначних моделей, яку в інтервальному аналізі називають інтервальними моделями. При цьому всі інте- рвальні моделі статичної системи належать такій множині (коридору) [3,13,16]:      ˆ ˆ ˆ[ ] [ ; ],y x y x y x    (7) де    ˆ min ( ) T y x x b b     ,    ˆ max ( ) T y x x b b     - нижня та верхня межі функ- ціонального коридору, відповідно. Зважаючи на спосіб представлення коридору інтервальних моделей, а та- кож на вирази для представлення його нижньої та верхньої межі, можемо стве- рджувати, що властивості області розв'язків ІСЛАР чи їх локалізації безпосере- дньо визначають властивості функціонального коридору (7) інтервальних мо- делей. Зокрема, відомо, якщо використати локалізацію області розв'язків ІСЛАР (4) у вигляді «насиченого блоку», то вона матиме вигляд паралелотопа, який, як відомо, є геометричною фігурою з 2m вершинами і m-попарно парале- льними гранями [2,5-6,14]. Такий спосіб локалізації області розв’язків ІСЛАР має ряд переваг у порівнянні з іншими. Зокрема, встановлено аналітичний зв'я- зок між зазначеною областю локалізації та її гарантованою оптимальною еліп- соїдною оцінкою [5-6,14]: Дивак М.П., Олійник І.С. Індуктивне моделювання складних систем, випуск 8, 2016 82  2( ) ( )m T T m mQ b R b b F E F b b m m          , (8) де  ( ), 1,...,T m iF x i m  – матриця значень базових функцій обраного «насиче- ного блоку»; 1 1 10,5 (( ),...,( ))T m m mb F y y y y         – вектор, який задає центр еліпсоїда;   1 10,5 ,..., ,...,i i m mE diag y y y y y y          – діагональна матриця інтервальних похибок для вибраних базових рівнянь. В результаті отримуємо оптимальну локалізацію коридору інтервальних моделей (7) (в загальному випадку) з кусковими функ- ціональними межами - у вигляді коридору з межами, які представлено достат- ньо гладкими функціями [3,5-6,14]: ( ) ( ) 1 1 [ ( )] [ ( ) ; ( ) ] 2 2m m m T T y x y xb Q b Q b Q y x x b x b              , (9) У виразі (9) за ( ) m y x b Q  позначено функцію похибки прогнозування (ширина коридору), яку обчислюють за формулою[3,13,16]:   1 2 ( ) ( ) ( ) m T T y x m mb Q x F E F x           , (10) Зважаючи на зазначене вище, є доцільним локалізація розв'язків ІСЛАР із застосуванням певним чином сформованого з її рівнянь «насиченого блоку». Одна із обчислювальних реалізацій такого методу, наведена у працях [3,7-8,11]. Для отримання локалізаційної області розв’язків ІСЛАР, необхідно здійснити п’ять основних ітерацій. 1. Вибір із ІСЛАР (4) m базових рівнянь («насиченого блоку»), що утво- рюють сумісну систему. Розв’язком такої системи є область m , яка має вигляд паралелотопа, з вершинами [3]: 1 s m sb F Y  (11) де sY - вектор, складений з межових значень інтервалів [ , ], 1,...,Ni iy y i   . Задача формування набору базових рівнянь у цій послідовності обчис- лень, побудована по аналогії із задачею планування DI -оптимального експери- менту на дискретній множині значень вектора , 1,...,ix i N [3,9-10]:     2 1 1 det minm m FT i i m m i y y F F               , , 1,...,ix i N (12) де  ( ), 1,...,T m iF x i m  , , 1,...,ix i N - стовпчик матриці X . 2. Обчислення деяких скалярних характеристик ( )sL k ( ( )sL k ) для усіх вершин області локалізації на підставі формул [3]: Метод формування оптимального «насиченого блоку» у задачі локалізації розв’язків і Індуктивне моделювання складних систем, випуск 8, 2016 83 1 1( ) ( ) ( )T s k k sL k y x b k     , (13) 1 1 1( ) ( ) ( ) ( )T s k s k s kL k x b k y L k             , (14) де 1kx  – вектор значень вхідних змінних k+1-го рівняння в ІСЛАР (4), яке не увійшло до вибраного «насиченого блоку»; 1 1, k ky y    – нижня та верхня межі інтервалу для значень вихідної змінної в k+1 рівнянні ІСЛАР (4); k 1 1 1k ky y       . 3. Обчислення значень ( 1)i k   та ( 1)i k   , відповідно, за формулами [3]: 1 1 1 1,...,2 1 min { ( ) / ( ) }, ( ( ) 0, 1....,2 ) ( ( ) 0) ( ( ) 0, 1,...,2 )( 1) 0, ( ) 0 m T m s k i s s T m k i s i s L k x f якщо L k s x f L k sk якщо L k                          (15) 1 1 1 1,...,2 1 min { ( ) / ( ) }, ( ( ) 0, 1....,2 ) ( ( ) 0) ( ( ) 0, 1,...,2 )( 1) 0, ( ) 0 m T m s k i s s T m k i s i s L k x f якщо L k s x f L k sk якщо L k                             (16) 4. Обчислення меж інтервалу [ ( 1)iy k  ; ( 1)iy k  ] значень вихідної змін- ної в інтервальних рівняннях «насиченого блоку» на k+1-й ( 1,...,k N m  ) іте- рації за формулою [3]: ( 1) ( ) ( 1)i i iy k y k k      , ( 1) ( ) ( 1)i i iy k y k k      , 1,...,i m . (17) 5. Якщо k N m  , то перехід на крок 2. У протилежному випадку завер- шення процедури. Як бачимо із наведеного алгоритму, на кожній k+1-й ітерації послідовно- сті із п’яти кроків, здійснюємо редукцію інтервальних рівнянь ІСЛАР, залиша- ючи тільки модифіковані за формулою (17) інтервальні рівняння «насиченого блоку». Наведена за допомогою формул (11, 13-17) послідовність обчислень для локалізації розв'язків ІСЛАР на основі виділення її «насиченого блоку» в ціло- му не є складною з обчислювальної точки зору і може бути реалізована у ви- гляді паралельної схеми [4,12]. Разом з тим, в розглянутому методі локалізації області розв’язків ІСЛАР, достатньо складним є перший крок формування «на- сиченого блоку» із розв’язування оптимізаційної задачі (12). Задача, сформу- льована виразом (12) є оптимізаційною задачею з нелінійною функцією мети, яка навіть для задач невеликої розмірності ІСЛАР буде містити велику кіль- Дивак М.П., Олійник І.С. Індуктивне моделювання складних систем, випуск 8, 2016 84 кість локальних мінімумів. Більше того, за обчислювальною складністю така задача суттєво перевищує складність обчислень за формулами (13-17). З іншого боку, довільний вибір «насиченого блоку» (базових рівнянь для локалізації) призводить до втрати змісту в цілому процедури локалізації. За цих умов, застосування для розв’язування прикладних задач методу локалізації об- ласті розв’язків ІСЛАР з виділенням «насиченого блоку» можливе тільки у ви- падку заміни процедури оптимізації за виразом (12) деякою простішою проце- дурою з одночасним забезпеченням умов високої точності інтервальної моделі. 2. Метод формування «насиченого блоку» у задачі локалізації розв’язків ІСЛАР Таким чином, метод локалізації розв’язків ІСЛАР з виділенням «насиченого блоку» повинен забезпечувати високу точність інтервальної моделі, тобто задовільні її прогностичні властивості. Одними з найважливіших прогностичних властивостей інтервальної моделі є максимальна та мінімальна на області вхідних змінних x  похибка прогнозування, відповідно:    max ˆ ˆmax( ) x y x y x        , (18)    min ˆ ˆmin( ) x y x y x        . (19) У випадку використання «насиченого блоку», для оцінки параметрів інтервальної моделі, її мінімальна похибка прогнозування на області вхідних змінних x  досягається в одній із точок заданого набору вхідних змінних , 1,...,jx j m [3,7,11]:    min , 1,.., 1,.., ˆ ˆmin min 2{ } { } j j j j x j m j m y x y x         (20)    min , 1,.., ˆ ˆargmin{ } i j j x j m y x y xx      (21) Процедури обчислення максимальної похибки прогнозування інтервальними моделями, є набагато складнішими, навіть у випадку оцінки її параметрів на основі «насиченого блоку» ІСЛАР [2-3,11]. Розглянемо їх особливості. У праці [3] наведено вирази для обчислення значення похибки в будь-якій точці для зазначеного випадку: ( ) 1 2 ( ) , m y x j j j x x         (22) 1( ) ( )T T mx x F    (23) Метод формування оптимального «насиченого блоку» у задачі локалізації розв’язків і Індуктивне моделювання складних систем, випуск 8, 2016 85 де ( )j x - j-та компонента вектора ( )x , яка у загальному випадку залежить від вибору точки на області експерименту; 0,5 ( )j j jy y     - інтервальні похибки у точках jx спостережень. Спираючись на формули (22), (23), сформулюємо умову вибору «насиченого блоку» із мінімізації максимальної похибки прогнозування на області значень вхідних змінних x  : 1 1 max 2 ( ) min, ( ) ( )m m F T T j j m x j x x x F                    . (24) Вираз (24) забезпечує мінімізацію максимальної похибки прогнозування інтервальної моделі серед усіх можливих «насичених блоків», вибраних із ІСЛАР. Очевидно, що цей вираз може бути використаний в методі локалізації області розв’язків ІСЛАР, реалізацію якого представлено виразами (11)-(17), взамін виразу (12). Разом з тим, оптимізаційна процедура (24) не набагато простіша за процедуру (12), тому потребує подальшого спрощення. Проведемо це спрощення із використанням аналогії з теорії планування послідовних побудови планування послідовних GI -оптимальних планів інтервального експерименту, які мінімізують максимальну похибку прогнозування інтервальних моделей [1,9-10,17-18]. В нашому випадку суть полягає: у плануванні деякої серії експериментів з незначною кількістю спостережень (наприклад, насиченого експерименту); отримання коридору інтервальних моделей; аналіз прогностичних властивостей цих моделей і на цій основі планування наступного одного спостереження [3,17-18]. Зважаючи на вимоги забезпечення оптимальних прогностичних властивостей інтервальної моделі (мінімізації максимальної похибки прогнозування) на області вхідних змінних, доцільно зазначений підхід використати для вибору «насиченого блоку» ІСЛАР, з метою спрощення процедури (24). Зауважимо, що в процедурі GI -оптимального планування на першій ітерації «насичений блок» обрають за GI -критерієм, вираз для якого представлений (24). У нашому випадку така ітерація втрачає сенс по причині високої обчислювальної складності. Тому, на першому кроці методу локалізації ІСЛАР з виділенням «насиченого блоку», цей блок ІСЛАР будемо обирати довільним чином. Отже, нехай структура математичної моделі статичної системи визначена виразом (1) з невідомими параметрами, задано інтервальні дані (2) та сформовано ІСЛАР у вигляді (4). Виберемо з ІСЛАР довільним чином «насичений блок», обчислимо його область розв’язків побудуємо коридор прогнозування інтервальними моделями: Дивак М.П., Олійник І.С. Індуктивне моделювання складних систем, випуск 8, 2016 86 ( ) ( ) 1 1 [ ( )] [ ( ) ; ( ) ] 2 2 T T y x y xy x x b x b          , (25) де ( )y x визначено виразами (22), (23). Тепер, згідно аналогії з процедурою послідовного GI -оптимального планування, спираючись на формули (22), (23), серед , 1,...,ix i N точок експерименту, для яких складена ІСЛАР (4), обчислимо вектор maxx , для якого є максимальне похибка прогнозування: max 1 1,..., 1 arg max 2 ( ) , , 1,..., , ( ) ( ) i m T T j i j i i i m x N j x x x i N x x F                   (26) Зауважимо, що процедура (26) є простою, оскільки виконується на скінченній множині точок , 1,...,ix i N . Отриманий за виразом (26) вектор, є вектором значень вхідних змінних, який визначає певне інтервальне рівняння в ІСЛАР (4). Згідно з процедурою послідовного GI -оптимального планування саме у цій точці необхідно провести наступне вимірювання. Спираючись на формулу (21) для визначення вектора значень вхідних змінних, де забезпечується мінімальна на області експерименту похибка прогнозування, можемо стверджувати, що якби вектор maxx співпадав з вектором значень вхідних змінних одного із інтервальних рівнянь «насиченого блоку» ІСЛАР, то він би задавав точку з мінімальним значенням похибки прогнозування. Звідси, доцільно замінити в поточному «насиченому блоці» одне з інтервальних рівнянь на інтервальне рівняння ІСЛАР з вектором значень вхідних змінних maxx , визначеного за формулою (26). Таким чином, по аналогії з процедурою послідовного GI -оптимального планування «імітуємо» процедуру додаткового вимірювання у точці maxx з максимальною похибкою прогнозування інтервальної моделі, отримуючи вимірювання з мінімальною інтервальною похибкою за формулою (20). Проте, на відміну від процедури GI - оптимального послідовного планування експерименту, зазначену точку обираємо на дискретній множині точок , 1,...,ix i N . Позначимо нижню і верхню межу для отриманого інтервалу за min min ˆ ˆ[ ; ]y y  . Зазначену процедуру проведемо для кожного інтервального рівняння «насиченого блоку». Отримаємо p нових «насичених блоків». Зокрема: у випадку заміни першого інтервального рівняння Метод формування оптимального «насиченого блоку» у задачі локалізації розв’язків і Індуктивне моделювання складних систем, випуск 8, 2016 87 max max min 1 1 min 1 1 1 1 ˆ ˆ( ) ( ) ( ) ( ) ( ) ( ) m m p p m m p p m m m m m m y b x b x y y b x b x y y b x b x y                                ; (27) - у випадку заміни p-го рівняння 1 1 1 1 1 1 max max min 1 1 min 1 1 ( ) ( ) ˆ ˆ( ) ( ) ( ) ( ) m m m m m m m m m m y b x b x y y b x b x y y b x b x y                                ; (28) - у випадку заміни m-го рівняння: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 max max min 1 1 min ( ) ( ) ( ) ( ) ( ) ( ) ˆ ˆ( ) ( ) m m p p m m p p m m m m m m m m y b x b x y y b x b x y y b x b x y y b x b x y                                              . (29) В результаті, для кожного з m «насичених блоків» отримаємо m значень максимальних похибок для відповідних інтервальних моделей: 1 max , 1,..., 1 max 2 ( ) , ( ) ( ) ( ), 1,..., i m p T T jp i j p i i m x i N j x x x F p p m                    , (30) де p - індекс, який в даному випадку означає номер «насиченого блоку», ( )mF p - матриця значень базових функцій для p-го блоку, ( )jp ix - i-та компонента вектора  , обчислена для p-го «насиченого блоку». Очевидно, що для вибору «оптимального насиченого блоку» на цьому кроці взамін складної обчислювальної процедури (24) достатньо вибрати з m «насичених блоків» той, який забезпечує найменше значення послідовності (30), тобто:  max 1,..., argmin , 1,...,opt p m p m F p m     , (31) Застосовуючи процедуру (26), отримуємо maxx - точку, в якій досягається максимальна похибка прогнозу для інтервальної моделі, область параметрів Дивак М.П., Олійник І.С. Індуктивне моделювання складних систем, випуск 8, 2016 88 якої обчислено із обраного у вищеописаний спосіб «насиченого блоку». Далі ітерації продовжуються до тих пір, поки не буде отримано такий «насичений блок», заміна рівнянь якого не призводить до зменшення максимальної похибки прогнозування інтервальними моделями. Алгоритм реалізації методу зобразимо у вигляді такої послідовності кроків: Крок 1. Довільний вибір «насиченого блоку» із ІСЛАР (4). Крок 2. Обчислення вектору maxx для із розв’язування задачі (26). Крок 3. Ітерація поетапної заміни кожного із m інтервальних рівнянь насиченого блоку на інтервальне рівняння ІСЛАР з вектором значень вхідних змінних maxx , формування набору (27)-(29) насичених блоків та обчислення максимальних похибок (22) інтервальних моделей, області параметрів яких обчислено із послідовності насичених блоків, відповідно. Крок 4. Вибір оптимального «насиченого блоку» за критерієм (31). Перехід на крок 2. Зауважимо, що при переході на 2 крок для отриманого «насиченого блоку» відомими будуть як область розв’язків, так і значення максимальної похибки інтервальної моделі, побудованої для цього блоку. Послідовність кроків реалізуємо до тих пір, поки на останньому кроці буде отримано «насичений блок», будь-яка заміна інтервальних рівнянь якого не призводить до зменшення максимальної похибки прогнозування для побудованих інтервальних моделей. Таким чином, запропонований метод здійснює напрямлений, а не повний, перебір «насичених блоків», складених із загальної ІСЛАР із N iнтервальних рівнянь. Варто зазначити, що у випадку відсутності такого напрямленого перебору кількість «насичених блоків», які необхідно проаналізувати (за допомогою складної обчислювальної процедури) визначається за комбінаторно. Наприклад, для випадку ІСЛАР із 30 рівнянь з 5 невідомими необхідно перебрати 142506 «насичених блоків»! Разом з тим, запропонований метод потребує теоретичного обґрунтування, в сенсі доведення ефективності процедури напрямленого перебору. Таке обґрунтування можна здійснити на основі аналізу функції мети, заданої виразом (26). 3. Аналіз функції мети в ітераційній процедурі вибору «насиченого блоку» Очевидно, що складність ітераційної процедури (26) безпосередньо ви- значається властивостями функції мети, тому доцільним є аналіз її властивос- тей. Для цього зробимо таку заміну у виразі (26): 1 1 2( , ,... )m mF N N N  , де N- номер i-го рівняння, вибраного із ІСЛАР (4). В результаті функція мети набуде вигляду: Метод формування оптимального «насиченого блоку» у задачі локалізації розв’язків і Індуктивне моделювання складних систем, випуск 8, 2016 89 max 1 1 2 1,..., 1 ( ,..., ) max 2 ( ) , ( ) ( ) ( , ,... ) i m T T m j i j i i m x N j N N x x x N N N                   (32) Тепер необхідно відобразити властивості цієї функції, в залежності від обраного набору рівнянь в «насиченому блоці». Очевидно, що в загальному ви- падку зробити такий аналіз практично неможливо, але на конкретних прикла- дах можна показати загальні властивості цієї функції. Зокрема, в оптимізацій- них задачах важливо виявити якого виду є функція мети (наприклад, унімода- льна чи багатоекстремальна; непервна чи дискретна і т.д.). Як видно з виразу (32), функція мети в задачі вибору «насиченого блоку» однозначно є дискретною, оскільки її значення визначається конкретним набо- ром інтервальних рівнянь. Очевидним є також факт, що ця функція не є унімо- дальною. Зазначену властивість проілюструємо на прикладі. Запишемо для цього прикладу загальний вигляд рівняння для побудови інтервальної моделі: 0 1( ) ln( )y x b x b x    , (33) Параметри моделі визначатимемо із набору «експериментальних» даних, наведених у таблиці 1. Таблиця 1. Таблиця зімітованих «експериментальних» даних i ix iy iy 1 14 36,976 45,215 2 25 59,424 72,642 3 25 59,502 72,721 4 24 57,471 70,249 5 24 57,566 70,344 6 29 67,288 82,255 7 9 26,13 31,927 8 11 30,551 37,349 9 18 45,325 55,415 10 21 51,43 62,874 11 10 28,459 34,762 12 29 67,277 82,244 13 30 69,207 84,608 14 14 37,082 45,321 15 7 21,377 26,123 16 2 6,652 8,146 Дивак М.П., Олійник І.С. Індуктивне моделювання складних систем, випуск 8, 2016 90 17 24 57,491 70,269 18 15 39,098 47,806 19 15 39,243 47,951 20 24 57,505 70,283 Тоді інтервальна система для знаходження коефіцієнтів моделі матиме такий вигляд: 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 36,976 14 2,639 45,215 59,424 25 3,219 72,642 59,502 25 3,219 72,721 57,471 24 3,178 70,249 57,566 24 3,178 70,344 67,288 29 3,367 82,255 26,13 9 2,197 31,927 30,551 11 2,398 b b b b b b b b b b b b b b b b                         0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 37,349 45,325 18 2,89 55,415 51,43 21 3,044 62,874 28,459 10 2,302 34,762 67,277 29 3,367 82,244 69,207 30 3,401 84,608 37,082 14 2,639 45,321 21,377 7 1,946 26,123 6,652 2 0,693 b b b b b b b b b b b b b b b                        1 0 1 0 1 0 1 0 1 8,146 57,491 24 3,178 70,269 39,098 15 2,708 47,806 39,243 15 2,708 47,951 57,505 24 3,178 70,283 b b b b b b b b b                                          (34) Пронумеруємо рівняння у системі (34). Відповідно, інтервальне рівняння 0 136,976 14 2,639 45,215b b   - отримає номер 1, а інтервальне рівняння 0 157,505 24 3,178 70,283b b   матиме номер 20. Згідно виразу (32) обчислимо значеня функції мети і занесемо їх у табли- цю 2. У таблиці 2, 1N означає номер першого рівняння у «насиченому блоці», 2N - номер другого рівняння. Метод формування оптимального «насиченого блоку» у задачі локалізації розв’язків і Індуктивне моделювання складних систем, випуск 8, 2016 91 Таблиця 2. Значення функції мети (32) На рисунку 1 відображено значення функції мети з таблиці 1. Як бачимо, функція мети є дискретною і має велику кількість локальних мінімумів . Рисунок 1. Поверхня дискретної функції мети (32) Дивак М.П., Олійник І.С. Індуктивне моделювання складних систем, випуск 8, 2016 92 Тепер застосуємо розроблений метод вибору оптимального «насиченого блоку» з ІСЛАР (34). На першому кроці алгоритму реалізації методу виберемо насичений блок (2,4) :  0 1 0 1 59,424 25 3,219 72,642 57,471 24 3,178 70,249 b b b b       (35) Побудована для зазначеного «насиченого блоку» інтервальна модель ха- рактеризується максимальною похибкою прогнозування 176,9 (на рисунку 2 виділено овалом). На наступній ітерації алгоритму реалізації методу формуван- ня набору базових рівнянь «насиченого блоку» «претендентами» є два «насиче- ні блоки» (2,13) та (4,13) , відповідно:  0 1 0 1 59,424 25 3,219 72,642 69,207 30 3,401 84,608 b b b b       , (36)  0 1 0 1 57,471 24 3,178 70,249 69,207 30 3,401 84,608 b b b b       (37) Інтервальні моделі, області параметрів яких обчислено із розв’язування ІСЛАР («насичених блоків») (36), (37), відповідно, характеризуються максима- льними похибками прогнозування, відповідно: 37,47 та 30,28. На рисунку 2 ці значенння максимальних похибок означено ромбами. Отже, «оптимальним насиченим блоком» є (37), який забезпечує меншу максимальну похибку прогнозування інтервальними моделями на області вхід- них змінних 30,28. На наступній ітерації реалізації методу претендентами є «насичені блоки» (4,14) та (13,14) :  0 1 0 1 57,471 24 3,178 70,249 37,082 14 2,639 45,321 b b b b       , (38)  0 1 0 1 69,207 30 3,401 84,608 37,082 14 2,639 45,321 b b b b       (39) Інтервальні моделі, побудовані на основі «насичених блоків» (38), (39) характеризуються максимальними похибками прогнозування, відповідно: 37 та 15,4 (рисунок 2). Отже, «оптимальним насиченим блоком» є ІСЛАР (39), який забезпечує числове значення 15,4 функції мети - мінімум максимальної похиб- ки для інтервальних моделей. Метод формування оптимального «насиченого блоку» у задачі локалізації розв’язків і Індуктивне моделювання складних систем, випуск 8, 2016 93 Рисунок 2. Таблиця значень функції мети з ілюстрацією кроків реалізації методу формування оптимального «насиченого блоку» для початкових умов (2,4) На рисунку 3 стрілками проілюстровано рух по поверхні функції мети, який за- безпечує алгоритм реалізації методу формування оптимального «насиченого блоку». Рисунок 3. Зображення функції мети з ілюстрацією кроків реалізації методу формування набору базових рівнянь «насиченого блоку» для початкових умов (2,4) Дивак М.П., Олійник І.С. Індуктивне моделювання складних систем, випуск 8, 2016 94 Як бачимо, замість повного перебору «насичених блоків» із ІСЛАР (34) в кількості 195, запропонований метод, для вибору оптимального, проаналізував – 5. Тепер перейдемо до аналізу впливу початкових умов для методу форму- вання набору базових рівнянь «насиченого блоку» на результат його реалізації. Скористаємося тим самим прикладом, але іншими початковими умовами. На першому кроці алгоритму реалізації методу в цьому випадку виберемо «наси- чений блок» з ІСЛАР (34) (8,18) :  0 1 0 1 30,551 11 2,398 37,349 39,098 15 2,708 47,806 b b b b       (40) Побудована для зазначеного «насиченого блоку» інтервальна модель ха- рактеризується максимальною похибкою прогнозування 161,36 (на рисунку 4 виділено овалом). На наступній ітерації алгоритму реалізації методу формуван- ня набору базових рівнянь «насиченого блоку» «претендентами» є два «насиче- ні блоки» (8,13) та (13,18) :  0 1 0 1 30,551 11 2,398 37,349 69,207 30 3,401 84,608 b b b b       , (41)  0 1 0 1 69,207 30 3,401 84,608 39,098 15 2,708 47,806 b b b b       (42) Інтервальні моделі, області параметрів яких обчислено із розв’язування ІСЛАР («насичених блоків») (41), (42), відповідно, характеризуються однако- вими максимальними похибками прогнозування 15,40. На рисунку 4 ці значен- ня максимальних похибок означено ромбами. Отже, «оптимальним насиченим блоком» є (41), який забезпечує числове значеня 15,4 функції мети – мінімум максимальної похибки прогнозування для інтервальних моделей. Метод формування оптимального «насиченого блоку» у задачі локалізації розв’язків і Індуктивне моделювання складних систем, випуск 8, 2016 95 Рисунок 4. Таблиця значень функції мети з ілюстрацією кроків реалізації методу формування набору базових рівнянь «насиченого блоку» для початкових умов (8,18) Рисунок 5. Зображення функції мети з ілюстрацією кроків реалізації методу формування набору базових рівнянь «насиченого блоку» для початкових умов (8,18) Дивак М.П., Олійник І.С. Індуктивне моделювання складних систем, випуск 8, 2016 96 Нехай обрано інший «насичений блок» з ІСЛАР (34), наприклад (3,10) :  0 1 0 1 59,502 25 3,219 72,721 51,43 21 3,044 62,874 b b b b       (43) Побудована для зазначеного «насиченого блоку» інтервальна модель ха- рактеризується максимальною похибкою прогнозування 56,87 (на рисунку 6 виділено овалом). На наступній ітерації алгоритму реалізації методу формуван- ня набору базових рівнянь «насиченого блоку» «претендентами» є два «насиче- ні блоки» (3,13) та (10,13) :  0 1 0 1 59,502 25 3,219 72,721 69,207 30 3,401 84,608 b b b b       , (44)  0 1 0 1 51,43 21 3,044 62,874 69,207 30 3,401 84,608 b b b b       (45) Інтервальні моделі, області параметрів яких обчислено із розв’язування ІСЛАР («насичених блоків») (44), (45), відповідно, характеризуються максима- льними похибками прогнозування, відповідно: 37,47 та 18,35. На рисунку 6 ці значенння максимальних похибок означено ромбами. Отже, «оптимальним насиченим блоком» є (45), який забезпечує меншу максимальну похибку прогнозування інтервальними моделями на області вхід- них змінних 18,35. На наступній ітерації реалізації методу претендентами є «насичені блоки» (10,14) та (13,14) :  0 1 0 1 57,471 24 3,178 70,249 37,082 14 2,639 45,321 b b b b       , (46)  0 1 0 1 69,207 30 3,401 84,608 37,082 14 2,639 45,321 b b b b       (47) Інтервальні моделі, побудовані на основі «насичених блоків» (46), (47) характеризуються максимальними похибками прогнозування, відповідно: 61,94 та 15,4 (рисунок 6). Отже, «оптимальним насиченим блоком» є ІСЛАР (47), який забезпечує числове значення 15,4 функції мети – мінімум максимальної похибки для інтервальних моделей. Метод формування оптимального «насиченого блоку» у задачі локалізації розв’язків і Індуктивне моделювання складних систем, випуск 8, 2016 97 Рисунок 6. Таблиця значень функції мети з ілюстрацією кроків реалізації методу формування набору базових рівнянь «насиченого блоку» для початкових умов (3,10) Рисунок 7. Зображення функції мети з ілюстрацією кроків реалізації методу формування набору базових рівнянь «насиченого блоку» для початкових умов (3,10) Дивак М.П., Олійник І.С. Індуктивне моделювання складних систем, випуск 8, 2016 98 Аналогічні приклади були розглянуті для різних початкових «насичених блоків» загальною кількістю 10. В кожному із 10 випадків результат застосу- вання методу збігався до значення максимальної похибки прогнозування 15,4. Це засвідчує збіжність обчислювальної процедури реалізації методу, принаймні для даного випадку. Хоча для загального випадку властивості методу ще необ- хідно дослідити. Як бачимо, на кожному кроці застосування методу дає можливість здійс- нити напрямлений перебір до локального мінімуму. На прикладах показано, що в даних задачах існує однозначний розв’язок, знайдений для різних початкових умов. З обчислювальної точки зору запропонований метод є простішим, у порі- внянні з відомими методами локалізації розв’язків ІСЛАР на основі виділення насиченого блоку методами планування оптимального експерименту. Висновки. Вперше запропоновано метод формування набору базових рівнянь у задачі локалізації розв’язків ІСЛАР на основі «насиченого блоку». Запропонований метод, на відміну від існуючих ґрунтується на розв’язуванні оптимізаційної задачі, з критерієм мінімізації максимальної похибки прогнозування для інтервальних моделей, область оцінок параметрів яких локалізована областю розв’язків ІСЛАР у вигляді «насиченого блоку». Досліджено властивості запропонованого методу, показано його ефективність та переваги (з точки зору обчислювальної складності та збіжності), у порівнянні з методами, що ґрунтуються на плануванні інтервальних експериментів. Запропонований метод може широко використовуватися в задачах побудови інтервальних моделей з заданими прогностичними властивостями. Література 1. Дивак М.П. Використання насиченого експерименту для оцінювання па- раметрів інтервальної моделі при аналізі інтервальних даних // Автоматика. Автоматизация. Электротехнические комплексы и системы. – 1999. – № 2. – с. 33–36. 2. Дивак М.П. Метод локалізації гарантованих оцінок в задачах параметри- чної ідентифікації // Вимірювальна та обчислювальна техніка в технологічних процесах. – 2000. №4. - с.12-17. 3. Дивак М.П. Задачі математичного моделювання статичних систем з інте- рвальними даними: монографія // Тернопіль: Економічна думка, 2011. – 216 с. 4. Дивак М.П. , Стахів П.Г. Реалізація методу локалізації параметрів інтер- вальних моделей з виділенням насиченого блоку експерименту на паралельних обчислювальних графах. // Электроника и связь. – 2001. №12. – с. 120-124. 5. Кунцевич В., Лычак М. Получение гарантированных оценок в задачах параметрической идентификации // Автоматика. – 1982. – № 4. – с. 49-59. Метод формування оптимального «насиченого блоку» у задачі локалізації розв’язків і Індуктивне моделювання складних систем, випуск 8, 2016 99 6. Куржанский А.Б. Задача идентификации – теория гарантированных оце- нок // Автоматика и телемеханика. – 1991. – № 4. – с. 3 –26. 7. Dyvak M., Manzhula V., Kozak O., New method tolerance estimation of the parameters set of interval model based on saturated block of ISLAE // Proceeding of the IX–th International Conference CADSM’2007. – Lviv–Polyana, 2007. – p. 376- 379. 8. Dyvak M., Oliynyk I., Kasatkina N. Reduction of Interval Equations for Interval System of Linear Algebraic Equations // Modern Problems of Radio Engineering, Telecommunications and Computer Sience of abstracts of the 13th International Conference TCSET’2016. – Lviv-Slavsko, Ukraine. – February 23-26, 2016. P. 128-131. 9. Dyvak, M., Pukas, A. Criterion of design of experiments for tasks of decision support interval model creation // Proceedings of the Third Workshop – 2005 IEEE Intelligent Data Acquisition and Advanced Computing Systems: Techology and Applications, IDAACS 2005, p.495-497, 2005. 10. Dyvak М., Pukas A. Identification of the static system interval models by application of optimal localization experiment // The Experience of Designing and Application of CAD Systems in Microelectronics. Proc. of the VII Intern. Conf. – Lviv-Slavske: National University „Lviv Polytechnic”, 2003. – P. 180-184. 11. Dyvak M., Pukas A. and Kozak O. Tolerance estimation of parameters set of models created on experimental data //Modern Problems of Radio Engineering, Telecommunications and Computer Science» 2008 Proceedings of International Conference on, Lviv-Slavsko, 2008, p. 24-26. 12. Dyvak M., Pukas A., Stakhiv P. Algorithms of Parallel Calculations in Task of Tolerance Ellipsoidal Estimation of Interval Model Parameters // Bulletin of the Polish Academy of sciences – Technical sciences, ISSN 0239-7528, Vol. 60, Issue 1, 2012, p.159-164. 13. Götz Alefeld and Jürgen Herzberger. Introduction to interval computations, Computer Science and Applied Mathematics // Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York, 1983. 14. Kurzhanski A. and Valyi I., Ellipsoidal Calculus for Estimation and Control. // Birkhauser, Berlin, 1997. 15. Letzky E., Voshinin A., Dyvak M., Simoff S., Orlov A., Gorsky V., Nikitina E., Nosov V. Design of experiments and data analysis: New trends and results // Moscow, ANTAL, 1993, 192 pages. 16. Shary S.P. Algebraic Approach to the Interval Linear Static Identification, Tolerance, and Control Problems, or One More Application of Kaucher Arithmetic. // Reliable Computing 2(1) (1996), p. 3–33. 17. Walter E. and Pronzato L. Identification of parametric model from experimental data. // London, Berlin, Heidelberg, New York, Paris, Tokyo: Springer, 1997. – 413 p. 18. Wu C. F. J., Hamada M. S., Experiments: Planning, Analysis and Optimization // Wiley, 2009, 743 p.