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

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

- 1 и^ Я?

Факультет вычислительной математики А-кибернетики

На правах рукописи УДК 519.6

МИСУРКИНА Наталья Вячеславовна

КОМПЛЕКС ПРОЦЕДУР, РАСШИРЯЮЩИХ ВОЗМОЖНОСТИ КОМПЬЮТЕРНО-АЛГЕБРАИЧЕСКОЙ СИСТЕМЫ МАРЬЕ ДЛЯ ЗАДАЧ ЛИНЕЙНОЙ АЛГЕБРЫ

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

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

Москва — 2000

Диссертация выполнена на кафедре общей математики факультета вычислительной математики и кибернетики Московского государственного университета им. М. В. Ломоносова

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

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

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

— доктор физико-математических наук, профессор С. А. Абрамов

— кандидат физико-математических наук М. С. Сагитов

Ведущая организация — Институт вычислительной математики РАН

на заседании Диссертационного Совета Д.053.05.38 при факультете ВМиК МГУ по адресу

119899, Москва, Воробьевы горы, МГУ, факультет вычислительной математики и кибернетики.

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

Автореферат разослан аР~>.а Я^^?1) ? 2000 г.

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

Защита состоится ^ ." . 2000 г. в 11 часов в ауд. 685

профессор

Н.П. Трифонов

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

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

Предметом исследования в настоящей работе стали следующие линейно-алгебраические разделы:

1. Инвариантные подпространства матричных алгебр.

2. Условная знакоопределенность матриц.

3. Разделение корней алгебраических уравнений.

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

Цель проведенного исследования — для задач из выделенных классов построить эффективные рациональные алгоритмы решения и реализовать их средствами системы Maple. Более конкретно, для каждой задачи предполагалось:

— изучить и систематизировать теоретический материал;

— выделить результаты, которые (возможно после некоторой конструктивной модификации) допускают представление в виде конечных рациональных алгоритмов;

— усовершенствовать (где это возможно) полученные алгоритмы (например, за счет применения известных быстрых линейно-алгебраических методов);

— реализовать алгоритмы в виде процедур системы Maple;

— сформировать тестовый материал (матрицы или многочлены с нужными свойствами);

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

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

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

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

1. Алгоритмы и Марк-процедуры для задач раздела I (задачи о наличии у матриц А и В общего собственного вектора или общего инвариантного подпространства размерности > 1, о возможности одновременного приведения А и В к нетривиальной блочно-треугольной или блочно-диагональной форме, и т.д.).

2. Алгоритмы и Марк-процедуры, реализующие критерии знакоопределенности относительно заданного линейного подпространства £ и положительного ортанта R" пространства R".

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

относительно действительной оси, мнимой оси, единичной окружности и т.п.).

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

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

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

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

"Автоматизация программирования", научный руководитель — профессор М. Р. Шура-Бура, факультет ВМпК МГУ;

"Компьютерная алгебра", научный руководитель — профессор С. А. Абрамов, ВЦ РАН;

"Матричные методы и вычисления", научный руководитель — профессор Е. Е. Тыртышпиков, ИВМ РАН.

Публикации.

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

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

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

Объем диссертации без приложений — 100 страниц.

Библиография включает в себя 56 наименований.

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

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

Изучению каждого из разделов отводится по одной из трех основных глав текста.

Основной вопрос, рассматриваемый в первой главе — вопрос о наличии или отсутствии подпространства С, которое является общим инвариантным подпространством для всех элементов алгебры Л {Л С Л4п(С), Мп(С) — алгебра всех комплексных п х п-матрпц).

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

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

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

Ах = Хх, Вх = Хх, х ф О

и задачи о наличии у матрицы А собственного вектора х, принадлежащего подпространству kerB:

Ах = Хх, Вх = 0, х ф 0.

В параграфе 1.2 рассматривается обобщение задачи об общем собственном векторе. Пусть р £ N — фиксированное натуральное число, большее, чем 1. Требуется определить, имеют ли А и В общее инвариантное подпространство размерности р.

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

нетривиальному блочно-треугольному (блочно-диагональному) виду является в то же время достаточным условием наличия у А и В общего инвариантного подпространства. П. 1.2.1 посвящен изучению вопроса: существует ли невырожденная матрица <5, такая, что подобие

