Введение в обратные задачи физической диагностики. Модельные расчеты в Матлаб

Министерство образования и науки Российской Федерации 

Уральский федеральный университет 
имени первого Президента России Б. Н. Ельцина 

И. Н. Огородников

Введение в обратные задачи 
физической диагностики.

Модельные расчеты в Матлаб

Учебное пособие 

Рекомендовано методическим советом 
Уральского федерального университета 
для студентов вуза, обучающихся 
по направлениям подготовки магистров 
14.04.02 «Ядерные физика и технологии», 
14.04.04 «Биотехнические системы и технологии» 
и специальности 14.05.04 «Электроника и автоматика 
физических установок»

Екатеринбург 
Издательство Уральского университета
2017 

УДК 517.9:001.891.57(076.5) 
ББК 22.1я73-5+22.3я73 
         О-39 

Рецензенты:
лаборатория математического моделирования в экологии и медицине Института промышленной экологии Уральского отделения Российской академии наук (канд. техн. наук, доц. В. Г. Панов  
и д-р физ.-мат. наук, проф. А. Н. Вараксин);
д-р физ.-мат. наук, гл. науч. сотр. Института физики металлов 
Уральского отделения Российской академии наук В. И. Соколов

Научный редактор — д-р физ.-мат. наук, проф. А. Н. Кислов

О-39
Огородников, И. Н.
Введение в обратные задачи физической диагностики. Модельные расчеты в Матлаб : учеб. пособие / И. Н. Огородников. — Екатеринбург : Изд-во Урал. ун-та, 2017. — 128 с.
ISBN 978-5-7996-2261-9

Учебное пособие направлено на развитие у студентов практических навыков 
создания теоретических и математических моделей и методов расчета современных физических установок, приборов радиационной безопасности и окружающей среды, а также различных приборов биофизического и медицинского назначения.
Пособие предназначено для студентов технических специальностей физико-технологического института всех уровней обучения и соответствует федеральному государственному образовательному стандарту третьего поколения.

Библиогр.: 11 назв. Табл. 10. Рис. 29.
УДК 517.9:001.891.57(076.5) 
ББК 22.1я73-5+22.3я73 

ISBN 978-5-7996-2261-9
© Уральский федеральный 
университет, 2017

Оглавление

Предисловие . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5

1. Оптимизация и теория двойственности
. . . . . . . . . . . .
7
1.1. Двойственность в оптимизации
. . . . . . . . . . . . . .
7
1.2. Основы табличного симплексного метода . . . . . . . . .
12
1.3. Решение прямой и двойственной задач
. . . . . . . . . .
19
1.3.1.
Постановка задачи . . . . . . . . . . . . . . . . . .
19
1.3.2.
Формулировки прямой и двойственной задач . . .
19
1.3.3.
Симплекс-метод решения прямой задачи . . . . .
21
1.3.4.
Оптимальное решение двойственной задачи . . .
26
1.4. Решение задач оптимизации в среде Матлаб . . . . . . .
27
1.4.1.
Функция linprog . . . . . . . . . . . . . . . . . . .
27
1.5. О недостатках симплексного метода . . . . . . . . . . . .
30
1.6. Выполнение численного расчета . . . . . . . . . . . . . .
31
1.7. Упражнения для самоконтроля . . . . . . . . . . . . . . .
32

2. Регуляризация на компактных множествах . . . . . . . . . .
33
2.1. Понятие компактных пространств . . . . . . . . . . . . .
33
2.1.1.
Некорректные задачи на компактах . . . . . . . .
34
2.2. Свойства метода регуляризации на компактных множествах . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
37
2.3. Конечно-разностные аналоги компактных множеств в L2
42
2.4. Основы построения алгоритма регуляризации
. . . . . .
47
2.5. Формулировка модельной задачи . . . . . . . . . . . . . .
52
2.6. Описание программного обеспечения . . . . . . . . . . .
56
2.6.1.
Минимизация методом условного градиента . . .
56
2.6.2.
Выбор оптимальной вершины многогранника
. .
58
2.6.3.
Интерфейс к программе Compact . . . . . . . . .
59
2.6.4.
Вывод результатов тестового расчета . . . . . . .
62
2.7. Выполнение численного расчета в среде Матлаб . . . . .
63

3. Регуляризация по методу обобщенной невязки . . . . . . .
67
3.1. Метод регуляризации А.Н. Тихонова
. . . . . . . . . . .
67
3.2. Регуляризация для уравнения Фредгольма . . . . . . . .
72
3.3. Регуляризация численного дифференцирования
. . . . .
78
3.4. Программное обеспечение расчетов в среде Матлаб . . .
79

