Эффективные методы определения энергетического спектра матриц большой размерности в задачах экспериментальной физики

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

Обеспечение возможности работы измерительного оборудования и высокопроизводительных систем обработки информации в реальном масштабе времени достигается за счет применения параллельных вычислительных многопроцессорных систем на базе параллельных матричных процессоров в виде СБИС, встроенных в датчики измерительных устройств и архитектура которых использует структуру методов матричной алгебры. Например, методы решения множества линейных алгебраических задач, матричные методы цифровой фильтрации сигналов определили архитектуру «систолических» матричных процессоров конвейерных вычислений (встречно-поточных процессоров), процессоров «волновой обработки», высокопараллельных процессоров с перестраиваемой конфигурацией.

При решении многих физических задач интегро-дифференциальные уравнения, описывающие математическую модель измерений физического эксперимента (либо физической системы), сводятся к матричным уравнениям, которые необходимо редуцировать с определенной точностью. Данная проблема связана с применением и разработкой методов регуляризации, использующих ортогональные методы приведения больших матриц к компактному виду (почти треугольной, треугольной, трехдиагональной, блочно-диагональной, диагональной), диагонализацией с определением их «энергетического» спектра, либо с их обращением. Например, в оптических обратных задачах, в статистической обработке экспериментальных данных, а также, и при разработке специализированных матричных процессоров на базе СБИС, устойчивость обращения матриц достигается ортогональными преобразованиями, реализующими разложение по сингулярным (собственным) значениям (разложение по энергетическому спектру). Хорошо известна, например, роль трехдиагональных матриц в теории ортогональных многочленов, к которым сводятся современные алгоритмы сплайновых аппроксимаций эмпирических зависимостей, в разностных методах решения задач математической физики, в расчетах энергетического спектра и электронной структуры «цепочных» молекул. Для них необходимы численно устойчивые алгоритмы определения собственных чисел с гарантированной точностью.

Состояние вопроса. Недостаточно развитое состояние в области создания ортогональных методов, которые характеризовались бы широкой универсальностью применения, нечувствительностью к свойству «плохой обусловленности» матриц, побуждает предпринимать попытки эффективно решить эту проблему. По данной проблеме широко известны работы зарубежных и отечественных научных школ под руководством Дж.Х. Уилкинсона, Б. Парлетта, В. В. Воеводина, С. К. Годунова, В. Н. Фадеевой, Д. К. Фадеева, А. Н. Тихонова и многих других авторов. Практически отсутствуют какие-либо эффективные методы декомпозиции задачи на собственные числа.

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

1) методы статистического анализа экспериментальных данных и планирования эксперимента, линейного прогнозирования и моделирования процессов измерений в технике физического эксперимента;

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

3) квантовомеханические расчеты атомных и молекулярных систем, кластерные методы в задачах физики твердого тела;

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

Например, в квантовомеханических расчетах молекулярных систем и кластеров твердого тела практически до 70 — 80% «машинного» времени затрачивается на диагонализацию матриц и для «больших» систем с большим порядком матриц (до десятка тысяч и выше) практически не реально за один непрерывный счет на ЭВМ получить результаты (проблема «метакомпьютинга»). Поэтому в настоящее время актуальным является решение проблемы декомпозиции задачи диагонализации матриц «по частям». То есть задача сводится к разработке такого метода, осуществляющего инвариантное преобразование большой матрицы к блочно-диагональному виду, в результате которого появилась бы возможность каждый матричный блок более низкого порядка диагонализировать «по частям» в рамках «однопроцессорной системы» по очереди, либо параллельно в рамках «многопроцессорной системы».

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

Задачи исследования;

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

2. Разработка быстродействующих методов диагонализации симметричных трехдиагональных и заполненных матриц, обладающих абсолютной сходимостью и гарантированной точностью независимо от свойств «обусловленности» матриц;

3. Создание быстродействующего метода декомпозиции «компактной» формы матриц большой размерности.

4. Разработка методов для решения обратных спектральных задач экспериментального исследования температурного распределения частиц в гетерогенных потоках.

Научная новизна результатов исследований:

Получены «апостериорные» оценки «ошибки смещения», «стандартного отклонения» и максимальной погрешности вычисленных различными методами собственных чисел действительных матриц, использующих инварианты матриц: след (S) и евклидову норму (Е).

Разработан «модифицированный» метод Гивенса, который за счет использования свойств рекуррентности пересчета определенной части элементов матрицы сокращает количество операций умножений в 4/3 раза, а, значит, имеет более высокое быстродействие, чем традиционный алгоритм Гивенса.

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

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

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

Новизна технических решений. Разработан принципиально новый способ определения температуры частиц конденсированной фазы движущихся гетерогенных объектов. Новизна технического решения подтверждена патентом № 2 107 899 на изобретение, зарегистрированным в Госреестре изобретений (РОСПАТЕНТ), Москва, 27.03.1998.

Методы исследования.

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

На всех этапах исследований проводилось сопоставление теоретических выводов и оценок с результатами компьютерного и физического эксперимента.

Практическая ценность работы:

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

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