(!)

приводит всякую матрицу А € Л к блочно-диагональному виду

¿л = ап е а22 ®... е апи, (2)

где порядки диагональных блоков не зависят от Айне превосходят р (здесь А — полупростая подалгебра алгебры Л4п(С)).

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

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

Определение. Алгебра А С М„(С) называется квазидиагона-лизуемой, если подобием (1) она может быть приведена к блочно-диагональному виду (2) с блоками порядков 1 и 2, среди которых есть хотя бы одпн блок второго порядка.

Однако к алгебрам, порождаемым парами эрмитовых матриц, применимы более эффективные рациональные алгоритмы. Они содержатся в теоремах Лаффея, цитируемых в п. 1.2.2. С помощью результатов Лаффея проверяется также гипотеза об унитарной квазидиагонализуемости отдельной матрицы С: можно ли привести С к блочно-диагональному виду с блоками порядков 1 и 2 посредством

подобия С —► Q~lCQ с унитарной матрицей Q. Предлагается и более экономичный рациональный критерий для вещественной матрицы С, принадлежащий Булатовичу.

Параграф 1.3 содержит описание некоторых конкретных семейств матриц, которые, с одной стороны, иллюстрируют понятия и вопросы, изучаемые в главе I, а с другой — служат тестовым материалом для проверки работы соответствующих алгоритмов и сравнения их эффективности. В их числе: алгебра брауновских матриц, алгебры Боццо, семейства циркулянтов, ретроциркулянтов и квазп-циркулянтов, матрицы с квадратичным минимальным многочленом. Для каждого из этих семейств указан рациональный способ вычи-слепия. Предлагаются также методы построения пар матриц для иллюстрации различных вариантов задачи об общем собственном векторе, пар перестановочных и квазиперестановочных матриц, пар матриц с коммутатором ранга 1.

На основе изложенного теоретического материала выделены и реализованы в системе Maple конечные рациональные алгоритмы решения задач главы I и формирования описанных в параграфе 1.3 тестовых матриц.

В параграфе 1.4 приводятся перечень и краткое описание полученных Марк-процедур.

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

фективности и проводится анализ полученных экспериментальных данных.

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

Пусть 5„ — множество вещественных симметричных п х тг-мат-риц, С — нетривиальное подпространство арифметического пространства 11".

Определение. Матрица А £ 5„ называется С-полуопределенной, если

(Лж,а;)>0 ЧхеС, и С-определенной матрицей, если

(А я, я) > 0 Ух£С, х^О.

Параграф 2.1 посвящен исследованию вопроса: является ли заданная вещественная симметричная матрица С-(полу)определенной относительно заданного подпространства С1

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

проверки свойства обычной (попу)определенности).

Особенности реализации алгоритмов средствами системы Maple и перечень полученных Марк-процедур приведены в п. 2.1.2.

В п. 2.1.3 описан удобный способ задания подпространств С и соответствующих им ¿-определенных матриц А, использующий матрицы Адамара и свойства ортопроекторов. Кроме того, указаны два класса матриц, определенных относительно подпространства С, задаваемого системой линейных уравнений:

еТх = 0, е = (1,1,...,1)г,

а именно, евклидовы дистанционные матрицы и лапласианы графов.

Далее (п. 2.1.4) следует описание и обсуждение результатов экспериментов по сравнению полученных алгоритмов и соответствующих Марк-процедур. Наиболее экономичным оказывается подход к проверке ¿-определенности, состоящий в сведении ее к проверке обычного свойства положительной определенности.

Пусть

R" = {х | х > 0}

— неотрицательный ортант вещественного арифметического пространства.

Определение. Матрица А £ Sn называется коположителъной, если

{Ах,х)> 0 VxGR", и строго коположителъной, если

(Ах,х)> 0 VzGR", хфО. 10

Основной вопрос второй части главы 2: является ли заданная вещественная симметричная матрица (строго) коположителъной.

