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

• Чугунов, Вадим Николаевич
• кандидат физико-математических наук
• 1998

Оглавление диссертации кандидат физико-математических наук Чугунов, Вадим Николаевич

1 Введение

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

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

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

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

Введение диссертации (часть автореферата) на тему «Расширение линейно-алгебраических возможностей систем компьютерной алгебры»

Проблемой собственных значений в прикладной линейной алгебре называют задачу вычисления (всех или части) собственных значений квадратной матрицы. Под обратной проблемой собственных значений понимают класс задач, которым можно дать следующее общее описание: для указанного класса С матриц размера п х п и заданного набора чисел Л = {А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", г). Порядок этих матриц, равно как и размерность векторов ег, не указывается явно, поскольку всегда ясен нз контекста.

Заключение диссертации по теме «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей», Чугунов, Вадим Николаевич

6 Заключение

В данной работе сделана попытка с единой точки зрения рассмотреть большой раздел линейной алгебры, представленный обратными задачами на собственные значения. Этой унифицирующей точкой зрения является возможность либо невозможность решить задачу посредством конечного рационального алгоритма. Если задача допускает такой алгоритм, то (при целочисленных или рациональных входных данных) для нее может быть построено точное решение средствами рациональной арифметики, реализуемой развитыми системами компьютерной алгебры. Для малых значений порядка с помощью символьных вычислений можно найти явный вид решения как функции входных параметров. Автору не известны какие-либо отечественные или зарубежные исследования, где проводилась бы аналогичная точка зрения. Именно с ней он связывает новизну и оригинальность результатов, полученных в диссертации.

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

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

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

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

2. Как рационально решать (А12, -А21) —, (А.ц, А12, А^-задачи с заданным характеристическим многочленом и (Ац, А12, А21)-задачу (хотя бы в варианте) с предписанным спектром?

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

Список литературы диссертационного исследования кандидат физико-математических наук Чугунов, Вадим Николаевич, 1998 год

1. Гантмахер Ф.Р. Теория матриц. — М.: Наука, 1966

2. Икрамов Х.Д. О размещении полюсов линейных стационарных систем // Вычисл. процессы и системы.— 1993.—9.— С. 35-162

3. Икрамов Х.Д., Уильямсон К. Об обратной задаче на собственные значения Хегланда-Марти // Мат. заметки.— 1977.— Vol. 61, N 1.— Р. 144-148

4. Икрамов Х.Д., Чугуиов В.Н. Об одной теореме де Оливейры // Библиотеки и пакеты прикладных программ. М.: Изд-во Моск. унта,— 1998 — С. 84-93

5. Маркус М., Минк X. Обзор по теории матриц и матричных неравенств. — М.: Наука, 1972

6. Парлетт Б. Симметричная проблема собственных значений. — М.: Мир, 1983

7. Фаддеев Д.К., ФаддееваВ.Н. Вычислительные методы линейной алгебры — М.-/ JL, Физматгиз. — 1963

8. Хорн Р., Джонсон Ч. Матричный анализ. — М.: Мир, 1989

9. Чугунов В.Н. О преобразовании матрицы посредством подобия в матрицу с заданной главной диагональю // Пакеты прикладных программ. М.: Изд-во Моск. ун-та,— 1997.— С. 133-140

10. Чугунов В.Н. Об условиях разрешимости одной специальной задачи на собственные значения // Библиотеки и пкеты прикладных программ. М.: Изд-во Моск. ун-та — 1998.— С. 94-104

11. Char B.W., Geddes К.О., Gonnet G.H. et al Maple V language reference manual // New York etc: Springer, 1991

12. Farahat H.K., Ledermann W. Matrices with prescribed characteristic polynomials // Proc. Edinburgh Math. Soc. — 1958. — 11. — P. 143-146

13. Fiedler M. Expressing a polynomial as the characterictic polynomial of a symmetric matrix // Linear Algebra Appl. — 1990. — Ц. — P. 255-270

14. Fillmore P.A. On similarity and the diagonal of a matrix // Amer. Math. Monthly. — 1969. — 76. — P. 167-169

15. Friedland S. Inverse eigenvalue problems // Linear Algebra Appl. — 1977. — 17. — P. 15-51

16. Friedland S. Matrices with prescribed off-diagonal elements // Isr. J. Math. — 1972. — 11. — P. 184-189

17. George A., Ikramov K., Krivoshapova A.N., Tang W.-P. A finite procedure for the tridiagonalization of a general matrix / / SI AM J. Matrix Anal. Appl. — 1995. — Vol. 16, N 2. — P. 377-387

18. George A., Ikramov Kh.D., Tang W.P., Tchugunov V.N. On double symmetric tridiagonal form for complex matrices and tridiagonal inverse eigenvalue problems // SIAM J. Matrix Analysis Appl. — 1996. — Vol. 17, N3. — P. 680-690

19. Hershkowitz D. Existence of matrices with prescribed eigenvalues end entries // Linear and Multilinear Algebra. — 1983. — Ц. — P. 315-342

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

21. Johnson C.R., Li C.-K., Rodman L., Spitkovsky I., Pierce S. Linear maps preserving regional eigenvalue location // Linear and Multilinear Algebra. — 1992. — Vol. 32, N 3/4. — P. 253-264

22. Johnson C.R., Shapiro H. Mathematical aspects of the relative gain array AA-*]* // SIAM J. Alg. Discr. Math. — 1986. — Vol. 7, N 4. — P. 627644

23. London D., Mine H. Eigenvalues of matrices with prescribed entries// Proc. Amer. Math. Soc. — 1972. — 31 — P. 8-14

24. Proceedings of the Colloquium on Numerical Methods. — Keszthely, Hungary (1977). — P. 491-500

25. Schmeiser G. A real symmetric tridiagonal matrix with a given characteristic polynomial // Linear Algebra Appl. — 1973. — 193. — P. 11-18

26. Silva F.C. Matrices with prescribed lower triangular part // Linear Algebra Appl. — 1993. — 182. — P. 27-34

27. Silva F.C. Matrices with prescribed characteristic polynomial and submatrices // Portugal. Math. — 1987. — U. — P. 261-264

28. Silva F.C. Matrices with prescribed eigenvalues and blocks // Linear Algebra Appl. — 1991. — 148. — P. 59-73

29. Wimmer H.K. Existenzs&tze in der Theorie der Matrizen und linear Kontrolltheorie // Monatsh. Math. — 1974. — 78. — P. 256-263

30. Wonham W.M., Morse A.S. Decoupling and pole assignment in linear multivariate systems: a geometric approach // SIAM J. Control. — 1970. — 8. — P. 1-18

31. Zaballa I. Existense of matrices with prescribed entries // Linear Algebra Appl. — 1986. — 73. — P. 227-280