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

На правах рукописи

Иванов Андрей Александрович

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

05.13.17 — Теоретические основы информатики

Автореферат диссертации на соискание учёной степени кандидата физико-математических наук

ОКТ 2014

Самара — 2014

005553745

005553745

Работа выполнена в федеральном государственном бюджетном образовательном учреждении высшего профессионального образования "Самарский государственный аэрокосмический университет имени академика С.П. Королева (национальный исследовательский университет)" (СГАУ) на кафедре прикладной математики.

Научный руководитель: доктор физико-математических наук, профессор

Жданов Александр Иванович

Официальные оппоненты:

Бутов Александр Александрович,

доктор физико-математических наук, профессор, заведующий кафедрой прикладной математики ФГБОУ ВПО "Ульяновский государственный университет"

Сироченко Владимир Прохорович,

кандидат физико-математических наук, доцент, доцент кафедры информатики и вычислительной математики ФГБОУ ВПО "Самарский государственный университет"

Ведущая организация: фГ(жу впо «Поволжский

государственный университет телекоммуникаций и информатики", г. Самара

Защита состоится 25 ноября 2014 г. в 10:00 на заседании диссертационного совета Д 212.215.07, созданного на базе федерального государственного автономного образовательного учреждения высшего образования "Самарский государственный аэрокосмический университет имени академика С.П. Королева (национальный исследовательский университет)"1, по адресу: 443086, г. Самара, Московское шоссе, д. 34.

С диссертацией можно ознакомиться в научно-технической библиотеке СГАУ и на сайте http://www.ssau.ru.

Автореферат разослан__2014 года.

Ученый секретарь диссертационного совета

Д 212.215.07, д.т.н., профессор Белоконов Игорь Витальевич

'Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Самарский государственный аэрокосмический университет имени академика С.П. Королева (национальный исследовательский университет)» переименовано в федеральное государственное автономное образовательное учреждение высшего образования «Самарский государственный аэрокосмический университет имени академика С.П. Королева (национальный исследовательский университет)»

Общая характеристика работы

Актуальность темы. Современный уровень развития постиндустриального общества наиболее точно можно описать как индустрию знаний, в которой наиболее значимую базу составляют наукоемкие технологии, результат применения которых по большей части состоит в производстве гигантских объемов данных, подлежащих последующему анализу. Достаточно рассмотреть проблемы анализа данных в задачах, неразрушающей диагностики как совокупности способов, методов, алгоритмов и средств, предназначенных для изучения характеристик исследуемых объектов по результатам косвенной информации о них. Большинство этих задач приводят к необходимости решения систем линейных алгебраических уравнений (СЛАУ) больших и сверхбольших размерностей по неточным данным.

Например, такие СЛАУ возникают при решении задач реконструктивной компьютерной томографии высокого разрешения. Для интерпретации данных, полученных в результате неразрушающего сканирования некоторого объекта, с 1950 года применяются различные аппаратные и программные реализации итерационного метода, разработанного польским математиком С. Качмажем (S. Kaczmarz) еще в 1937 году. Малая вычислительная сложность одной иге-рации Делает его достаточно привлекательным при решении большого класса практических задач.

Однако последовательность приближений по методу С. Качмажа сходится не к нормальному псевдорешению в случае, если решаемая СЛАУ оказывается несовместной, что может приводить к появлению различных артефактов при интерпретации данных сканирования. Отметим, что любая несовместная СЛАУ может быть приведена к расширенной регупяризованной системе уравнений с использованием метода А.И. Жданова. Этот подход играет важную роль в данной работе.

С увеличением разрешающих способностей сканирующих устройств, объем данных для анализа возрастает на порядки, а влияние возможных артефактов в интерпретации этих данных приобретает критическую значимость.

Построению различных алгоритмов на основе итераций С. Качмажа посвящено существенно значимое количество работ; согласно исследованию польского математика А. Сигелски (A. Cegielski) на начало 2010 года статья С. Качмажа цитируется более чем в четырехстах реферируемых и значимых публикациях ученых из различных областей знаний. В советской и российской научных школах исследования итераций С. Качмажа представлены в литературе такими известными учеными как В.П. Ильин, Г.П. Васильченко, А. А. Светланов и другие. В 2008 году американскими математиками Т. Штромером (Т. Strohmer) и Р. Вершининым (R. Veishynin) была предложена рандомизированная модификация итерационного метода, генерирующая последовательность приближений к решению, которая для совместных и переопределенных СЛАУ сходится с экспоненциальной скоростью.

Множество модификаций метода ортогональных проекций или алгоритма алгебраической реконструкции нашли свое практическое применение в различных областях знаний, связанных с обработкой и интерпретацией больших объемов данных: реконструкция синограмм в медицине, биологии, геологии; при решении задач диагностики плазмы, кристаллографии, дефектоскопии и микроскопии и др.

Однако до настоящего времени продолжаются теоретические исследования сходимости последовательности итераций по методу С. Качмажа с целью ее ускорения, а также разработки регуляризованных модификаций метода для решения классической и обобщенной задачи регуляризации А.Н. Тихонова. В частности, является актуальным построение такой модификации, которая будет обладать гарантированной сходимостью последовательности приближений к ре-гуляризованному решению исследуемой некорректной или плохо обусловленной задачи, вне зависимости от того - является СЛАУ совместной или нет, имеет полный или неполный ранг.

Отдельная проблема использования итерационных методов состоит в выборе правила останова итераций. Решение этой проблемы позволяет ответить на вопрос - какое из приближений в последовательности стоит принять за искомое решение, что особенно актуально в случае плохо обусловленной задачи.

В большинстве частных случаев, различные задачи диагностики могут быть преобразованы к задачам разделения сигналов, когда из аддитивной смеси множества сигналов, которые поступают из источников недоступных для непосредственного измерения, необходимо выделить некоторый отдельный сигнал или его параметры. Например, к таким задачам следует относить различные задачи связи, гидро-и виброакустики, обработки речевых сигналов, изображений и т.д.

Описанные выше задачи по большей своей части являются яркими представителями, так называемых обратных задач, что предполагает возможную вычислительную неустойчивость при их решении.

В связи с вышеизложенным в диссертации были сформулированы объект, предмет, цель и задачи исследования.

Цель работы: создание новых численных итерационных проекционных методов дан отыскания вычислительно устойчивых решений СЛАУ большой размерности; а также создание программного обеспечения, позволяющего повысить точность расчетов в задачах математического моделирования и обработки сигналов.

Объектом исследования являются конечные итерационные последовательности, построенные с использованием итерационных методов и алгоритмов, а также некоторые структуры данных и вспомогательные подпоследовательности возникшие в процессе исследования.

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

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

Для достижения поставленной цели решены следующие задачи:

1. Разработана квазиоптимальная модификация проекционного алгоритма Качмажа, позволяющая на каждой итерации уменьшать ошибку максимально возможным образом.

2. Разработана модификация проекционного алгоритма для решения задачи регуляризации Л .Я. Тихонова.

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

4. Получены условия сходимости регуляризованной формы проекционного алгоритма.

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

6. Разработан критерий останова итерационного алгоритма, обеспечивающий его регуляризирующие свойства.

Научная новизна:

1. Впервые предложена квазиоптимальная модификация классического итерационного метода С. Качмажа (и показана его связь с методом координатного спуска), которая на практике обладает самой быстрой скоростью сходимостью из всех известных модификаций.

2. Впервые предложена регуляризованная модификация классического итерационного метода С. Качмажа, а также специально для нее сконструированы казиоптимальный и рандомизированный аналоги.

3. Впервые предлагается критерий останова итерационного метода наискорейшего спуска для получения регупяризованных решений по методу наименьших квадратов с несмещенным квадратом длины.

Положения, выносимые на защиту:

1. Теорема 1 о геометрической скорости сходимости итерационной последовательности, полученной в результате применения квазиоптимальной модификации алгоритма Качмажа.

2. Теорема 2 о сходимости итерационной последовательности, полученной в результате применения регуляризованной модификации алгоритма Качма-жа.

3. Теоремы 3 и 4 о геометрической скорости сходимости квазиоптимальной и рандомизированной регуляризованных модификаций алгоритма С. Качма-жа.

4. Правило останова (22) итерационного метода наискорейшего спуска для получения регуляризованных решений по методу наименьших квадратов с несмещенным квадратом длины.

5. Разработанный комплекс программ для решения задачи регуляризации А.Н. Тихонова с использованием итерационных проекционных методов.

6. Применение разработанного комплекса программ для решения ряда задач:

• задача компьютерной томографии при параллельном и веерном методах сканирования;

• задача непараметрической идентификации импульсной характеристики линейной искажающей системы;

■ тестовая задача Филлипса;

• тестовая задача восстановления изображений (в одномерном случае).

Теоретическая и практическая значимость. Большая часть результатов диссертации имеет теоретический характер. Разработанные методы и алгоритмы тестируются на модельных задачах, имеющих приближенное отношение к реальности, а также представляющие ее экстремальные случаи. Часть результатов работы нашла практическое применение при разработке терагерцевого спектрометра Фабри-Перо [2,7]. Предлагаемые в работе методы и алгоритмы могут быть использованы при решении широкого класса вычислительных задач, приводящих к необходимости решения плохо обусловленных линейных алгебраических систем. Также имеет практическое значение разработанный комплекс программ [21].

Достоверность полученных результатов обеспечивается корректным применением математических методов доказательств в линейной алгебре и математической статистике, строгостью постановок задач, а также подтверждена результатами вычислительных экспериментов для различных задач.

Апробация работы. Основные результаты работы докладывались на региональных, всероссийских и международных конференциях и конкурсах:

1. С 2006-2012 гг. на секции кафедры прикладной математики студенческой научно-технической конференции СГАУ

2. Семинар по компьютерной оптике и обработке изображений посвященный 70-летию профессора И.Н. Сисакяна и 20-летию института систем обработки изображений РАН, г. Самара, 20-22 июня 2008 г.

3. Международная конференция по вычислительной механике и современным прикладным программным системам (ВМСППС'2009), г. Алушта, 2531 мая 2009 г.

4. Международная конференция «Математика. Компьютер. Образование», г. Дубна, 25-30 января, 2010 г.

5. Международная молодежная научная конференция «Гагаринские чтения», г. Москва, 6-10 апреля, 2010 г.

6. Международная научная конференции «XVIII Туполевские чтения», г. Казань, 26-28 мая 2010 г.

7. Всероссийская конференция с международным участием «Математическое моделирование и краевые задачи», г. Самара, 3-6 июня, 2010 г.

8. Международная конференция с элементами научной школы для молодежи «Перспективные информационные технологии для авиации и космоса», г. Самара, 29.09-01.10, 2010 г.

9. Международная конференция по вычислительной механике и современным прикладным программным системам (ВМСППС'2011), г. Алушта, 2531 мая, 2011 г.

10. Всероссийская конференция с международным участием «Математическое моделирование и краевые задачи», г. Самара, 15-17 сентября, 2011.

11. IX Всероссийский молодежный Самарский конкурс-конференция научных работ по оптике и лазерной физике, г. Самара, 9-13 ноября, 2011 г.

12. I Всероссийский конгресс молодых ученых, НИУ ИТМО, г. Санкт-Петербург, 9-14 апреля, 2012 г.

13. XI Всероссийский молодежный Самарский конкурс-конференция научных работ по оптике и лазерной физике, г. Самара, 6-10 ноября, 2013 г.

14. IRMMW-THz 2013-2013 38th International Conference on Infrared, Millimeter, and Terahertz Waves (ERMMW-THz 2013), Mainz / Germany, 2013 r.

Диссертационная работа была выполнена при поддержке грантов:

1. Грант для молодых исследователей НОЦ SA-014-02 "Математические основы дифракционной оптики и обработки изображений"(2008);

2. Грант РФФИ (№ 10-01-00723-а) "Разработка численно устойчивых алгоритмов регуляризации на основе расширенных нормальных систем"(2010).

Личный вклад. Постановка задач осуществлялась научным руководителем профессором А.И. Ждановым Доказательства теорем и утверждений, разработка тестовых моделей и их программная реализация, анализ полученных результатов и выводы из них выполнены автором самостоятельно.

Публикации. Основные результаты по теме диссертации изложены в 21 печатных изданиях, 6 из которых изданы в журналах, рекомендованных ВАК, 15 — в тезисах докладов.

Объем и структура работы. Диссертация состоит из введения, четырех глав и заключения. Полный объем диссертации — 143 страницы с 15 рисунками и 5 таблицами. Список литературы содержит 118 наименований.

Содержание работы

Во введении обосновывается актуальность исследований, приводятся цель и задачи диссертации, научная новизна, а также практическая и теоретическая значимость проведенных исследований. Там же приводятся результаты апробации и краткое содержание диссертации.

Первая глава посвящена исследованию и разработке нерегуляризованных модификаций итерационных методов, основанных на ортогональных проекциях по С. Качмажу [6]. Рассмотрим наиболее общую2 формулировку алгоритма Качмажа для решения совместной СЛАУ Аи — f

. . ¡¡(к) ~ {Ч](к);ик) , - л ...

щ+1 = ик + \к [|д.^||2--к = 0,1,..., (1)

где А = (01, а,2, ... , amf € Rm™, ие Д», / = (Д, /а, ... , fmf € Rm, Хк -параметр релаксации, a j(k) - сюрьективное отображение

j.-N0->{l,2,...,m}. (2)

Классические методы, основанные на итерациях С. Качмажа, используют так называемое циклическое правило задания j(k), при котором уравнения ре-шамой СЛАУ используются последовательно — от первого уравнения к последнему, а от последнего — к первому, а именно

j (к) = (к mod m) + 1, к = 0,1,... . (3)

Далее, будем называть последовательность, порождаемую таким отображением (2) - проекционной последовательностью. Различные модификации итераций (1) предлагаются за счет различного задания отображения (2). Наиболее известны следующие:

• циклическое правило (3) - ART3;

• симметричное правило - SymART4;

• правило четной перестановки - MLS-ART5;

• рандомизированное правило - RND-ART6, при котором отображение (2) задается с использованием дискретного закона распределения

<4)

Данная фурмулировка удобна тем, что в ней не вводится разделений на макро-и микроитерации.

3 Algebraic Reconstruction Technique - Техника алгебраической реконструкции.

4Symmetry ART - Симметричная техника алгебраической реконструкции.

5Multi Level Scheme of ART - Многоуровневая техника задания проекционной последовательности.

6Randomized ART - Рандомизированная техника задания проекционной последовательности.

где ||-|[F - матричная норма Фробениуса, a i = 1, т.

Каждое из этих отображений порождает свою уникальную последовательность приближений {tifc}^!, причем только для рандомизированного правила (4) известна оценка скорости сходимости, которая зависит от относительного спектрального числа обусловленности матрицы СЛАУ. Далее в работе предлагается классификация различных известных правил задания проекционной последовательности.

В первой главе исследуются известные правила задания отображения (2) и предлагается квазиоптимальная модификация итераций по методу С. Качмажа (QO-AR.T7), в том смысле, что на каждой итерации ошибка решения уменьшается максимально возможным образом. Для этого в работе доказывается следующая теорема [17].

Теорема 1 (О сходимости квазиоптимальной модификации проекционного алгоритма). Для СЛАУ Аи = /, А € Rnxn, и е R\ / € Я", с невырожденной матрицей А, последовательность порождаемая рекуррентной форму-

лой (1), при задании

j (k) = arg там |r{ I ЦогЦ-1 > (5)

t=l,n

где rf - (a»,Ufc) — fi, сходится к uf со скоростью геометрической прогрессии. А именно, существует 0<д<1ме>0, такие, что

||ufc _ || < оД и°° = Hm ик. (6)

к—юо

Так как вычисление всего вектора невязки гк на каждой итерации может представлять определенную вычислительную трудоемкость, то предлагается [17] итерационная формула

гк+1 = гк — fj^A ■ aj(fc) |[aj(fe) ||~2. (7)

Таким образом, вычисление вектора невязки может быть оптимизировано с использованием полученной итеративной формулы и предварительного расчета и хранения матрицы ААТ. В случае условий, связанных с экономией оперативной памяти ЭВМ, и разреженности матрицы А предлагаемая оптимизация может оказаться неэффективной.

Основная задача, для решения которой исторически применялся метод С. Качмажа, является задача реконструктивной компьютерной томографии, постановка которой [11] для плоского модельного случая приводится в первой главе. Для этой задачи описывается вычислительный эксперимент, в котором решаемая СЛАУ является совместной, то есть внесение шума в правую часть системы не производилось. В Таблице 1 приведены результаты вычислительного эксперимента, из которого следует, что последовательность приближений с использованием квазиоптимальной модификации сходится быстрее, чем все известные.

7 Quasi-optimal ART - квазиоп-тмалыгая техника ART.

9

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

Стоит отметить, что невозможно произвести более детальное аналитическое сравнение исследуемых модификаций, так как в общем, для всех методов, кроме предлагаемых ОО-АКГ и КИС-АНТ, неизвестны конструктивные оценки скорости сходимости, которые бы зависели от числа обусловленности матрицы СЛАУ.

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

Вторая глава посвящена разработке регуляризоваиного метода на основе итераций С. Качмажа [5,8-11] для решения классической задачи регуляризации А.Н. Тихонова:

тш{||Аи-/||2 + а||М||2}, (8)

где А € Жтхп, / € Кт, а > 0 - параметр регуляризации, || • || = || • ||г - евклидова векторная норма.

С использованием метода расширенных регуляризованных систем исходная СЛАУ приводится к квадратной неврожденной всегда соместной системе

(а" Л)(»Но) - и

где у ~ и>'лг, ш =' л/а. К системе (9) применяется метод итераций С. Качмажа (1) с использованием (3) - циклического правила задания проекционной последовательности. В результате разработан самостоятельный метод для решения

Таблица 1: К сравнению модификаций алгоритма Качмажа для тестовой задачи компьютерной томографии; (а) - общее время работы алгоритмов до сходимости в секундах, (б) - суммарное количество итераций до сходимости, (в) - среднее время одной итерации, (г) - достигнутая относительная точность.

№ Метод (а) (б) (в) (г)

1 АКТ 107.9 407344 0.00026 0.0099

2 МЬв-АКГ 49.23 186500 0.00026 0.0099

3 ЮГО-АКТ 19.74 69402 0.00028 0.0099

4 (ЗО-АКТ 5.08 8994 0.00056 0.0099

задачи регуляризации для произвольных систем, а именно, с использованием метода математической индукции доказывается Теорема 2 о сходимости. В результате предлагается метод, основанный на итерациях по формулам

о а ( ат \ (а?(*)' ~aRm)ek-i

Ok = h-i-Pk-i[ , Рк-i =—ir-¡¡#г--, к = 1,2,...,

(10)

где во — вектор начальных значений, а А = (ai,..., ап), таким образом, в итерациях участвуют уже не строки матрицы системы, а ее столбцы.

Теорема 2 (О сходимости регуляризованного проекционного алгоритма). Пусть в рекуррентном уравнении (10) вектор во = (rg Uq)t удовлетворяет условию согласования

ro = f-Auo. (11)

Тогда для произвольного начального вектора щ 9f¡ —> в, при к —> оо, где в. = (г? иТ)Т, в U, = (АТА + aIn)-1ATf ur, = f- Аи,.

С использованием следствий из предлагаемой теоремы о сходимости, а также рандомизированного и квазиоптимального правил задания проекционной последовательности разработаны дополнительные две модификации регуляризованного метода:

• рандомизированный регуляризованный метод С. Качмажа [1], для которого

р U (к) = i)= l|o*f + , i = 1,2,..., п, к = 1,2,..., (12) IHIlF+m^2

где - матричная норма Фробениуса, а а2 = и>;

• квазиоптимальный регуляризованный метод С. Качмажа, для которого

\счук-ищ\- (||a¿||2 +W2) 'j, (13)

j (к) = arg max

a=l,n

вде ук = w^Vfc.

Стоит отметить, что в регуляризованной версии оптимальной модификации метода, проблемы трудоемких вычислений для j(k) не возникает, так как и векшр щ и вектор г к известны на каждой итерации как компоненты вектора Ok = (rlulf.

Далее, во второй главе доказывается теорема о скорости сходимости рандомизированного регуляризованного метода, с использованием вспомогательной матрицы Вш — ( Ат j —шЕп ).

Теорема 3 (О сходимости рандомизированного регуляризованного алгоритма). Пусть ип решение задачи (8), а уп = (/ — Аип) и ж* = (г/J ujx) , а х0 = «о)Г " некоторое начальное приближение, компоненты которого удовлетворяют условия согласования г0 — f - Ащ, и для реккурентной формулы

11

(10) значения последовательности(к) определяются на основе закона распределения (12). Тогда последовательность приближений сходится к вектору х*а со средней скоростью такой, что

М [||а* - <||2] < (1 - к (ВшГ2)к ||х0 - <||2, (14)

г^ к(Вш) = \\Bjp ||В+1| и \\BJI = \\А\\2р + п ■ и?, ||В+||2 = ^ (А) + и2, а В+ - псевдообратная матрица Мура-Пенроуза к матрице Ви.

Для квазиоптимальной модификации также доказывается теорема о сходимости.

Теорема 4 (О сходимости квазиоптимального регуляризованного алгоритма). Пусть иа решение задачи (8), а уа = аГ1 (/ — Аиа) и х*а = и^) , а Х() = (уд - некоторое начальное приближение, компоненты которого удовлетворяют условию согласования г0 = / — Ащ, и для реккурентной формулы (10) значения последовательности } (к) определяются с использованием формулы (13). Тогда последовательность приближений сходится к вектору а;* со скоростью геометрической прогрессии. А именно, существует 0 < 5 < 1 и е > 0, такие, что

\\хк-х*а\\<едк,х1= ИтаА (15)

к—Ьоо

Предлагаемые во второй главе три новых метода для решения задачи регуляризации (регупяризованный метод с использованием циклического правила -К-АКГ, рандомизированный регупяризованный метод - Я-ЮМО-АКТ, квазиоптимальный регупяризованный метод Й-СЮ-АКТ) применяются для решения следующих задач:

• модельная задача компьютерной томографии с возмущениями в векторе

правой части [11];

• знаменитое интегральное уравнение Филлипса [1];

• модельная одномерная задача реконструкции изображений [4].

Во второй главе решается задача компьютерной томографии (результаты вычислительного эксперимента приведены в Таблице 2), а последние две - уже в третьей, в рамках исследования регулярных методов для решения интегрального уравнения Фредгольма первого рода.

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

Третья глава посвящена итерационным регулярным алгоритмам численного решения интегрального уравнения Фредгольма первого рода. В начале главы приводятся общие сведения из теории регуляризации А.Н. Тихонова, необходимые для дальнейшего целостного изложения. Продемонстрировано, что задача отыскания нормального псевдорешения СЛАУ с шумом только в правой части

системы всевда является корректной, однако в случае большого числа обусловленности на практике этот результат оказывается неконструктивным, так как возникающая погрешность в решении хоть и ограничена сверху, но оказывается крайне велика — наблюдается вычислительная неустойчивость задачи к малому шуму в правой части.

Отдельной проблемой представляется решение задачи выбора оптимального значения параметра регуляризации а. Для решения модельных задач в диссертации используется известный результат предложенный А.Н. Тихоновым, в основе которого лежит принцип невязки

а < Sa™* (А)

+ 6

/|| < - (16)

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

^■¿¿ИМГ-Мел, <17>

¿=1 г—1

где I - количество известных реализаций вектора правой части [2,7-9].

Далее, рассматривается [1] задача решения интегрального уравнения Фил-липса

/■3

с правой частью

J s К (х — X) f (х) dx = g(\),K(z) = {1 + C°S *г' И J | (18)

гыо

ш _ Г (6 + А) (1 - icos f) - £sinf, |A| < 6,

0, |A| > 6. иУ)

Таблица 2: К сравнению модификаций алгоритма Качмажа для тестовой задачи компьютерной томографии с шумом; (а) - общее время работы алгоритмов до сходимости в секундах, (Ь) - суммарное количество итераций до сходимости, (с) - среднее время одной итерации, (d) - достигнутая относительная точность.

№ Метод (а) (б) (в) (г)

1 R-ART 4.057 21840 0.00018 0.00997

2 R-RND-ART 4.755 22866 0.00021 0.00999

3 R-QO-ART 2.847 4777 0.00060 0.00999

Точное решение данной задачи / (х) = К (х). Для сведения задачи решения интегрального уравнения к задаче решения системы линейных уравнений

Аи = /, А € / 6 Яп, и 6 Л", п = 512, (20)

использовался метод Бубнова-Галеркина с ортонормированным базисом из прямоугольных функций [21]. Спектральное относительное число обусловленности такой матрицы оказывается крайне велико - к (А) и 1.8 • 10®, а численное решение - неустойчивым к возмущениям в векторе правых частей. Далее задача решается с использованием предлагаемых итерационных регуляризованных методов, эти результаты приведены в Таблице 3.

Таблица 3: К решению задачи Филлипса. Данные об ошибках решений, полученных предлагаемыми регулярными методами; (а) - количество итераций до сходимости.

№ Метод 11«,-йа || Айа~/ 1М 11«,-«»II II«- II (а)

1 И-АЛТ 0.16747805 0.409491738 2.919671212 0.055826484 764928

2 к-юго-дет 0.16747804 0.409491735 2.919671213 0.055826481 23552

3 Я-ОО-АКГ 0.16747804 0.409491735 2.919671213 0.055826481 5120

Таким образом, продемонстрирована возможность применения разработанных регуляризованных методов для решения задач различного класса, не ограниченного задачами томографии. С этой же целью решается задача, которая является одномерной моделью задачи реконструкции изображений, и получаются аналогичные по качеству результаты. На практике данные алгоритмы применялись для решения задачи восстановления спектра терагерцевого излучения по результатам измерений, полученных с использованием интерференционного спектрометра Фабри-Перо [2,7].

Четвертая глава посвящена задаче непараметрического оценивания двумерных импульсных характеристик линейных искажающих систем [4]. Решение задачи идентификации модели искажающей системы часто необходимо при проведении научных исследований и технических испытаний различных устройств. Как правило, идентификация системы используется для оценки качества работы оборудования с целью обнаружения неполадок и при их наличии - коррекции выходных данных. При невозможности устранения неполадки на аппаратном уровне, например, в устройствах дистанционного зондирования Земли, часто прибегают к созданию цифровых корректирующих систем, позволяющих устранить последствия работы неисправной техники на уровне выходных данных. Из-за погрешностей наблюдения за реакцией системы, больших объемов статистических данных, задача идентификации почти всегда плохо обусловлена.

Для систем, допускающих линейное приближение, ставится задача решения стохастической СЛАУ. В предлагаемой работе исследуется способ получе-

14

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

Далее приводится постановка задачи идентификации [20] с использованием матрицы, обладающей двухуровневой теплицевой структурой; предлагается способ эффективной индексации двумерного сигнала [16], с использованием которого решение линейный системы возможно без формирования соответствующей матрицы в памяти ЭВМ.

Задача идентификации рассматривается с позиции метода обобщенной регуляризации А.Н. Тихонова, когда решение СЛАУ находится из условия

В том случае, когда матрица Ь симметричная и положительно определена, принято использовать метод В.В. Воеводина, суть которого состоит в приведении системы нормальных регуляризованных уравнений к каноническому виду с использованием разложения Холецкого. В качестве матрицы Ь предлагается выбирать дискретный двумерный аналог оператора дифференцирования [4].

Далее на основании обобщенного статистического принципа невязки для известного метода наискорейшего спуска предлагается специальное правило останова [4,12,15,18,19]

II "II2 п

Ц-^^ор! ~ /|| > Ятт +7,7= т _ п<3тгп, (22)

где, при решении переопределенных систем т, > п, а (¿тт - мера несовместности системы, определяемая как <2„и„ — д (а, = т£„<=д» ||Ли — /|| . Затем предлагаемое правило останова сравнивается с известным итерационным аналогом метода перекрестной значимости. Приводятся аргументы к использованию предлагаемого подхода ввиду его сравнительно малой вычислительной трудоемкости.

В этой же главе рассматривается задача регуляризации для случая когда матрица ЬТЬ из (21) имеет неполный ранг. В этом случае не существует простых способов решения обобщенной задачи регуляризации. На основании метода регуляризованных расширенных систем предложен вычислительно устойчивый и эффективный метод решения таких задач [2,7].

В заключении приведены основные результаты работы:

1. Разработана квазиоптимальная модификация проекционного алгоритма Качмажа, позволяющая на каждой итерации уменьшать ошибку максимально возможным образом.

2. Разработана модификация проекционного алгоритма для решения задачи регуляризации А.Н. Тихонова.

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

4. Получены условия сходимости регуляризованной формы проекционного алгоритма.

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

6. Разработан критерий останова итерационного алгоритма, обеспечивающий его регуляризирующие свойства.

7. При специальном выборе параметра регуляризации решена проблема применения проекционного метода к решению несовместных СЛАУ.

8. В целях тестирования разработанных алгоритмов и методов разработаны математические модели и соответствующие тестовые задачи:

• задача компьютерной томографии при параллельном и веерном методах сканирования,

• задача непараметрической идентификации импульсной характеристики линейной искажающей системы,

• тестовая задача Филлипса,

• тестовая задача восстановления изображений (в одномерном случае).

Важное место в работе занимает вычислительный эксперимент и статистические методы обработки его результатов, все предложенные методы сравниваются между собой на примере различных вычислительных задач.

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

Публикации автора по теме диссертации в журналах, рекомендованных ВАК

1. Ivanov, A.A. Kaczmarz algorithm for Tifchonov regularization problem [Текст] /

A.A. Ivanov, A.I. Zhdanov H Applied Mathematics E-Notes/ — 2013. — Vol. 13.

- P. 270-276.

2. Kaveev, A.K. Terahertz polarization conversion with quartz waveplate sets [Текст]

/ A.K. Kaveev, A.A. Ivanov, A.I. Zhdanov and others // Applied Optics. — 2013.

- Vol. 52, Issue 1. - P. B60-B69.

3. Myasnikov, V.V. Computer Program for Automatic Estimation of Digital Image Quality [Текст] / V.V. Myasnikov, A.A. Ivanov, M.V. Gashnikov, E.V. Myasnikov // Pattern Recognition and Image Analysis. — 2011. — Vol. 21, No. 3. — P. 415-418.

4. Жданов, А.И. Оценка оптимального номера останова итераций при восстановлении импульсной характеристики искажающей системы [Текст] / А.И. Жданов, A.A. Иванов И Компьютерная оптика. — Т. 34, N3. — С. 367-373.

5. Жданов, А.И. Проекционный регуляризирующий алгоритм для решения некорректных линейных алгебраических систем большой размерности [Текст] / АЛ. Жданов, A.A. Иванов // Вестник Самарского государственного технического университета. Серия "Физико-математические науки". — 2010. - Вып. 5(21). - С. 309-312.

6. Иванов, А. А. Решение задачи полиномиальной аппроксимации с использованием итерационного метода Качмажа [Текст] / A.A. Иванов И Вестник Самарского государственного аэрошсмичесшго университета имени академика С.П. Королева. - 2008. - №2(15). - С. 179-182.

Публикации автора по теме диссертации в материалах конференций

7. Tzibizov, I.A. Novel conception of the terahertz-range spectrometer based on Fabry-Perot interferometer [Текст] / I.A. Tzibizov, A.I. Zhdanov, A.A. Ivanov and others // Infrared, Millimeter, and Terahertz Waves (ERMMW-THz) 38th International Conference on. — 2013. — P. 1.

8. Иванов, A.A. Метод расширенных регуляризованных систем для решения некорректных задач прикладной оптики [Текст] / A.A. Иванов И XI Всероссийский молодежный Самарский конкурс-конференция научных работ по оптике и лазерной физике: сборник конкурсных докладов (Самара, 6—10 ноября 2013 г.). — Москва: ФГБУН Физический институт им. П. Н. Лебедева РАН, 2013. - 351с.

9. Иванов, A.A. Об одном алгоритме решения линейных алгебраических систем неполного ранга с множеством правых частей [Текст] / A.A. Иванов // Сборник тезисов докладов конгресса молодых ученых, Выпуск 2. Труды молодых ученых / Главный редактор д.т.н., проф. В.О. Никифоров. — СПб : НИУ ИТМО, 2012. - С. 253.

10. Иванов, A.A. Метод расширенных нормальных уравнений и регуляризирующий алгоритм Гаусса-Зейделя [Текст] / A.A. Иванов, А.И. Жданов // Материалы XVII Международной конференции по вычислительной механике и

современным прикладным программным системам (ВМСППС'2011), 25-31 мая 2011г., Алушта. - М.: Изд-во МАИ-ПРИНТ, 2011. - С. 241-243.

11. Иванов, A.A. Регуляризованный алгоритм Качмажа в задачах компьютерной томографии [Текст] / A.A. Иванов И Материалы 18 международной конференции "Математика. Компьютер. Образование". — Дубна, 2011. — С. 169.

12. Сидоров, П.С. Восстанавливающий фильтр на основе алгоритма наискорейшего спуска [Текст] / П.С. Сидоров, A.A. Иванов // XVIII Туполевские чтения: Международная молодежная научная-конференция, материалы конференции. Том IV. — Казань : Изд-во Казан, гос. текх. ун-та, 2010. — С. 196198.

13. Myasnikov, V.V. Software System for Identification of Optoelectronic Digital Imaging system and Estimation of Their Quality [Текст] / V.V. Myasnikov, A.A. Ivanov, M.V. Gashnikov, E.V. Myasnikov // 10th International Conference on Pattern Recognition and Image Analysis: New Information Technologies (PRIA-10-2010), St. Petersburg, Conference Proceedings, - SPb.: Politechnika, 2010. — Vol. П.-P. 109-113.

14. Иванов, A.A. Метод L-кривой для итерационных алгоритмов решения плохо обусловленных задач [Текст] I A.A. Иванов // Перспективные информационные технологии для авиации и космоса: Труды международной конференции с элементами научной школы для молодежи. - Самара : СГАУ, 2010. — С. 628-632.

15. Иванов, A.A. Сверточный аналог алгоритма наискорейшего спуска [Текст] / A.A. Иванов // 60-я студенческая научная конференция: тезисы докладов. -Самара: Изд-во Самар. гос. аэрокосм, ун-та, 2010. — С. 66-68.

16. Сидоров, П.С. Эффективная индексация двухуровневых теплицевых матриц [Текст] / П.С. Сидоров, A.A. Иванов // 60-я студенческая научная конференция: тезисы докладов. — Самара: Изд-во Самар. гос. аэрокосм, ун-та, 2010.

- С. 68-70.

17. Иванов, A.A. Об одной модификации итерационного алгоритма Качмажа [Текст] / A.A. Иванов, А.И. Жданов // Математическое моделирование и краевые задачи: Труды седьмой Всероссийской научной конференции с международным участием. 4.4: Моделирование и оптимизация динамических систем и систем с распределенными параметрами. — Самара : СамГТУ, 2010.

- С. 75-77.

18. Иванов, A.A. Об одном критерии останова итерационных алгоритмов решения плохо обусловленных задач [Текст] / A.A. Иванов, А.И. Жданов //

Математическое моделирование и краевые задачи: Труды седьмой Всероссийской научной конференции с международным участием. 4.4: Моделирование и оптимизация динамических систем и систем с распределенными параметрами. — Самара: СамГТУ, 2010. - С. 78-81.

19. Иванов, A.A. Итерационный метод решения задачи деконволюции [Текст] / A.A. Иванов. II XXXVI Гагаринские чтения. Научные труды Международной молодежной научной конференции в 8 томах, г. Москва, 6-10 апреля. — 2010. -С. 91-92.

20. Жданов А.И., Иванов A.A. Восстановление импульсной характеристики искажающей системы [Текст] / Жданов А.И., Иванов A.A. // Материалы 17 международной конференции "Математика. Компьютер. Образование г. Дубна, 25-30 января. - 2010. - С. 115.

21. Ivanov, A.A. Regularization Kaczmarz Tools Version 1.0 for Matlab, Matlabcentral Fileexchange [Электронный ресурс] / Режим доступа: http://www.mathworks.com/matlabcentral/fileexchange/43791.

Подписано в печать: 12.09.2014

Заказ № 10267 Тираж - 100 экз. Печать трафаретная. Объем: 1 усл.п.л. Типография «11-й ФОРМАТ» ИНН 7726330900 115230, Москва, Варшавское ш., 36 (499) 788-78-56 www.autoreferat.ru