Необходимым условием наличия у матрицы свойства коположи-тельностп является коположительность всех ее главных подматриц. Поэтому большинство критериев коположительности являются индуктивными, т.е. основаны на последовательном анализе главных подматриц в направлении возрастания их порядков. Известные критерии такого рода, принадлежащие Моцкпну, Келлеру и Вальяхо, формулируются в п. 2.2.1. Часть из них относится к так называемым внутренним критериям, где анализ очередной главной подматрицы П не использует информации о внешней по отношению к И части исходной матрицы А. Формулируется и внешний критерий, в котором инспекция текущей главной подматрицы I) связана с анализом определяемого ею блочного исключения — операции перехода к матрице специального вида, в формировании которой участвуют и внешние для Б элементы А.

Комбинацией двух критериев внутреннего типа получен третий, более эффективный внутренний критерий.

Известно, что задача проверки заданной квадратной целочисленной матрицы на наличие или отсутствие свойства коположительности является ЫР-полной. Поэтому особый интерес представляют ситуации, позволяющие значительно сократить перебор подматриц. В п. 2.2.2 приводятся две такие ситуации:

1) заранее известен ранг пли положительный индекс инерции А;

2) в А имеется строка (или строки), все элементы которой неотрицательны.

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

На основе критериев из п. 2.2.1 с предложенными в п. 2.2.2 усовершенствованиями составлено несколько версий алгоритмов проверки свойства коположительности. Соответствующие Мар1е-процедуры перечисляются в п. 2.2.3. Там же приводятся способы формирования тестовых коположительных матриц (простыми их примерами могут служить матрицы с неотрицательными элементами и положительно определенные в обычном смысле матрицы, а также пх линейные комбинации с неотрицательными коэффициентами). После чего описываются сравнительные тесты с полученными процедурами и обсуждаются их результаты.

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

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

f(x) = О,

где

