О поиске дефектов в регулярных 3D-структурах
Рассмотрены оптимизационные задачи для нахождения лучших в Lp-норме параметров регулярных 3D-структур и методы их решения. Показано, что при восстановлении параметров 3D-структур с дефектами метод наименьших модулей более устойчив, чем метод наименьших квадратов. Приведены результаты вычислительных...
Saved in:
| Published in: | Проблемы управления и информатики |
|---|---|
| Date: | 2018 |
| Main Authors: | , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2018
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/180551 |
| 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: | О поиске дефектов в регулярных 3D-структурах / П.И. Стецюк, В.В. Савицкий // Проблемы управления и информатики. — 2018. — № 2. — С. 33-48. — Бібліогр.: 9 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860026852485103616 |
|---|---|
| author | Стецюк, П.И. Савицкий, В.В. |
| author_facet | Стецюк, П.И. Савицкий, В.В. |
| citation_txt | О поиске дефектов в регулярных 3D-структурах / П.И. Стецюк, В.В. Савицкий // Проблемы управления и информатики. — 2018. — № 2. — С. 33-48. — Бібліогр.: 9 назв. — рос. |
| collection | DSpace DC |
| container_title | Проблемы управления и информатики |
| description | Рассмотрены оптимизационные задачи для нахождения лучших в Lp-норме параметров регулярных 3D-структур и методы их решения. Показано, что при восстановлении параметров 3D-структур с дефектами метод наименьших модулей более устойчив, чем метод наименьших квадратов. Приведены результаты вычислительных экспериментов для программных реализаций методов на основе r-алгоритма Шора.
Розглянуто оптимізаційні задачі для знаходження найкращих в Lp-нормі параметрів регулярних 3D-структур і методи їх розв'язання. Показано, що при відновленні параметрів 3D-структур з дефектами метод найменших модулів більш стійкий, ніж метод найменших квадратів. Наведено результати обчислювальних експериментів для програмних реалізацій методів на основі r-алгоритму Шора.
Optimization problems for finding the best in Lp-norm parameters of regular 3D-structures and methods for their solution are considered. It is shown that when restoring the parameters of 3D structures with defects, the least moduli method is more stable than the least squares method. The results of computational experiments for software implementations of methods based on Shor's r-algorithm are reported.
|
| first_indexed | 2025-12-07T16:50:30Z |
| format | Article |
| fulltext |
© П.И. СТЕЦЮК, В.В. САВИЦКИЙ, 2018
Международный научно-технический журнал
«Проблемы управления и информатики», 2018, № 2 33
УДК 519.85
П.И. Стецюк, В.В. Савицкий
О ПОИСКЕ ДЕФЕКТОВ
В РЕГУЛЯРНЫХ 3D-СТРУКТУРАХ
Введение
Регулярные изображения c дефектами (рис. 1, нарушение регулярности в центре)
характерны при неразрушающем контроле качества (НКK) тонкостенных многослой-
ных композиционных материалов с помощью методов лазерной интерферометрии,
таких как метод голографической интерферометрии, метод спекл-интерферометрии и
метод ширографии [1].
а б
Рис. 1
Методы лазерной интерферометрии для НКК предполагают измерение пере-
мещений или деформаций точек поверхности исследуемых объектов, которые
возникают в результате термической или механической нагрузки. При НКК эле-
ментов конструкций, которые имеют периодическую (регулярную) 3D-структуру,
поле измеряемых методами лазерной интерферометрии величин (перемещения,
деформации) должно также иметь периодическую структуру. Если при изготов-
лении или эксплуатации таких элементов конструкций возникают дефекты
(например, отсутствие соединения, наличие трещин, пор, вмятин и т.п.), то в та-
ких местах нарушается регулярность поля измеряемых величин, и область дефек-
та определяется оператором (наблюдателем) как место, в котором это нарушение
очевидно. Требуется автоматизировать процесс определения местоположения де-
фектов в ответственных элементах конструкций, чтобы снизить влияние челове-
ческого фактора при неразрушающем контроле качества с помощью указанных
выше методов. Рассмотрим оптимизационные задачи для регулярных 3D-струк-
тур, которые введены авторами в работе [2] и имеют место при анализе регуляр-
ных изображений с дефектами, и методы их решения на основе метода Ньютона и
алгоритмов негладкой оптимизации.
Материал статьи изложен в таком порядке. В разд. 1 определены регулярная
3D-структура и связанные с ней дефекты. В разд. 2 сформулированы оптимизаци-
онные задачи для нахождения наилучших в pL -норме параметров регулярных
Работа выполнена при поддержке НАН Украины (проект № 0116U004558) и Volkswagen Foundation
(грант № 90 306).
34 ISSN 0572-2691
3D-структур и исследованы их свойства. В разд. 3 описаны методы наименьших
квадратов и наименьших модулей для нахождения параметров регулярных струк-
тур. Показано, что метод наименьших квадратов не способен восстановить их па-
раметры при наличии хотя бы одного дефекта, а метод наименьших модулей
устойчив к нахождению параметров регулярных 3D-структур с одной и несколь-
кими областями с дефектами. В разд. 4 описаны два общих неравенства для сум-
мы квадратов двух наборов чисел, первое из которых неявно использовалось в
разд. 1 при определении базисной регулярной 3D-структуры.
1. Регулярные 3D-структуры, их параметры и дефекты
3D-структурой будем называть тройку },,{ vuA , где A — nm -матрица, та-
кая что nmnj
miij RaA
...,,1
...,,1}{ , mRu и nRv . Параметрами 3D-структуры
},,{ vuA будем называть m -мерный вектор u - и n -мерный вектор ,v их компо-
ненты будут определять значения элементов матрицы nmRA .
Определение 1. 3D-структура },,{ vuA называется регулярной, если матрица
nmRA и векторы mRu и nRv такие, что jiij vua , mi ,,1 ,
nj ,,1 .
Одно из свойств регулярной 3D-структуры определяет следующее утверждение.
Лемма 1. Если },,{ vuA — регулярная 3D-структура, то регулярной будет
и 3D-структура }~,~,{ vuA , где tuu ii ~ , mi ,,1 , tvv jj ~ , nj ,,1 ,
Rt , 0t .
Лемма 1 означает, что для регулярной 3D-структуры параметры u и v опреде-
лены неоднозначно. Так, на рис. 2 приведены три различных набора параметров для
одной и той же 53 -матрицы
32323
10101
21212
A , которая определяет регулярную
3D-структуру. Первой регулярной 3D-структуре },,{ vuA соответствуют пара-
метры 11, vvuu , второй — 22, vvuu , третьей — 33, vvuu . Неод-
нозначные регулярные 3D-структуры имеют следующий вид: (a) ,)1,1,0( T
1 u
.)1,0,1,0,1(,)2,0,1()(;)0,1,0,1,0(,)3,1,2()(;)2,1,2,1,2( T
3
T
3
T
2
T
2
T
1 vuâvuáv
0
– 1
2
1
1 2 1 2
2 1 2 1 2
1 0 1 0 1
3 2 3 2 3
2
1
0
3
– 1 0 – 1 0
2 1 2 1 2
1 0 1 0 1
3 2 3 2 3
1
0
1
2
0 1 0 1
2 1 2 1 2
1 0 1 0 1
3 2 3 2 3
а б в
Рис. 2
Для того чтобы параметры регулярной 3D-структуры были определены одно-
значно, достаточно зафиксировать величину t из тех или иных соображений. Так,
ее значение можно выбрать таким, чтобы выражение
22
nm tevteu было
минимальным. Здесь me и ne — m - и n -мерный векторы, все компоненты кото-
рых равны единице. Это приводит к минимизации одномерной функции
Международный научно-технический журнал
«Проблемы управления и информатики», 2018, № 2 35
2
11
2
1
2
1
22
2=)( tnmtvuvutevteutf j
n
j
i
m
i
j
n
j
i
m
i
nm
. (1)
Она достигает минимального значения *f при *tt , которые определяются
по формулам
nm
uv
t
nm
vu
vutff
i
m
i
j
n
j
j
n
j
i
m
i
j
n
j
i
m
i
11*
2
112
1
2
1
** ,=)( . (2)
С помощью формул (1) и (2) можно однозначно определить параметры регу-
лярной 3D-структуры. Из выражения для *f в (2) следует, что уменьшить сумму
квадратов компонент векторов u и v нельзя, если для них выполнено условие
n
j
j
m
i
i vu
11
. Именно его поставим в основу однозначной (по параметрам) регу-
лярной 3D-структуры.
Определение 2. Регулярную 3D-структуру },,{ ** vuA будем называть базис-
ной, если ее параметры mRu * и nRv * такие, что
*
1
*
1
i
n
i
j
m
j
vu
.
Справедливо следующее утверждение.
Лемма 2. Если },,{ vuA — регулярная 3D-структура, то регулярная 3D-
структура },,{ ** vuA будет базисной, если
.ãäå,;
11*****
nm
uv
tetvvetuu
m
i
i
n
j
j
nm
(3)
Если },,{ ** vuA — базисная регулярная 3D-структура, то 3D-структура
},,{ vuA будет регулярной, если
nm tevvteuu ** , (4)
для произвольного Rt .
Лемма 2 дает нам формулы (3) и (4), которые связывают между собой пара-
метры базисной и обычной регулярных 3D-структур. Так, базисной регулярной
3D-структурой для 53 -матрицы
32323
10101
21212
A является третья регулярная
3D-структура из рис. 2, параметры которой
T
3 )2,0,1( uu и 3vv
T)1,0,1,0,1( . Для нее
5
1
3
1
3
j
j
i
i vu , и, следовательно,
T* )2,0,1(u и
T* )1,0,1,0,1(v . Чтобы от первой и второй регулярных 3D-структур из рис. 2
перейти к третьей, достаточно в формулах (3) использовать 1uu , 1vv ,
1*
1
* tt либо 2uu , 2vv , 1*
2
* tt . С помощью формулы (4) и параметров
36 ISSN 0572-2691
базисной регулярной 3D-структуры для 53 -матрицы A можно построить не
только первую и вторую регулярные 3D-структуры (им в формуле (4) соответ-
ствуют значения 11 tt и 12 tt ), а и ряд других, удовлетворяющих тем или
иным свойствам. Например, при 5,04 tt получаем регулярную 3D-структуру с
параметрами T
4 )5,1;5,0;5,0( uu и T
4 )5,1;0,5;1,0;5,1( vv , т.е. такую, что
последние компоненты векторов u и v одинаковы.
Определение 3. Элементарным дефектом в регулярной 3D-структуре },,{ vuA
будем называть такую пару индексов ji, , mi ,,1 , nj ,,1 , для которых
jiij vua .
Для регулярных 3D-структур с дефектами будем придерживаться таких
названий. Если регулярная 3D-структура имеет один элементарный дефект, то ее
будем называть регулярной с одним дефектом. Если регулярная 3D-структура
имеет k элементарных дефектов ( 1k ), то ее будем называть регулярной с k
дефектами. Примеры регулярных 3D-структур без дефекта (а), с одним
1~
2323 aa (б) и тремя дефектами 1~
1414 aa , 1~
2323 aa , 1~
3232 aa (в)
53 -матрицы ,
~
A приведены на рис. 3, где в «рамки» взяты те элементы матрицы
A
~
с индексами ji, , где имеет место элементарный дефект jiij vua ~ . Это сде-
лано на примере той же 53 -матрицы A , как и на рис. 1.
1
0
1
2
0 1 0 1
2 1 2 1 2
1 0 1 0 1
3 2 3 2 3
1
0
1
2
0 1 0 1
2 1 2 1 2
1 0 2 0 1
3 2 3 2 3
1
0
1
2
0 1 0 1
2 1 2 2
1 0 0 1
3 3 2 3
2
2
3
а б в
Рис. 3
В этой статье достаточно определения 3, но следует отметить, что для ре-
альных задач понятие «дефект» может потребовать более точного определения.
В них для регулярных изображений под «дефектными» понимаются некоторые
множества пар индексов ji, , в которых нарушено «условие jiij vua ». Как
правило, эти множества задают связные области, но в принципе они могут зада-
вать и несвязные области.
2. Задачи для поиска наилучших параметров
Рассмотрим формулировки оптимизационных задач для нахождения
наилучших параметров регулярной 3D-структуры и базисной регулярной 3D-
структуры, где под «наилучшими параметрами» будем понимать такие значения
векторов *x и
*y , что коэффициенты ***
jiij yxa минимально (в том числе в ев-
клидовой и манхеттеновской нормах) отклоняются от коэффициентов некоторой
заданной матрицы .A
Задача 1. Имеется nm -матрица A . Для регулярной 3D-структуры
},,{ *** yxA требуется найти такие векторы mRx * и
nRy *
, чтобы коэф-
фициенты nm -матрицы *A минимально отклонялись от коэффициентов
nm -матрицы A .
Поиск наилучших параметров для регулярной 3D-структуры можно обеспечить
с помощью безусловной задачи минимизации негладкой выпуклой функции: найти
Международный научно-технический журнал
«Проблемы управления и информатики», 2018, № 2 37
p
p
jiij
n
j
m
i
p
RyRx
pppp yxayxfyxff
nm
/1
11,
*** ),(min),( , (5)
где — модуль числа, а скалярная величина p такая, что 21 p . Решение зада-
чи (5) дает регулярную 3D-структуру },,{ ***
pp yxA , а коэффициенты матриц A и *A
будут минимально различаться в так называемой pL -норме, т. е. когда норма вектора
T
1 ),,(= Nzzz определена следующим образом:
p
p
i
N
i
p
zz
/1
1=
||=
, где 1p .
Если 2=p , то коэффициенты матриц A и *A будут минимально отклоняться в
евклидовой норме, если 1=p — то в манхеттеновской норме. Кроме того, можно
рассматривать и другие значения величины 21: pp . Ее выбор определяет тот
или иной метод для восстановления параметров регулярных 3D-структур, напри-
мер метод наименьших квадратов ( 2=p ) и метод наименьших модулей ( 1=p ).
Задача (5) имеет много решений, так как значения параметров регулярной
3D-структуры },,{ ***
pp yxA определены неоднозначно (см. лемму 1). Однозначно
они будут определены тогда, когда регулярная 3D-структура },,{ ***
pp yxA будет
еще и базисной. Для того чтобы найти параметры базисной регулярной 3D-струк-
туры, можно поступить следующим образом: вначале решить задачу (5), а затем
для нахождения *u и *v использовать формулы (3), где *
pxu и *
pyv . Но это
же можно сделать, сформулировав оптимизационную задачу, которая будет рас-
считана на поиск наилучших параметров базисной регулярной 3D-структуры.
Задача 2. Имеется nm -матрица A . Для базисной регулярной 3D-струк-
туры },,{ ****** yxA требуется найти такие векторы mRx ** и nRy ** , чтобы
коэффициенты nm -матрицы **A минимально отклонялись от коэффициентов
nm -матрицы A .
Поиск наилучших параметров для базисной регулярной 3D-структуры
},,{ ****** yxA можно обеспечить, если задачу (5) дополнить единственным
ограничением
0
11
j
n
j
i
m
i
yx , (6)
которое задает условие на параметры базисной 3D-структуры из леммы 2. За-
дача (5)–(6) является задачей выпуклого нелинейного программирования. Ей
будет соответствовать такое же, как и задаче (5), оптимальное значение *
pf , а ее
оптимальное решение **
px и **
py будет определять наилучшие в pL -норме пара-
метры базисной регулярной структуры },,{ ****** yxA . Если 2=p , то для
нахождения параметров базисной регулярной 3D-структуры получим метод
наименьших квадратов, а если 1=p , то — метод наименьших модулей.
Оптимизационные задачи (5) и (5)–(6) можно решать с помощью стандартно-
го программного обеспечения для решения задач нелинейного программирования.
38 ISSN 0572-2691
Однако здесь имеются некоторые особенности, связанные с представлением за-
дач (5) и (5)–(6) в форме задач выпуклого программирования. Так, задачу (5)
можно свести к такой задаче выпуклого программирования: найти
m
i
n
j
p
ij
p
p
RyRxRz
p
pppp
p
p zyxzfyxzff
nmnm
1 1,,
**** )),,((min)),,(()( (7)
при ограничениях
,,,1,,,1, njmiayxz ijjiij (8)
,,,1,,,1, njmiayxz ijjiij (9)
которая при 1p превращается в задачу линейного программирования, а при
2p — в задачу квадратичного программирования. Чтобы задачу (5)–(6) свести
к задаче выпуклого программирования, достаточно к задаче (7)–(9) добавить еще
линейное ограничение (6). Особенностью задач (7)–(9) и (7)–(9), (6) есть то, что
целевая функция (7) определена только для неотрицательных значений перемен-
ных 0ijz , которые удовлетворяют ограничениям (8), (9). Действительно, если
для некоторой пары индексов i и j сложить неравенства (8) и (9), то получим
неравенство 02 ijz , которое равносильно 0ijz . Поэтому при значениях p
таких, что 21 p , для решения задач (7)–(9) и (7)–(9), (6) применимы только те
итерационные методы, которые работают с допустимыми точками для систе-
мы ограничений (8)–(9). Кроме того, даже при сравнительно небольших значе-
ниях m и n задача (7)–(9) будет иметь большое количество переменных
nmnmN и ограничений nmM 2 .
Более перспективным является решение задачи (5) с помощью субградиент-
ных методов для минимизации негладких выпуклых функций [3, 4]. При этом ко-
личество переменных nmN , а субградиент выпуклой функции ),( yxf p вы-
числяется по формуле
m
i
p
jiijjiij
n
j
p
jiijjiij
p
pf
njyxayxa
miyxayxa
yxfyxg
p
1
1
1
1
1
,,,1,)sgn(
,,,1,)sgn(
)),((),(
(10)
которую легко реализовать для матлаб-подобных языков программирования. Этот
путь также подходит и для задачи (5)–(6), так как она сводится к задаче миними-
зации негладкой выпуклой функции: найти
),( *****
pppp yxFF
qn
j
j
m
i
i
pm
i
n
j
p
jiijp
RyRx
yxMyxayxF
nm
11
/1
1 1,
),(min , (11)
где скалярные величины p и q такие, что 2,1 qp , а скалярная величина
0M . Следует отметить, что для решения задачи (5)–(6) можно использовать и
субградиентные методы с проекцией на линейное равенство (6). Так, при приме-
нении r-алгоритмов это приводит к определенному способу установки начальной
матрицы 0B и последующей ее коррекции таким образом, чтобы для каждой точки
итерационного процесса выполнялось равенство (6).
Международный научно-технический журнал
«Проблемы управления и информатики», 2018, № 2 39
Итак, с помощью решения задачи (5) можно находить параметры регулярных
3D-структур, а с помощью решения задачи (5)–(6) восстанавливать параметры
базисных регулярных 3D-структур. Справедливо следующее утверждение.
Теорема 1. Если 3D-структура },,{ vuA регулярная, то в задаче (5) решение
*
px и *
py такое, что 0),( *** ppp yxff , а 3D-структура },,{ **
pp yxA является ре-
гулярной. Если регулярная 3D-структура },,{ ** vuA базисная, то в задаче (5)–(6)
решение **
px и **
py такое, что 0),( ***** ppp yxff , а ***
pxu и ***
pyv .
Если к регулярной 3D-структуре прибавить один или несколько элементар-
ных дефектов, то 0* pf как для задачи (5), так и для задачи (5)–(6). При этом
выбор параметра p существенно влияет на то, сможем ли мы найти параметры
регулярных 3D-структур. Это иллюстрируют вычислительные эксперименты
по восстановлению параметров T* )2,0,1(u и T* )1,0,1,0,1(v для базисной
регулярной 3D-структуры },,{ *** vuA по 53 -матрицам
32323
101101
21212
1 A
и
323123
101101
211212
2
A , которые содержат один и три элементарных дефек-
та (см. рис. 3). Их результаты для десяти значений ]2,1[p отражены в табл. 1,
где приведены значения p (первый столбец), оптимальные значения целевых
функций (столбцы ),( ****
ppp yxf ) и отклонения найденных параметров **
px и **
py
от точных T* )2,0,1(u и T* )1,0,1,0,1(v (столбцы
***
pxu и
***
pyv ).
Здесь с помощью r-алгоритма (программа ralgb5 [5]) решалась оптимизационная
задача (11) при 1M и 1q .
Таблица 1
p
Один дефект (
1AA ) Три дефекта (
2AA )
),( ****
ppp yxf ***
pxu ***
pyv ),( ****
ppp yxf ***
pxu ***
pyv
1,00 1,00000 0,00000 0,00000 3,00000 0,00000 0,00000
1,05 1,00000 0,00000 0,00000 2,84709 0,00000 0,00000
1,06 1,00000 0,00000 0,00001 2,81912 0,00001 0,00001
1,08 0,99999 0,00004 0,00016 2,76550 0,00011 0,00021
1,10 0,99991 0,00021 0,00089 2,71461 0,00063 0,00118
1,20 0,99472 0,00693 0,02762 2,48527 0,01968 0,03653
1,40 0,94620 0,04579 0,13764 2,09220 0,09757 0,18108
1,60 0,87096 0,09568 0,21940 1,79311 0,15558 0,28875
1,80 0,79586 0,14130 0,27027 1,57515 0,19226 0,35681
2,00 0,73030 0,17854 0,30334 1,41421 0,21651 0,40182
Из табл. 1 видно, что при 1p (соответствует методу наименьших модулей)
параметры
T* )2,0,1(u и
T* )1,0,1,0,1(v восстанавливаются точно и при од-
ном и при трех элементарных дефектах. Об этом свидетельствует оптимальные
значения функций, которые для одного и трех дефектов должны равняться
1*
1 AA и 3*
2 AA соответственно. Похожее поведение наблюдается и
40 ISSN 0572-2691
для значений p , которые близки к единице. Но совсем другая картина имеет ме-
сто при 2p (соответствует методу наименьших квадратов) и значениях p , ко-
торые близки к двойке. Здесь говорить о достаточно точном восстановлении па-
раметров не приходится, так как отклонения найденных параметров **
2x и **
2y от
точных значений параметров *u и *v уже достаточно большие как при наличии
одного, так и при наличии трех элементарных дефектов.
3. Методы наименьших квадратов и наименьших модулей
Метод наименьших квадратов (МНК) и метод наименьших модулей (МНМ)
являются важными частными случаями методов решения оптимизационных задач (5)
и (5)–(6). Так, МНК получается, если выбрать 2=p , а МНМ — если выбрать 1=p .
Если методы связаны с решением задачи (5), то они позволяют находить наилучшие
параметры регулярных 3D-структур, а если с решением задачи (5)–(6), то —
наилучшие параметры базисных регулярных 3D-структур. Для обоих методов
справедлива теорема 1, а значит, МНМ и МНК позволяют восстанавливать пара-
метры базисных регулярных 3D-структур. Это можно сделать двумя способами:
первый — найти одно из решений задачи (5) и применить формулу (3) из леммы 2,
второй — найти единственное решение задачи (5)–(6). Для регулярных 3D-структур
с одним или несколькими дефектами поведения МНК и МНМ существенно раз-
личаются. Так, если у МНК нет шансов восстановить параметры регулярных
3D-структур с дефектами, то у МНМ такие шансы очень большие, что подтвер-
ждают результаты вычислительных экспериментов из табл. 1.
Соответствующие методам МНК и МНМ оптимизационные задачи можно
упростить. Так, для МНМ задача выпуклого программирования (7)–(9) переходит
в следующую задачу линейного программирования:
m
i
n
j
ij
RyRxRz
zyxzfyxzff
nmnm
1 1
1
,,
***
1
*
1 ),,(min),,( (12)
при ограничениях (8)–(9) (для регулярных структур), либо (8)–(9), (6) для (базисных
регулярных структур). Для МНМ задача выпуклого программирования (7)–(9)
переходит в задачу квадратического программирования
m
i
n
j
ij
RyRxRz
zyxzfyxzff
nmnm
1 1
22
2
,,
2***
2
2*
2 )),,((min)),,(()( (13)
при ограничениях (8)–(9) (для регулярных структур), либо (8)–(9), (6) для (базис-
ных регулярных структур). Для задач линейного и квадратического программиро-
вания нет никаких трудностей, связанных с областью определения целевой
функции, которые обсуждались для задачи (7)–(9). Кроме того, их легко допол-
нять линейными ограничениями, которые могут задавать дополнительные усло-
вия на искомые параметры регулярных 3D-структур.
Несмотря на то, что указанные задачи могут иметь достаточно большие раз-
меры, для их решения можно успешно применять стандартное программное обес-
печение, используемое для решения задач линейного и квадратического програм-
мирования. Так, задачи линейного программирования с сотнями тысяч перемен-
ных решаются за минуты на современных персональных компьютерах.
Следовательно, нахождение параметров 3D-структур при 500m и 500n
представляется достаточно реалистичным с помощью современных программ для
решения задач линейного программирования. Для задачи квадратического про-
Международный научно-технический журнал
«Проблемы управления и информатики», 2018, № 2 41
граммирования размеры m и n будут несколько меньше. Менее чувствитель-
ными к размерам 3D-структур будут методы МНК и МНМ, которые используют
оптимизационные задачи, полученные непосредственным упрощением задач (5)
и (5)–(6).
МНК для нахождения параметров регулярной 3D-структуры связан с реше-
нием такой задачи: найти
m
i
jiij
n
jRyRx
yxayxfyxff
nm
1
2
1
2
2
,
2**
2
2*
2 )()),((min)),(()( , (14)
а для нахождения параметров базисной регулярной 3D-структуры — с решением
задачи: найти
.)(min)),(()(
2
111
2
1,
2****
2
2*
2
j
m
j
i
n
i
n
i
jiij
m
jRyRx
yxyxayxff
nn
(15)
Задачи (14) и (15) являются задачами минимизации выпуклой квадратичной
функции от nmN переменных, с тем отличием, что первая задача имеет много
решений, а вторая — единственное.
Задачи (14) и (15) отличаются от тех негладких задач, которые непосред-
ственно следуют из формулировок (5) и (5)–(6). В них из 2L -нормы опущена опе-
рация извлечения корня квадратного, и сделано это для того, чтобы иметь дело с
минимизацией квадратичных функций. Кроме того, для задачи (15) штраф за
нарушение равенства (6) выбран равным единице, поскольку в этом случае
нахождение минимума квадратической функции связано с решением «блочно-
диагональной» системы линейных уравнений:
nja
mia
y
x
eemI
eenI
m
i
ij
n
j
ij
T
nnn
T
mmm
,,1,
,,1,
0
0
1
1
**
**
, (16)
где nI — единичная nn -матрица, mI — единичная mm -матрица. Из (16) по-
лучаем аналитическое решение задачи (15):
.,,1,
)(
11
,,,1,
)(
11
1 11
**
1 11
**
nja
mnm
a
m
y
mia
mnn
a
n
x
m
i
ij
n
j
ij
m
i
j
m
i
ij
n
j
ij
n
j
i
(17)
Формулы (17) объясняют, почему МНК не может восстановить регулярную
3D-структуру с одним элементарным дефектом. Действительно, если для какой-то
пары индексов ji, имеем **
jiij vua , где 0 , то из формул (17) следует,
что
***
ii ux для всех ni ,,1 и ***
jj vy для всех mj ,,1 . Кроме того, для
единственного элементарного дефекта **
jiij vua справедливы формулы
.0
)()(
2
,0
)()(
2
222
***
222
***
mnm
n
mnm
mn
vy
mnn
m
mnn
mn
ux
(18)
42 ISSN 0572-2691
Если формулы (18) применить для 1 , 3m и 5n , то получим откло-
нения 0,17854 *** pxu и 0,30334*** pyv из последней строки табл. 1, ко-
торые при 2p получены с помощью r-алгоритма для регулярной 3D-структуры
с одним дефектом: .1*
2323 aa
Задачи (14) и (15) могут служить тестовыми примерами для проверки сходи-
мости алгоритмов минимизации гладких выпуклых функций. Аналитическое ре-
шение (18) в сочетании с формулами леммы 2 позволяет оценить отклонение
найденного решения от точного. При этом если для задачи (15) применимы алго-
ритмы ньютоновского типа, то для задачи (14) они неприменимы, так как матрица
квадратичной формы вырождена, ее ранг равен 1nm и он на единицу меньше,
чем количество переменных nmN . Но задача (14) удобна для градиентных
методов, в том числе и предельных вариантов r-алгоритмов, которые сходятся за
не более чем за N итераций (см. теорему 1 в [6]). Для нее, учитывая, что множе-
ство решений неоднозначно, легче найти одну точку из множества оптимальных
точек, чем найти единственную оптимальную точку в задаче (15). Поэтому алго-
ритмы, решающие обе задачи с подобными затратами для одной и той же точности,
будут более предпочтительными, чем алгоритмы, которые хорошо решают одну
задачу и плохо — другую. Более того, задачу (15) можно усложнить, умножив по-
следний член суммы на некоторый штраф ,0M управление которым позволяет
изменять степень вытянутости квадратичных функций.
В отличие от МНК, оптимизационные задачи для МНМ следуют из (5) и
(5)–(6) без всяких ухищрений. Так, МНМ для нахождения параметров регулярной
3D-структуры используется для решения такой задачи: найти
m
i
jiij
n
jRyRx
yxayxfyxff
nm
1 1
1
,
**
1
*
1 ),(min),( , (19)
а для нахождения параметров базисной регулярной 3D-структуры — для решения
задачи: найти
n
j
j
m
i
i
m
i
jiij
n
jRyRx
yxyxayxff
nm
111 1,
**
1
*
1 min),( . (20)
Задачи (19) и (20) — задачи минимизации выпуклой кусочно-линейной
функции от nmN переменных, где первая имеет много решений, а вторая —
одно. Для решения негладких задач (19) и (20) можно использовать как субгра-
диентные методы минимизации негладких выпуклых функций [3,4], так и специ-
альные итеративные методы, например метод вариационно-взвешенных квадра-
тических приближений [7].
Робастность МНМ для 3D-структур с дефектами подтверждена вычислитель-
ными экспериментами в предыдущем разделе. Это означает, что если 3D-струк-
тура регулярна и к ней добавлены одна или несколько областей с дефектами, то
параметры регулярной 3D-структуры более точно определяются с помощью
МНМ, чем с помощью МНК. Это подтверждается рис. 4, где проиллюстрированы
результаты работы обоих методов для автоматического определения нерегуляр-
ности в 3D-структурах. Это сделано для двух изображений, которые анало-
гичны получаемым методами лазерной интерферометрии (рис. 4, в центре).
Верхнее изображение содержит одну область с дефектами, а нижнее — две
области с дефектами. Первая дефектная область с центром в точке с координа-
тами )74,55(),( ji со значительным отклонением от регулярной структуры лег-
ко идентифицируется оператором неразрушающего контроля качества. Вторая
Международный научно-технический журнал
«Проблемы управления и информатики», 2018, № 2 43
дефектная область с центром в точке с координатами )37,37(),( ji может быть
пропущена оператором из-за низкой контрастности изображений. На рис. 4 (слева
и справа) приведены абсолютные разности между коэффициентами матрицы для
3D-структур с дефектами и коэффициентами матриц регулярных 3D-структур,
найденных с помощью МНК и МНМ. Из рис. 4 видно, что МНМ однозначно
определяет координаты дефектов, в отличие от МНК, который ошибочно выделя-
ет участки вдоль столбцов и строк каждого дефекта.
– 1
1
3
0
100
60
20
100
60
20
20 40 80
0
100
40
20
100
80
60
60
– 1
1
3
0
100
60
20
100
60
20
– 1
1
3
0
100
60
20
100
60
20
20 40 80
0
100
40
20
100
80
60
60
– 1
1
3
0
100
60
20
100
60
20
Рис. 4
На основе Octave-функции ralgb5 [5], одной из современных реализаций
r-алгоритма Шора, разработаны программы на языке Octave для МНМ, где
решается задача (14), и для МНК, где решается задача (19). Для регулярной
3D-структуры, где 600n и 400m , временные и другие затраты обеих про-
грамм приведены в табл. 2. Вычисления проводились на компьютере Pentium
3GHz в системе Windows7/32, используя GNU Octave версии 3.6.4.
Таблица 2
№ п/п
МНК МНМ
itn nfg time Itn nfg time
1 457 700 10,58 411 502 11,76
2 494 785 11,59 413 505 11,79
3 426 647 9,77 412 503 11,77
4 453 702 10,50 412 502 11,77
5 488 764 11,34 410 499 11,69
44 ISSN 0572-2691
В таблице для пяти тестовых примеров jiij vua , где компоненты векто-
ров 400Ru и
600Rv генерировались датчиком случайных чисел в диапазоне
от 0 до 10, приведены: itn — количество итераций, nfg — количество вычислений
значения функции и ее субградиента, time — время выполнения программы в секун-
дах. Из таблицы видно, что для решения задач с помощью МНК и МНМ достаточно
около 10 с, это означает, что разработанные программы можно использовать в
диалоговом режиме для нахождения параметров регулярных изображений.
4. О неравенствах для суммы квадратов двух наборов чисел
В разд. 1 при описании базисных регулярных 3D-структур (определение 2)
неявно использовалось неравенство, которое связано с формулами (1) и (2) для
минимизации одномерной квадратичной функции )(tf . Поскольку это неравен-
ство может представлять и самостоятельный интерес, ниже изложим его в расчете
на самый общий случай.
Теорема 2. Для n чисел naa ...,,1 и m чисел mbb ...,,1 всегда справедливо
неравенство
m
j
m
j
j
n
i
i
j
n
i
i
mn
ba
ba
1
2
112
1
2
, (21)
которое как равенство выполняется, если и только если caa n ...1 и ...1 b
cbm ... , где c — произвольная константа.
Доказательство. Покажем справедливость неравенства
m
j
m
j
j
n
i
i
j
n
i
i
mn
ba
ba
1
2
112
1
2 0 , (22)
которое равносильно неравенству (21). Левую часть неравенства (22) можно запи-
сать следующим образом:
m
j
m
j
j
n
i
i
j
n
i
i
mn
ba
ba
1
2
112
1
2
m
j
m
j
j
n
i
i
m
j
j
n
i
i
j
n
i
i
mn
banm
mn
ba
ba
1
2
2
11
2
112
1
2
2
2
2
1111
11
2 2
mn
ban
mn
ba
aa
m
j
j
n
i
i
m
j
j
n
i
i
n
i
i
n
i
i
m
j
m
j
j
n
i
i
m
j
j
n
i
i
m
j
jj
mn
bam
mn
ba
bb
1
2
2
1111
1
2
)(
2
Международный научно-технический журнал
«Проблемы управления и информатики», 2018, № 2 45
2
11
1
2
11
1
mn
ba
b
mn
ba
a
m
j
j
n
i
i
j
m
j
m
j
j
n
i
i
i
n
i
.
Следовательно, неравенство (22) можно переписать в эквивалентной форме
0
2
11
1
2
11
1
mn
ba
b
mn
ba
a
m
j
j
n
i
i
j
m
j
m
j
j
n
i
i
i
n
i
, (23)
для которой очевидно, что оно будет выполняться для произвольных последова-
тельностей чисел naa ...,,1 и mbb ...,,1 . Более того, из неравенства (23) видно, что
оно превращается в равенство, если
mn
ba
bb
mn
ba
aa
m
j
j
n
i
i
m
m
j
j
n
i
i
n
11
1
11
1 , ,
что возможно, если и только если caa n ...1 и cbb m ...1 , где c —
произвольная константа.
Доказательство теоремы завершено.
Если в теореме 2 взамен последовательности чисел mbb ...,,1 использовать
последовательность чисел mbb ...,,1 , то получим справедливость еще одного
неравенства, которое более простое, чем неравенство (21).
Теорема 3. Для n чисел naa ...,,1 и m чисел mbb ...,,1 всегда справедливо
неравенство
m
j
m
j
j
n
i
i
j
n
i
i
mn
ba
ba
1
2
112
1
2
, (24)
которое как равенство выполняется, если и только если mn bbaa ...... 11 .
Теорему 3 легко доказать по той же схеме, по которой доказана теорема 2.
Из теорем 2 и 3 следует ряд известных неравенств. Так если 1 nm , то по-
лучаем хорошо известные «школьные» неравенства
.
2
)(
è
2
)( 2
22
2
22 ba
ba
ba
ba
Если выбрать mn и одинаковые последовательности чисел, т.е.
nn abab ...,,11 , то из неравенства (24) теоремы 3 получим неравенство
n
aa
aa n
n
2
122
1
)(
, (25)
которое выполняется как равенство, если и только если naa ...1 . Это же не-
равенство можно получить и из теоремы 2, если выбрать mn и 1b
nn aba ...,,1 .
46 ISSN 0572-2691
Задача «Докажите неравенство (25)» включена в [8] (№ 8.10, с. 97). В книге
дано такое решение задачи 8.10: «Неравенство (25) является частным случаем не-
равенства Коши
2
1
2
2
1
2
2
1
n
i
i
n
i
i
n
i
ii baba , (26)
в котором достаточно положить 1...1 nbb ».
Однако более элегантным будет доказательство, которое легко провести по той
же схеме, что и доказательство теоремы 2. Для этого достаточно неравенство (25)
заменить на эквивалентное неравенство
0
)( 2
122
1
n
aa
aa n
n
, (27)
для которого левую часть можно записать следущим образом:
2
2
1
2
122
1
2
122
1
)()(2)(
n
aan
n
aa
aa
n
aa
aa nn
n
n
n
n
aa
aa
n
aa
n
aa
aa n
nn
nn )(
2
)()(
2 12
2
2
11
1
2
1
2
1
2
1
12
2
1 )()()(
n
aa
a
n
aa
a
n
aa n
n
nn
.
Следовательно, неравенство (17) можно переписать в эквивалентной форме
0
)()(
2
1
2
1
1
n
aa
a
n
aa
a n
n
n
, (28)
откуда очевидно, что неравенство (28) выполняется для произвольных n чисел
naa ...,,1 .
Аналогичное доказательство можно провести и для неравенства (16) — нера-
венства Коши–Буняковского–Шварца. Для этого достаточно неравенство (16)
заменить на эквивалентное неравенство
0
2
1
2
2
1
2
1
2
n
i
i
n
i
ii
n
i
i bbaa (29)
в предположении 0
1
2
n
i
ib . Левую часть неравенства (29) можно записать таким
образом:
4
1
2
2
1
2
1
2
2
1
2
11
2
1
2
2
1
2
2
1
2
1
2
2
n
i
i
n
i
ii
n
i
i
n
i
i
n
i
ii
n
i
iin
i
i
n
i
i
n
i
iin
i
i
b
bab
b
baba
a
b
ba
a
Международный научно-технический журнал
«Проблемы управления и информатики», 2018, № 2 47
n
i
i
n
i
i
n
i
ii
i
n
i n
i
i
n
i
iii
n
i
i
n
i
iiii
i b
b
ba
a
b
bab
b
baba
a
1
2
2
1
2
12
1
4
1
2
2
1
2
2
1
2
12
2
.
Следовательно, неравенство (29) можно переписать в эквивалентной форме
0
1
2
2
1
2
12
n
i
i
n
i
i
n
i
ii
i b
b
ba
a , (30)
откуда очевидно, что неравенство (30) будет выполняться для произвольных
n чисел naa ...,,1 и n чисел nbb ...,,1 .
Заключение
В статье рассмотрены регулярные и базисные регулярные 3D-структуры, для них
сформулированы оптимизационные задачи нахождения наилучших в pL -норме
параметров и исследованы методы решения рассмотренных задач. Особое внима-
ние уделено частным случаям методов — методу наименьших квадратов и методу
наименьших модулей. Показано, что при восстановлении параметров 3D-структур
с дефектами метод наименьших модулей более устойчив, чем метод наименьших
квадратов. Приведены результаты вычислительных экспериментов для программ-
ных реализаций методов на основе r-алгоритма, которые позволяют оценить их
временные затраты при нахождении параметров регулярных 3D-структур боль-
ших размеров (400 строк и 600 столбцов).
Регулярные изображения с областями дефектов характерны при неразрушающем
контроле качества тонкостенных многослойных композиционных материалов с
помощью методов лазерной интерферометрии, таких как метод голографической
интерферометрии, метод спекл-интерферометрии и метод ширографии [1]. Опи-
санные в статье методы для поиска дефектных участков позволяют автоматизиро-
вать процесс определения местоположения дефектов в ответственных элементах
конструкций и снизить влияние человеческого фактора при неразрушающем кон-
троле качества. Оптимизационные задачи для изображений с 400 пикселами по
вертикали и 600 по горизонтали можно решать в диалоговом режиме, так как для
этого требуется около 10 с на современных персональных ЭВМ с использованием
GNU Octave версии 3.6.4.
Разработанные Oсtave-программы легко переписать на языки Фортран и Си,
используя библиотеку базовых подпрограмм линейной алгебры BLAS (Basic
Linear Algebra Subprograms) или библиотеку математических прикладных про-
грамм IntelR Math Kernel Library (IntelR MKL), которые оптимизированы под со-
временные вычислительные машины. Это может позволить значительно ускорить
методы для решения больших задач (тысяча и более переменных), например, за
счет использования вычислительных мощностей графического процессора, кото-
рые в разы превышают вычислительные мощности классических процессоров.
Так, существенное ускорение можно получить, используя для расчетов техноло-
гию CUDA на графических ускорителях. Это подтверждает гибридная реализация
r-алгоритма [9], где сокращение времени, которое достигается при решении задач
с 1000 — 8000 переменными, варьируется от 14 до 18 раз.
48 ISSN 0572-2691
Авторы благодарны И.И. Ткачеву и М.И. Шлезингеру за обсуждение за-
дач и ценные советы, Т.А. Бардадым и А.В. Фесюку за помощь при подготовке
рукописи статьи.
П.І. Стецюк, В.В. Савицький
ПРО ПОШУК ДЕФЕКТІВ
В РЕГУЛЯРНИХ 3D-СТРУКТУРАХ
Розглянуто оптимізаційні задачі для знаходження найкращих в
pL -нормі па-
раметрів регулярних 3D-структур і методи їх розв'язання. Показано, що при
відновленні параметрів 3D-структур з дефектами метод найменших модулів
більш стійкий, ніж метод найменших квадратів. Наведено результати обчис-
лювальних експериментів для програмних реалізацій методів на основі
r-алгоритму Шора.
P.I. Stetsyuk, V.V. Savitsky
ON DEFECTS SEARCH
IN REGULAR 3D-STRUCTURES
Optimization problems for finding the best in pL -norm parameters of regular
3D-structures and methods for their solution are considered. It is shown that when
restoring the parameters of 3D structures with defects, the least moduli method is
more stable than the least squares method. The results of computational experiments
for software implementations of methods based on Shor's r-algorithm are reported.
1. Lobanov L.M., Pivtorak V.A., Kyjanets I.V., Savitsky V.V., Tkachuk G.I. Express control of quality
and stressed state of welded structures using method of electron shearography and speckle-
interferometry. — The Paton Welding Journal. — August, 2005. — Р. 35–40.
2. Стецюк П.И., Cавицкий В.В. О робастности метода наименьших модулей для поиска
дефектов в регулярных 3D-структурах // Матеріали Дев’ятнадцятого Міжнародного
науково-практичного семінару «Комбінаторні конфігурації та їх застосування», присвя-
ченого пам’яті д.ф.-м.н., професора А.Я. Петренюка (Кропивницький, 7–8 квітня 2017 ро-
ку). —2017. — C. 127–132.
3. Шор Н.З. Методы минимизации недифференцируемых функций и их приложения. — Ки-
ев: Наук. думка, 1979. — 200 с.
4. Стецюк П.И. Методы эллипсоидов и r-алгоритмы. — Кишинэу : Эврика, 2014. — 488 с.
5. Стецюк П.И. Субградиентные методы ralgb5 и ralgb4 для минимизации овражных выпук-
лых функций // Вычислительные технологии. — 2017. — 22, № 2. — С. 127–149.
6. Стецюк П.И. Теория и программные реализации r-алгоритмов Шора // Кибернетика и си-
стемный анализ. — 2017. — № 5. — С. 43–57.
7. Мудров В.И., Кушко В.Л. Метод наименьших модулей. — М. : Знание, 1971. — 64 c.
8. Прасолов В.В. Задачи по алгебре, арифметике и анализу. — М. : МЦНМО, 2007. — 608 с.
9. Стецюк П.І., Хіміч О.М., Сидорук В.А. Реалізація r-алгоритму на графічних процесорах //
Комп’ютерна математика. — 2016. — № 2. — С. 100–109.
Получено 15.08.2017
https://ru.wikipedia.org/wiki/%D0%9C%D0%BE%D1%81%D0%BA%D0%B2%D0%B0
https://ru.wikipedia.org/wiki/%D0%97%D0%BD%D0%B0%D0%BD%D0%B8%D0%B5_%28%D0%B8%D0%B7%D0%B4%D0%B0%D1%82%D0%B5%D0%BB%D1%8C%D1%81%D1%82%D0%B2%D0%BE,_%D0%9C%D0%BE%D1%81%D0%BA%D0%B2%D0%B0%29
|
| id | nasplib_isofts_kiev_ua-123456789-180551 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0572-2691 |
| language | Russian |
| last_indexed | 2025-12-07T16:50:30Z |
| publishDate | 2018 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Стецюк, П.И. Савицкий, В.В. 2021-10-03T16:15:16Z 2021-10-03T16:15:16Z 2018 О поиске дефектов в регулярных 3D-структурах / П.И. Стецюк, В.В. Савицкий // Проблемы управления и информатики. — 2018. — № 2. — С. 33-48. — Бібліогр.: 9 назв. — рос. 0572-2691 https://nasplib.isofts.kiev.ua/handle/123456789/180551 519.85 Рассмотрены оптимизационные задачи для нахождения лучших в Lp-норме параметров регулярных 3D-структур и методы их решения. Показано, что при восстановлении параметров 3D-структур с дефектами метод наименьших модулей более устойчив, чем метод наименьших квадратов. Приведены результаты вычислительных экспериментов для программных реализаций методов на основе r-алгоритма Шора. Розглянуто оптимізаційні задачі для знаходження найкращих в Lp-нормі параметрів регулярних 3D-структур і методи їх розв'язання. Показано, що при відновленні параметрів 3D-структур з дефектами метод найменших модулів більш стійкий, ніж метод найменших квадратів. Наведено результати обчислювальних експериментів для програмних реалізацій методів на основі r-алгоритму Шора. Optimization problems for finding the best in Lp-norm parameters of regular 3D-structures and methods for their solution are considered. It is shown that when restoring the parameters of 3D structures with defects, the least moduli method is more stable than the least squares method. The results of computational experiments for software implementations of methods based on Shor's r-algorithm are reported. Работа выполнена при поддержке НАН Украины (проект № 0116U004558) и Volkswagen Foundation (грант № 90 306).
 Авторы благодарны И.И. Ткачеву и М.И. Шлезингеру за обсуждение задач и ценные советы, Т.А. Бардадым и А.В. Фесюку за помощь при подготовке рукописи статьи. ru Інститут кібернетики ім. В.М. Глушкова НАН України Проблемы управления и информатики Оптимальное управление и методы оптимизации О поиске дефектов в регулярных 3D-структурах Про пошук дефектів в регулярних 3D-структурах On defects search in regular 3D-structures Article published earlier |
| spellingShingle | О поиске дефектов в регулярных 3D-структурах Стецюк, П.И. Савицкий, В.В. Оптимальное управление и методы оптимизации |
| title | О поиске дефектов в регулярных 3D-структурах |
| title_alt | Про пошук дефектів в регулярних 3D-структурах On defects search in regular 3D-structures |
| title_full | О поиске дефектов в регулярных 3D-структурах |
| title_fullStr | О поиске дефектов в регулярных 3D-структурах |
| title_full_unstemmed | О поиске дефектов в регулярных 3D-структурах |
| title_short | О поиске дефектов в регулярных 3D-структурах |
| title_sort | о поиске дефектов в регулярных 3d-структурах |
| topic | Оптимальное управление и методы оптимизации |
| topic_facet | Оптимальное управление и методы оптимизации |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/180551 |
| work_keys_str_mv | AT stecûkpi opoiskedefektovvregulârnyh3dstrukturah AT savickiivv opoiskedefektovvregulârnyh3dstrukturah AT stecûkpi propošukdefektívvregulârnih3dstrukturah AT savickiivv propošukdefektívvregulârnih3dstrukturah AT stecûkpi ondefectssearchinregular3dstructures AT savickiivv ondefectssearchinregular3dstructures |