Введение к работе
Актуальность работы. Одним из перспективных современных направлений развития компьютерных технологий в образовании является разработка новых учебных курсов на базе существующих специализированных пакетов прикладных программ. В рамках такого подхода при изучении математических дисциплин, в частности, линейной алгебры, широко используется возможность проведения на компьютере символьных преобразований, а также использования безошибочной арифметики при действиях с целыми или рапиональ-пыми числами. Такую возможность предоставляют современные системы символьных вычислений (системы компьютерной алгебры). В состав одной из наиболее популярных компьютерно-алгебраических систем Maple входит, в числе прочих, пакет, ориентированный па решение линейно-алгебраических задач (пакет linalg). Набор его процедур охватывает — с некоторыми оговорками, — круг вопросов, рассматриваемых в элементарном курсе линейной алгебры, но оказывается недостаточным для поддержки более или менее продвинутого курса. Таким образом, существует необходимость расширить возможности системы Maple для решения нестандартных линейно-алгебраических задач.
Предметом исследования в настоящей работе стали следующие линейно-алгебраические разделы:
Инвариантные подпространства матричных алгебр.
Условная знакоопределенность матриц.
Разделение корней алгебраических уравнений.
В рамках каждого раздела был выделен класс задач, для решения которых могут быть построены конечные рациональные алгоритмы. Так мы называем алгоритмы, использующие только арифметические операции и за конечное число шагов дающие точное решение задачи (при условии, что начальные данные также заданы точно, например, матрицы с целыми или рациональными элементами, многочлены с целыми или рациональными коэффициентами). Рациональные алгоритмы могут быть реализованы в безошибочной арифметике, являющейся одной из опций развитых систем компьютерной алгебры.
Цель проведенного исследования — для задач из выделенных классов построить эффективные рациональные алгоритмы решения и реализовать их средствами системы Maple. Более конкретно, для каждой задачи предполагалось:
изучить и систематизировать теоретический материал;
выделить результаты, которые (возможно после некоторой конструктивной модификации) допускают представление в виде конечных рациональных алгоритмов;
усовершенствовать (где это возможно) полученные алгоритмы (например, за счет применения известных быстрых линейно-алгебраических методов);
реализовать алгоритмы в виде процедур системы Maple;
сформировать тестовый материал (матрицы или многочлены с нужными свойствами);
если для решения задачи можно выделить несколько различных алгоритмов, сравнить их (теоретически и экспериментально), чтобы указать наиболее эффективный.
Научная новизна работы. Для перечисленных выше трех линейно-алгебраических разделов проведена классификация задач с точки зрения возможности их решения конечным рациональным способом, обусловленная особенностями компьютерно-алгебраической реализации. Для задач, допускающих конечное рациональное решение, выделены и в ряде случаев усовершенствованы рациональные алгоритмы решения. Эти алгоритмы реализованы посредством комплекса из 46 процедур системы Maple, существенно расширяющего возможности ее стандартного линеішо-алгебраического пакета linalg (125 процедур).
Предложен комплекс тестовых матриц, обслуживающих рассмотренные задачи и соответствующие алгоритмы. Он коренным образом отличается от известных наборов тестовых матриц в вычислительной линейной алгебре.
На защиту выносятся следующие результаты работы:
1. Алгоритмы и Maple-процедуры для задач раздела I (задачи
о наличии у матриц А и В общего собственного вектора или об
щего инвариантного подпространства размерности > 1, о возмож
ности одновременного приведения А и В к нетривиальной блочно-
треугольной или блочно-диагональной форме, и т.д.).
Алгоритмы и Maple-процедуры, реализующие критерии знакоопределенности относительно заданного линейного подпространства п положительного ортанта R" пространства R".
Алгоритмы и Maple-процедуры для задач разделения корней алгебраических уравнений (т.е. задач типа: определить расположение корней заданного вещественного или комплексного многочлена
относительно действительной оси, мнимой оси, единичной окружности и т.п.).
4. Алгоритмы и Maple-процедуры для генерации матриц из тестовых семейств.
Практическая значимость работы. Получено содержательное расширение линейно-алгебраических возможностей системы компьютерной алгебры Maple. В среде Maple реализованы конечные рациональные алгоритмы решения ряда задач из трех конкретных разделов линейной алгебры, а также алгоритмы формирования соответствующих тестовых матриц.
Созданный комплекс процедур может применяться для сопровождения учебных курсов линейной алгебры, включающих указанные разделы. Некоторые из процедур могут быть полезны п в теоретико-матричных исследованиях.
Апробация работы. Основные положения диссертации докладывались на семинарах:
"Автоматизация программирования", научный руководитель — профессор М. Р. Шура-Бура, факультет ВМпК МГУ;
"Компьютерная алгебра", научный руководитель — профессор С. А. Абрамов, ВЦ РАН;
"Матричные методы и вычисления", научный руководитель — профессор Е. Е. Тыртышпиков, ИВМ РАН.
Публикации.
Основные результаты работы отражены в публикациях [1-9].
Структура и объем работы.
Диссертация состоит из введения, трех глав основного текста, заключения, списка литературы и двух приложений. Объем диссертации без приложений — 100 страниц. Библиография включает в себя 56 наименований.