f(x) = a0xn + a1xn-l + --- + an> а{ <Е R(C), а0 ф 0.

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

внутри или вне единичного круга (проблема Шура-Кона).

Основным источником теоретических сведений послужила классическая обзорная статья Крейна и Наймарка, посвященная особенностям применения метода квадратичных (эрмитовых) форм в теории разделения корней.

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

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

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

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

Диссертация содержит два приложения.

В приложении I систематизированы результаты экспериментов по сравнению эффективности Марк-процедур, реализующих различ-ные-алгоритмы решения рассмотренных задач. Показателем эффективности является время применения процедур к тестовым матрицам (многочленам). Данные экспериментов содержатся в 14-тп таблицах.

Приложение II содержит несколько типичных примеров использования полученных Марк-процедур для формирования тестовых матриц и решения задач.

Основные результаты работы

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

1. Инвариантные подпространства матричных алгебр.

2. Условная знакоопределенность матриц.

3. Разделение корней алгебраических уравнений.

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

• выделены рациональные алгоритмы решения;

• предложены способы повышения эффективности некоторых алгоритмов;

• полученные алгоритмы реализованы средствами компьютерно-алгебраической системы Maple.

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

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

Публикации по теме диссертации

1. Икрамов Х.Д., Савельева Н.В., Чугунов В.Н. О рациональных критериях существования общих собственных векторов или инвариантных подпространств // Программирование. 1997. N3. С. 43-57

2. Икрамов Х.Д., Савельева Н.В. Об эффективной компьютерно-алгебраической реализации критерия Шура-Кона-Фудживары // Вестник МГУ. Вычисл. матем. и киберн. 1998. N2. С. 9-12

3. Икрамов Х.Д., Савельева Н.В. О некоторых квазидиагонали-зуемых семействах матриц// ЖВМиМФ. 1998. Т.38. N7. С.1075-1084

4. Икрамов Х.Д., Савельева Н.В., Чугунов В.Н. О компьютерно-алгебраических процедурах, проверяющих наличие общих собственных векторов или инвариантных подпространств // Методы математического моделирования. М.: Изд-во МГУ. 1998. С.5-23

5. Икрамов Х.Д., Савельева Н.В. Условно знакоопределенные матрицы. Современная математика и ее приложения. Тематические обзоры. 1998. Т. 52. Алгебра-9. Итоги науки и техники. ВИНИТИ

6. Икрамов Х.Д., Савельева Н.В. Компьютерно-алгебраические процедуры для проверки матричного свойства знакоопределенности на подпространстве // ЖВМиМФ. 1999. V. 39. N3. С.357-370

7. Икрамов Х.Д., Савельева Н.В. Коположительные матрицы // ЖВМиМФ. 1999. У.39. N8 . С. 1253-1279

8. Савельева Н.В. Компьютерно-алгебраические процедуры для задачи разделения корней алгебраических уравнений // ЖВМиМФ. 1999. V. 39. N10. С. 1603-1619

9. Икрамов Х.Д., Савельева Н.В. Инерция матриц и квадратичных форм, условно знакоопределенные матрицы, разделение корней алгебраических уравнений п Марк-процедуры // Программирование. 2000. N1.

Введение.

Глава 1. Инвариантные подпространства матричных алгебр.

1.1. Наличие общих собственных векторов.

1.1.1. Одновременная триангуляризация.

1.1.2. Критерий Шемеша.

1.2. Инвариантные подпространства размерности >1.

1.2.1. Полиномиальные тождества.

1.2.2. Критерии квазидиагонализуемости.

1.3. Семейства и классы матриц, обладающие общими инвариантными подпространствами.

1.4. Описание Марк-процедур.

1.5. Особенности практического применения процедур.

Глава 2. Условно знакоопределенные матрицы.

2.1. /^-определенность матриц.

2.1.1. Критерии и алгоритмы ^-определенности.

2.1.2. Особенности Мар1е-реализации алгоритмов.

2.1.3. Способы построения ^-определенных матриц.

2.1.4. Сравнительный анализ алгоритмов ^-определенности

2.2. Коположительность матриц.

2.2.1. Внутренние и внешние критерии коположительности

2.2.2. Способы повышения эффективности критериев.

2.2.3. Построение тестовых коположительных матриц и сравнительные тесты с Maple-процедурами.

Глава 3. Разделение корней алгебраических уравнений.

3.1. Постановка задач разделения корней и алгоритмы их решения.

3.2. Особенности реализации и способы усовершенствования алгоритмов.

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

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

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

В рамках упомянутого подхода весьма перспективно использование компьютерно-алгебраических систем при разработке различных курсов высшей математики. Отличительная особенность систем компьютерной алгебры (систем символьных вычислений) — возможность проведения расчетов в символьном виде; в развитых системах пользователь имеет и возможность работы в безошибочной арифметике при действиях с рациональными числами. К таким системам относятся, например, хорошо известные пакеты Mathematica, Maple, REDUCE, Axum, Derive.

Одну из ведущих позиций среди перечисленных систем занимает

Maple. Ее отличают богатая математическая библиотека (около 2000 процедур), в составе которой имеются специализированные пакеты, соответствующие ряду математических разделов; хорошо структурированный Help; лаконичный и удобный интерфейс; широкие возможности визуализации информации и ее вывода в различных форматах. Стандартная библиотека может пополняться собственными программами пользователя, написанными на Мар1е-языке, что позволяет расширить возможности того или иного раздела Maple для решения нестандартных задач.

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

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

Предметом исследования в настоящей работе стали следующие разделы:

Заключение

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

1. Инвариантные подпространства матричных алгебр.

2. Условная знакоопределенность матриц.

3. Разделение корней алгебраических уравнений.

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

Для всех таких задач:

• выделены конечные рациональные алгоритмы решения;

• предложены способы повышения эффективности некоторых алгоритмов;

• полученные алгоритмы реализованы средствами компьютерно-алгебраической системы Maple.

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

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

1. Сливина Н. Универсальные математические пакеты в математическом образовании инженеров // КомпьютерПресс. — 1997. — N8. — С.78-85

2. Икрамов Х.Д., Савельева Н.В., Чугунов В.Н. О рациональных критериях существования общих собственных векторов или инвариантных подпространств // Программирование. — 1997. — N3. — С. 43-57

3. Икрамов Х.Д., Савельева Н.В., Чугунов В.Н. О компьютерно-алгебраических процедурах, проверяющих наличие общих собственных векторов или инвариантных подпространств / Методы математического моделирования. — М.: Изд-во МГУ, 1998. — С. 5-23

4. McCoy N. Н. On the characteristic roots of matrix polynomials // Bull. Amer. Math. Soc. — 1936. — V. 42. — P. 592-600

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

6. Laffey Т. J. Simultaneous triangularization of matrices — low rank cases and the nonderogatory case // Linear and Multilinear Algebra. — 1978.— V,6 — P. 269-305

7. McCoy N. H. On quasi-commutative matrices // Trans. Amer. Math. Soc. — 1934. — V. 36. — P. 327-340

8. Shemesh D. Common eigenvectors of two matrices // Linear Algebra Appl. — 1984. — V. 62. — P. 11-18

9. George A., Ikramov Kh.D. Common invariant subspaces of two matrices 11 Linear Algebra Appl. — 1999. — V. 287. — P. 171-179

10. Amitsur S.A., Levitzki J. Minimal identities for algebras // Proc. Amer. Math. Soc. — 1950. — V. 1. — P. 449-463

11. Levitzki J. A theorem on polynomial identities // Proc. Amer. Math. Soc. — 1950. — V. 1. — P. 334-341

12. Barker G.P., Eifler L.Q., Kezlan T.P. A non-commutative spectral theorem // Linear Algebra Appl. — 1978. — V. 20. — P. 95-100

13. Дренский B.C. Минимальный базис для тождеств матричной алгебры порядка 2 над полем характеристики нуль // Алгебра и Логика.1981. — Т. 20. — С. 282-290

14. Laffey Т. J. Simultaneous quasidiagonalization of complex matrices // Linear Algebra Appl. — 1977. — V. 16. — P. 189-201

15. Булатович P.M. Одновременное приведение симметрической и косо-симметрической матриц к каноническому виду // Мат. Црне Горе.1997.— Т. 8.— С. 33-36

16. Gover M.J.С. A ring of Brownian matrices // Linear Algebra Appl. — 1988.— V. 103. — P. 87-102

17. Икрамов Х.Д. Несколько замечаний о брауновских матрицах / Библиотеки и пакеты прикладных программ. — М.: Изд-во МГУ, 1996.1. С.127-132

18. Martignon L. F. Doubly stochastic matrices with prescribed positive spectrum // Linear Algebra Appl. — 1984. — V.61. — P. 11-13

19. Bell С. L. Generalized inverses of circulant and generalized circulant matrices // Linear Algebra Appl. — 1981. — V.39. — P. 133-142

20. Chao C.-Y. On a type of circulants // Linear Algebra Appl. — 1973. — V. 6. — P. 241-248

21. Aitken A.C. Two notes on matrices // Proc. Glasgow Math. Assoc. — 1961. — V.62. — N5. — P. 109-113

22. Smith. R. L. The Moore-Penrose inverse of a retro circulant / / Linear Algebra Appl. — 1978. — V. 22. — P. 1-8

23. Икрамов Х.Д., Савельева H.B. О некоторых квазидиагонализуемых семействах матриц // ЖВМиМФ. — 1998. — Т. 38. — N7. — С. 1075-1084

24. Икрамов X. Д. О численном решении линейных систем квазицирку-лянтной структуры / Пакеты прикладных программ. — М.: Изд-во МГУ, 1997.— С. 120-123

25. Bozzo Е. Algebras of higher dimension for displacement decompositions and computations with Toeplitz plus Hankel matrices // Linear Algebra Appl. — 1995. — V. 230. — P. 127-150

26. Икрамов X. Д. Каноническая форма Шура унитарно квазидиагонали-зуемой матрицы // ЖВМиМФ. — 1997. — Т. 37. — N. 12. — С. 14111415

27. Икрамов Х.Д., Савельева Н.В. Условно знакоопределенные матрицы. Современная математика и ее приложения. Тематические обзоры. 1998. Т. 52. Алгебра-9. Итоги науки и техники. ВИНИТИ.

28. Икрамов Х.Д., Савельева Н.В. Компьютерно-алгебраические процедуры для проверки матричного свойства знакоопределенности на подпространстве // ЖВМиМФ. — 1999. — V.39. — N3. — С. 35737029