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

лл/лЛАтг^ий ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

ЧУГУНОВ ВАДИМ НИКОЛАЕВИЧ

РАСШИРЕНИЕ ЛИНЕЙНО-АЛГЕБРАИЧЕСКИХ

ВОЗМОЖНОСТЕЙ СИСТЕМ КОМПЬЮТЕРНОЙ АЛГЕБРЫ

им. М.В.ЛОМОНОСОВА

'тельной математики и кибернетики

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

удк 519.01

05.13.11 математическое и программное обеспечение вычислительных машин, комплексов, систем и сетей

Москва 1998

Работа выполнена на кафедре Общей Математики факультета ВМиК МГУ

Научный руководитель:

доктор физико-математических наук

профессор Х.Д. Икрамов

Официальные оппоненты: доктор физико-математических наук

профессор С.А. Абрамов

кандидат физико-математических наук

доцент М.С. Сагитов

Ведущая организация:

Институт Вычислительной Математики РАН

Защита состоится ^й^ИКЛт.ЦХ. 1998 г. в 11 часов в ауд. 685 на заседании диссег тационного совета Д 053.05.38 при факультете ВМиК МГУ по адресу 119899, Москв; Воробьевы горы, МГУ, факультет Вычислительной Математики и Кибернетики.

С диссертацией можно ознакомиться в библиотеке факультета ВМиК МГУ.

Автореферат разослан (? ноября 1998 г.

Ученый секретарь диссертационного совета Д.053.05.38 кандидат физико-математических наук

профессор Н.П. Трифонов

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность работы -

Линейно-алгебраические разделы систем компьютерной алгебры раз-гоаютея в настоящее время путем включения в них стандартных патов по вычислительной линейной алгебре. Такие пакеты, ориептиро-,нные на работу в арифметике с плавающей точкой, являются весьма >фективным средством научных и инженерных расчетов. Вместе с тем же развитые и популярные компьютерно-алгебраические системы не-статочно учитывают интересы двух других категорий пользователей: [Ц, изучающих основной курс линейной алгебры или более сложные ее .зделы, с одной стороны, и алгебраистов-теоретиков, с другой. По раз-1М причинам, и тем, и другим пользователям целесообразно абстра-роваться от того факта, что в практических приложениях линейной гебры, как правило, приходится иметь дело с приближенными вычи-ониямп. Иными словами, процедуры, используемые при обучении или оретической работе, должны давать точуиле ответы для решаемых ими пач. Именно такого сорта процедур не хватает в современных системах мпьютерной алгебры. Подобное положение вещей послужило стимулом для выполнения дан-й работы. Ее целью было создание комплекса компыотерно-алгебра-егких процедур, позволяющих точно решать задачи из важного раз-па линейной алгебры, называемого обратными задачами на собствен-:е значения.

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

1

для указанного класса С матриц размера я X п и заданного набора чисе Л = {А1,...,АП} найти матрицу А £ С, спектр а (А) которой совпадав с А. Вместо набора А может быть задан многочлен /(А) степени п с старшим коэффициентом 1 (иначе говоря, нормированный многочлен), тогда задача состоит в отыскании матрицы А £ С с характеристически многочленом /(А).

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

Цель работы

В настоящей работе автор ставил перед собой следующие задачи:

1. Осмыслить и систематизировать имеющийся огромный теорет: ческий материал по ОМЗ с точки зрения возможности (или невозмо> ности) решать конкретные задачи посредством конечных рациональнь алгоритмов.

2. Найти эффективные алгоритмы для ОМЗ, допускающих ради нальное решение.

3. Реализовать эти алгоритмы в виде процедур известной компы терно-алгебраической системы МАРЬЕ.

Научная новизна работы

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

С другой стороны, указана возможность осмысленного расширения инсйно-алгебраичсских разделов современных систем компьютерной ал-збры за счет включения в них функций, дающих точные решения со-гветствующих задач. Для конкретного раздела линейной алгебры (а менно, теории обратных матричных задач на собственные значения) конкретной компьютерно-алгебраической системы (а именно, системы ГАРТ.ТС) эта возможность реализована в виде комплекса процедур, ре-гающих девять содержательных и нетривиальных ОМЗ.

Защищаемые положения

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

1. Алгоритмы и МАРЬЕ-процедуры для задач Мирского и Фарахата-едерманна (постановка этих и других упоминаемых и данном разделе щач разъясняется в приводимом ниже обзоре содержания диссертации).

2. Алгоритмы и МАРЬЕ-процедуры для трех задач дополнения об-[его типа.

3. Алгоритмы и МАРЬЕ-процедуры для трех задач дополнения блоч-л о типа.

4. Алгоритмы и МАРЬЕ-процедуры для задачи Сильвы.

Практическая значимость работы

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

Апробация работы

Основные результаты диссертации докладывались на семинарах "А1 томатизация программирования" (научн. рук. проф. М.Р. Шура-Бур; факультет ВМиК, МГУ), "Компьютерная алгебра" (научн. рук. про с С.А. Абрамов, ВЦ РАН) и "Матричные методы и вычисления" (науи рук. проф. Е.Е. Тыртышников, Институт вычислительной математик] РАН).

Публикации

Основные результаты диссертации отражены в публикациях (1-7].

Структура и объем работы

Диссертация состоит из введения, четырех глав основного текста и з; ключения. Объем диссертации — 94 страницы. Библиография включас в себя 40 наименований. Диссертация содержит 9 приложений.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

Во введении описываются цени данной работы и обосновывается ее стуадьность. Приведен краткий обзор содержания диссертации.

Диссертация посвящепа обратным матричным задачам на собственно значения, в которых требуется построить матрицу из заданного lacea С с предписанным спектром или характеристическим многочле-ш. Класс С в работе определяется условиями:

Вес bij = rv.j, V (г,i) <Е >С,

te /С — некоторое фиксированное множество пар индексов, ntj — задан-ае числа из рассматриваемого поля К. Эта разновидность обратных хтричных задач на собственные значения называется задачами допол->пия. Если существует блочное 2 х 2-разбиение матрицы такое, что гшщш множества fC заполняют один или несколько блоков, то говорят задаче дополнения блочного типа, в противном случае, о задаче допол-пия общего типа. Различным видам множества fC отводятся четыре авы основной части диссертации.

Вторая глава содержит исследование наиболее простого случая, ко-а /С — множество диагональных позиций матрицы. Для такого класса обратная матричная задача заключается в том, чтобы выбором вне-ахональных элементов "навязать" матрице требуемый спектр (задача ярского) или характеристический многочлен (задача Фарахата-Ледермання) ¡я разрешимости этих задач необходимо и достаточно, чтобы сумма за-нных диагональных элементов была равпа сумме желаемых собствен-х значений либо, если задан характеристический многочлен, коэффи-енту при (п - 1) -й степени, взятому с противоположным знаком.

Известные доказательства разрешимости задач Мирского и Фараха та-Ледерманна являются рациональными алгоритмами (или могут быт превращены в таковые путем несложной модификации) с трудоемкость! соответственно |п4 + 0(п3) и п3 + 0(п) арифметических операций. М] даем значительно более эффективные решения обеих задач, рассматр! вая их как частные случаи более общей задачи, часто встречающейс в различных теоретико-матричных построениях: по заданной нескалях ной матрице А со следом равным % и числам ¿1,^2сумма которы равна t, построить матрицу В с диагональными элементами , ¿2, •••, <1, подобную А. Алгоритм решения задачи Мирского, названный в работ алгоритмом Ч, заключается в следующем: с матрицей вида

Ч 1

А2 1

>«-1 1 V Ап,

выполняется последовательность элементарных преобразований; г-е ] них (г = 1,2,...,п - 1) затрагивает строки и столбцы с номерами г 1+1 и приводит к появлению в г-й диагональной позиции очередно: заданного элемента. Присутствие наддиагональных единиц в матри; (1) позволяет ограничиться использованием элементарных матриц пр стейшего типа. В результате п — 1 шагов указанного процесса получа< решение задачи Мирского.

