Про пришвидшення оптимізаційних методів для задачі синтезу багатошарових оптичних покриттів

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

Full description

Saved in:

Bibliographic Details
Date:	2021
Main Authors:	Міца, О.В., Стецюк, П.I., Левчук, О.М., Пецко, В.I., Повхан, I.Ф.
Format:	Article
Language:	Ukrainian
Published:	Інститут кібернетики ім. В.М. Глушкова НАН України 2021
Series:	Проблемы управления и информатики
Subjects:	Методы оптимизации и оптимальное управление
Online Access:	https://nasplib.isofts.kiev.ua/handle/123456789/209042
Tags:	Add Tag No Tags, Be the first to tag this record!
Journal Title:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Cite this:	Про пришвидшення оптимізаційних методів для задачі синтезу багатошарових оптичних покриттів / О.В. Міца, П.I. Стецюк, О.М. Левчук, В.I. Пецко, I.Ф. Повхан // Проблемы управления и информатики. — 2021. — № 6. — С. 13-26. — Бібліогр.: 12 назв. — укр.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	nasplib_isofts_kiev_ua-123456789-209042
record_format	dspace
spelling	nasplib_isofts_kiev_ua-123456789-2090422025-11-13T01:05:41Z Про пришвидшення оптимізаційних методів для задачі синтезу багатошарових оптичних покриттів О ускорении оптимизационных методов для задачи синтеза многослойных оптических покрытий On accelerating optimization methods for the problem of multilayer optical coatings synthesis Міца, О.В. Стецюк, П.I. Левчук, О.М. Пецко, В.I. Повхан, I.Ф. Методы оптимизации и оптимальное управление Розглянуто п’ять способів для пришвидшення багатовимірного пошуку розв’язку задачі синтезу багатошарових оптичних покриттів за допомогою методів нульового та першого порядків. Перший спосіб — це використання аналітичної похідної для цільової функції якості багатошарового покриття. Він дозволяє точно (у межах комп’ютерної арифметики) обчислити значення градієнта гладкої цільової функції та узагальненого градієнта негладкої цільової функції. Перший спосіб потребує таку ж кількість арифметичних операцій, як і скінченно-різницеві способи обчислення градієнта та узагальненого градієнта. Другий спосіб — це використання пришвидшеного знаходження градієнта цільової функції за допомогою використання префікс- та суфікс-масивів у аналітичному способі обчислення градієнта. Цей прийом дозволяє зменшити кількість арифметичних операцій втричі для задач великої розмірності. Третій спосіб — це використання табуляції значень тригонометричних функцій для обчислення характеристичних матриць. Цей прийом зменшує час виконання операцій множення характеристичних матриць у десятки разів в залежності від характеристик комп’ютера. Для деяких архітектур комп’ютера ця перевага становить більше ніж 140 разів. Четвертий спосіб — це використання методу золотого перерізу для одновимірної оптимізації в задачах синтезу оптичних покриттів. Зокрема, при розв’язанні однієї часткової задачі показано, що метод тернарного пошуку потребує приблизно на 40 % більше часових затрат, ніж метод золотого перерізу. П’ятий спосіб — це використання ефективної реалізації множення двох матриць. Вона полягає у зміні порядку другого і третього циклів для загальновідомого методу множення двох матриць та фіксації у звичайній змінній значення елемента першої матриці. Це дозволяє суттєво прискорити виконання операції множення двох матриць. Для матриць розмірності 1000×1000 придшвидшення складає від 2 до 15 разів — залежно від характеристик комп’ютера. Five ways to speed up the multidimensional search in order to solve the problem of synthesis of multilayer optical coatings by using the methods of zero and first orders have been considered. The first way is to use an analytical derivative for the target quality function of the multilayer coating. It allows us to calculate accurately (within the computer arithmetic) the value of the gradient of a smooth objective function and generalized gradient of a non-smooth objective one. The first way requires the same number of arithmetic operations as well as finite-difference methods of calculating the gradient and the generalized gradient. The second way is to use a speedy finding of the objective function gradient using the prefix- and suffix-arrays in the analytical method of calculating the gradient. This technique allows us to reduce the number of arithmetic operations thrice for large-scale problems. The third way is the use of tabulating the values of trigonometric functions to calculate the characteristic matrices. This technique reduces the execution time of multiplication operations of characteristic matrices ten times depending on the computer’s specifications. For some computer architectures, this advantage is more than 140 times. The fourth method is the use of the golden section method for the one-dimensional optimization in the problems of synthesis of optical coatings. In particular, when solving one partial problem it is shown that the ternary search method requires approximately 40% more time than the golden section method. The fifth way is to use the effective implementation of multiplication of two matrices. It lies in changing the order of the second and third cycles for the well-known method of multiplying two matrices and fixing in a common variable value of the element of the first matrix. This allows us to speed up significantly the multiplication operation of two matrices. For matrices having 1000 x 1000 dimension the acceleration is from 2 to 15 times, depending on the computer's specifications. 2021 Article Про пришвидшення оптимізаційних методів для задачі синтезу багатошарових оптичних покриттів / О.В. Міца, П.I. Стецюк, О.М. Левчук, В.I. Пецко, I.Ф. Повхан // Проблемы управления и информатики. — 2021. — № 6. — С. 13-26. — Бібліогр.: 12 назв. — укр. 0572-2691 https://nasplib.isofts.kiev.ua/handle/123456789/209042 519.87; 535.345.67 10.34229/1028-0979-2021-6-2 uk Проблемы управления и информатики application/pdf Інститут кібернетики ім. В.М. Глушкова НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Ukrainian
topic	Методы оптимизации и оптимальное управление Методы оптимизации и оптимальное управление
spellingShingle	Методы оптимизации и оптимальное управление Методы оптимизации и оптимальное управление Міца, О.В. Стецюк, П.I. Левчук, О.М. Пецко, В.I. Повхан, I.Ф. Про пришвидшення оптимізаційних методів для задачі синтезу багатошарових оптичних покриттів Проблемы управления и информатики
description	Розглянуто п’ять способів для пришвидшення багатовимірного пошуку розв’язку задачі синтезу багатошарових оптичних покриттів за допомогою методів нульового та першого порядків. Перший спосіб — це використання аналітичної похідної для цільової функції якості багатошарового покриття. Він дозволяє точно (у межах комп’ютерної арифметики) обчислити значення градієнта гладкої цільової функції та узагальненого градієнта негладкої цільової функції. Перший спосіб потребує таку ж кількість арифметичних операцій, як і скінченно-різницеві способи обчислення градієнта та узагальненого градієнта. Другий спосіб — це використання пришвидшеного знаходження градієнта цільової функції за допомогою використання префікс- та суфікс-масивів у аналітичному способі обчислення градієнта. Цей прийом дозволяє зменшити кількість арифметичних операцій втричі для задач великої розмірності. Третій спосіб — це використання табуляції значень тригонометричних функцій для обчислення характеристичних матриць. Цей прийом зменшує час виконання операцій множення характеристичних матриць у десятки разів в залежності від характеристик комп’ютера. Для деяких архітектур комп’ютера ця перевага становить більше ніж 140 разів. Четвертий спосіб — це використання методу золотого перерізу для одновимірної оптимізації в задачах синтезу оптичних покриттів. Зокрема, при розв’язанні однієї часткової задачі показано, що метод тернарного пошуку потребує приблизно на 40 % більше часових затрат, ніж метод золотого перерізу. П’ятий спосіб — це використання ефективної реалізації множення двох матриць. Вона полягає у зміні порядку другого і третього циклів для загальновідомого методу множення двох матриць та фіксації у звичайній змінній значення елемента першої матриці. Це дозволяє суттєво прискорити виконання операції множення двох матриць. Для матриць розмірності 1000×1000 придшвидшення складає від 2 до 15 разів — залежно від характеристик комп’ютера.
format	Article
author	Міца, О.В. Стецюк, П.I. Левчук, О.М. Пецко, В.I. Повхан, I.Ф.
author_facet	Міца, О.В. Стецюк, П.I. Левчук, О.М. Пецко, В.I. Повхан, I.Ф.
author_sort	Міца, О.В.
title	Про пришвидшення оптимізаційних методів для задачі синтезу багатошарових оптичних покриттів
title_short	Про пришвидшення оптимізаційних методів для задачі синтезу багатошарових оптичних покриттів
title_full	Про пришвидшення оптимізаційних методів для задачі синтезу багатошарових оптичних покриттів
title_fullStr	Про пришвидшення оптимізаційних методів для задачі синтезу багатошарових оптичних покриттів
title_full_unstemmed	Про пришвидшення оптимізаційних методів для задачі синтезу багатошарових оптичних покриттів
title_sort	про пришвидшення оптимізаційних методів для задачі синтезу багатошарових оптичних покриттів
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate	2021
topic_facet	Методы оптимизации и оптимальное управление
url	https://nasplib.isofts.kiev.ua/handle/123456789/209042
citation_txt	Про пришвидшення оптимізаційних методів для задачі синтезу багатошарових оптичних покриттів / О.В. Міца, П.I. Стецюк, О.М. Левчук, В.I. Пецко, I.Ф. Повхан // Проблемы управления и информатики. — 2021. — № 6. — С. 13-26. — Бібліогр.: 12 назв. — укр.
series	Проблемы управления и информатики
work_keys_str_mv	AT mícaov proprišvidšennâoptimízacíjnihmetodívdlâzadačísintezubagatošarovihoptičnihpokrittív AT stecûkpi proprišvidšennâoptimízacíjnihmetodívdlâzadačísintezubagatošarovihoptičnihpokrittív AT levčukom proprišvidšennâoptimízacíjnihmetodívdlâzadačísintezubagatošarovihoptičnihpokrittív AT peckovi proprišvidšennâoptimízacíjnihmetodívdlâzadačísintezubagatošarovihoptičnihpokrittív AT povhanif proprišvidšennâoptimízacíjnihmetodívdlâzadačísintezubagatošarovihoptičnihpokrittív AT mícaov ouskoreniioptimizacionnyhmetodovdlâzadačisintezamnogoslojnyhoptičeskihpokrytij AT stecûkpi ouskoreniioptimizacionnyhmetodovdlâzadačisintezamnogoslojnyhoptičeskihpokrytij AT levčukom ouskoreniioptimizacionnyhmetodovdlâzadačisintezamnogoslojnyhoptičeskihpokrytij AT peckovi ouskoreniioptimizacionnyhmetodovdlâzadačisintezamnogoslojnyhoptičeskihpokrytij AT povhanif ouskoreniioptimizacionnyhmetodovdlâzadačisintezamnogoslojnyhoptičeskihpokrytij AT mícaov onacceleratingoptimizationmethodsfortheproblemofmultilayeropticalcoatingssynthesis AT stecûkpi onacceleratingoptimizationmethodsfortheproblemofmultilayeropticalcoatingssynthesis AT levčukom onacceleratingoptimizationmethodsfortheproblemofmultilayeropticalcoatingssynthesis AT peckovi onacceleratingoptimizationmethodsfortheproblemofmultilayeropticalcoatingssynthesis AT povhanif onacceleratingoptimizationmethodsfortheproblemofmultilayeropticalcoatingssynthesis
first_indexed	2025-11-29T12:32:37Z
last_indexed	2025-11-29T12:32:37Z
_version_	1850128011142103040
fulltext	© О.В. МІЦА, П.І. СТЕЦЮК, О.М. ЛЕВЧУК, В.І. ПЕЦКО, І.Ф. ПОВХАН, 2021 Международный научно-технический журнал «Проблемы управления и информатики», 2021, № 6 13 УДК 519.87; 535.345.67 О.В. Міца, П.І. Стецюк, О.М. Левчук, В.І. Пецко, І.Ф. Повхан ПРО ПРИШВИДШЕННЯ ОПТИМІЗАЦІЙНИХ МЕТОДІВ ДЛЯ ЗАДАЧІ СИНТЕЗУ БАГАТОШАРОВИХ ОПТИЧНИХ ПОКРИТТІВ Ключові слова: багатошарові оптичні покриття, спектральні характеристики, синтез оптичних покриттів, аналітична похідна, узагальнений градієнт, метод золотого перерізу. Ключевые слова: многослойные покрытия, спектральные характеристики, син- тез оптических покрытий, аналитическая производная, обобщенный градиент, метод золотого сечения. Вступ Багатошарові оптичні покриття створюються шляхом напилення тонких діе- лектричних шарів, знаходять широке застосування в сучасних оптичних пристро- ях, пов'язаних з вивченням і формуванням оптичного випромінювання, а також в таких областях високих технологій, як лазерна техніка, оптоелектроніка, телеко- мунікації [1–5]. Першочерговим завданням при конструюванні таких структур за- лишається забезпечення максимальної селективності та експлуатаційної надійно- сті таких структур під час використання мінімальної кількості тонкоплівкових шарів у структурах [6]. Такі задачі описано у дисертаційній роботі [7]. Розгляда- ються можливості, які дозволяють пришвидшити роботу відомих оптимізаційних заходів для синтезу багатошарових оптичних покриттів. Постановка задачі Задача синтезу багатошарових оптичних покриттів полягає в знаходженні та- ких параметрів багатошарового оптичного покриття — показників заломлення та геометричних товщин шарів 1 2 ( , , , ) N d d d d  (N — кількість шарів), щоб функ- ціонал, який введено для оцінки якості коефіцієнтів пропускання, був мінімаль- ним на заданому спектральному діапазоні 1 2 [ ], :  * * * , ( , min ( , )) n d F F n d F n d  (1) при обмеженнях min max 1 2, , , , , i i i n n n i N    (2) min max 1 2, , , , , i i i d d d i N    (3) де F — мінімальне значення функції якості покриття. Функціями якості покриття в задачі (1)‒(3) можуть бути: 2 1 1 1 λ (λ)( , ) ( ( , )) ,, L i i ideal i i F n d w T n d T L    (4) 2 1 1 λ (λ( , ) ( ) ), , L i i ideal i i F n d w T n d T L    , (5) 3 i 1 L λ (λ , , ( , ) max ( , , ) ) i i ideal i F n d w T n d T     , (6) 14 ISSN 1028-0979 де i w — вагові коефіцієнти, що визначають внесок у цільову функцію при дов- жині хвилі , i  L — число точок сітки спектрального інтервалу від 1  до 2 , λ( , , ) i T n d — значення коефіцієнта пропускання для параметрів ( , )n d та довжи- ни хвилі , i  (λ ) ideal i T — значення коефіцієнта пропускання, який потрібно досяг- нути при довжині хвилі . i  Значення коефіцієнта пропускання енергії електромагнітної хвилі довжини  через багатошарову оптичну структуру при падінні світла на поверхню під ку- том 0  обчислюється за допомогою коефіцієнтів характеристичної матриці λ)( , ,M n d таким чином: 0 2 2 2 20 11 22 0 12 21 0 0 4 λ 1 2 )( , , , , s s s s T n d p p M M p p M M p p p p      (7) де 0 0 0 cosp n  і cos s s s p n  — для ТЕ-хвилі (s — поляризація); 0 0 0 cos n p   і cos s s s n p   — для ТМ-хвилі (p — поляризація); 0  — кут, під яким промінь падає на багатошарову структуру; s  — кут, під яким промінь виходить із бага- тошарової структури; 0 ,n s n — показники заломлення зовнішнього середовища та підкладинки відповідно. Характеристична матриця N -шарової структури рівна добутку матриць кож- ного із шарів: 0 1 1 1 2 2 2 1 1 1 λ λ λ λ λ ( , , , ( , , , ( , , ,) ) ) ) ),( , , , ( , , , N N N N N N M n d M n d M n d M n d M n d                  (8) де характеристична матриця одного шару рівна cos λ sin λ λ sin λ cos λ ( , , , ) ( , , , ) ( , , , ) ( , , , ) ( , , , ) i n d n d nM n d i n n d n d                , 2 cos λ λ ( , , , ) n d n d          — фазова товщина шару, 1,i    — кут між променем і нормаллю до площини падіння. Кути між променем і нормаллю до площини падіння для кожного із шарів пов’язані законом Снеліуса і легко визначаються зі співвідношення 0 0 1 1 sin sin sin sin sin . j j N N s s n n n n n         Международный научно-технический журнал «Проблемы управления и информатики», 2021, № 6 15 Способи обчислення узагальненого градієнта Розглянемо скінченно-різницевий метод обчислення градієнта функції ( , ).F n d Нехай і е — N -вимірний вектор, i -та компонента якого рівна одиниці, усі інші компоненти рівні нулю. Задаємо досить малі величини i n та , i d 1, , .i N  Тоді компоненти градієнта функції ( , )F n d в точці ( , ) k k n d будуть обчислюватись за допомогою формул 1 ) ) ) ( , ( , ( , , , , ,k i i k k k i k k i F n n e d F n d F n d i N n        1 ( , ( , ) ) ( , , , , .) k k i i k k N i k k i F n d d e F n d F n d i N d        Твердження 1. Для обчислення градієнта функції ( , )F n d скінченно-різ- ницевий метод вимагає 0 2 1 1 ( ) ( )N N N L     операцій множення характерис- тичних матриць. Доведення. Для знаходження значення ( , ) k k F n d потрібно 1( )N  операцій множення характеристичних матриць. Для кожного з 2N параметрів, для яких потрібно обчислити значення ( ), k i i k F n n e d або , )( , k k i i F n d d e потрібно також 1( )N  таких операцій. Ці операції необхідно зробити для кожної з L виб- раних значень довжин хвиль. Відповідно кількість операцій буде рівна 0 1 2 1 2 1 1* (( ) ( )) ( ) ( ) .N N N N L N N L          Твердження доведено. Аналітичний спосіб обчислення градієнта функції ( , )F n d позбавлений не- доліків, властивих скінченно-різницевому способу. Безпосереднє диференціюван- ня функції 1 ( , )F n d дає формули для знаходження компонента її градієнта в точ- ці ( , ) : k k n d 1 1 1 2 1 ( , ( , ( ( , ) , ,... , ) , ) ,) L k k i k k k k j j j ij T n d F n d T n d T i N L n         , 1 1 1 2 1 ( , ( , ( ( , ) , , ) ,.., ., ,) ) L k k N i k k k k j j ij j T n d F n d T n d T i N L d           та формули для знаходження узагальнених градієнтів: 2 1 1 sign 1 ( , , ) ( , ( ( , , ) ) , ,..., ,) L k k j i k k k k j j ij T n d F n d T n d T i N L n           2 1 1 sign 1 ( , , ) ( , ) ( ( , , ) ) , ,..., , L k k j N i k k k k j j ij T n d F n d T n d T i N L d           16 ISSN 1028-0979 3 sign 1 * * * ( , , ) ( , ) ( ( , , ) , ,..) ., , k k j i k k j j i T n d F n d T n d T i N n         3 sign 1 * * * ( , , ) ( , ) ( ( , , ) , ,. .,) . , k k j N i k k j j i T n d F n d T n d T i N d         де 1 L argmax λ* , , )( , , j j j j T n d T     . У випадку цільової функції (4) це буде градієнт, а у випадку цільової функ- ції (5), (6) — узагальнений градієнт. Узагальнений градієнт використовується при розв’язанні задач синтезу багатошарових оптичних покриттів за допомогою мето- дів негладкої оптимізації [8, 9]. Отже, для аналітичного обчислення 1 ( , ) k k F n d , 2 ( , ) k k F n d та 3 ( , ) k k F n d достатньо для всіх 1, ,i N  уміти знаходити аналітичні вирази для похідних ,( , ) k k j i T n d n   та ,( , ) k k j i T n d d   при фіксованому значенні . Використовуючи ці похідні (7), легко знайти для кожного 1( )i i N  за таким правилом [10]: 0 11 22 12 21 11 22 0 12 21 0 0 2 2 2 2 20 11 22 0 12 21 0 0 1 8 1 2 ,, , )( s s s i i i s i i s s s s n nm m m m m m n n m m T n d n n n n n n n n n n n m m n n m m n n n n                               0 11 22 12 21 11 22 0 12 21 0 0 2 2 2 2 20 11 22 0 12 21 0 0 1 8 1 2 ,, , )( s s s i i i s i i s s s s n nm m m m m m n n m m T n d n d n d d n n d d n n m m n n m m n n n n                               де 11 12 21 22 11 12 21 22, , , , , , , i i i i i i i i m m m m m m m m n n n n d d d d                 — коефіцієнти наступних 2 2( ) -матриць: 11 12 21 22 ,, )( i i i i i m m i n nM n d n m m i n n            ; 11 12 21 22 ,, )( i i i i i m m i d dM n d d m m i d d            . Международный научно-технический журнал «Проблемы управления и информатики», 2021, № 6 17 Матриці ,( , ) i M n d n    та ,( , ) i M n d d    легко розрахувати, використовуючи (8): 1 1 1 1 2 ( , ( , ( ) , , ) ), , , N k k k M n d M n d M n d n n           1 1 1 2 1 , ,( , ( , , ) ( , , ), , , ) , , i N i i k k k k i ik k i M n dM n d M n d M n d i N n n                  1 1 ( , ( , , ) ( , , ) , ) , N N N k k N Nk M n d M n d M n d n n            1 1 1 1 2 ( , ( , ,, ) ) ( , , ), N k k k M n d M n d M n d d d           1 1 1 2 1 ( , ( , , ), ) ( , , ) ( , , ), , , , i N i i k k k k i ik k i M n d M n d M n d M n d i N d d                   1 1 ( , ( , , ) ( , , ) , ) , N N N k k N Nk M n d M n d M n d d d            (9) де матриця 2 2( ) — матриці ,( , ) i M n d n    та ,( , , ) i M n d d   для кожного 1, ,i N  матимуть наступний вигляд: 2 21 2 2 cos sin ( , , ) sin cos k k k k k j k k ji i i k k k k k k j k j n d n d i n n nM n d n n d n d i n n n                                                                   2 2 2 2 2 2 2 2 sin cos cos sin i i i i i i j j i j j i i i i i i i j j j j d n d d n di n d n d d n d in                                                , 2 21 2 2 cos sin ( , , ) sin cos k k k k k j k k ji i i k k k k k k j k j n d n d i d d nM n d d n d n d i n d d                                                                   18 ISSN 1028-0979 2 2 2 2 2 2 2 2 sin cos cos sin i i i i i i j j i j j i i i i i i i j j j j n n d n n di n n n d n n d in                                                . Аналітичний спосіб дозволяє обчислити точне (у межах комп’ютерної ариф- метики) значення градієнта функції ( , )F n d в точці ),( , k k n d за затратами ариф- метичних операцій він такий, як і в скінченно-різницевому способі. Аналітичний спосіб доцільніше використовувати, ніж скінченно-різницевий, коли потрібна ви- сока точність знаходження оптимальних параметрів * ).( ,n d Твердження 2. Для обчислення градієнта функції ( , )F n d аналітичним способом кількість операцій множення характеристичних матриць рівна 1 N  2 1( ) .N N L  Пришвидшення оптимізаційних методів Знаходження значення функції якості та її градієнта (узагальненого градієн- та) є основними операціями при розв’язанні задачі синтезу оптичних покриттів. Відповідно для пришвидшення роботи методів багатовимірного пошуку пропону- ється використати такі вдосконалення. 1. Використати аналітичну похідну при використанні градієнтних мето- дів. Операції множення характеристичних матриць найбільш ресурсозатратні при знаходженні похідних. Перевагою аналітичного підходу є не лише менша на 1( )N  кількість таких операцій, а насамперед — більша точність і, як наслідок, менша кількість ітерацій. 2. Пришвидшене множення матриць. Пришвидшена реалізація [11], при якій забирається повторюване множення матриць для різних 1, , ,i N  властива прямолінійній реалізації. Суть прискореної реалізації полягає в наступному. Об- числюємо такі префікс-матриці: 1 1 1( , , ), , , . i i k k j k M M n d i N       Обчислюємо такі суфікс-матриці: 1 2( , , ), , , . N i k k j k M M n d i N      Для цього досить 2 2( )N  операцій помножених матриць розміром 2 2( .) Далі для знаходження матриць ( , , ) i M n d n    та ( , , ) i M n d d    для всіх 1, ,i N  замість (9) використовуємо такі формули: 1 1 2 1 1 ( , , ) ( , , , ) j j M n d M n d М n n          Международный научно-технический журнал «Проблемы управления и информатики», 2021, № 6 19 1 1 2 1 ( , , ) ( , , ) , , , , j i i j i i і i M n d M n d M M i N n n                 1 ( , , ) , ) ( , , j N N j N N N M n d M n d M n n           1 1 2 1 1 ) )( , , , , ( , j j M n d M n d М d d          1 1 2 1 ( , , ( ,) ), , , , , j i i j i i і i M n d M n d M M i N d d                 1 ( , , ) , ) ( , , j N N j N N N M n d M n d M d d           (10) яка є також формулою (9), але записана в більш компактному для практичного за- стосування вигляді. Твердження 3. Для обчислення градієнта функції ( , )F n d пришвидшеним ана- літичним способом потрібно 2 2 3 4* ( )N N L  множень характеристичних матриць. Доведення. Підрахуємо кількість операцій для однієї довжини хвилі. Для зна- ходження допоміжних матриць 1 1( ,..., ) i M i N   та 2( ,..., ) i M i N  потрібно всього 2 2( )N  операцій, тобто 2( )N  для кожної. Для реалізації формули (10) потрібно 2 2 2 2 4 1( ( )) ( )N N    множень характеристичних матриць. Тому для обчислення матриць ( , , ) і M n d n    та ( , , ) і M n d d    для всіх 1, ,i N  прискорена реалізація потребує 2 2 2 4 1 2 3 4* ( ( ) ( )) ( )N N N L N L      операцій множення матриць. Твердження доведено. Твердження 4. Пришвидшений варіант аналітичного способу обчислення градієнта функції ( , )F n d виграє у прямолінійної реалізації, і цей виграш буде ха- рактеризуватися величиною 3 1 1 ( ) , ( ) q N N N N    де N — кількість шарів. Доведення. Знайдемо відповідне співвідношення кількостей операцій мно- ження характеристичних матриць: 2 1 2 3 4 3 1 1 3 1 2 1 1 1 * * ( ) ( ) ( ) . ( ) ( ) ( ) N LN N q N N N L N N N N NN            Твердження доведено. 20 ISSN 1028-0979 Аналогічне твердження також можна сформулювати і для обчислення градієн- та функції ( , )F n d скінченно-різницевим методом (див. твердження 1). Для обчислення градієнта функції ( , )F n d пришвидшеним скінченно-різ- ницевим методом кількість операцій множень характеристичних матриць буде 3 2 3 4 1* ( ( ) ( )) .N N N L    Розглянемо перевагу пришвидшеного множення матриць. При 2N  ма- ємо 2 1( ) ,q  а при 3N  маємо 5 3 6 ( ) .q  Однак при 60N  маємо суттєвий виграш: 3 60 4 176 1 60 60 59 3540 20 ( ) .q       Це означає, що при роботі зі шістдесятишаровим оптичним покриттям можна зекономити у двадцять разів на обчисленнях, пов’язаних із множенням матриць. Однак потрібно відзначити, що при розв’язанні оптимізаційної задачі (1)‒(3) ми не отримаємо «чистого» виграшу за часом у ( )q N разів. Річ у тім, що розрахунок характеристичних матриць для кожного шару потребує використання трудоміст- ких щодо обчислення математичних функцій sin ( )x та cos( ),x які можуть пере- вершувати складні операції, пов’язані з множенням матриць. Тому застосуємо прийом, який дозволить зменшити час виконання цих операцій. 3. Табуляція тригонометричних функцій (sin ( cos (x x), )). У роботі зна- чення косинусів та синусів потрібно знаходити від функції 2 λ) λ ( , , . nd n d    Якщо значення min max [ , ],n n n min max [ ],d d d та min max [ , ,]   то діа- пазон значень цієї функції буде max maxmin min max min 22 λ λ , n dn d       . Розділимо його не менше, ніж на 10 7 частин, і протабулюємо значення синусів та косинусів. Переві- римо на різних комп’ютерах, наскільки збільшилась швидкодія при 10 9 операцій множення характеристичних матриць (табл. 1). Для цього була написана програ- ма-автоматизатор, яка виконувала цю дію 100 разів, і визначався середній час. Таблиця 1 № Характеристики комп’ютера Час виконання без табуляції, с Час виконання з використанням табуляції, с 1 Intel(R) Core(TM) i3-3220 3.30 ГГц ОЗУ 8 ГБайт 742,22 7,98 2 AMD Ryzen 3 3250U with Radeon Graphics 2.60 ГГц ОЗУ 8 ГБайт 853,74 10,04 3 Intel(R) Core(TM) i3-3250 3.50 ГГц ОЗУ 4 ГБайт 1008,85 6,94 4 Intel(R) Pentium(R) CPU 2.2 ГГц ОЗУ 4 ГБайт 4253,16 31,74 Международный научно-технический журнал «Проблемы управления и информатики», 2021, № 6 21 З табл. 1 видно, що швидкість виконання суттєво збільшилась. Для ком- п’ютера з процесором AMD Ryzen 3 3250U with Radeon Graphics 2.60 ГГц ОЗУ 8 ГБайт час виконання зменшився приблизно у 85 разів, а для комп’ютера з про- цесором Intel(R) Core(TM) i3-3250 3.50 ГГц ОЗУ 4 ГБайт процес множення харак- теристичних матриць прискорився понад 140 разів. Відзначимо, що під час зміни кількості операцій множення характеристичних матриць час виконання без табу- ляції та з табуляцією збереже вказане співвідношення. Твердження 5. Наявність табуляцій значень тригонометричних функцій при виконанні операцій множення характеристичних матриць у задачі (1)‒(3) зменшує час виконання у десятки разів. 4. Використання методу золотого перерізу при визначенні кроку. Крок * k  в ітераційному процесі визначається із розв’язку задачі ( min) ).( k k k k k k k F x p F x p       Це задача одновимірної оптимізації. Порівняємо ефективність методів одновимірної оптимізації — золотого пе- рерізу та тернарний пошук. Для цього розв’яжемо окрему задачу: знайти розмі- щення точки, від якої відстань до прямих була б якомога меншою. Під відстанню до прямих будемо розуміти відстань до найбільш віддаленої прямої. Прямі задані двома точками. Спочатку задамо структуру, яка буде описувати лінію в програмі struct line { double a, b, c; line (double x1, double y1, double x2, double y2) { double aa = (y2 - y1); double bb= (x1 - x2); double cc = x2 (y1 - y2) + y2 * (x2 - x1); double norm = sqrt(aa * aa + bb * bb); this->a = aa / norm; this->b = bb / norm; this->c = cc / norm; } double get(double x, double y) { return abs(a * x + b * y + c); } }; В описаній структурі вже зразу наведено метод, який повертає відстань від точки до прямої. Як відомо, відстань від точки 0 0 ( , )x y до i-ї прямої 0· · i i i a x b y c   рівна 0 0 0 0 2 2 ) · · ( , , , , i i i i i i i i a x b y c dist x y a b c a b     . Поділивши на 2 2 i i a b значення коефіцієнтів прямої 2 2 ,i i i i a a a b    2 2 ,i i i i b b a b    2 2 ,i i i i c c a b    отримаємо, що відстань 0 0 0 0 ( , , ), , i i i i i i dist x y a b c a x b y c   . 22 ISSN 1028-0979 Структура, яка описує пряму, готова до використання, і швидкість знахо- дження відстані від точки до прямої зростає після уникнення постійного визна- чення кореня квадратного та поділу на нього. Введемо дані та сформуємо всю інформацію про прямі у векторі vector<line> lines: int n; cin >> n; for (int i = 0; i < n; i++) { int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2; line s(x1, y1, x2, y2); lines.push_back(s); } Відстань від точки до прямих знайдемо за допомогою функції: double dist(double x, double y) { double ans = 0.0; for (auto i : lines) { ans = max(ans, i.get(x, y)); } return ans; } З огляду на введені вище позначення, цільова функція має вигляд 1 min ,, ( , ) max ( , ) ., , , i i i xєR yєRi n f x y dist x y a b c    Дослідимо, як буде зображена ця цільова функція в просторі. Типовий вигляд цільової функції зображено на рис. 1. Рис. 1 Якщо записати функцію відстані від точки до прямих при фіксації одного з параметрів x чи y , то можна звернути увагу, що вона унімодальна, тобто непе- рервна і при зміні незафіксованого параметра спочатку спадає, а потім зростає (рис. 2). Тому застосуємо для знаходження мінімального значення цільової функ- ції метод золотого перерізу. Рис. 2 Международный научно-технический журнал «Проблемы управления и информатики», 2021, № 6 23 Зуважимо, що цей метод можна застосовувати по черзі — спочатку до одно- го, а потім — до іншого параметра. Але такий підхід потребує великої кількості ітерацій, поки наблизиться до шуканого розв’язку. Тому використаємо те, що ці- льова функція при кожному фіксованому значенні змінної x унімодальна. Будемо всередині кожного кроку для змінної x знаходити оптимальне значення цільової функції зразу ж і щодо змінної y (рис. 3). Це суттєво пришвидшить пошук розв’язку. Для визначення шуканого значення щодо змінної x щоразу запуска- ється метод золотого перерізу за змінною ,y і досягнуте значення є індикатором вибору значення звуження проміжку за змінною .x Рис. 3 Відповідна реалізація наведена нижче: double Golden_Section_y (double x) { double l = -1e9, r = 1e9; while (r - l > eps) { double ll = l + 0.38 * (r - l); double rr = l + 0.62 * (r - l); if (dist(x, ll) < dist(x, rr)) r = rr; else l = ll; } return l; } double Golden_Section_x () { double l = -1e9, r = 1e9; while (r - l > eps) { double ll = l + 0.38 * (r - l); double rr = l + 0.62 * (r - l); if (dist(ll,Golden_Section_y(ll)) < dist(rr,Golden_Section_y(rr))) r = rr; else l = ll; } return l; } Часова складність алгоритму рівна 2log( · )O n C , де C — параметр, який за- лежить від діапазону пошуку та точності. Квадрат операцій виникає через те, що один метод золотого перерізу використовується в іншому. Порівняємо метод золотого перерізу з іншим — тернарним пошуком. Відзна- чимо, що при заміні коефіцієнтів у методі золотого перерізу 0,38 на 1/3, а 0,62 на 2/3 отримаємо метод тернарного пошуку. У системі Codeforces проведено замір часу знаходження розв’язків для обох цих методів, коли розмірність задачі більша і йтиме від 10000 до 100000 з кроком 10000. Як видно з рис. 4, існує лінійна залежність часу виконання розглядуваних ме- тодів від розмірності задачі. Метод тернарного пошуку потребує приблизно на 40 % більше часових затрат, ніж метод золотого перерізу при знаходженні розв’язку розглядуваної задачі. Також важливим показником є те, що кількість x y y r rr ll l 24 ISSN 1028-0979 ітерацій методу золотого перерізу для визначення шуканого значення змінної x у діапазоні 9 910 10[ , ] становитиме 74, а для методу тернарного пошуку — 87. Графіки залежності часу виконання тернарного пошуку та методу золотого пере- різу від розмірності задачі приведені на рис. 4. Рис. 4 5. Ефективна реалізація множення двох матриць. Для задач, пов’язаних з оптимізацією шаруватих структур в задачах теплопровідності та радіації, потріб- но виконувати множення матриць великої розмірності. Тут може з’явитися ще один пункт пришвидшення роботи методів багатовимірного пошуку, який пов'я- заний з особливістю реалізації операції множення матриць. Розглянемо дві реалі- зації цієї операції. Таблиця 2 Загальновідомий варіант Пришвидшений варіант for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) for (int k = 0; k < n; k++) c[i][j] += a[i][k] * b[k][j]; for (int i = 0; i < n; i++) for (int k = 0; k < n; k++) { long long x = a[i][k]; for (int j = 0; j < n; j++) c[i][j] += x * b[k][j]; } У табл. 2 описано знаходження добутку матриць ,C A B  усі матриці роз- мірностей .n n Проведемо для цих двох реалізацій обчислювальний експери- мент, використавши тестувальну систему ejudge 3.7.9+. Для проведення обчислювального експерименту підготовлено десять тестів для матриць розмірності 1000 ×1000. Час проходження кожного тесту при загальновідо- мій реалізації перевищує 15 с. При пришвидшеній реалізації він суттєво менший, ніж при загальновідомій, і максимально витрачений час рівний 1,388 с. Відзначимо, що час зчитування вхідних даних і виводу відповіді становить приблизно 350 млс. Відпо- відно, якщо у загальновідомому варіанті поміняти другий та третій цикли місцями і зафіксувати у звичайній змінній значення елемента першої матриці, то швидкість ви- конання операції множення для матриць суттєво зросте. Це пришвидшення становить від 2 до 15 разів — залежно від характеристик комп’ютера. При збільшенні розмірно- сті матриць перевага пришвидшеного варіанту зростатиме. Можливі й подальші пок- ращення [12], які можуть дати перевагу ще на 20 %. 9000 0 1000 2000 3000 4000 5000 6000 7000 8000 10000 20000 30000 40000 50000 60000 70000 80000 90000 100000 Метод золотого перерізу Тернарний пошук Ч а с в и к о н а н н я , м с 561 779 1076 1528 1638 2308 2199 3135 2730 3884 3338 4820 4430 6208 3993 5506 5522 7737 4882 6925 Международный научно-технический журнал «Проблемы управления и информатики», 2021, № 6 25 Висновок Для пришвидшення роботи оптимізаційних методів для синтезу багатошаро- вих оптичних покриттів запропоновано використати: пришвидшений спосіб для знаходження узагальненого градієнта цільової функції за допомогою використан- ня префікс- та суфікс-масивів у аналітичному способі обчислення градієнта, табу- ляцію значень тригонометричних функцій, швидке множення матриць та викори- стання ефективного методу при одновимірній оптимізації. Зокрема показано, що при виконанні 10 9 операцій множення характеристичних матриць використання табуляції значень sin ( )x та cos ( )x зменшує час виконання в десятки разів. Сво- єю математичною природою задачі синтезу оптичних шаруватих покриттів близь- кі до цілого ряду задач синтезу в інших областях: електродинаміці, радіофізиці, акустиці, оскільки хвильові процеси в них та їх основні характеристики опису- ються тими ж рівняннями, що і в оптиці. Тому математичні методи і підходи до розв’язання задач синтезу, пов’язаних з оптичними шаруватими покриттями, можна поширити і на задачі синтезу з інших розділів фізики та техніки. О.В. Міца, П.І. Стецюк, О.М. Левчук, В.І. Пецко, І.Ф. Повхан ПРО ПРИШВИДШЕННЯ ОПТИМІЗАЦІЙНИХ МЕТОДІВ ДЛЯ ЗАДАЧІ СИНТЕЗУ БАГАТОШАРОВИХ ОПТИЧНИХ ПОКРИТТІВ Розглянуто п’ять способів для пришвидшення багатовимірного пошуку розв’язку задачі синтезу багатошарових оптичних покриттів за допомогою ме- тодів нульового та першого порядків. Перший спосіб — це використання аналі- тичної похідної для цільової функції якості багатошарового покриття. Він до- зволяє точно (у межах комп’ютерної арифметики) обчислити значення градієн- та гладкої цільової функції та узагальненого градієнта негладкої цільової функції. Перший спосіб потребує таку ж кількість арифметичних операцій, як і скінченно-різницеві способи обчислення градієнта та узагальненого градієнта. Другий спосіб — це використання пришвидшеного знаходження градієнта ці- льової функції за допомогою використання префікс- та суфікс-масивів у аналі- тичному способі обчислення градієнта. Цей прийом дозволяє зменшити кіль- кість арифметичних операцій втричі для задач великої розмірності. Третій спо- сіб — це використання табуляції значень тригонометричних функцій для обчислення характеристичних матриць. Цей прийом зменшує час виконання операцій множення характеристичних матриць у десятки разів в залежності від характеристик комп’ютера. Для деяких архітектур комп’ютера ця перевага ста- новить більше ніж 140 разів. Четвертий спосіб — це використання методу зо- лотого перерізу для одновимірної оптимізації в задачах синтезу оптичних пок- риттів. Зокрема, при розв’язанні однієї часткової задачі показано, що метод тер- нарного пошуку потребує приблизно на 40 % більше часових затрат, ніж метод золотого перерізу. П’ятий спосіб — це використання ефективної реалізації множення двох матриць. Вона полягає у зміні порядку другого і третього цик- лів для загальновідомого методу множення двох матриць та фіксації у звичай- ній змінній значення елемента першої матриці. Це дозволяє суттєво прискорити виконання операції множення двох матриць. Для матриць розмірності 1000×1000 придшвидшення складає від 2 до 15 разів — залежно від характерис- тик комп’ютера. Ключові слова: багатошарові оптичні покриття, спектральні характеристики, синтез оптичних покриттів, аналітична похідна, узагальнений градієнт, метод золотого перерізу. 26 ISSN 1028-0979 O.V. Mitsa, P.I. Stetsyuk, O.M. Levchuk, V.I. Petsko, I.F. Povkhan ON THE ACCELERATION OF OPTIMIZATION METHODS FOR THE PROBLEM OF SYNTHESIS OF MULTILAYER OPTICAL COATINGS Five ways to speed up the multidimensional search in order to solve the problem of synthesis of multilayer optical coatings by using the methods of zero and first orders have been considered. The first way is to use an analytical derivative for the target quality function of the multilayer coating. It allows us to calculate accurately (within the computer arithmetic) the value of the gradient of a smooth objective function and generalized gradient of a non-smooth objective one. The first way requires the same number of arithmetic operations as well as finite-difference methods of calculating the gradient and the generalized gradient. The second way is to use a speedy finding of the objective function gradient using the prefix- and suffix-arrays in the analytical method of calculating the gradient. This technique allows us to reduce the number of arithmetic operations thrice for large-scale problems. The third way is the use of tab- ulating the values of trigonometric functions to calculate the characteristic matrices. This technique reduces the execution time of multiplication operations of characteris- tic matrices ten times depending on the computer’s specifications. For some comput- er architectures, this advantage is more than 140 times. The fourth method is the use of the golden section method for the one-dimensional optimization in the problems of synthesis of optical coatings. In particular, when solving one partial problem it is shown that the ternary search method requires approximately 40% more time than the golden section method. The fifth way is to use the effective implementation of multi- plication of two matrices. It lies in changing the order of the second and third cycles for the well-known method of multiplying two matrices and fixing in a common var- iable value of the element of the first matrix. This allows us to speed up significantly the multiplication operation of two matrices. For matrices having 1000 x 1000 di- mension the acceleration is from 2 to 15 times, depending on the computer's specifi- cations. Keywords: multilayer optical coatings, spectral characteristics, synthesis of optical coatings, an analytical derivative, the generalised gradient, the golden section method. 1. Willey R.R. Practical production of optical thin films. Willey Optical, Consultants: Charlevoix, MI, USA. 2008. 419 p. 2. Macleod H.A. Thin film optical filters. New York : McGraw-Hill. 1986. P. 260–261. 3. Kryuchyn A.A., Petrov V.V., Rubish V.M., Trunov M.L., Lytvyn P.M. and Kostyukevich S.A. Formation of nanoscale structures on chalcogenide films. Phys. Status Solidi B. 2017. DOI: 10.1002/pssb.201700405. 4. Liu Q, Gerling LG, Bernal‐Texca F, Toudert J, Li T, Zhan X, Martorell J. Light harvesting at oblique incidence decoupled from transmission in organic solar cells exhibiting 9.8 % efficiency and 50 % visible light transparency. Advanced Energy Materials. 2020. 10. 1904196. P. 1–9. 5. Dobrowolski J.A., Tikhonravov A.V., Tmbeсkov M.K., Sullivan B.T., Verly P.G. Optimal nor- mal-incidence antirefiection coatings. Appl. Opt., 1996. 35. P. 644–658. 6. Furman, Sh.A., Tikhonravov A.V. Basics of optics of multilayer systems. Edition Frontieres, Gif- sur-Yvette. 1992. 242 p. 7. Міца О.В. Моделювання та оптимізація спектральних коефіцієнтів шаруватих оптичних систем з неоднорідними границями. Рукопис дисертації на здобуття наукового ступеня до- ктора технічних наук. Ін-т кібернетики ім. В.М. Глушкова НАН України. Київ, 2021. 298 с. 8. Сергиенко И.В., Стецюк П.И. О трех научных идеях Н.З. Шора. Кибернетика и системный анализ. 2012. № 1. C. 4–22. 9. Стецюк П.И. Теория и программные реализации r-алгоритмов Шора. Кибернетика и сис- темный анализ. 2017. 53, № 5. С. 43–57. 10. Стецюк П.І., Міца О.В. Про обчислення градієнта у задачі синтезу оптичних покриттів. Те- орія оптимальних рішень. 2005. № 4. С. 127–133. 11. Стецюк П.И., Мица А.В. О задачах оптимизации параметров для многослойных оптиче- ских покрытий. Кибернетика и системный анализ. 2005. № 4. C. 107–115. 12. Ермолаев И. Умножение матриц: эффективная реализация шаг за шагом. [Електронний ре- сурс]. Доступно: https://habr.com/ru/post/359272/. Дата звернення: Лист. 28, 2020. Отримано 28.09.2021

Про пришвидшення оптимізаційних методів для задачі синтезу багатошарових оптичних покриттів

Institution

Similar Items