3

3.5. Выполнение численного расчета в среде Матлаб . . . . .
88

4. Итеративная регуляризация вариационных неравенств . .
91
4.1. Сведения из теории вариационного исчисления
. . . . .
91
4.2. Элементы теории вариационных неравенств
. . . . . . .
96
4.2.1.
Принцип итеративной регуляризации . . . . . . . 100
4.3. Пример решения простейшей задачи . . . . . . . . . . . . 102
4.4. Выполнение практического расчета в среде Матлаб . . . 110

Список библиографических ссылок . . . . . . . . . . . . . . . . . 112

Алфавитный указатель
. . . . . . . . . . . . . . . . . . . . . . . . . 113

Приложение 1. Упражнения для расчетов в среде Матлаб . . 116

Приложение 2. Вычисление интегралов в среде Матлаб . . . 123

4

Предисловие

Учебное пособие основано на семестровом курсе лекций с условным названием «Специальные главы высшей математики (Введение
в обратные задачи физической диагностики)», который читается в
Уральском федеральном университете для студентов старших курсов
физико-технологического института, специализирующихся в электронике и автоматике физических установок, защите от излучений, радиационной экологии, биомедицинской инженерии, а также в конструировании приборов для применения в области радиационной безопасности человека и окружающей среды. Оно посвящено реализации расчетных методов, изложенных в [1], и может быть полезно для студентов других технических специальностей.
Цель учебного пособия — помочь студентам в овладении практическими навыками применения некоторых инструментов решения обратных задач физической диагностики. Такая формулировка цели предопределила направленность выбора материала для данного пособия,
поэтому при его составлении во главу угла было положено несколько
основополагающих принципов.
Во-первых, в данном пособии не обсуждаются результаты полного
и всестороннего математического исследования обсуждаемых методов
решения обратных задач. В рамках сформулированного принципа все
необходимые теоремы в пособии приведены лишь в качестве справочного материала: их число минимизировано и они приводятся без
доказательства. Однако для каждой теоремы приведена точная ссылка на первоисточник (с указанием страниц), где содержится полное
и всестороннее математическое исследование обсуждаемого вопроса.
Вдумчивый и подготовленный читатель без труда найдет эту информацию в литературе, цитируемой в приведенном библиографическом
списке.
Во-вторых, для демонстрации обсуждаемых методов решения обратных задач и разработки инструментов их практического решения
была выбрана математическая среда универсального назначения, а не
какое-либо специализированное программное обеспечение. Причины
такого выбора определяются учебной направленностью пособия: специализированное программное обеспечение имеет, как правило, ограниченную область применения и, самое главное, является «непрозрачным» с точки зрения алгоритмов и методов, применяемых в нем для
решения поставленных задач. Напротив, универсальная математиче
5

Предисловие

ская среда широкого применения позволяет продемонстрировать все
особенности алгоритмов и методов решения обратных задач.
В настоящее время для профессионального и учебного применения
доступен широкий набор математических сред универсального назначения. Не ставя задачу сравнительного анализа этих сред, отметим
лишь, что из широкого набора доступных математических сред универсального назначения была выбрана Matlab R⃝ — матричная лаборатория фирмы The MathWorksTM (далее для краткости — Матлаб).
В-третьих, данное учебное пособие не направлено на детальное исследование и обсуждение всех аспектов программирования обсуждаемых методов решения обратных задач. В связи с этим, при составлении учебных программ использован лишь минимальный набор средств
программирования. Для понимания особенностей функционирования
большинства приведенных программ (или фрагментов программного
кода) требуется владение лишь базовым уровнем языка программирования Матлаб. Однако учебное пособие не ставит перед собой задачу обучения основам работы (и программирования) в среде Матлаб,
оставляя этот аспект для специализированных учебных курсов и многочисленной литературы.
На страницах учебного пособия приведены и обсуждаются исходные тексты головных программ, применяемых для демонстрации соответствующих методов решения. Для их функционирования используются также многочисленные вспомогательные модули, реализующие
рутинные процедуры. Весь программный код на языке Матлаб создан автором целенаправленно для использования в учебном пособии, однако полный объем программного кода, подготовленного для
достижения поставленной цели, оказался все же достаточно обширным, чтобы его можно было привести в виде исходных текстов на
страницах учебного пособия. Программное обеспечение для демонстрации возможностей обсуждаемых методов может быть бесплатно
выслано по электронной почте по запросу. Запрос можно сделать по
адресу inv_illposed@bk.ru. Общий объем программного обеспечения, сжатого в zip-архив, не превышает 1 MБ. Разархивированные
программы не требуют инсталляции.
Программные модули расположены в архиве по главам. Для каждой главы в архиве имеется файл Contents, в котором перечислены
программы и используемые ими служебные модули. Для головных
модулей, которые нужно запускать в Матлаб, принято соглашение:
их названия начинаются с прописной буквы. Напротив, названия служебных модулей начинаются со строчных букв. Нет никаких лицензионных ограничений на использование и модификацию приведенных
в архиве модулей для решения собственных задач читателя.