Аналогично решается задача Фарахата-Ледерманна; отличие лиш!

ом, что вместо (1) нужно взять нижнюю клетку Фробениуса

/

\

О 1

О

1

О 1

\

~ап -яп-1 -а„_2 ••• "Û2 -«i

/

наче говоря, сопровождающую матрицу предписанного многочлена (Л) = Л" + >'i¡A„ -i + ... + ап. Алгоритм Ч использует |п2 + 0(п) арифме-ических операций.

Однако, быстродействие этой процедуры можно повысить, основыва-сь па хорошо известной идее сдваивания. Сущность предлагаемых избиений состоит в том, что, в отличие от алгоритма Ч, требуемые диаго-альные элементы получаем сначала в нечетных позициях (первый этап), алее в четных с номерами, не делящимися на 4 (второй этап), затем в озициях с номерами, делящимися на 4, но не делящимися на 8 (третий гаи), п т.д. Каждый этап, начиная со второго, предваряем элементар-ыми преобразованиями, которые обусловлены необходимостью сделать [.■скалярными главные 2 х 2-подматрицы, диагональные элементы кото-ых еще не приобрели требуемых значении. Это позволяет затем пропоить очередной этап посредством шагов, аналогичных тем, которые про-зводятся в алгоритме Ч. В результате в модифицированном алгоритме роисходит заполнение некоторых иаддиагональных позиций. С другой гороны, поддиагональные позиции заполняются иначе, чем в алгоритме , и притом не все. По сравнению с алгоритмом Ч, модифшщрован-лй алгоритм обладает двумя преимуществами: число арифметических герацпй, равное ri Iog2 п + 0(п), почти на порядок меньше; если вход-ле данные задачи суть целые или рациональные числа, а алгоритмы >,ализованы в рациональной арифметике, то средняя разрядность опе-

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

В заключение главы приведено символьное решение задач Мирского и Фарахата-Ледермана для п = 3 в виде матриц, элементы которых суть явные функции от заданных диагональных элементов и спектра или коэффициентов предписанного характеристического многочлена.

Третья глава посвящена задачам дополнения общего типа, т.е. задачам, в которых К — множество, состоящее из г произвольно заданны? позиций.

В параграфе 3.1 проводится анализ рациональной разрешимости трез конкретных задач дополнения. Сначала исследуется случай, когд; г = п — 1 и задан спектр (Задача За). Решение этой задачи существус] при любых начальных данных. В работе приведена конечная процедур« построения требуемой матрицы, основанная на доказательстве разреши мости, принадлежащем де Оливейре. Описание алгоритма проводите) методом индукции. Сначала рассматривается случай п = 2, для ко торого решения выписываются в явном виде. Далее, предполагая, чт< можно построить матрицу (п — 1)-го порядка с п - 2 заданными позици ями и спектром, исследуется матрица порядка п. Этот анализ разбива ется на несколько случаев, определяемых количеством заданных позицш в последних строке и столбце. Оказывается, что реально различны липи три ситуации: в последних строке и столбце нет заданных позиций либ< задана только одна позиция, и тогда важно, является эта позиция диаго нальной или внедиагональной. Для каждой из перечисленных ситуацш приводится решение по плану: строим главную подматрицу порядка п— с п — 2 заданными позициями и спектром А^..., А„_1, определяем специ альным образом последние строку и столбец и, если нужно, совершае»

