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

• Матин Фар Машалла Набиолла
• кандидат физико-математических наук
• 2004

Оглавление диссертации кандидат физико-математических наук Матин Фар Машалла Набиолла

Введение.

Глава 1. Псевдообращение матрицы и безусловная задача наименьших квадратов.

1.1. Рациональные алгоритмы.

1.1.1. Скелетное разложение.

1.1.2. Метод Эрмита.

1.1.3. Метод Гревилля.

1.2. Вычисление псевдообратной матрицы в системе Maple

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

Глава 2. Задачи наименьших квадратов с линейными ограничениями

2.1. Ограничения в виде линейных уравнений.

2.1.1. Постановка задачи HKY.

2.1.2. Рациональные алгоритмы.

2.1.3. Тестовые задачи.

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

2.2. Ограничения в виде линейных неравенств.

2.2.1. Постановка задачи НКН.

2.2.2. Алгоритм NNLS.

2.2.3. Тестовые задачи.

2.2.4. Результаты численных экстриментов.

2.2.5. Преобразование задачи НКН в задачу LDP.

2.2.6. От задачи LDP к задаче NNLS.

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

Глава 3. Пересчёт псевдообратных матриц и нормальных псевдорешений при одноранговых модификациях задачи.

3.1. Безусловная ЗНК.

3.1.1. Постановка задачи.

3.1.2. Формулы пересчёта.

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

3.2. Задача НКУ.

3.2.1. Постановка задачи.

3.2.2. Модифиицрованные формулы Гревилля.

3.2.3. Детали реализации и численные эксперименты.

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

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

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

В методе наименьших квадратов наиболее желательный вектор — это вектор х с наименьшей 2-нормой. Он называется нормальным псевдорешением системы (0.2) и существует для всякой системы линейных уравнений. Если система однозначно разрешима, то нормальное псевдорешение этой системы совпадает с ее единственным решением в обычном смысле.

В библиотеках и пакетах программ по численному анализу для решения системы (0.2) в смысле наименьших квадратов применяется следующий стандартный подход:

1. Для матрицы А находим то или иное ортогональное (или унитарное) разложение, т.е. представление типа х) = \\АХ-Ъ\\2.

Всякий такой вектор х называется решением системы

Ах = Ь

0.1)

0.2)

А = НШ

0.3) где Н и К — унитарные матрицы соответственно порядка т и п, а Я — матрица вида

Я = Rn 0 х о о с невырожденной (г х г)-подматрицей Яц. 2. Представим вектор д = Н*Ь в виде

9 = \

91 v 92 , где д\ — подвектор размерности г. Обозначим через у\ единственное решение системы линейных уравнений

RnVi = 9i

Если г = ?2, то вектор х = Kyi есть единственное и, значит, нормальное псевдорешение системы (0.2). В противном случае, линейное многообразие псевдорешений описывается формулой х = К где у2 — произвольный вектор размерности п —г. Выбор у2 = 0 определяет нормальное псевдорешение х = К ~ \ Vi о

Два наиболее популярных типа разложения (0.3) — это С^Я-разложение матрицы Л и ее сингулярное разложение. Первый тип разложения может быть осуществлен разными способами — посредством той ли иной разновидности процесса ортогонализации Грама-Шмидта или с помощью элементарных унитарных матриц. В любом варианте это конечный процесс, использующий арифметические операции (к числу которых в случае комплексной системы прибавляется операция сопряжения) и квадратичные радикалы. Матрица К в QR-разложении — это некоторая матрица- перестановка, а подматрица Яц — треугольпая. Сингулярное разложение есть итерационный процесс, в котором вычисляется диагональная матрица Яц, составленная из сингулярных чисел матрицы А.

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

Сопоставим задаче (0.2) систему линейных уравнений

А* Ах = А*Ь. (0.4)

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

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

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

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

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

ХАХ = X, (АХ)* = АХ, (ХА)* = ХА.

0.6) (0.7) (0.8)

Эта матрица получила символ А+ и нередко называется (псевдо)обратной матрицей Мура-Пенроуза, чтобы отличить ее от других типов обобщенных обратных матриц.

Несмотря на присутствие в системе уравнений Пенроуза квадратичного уравнения (0.6), псевдообратная матрица А+ может быть вычислена посредством рационального алгоритма. Этот удивительный факт более подробно обсуждается в первой главе диссертации. Возвращаясь к задаче (0.2), укажем, что если матрица А+ известна, то нормальное псевдорешение х можно найти по формуле