6

1. Оптимизация и теория двойственности

1.1. Двойственность в оптимизации

Понятие двойственности в математическом программировании носит фундаментальный характер, оно имеет важное теоретическое и
практическое значение. В рамках этого понятия формулируют две сопряженные задачи: прямая задача (П) — исходная задача линейного
программирования и двойственная задача (Д) — сопряженная задача, которую получают из прямой задачи с помощью установленного
набора правил [2].

1. Основополагающая идея теории двойственности. Для любой исходной задачи (П) можно сформулировать сопряженную задачу (Д).
Между решениями этих задач имеется тесная связь. Количественное
выражение связи представлено рядом соотношений, которые используют при анализе моделей на чувствительность, исследовании свойств
оптимального решения и проверке оптимальности допустимого решения.
О п р е д е л е н и е.
Две экстремальные задачи на нахождение оптимальных решений считаются эквивалентными задачами, если множества их решений совпадают, или обе задачи не имеют решений.

Формулировка прямой задачи в значительной мере определяется
типами ограничений, знаками переменных (неотрицательные или свободные, т. е. без ограничения в знаке) и типом оптимизации (максимизация или минимизация целевой функции). Теорию двойственности часто излагают, рассматривая формулировки двойственных задач в зависимости от особенностей формулировки прямых задач. Для
унификации правил перехода к двойственной задаче выработали стандартную формулировку исходной прямой задачи. В стандартной форме
задача линейного программирования записывается следующим образом: максимизировать или минимизировать целевую функцию z при
заданных ограничениях bi, i = 1, m:

z =

n
j=1
cj xj;

n
j=1
aij xj = bi,
xj ⩾ 0,
j = 1, n.

7

1. Оптимизация и теория двойственности

Список n переменных xj может включать также некоторые дополнительные (фиктивные) переменные. Для записи задачи линейного программирования в стандартной форме необходимо выполнить следующие обязательные условия.
1. Все ограничения задачи записаны в виде ограничений-равенств
с неотрицательной правой частью. Отметим, что если среди ограничений задачи имеются ограничения-неравенства, то путем регулярных
преобразований они могут быть сведены к ограничениям-равенствам.
2. Все переменные задачи считаются неотрицательными.
3. Оптимизация — это задача на экстремум целевой функции, она
определяется как минимизация или максимизация целевой функции.
Для стандартной формулировки исходной задачи линейного программирования используют стандартизованную таблицу симплекс-метода. На основе стандартной формы прямой задачи формулируют двойственную задачу. При этом ограничения и переменные двойственной
задачи получают используя унифицированные правила симметричных структурных преобразований прямой задачи. После вычислений
симплекс-метода получаем решение прямой задачи. Непосредственно
из симплекс-таблицы, соответствующей оптимальному решению прямой задачи, можно автоматически получить решение двойственной
задачи [3, 4].

2. Правила перехода к двойственной задаче. Существуют следующие правила для перехода от прямой задачи к двойственной:
а) ограничения–неравенства в исходной задаче (П) записывают
в стандартном виде со знаками: [⩾] (min-процедура) и [⩽] (maxпроцедура);
б) каждому из m ограничений прямой задачи (П) ставится в соответствие переменная двойственной задачи (Д);
в) каждой из n переменных прямой задачи (П) ставится в соответствие ограничение двойственной задачи (Д);
г) пусть xj – переменная прямой задачи (П), тогда коэффициенты
при xj в ограничениях задачи (П) становятся коэффициентами ограничения задачи (Д), соответствующей этой переменной, а правая часть
формируемого ограничения будет равна коэффициенту при xj в целевой функции;
д) правые части ограничений прямой задачи (П) становятся коэффициентами целевой функции двойственной задачи (Д);
е) если переменная задачи (П) является неотрицательной (xj, ⩾ 0),
то j-е условие системы ограничений задачи (Д) является неравенством
в соответствие п. а;