«дополнительные элементарные преобразования подобия.

Задача 36 заключается в построении матрицы по заданным п произвольным позициям п спектру. Ее решепие представлено в виде алгоритма, полученного в результате анализа трех статей де Оливейры. Увеличение числа заданных позиций всего лишь на единицу приводит к заметному усложнению по сравнению с Задачей За. Так, для разреши мости данной проблемы должны выполняться необходимые и достаточные условия: 1) если полностью задана диагональ, то сумма требуемых циагоналъных элементов должна быть равна сумме предписываемых соб-;тн«шых значений; 2) если целиком задана строка (столбец) с нулями зо внедиагоналышх позициях, то значение, заданное для диагонального элемента, должно принадлежать предписываемому спектру. А при п —2 I заданных позициях (1,2) и (2,1) необходимо потребовать, чтобы поле К было алгебраически замкнутым.

Исследование Задачи 36 начинается с построения требуемой матрицы тля п — 2. Решение для произвольного и > 3 включает в себя анализ нести случаев, определяемых по аналогии с Задачей За. Построение требуемой матрицы для каждой ситуации происходит по единообразной :хеме, также похожей на соответствующую схему в предыдущей задаче. Основное отличие заключается в том, что, если построение алгоритма За фоводится по индукции, то в анализе Задачи 36 индукция отсутствует: 1 каждом случае ее решение сводится к решению одной или нескольких 5адач За меньшего порядка.

В третьей из задач данной главы требуется построить матрицу по [редписанным и—1 произвольным позициям и характеристическому мно-очлену. Замена спектра характеристическим многочленом в условии Задачи За влечет за собой существенное увеличение ее сложности. Если !адача За разрешима всегда, то разрешимость модифицированной за-

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

Как и в алгоритмах За и 36, анализ начинается с разбора ситуацш 71 = 2, а случай п > 3 включает в себя рассмотрение двух возможностей определяемых по аналогии с предыдущими задачами. Для каждой ситу ации строим (п — 1)х(п — 1)-матрицу В с п — 1 или п — 2 предписанным! позициями и простым спектром. Далее выбираем (п — 1)-мерный вектор V такой, чтобы пара {В, у) была управляемой. Приведя эту пару к ка ионической форме в виде нижней клетки Фробениуса (см. (2)) и вектор; (О, ...,0,1), достраиваем ее до п х п-матрицы с нужным характеристи ческим многочленом и, выполняя обратные преобразования, приходим з желаемому результату.

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

В параграфе 3.2 описаны особенности программной реализации ал горитмов За-Зв. В каждый из этих алгоритмов введен этап предвари тельного анализа предписанного множества /С; его задачей является вы бор по возможности более экономичного варианта построения требуемо! матрицы за счет (симметричного) переупорядочения строк и столбцов Примерами проиллюстрирована эффективность этого приема. Большо* внимание уделено вопросу о приведении управляемой пары (А, Ь) к вид;* (Г, е„), где ^ — нижняя клетка Фробениуса, а е„ — последний коор динатный вектор пространства Кп] это приведение является ключевое