Эта формула и дает рациональное решение задачи вычисления нормального псевдорешения. В случае квадратной невырожденной матрицы А псевдообратная матрица А+ совпадает с обычной обратной матрицей А"1, а формула (0.9) переходит в хорошо известное равенство

Важная роль, которую приобрела в современной теории матриц операция псевдообращения, до недавнего времени не находила отражения в системах компьютерной алгебры. Так, в системе Maple вплоть до ее седьмой версии не было процедур для прямого вычисления матрицы А+. Если пользователю матрица А+ все же была необходима, то приходилось многократно обращаться к библиотечной процедуре LeastSquares, решающей задачу наименьших квадратов (0.2): задавая в качестве Ь координатные х = А+Ъ.

0.9) х = A~lb. векторы n-мерного пространства ei,., еп, пользователь получал в качестве нормальных псевдорешений столбцы псевдообратной матрицы.

Лишь в седьмой версии Maple процедура LeastSquares была модифицирована таким образом, чтобы можно было решать более общие задачи наименьших квадратов

Ах = В (0.10) с (тхр)-матрицей В. Теперь псевдообращение матрицы А может быть достигнуто единственным обращением к LeastSquares с единичной матрицей 1т в качестве правой части В задачи (0.10).

Однако и теперь возможности Maple даже в отношении собственно задачи наименьших квадратов остаются весьма ограниченными. Например, помимо безусловной ЗНК, обсуждавшейся до сих пор, на практике очень часто возникает необходимость в минимизации функционала (0.1) при тех или иных ограничениях на искомый вектор х, Наиболее распространенными типами ограничений являются системы линейных уравнений, системы линейных неравенств, комбинации тех и других и квадратичные ограничения вида ЦжЦг < с или ||ж — < с. Во второй главе диссертации показано, что задачи наименьших квадратов с линейными ограничениями могут быть решены рационально, и описаны соответствующие алгоритмы. Ни один из них не содержится в Maple.

Не эффективна Maple и в такой ситуации, типичной для многих приложений: после того как задача (0.2) решена, в систему вводится новое уравнение и требуется решить новую ЗНК

Ах = Ъ. (0.11)

Другая типичная ситуация: задача (0.11) получается из (0.2) удалением одного уравнения. В обоих этих случаях у пользователя Maple нет альтернативы решению задачи (0.11) как новой посредством той же процедуры

LeastSquares без какого-либо использования информации о решении предыдущей задачи.

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

А A + cd\

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

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

В каждой главе диссертации и Приложении 1 мы стараемся придерживаться следующего общего плана:

1. Постановка задачи.

Всякий раз предполагается, что коэффициенты задачи суть точно заданные рациональные числа, и ищется точное решение.

2. Описание рациональных алгоритмов, решающих данную задачу.

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

3. Обсуждение особенностей реализации алгоритмов из п.2 в виде процедур языка Maple.

4. Описание тестовых задач.

5. Обсуждение результатов тестирования (включающее в себя сравнение эффективности различных алгоритмов).

Вычисления проводились на персональном компьютере Pentium III-650 с версиями б и 7 системы Maple.

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

Разделы "Псевдообратные операторы и матрицы"и "Решение линейных систем по методу наименьших квадратов "были впервые введены в программу обязательных университетских курсов линейной алгебры в книге В.В. Воеводина "Линейная алгебра"(1974 г.) и сопровождавшем ее "Задачнике по линейной алгебре"Х.Д. Икрамова. Комплекс Мар1е-процедур, разработанных в данной диссертации, существенно облегчает учащемуся овладение этими разделами, избавляя от рутинных вычислений и позволяя сосредоточиться на сути.

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

Заключение

С теоретической точки зрения, основным результатом настоящей диссертации является доказательство возможности получения точных решений для двух важных классов линейно-алгебраических задач с точно заданными рациональными коэффициентами. Это, во-первых, обобщенное обращение матриц, среди многочисленных разновидностей которого наиболее полезными являются псевдообращение по Муру-Пенроузу (глава 1) и обращение вырожденных квадратных матриц по Дрейзину (см. П1.1). Это, во-вторых, линейные задачи наименьших квадратов. Возможность точного решения безусловной задачи наименьших квадратов (ЗНК) была осознана уже довольно давно, что отразилось, в частности, во включении процедуры LeastSquares уже в ранние версии Maple. Такого осознания не было в отношении ЗНК с ограничениями в виде линейных уравнений и/или неравенств. В главе 2 мы показали возможность точного решения этой задачи. То же относится к вопросам экономного пересчета псевдорешений при одноранговых модификациях задачи наименьших квадратов (глава 3).

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

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

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