8

1.1. Двойственность в оптимизации

ж) ограничение j двойственной задачи записывается в виде строгого равенства, если на переменную xj прямой задачи не наложено
условие неотрицательности;
з) если в прямой задаче (П) имеются ограничения равенства, то на
соответствующие переменные двойственной задачи (Д) не накладывается условие неотрицательности.
В графическом виде эти правила представлены в табл. 1.1.

Таблица 1.1
Соответствие прямой и двойственной задач

Переменные
двойственной
задачи

Переменные прямой задачи
Коэффициенты
целевой функции двойственной задачи

x1
x2
· · ·
xj
· · ·
xn

c1
c2
· · ·
cj
· · ·
cn

y1
a11
a12
· · ·
a1j
· · ·
a1n
b1

y2
a21
a22
· · ·
a2j
· · ·
a2n
b2

· · ·
· · ·
· · ·
· · ·
· · ·
· · ·
· · ·
· · ·

ym
am1
am2
· · ·
amj
· · ·
amn
bm

j-ограничение
задачи Д

Далее удобно перейти к матричной форме записи. Для этого введем новые обозначения:
C = [ cj ] – вектор-строка (1 × n) коэффициентов cj;
X = [ xj ] – вектор-столбец (n × 1) переменных xj;
A = [ aij ] – матрица (m × n) ограничений;
B = [ bi ] – вектор-столбец (m×1) свободных членов (правая часть)
для матрицы ограничений;
U = [ ui ] – вектор-строка (1 × m) промежуточных переменных ui.
В таком случае прямую задачу можно записать в матричной форме

max z = C × X,
A × X ⩽ B,
X ⩾ 0.
(1.1)

Формулировка двойственной задачи (Д) вытекает из формулировки
прямой задачи (П): для перехода к двойственной задаче (Д) следует
применить табл. 1.2 и учесть, что вектор-столбец Y (m × 1) переменных задачи (Д) связан с промежуточной переменной U соотношением
Y= UT, табл. 1.2.
Для прямой задачи (1.1) формулировка двойственной задачи (Д)
заключается в минимизации целевой функции w при ограничениях A:

min w = U × B,
U × A ⩾ C,
U ⩾ 0.
(1.2)

9

1. Оптимизация и теория двойственности

Таблица 1.2
Правила перехода к двойственной задаче

Прямая задача
Двойственная задача

Целевая функция (min)
Правая часть ограничений

Правая часть ограничений
Целевая функция (max)

A–матрица ограничений
AT–матрица ограничений

Ограничение bi ⩾ 0, (⩽ 0)
Переменная ui ⩾ 0, (⩽ 0)

Ограничение bi = 0
Переменная ui ̸= 0

Переменная xj ⩾ 0
j-ограничение: "⩽"

Переменная x ><0
j-ограничение: "="

Чтобы получить окончательную формулировку двойственной задачи,
необходимо перейти от промежуточных переменных U к переменным
Y двойственной задачи:

min w = BT × Y,
AT × Y ⩾ CT,
Y ⩾ 0.
(1.3)

Отметим, что если задачу (1.3) принять за прямую задачу, то формулировка задачи, двойственной к ней, совпадет с исходной задачей (1.1).

Рассмотрим пример формулировки двойственной задачи из прямой.

Задача (П): min z = 2 x1 − 3 x2, ограничения заданы системой:

⎧
⎪
⎪
⎪
⎨

⎪
⎪
⎪
⎩

x1 − x2
⩽ 1;

2 x1 + 3 x2 ⩾ 4;

x1 + x2
= 3;
⇒

⎧
⎪
⎪
⎪
⎨

⎪
⎪
⎪
⎩

−x1 + x2
⩾ −1, b1 = −1;

2 x1 + 3 x2 ⩾
4, b2 =
4;

x1 + x2
=
3, b3 =
3;

x1 ⩾ 0;
x2 >< 0.
x1 ⩾ 0;
x2 >< 0.

Очевидно, что переменная x2 не ограничена по знаку, т. е. она может
быть как меньше, так и больше нуля. Сформулируем двойственную
задачу: поскольку число ограничений равно трем, то получим три переменные u1, u2, u3. Целевая функция двойственной задачи (Д) будет
иметь вид:

max w = U × B = u1 b1 + u2 b2 + u3 b3 = −u1 + 4 u2 + 3 u3.

10