конструкцией в решении Задачи Зв. Описана оригинальная процедура, эснованная на модификации известного алгоритма Данилевского. Отметим, что обычный алгоритм Данилевского также может быть использован для приведения управляемой матрично-векторной пары к некоторой канонической форме, но эта форма отличается от той, что нужна в алгоритме Зв. Поправки, внесенные нами в метод Данилевского, состоят в изменении порядка обработки строк и столбцов, некотором ограничении ■терапий но исключению элементов и введении дополнительного этана, за котором "почти-фробениусова" матрица преобразуется в клетку Фро-зениуса при сохранении вида вектора еп.

Параграф 3.3 отводится описанию численных экспериментов с задачами За-Зв. Здесь же приведены решения этих задач в символьном виде тля малых порядков п.

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

(Ли А\ч

(3)

>121 Л22

: квадратными блоками Ли и Л22 заданные позиции занимают один или «.•сколько блоков; нужно выбрать значения элементов оставшихся блоков гак, чтобы матрица приобрела предписанный спектр или характеристи-теский многочлен. Параграф 4.1 содержит постановку задач и сводку ■ведений из линейной алгебры, необходимых для данной главы.

В параграфе 4.2 приведен подробный анализ трех задач дополнения шочного типа. В них задаются соответственно: а) блок Аи (Л^-задача); >) блок Лц (Лц-задача); в) блоки Лц и А\1 ((Ли, Л^-задача), — и пред-шсывается характеристический многочлен. Понятно, что к решению 1тих задач могут быть сведены их вариалты, в которых задается спектр ¡место характеристического многочлена. Пусть I — порядок блока Лц в

(3), тогда т — n — l порядок блока А-п-

Анализ начинается с Л^-задачи. Если блок Л]2 — 0, то необходимым и достаточным условием ее разрешимости является возможность разложить заданный многочлен /(А) над полем К в произведение /(А) = Л(А)/2(А) многочленов степени / ига соответственно. При А\? ф 0 задача всегда рационально разрешима. Для построения решения заменим с помощью элементарных преобразований исходную задачу эквивалентной задачей, в которой блок Л12 имеет ненулевой элемент в позиции (1 ,тп). Выбираем блоки Лц, Л21 и Л 22 так, чтобы в полученной матрице А ведущая главная подматрица порядка п — 1 и последний столбец (взятый без последней компоненты) составляли управляемую пару. Достраивая эт> пару до матрицы с нужным характеристическим многочленом и возвращаясь в "исходную систему координат", получаем решение.

Далее анализу подвергается Лц-задача. В работе разбираются случаи, когда I < т или / > т, но к < га, где к — число инвариантные многочленов блока Лц, отличных от константы. При этих условиях Лц-задача разрешима для любых матрицы Лц и многочлена /(А). Построение решения начинается с выбора матрицы Л12 такой, что Лц и Ау. составляют управляемую пару. Разбор алгоритмических деталей этогс и последующих этапов выносится в параграф 4.3. Пусть фиксировав вектор х, представляющий собой линейную комбинацию столбцов найденного блока Л12; в качестве х можно взять, например, первый столбег этого блока. От пары (Лц, Л12) посредством допустимых преобразований задачи переходим к паре (Лц, Л12), где

Лп = Mi - A12G,

блок A\i имеет х своим первым столбцом и т X /-матрица G выбрана так чтобы матрично-векторная пара (Лц,х) была управляемой. Это свой-