Список литературы диссертационного исследования кандидат физико-математических наук Матин Фар Машалла Набиолла, 2004 год

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

2. Ben-Israel A., Greville T.N.E. Generalized Inverses: Theory and Applications. New York: Wiley-Interscience, 1974.

3. Rao T.M., Subramanian K., Krishnamurthy E.V. Residue arithmetic algorithms for exact computation of д-inverses of matrices // SIAM J. Numer. Anal. 1976. V. 13. P. 155-171.

4. Грегори P.Т., Кришнамурти E.B. Безошибочные вычисления. Методы и приложения. М.: Мир, 1988.

5. Boullion T.L., Odell P.L. Generalized Inverse Matrices. New York: Wiley-Interscience, 1971.

6. Greville T.N.E. Some applications of the pseudoinverse of a matrix // SIAM Review. I960. V. 2. P. 15-22.

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

8. Икрамов Х.Д., Матин фар М. О компьютерно-алгебраических процедурах для псевдообращения матриц // ЖВМ и МФ. 2003. Т. 43, N2. С. 163-168.

9. Лоусон Ч., Хенсон Р. Численное решение задач метода наименьших квадратов. М.: Наука, 1986.

10. Воеводин В.В., Кузнецов Ю.А. Матрицы и вычисления. М.: Наука, 1984.

11. Khoury R.N. Closest matrices in the space of generalized doubly stochastic matrices //J. Math. Anal. Appl. 1998. V. 222, N 2. P. 562-568.

12. Икрамов Х.Д., Матин фар M. Одноранговые модификации и пересчет псевдообратных матриц // Вести. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2002. N4. С. 12-17.

13. Икрамов Х.Д., Матин фар М. Пересчет нормальных псевдорешений при одноранговых модификациях матрицы // ЖВМ и МФ.2003. Т.43. N4. С.493-505.

14. Икрамов Х.Д., Матин фар М. О компьютерно-алгебраических процедурах для линейной задачи наименьших квадратов с линейными связями // ЖВМ и МФ. 2004. Т. 44. N2. С. 206-212

15. Икрамов Х.Д., Матин фар М. О компьютерно-алгебраической реализации метода наименьших квадратов на неотрицательном ортанте // Зап. научн. сем. ПОМИ. 2004. Т. 309.

16. Каханер Д., Молер К., Нэш С. Численные методы и программное обеспечение. М.: Мир, 1998.

17. Campbell S.L., Meyer C.D. Generalized inverses of linear transformations. London: Pitman, 1979.

18. Zhou J., Zhu Y., Li X.R., You Z. Variants of the Greville formula with applications to exact recursive least squares // SIAM J. Matrix Anal. Appl. 2002. V. 24, N 1. P. 150-164.

19. Wilkinson J.H. Note on the practical significance of the Drazin inverse. Nat. Physics Lab. Report, 1979, N 13.

20. Campbell S.L., Meyer C.D., Rose N.J. Applications of the Drazin inverse to linear systems of differential equations // SIAM J. Appl. Math. 1976. 31. P. 411-425.

21. Wang G. The reverse order law for the Drazin inverses of multiple matrix products // Linear Algebra Appl. 2002. V. 348. P. 265-272.

22. Икрамов Х.Д. Задачник по линейной алгебре. М.: Наука, 1975.

23. Кублановская В.Н. Об одном способе решения полной проблемы собственных значений вырожденной матрицы // Журнал вычисл. матем. и матем. физ. 1966. Т. 6. N 4. С. 611-620.

24. Икрамов Х.Д, Савельева Н.В. Коположительные матрицы // Журнал вычисл. матем.и матем. физ. 1999. Т. 39. N8. С. 1253-1279.

25. Ikramov Kh.D., Savel'eva N.V. Conditionally definite matrices // J.Math. Sci. 2000. V. 98. N1. P. 1-50.