Разработанные алгоритмы диагонализации симметричных трехдиагональных и заполненных матриц могут быть рекомендованы в различных прикладных задачах на собственные значения для матриц большой размерности (п > 1 ООО).

Разработанные быстродействующие метод «коррекции линейной интерполяции» и метод «коррекции кратного корня» для определения корней «характеристического» уравнения трехдиагональной симметричной матрицы позволяют вычислять собственные числа матриц с высокой точностью и в случае «патологически близких» и кратных корней;

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

Реализация результатов.

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

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

На новый способ определения температуры частиц конденсированной фазы движущихся гетерогенных объектов получен патент РФ № 2 107 899, использующий предлагаемые в работе матричные методы.

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

На защиту выносятся следующие основные научные результаты:

1. Методика «апостериорных» оценок погрешности вычисляемых различными методами собственных значений действительных матриц;

2. Модифицированный метод Гивенса для приведения матрицы общего вида к компактной форме и быстродействующие методы диагонализации симметричных трехдиагональных и заполненных матриц, основанные на устойчивых элементарных вращениях, обладающие абсолютной сходимостью и гарантированной точностью независимо от свойств «обусловленности» матриц;

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

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

Публикации. Основные результаты диссертационной работы опубликованы в 24 печатных работах, получен один патент на изобретение.

Апробация работы. Основные положения и результаты диссертационной работы докладывались и обсуждались на следующих всероссийских и международных конференциях и совещаниях: Всесоюзная научная конференция «Современное состояние теории атомов и молекул», г. Вильнюс, 1979 г., Всесоюзная научная конференция «X Сибирское совещание по спектроскопии», г. Томск, 1981 г., Всесоюзная научная конференция «Планарные дефекты в упорядоченных сплавах и интерметалл идах», г. Барнаул, 1987 г., Всесоюзная научная конференция «Координатно-чувствительные фотоприемники и оптико-электронные устройства на их основе», г. Барнаул, 1989 г., Всесоюзная научная конференция «Оптические сканирующие устройства и измерительные приборы на их основе», г. Барнаул, 1990 г., 10-ое Всесоюзное координационное совещание по квантовой химии, г. Казань, 1991 г., Международная конференция по алгебре памяти А. И. Ширшова, г. Новосибирск, 1991 г., Первая международная конференция «Нанотехнология, наноэлектроника и криоэлектроника», г. Барнаул, 1992 г., Третья международная конференция памяти М. И. Каргаполова, г. Красноярск, 1993 г., Международная конференция «Всесибирские чтения по математике и механике», г. Томск, 1997 г., Международная научно-техническая конференция «Совершенствование быстроходных ДВС», Барнаул, 1999 г., 8-ая международная конференция «Математические методы в электромагнитной теории», г. Харьков, Украина, 2000 г.

Структура и объем работы. Диссертационная работа состоит из введения, 5 глав, заключения, списка литературы и приложения. Работа изложена на 197 страницах машинописного текста, содержит 34 рисунка, 11 таблиц и список литературы из 102 наименований.

ОСНОВНЫЕ ВЫВОДЫ И РЕЗУЛЬТАТЫ.

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

1. Определен класс задач экспериментальной физики, использующих модель измерительного уравнения в матричном виде, проведен анализ погрешностей вычисления собственных значений матриц большой размерности и получены их апостериорные оценки «снизу»: оценка ошибки смещения £с, минимальная оценка стандартного отклонения crmin и максимальная погрешность crmax вычисленных собственных чисел действительных матриц. Эти оценки выглядят так:

1 «% -Е01 смеЩ =(^1 = -а), amin=-j^-, <7max = t ¦ crmin, где S0, E0 -след и евклидова норма исходной матрицыS], E] - след и евклидова норма преобразованной матрицыtкоэффициент Стъюдента.

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

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

4. Разработаны быстродействующие методы определения собственных чисел трехдиагональной симметричной матрицы как корней высокой точности ее «характеристического» уравнения;

5. Созданы быстродействующие алгоритмы «затухающего маятника» метода «диакоптики» спектра собственных чисел больших матриц в трехдиагональной симметричной форме и в форме Хессенберга, реализующего процедуру декомпозиции матрицы «по частям» путем последовательного приведения (разделения) блочно-диагональной формы к диагональной и форме Шура соответственно.

6. Впервые сформулирована физическая постановка задачи редукции температурного распределения разнородно нагретых частиц по их интегральному тепловому спектру и разработан способ ее реализации. Установлено, что она относится к хорошо обусловленным задачам по Тихонову, допускающим процедуру прямого обращения при уровне приведенных ко входу шумов фотоприемника AW < к ¦ AT, где ATразрешающая способность по температуре. При этом спектрофотометр, регистрирующий излучение, должен быть тарирован по эталонным источникам теплового излучения в соответствии с условием ||Лт1ПГтах-ЛтахГтт|< которое связано с законом смещения Вина и определяет вычислительную устойчивость метода.

7. Техническая новизна полученных результатов подтверждена патентом на изобретение нового способа определения температуры частиц конденсированной фазы движущихся гетерогенных объектов и результатами экспериментальных исследований на установках детонационно-газового напыления.