/гво позволяет привести последнюю пару к канонической форме (Г, е/), где Г — нижняя клетка Фробениуса. Используем это приведение, чтобы тсрестроить пару (/1ц, Л12) в пару вида (.//, А12), где 3\ — жордапова ¿летка порядка 1с нулевыми собственными значениями. Для полученной ■дары несложно подобрать блоки Л21 и Дг2 так, чтобы ведущая главная тодматрица порядка п -1 в текущей матрице А и последний столбец этой матрицы (без последи«! компоненты) образовывали управляемую пару. Завершаем построение требуемой матрицы, как в решении Л12 задачи.

Для (Лц, Л^-задачи мы ограничиваемся формулированием теоремы :уществовапия: если заданные матрицы (Лц и Л^) составляют управляемую пару, то (Ли, Л^-задача рационально разрешима для любого юрмированного многочлена /(А) степени п. Конечный рациональный шгоритм решения этой задачи был по существу полностью описан при шализе Ли-задачи.

Параграф 4.2 заканчивается изложением условий разрешимости ^111^22) и (Л12, Л21)-задач с предписанным характеристическим мпо-■очленом п (Л ц, Л12, Л^-задачи с заданным спектром.

В параграфе 4.3 обсуждаются особенности программной реализации алгоритмов предыдущего раздела. Для Л12-задачи явпо выписан вид, к :оторому выгоднее приводить блок Ац:

Л12 -

/ О ТГ \

о о

(4)

де Т>г

матрица-перестановка:

а г = гапкЛ12. Напомним, что в приведенном выше описании алгоритма для .А) 1-задачи от блока А^ требовалось лишь неравенство нулю элемента в позиции (1 ,т). Выбор (4) значительно упрощает наиболее трудный этап алгоритма: приведение матрично-векторной пары к канонической форме.

Для Ац-задачи сначала описывается алгоритм построения матрицы Аобразующей с Ац управляемую пару. Матрица Ац приводится к прямой сумме клеток Фробениуса. Их количество Д- и порядки 6'],..., л^ указывают простейший выбор для подходящего блока А^:

А\2 = (е«, е82 ... ен О ... 0).

Здесь символ е,- обозначает координатный вектор размерности I. Далее указаны простые формулы для элементов матрицы С такой, что пара (Лл — А^С, е/) является управляемой.

Основное отличие алгоритма для (Ац, А^-задачи от предыдущего алгоритма, объясняемое тем, что теперь блок А\ч не может быть выбран по произволу, а определен условиями задачи, состоит во введении дополнительного этапа: пара (Ап,^^), вообще говоря, не являющаяся управляемой, преобразуется в пару специального вида (Ац, А^), где Ац — блочно-треугольная матрица, диагональные клетки которой суть (правые) клетки Фробениуса. Полагая затем х — е\, мы и здесь можем предложить простой способ выбора матрицы обеспечивающей управляемость пары (Ац - А12С?, х).

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

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

А =

А\

122

А\к Аък

(5)

О Аи

(в этом случае говорим, что матрица А разложима по Сильве). В такой ситуации нужно, чтобы многочлен / допускал над К разложение /(А) = /\(А) ■ ■ ■ Д(А), где степени сомножителей согласованы с порядками диагональных блоков в (5); кроме того, если положить

/¿(А) = А"' + с^А"'"1 + ■ • • + с*?., А + с« ¿ = 1,2,..., к,

то должно быть с^ = —Ц- Ац, г = 1,2,..., к. При этих условиях данная задача разрешима.

В параграфе 5.2 описан алгоритм решения задачи для случая, когда матрица А неразложима по Сильве. Наряду с этим накладывается еще одно условие: если представить А в виде

А =

I I \ «и К-\

9п-\ А-1

где А,,.! — (п-1)х(тг-1)-матрица, то пара (Ап„1,дп-{) управляема. При

/

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

Глава завершается обсуждением результатов чцсленных экспериментов и выводом символьного решения задачи Сильвы для п = 3.

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

Основные результаты диссертации состоят в следующем:

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

2. Резко повышена по сравнению с известными алгоритмами эффективность решения некоторых обратных задач на собственные значения-(например, задач Мирского и Фарахата-Ледерманна).

3. Решающие алгоритмы для девяти конкретных (и содержательных) обратных задач на собственные значения реализованы процедурами компьютерно-алгебраической системы МАРЬЕ.

Основные положения диссертации отражены в работах:

1. Ikramov Kh.D., Chugunov V.N. On the Teng inverse eigenvalue problem // Linear Algebra Appl. 1994. V. 208/209. P. 397-399.

2. Икрамов Х.Д., Чугунов B.H. Об одной обратной задаче на собственные значения. В сборнике "Численные методы анализа". Изд-во МГУ, 1995, с. 3 11.

3. "Икрамов Х.Д., Чугунов В.Н. Рациональная разрешимость обратной задачи Сильвы // ЖВМ и МФ. 1996. Т. 36, N 6. С. 20-27.

4. George A., Ikramov Kli.D., Tang W.-P., Tchugunov V.N. On doubly symmetric tridiagonal forms for complex matrices and tridiagonal inverse eigenvalue problems // SIAM Л. Matrix Analysis Appl. 1996. V. 17, N 3. P. 380-690.

5. Чугунов B.H. О преобразовании матрицы посредством подобия в матрицу с заданной главной диагональю. В сборнике "Пакеты прикладных программ". Изд-во МГУ, 1997, с. 133-140.

6. Икрамов Х.Д., Чугунов В.Н. Об одной теореме де Оливейры. В •¡борнпке "Библиотеки и пакеты прикладных программ". Изд-во МГУ, 1998, с. 84 93.

7. Чугунов В.Н. Об условиях разрешимости одной специальной обратной задачи на собственные значения. В сборнике "Библиотеки и па-сеты прикладных программ". Изд-во МГУ, 1998, с. 94 104.

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ им. М.В.ЛОМОНОСОВА

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

ЧУГУНОВ ВАДИМ НИКОЛАЕВИЧ

РАСШИРЕНИЕ ЛИНЕЙНО-АЛГЕБРАИЧЕСКИХ ВОЗМОЖНОСТЕЙ СИСТЕМ КОМПЬЮТЕРНОЙ

АЛГЕБРЫ

05.13.11 — математическое и программное обеспечение вычислительных машин, комплексов, систем и сетей

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

Москва 1998

Оглавление

1 Введение 3

2 Задачи Мирского и Фарахата-Ледерманна 10

3 Матричные задачи дополнения с произвольным расположением заданных элементов 20

4 Матричные задачи дополнения блочного типа 51

5 Обратная задача Сильвы 71

6 Заключение 79

7 Литература 81

8 Приложения 86

1 Введение

Проблемой собственных значений в прикладной линейной алгебре называют задачу вычисления (всех или части) собственных значений квадратной матрицы. Под обратной проблемой собственных значений понимают класс задач, которым можно дать следующее общее описание: для указанного класса С матриц размера п х п и заданного набора чисел Л = {А1,Ап} найти матрицу А £ С, спектр сг(А) которой совпадает с А. Вместо набора А может быть задан многочлен /(А) степени п со старшим коэффициентом 1 (такие многочлены мы называем нормированными), и тогда задача состоит в отыскании матрицы А £ С с характеристическим многочленом /(А).

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

1 < г'ь^ < тг V 1, (1.1)

и набор чисел {а^}, где (г,]) £ 1С. Класс С теперь определяется условием

= ау, V (г,.г) £ К. (1.2)

Элементы матрицы В £ С в позициях, дополнительных к 1С:

и = <щ («,;)££}, (1.3)

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

Эту вторую разновидность обратных задач на собственные значения мы будем называть задачами дополнения. Между собой такие задачи различаются мощностью подмножества /Си — при одинаковой мощности, — расположением позиций (г^). Может случиться, что существует блочное разбиение матрицы такое, что позиции (г,.у) Е /С заполняют один или несколько блоков; в этом случае мы говорим о задаче дополнения блочного типа. Всем прочим подмножествам К соответствуют задачи дополнения общего типа.

По отношению к каждому типу обратных задач на собственные значения будем изучать следующие вопросы: 1) разрешима ли задача над рассматриваемым числовым полем; 2) в случае разрешимости, как следует вычислять ее решение (или решения).

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

