Проблемой собственных значений в прикладной линейной алгебре называют задачу вычисления (всех или части) собственных значений квадратной матрицы. Под обратной проблемой собственных значений понимают класс задач, которым можно дать следующее общее описание: для указанного класса С матриц размера п х п и заданного набора чисел Л = {А1,Ап} найти матрицу, А? С, спектр сг (А) которой совпадает с А. Вместо набора, А может быть задан многочлен /(А) степени п со старшим коэффициентом 1 (такие многочлены мы называем нормированными), и тогда задача состоит в отыскании матрицы, А? С с характеристическим многочленом /(А).
Класс С может представлять собой один из хорошо известных классов специальных матриц, например, класс симметричных, теплицевых или неотрицательных матриц. Другая возможность задать класс С состоит в том, что фиксируются некоторое подмножество К пар индексов.
1 < г’ь^ < тг V 1, (1.1) и набор чисел {а^}, где (г,])? 1С. Класс С теперь определяется условием ау, V (г,.г)? К. (1.2).
Элементы матрицы В? С в позициях, дополнительных к 1С: и = <щ («,-)??}, (1.3) называются свободными. Обратная проблема собственных значений для класса С такого типа заключается в том, чтобы подбором свободных элементов «навязать» матрице из С требуемый спектр или характеристический многочлен.
Эту вторую разновидность обратных задач на собственные значения мы будем называть задачами дополнения. Между собой такие задачи различаются мощностью подмножества /Си — при одинаковой мощности, — расположением позиций (г^). Может случиться, что существует блочное разбиение матрицы такое, что позиции (г,.у) Е /С заполняют один или несколько блоковв этом случае мы говорим о задаче дополнения блочного типа. Всем прочим подмножествам К соответствуют задачи дополнения общего типа.
По отношению к каждому типу обратных задач на собственные значения будем изучать следующие вопросы: 1) разрешима ли задача над рассматриваемым числовым полем- 2) в случае разрешимости, как следует вычислять ее решение (или решения).
Что касается разрешимости, то полезно взглянуть на этот вопрос под таким углом зрения. Всякая обратная задача на собственные значения эквивалентна некоторой системе алгебраических уравнений относительно свободных параметров (свободных элементов, в случае задачи дополнения). Действительно, пусть.
Л) = А" + а1 + • • • + ап1А + ап (1.4) есть заданный характеристический многочлен. Если вместо /(А) предписаны собственные значения Лх,., Ап, то коэффициенты ах,., ап в (1.4) могут быть вычислены с помощью элементарных симметрических функций от чисел Аг-: ак = (—1)^(Аь Л&bdquo-). (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″, г). Порядок этих матриц, равно как и размерность векторов ег, не указывается явно, поскольку всегда ясен нз контекста.
6 Заключение.
В данной работе сделана попытка с единой точки зрения рассмотреть большой раздел линейной алгебры, представленный обратными задачами на собственные значения. Этой унифицирующей точкой зрения является возможность либо невозможность решить задачу посредством конечного рационального алгоритма. Если задача допускает такой алгоритм, то (при целочисленных или рациональных входных данных) для нее может быть построено точное решение средствами рациональной арифметики, реализуемой развитыми системами компьютерной алгебры. Для малых значений порядка с помощью символьных вычислений можно найти явный вид решения как функции входных параметров. Автору не известны какие-либо отечественные или зарубежные исследования, где проводилась бы аналогичная точка зрения. Именно с ней он связывает новизну и оригинальность результатов, полученных в диссертации.
К числу основных результатов диссертации следует отнести следующие: а) для ряда обратных матричных задач на собственные значения известные теоремы существования их решений превращены в конечные рациональные алгоритмы путем «рационализации» неконструктивных этапов доказательствб) резко повышена по сравнению с известными алгоритмами эффективность решения некоторых обратных задач на собственные значения (например, задачи Мирского) — в) решающие алгоритмы для девяти конкретных (и содержательных) обратных задач на собственные значения реализованы процедурами компьютерно-алгебраической системы МАРЬЕ.
Процедуры, упомянутые в п. в), могут быть включены в состав программных средств, обучающих стандартному и продвинутым курсам линейной алгебры. Они могут использоваться для генерирования тестовых матриц с целью проверки вычислительных алгоритмов линейной алгебры.
Диссертация отнюдь не исчерпывает данной области. Мы закончим работу формулированием некоторых направлений, по которым могут развиваться дальнейшие исследования:
1. При каком максимальном числе (как функции от п) заданных позиций возможно найти необходимые и достаточные условия существования решения задачи дополнения общего типа, при которых требуемую матрицу все еще можно получить посредством конечного рационального алгоритма?
2. Как рационально решать (А12, -А21) —, (А.ц, А12, А^-задачи с заданным характеристическим многочленом и (Ац, А12, А21)-задачу (хотя бы в варианте) с предписанным спектром?
3. Какие еще виды обратных матричных задач на собственные значения допускают построение решения, используя лишь конечное число арифметических операций рассматриваемого числового поля?