/(Л) = А" + а^1 + • • • + ап_1А + ап (1.4)

есть заданный характеристический многочлен. Если вместо /(А) предписаны собственные значения Лх,..., Ап, то коэффициенты ах,..., ап в (1.4) могут быть вычислены с помощью элементарных симметрических функций от чисел Аг-:

ак = (—1)^(Аь Л„). (1.5)

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

а* = (-1)* Е ¿е! А(ги...,гк). (1.6)

В этом равенстве А(г — главная подматрица матрицы А, сто-

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

Правая часть равенства (1.6) представляет собой многочлен степени < к от свободных параметров задачи; левая же часть задана. Тем самым, (1.6) и есть система алгебраических уравнений, эквивалентная исходной обратной задаче.

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

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

Теорема 1.1. Над алгебраически замкнутым полем К всякая аддитивная обратная задача на собственные значения разрешима и имеет конечное число решений. Если п — порядок задачи, то число ее решений всегда не превосходит п\ и почти всегда в точности равно п\.

Первое утверждение теоремы 1.1 было доказано в [16]. Другое его доказательство было дано в [15]; это доказательство содержало оценку числа решений задачи, указываемую вторым утверждением.

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

неизвестными, следовательно, и для обратных задач на собственные значения. Однако это высказывание общего характера не избавляет от необходимости исследовать конкретную задачу, если нас интересует ее разрешимость в радикалах. Такое исследование проведено лишь для сравнительно небольшого числа обратных задач; мы упомянем о нескольких из них. В [20] показано, что аддитивная обратная задача, для которой все числа а^ в (1.2) равны единице, при п > 5, вообще говоря, неразрешима в радикалах. Аддитивная обратная задача с " трехдиагональным портретом"

о, |«-Л>1,

неразрешима в радикалах уже при п = 4 [3]. С другой стороны, имеется хорошо известная трехдиагональная обратная задача (не относящаяся к классу аддитивных задач), которая разрешима даже в квадратичных радикалах. Она формулируется так: для заданного набора А различных чисел Ах,..., Ап построить дважды симметричную трехдиагональную матрицу А, спектр которой совпадает с А. Свойство двойной симметрии означает, что А, будучи симметричной в обычном смысле, симметрична еще и относительно диагонали (1, тг), (2, тг — 1),..., (п, 1). Решение этой задачи для случая, когда все числа Ах,Лп вещественны и требуется вычислить вещественную лее матрицу А, описано в [6, §7.12]. Комплексный вариант задачи рассмотрен в [18]. Еще одним примером обратной задачи, разрешимой в квадратичных радикалах, является задача Фид-лера: для заданного нормированного многочлена /(А) степени п найти симметричную пхп-матрицу А с характеристическим многочленом /(А). Два различных алгоритма, решающих эту задачу, указаны самим Фид-лером и Шмайзером [13, 32].

Итак, некоторые обратные задачи могут быть решены в квадратич-

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

/

0 0 • • • ~ап

1 0 • ■ ■ —&П-1

0 1 • • • —0"П-2

\

V

(1.7

/

О 0 ••• ~й!

составление которой вовсе не требует вычислений. Матрица (1.7) называется клеткой Фробениуса, или сопровождающей матрицей многочлена /(А).

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

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

заны построения в известных теоремах существования решения, где нарушена конечность или рациональность; приведены новые рациональные алгоритмы для этих ситуаций. Диссертация содержит также исследования результатов работы процедур, реализующих описанные алгоритмы средствами системы символьных вычислений МАРЬЕ.

Глава 2 посвящена задаче построения матрицы по заданной главной диагонали и спектру (или характеристическому многочлену). Задачам дополнения с произвольным расположением заданных элементов отводится глава 3. Далее (глава 4) рассматриваются задачи дополнения блочного типа, а последняя глава 5 содержит решение задачи Ф. Сильвы — построение матрицы по заданным диагональным и поддиагональным позициям и характеристическому многочлену.

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

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

г

Для пары индексов (г,^'), где г < ;}. символы ЬК1(с) и Щ(с) обозначают элементарные матрицы, отличающиеся от единичной только присутствием элемента с соответственно в позициях г) и (¿,7); для той же пары индексов Р^ обозначает матрицу-транспозицию, описывающую простейшую перестановку (г,.;) —► 0", г). Порядок этих матриц, равно как

и размерность векторов ег, не указывается явно, поскольку всегда ясен нз контекста.

2 Задачи Мирского и Фарахата-Ледерман-на

2.1. Постановка задач Мирского и Фарахата-Ледерманна

Задача Мирского [24] формулируется так: пусть Аь ..., Хп и 5П -два набора чисел из поля К, причем

Ах +----н = 5х +----Ь 5га. (2.1)

Найти п х п-матрицу над К, имеющую собственные значения Ах,..., А„ и диагональные элементы $х>

Эта задача (называемая в дальнейшем задачей М) является одной из первых (если не самой первой) из рассмотренных в алгебраической литературе матричных обратных задач на собственные значения. Сам Мирский дал в [24] индуктивное доказательство разрешимости задачи М над полем нулевой характеристики, которое может быть превращено в конечную процедуру для построения решений. Эта процедура использует лишь арифметические операции поля К; можно показать, что число операций умножения в ней равно |п4 + 0(п3).

Фарахат и Ледерманн рассмотрели в [12] следующую модификацию задачи Мирского: пусть помимо чисел «х, £ К задан еще нормированный многочлен /(А) степени п с коэффициентами из К:

/(А) = Ага + ахА"-1 + • • • + ап_хА + а„, (2.2)

причем

5х Н-----Ь = -а\. (2.3)

Найти п х те-матрицу над К, имеющую характеристический многочлен /(А) и диагональные элементы ..., 5П. Характеристический многочлен матрицы А здесь определяется как 6.еЬ(Х1п — А).

Сформулированная задача в дальнейшем именуется задачей ЕЬ. Фа-рахат и Ледерманн указали несложный рациональный алгоритм ее решения (алгоритм ЕЬ). Именно, строится система многочленов

щ(А) = 1, «1(Л) = Л — и2{А) = (А - вх)(А - в2)>

(2.4)

ип(А) = (А - 5х)(А - в2) • • • (А - 5П).

Заданный многочлен /(А) единственным образом разлагается по этой системе:

/(А) = ип + (р\ип—1 + (р2ип-2 + ... + (рпЩ■ (2.5)

Из условия согласования (2.3) следует, в частности, что коэффициент щ в (2.5) равен нулю. Если прочие коэффициенты (р2,...,(рп найдены, то решением задачи ЕЬ может служить матрица

А =

«1 О

о

1

«2

О

'^рп—1

0

1

о

■<Рп-2

О

о

о о

8п-1 1 -¥>2 «п

Учитывая только (более трудоемкие) операции умножения, нетрудно показать, что: 1) формирование системы многочленов (2.4) требует \п2 + 0(п) операций; 2) такое же (в главном члене) число операций понадобится для последовательного определения коэффициентов (р2,...,(рп из соотношения (2.5). В целом трудоемкость алгоритма Фарахата-Ледерманна составляет те2 + О (те) операций (умножения).

Цель настоящей главы — предложить рациональные алгоритмы для решения задач Мирского и Фарахата-Ледерманна, более эффективные,

чем алгоритмы из [24] и [12]. 2.2. Теорема Филмора

Указанная в заголовке теорема содержится в [14] и формулируется следующим образом.

Теорема 2.1. Пусть А — нескалярная п х п-матрица над полем К характеристики нуль, а 51,..., 5П — набор элементов из К такой, что

51 + ■ • ■ + 5„ = ^А. (2.6)

Тогда А подобна над К некоторой матрице с главной диагональю 51,..., вп.

Задачу построения по заданной матрице А и заданному набору 51,..., зп удовлетворяющему условию (2.6), невырожденной матрицы X такой, что ХАХ~1 имеет главную диагональ 51,..., 5П, мы называем задачей Т.

Нужно сказать, что работа Филмора [12] мало известна даже среди весьма сведущих экспертов в области теории матриц. Только этим можно объяснить тот факт, что в недавней публикации [21] теорема 1 аттестуется как теорема 3 из статьи [22].

Простой рациональный алгоритм, решающий задачу Г, предложен в [9]. Алгоритм основан на следующем анализе случая п = 2. Пусть

А =

(а П

с сI

/

(2.7)

— заданная матрица со следом t = а-М, а (в, — заданная новая главная диагональ. Если Ь ф- 0, то решением задачи Е является, например, матрица

Ь =

а 1

(2.8)

а — в

а

Если Ь = 0, но с ф 0, то можно положить

X = и =

/1 ^

О 1

(2.9)

где

5 — а

Наконец, при Ь = с = 0 имеем а ф ё, (матрица А нескалярная). В этом случае X строится как произведение треугольных матриц типа (2.8) и (2.9); в качестве значений параметров а и /3 можно взять, например

а = 1, (3 =

з — а

2 а - г

Пусть теперь те > 3. Обозначим через Ьц{а) и ((3) элементарные п х те-матрицы, опорный квадрат которых (т.е. четверка элементов, стоящих на пересечении строк и столбцов г и ]) имеет соответственно вид (2.8) и (2.9). Матрица X, решающая задачу Г, строится как произведение

X — Хп_\Х.

п—2 ■••

Х2Х1.

Сомножитель Х{ {г = 1,..., п— 1) определяется на г-м шаге процесса. Этот шаг состоит в том, что к главной подматрице

М+1

( (г) \

^ ъъ ^

о(г'} а®

\ аг+1,г г+1,г+1 )

текущей матрицы А^ = Хг-_х • • • Х\АХ\ 1 • ■ • 1 применяется описанный выше алгоритм для случая те = 2, причем

- „(О .

I — а+ а

г'+1,г+Ъ

8 = 5,-

Понятно, что вместо матриц (2.8) и (2.9) используются подобия с соответствующими п х п-матрицами Х<г;г+1 или £/¿.¿+1.

Наше изложение алгоритма из [9] — будем называть его алгоритмом Ч, — упрощено в том отношении, что не учитывается возможность возникновения на шаге % (г > 1) ситуации, когда нижняя угловая подматрица порядка п — г + 1 текущей матрицы Аг- является скалярной. Полное описание алгоритма включает в себя специальные подобия (тоже элементарные), предназначенные для выхода из таких ситуаций.

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

' \х 1 Л2 1

(

(2.10)

^п-1 1

х Хп /

На выходе алгоритма будет получена матрица Апу подобная матрице

(2.10) и имеющая диагональные элементы 51,...,5П. Роль наддиагональ-ных единиц в (2.10) состоит в том, чтобы обеспечить неравенство нулю элемента в позиции (г, ¿4-1) на каждом шаге алгоритма. Это гарантирует от возникновения особых ситуаций и позволяет ограничиться выполнением подобий с матрицами типа (2.8). Несложный подсчет показывает, что для построения матрицы Ап достаточно |п2 + 0(п) операций умножения. Это число на два порядка меньше, чем трудоемкость алгоритма Мирского.

Для решения задачи ГЬ алгоритм применяется к нижней сопрово-

/

А =

О

—а.

1 О

•О'п-1 —0"п-2

О 1

— 0>2 ~а1

1 „2

И здесь трудоемкость алгоритма составляет ^ операций умноже-

ния, что примерно вдвое меньше, чем в алгоритме Фарахата-Ледерманна.

2.3. Анализ численных экспериментов

Алгоритм Фарахата-Ледерманна и алгоритм Ч в применении к задаче ЕЬ были реализованы процедурами языка МАРЬЕ [11]. По этим процедурам был проведен счет для ряда задач, входными данными которых (т.е. предписываемыми диагональными элементами 51,..., зп и коэффициентами <21,...,а„) служили целые числа, (псевдо)случайным образом выбираемые из отрезка [—9,9]. Полученные результаты представлены в табл.1, (см. приложение 1). Значения порядка п, изменяющиеся от 2 до 100, указаны в первом столбце. При фиксированном п оба алгоритма применялись к одной и той же группе из т=50 матриц размера п х п. Во втором и третьем столбцах таблицы приведено среднее время работы (в секундах) соответственно алгоритма ЕЬ и алгоритма Ч для матриц порядка п.

Анализ табл.1 позволяет сделать несколько любопытных заключений. Несмотря на использование арифметики переменной разрядности, решение задачи ЕЬ даже при большом п порядка 100 все же возможно за вполне приемлемое время. Что