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

На правах рукописи

ЕРОХИН Владимир Иванович

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

ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Специальность 05.13.17 — теоретические основы информатики

АВТОРЕФЕРАТ

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

Работа выполнена в отделе Имитационных систем Вычислительного центра им. A.A. Дородницына РАН

Научный консультант:

доктор физико-математических наук, профессор ГОРЕЛИК В.А.

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

доктор физико-математических наук, профессор ВАСИЛЬЕВ Ф.П.

доктор физико-математических наук, профессор ТОКАРЕВ В.В.

доктор физико-математических наук, профессор ЦУРКОВ В.И.

Ведущая организация: Институт математики и механики УрО РАН

Защита состоится 16 февраля 2006 г. в (Y- ^ч. на заседании Диссертационного совета Д 002.017.02 по защите диссертаций на соискание ученой степени доктора физико-математических наук в Вычислительном центре им. A.A. Дородницына РАН по адресу: 119991, Москва, ул. Вавилова, д. 40, конференц-зал.

С диссертацией можно ознакомиться в библиотеке ВЦ РАН.

Автореферат разослан " Х^ 200*^г.

Ученый секретарь Диссертационного совета

РЯЗАНОВ В.В.

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

Актуальность проблемы. Формальной основой описательных или оптимизационных линейных моделей являются, как известно, системы линейных алгебраических уравнений (СЛАУ) и задачи линейного программирования (ЛП). Указанные линейные модели широко распространены и имеют многочисленные приложения в самых различных областях, причем могут быть использованы либо непосредственно (когда исследуемые с их помощью процессы или объекты являются линейными) либо опосредовано, в процессе линеаризации нелинейных моделей.

Исследуемые в диссертации СЛАУ являются несовместными, а задачи ЛП -несобственными. Роль и место подобных моделей, а также актуальность их исследования, хорошо обозначены академиком И.И. Ереминым: "В теории тех или иных классов задач (математических моделей) прослеживается эволюция в сторону ослабления требований, накладываемых на исследуемый математический объект. Эволюция, по большому счету, определялась давлением со стороны возникающих прикладных задач в той или иной предметной области. Приведем схему:

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

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

дем называть подобную коррекцию матричной, а соответствующие задачи - задачами матричной коррекции несовместных СЛАУ и несобственных задач ЛП.

Матричная коррекция несовместных СЛАУ, как научное направление, изначально развивалась в связи с важной и широко распространенной прикладной проблемой - задачей обработки экспериментальных данных с помощью так называемого обобщенного метода наименьших квадратов — Total Least Squares (TLS). Таким образом, TLS является обобщением классического метода наименьших квадратов (МНК) на случай, когда шум присутствует в наблюдениях как зависимых, так и независимых переменных, и может рассматриваться, как метод матричной коррекции несовместных СЛАУ по минимуму евклидовой нормы. Если принять гипотезу, что погрешности всех переменных имеют нормальное распределение с нулевым средним значением и одной и той же дисперсией, то TLS получает статистическое обоснование как метод, дающий оценки неизвестных параметров линейной модели, гарантирующие максимум функции правдоподобия.

Как свидетельствуют обзоры и популярные статьи, посвященные TLS, интенсивные исследования метода и его активное использование при решении прикладных задач начались в конце 80-х годов (XX в.). В настоящее время TLS достаточно хорошо изучен теоретически, его практическое использование доведено до уровня технологии, ведутся интенсивные исследования (в основном, зарубежные) по обобщению и расширению TLS как на новые виды задач (например, на задачи матричной коррекции несовместных СЛАУ специального вида — с матрицами Ганкеля, Теплица, Вандермонда и пр.), так и на использование отличных от евклидовой матричных норм (например, чебышевской и октаэдрической). При этом, однако, следует отметить две до конца не разрешенные проблемы. Во-первых, в отличие от классического МНК, задача TLS не всегда имеет решение, т.е., может быть несобственной. Указанный случай, получивший название Nongeneric TLS, изучен значительно слабее регулярного случая, причем складывается впечатление, что среди специалистов, занимающихся прикладными исследованиями, бытует недооценка проблемы Non-generic TLS, сходная, например, с встречавшейся когда-то недооценкой проблемы вырожденности и зацикливания в симплекс-методе. Во-вторых, несмотря на определенные успехи в использовании матричных норм, отличных от евклидовой, в матричной коррекции СЛАУ со специальной структурой, до сих пор в строгой постановке не решены соответствующие задачи матричной коррекции систем общего вида.

Как известно, систематические исследования несобственных задач линейного и выпуклого программирования (с введением соответствующей терминологии) были начаты 80-х годах (XX в.) И.И. Еремиными, его учениками и коллегами. В работах, выполненных Н.Н. Астафьевым, А.А. Ватолиным, Вл. Д. Мазуровым, Л.Д. Поповым, В.Д. Скариным, С.П. Трофимовым, В.Н. Фроловым и другими, рассматриваются несобственные задачи линейного и выпуклого программирования, проводится классификация, строится и исследуется теория двойственности, вводятся и исследуются дискретные аппроксимации решений — комитетные конструкции, предлагаются различные постановки и методы решения задач полной или частичной (правая часть системы уравнений или неравенств) параметрической коррекции и их содержательная (в основном, экономическая) интерпретация. При этом в большинстве

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

Матричная коррекция впервые была рассмотрена в работах A.A. Ватолина. В частности, им были рассмотрены задачи: 1\ — задача коррекции расширенной матрицы коэффициентов несовместной СЛАУ по минимуму евклидовой нормы; V,' — модификация задачи \\ с запретом на коррекцию отдельных столбцов матрицы коэффициентов исследуемой системы; V" — модификация задачи Vx с взвешенной с помощью левого и правого умножения на невырожденные матрицы евклидовой нормой и дополнительным ограничением в виде системы линейных неравенств, У2 — задача коррекции всех коэффициентов двойственной пары задач ЛП в стандартной форме по минимуму евклидовой нормы, V3 — задача коррекции всех коэффициентов смешанной системы линейных уравнений и неравенств по минимуму аддитивной матричной нормы с ограничениями в виде условий принадлежности множеств решений скорректированной системы и множеств оптимальных матриц коррекции заданным линейным подпространствам.

Для задач ,V2 были получены: значение нижней грани квадрата евкли-

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

Для задачи V3 A.A. Ватолиным было показано, что она сводится к конечному набору задач ЛП с использованием полиэдральных матричных норм в роли показателей качества коррекции. При этом необходимые условия существования решения, условия единственности решения и вид множества решений скорректированной линейной системы (задачи ЛП) для указанных задач также остались не исследованы. Заметим, что математический инструментарий, использованный при исследовании указанных выше задач матричной коррекции, не был унифицированным: для задач Vl, V' была использована лемма А.Н. Тихонова о решении с минимальной евклидовой нормой СЛАУ относительно неизвестной матрицы, для задач V" и \\ кроме упомянутой выше леммы А.Н. Тихонова привлекались фундаментальные свойства систем линейных неравенств, задача И, была исследована с использованием фундаментальных свойств систем линейных неравенств и геометрических свойств полиэдральных матричных норм.

Исследования A.A. Ватолина в конце 90-х годов (XX в.) были продолжены в ВЦ им. A.A. Дородницына РАН и МПГУ В.А. Гореликом и его учениками: В.А. Кондратьевой, О.В. Муравьевой, P.P. Ибатуллиным, Р.В. Печенкиным и другими. Указанными авторами с использованием леммы А.Н. Тихонова, свойств евклидовой нормы и методов математического анализа были уточнены некоторые результаты A.A. Ватолина (в частности, для задач Vt, V были получены необходимые и доста-

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

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

Следующий класс проблем связан как с требованиями возможных приложений, так и с внутренней логикой математического исследования проблем оптимальной матричной коррекции линейных моделей. Применим приведенную выше схему из цитаты И.И Еремина к самим задачам матричной коррекции. Очевидно, что потребностям практики в наибольшей степени отвечает ситуация, когда задача коррекции имеет единственное решение — единственную оптимальную матрицу коррекции, причем это решение является устойчивым. Также очевидно, что высокую ценность в контексте некоторой прикладной задачи может представлять единственность и устойчивость решения самой скорректированной линейной модели. Итак, мы описали задачу матричной коррекции, решение которой обладает идеальными свойствами. К сожалению, на практике возможны и другие ситуации: неустойчивость решения задачи матричной коррекции, не единственность оптимальной матрицы коррекции, не единственность решения скорректированной линейной модели, отсутствие решения (несобственность) задачи оптимальной матричной коррекции. Следует признать, что несмотря на отдельные результаты, полученные, например, для 1Моп£епепс ТЬБ, систематизированное исследование указанных проблем и путей их преодоления в настоящее время отсутствует.

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

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

Все вышесказанное и обуславливает актуальность данного диссертационного исследования.

Объектом исследования является теория несовместных систем линейных алгебраических уравнений и несобственных задач линейного программирования.

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

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

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

Научная новизна. Впервые с единых позиций, обеспеченных использованием критериев качества коррекции в виде обобщенных матричных норм и представлением задач ЛП в канонической форме, исследованы задачи матричной коррекции несовместных СЛАУ и несобственных задач ЛП. Построена теория указанных задач (включающая в себя необходимые и достаточные условия существования решений задач матричной коррекции, достаточные условия единственности указанных решений, вид оптимальных матриц коррекции и множеств решений скорректированных систем, достаточные условия ограниченности множеств решений скорректированных систем, априорные оценки норм оптимальных матриц коррекции, формы сведения задач матричной коррекции к известным задачам линейной алгебры и математического программирования и пр.), а также эффективные численные алгоритмы их решения. Даны примеры практического использования указанных результатов при решении ряда прикладных задач: исследовании условий регулярности интервальных матриц, коррекции матричной игры, коррекции непродуктивной матрицы Леонтьева, оценивании параметров временного ряда. В числе наиболее важных теоретических результатов, характеризующих новизну работы, назовем следующие: - Впервые показано, что, для преодоления возможной некорректности или несобственности задач матричной коррекции несовместных СЛАУ кроме подхода, предложенного для Nongeneric ТЬБ и регуляризации по Тихонову, можно фиксировать (ос-

вобождать от коррекции) отдельные столбцы матрицы (или расширенной матрицы) коэффициентов исследуемой системы.

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

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

- Получены неизвестные ранее обобщения на широкий класс аддитивных матричных норм леммы А.Н. Тихонова о решении с минимальной евклидовой нормой СЛАУ относительно неизвестной матрицы; необходимые и достаточные условия невырожденности интервальных матриц специального вида (и возможность проверки указанных условий за полиномиальное время); нижняя оценка нижней грани ||-||

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

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

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

Концепция заключается в едином подходе к проблемам коррекции как несовместных СЛАУ так и несобственных задач ЛП в канонической форме, базирующимся на широком использовании математического аппарата линейной алгебры: фундаментальных свойств псевдообратных матриц, евклидовой матричной нормы, аддитивных матричных норм и обобщениях на широкий класс аддитивных матричных норм леммы А.Н. Тихонова о решении СЛАУ относительно неизвестной матрицы с минимальной евклидовой нормой.

Внедрение и апробация результатов исследования. Основные результаты, полученные в диссертации, докладывались на Международной конференции "Математика. Образование. Экология. Тендерные проблемы" (Воронеж, 2000 г.), XII Байкальской международной конференции "Методы оптимизации и их приложения" (Иркутск, 2001 г.), XIII Байкальской международной школе-семинаре "Методы оптимизации и их приложения" (Иркутск, 2005 г.), Международной конференции "Некорректные и обратные задачи" (Новосибирск, 2002 г.), Международной научно-технической конференции "Методы и средства измерения в системах контроля и управления" (Пенза, 2002 г.), 4-й Московской международной конференции по исследованию операций (ORM2004) (Москва, 2004 г.), Международной конференции по вычислительной математике МКВМ-2004 (Новосибирск, 2004 г.), Международной конференции "Дискретный анализ и исследование операций (DAOR-2000) (Новосибирск, 2000 г.), Российской конференции "Дискретный анализ и исследование операций (DAOR'02, DAOR'04)" (Новосибирск, 2002, 2004 гг.), Всероссийской конференции "Математическое программирование и приложения" (Екатеринбург, 2003 г.), Всероссийской конференции "Алгоритмический анализ неустойчивых задач" (Екатеринбург, 2004 г.), 1-й Московской конференции "Декомпозиционные методы в математическом моделировании" (Москва, 2001 г.), 2-й Московской конференции "Декомпозиционные методы в математическом моделировании и информатике" (Москва, 2004 г.), Воронежском зимнем симпозиуме "Математическое моделирование в естественных и гуманитарных науках" (Воронеж, 2000 г.), научном семинаре по исследованию операций ВЦ им. А.А. Дородницына РАН, научном семинаре отдела Имитационных систем ВЦ им. А.А. Дородницына РАН, научных конференциях преподавателей и сотрудников Борисоглебского гос. пед. института, научных семинарах каф. прикладной математики и информатики Борисоглебского гос. пед. института.

Основные результаты диссертации опубликованы в 20 печатных работах, в том числе — одной монографии.

Результаты диссертационной работы вошли в состав проекта «Исследование и оптимизация сложных управляемых систем при нечетких или некорректных данных» (поддержан ФАП, 2005 г., рук. проф. Тараканов А.Ф., исполнители Ерохин В.И, Тараканов А.Ф.) и в тематику НИР Отдела Имитационных систем ВЦ РАН (в рамках Программы поддержки ведущих научных школ НШ —2094.2003.1).

Струюура и объем работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы и приложений. Общий объем работы — 346 м.п.с., напечатанных в текстовом редакторе Microsoft Word. Библиография содержит 238 названий. Работа содержит 15 рисунков и 11 таблиц.

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

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

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

Ах — b, (1)

и та же система, дополненная условием неотрицательности

Ах = Ь, х £ 0, (2)

где А е R""", хеМ", АеК", rank А = г и соотношения между параметрами т, п, г произвольные. Практически во всей работе (кроме параграфа 5 главы 4) предполагается также условие Ь* 0. Обозначим через Х(А,Ь) = Ах е ¿>| и ЛГ+(А,Ь) = Ах = b, х £ о|

множества решений систем (1) и (2). Тогда основные предположения, связанные с системами (1) и (2), можно записать как Х(А,Ь) = 0, Х+(А,Ь) = 0.

Второй и третий параграфы содержат некоторые сведения из линейной алгебры, такие, как сингулярное разложение, задача аппроксимации некоторой матрицы матрицей меньшего ранга, псевдообращение и его использование для построения ортогональных проекций и нахождения нормальных псевдорешений возможно несовместных СЛАУ, лемма Тихонова о решении с минимальной евклидовой нормой СЛАУ относительно неизвестной матрицы. Указанные сведения составляют, наряду с методом множителей Лагранжа, основу используемого в первой главе математического аппарата. Поскольку псевдообращение матриц и векторов (которые в указанном контексте рассматриваются как матрицы, состоящие из одного столбца) широко используется как в самой диссертационной работе, так и в приводимых ниже формулах, поясним, что псевдообратной (обобщенной обратной по Муру-Пенроузу) матрицей к некоторой матрице ЛеМ""" считаем матрицу /еЕ""", удовлетворяющую уравнениям Пенроуза: А А* А = А, А*АА* = А*,

(аа+)т = аа+ и (а+аУ=а+а.

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

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

(3)

(4)

£}[!]): ||[Я -к]

inf

(гл+н

zmstvm){^ т и • d

inf

fl"л+н sir6T\

f_ (\л 51 NYl

I ~ Zy!x{S.r,C/.Wil Г и ■ d 111

где S € R""*, Т е R/x", и е R'*\rf е R'.

Начинается исследование с базовых задач Z^Ub): ||[Я -А] ZMt}(A,b): ||Я||£ -

(5)

(6)

где ||-[|£ - евклидова матричная норма, Я = (й9.) е R"x" - некоторая матрица, A = (А,) е R"

- некоторый вектор.

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

и т.д. Пусть ¿^(Q) - минимальное собственное значение вещественной симметричной матрицы Q, Х^ (Q) - множество нормированных собственных векторов матрицы Q, соответствующих Л^ (Q), I - единичная матрица.

Теорема 1. Для оптимального значения целевой функции в задаче (5) справедлива формула zw (A,b) = -aJ [a -¿jj. Задача (5) имеет решение тогда и

только тогда, когда существует вектор у е Xmin -¿J [a -а]| такой, что * 0. При этом [я* -А*] = [-Л а]. * • * 6 7{(гшЫ(А,Ь)) и Х{А + H\b + h') = x , где

= — Гд'Г - • 1 J

Следствие. Если rank А < п то задача (5) не имеет решения. Теорема 2. Для оптимального значения целевой функции в задаче (6) справедлива формула zfa{b) (A,b) = (Ат(/ -ЬЬ*)А). Задача (6) имеет решение тогда и только тогда, когда существует вектор у е Xmin (Ат(1 - ЬЬ*)А) такой, что bTAy * 0.

При этом Я* = (А- Ах') jc*+ е H{ZMb) (А,Ь)) и Х(А + Я*,б) = х', где х* = ■ у.

Следствие. Если rank А < п то задача (6) не имеет решения. Пусть Tx = d, где Т е R/x", d е R' - некоторая совместная подсистема линейных алгебраических уравнений, S е R""*, R- I - SS*, А = RA, А = Rb. Рассмотрим задачи

Ш

'fix{T,b.c

ГРЧ PI)

.<0^ t ■ d j

[H -h]

me

fr.JirL™ - Zfi'\T4\ ( т • ä JJ.

IMi'JJ

inf

1. ' л-.Г

(9) (10)

Задача (7) ранее рассматривалась A.A. Ватолиным. Для нее были получены: значение нижней грани квадрата евклидовой нормы матрицы коррекции, достаточные условия существования решения, вид оптимальной матрицы коррекции и вид вектора х - решения скорректированной системы. В диссертации удалось уточнить условия существования решения и придать им форму необходимых и достаточных условий. Удалось также уточнить вид множества решений скорректированной системы, т.е., получить параметрическое представление вектора х'. Задача (8) ранее не рассматривалась. Для нее получены: значение нижней грани квадрата евклидовой нормы матрицы коррекции, необходимые и достаточные условия существования решения, вид оптимальной матрицы коррекции и параметрическое представление вектора - решения скорректированной линейной системы.

Теорема 3. Для оптимального значения целевой функции в задаче (7) справедлива формула zMS) ^ = 2*>«л • Задача (7) имеет решение тогда и только тогда, когда имеет решение задача 2,оЫ (Дб). При этом если [И' -Ä'jeWjz^l^")) и X(Ä + H',b + h') = x\, то

[Я* -Л*] = [/Г -h*]z?i(zMS)§A s],6)),Af([/l + tf' S],6 + A*)=

где x's = S*(b- Лх'А) + (I - S*S)*xs, *xs e R* - произвольный вектор.

Теорема 4. Для огтгимального значения целевой функции в задаче (8) справедлива формула zßl{Si} ([^ = z/ix{i) (Дй). Задача (8) имеет решение тогда и

только тогда, когда имеет решение задача Zfix{B){Ä,b}. При этом если

Й' e7i(zM6}(Ä,b)) и Х(А + Й',Ь) = х\, то Я* =Й' <=?i(zMSib}([A

xi^A + H* S],*>) =

где x's = S*(b - Ax'4) + (/ - S*S)bXs, £,xs e К* - произвольный

вектор.

Заметим, что если ранг матрицы составленной из некорректируемых столбцов, меньше числа ее столбцов к, то решение скорректированной системы в задачах (7) и (8) не единственно.

Задачи (9) и (10) ранее рассматривались в работах В.А. Горелика, В.А. Кондратьевой и О.В. Муравьевой. Тем не менее, немого видоизменив технику исследования (в частности, детально рассмотрев частные случаи, связанные с возможным видом множества решений подсистемы Тх = <1), удалось получить новые и не казавшиеся ранее очевидными результаты. Самый важный из них - задачи (9) и (10) не имеют решения в наиболее интересном случае — тогда, когда решение подсистемы

Тх = Ы не единственно. Для того, чтобы в указанном случае задачи (9) и (10) все же имели решение, необходимо присутствие дополнительных условий, делающих возможную область допустимых решений скорректированной системы ограниченной. Заметим, что в роли условий, обеспечивающих ограниченность допустимой области, может (но не обязательно будет) выступать условие неотрицательности вектора х, естественным образом возникающее, например, в постановке задачи матричной коррекции допустимой области несобственной задачи ЛП в канонической форме. Теорема 5. При решении задачи (3) возможны только следующие 4 случая: а) Выполнены условия Р = 0, 0 = 0. В этом случае

~л 5"

т и а

=

,(а,В).

Для того, чтобы задача имела решение необходимо и достаточно, чтобы имела решение задача При этом если [я* -Л*]е П^г^^ь)),

Х{А + Й',В + И') = х'А,то(В- Лх'А)-

b) Выполнены условия Р = 0, £? * 0 и (или) выполнены условия РТ = 0, РЫ = 0, . В этом случае

Для того, чтобы задача имела решение необходимо и достаточно, чтобы имела решение задачаг^ . При этом если -Л*^ е (Д и

Х(А + Й\В +И') = х'А, то

- »-|+

(I-!*;)■ х* =[я* £].[!]))•

c) Выполнены условия Р * 0, £? = 0, РГ = 0, А* = 0. В этом случае

;шение необходимо и

решение задача 1ша1 (Дб). При этом если -А*^ е (Д^))

- «-)+

х(Я + й\В + й*) = то (I - Щ ■ = [я* -л*] € н\гМ5хи^ [р у].

Для того, чтобы задача имела решение необходимо и достаточно, чтобы имела

и

с!) Выполнены условия Р * 0, о, РГ ф о, /У * 0. В этом случае

2Ми.т.и</} (р у]'р]) ~ 2МтА | При этом для того, чтобы задача имела решение необходимо и достаточно, чтобы

имела решение задача [я" -Л"] = (А,Ь)). При этом если

МТ4)

А ь )М

f 3 т 3

то

Если задача (3) имеет решение — некоторую оптимальную матрицу коррекции -Л*], то множество решений скорректированной системы можно охарактери-

зовать формулой X

/ ~а + н' б' ~ь + а'" 1

V т и 1 а Г

, где вид вектора хл в зависимости от

совокупности условий (а), (Ь), (с) или (с1), указан выше, а вид вектора х'3 является следующим:

(а) х;=и-1{с1-тхлу, (Ь),(<1) = где

ХБ е К* - произвольный вектор; (с) дг* = и*(Л- Тх\).

Результаты, аналогичные теореме 6, удалось получить и для задачи (4). Схема редукций рассмотренных задач матричной коррекции, в рамках которой решение более сложных задач сводится к решению менее сложных, образуя "модульную систему" методов (и возможных алгоритмов), представлена на рисунке 1.

Рис.1. Схема редукций задач матричной коррекции несовместных СЛАУ по

минимуму евклидовой нормы

Пятый параграф посвящен более детальному исследованию задач (5) и (6). Учитывая схему, представленную на рис.1, подобное дополнительное исследование представляется оправданным. Результатами его стали: альтернативные формулировки необходимых и достаточных условий существования решения задач (5) и (6), необходимые и достаточные условия единственности решения указанных задач и формулы, характеризующие решение задачи об "аналоге нормального решения" на множестве решений скорректированной СЛАУ. Также получены утверждения, характеризующих только необходимые или только достаточные условия существования решения задач (5) и (6) и неравенства, связывающие нормы оптимальных матриц коррекции с нормами невязок метода наименьших квадратов.

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

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

\.А \.А ~Ь~1 и АТ(1-ЬЬ*)А, и, с использованием упомянутых выше

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

Случай не единственности оптимальной матрицы коррекции интересен тем, что в зависимости от выбора указанной матрицы можно получать разные решения скорректированной СЛАУ, различающиеся, в частности, величиной евклидовой нормы. В частности, как удалось показать, возможен такой выбор корректирующей матрицы (обладающей минимальной евклидовой нормой), при котором норма вектора х* - решения скорректированной системы становится бесконечной. Если в этой ситуации главный интерес представляет именно решение скорректированной системы, приходится признать, что задача его нахождения является неустойчивой (некорректной). Одним из выходов может быть поиск и построение такой оптимальной матрицы коррекции, которая обеспечивала бы минимальность евклидовой нормы вектора - решения скорректированной системы. Указанные задачи, являющиеся расширениями задач (5) и (6), названы в настоящей работе задачами матричной коррекции с нахождением аналога нормального псевдорешения исследуемой несовместной СЛАУ. В рамках их исследования установлена единственность их решения и получены связанные между собой параметрические представления оптимальных матриц коррекции и однозначно соответствующих им векторов решений скорректированных систем. Указанные параметрические представления основаны на наборах собственных векторов матрицы

\.А ~Ь~\ \.А [задача (ЭД или матрицы АТ (/ - ЬЬ*)А [задача (6)] и позволяют

строить матрицы коррекции, обеспечивающие любое заданное значение евклидовой нормы вектора х' - решения скорректированной системы, изменяющееся в диапазоне от минимального значения до бесконечности. Кроме того, получены интересные результаты, характеризующие взаимосвязь задач матричной коррекции несовместных СЛАУ по минимуму евклидовой нормы с методом наименьших квадратов. Точнее, удалось показать связь рассмотренных задач матричной коррекции с нахождением аналога нормального псевдорешения с задачей нахождения нормального псевдорешения в классической постановке. Выяснилось, что указанные задачи матричной коррекции эквивалентны задаче х" = ах§ ппп — дг* (а)|, где х - нормальное псевдорешение исследуемой

г"(ак где а =1

несовместной системы, х' (а) - решение скорректированной с помощью оптимальной, параметризованной вектором а матрицы коррекции Н или [Н -И].

В шестом параграфе модифицируется критерий оптимальности задач

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

Рассмотрим задачи:

(Л-Ь) : о ни = и*)Ь

где = > 0) - весовая матрица с размерами тх(п +1), как у матрицы ,

или с размерами тхп, как у матрицы Я, знак "о" означает поэлементное перемножение матриц (произведение Адамара).

Лемма 1. Задачи г™«,/(А, 6) и г^х{ь](А,Ь) эквивалентны задаче

||<Каё(ю)Щ т|: (= г 1, (А,Ь) или г*,*, (А,Ь)), (11)

где

со =

,,■..,я+1,w21,...,.... ч*.,,...,я+1 ]Т6 ЕГ<"+|) для задачи (А,Ь),

К"" для задачи г%т(А,Ь),

"V ']

ХСх) = {

о

'К .'Г-

о

О ' [хт |]

хТ О

О V

••• О

О " хт

6 цг*"<"+,> дм задачи (А,Ь),

" " для задачи 2^[ь] (А,Ь),

Пусть

[К..• • •,-Л,.л+1 Ли-,-Ьж,• • •,Ли,,• • •,-Лмл+1 ]Те К-(я+,) для задачи г™ш1 (А,Ь),

для задачи ( а,ь).

г (х) = [г, (*),...,/•„ (д)]т= Ь-Ах, Х(дс) = Х(х) • (^авС®))-1, /(х) = гт(*)Х+т(х);Г+(*)/-(;с). Опираясь на лемму 1, можно показать, что

о/(дг) Ы(= (гГиДЬ))2), 21{ь](А,Ь) «/(*) т0г(= Пусть Л = (сг&) и для £ = 1,2,...,/я

1 ^ дг,2

+ X —2~ д™ задачи (А,Ь),

ы w«

длязaдaчиZ^{4}(Л,¿)•

<=l ^ке

Лемма 2. Для частных производных функции /(*), порождаемой задачами 2,1/(л. ¿0 и (а,д), справедливы формулы

дх1

т

-2-1

*=1

' *Л2(*) , гк{х)а^

, / = 1,2,...,я,

д2/(х)

т

= Х

ЙХ/ *=1

дх1дх)

(8х?г?(х) 8х1гк(х)аи - 2гЛ*) 2*П

/ = 1,2,..., л; у = 1,2,..., и; / * у.

Если х'еАг^т {/(*)}, то соответствующие решения задач г^и,(А,Ь) и г%{ь}(а,ь) - матрицы [я* -А*] и н* могут быть восстановлены по вектору

й* = (сИа§(е>))~' -(Х(х*)У-г(х'), являющемуся решением задачи (11). При этом х'еЛ:(а + н\ь + н*) или x*&х{а + н\ь).

В качестве следствий из теорем 1 и 2 можно вывести достаточные условия единственности решения скорректированной системы в задачах (а,ь) и г%х{ь) (а,ь): при существовании решения задачи (5) в задаче (а,ь) справедливо условие х(а + Н*,Ь+И') = х* , при существовании решения задачи (6) в задаче справедливо условие х[а + н\ь) = х*.

В седьмом параграфе рассматриваются несобственные задачи вида (5) и (6). Заметим, что в указанных задачах мы имеем дело с несобственностью как бы "более высокого порядка": Исходный объект — СЛАУ — оказывается несовместной, а задача ее оптимальной коррекции - несобственной. Начинается параграф с исследования решения задач (5) и (6) с помощью метода, за которым в зарубежных исследованиях закрепилось название "Ыог^епепс ТЬБ". Удается показать, что "Ыогщепепс ТЬБ" -

решения задач (5) и (6) в общем случае не обладают свойством единственности, причем не единственными оказываются к сами оптимальные матрицы коррекции, так и соответствующие им векторы х* - решения скорректированных систем. Приводится также пример "патологического" поведения Моп§епепс ТЬБ на задачах (5) и (6) при коррекции несовместной СЛАУ, вектор правой части которой ортогонален всем столбцам матрицы коэффициентов. Показано, что в рассматриваемом случае Иог^епепс ТЬБ и его дальнейшие модификации не позволяют решить задачу (6) а для задачи (5) коррекция с помощью Ког^епепс ТЪБ и его дальнейших модификаций делает исследуемую систему однородной (не затрагивая при этом матрицу коэффициентов), что может быть неоправданным в контексте некоторой прикладной задачи.

Следующим вопросом, исследованным в данном параграфе, является связь Коп^епепс ТЬБ с регуляризованным по Тихонову обобщенным методом наименьших квадратов. В работе удалось показать, что решения задач (5) и (6), полученные с помощью Ыоп£епепс ТЬБ (если они существуют), могут быть получены как решения задач

«"(■о): - --К'ЧАЧ), (13)

при соответствующем выборе регуляризующего параметра £>0. Таким образом, регуляризованный по Тихонову обобщенный метод наименьших квадратов и его модификация, в которой корректируется только левая часть исследуемой системы, являются более общим методом, чем >1оп£епепс ТЬБ. В качестве замечаний в работе приведены утверждения о том, что при замене условия \\х\\ $<5 в задачах (12), (13) на условие ||1х|| ^ 3 для достаточно широкого класса регуляризующих матриц Ь решения задач (5) и (6), полученные с помощью Моп£епепс ТЬБ (при условии их существования), могут быть по-прежнему (при соответствующем выборе параметра >0) получены как решения задач (12), (13).

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

Глава состоит из шести параграфов. Большая часть материала главы (§§ 1-4) фактически посвящена задачам матричной коррекции несовместных СЛАУ с условием неотрицательности решения, хотя общий круг рассматриваемых в главе вопросов достаточно широк, и затрагивает, в частности, проблемы коррекции несовместных систем линейных неравенств и несобственных задач ЛП в различных формах (§ 5) и наиболее общую (по своей постановке) проблему матричной коррекции несобственной задачи ЛП в общей форме с произвольными фиксированными (некорректируемыми) коэффициентами по минимуму взвешенной с произвольными индивидуальными положительными весами евклидовой нормы.

Основное внимание уделено задачам матричной коррекции несовместных СЛАУ с условием неотрицательности не случайно. Во-первых, указанные задачи на начальном уровне могут быть исследованы алгебраическими методами, рассмотренными в первой главе. Затем, разумеется, требуется привлечение методов матема-

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

Во-вторых, исследуемые несовместные системы тесно связаны с несобственными задачами ЛП 1 -го и 3-го рода в канонической форме, а также с двойственными к ним (по своей формальной постановке) несобственными задачами ЛП 2-го рода в основной форме. Приведем простые примеры. Так, пустая допустимая область несобственных задач ЛП 1 -го и 3-го рода в канонической форме и пустая допустимая область двойственной задачи для несобственной задачи ЛП в основной форме формально задается несовместной СЛАУ с условием неотрицательности решения. Кроме того, собственную или несобственную задачу ЛП в канонической форме можно свести к указанной несовместной системе, задав в виде дополнительного ограничения - равенства условие достижения целевой функцией некоторого директивного значения (недостижимого в исследуемой собственной задаче ЛП).

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

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

(Л*) : |Ь[Н -Л>[£ -> Х (А}п1и)^ (А,Ь)), (14)

См"*"'" иь) : \\ит\\Е -> х Мь)г0{= к?-^' (А,Ь)), (15)

где ¿еГ<я - некоторая невырожденная матрица, - невырожден-

ная матрица, такая Я = К"1 = (15 ^ 0) (например, диагональная матрица с положительными элементами), и >0)еГх" - невырожденная матрица, такая 11 = Я-1 =(г;у >0)

(например, диагональная матрица с положительными элементами).

Для задач (14), (15) получены: необходимые и достаточные условия существования решения, вид оптимальных матриц коррекции, вид вектора х*, являющегося решением скорректированной системы. При этом сами задачи матричной коррекции сведены к задачам минимизации дробно-квадратичных функций с условием неотрицательности или квадратичных функций на единичной сфере с условием неотрицательности. Получены также достаточные условия, при выполнении которых допустимые области скорректированных систем а) содержат единственную точку; Ь) ограничены. Как несложно заметить, указанные условия являются также достаточными для собственности соответствующих изначальной несобственных задач ЛП 1-го и 3-го рода в канонической форме, а также изначально несобственных задач ЛП 2-го рода в основной форме.

Второй параграф также содержит результаты, являющиеся "мостиками" между задачами коррекции несовместных СЛАУ с условием неотрицательности и проблемами коррекции несобственных задач ЛП 1-го и 3-го рода в канонической фор-

ме. К указанным результатам относятся, во-первых, две леммы, устанавливающие ограниченность допустимых множеств, получаемых в результате решения задач (14) и (15) вдоль определенных лучей, выходящих из допустимой области:

Во-вторых (и это главный результат данного параграфа), доказаны две теоремы, устанавливающие достаточные условия собственности скорректированных изначально несобственных задач ЛП 1-го или 3-го рода:

{А + Н*)х = Ь + Ь\х-£0,с1х-*тзх{=?), (16)

(А + Н')х = Ь,х7>0,сТх^>тгх(=С*), (17)

Теорема 7. Если задача С^*"'*1""1 (А,Ь) имеет решение - некоторую матрицу

[я* -А*], а система (2) несовместна даже без учета условия х ^ 0, то задача ЛП вида

(16) является собственной.

Теорема 8. Если задача С^^1*1""1 (А,Ь) имеет решение — некоторую матрицу

Н', а система (2) несовместна даже без учета условия * £ 0, то задача ЛП вида (17) является собственной.

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

Для численного решения задачи минимизации отношения Рэлея с условием неотрицательности предложен алгоритм градиентного типа с точным решением вспомогательной задачи одномерного поиска вдоль заданного направления. Работа алгоритма проверялась в рамках решения задач матричной коррекции модельных несовместных СЛАУ с условием неотрицательности. В работе приводятся экспериментальные результаты, полученные при решении одной из таких задач. Они хорошо иллюстрируют два важных факта, выявленных при тестировании алгоритма: во-первых, сходимость алгоритма к точке останова (которой может быть любая точка локального минимума целевой функции и любая стационарная точка) как по аргументу, так и по целевой функции является сверхлинейной (возможно - квадратичной). Во-вторых, при случайном выборе стартовой точки достаточно велика вероятность сходимости алгоритма именно в точку глобального минимума даже при большом числе локальных минимумов.

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

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

Рассмотрим несовместную систему

Ахл+Бх$ = Ь, Тхл + их$=4 ,ха,х52:0. (18)

Ее подсистему Тхл+их<;=(1 ,хл,х5*::0 будем считать совместной. Свяжем с системой (18) задачи

Щ: [¿[Я -Л]К[- - '

4. г с').«

х.

inf

A+H S'

г U d

*0

- - -д-----[ I

*/«{S.r,£/.<i}l I Т

Л/ = [й -b]-SN,S = SQ, R =

' Пусть

[а = -¿>]Я,[Г -<?], 5 = ^5, () = 1-и+и, Ы = и*[Т -</],

г е К|х("+|)

Теорема 9. Пусть дана несовместная система (18). Тогда 1) Для оптимального значения целевой функции в задаче (

справедлива формула

\\Мг +

~A S~ "6"

T U d

veighled I

■Г,i\d) у

^LR-weighted

а S' Т U

= inf

l^O.qQqk.Vt

2) Задача С^'Й?

hud (

~A S~

T U d

решение z' е М"+|, q' е R* задача

имеет решение тогда и только тогда, когда имеет

, ч ЦЛ/2 + ^f

<p(z,q) = ^-L -» min, Qq ^Nz, zZ 0, rz > 0.

При этом

[//• -А'] = -¿-' (Mz' + Sq')z'+R l е П

r с 'А S~ ~b~ \

s~*LR- weighltd

fixiSTX> M\ T и > d

\ К - - - /

A + H S T U

b + h d

, где x4 =

yt

Уп-l

. . Qq-Nz ,y = Rz ,xs --

Теорема 10. Если задача (

'А 5"

т и а

связанная с некоторой несовме-

стной системой (18), имеет решение — некоторую матрицу [я* -Л*], то множество

А+Н' ь+и'

т и ¡1

ограничено по любому направлению дх =

такому, что

Алхл + = 0.

Для задачи

I Т и • Л I

удалось получить результаты, аналогичные

теоремам 9 и 10.

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

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

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

Пусть

с?х1 + с2х2 —> ¡пГ, А1 + А12х2 ^ ,

и Г:

6[ТИ, + ЬГ2и2 —» Бир, и?Ап +и]А2] >с,, и^Ап+и^А22=с2,

Щ>0,

А^ | А^ 2 = А = (а^ ), А с, = * = (*,), и\

А. = А = (4Х р2 = с = (суХ 1 Л. "2.

ется пустым. Пусть Н =

= [Я -А] = (^)е1Г'("*1) -

где Ап Д^Е"1^, А^ е , ^.с^Г, х^с^Г, ¿,еР, Ь2 е ,

м, е К™1, и2ей*! - пара взаимодвойственных задач ЛП, записанных в общей форме, причем /и, + т2 =т,пх + п2 =п,

А Л V» 1 11

= « = ("/)•

Обозначим допустимое множество задачи Ь как Хс(А,Ь) = {х}, а допустимое множество задачи V как Ыс{А,с) = {и). Задачи I и V предполагаются несобственными, поэтому первоначально хотя бы одно из множеств Х1(А,Ь) или Ыс (А,с) являли #12 #21 #22

некоторая матрица коррекции (отдельные элементы которой возможно являются нулевыми), т.е., такая матрица, что Х1(А + Н,Ь+И)*0, ис(А + Н,с)*0. Пусть

XV = (\Уц) е Е",х(я+1) - матрица, состоящая из произвольных положительных элементов. Рассмотрим задачи

г.ПЬУоН!!-» Ы (=£), г, :/(£,>>,г)-> Ы" (=£), где

И1.(А+Н,с)*0

~Ьх-у-АХ1х1-АХ2х2 Ьг - А21х1 - А22х2

. С2~АТ2и,-^2и2

8 =

>г(8,у,г) =

Ме) =

Х(х) и (и)

(й^Сю))'1.

Х(х) =

.] о -О [,т ,] ...

О [,т ,]]

бК"^, и(м) = [ы,./я+1

/»+1 = {К 6 К"х("+1), ^еЕ4, 2еК\ у,г^О, /„ - единичная матрица порядка п. Теорема 11. Пусть для пары несобственных задач ЛП рассматривается задача взвешенной матричной коррекции 2Х. Тогда

1) =С2. 2) Нижние грани целевых функций 2Х и 12 достигаются или не

достигаются одновременно. 3) Если =

уу',г' - оптимальное решение задачи 22,

то матрица н*=[я* -Л*], построенная по вектору

ь[ё\у\гт} = (<ааё(&)у1-С+ (г)-г(^,у,г), является оптимальным решением задачи причем дг* еЛТ£(л + Я\А+Л*} и и е Ц. (Л + Я*).

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

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

Третья глава содержит исследование задач матричной коррекции несовместных СЛАУ и несобственных задач ЛП с использованием показателей качества коррекции, основанных на достаточно широком классе обобщенных (аддитивных) матричных норм. Указанные нормы, следуя известной книге Р. Хорна и Ч. Джонсона, можно также назвать векторными нормами на множестве матриц.

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

Гёльдеровой нормой с показателем р > 1 для матрицы А е R"x" будем называть величину ЦлЦ, = Х2КГ * Взвешенную с помощью левого и правого умножения

на невырожденные матрицы || ||, -норму определим как ||л||" = ||1ЛЯ||, , где А е R"*" -произвольная матрица, ieR""", ЛеМ"*", rankL = m, rank fi = n. -нормой для матрицы AeR"*" будем называть величину ||л|| = max^^f*), где <р(-) и <//(•) - некоторые векторные нормы.

Заметим, что || ||, и ||" - нормы являются типичными представителями^адди-тивных матричных норм. ||-|| -норма в общем случае также является аддитивной.

\уТА

Функцию <р* (.у) = max -Цр—где jc,j>eR" - некоторые векторы, <р(Л - некоторая

<р\х) ,

векторная норма, будем называть векторной нормой, двойственной к норме <р(-) относительно скалярного произведения. Упорядоченную пару векторов дг^е!" будем называть двойственной парой по отношению к норме <р(-), если вектор у принадлежит множеству векторов, двойственных к х по отношению к норме <р{ ).

В первом параграфе выводятся формулы для построения вектора у, двойственного к заданному ненулевому вектору х относительно нормы |-|*р - векторной

нормы, двойственной к норме Гёльдера с показателем р. При 1 <р<+оо показана единственность вектора у. При р- 1,°о вектор у не является единственным и для него приведены соответствующие параметрические представления.

Главный результат второго параграфа - обобщение леммы А.Н. Тихонова о решении с минимальной евклидовой нормой СЛАУ относительно неизвестной матрицы на И" и ||-||^ -нормы:

Пусть дана система линейных алгебраических уравнений Ах = Ь, где А е К""" -неизвестная матрица, .хеМ" и 6eR" - заданные векторы, причем Требуется

найти матрицу А, являющуюся решением указанной системы и имеющую минимальную , 1Н1" или - норму.

Теорема 12. Матрица А = Ьут, где уеК" - вектор, двойственный к вектору х относительно нормы принадлежит к множеству матриц, являющихся решением

системы Ах = Ь при ;с*0 с минимальной ||| - нормой. При этом ||л|| =—г» где

И,

векторная норма Гёльдера с показателем р. При 1 < р < +оо матрица А является единственной.

Теорема 13. Матрица А = ЬутЯ'1, где у е К" - вектор, двойственный к вектору Я~хх относительно нормы ||-|£, принадлежит к множеству матриц, являющихся решением системы Ах = Ь при с минимальной ||-||" - нормой. При этом

||л||" = ^ [ .При 1 < р < +оо матрица А является единственной.

Теорема 14. Матрица А = Ьут, где - вектор, двойственный к вектору х

относительно нормы <р(-), принадлежит к множеству матриц, являющихся решением

системы Ах = Ь при лг*0 с минимальной | - нормой. При этом ||л|| = ^^ .

Замечание. При соответствующем выборе норм ?>(•) и матрицы, минимальные по || | или ||-||" - норме, принадлежат к множеству матриц, разрешающих систему Ах = Ь при ,х*0 и минимальных по ||| - норме.

Результаты, приводимые в теоремах 12-14, имеет принципиальное значение для всей третьей главы, так как с их помощью непосредственно решаются задачи матричной коррекции несовместных СЛАУ по минимуму некоторой ||-|" и ¡Ц^ -

нормы при заданном ненулевом векторе х. Заметим, что теоремы 12, 14 позволяют, в частности, прийти к результатам, полученным с помощью другой техники В.А. Гореликом, О.В. Муравьевой и автором данной диссертационной работы при исследовании коррекции несовместных СЛАУ по минимуму спектральной нормы. Так, оказывает возможным переформулировать лемму А.Н. Тихонова для спектральной нормы. При этом можно показать, что, во-первых, матрица, являющаяся решением СЛАУ с минимальной спектральной нормой - не единственна, т.е., можно говорить о множестве или семействе матриц. Во-вторых, указанное семейство матриц содержит одноранговую матрицу, являющуюся решением исследуемой системы и минимальную по евклидовой норме (т.е., матрицу, описываемую леммой А.Н. Тихонова).

Третий параграф посвящен исследованию задач матричной коррекции несовместных СЛАУ по минимуму Ц, , |||" и -норм, являющихся обобщениями задач вида (5) и (6). Для указанных задач с использованием полученного во втором параграфе обобщения леммы А.Н. Тихонова, найдены необходимые и достаточные условия существования решения, вид оптимальных матриц коррекции и множеств

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

В четвертом параграфе рассматриваются вопросы регуляризации решений изначально несовместных СЛАУ в процессе их матричной коррекции по минимуму |-| -нормы. Указанная проблема требует некоторых пояснений. Как было показано

в § 3, задачи оптимальной матричной коррекции сами могут быть несобственными или приближаться к таковым. На практике это означает, что решения скорректированных систем велики или неограниченны по норме. Подобная ситуация, возникающая в задачах матричной коррекции по минимуму евклидовой нормы, рассматривалась ранее в главе 2. Там были указаны некоторые методы ее преодоления — Коп§епепс ТЬБ и регуляризации задачи коррекции по Тихонову. К сожалению, для задач матричной коррекции в нормах, отличных от евклидовой, трудно предложить методы регуляризации, подобные Мог^епепс ТЬБ, поскольку при рассмотрении отношения двух векторных норм вместо отношения Рэлея, трудно найти аналог собственным значениям матрицы. По этой же причине затруднена и регуляризация по Тихонову — при ее классическом воплощении необходимо решать задачу минимизации отношения векторных норм с ограничением на величину знаменателя указанного отношения. В настоящей работе предложено два подхода к регуляризации исследуемых задач, близких к регуляризации по Тихонову (но не совпадающих с ней). Оба подхода предполагают, что матрица коррекции исследуемой системы является одноранговой. При этом первый способ регуляризации сводится к нахождению условного экстремума с ограничением в форме равенства, а второй - к минимаксной задаче без ограничений.

Пятый параграф посвящен исследованию задач оптимальной матричной коррекции несовместных СЛАУ с условием неотрицательности по минимуму некоторой ||| -нормы, т.е., задач

Результаты, полученные в указанном параграфе являются обобщением соответствующих результатов, полученных для задач матричной коррекции несовместных СЛАУ по минимуму ||| -нормы (§ 3 главы 3) и коррекции несовместных

СЛАУ с условием неотрицательности по минимуму евклидовой нормы (§ 1. главы 2). В качестве примера приведем теоремы:

0ЮИ,ДЛ,6): |¡Н -И] ^

Теорема 15. вМЬ\+ Ы, b) = inf ^ ~ ^, где jcgE" - некоторый вектор. Достижимость inf —^^ является необходимым и достаточным условием существовало <рог)

ния решения задачи Если решение задачи существует, то

вМь}ЛАЬ)>0, Н' = (Ь-Ах')угеП{&/1Х{Ь)+(А'1>)),хвХ(А+Н',Ь), где

. wib—Лх) .

* eArginf— , . , уеМ" - вектор, двойственный к вектору * относительно нормы «о ^(jr)

Теорема 16. Если задача (А,Ь) имеет решение — матрицу Я*, а система

(2.1.1) несовместна даже без учета условия *ä0, то множество Х+(А + H',b) состоит

только из одного элемента.

Результаты, аналогичные теоремам 15 и 16, удалось получить и для задачи

Шестой параграф специально посвящен исследованию достаточных условий собственности скорректированных по минимуму ||| -нормы несобственных задач

ЛП 1-го и 3-го рода в канонической форме. Полученные результаты являются обобщениями на случай -нормы соответствующий достаточных условий собственности задач ЛП, скорректированных по минимуму евклидовой нормы, представленных в § 2 второй главы.

Проблематика седьмого параграфа — задачи матричной коррекции несовместных СЛАУ с условием неотрицательности и показателями качества коррекции в ви-

Д=НМ1".Си1С-норм:

||Z.tf/?|| , = \\LHR\\ min , (25) ||Zifl?|l -> min .(26)

Задачи (19)-(26) представляют собой важный специальный случай задач матричной коррекции и заслуживают отдельного рассмотрения, поскольку используемые в них матричные нормы тесно связаны с весьма употребительными в прикладных задачах (в основном — задачах оценивания неизвестных параметров по подверженным шуму и ошибкам экспериментальным данным) полиэдральными векторными нормами ЦК,, l'L и их "взвешенными" модификациями.

Удалось показать, что задачи (19)-(26) допускают эффективное теоретическое исследование (и эффективное численное решение), поскольку сводятся к задачам (или конечной совокупности задач) ЛП. Для всех задач подробно рассмотрены способы такой редукции, представлены расчетные формулы.

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

Теорема 17. Для совместности системы Ах = Ь, дс>0, А<А<А, где ^еЕ""",

üi ax

xeR", b<= R", A,AeRmx", A = J , A = J , А < А, необходимо и достаточно, чтобы

Я*. ß-.

была совместна система линейных неравенств Ах<Ь<Ах, х>0. Если х - ее решение, то матрица А может быть построена по формуле А = А + &гц>^)-(А-А}, где

& =

Ь . если (а, любое число у е [0,1] в противном случае.

(27)

(28)

Рассмотрим задачи

||А о Н\\и шГ(= и), £].[;]) *0,А*(Л + Н)*Л,

|аоя еои^п^ъ),*^;»

А<(А + Н)<А, Ь<(Ь + И)<Ъ, где А = (а? >0)еИя"" - матрица индивидуальных весовых коэффициентов для коэффициентов матрицы Ну р = (Д > 0) е К" - вектор индивидуальных весовых коэффициентов для компонент вектора А. Пусть <5>0 - некоторый параметр. Введем в рассмотрение зависящие от параметра 3 матрицы

w(s) =

w,

W.

и векторы :(<5) = (:|(^))бГ, г(5) = (:Д(5))еГ следующим образом:

= maxiq^ - — L wt (S) = min]ä0,atj + — L

a„

a..

г, («5) = шах |л„ Ь, - 1, - (3) = шт , Ъ, + -д-1.

Теорема 18. Задача (27) эквивалентна задаче

IV (6)хА+ Ь < IV (3)хА+ 5д:5,Тхл+ их$= с1,3 ^ 0,3 -> тГ. (29)

При этом, если «Г,*',*' - решение задачи (29), то 3' = у, = ||а°Я*|^ ,

5 =

л-.^Л если (м* И***0«

любое число ^е[0,1] в противном случае.

Для задачи (28) удалось получить результаты, аналогичные теореме 18.

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

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

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

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

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

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

Интервальной матрицей принято называть множество матриц, удовлетворяющих некоторой системе поэлементных двухсторонних ограничений. Интервальную матрицу называют невырожденной, если все матрицы указанного множества являются невырожденными. Известно, что в общем случае проверка невырожденности интервальной матрицы является ЫР-трудной. В диссертационной работе, используя математический аппарат, разработанный для задач оптимальной матричной коррекции несовместных СЛАУ, удалось получить новые достаточные условия невырожденности интервальных матриц, сводящиеся к определению ЦЦ'1, -нормы так называемой центральной матрицы. Кроме того, удалось выделить класс интервальных матриц, для которого указанные условия являются также необходимыми, и подкласс интервальных матриц, для которого указанные условия могут быть проверены за полиномиальное время. Был также проведен вычислительный эксперимент по проверке чувствительности предложенных необходимых и достаточных условий невырожденности интервальной матрицы к погрешностям в задании ее центральной матрицы, который показал, высокую численную устойчивость указанных условий.

Близость некоторой квадратной матрицы полного ранга к вырожденной матрице удалось количественно выразить формулой 0(л) = ||л~'| \где 0(А) - минимальное значение ||-|| -нормы некоторой "поправочной" матрицы Н такой, что А + Н -

вырожденная матрица. Указанный результат является обобщением хорошо известного в линейной алгебре результата, справедливого для операторных (индуцированных) норм. В то же время, для частного случая, когда исследуемая несовместная СЛАУ такова, что [А -¿]е1Щ|", гапк[Л -Ь] = т, приведенная выше формула дает точное значение нижней грани || -нормы матрицы, корректирующей указанную

систему. Если же [А -¿] е , т>п +1 и гапк[Л -¿>] = и +1, то как удалось пока-

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

Указанная проблема решена путем сведения задачи максимизации гарантированного выигрыша первого игрока сначала к задаче ЛП, затем — к несовместной сис-

зать, в ([А

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

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

Пятый параграф посвящен исследованию задач матричной коррекции несовместных СЛАУ с матрицами, имеющими специальную структуру - так называемую структуру Теплица или Ганкеля. Приложения, в которых возникают системы линейных алгебраических уравнений указанного вида — это, как правило, задачи обработки временных рядов, анализа сигналов, идентификации линейных динамических систем по результатам наблюдений. При этом системы с матрицами Ганкеля в определенном смысле эквивалентны системам с матрицами Тёплица, поскольку обе матрицы могут быть получены друг из друга перестановками строк и столбцов. В настоящей работе рассматривается специальный частный случай несовместной линейной системы с матрицей Тёплица - однородная система, не имеющая нетривиального решения. Проблема заключается в том, чтобы с помощью минимального изменения коэффициентов матрицы исследуемой системы добиться существования нетривиального решения. При этом матрица коррекции тоже должна быть матрицей Тёплица. Задачи матричной коррекции в такой постановке раннее не рассматривались.

Сама задача поиска нетривиального решения однородной системы с матрицей Тёплица может возникнуть, например, в задаче оценивания параметров некоторого динамического сигнала по его наблюдениям (снятым через одинаковые промежутки времени), при условии, что его моделью является линейное однородное дифференциальное уравнение к -го порядка. Несовместность же подобной системы может быть вызвана как неправильным оцениванием порядка дифференциального уравнения, и, как следствие, неправильным заданием числа п столбцов исследуемой матрицы (п = к +1), так и наличием шума в наблюдаемом сигнале.

Для решения рассматриваемой задачи матричной коррекции в работе предложен алгоритмический подход, основанный на "векторизации" задачи и ее линеаризации. Линеаризация осуществляется стандартным образом, а "векторизация" основана на взаимно однозначном соответствии, существующем между вектором порядка N и матрицей Тёплица с размерами (Л'-л + ^хл. Указанный подход конкретизирован и доведен до уровня работающего вычислительного алгоритма в трех вариантах, соответствующих использованию в роли показателя качества матричной коррекции взвешенных с неотрицательными весами ||Ц, ,||Ц, и ||Ц, матричных норм.

Вычислительные алгоритмы матричной коррекции по минимуму взвешенных I'll,' Hi " Н0РМ на каждой итерации требуют решения вспомогательных задач ЛП.

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

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

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

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

Шестой параграф является иллюстрацией практического использования задач матричной коррекции, рассмотренных в предыдущем параграфе, для решения задач параметрической идентификации сигнала, представляющего собой сумму показательных функций. Параграф содержит краткое описание метода де Прони и его модификаций, в рамках которого и происходит сведение задачи параметрической идентификации динамического сигнала к задаче матричной коррекции однородной СЛАУ с матрицей Теплица или Ганкеля. Кроме того, приводятся результаты оценивания параметров известного модельного примера К. Ланцоша с помощью методов матричной коррекции, изложенных в § 5, по минимуму Ц-Ц^Ц-Ц, и ||-||f -норм, а также

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

Седьмой параграф посвящен дополнительному исследованию задач матричной коррекции СЛАУ со специальной структурой по минимуму взвешенной евклидовой нормы. Он продолжает линию использования метода Ньютона, начатую в § 6 первой главы. Материал параграфа перекликается также с результатами, полученными в § 6 второй главы. Результаты исследования оказываются достаточно инте-

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

В заключении отражены основные результаты диссертационной работы.

ОСНОВНЫЕ ВЫВОДЫ И РЕЗУЛЬТАТЫ РАБОТЫ

1. Для проблем коррекции несовместных СЛАУ общего вида с показателями качества коррекции, основанными на евклидовой матричной норме и ее "взвешенных" с помощью левого и правого умножения на невырожденные матрицы модификациях, исследованы задачи матричной коррекции с фиксированными столбцами, фиксированными строками и совокупностью фиксированных столбцов и строк, и построена модульная система задач, а также методов и алгоритмов их решения, в которой более сложные по своей постановке задачи сводятся к менее сложным, и, в итоге, сводятся к задачам матричной коррекции двух типов: задаче коррекции расширенной матрицы некоторой системы линейных алгебраических уравнений и задаче коррекции только ее матрицы коэффициентов. Для всех рассмотренных задач получены или уточнены необходимые и достаточные условия существования решения, вид оптимальных матриц коррекции, достаточные условия их единственности, вид множества решений скорректированной системы, достаточные условия его ограниченности, достаточные условия того, что указанное множество состоит из единственного вектора. Для случая не единственности оптимальной по норме матрицы коррекции решена задача выбора из множества оптимальных матриц такой, которая обеспечивала бы минимальную евклидову норму решению *** скорректированной системы (аналог нормального псевдорешения несовместной системы). Показано, что указанная задача эквивалентна минимизации угла между векторами х" и х, где х - нормальное псевдорешение исследуемой системы.

2. Для случая некорректности или несобственности указанных выше задач оптимальной матричной коррекции впервые показано, что кроме подхода, получившего название "Ког^епепс ТЬБ" и регуляризации задачи матричной коррекции по Тихонову, можно использовать еще один подход - фиксировать (освобождать от коррекции) отдельные столбцы матрицы (или расширенной матрицы) коэффициентов исследуемой системы.

3. Впервые рассмотрена и решена проблема оптимальной матричной коррекции несовместной СЛАУ общего вида по минимуму взвешенной (с произвольными

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

4. Для проблем коррекции СЛАУ по минимуму обобщенной матричной нормы впервые получены необходимые и достаточные условия существования решения, вид оптимальных матриц коррекции и решений скорректированных систем. Показано, что полнота столбцевого ранга матрицы коэффициентов корректируемой системы является необходимым условием существования решений рассматриваемых задач матричной коррекции. Получены достаточные условия единственности решения скорректированной системы. Для норм Гёльдера с показателем 1 <р«х> показана единственность оптимальной матрицы коррекции. Рассматриваемые задачи матричной коррекции сведены к задачам минимизации отношений векторных норм. Предложены методы регуляризации указанных задач матричной коррекции, которые сводятся либо к нахождению условного экстремума с ограничением в форме равенства, либо к минимаксной задаче без ограничений.

5. В качестве вспомогательных получены новые результаты из области линейной алгебры и ее приложений: обобщение на случай произвольных Щ, , |||" и -

норм леммы А.Н. Тихонова о решении с минимальной евклидовой нормой СЛАУ относительно неизвестной матрицы; необходимые и достаточные условия невырожденности интервальных матриц специального вида (и возможность проверки указанных условий за полиномиальное время); нижняя оценка нижней грани ||| -

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

6. Рассмотрены задачи матричной коррекции несовместных СЛАУ, имеющих специальную, так называемую аффинную структуру, частными случаями которых являются системы с матрицами, имеющими корректируемые и некорректируемые (нулевые) блоки, и системы с матрицами Тёплица (Ганкеля). Для указанных задач в роли показателя качества коррекции впервые была рассмотрена евклидова норма, взвешенная с произвольными неотрицательными индивидуальными для каждого коэффициента весами. При этом задачу матричной коррекции удалось свести к эквивалентной задаче минимизации дифференцируемой функции, частные производные первого и второго порядка которой (с привлечением методов дифференцирования псевдообратных матриц, являющихся специальным частным случаем методов Дж. Голуба и В. Перейры) могут быть вычислены в замкнутом виде без применения итерационных методов и конечно-разностных аппроксимаций, что открывает возможность эффективного использования градиентных методов и метода Ньютона. Для рассмотренных впервые "блочных" задач и задач коррекции несовместных однородных СЛАУ с матрицами Тёплица (Ганкеля) получены также специализированные методы и алгоритмы коррекции, проведены соответствующие вычислительные эксперименты, давшие положительные результаты. При использовании евклидовой

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

7. Для несовместных СЛАУ с условием неотрицательности впервые рассмотрены задачи матричной коррекции, постановки которых одновременно содержат фиксированные столбцы, фиксированные строки и взвешивание с помощью левого и правого умножения на невырожденные матрицы евклидовой нормы. Для указанных задач получены достаточные условия существования решения и вид оптимальных матриц коррекции, а сами задачи сведены к задаче минимизации квадратичной функции на единичной сфере с условием неотрицательности и некоторым ее модификациям, для которых построены и апробированы эффективные вычислительные алгоритмы градиентного типа, проверенные в вычислительных экспериментах. Кроме того, получена априорная верхняя оценка минимальной нормы матрицы коррекции, базирующаяся на новом алгебраическом результате — верхней оценке минимума квадратичной функции на пересечении единичной сферы с областью неотрицательных координат.

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

9. Получены необходимые и достаточные условия разрешимости задач оптимальной матричной коррекции по минимуму ||| -нормы несовместных СЛАУ с условием неотрицательности, вид оптимальных матриц коррекции и множеств реше-

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

форме.

10. Для широкого круга задач матричной коррекции несовместных СЛАУ с условием неотрицательности и показателями качества коррекции в виде |||",

|||", |||" и 11"^-норм получены редукции к задачам ЛП. Впервые рассмотрены задачи матричной коррекции несовместных СЛАУ с условием неотрицательности по минимаксному критерию, взвешенному с положительными индивидуальными для каждого корректируемого элемента весами, а также с фиксированными (не подлежащими коррекции) столбцами и строками матрицы (расширенной матрицы) коэффициентов и получены их редукции к задачам проверки совместности зависящих от скалярного параметра систем линейных алгебраических уравнений и неравенств.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИИ ОПУБЛИКОВАНЫ В

СЛЕДУЮЩИХ РАБОТАХ:

1. Ерохин В.И., Кашмет В.В., Лисицын Н.В. Модификация алгоритма Гревилля для удаления столбцов (строк) при построении псевдообратной матрицы // Журн. вы-числ. матем. и матем. физ. — 1989. - Т.29, №11.- С. 1753.

2. Ерохин В.И. Обобщение тождества Шермана-Моррисона на случай одноранговой модификации псевдообратной матрицы полного ранга // Журн. вычисл. матем. и матем. физ. - 1999. - Т.39, № 8. - С.1280-1282.

3. Ерохин В.И. Свойства оптимальной одноранговой коррекции матриц коэффициентов несовместных неоднородных линейных моделей // Дискрет, анализ и исслед. операций. Сер. 2. - 2002. - Т. 9, № 1. - С. 33-60.

4. Ерохин В.И. Оптимальная матричная коррекция и регуляризация несовместных линейных моделей // Дискретный анализ и исследование операций. Сер. 2. — 2002. — Т. 9, №2.-С. 41-77.

5. Ерохин В.И. Об условиях невырожденности интервальных матриц // Электронный журнал "Исследовано в России". - 2003. - С. 2488-2508. (http://zhurnal.ape.relarn.rU/articles/2003/214.pdf)

6. Горелик В.А., Ерохин В.И. Оптимальная матричная коррекция несовместных систем линейных алгебраических уравнений по минимуму евклидовой нормы. - М.: ВЦ РАН, 2004. — 193 с.

7. Горелик В.А., Ерохин В.И., Печенкин Р.В. Оптимальная матричная коррекция несовместных систем линейных алгебраических уравнений с блочными матрицами коэффициентов // Дискрет, анализ и исслед. операций. Сер. 2. - 2005. - Т. 12, № 2. - С. 3-22.

-358. Ерохин В.И. О коррекции матрицы коэффициентов несобственной задами линейного программирования в рамках интервальных ограничений. Методы оптимизации и их приложения: Труды XII Байкальской международ, конф. - Иркутск: Изд-во ИСЭМ СО РАН,2001.-Т. 1.-С.12-15.

9. Ерохин В.И. Необходимые и достаточные условия невырожденности интервальных матриц // Международная конф. по вычислительной математике МКВМ - 2004: Труды. - Новосибирск, Изд.-во ИВМ и МГ СО РАН, 2004. - С. 193-200.

10. Ерохин В.И. Матричная коррекция несобственных задач линейного программирования по минимуму евклидовой нормы с произвольными весами и фиксированными элементами // Математическое программирование: Труды Х111 Байкальской международной школы-семинара "Методы оптимизации и их приложения". — Иркутск: Изд-во ИСЭМ СО РАН, 2005. - Т. 1. - С. 105-110.

11. Горелик В.А., Ерохин В.И. О верхней оценке минимума квадратичной формы на пересечении единичной сферы с областью неотрицательных координат. //Моделирование, оптимизация и декомпозиция сложных динамических процессов.

- М.: ВЦ РАН, 2001. - С.30-50.

12. Горелик В.А., Ерохин В.И. Интервальная коррекция непродуктивной матрицы прямых затрат в линейной модели межотраслевого баланса // Моделирование, оптимизация и декомпозиция сложных динамических процессов. — М.: ВЦ РАН, 2001. -С.51-56.

13. Горелик В.А., Ерохин В.И., Муравьева О.В. Некоторые задачи аппроксимации матриц коэффициентов несовместных систем линейных уравнений и несобственных задач линейного программирования // Моделирование, декомпозиция и оптимизация сложных динамических процессов. - М.: ВЦ РАН, 2001. - С.57-88.

14. Горелик В.А., Ерохин В.И., Печенкин Р.В. Матричная коррекция несовместных линейных систем с матрицами Тёплица (Ганкеля) // Моделирование, декомпозиция и оптимизация сложных динамических процессов. - М: ВЦ РАН, 2003. - С. 41-73.

15. Горелик В.А., Ерохин В.И., Печенкин Р.В. Идентификация сигнала в виде суммы экспонент с помощью методов матричной коррекции несовместных линейных систем с матрицами Тёплица // Моделирование, декомпозиция и оптимизация сложных динамических процессов. - М: ВЦ РАН, 2003. - С.74-88.

16. Горелик В.А., Ерохин В.И. Оптимальная (по минимуму полиэдральной нормы) матричная коррекция несовместных систем линейных алгебраических уравнений и несобственных задач линейного программирования // Моделирование, декомпозиция и оптимизация сложных динамических процессов. - М: ВЦ РАН, 2004. — С. 3563.

17. Горелик В.А., Ерохин В.И., Печенкин Р.В. Использование L, и Lx норм в регу-• ляризованном структурном нелинейном алгоритме обобщенной наименьшей нормы U Моделирование, декомпозиция и оптимизация сложных динамических процессов.

- М: ВЦ РАН, 2004. - С. 64-77.

18. Свидетельство об отраслевой регистрации разработки в Отраслевом фонде алгоритмов и программ. Матричная коррекция несовместных однородных систем линейных алгебраических уравнений с матрицами Тёплица по минимуму евклидовой нормы / Ерохин В.И., Красников A.C., Волков В.В. (Борисоглебский государственный педагогический институт) № 4916 от 09.06.2005 . Алгоритм зарегистрирован в

"Национальном информационном фонде неопубликованных документов" 29.06.2005, № 50200501007.

19. Erokhin V.I. Optimum correction for matrix of parameters of improper linear programming problem // Дискретный анализ и исследование операций (DAOR'2000): М-лы международ, конф. - Новосибирск: Изд-во Ин-та математики СО РАН, 2000. - С. 132.

20. Erokhin V.I., Tarakanov A.F. On Minimax Matrix Correction of Matrix Game. 4-я Московская международная конференция по исследованию операций (ORM 2004): Труды. - М.: МАКС Пресс, 2004. - С. 81-82.

Ерохин Владимир Иванович

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

Подписано в печать 03.11.2005

Формат бумаги 60x84 1/16 Уч.-изд.л. 3. Усл.-печ. л. 2,25 Тираж 100 экз. Заказ 35

Отпечатано на ротапринтах в Вычислительном центре им. A.A. Дородницына Российской академии наук 119991, Москва, ул. Вавилова, 40

1. Матричная коррекция несовместных систем линейных алгебраических уравнений по минимуму евклидовой нормы

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

1.2. Сингулярное разложение, задача о матричной аппроксимации, наилучшей в смысле минимума евклидовой нормы, и задача Zlolal (А, Ъ)

1.3. Псевдообращение, классический метод наименьших квадратов и задача о минимальной по евклидовой норме матрице, разрешающей систему Ах = Ъ при фиксированных х и Ъ

1.4. Условия существования решения задач матричной коррекции и вид множеств решений скорректированных систем

1.5. Дополнительные сведения о задачах Zlnlaj(A,b) и Z/iv{/)( (A.b), альтернативные формулировки необходимых и достаточных условий существования решения

1.6. Использование взвешенной евклидовой нормы в задачах Zllllal(A,b) и Zflx{b](A,b)

1.7. Регуляризация задач матричной коррекции несовместных систем линейных алгебраических уравнений по минимуму евклидовой нормы

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

2.1. Коррекция несовместной СЛАУ с условием неотрицательности по минимуму взвешенной (с помощью левого и правого умножения на невырожденные матрицы) евклидовой нормы

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

2.3. Задача минимизации квадратичной формы на единичной сфере с условием неотрицательности и ее использование для решения задач коррекции несовместных СЛАУ с условием неотрицательности по минимуму евклидовой нормы

2.4. Обобщение задач (А,Ь) и (А,Ь) на случай фиксированных строк и столбцов при коррекции матрицы (расширенной матрицы) несовместной СЛАУ с условием неотрицательности решения

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

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

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

3.1. Необходимые сведения о векторных и матричных нормах

3.2. Обобщения задачи о решении СЛАУ относительно неизвестной матрицы с минимальной евклидовой нормой на гёльдеровы матричные нормы и ||| -нормы

3.3. Задачи матричной коррекции несовместных СЛАУ по минимуму li-fj ,|-||/"v и Н норм

3.4. Регуляризация решений изначально несовместных СЛАУ при матричной коррекции их коэффициентов по минимуму ||| ^ - нормы

3.5. Оптимальная матричная коррекция несовместных СЛАУ с условием неотрицательности по минимуму ||-|| -нормы

3.6. Достаточные условия собственности скорректированных по минимуму ||| -нормы несобственных задач ЛП 1 -го и 3-го рода в канонической форме

3.7. Практические методы матричной коррекции несовместных СЛАУ с условием

II II \\LR неотрицательности по минимуму Ц-^ и |]-j|( -норм

3.8. Альтернативная техника матричной коррекции несовместных СЛАУ с условием неотрицательности решения по минимуму взвешенной с произвольными положительными весами II ( -нормы

4. Задачи матричной коррекции специального вида. Практические приложения задач матричной коррекции

4.1. Оптимальная матричная коррекция несовместных систем линейных алгебраических уравнений и ограничений несобственных задач линейного программирования 1-го и 3-го рода с блочными матрицами коэффициентов

4.2. Условия невырожденности матриц и смежные вопросы

4.3. Минимаксная матричная коррекция матричной игры

4.4. Интервальная коррекция непродуктивной матрицы прямых затрат в линейной модели межотраслевого баланса

4.5. Матричная коррекция несовместных систем линейных алгебраических уравнений с матрицами Тёплица (Ганкеля) по минимуму ||-|| INI и У -норм

II lit, II llf2 И IIC^

4.6. Идентификация сигнала в виде суммы экспонент с помощью методов матричной коррекции несовместных систем линейных алгебраических уравнений с матрицами Тёплица (Ганкеля)

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

Актуальность проблемы. Формальной основой описательных или оптимизационных линейных моделей являются, как известно, системы линейных алгебраических уравнений (СЛАУ) и задачи линейного программирования (ЛП). Указанные линейные модели широко распространены и имеют многочисленные приложения в самых различных областях, причем могут быть использованы либо непосредственно (когда исследуемые с их помощью процессы или объекты являются линейными) либо опосредовано, в процессе линеаризации нелинейных моделей.

Исследуемые в диссертации СЛАУ являются несовместными, а задачи ЛП -несобственными. Хорошо известно, что совместность или несовместность линейных моделей, заданных системами уравнений, неравенств или смешанными системами уравнений и неравенств это фундаментальные свойства, связанные так называемыми теоремами об альтернативах - классической основой теорем существования решений задач оптимизации [12, 13], и возможным инструментом их эффективного численного решения, развитым в работах А.И. Голикова и Ю.Г. Евтушенко [35-37]. Но главный источник несовместных моделей - практика. Очень емко об этом сказал академик И.И. Еремин [70]: "В теории тех или иных классов задач (математических моделей) прослеживается эволюция в сторону ослабления требований, накладываемых на исследуемый математический объект. Эволюция, по большому счету, определялась давлением со стороны возникающих прикладных задач в той или иной предметной области. Приведем схему: единственность решения и устойчивость (корректность) единственность, неустойчивость (некорректность) неединственность и неустойчивость несобственность несобственность и плохая формализуемость гибкое моделирование

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

Одним из принципиально новых методов моделирования является предлагаемый академиком Ю.И. Журавлевым и его учениками, в частности, К.В. Рудаковым, алгебраический подход с использованием эвристических информационных моделей (см., например, [104,138]). Указанный подход наиболее перспективен для решения прикладных задач в тех предметных областях, для которых нет адекватных математических моделей, однако его существенной особенностью является применимость для строго определенного класса разрешимых задач, т. е. задач с внутренне непротиворечивой информацией.

Общие причины возникновения несовместных (несобственных) линейных моделей хорошо известны. Так, ими могут быть ошибки, допущенные исследователем при попытке в рамках некоторой прикладной задачи построить формальное описание исследуемого объекта. Например, при описании химико-технологического процесса исследователь не знает о протекании некоторых побочных химических реакций или имеет неверные сведения о схеме этих реакций, их кинетических и термодинамических константах и пр. Заметим, что моделирование, по признанию академиков П.С Краснощекова, А.А. Петрова и многих других ученых (см., например, [113, 128-129]) является скорее искусством, чем точной наукой, особенно в нетрадиционных для естествознания областях. Отбросим указанные грубые ошибки моделирования. Тогда для описательных линейных моделей (систем линейных алгебраических уравнений) в качестве источника их несовместности можно указать погрешности (шум) в экспериментальных данных, неопределенность, присутствующую в экспериментальных данных, ошибки округления, возникающие при вычислениях в арифметике с конечной разрядностью. Названные проблемы могут быть значительно усилены высокой размерностью исследуемой линейной модели [159]. Для оптимизационных линейных моделей (задач ЛП) источником несобственности могут быть как перечисленные выше причины, так и объективные внутренние противоречия исследуемого объекта. Наиболее выпуклые, яркие примеры для последнего случая легко взять из экономики или техники. Например, при рассмотрении задачи о максимизации выпуска некоторой продукции или ее производстве с минимальными затратами оказывается, что даже плановое задание невозможно выполнить из-за дефицита ресурсов. Достаточно злободневный технический пример - задача оптимального функционирования электроэнергетической системы в условиях дефицита мощности [105-107].

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

Матричная коррекция несовместных СЛАУ, как научное направление, изначально развивалась в связи с важной и широко распространенной прикладной проблемой -задачей обработки экспериментальных данных с помощью так называемого обобщенного метода наименьших квадратов - Total Least Squares (TLS). TLS является обобщением классического метода наименьших квадратов (MHK) на случай, когда шум присутствует в наблюдениях как зависимых, так и независимых переменных. Если принять гипотезу, что погрешности всех переменных имеют нормальное распределение с нулевым средним значением и одной и той же дисперсией, то TLS получает статистическое обоснование как метод, дающий оценки неизвестных параметров линейной модели, гарантирующие максимум функции правдоподобия. Системы линейных алгебраических уравнений, обрабатываемые с помощью TLS - это, как правило, переопределенные системы полного ранга. Для сравнения - системы, возникающие при коррекции несобственных задач ЛП в канонической форме - как правило, являются недоопределенными. Главная задача TLS -определить квазирешение исследуемой линейной системы. В то же время, можно показать, что указанное квазирешение - это точное решение модифицированной системы, повергшейся матричной коррекции по минимуму евклидовой нормы. Таким образом, TLS может рассматриваться, как метод матричной коррекции несовместных СЛАУ по минимуму евклидовой нормы.

Как свидетельствуют обзоры и популярные статьи, посвященные TLS (см., например, [167, 170, 208] и [229]), интенсивные исследования метода и его активное использование при решении прикладных задач начались в конце 80-х годов после появления работ Бельгийского математика S. Van Haffel. Ее диссертация [230] и, в особенности, написанная в соавторстве с J. Vandewalle монография [232] до сих пор являются одними из наиболее часто цитируемых материалов по TLS. Заметим, что задача ZTIS является частным случаем из обширного класса задач матричной аппроксимации и известна достаточно давно. Работы [208] и [229] содержат интересные исторические сведения, свидетельствующие о том, что задача ZTls или близкие к ней задачи многократно переоткрывались и связаны с такими именами как Е. Beltrami (1873) С. Jordan (1874), Е. Schmidt [227] (1907), Н. Weyl [237] (1912), L. Mirsky [205], С. Eckart, G. Young [173] (1936). Задача Z7VS просто и элегантно решается с помощью сингулярного разложения матрицы [а б]. Как известно, соответствующая техническая база (универсальные вычислительные машины третьего поколения), позволяющая решать нетривиальные задачи линейной алгебры, появилась в начале 70-х годов прошлого века. В это же время появляются и соответствующие математические работы, закладывающие алгоритмическую базу для вычисления сингулярного разложения [181, 182], а затем и для решения задачи TLS [184,185].

В настоящее время обобщенный метод наименьших квадратов (TLS) представляет собой широко и мощно развивающееся научное направление. Описание всевозможных известных к настоящему времени модификаций TLS вполне может быть предметом самостоятельной специализированной публикации. Одним из таких направлений, тесно связанным с рассматриваемыми в данной диссертационной работе проблемами регуляризации задач матричной коррекции линейных систем, является RTLS -регуляризованный обобщенный метод наименьших квадратов. Заметим, что "технология" регуляризации TLS - в настоящее время в подавляющем большинстве предмет зарубежных исследований: [168, 180, 186, 190, 193, 194, 200, 214, 234, 238]. Задачи математического программирования, которые при этом возникают, и проблемы эффективной вычислительной реализации методов их решения, тесно перекликаются с более общей задачей минимизации квадратичной функции на сфере [191, 192], достаточно интересны сами по себе, и, видимо, представляют еще широкое поле для исследования. "Идеология" RTLS, в отличие от "технологии" - заслуга отечественных математиков: (см, например, [17, 39,146] и др.)

Задачи TLS и их модификации могут быть не только некорректными но и несобственными (см. приведенную выше схему). В зарубежной литературе подобные задачи (и метод их решения, связанный с ограничением линейного подпространства столбцов матрицы коррекции) получили название Nongeneric TLS (соответствующего русскоязычного термина пока нет). Складывается впечатление, что необходимость серьезного исследования Nongeneric TLS зарубежными учеными недооценивается (отечественные исследования автору неизвестны). "Практики" - специалисты, использующие TLS и его модификации в прикладных исследованиях (в основном, это задач обработки наблюдений, см., например, [167]), считают, что отсутствие решения при использовании TLS - очень редкая аномалия, нонсенс. Примерно также долгое время относились к проблеме зацикливания в симплекс-методе. Для решения задач Nongeneric TLS сейчас используется два подхода: получение приближенного решения с использованием техники регуляризации (т.е., несобственная задача рассматривается как некорректная и для решения используются методы, упомянутые выше). Другой подход -ограничение линейного подпространства, в котором должно находиться TLS-решение. Более детально об этом написано в главе 1, а сейчас просто заметим, что если регулярный TLS сводится к нахождению минимального собственного значения матрицы [а -/>]' [a -b] и соответствующего ему собственного вектора, то в качестве решения задачи Nongeneric TLS предлагается брать следующие по величине собственные значения и соответствующие векторы [231, 233]. Указанный подход не устраняет всех проблем. Можно показать и теоретически и на примерах, что полученное таким образом Nongeneric TLS - решение не будет единственным и, как следствие, устойчивым. Кроме того, легко строятся примеры, когда ограничение линейного подпространства не снимает несобственности задачи TLS. Этот факт, скорее всего, известен специалистам, но еще не нашел отражения в публикациях (за исключением [51]).

Схема

TLS\ \STLS

I \ ; тш\ STLN иллюстрирует еще два направления, по которым может быть модифицирован обобщенный метод наименьших квадратов. Это переход от евклидовой к другим матричным нормам - Total Least Norm (TLN) - метод обобщенной наименьшей нормы, и переход к исследованию линейных систем со специальной структурой - Structured TLS (STLS) и Structured TLN (STLN). Из многообразия задач со специальной структурой сразу же выделим задачи с аффинной [171] структурой. Это задачи с матрицами (расширенными матрицами) Тёплица или Ганкеля, блочные задачи и т.д. В решении задач с аффинной структурой в L„L2,LX нормах (STLS, STLN) [130, 131, 189 198, 201, 202, 203, 209, 210, 211, 213, 219-223, 234, 238 и др.] существуют как определенные достижения, так и определенные нерешенные проблемы. К достижениям можно отнести то, что с помощью известных к настоящему времени методов уже успешно решаются практические задачи обработки наблюдений. Известные проблемы лежат как в теоретической плоскости - это проблемы с обоснованием сходимости соответствующих вычислительных алгоритмов, так и в практической - это проблемы численной эффективности алгоритмов (т.е., повышения их быстродействия и снижения требований к используемой памяти).

Распространение обобщенного метода наименьших квадратов на задачи матричной аппроксимации СЛАУ общего вида, использующие в качестве критериев полиэдральные матричные нормы (TLN), не стало еще не столь мощным направлением, как TLS, STLS, STLN. Здесь следует упомянуть исследования, которые проделал G.A. Watson [235, 236]. В данных работах для построения матричных аппроксимаций, оптимальных в смысле минимума полиэдральной нормы, предлагаются приближенные методы и вместо исходных, решаются "близкие" задачи (т.е., результаты о решении задачи TLN в точной постановке до настоящего времени неизвестны).

Обратимся теперь к истории и современному состоянию исследований, посвященных матричной коррекции несобственных задач линейного программирования. Сразу же отметим, что за рубежом указанное научное направление не получило широкого развития. Так, даже в фундаментальной монографии А. Схрейвера [143] не упоминания о несобственных задачах ЛП и методах их коррекции.

Как известно, систематические исследования несобственных задач линейного и выпуклого программирования (с введением соответствующей терминологии) были начаты 80-х годах (XX в.) И.И. Еремиными, его учениками и коллегами: Н.Н. Астафьевым, А.А. Ватолиным, Вл. Д. Мазуровым, Л.Д. Поповым, В.Д. Скариным, С.П. Трофимовым, В.Н. Фроловым и другими (см., например, [2-4, 18-26, 60-64, 67-69, 119, 120, 142, 147, 148, 152-155] и др.). В указанных работах (более полный список которых до 1992 г., содержащий также прикладные, в основном экономические работы, можно найти в диссертации [26]) рассматриваются несобственные задачи линейного и выпуклого программирования, проводится классификация, строится и исследуется теория двойственности, вводятся и исследуются дискретные аппроксимации решений -комитетные конструкции, предлагаются различные постановки и методы решения задач полной или частичной (правая часть системы уравнений или неравенств) параметрической коррекции и их содержательная (в основном, экономическая) интерпретация.

Последнее направление представляет наибольший интерес в контексте данного исследования. В его рамках коррекция несобственных линейных моделей осуществляется на основе метода параметрического программирования [115]. При этом в большинстве исследований рассматривается коррекция по вектору правой части ограничений и коэффициентам вектора целевой функции [18, 23, 57, 65, 66, 68, 132-134, 139, 140, 142, 145, 154, 164, и др.]. Такие задачи матричной коррекции конечно являются многопараметрическими, но не обладают максимально возможной общностью. Заметим, что исследование задач многопараметрической коррекции подобного типа, анализ проблем двойственности для несобственных задач математического программирования и изучение комитетных конструкций продолжаются и сейчас [5-11, 70-76, 108, 109, 121, 135-137, 156, 160,161,199, 204 и др.].

Матричная коррекция впервые была рассмотрена в работах А.А. Ватолина [19, 21, 22, 24-26, 63]. В частности, им были рассмотрены задачи: V, - задача коррекции расширенной матрицы коэффициентов несовместной СЛАУ по минимуму евклидовой нормы; V[ - модификация задачи Vt с запретом на коррекцию отдельных столбцов матрицы коэффициентов исследуемой системы; V" - модификация задачи V] с взвешенной с помощью левого и правого умножения на невырожденные матрицы евклидовой нормой и дополнительным ограничением в виде системы линейных неравенств, V2 - задача коррекции всех коэффициентов двойственной пары задач ЛП в стандартной форме по минимуму евклидовой нормы, V3 - задача коррекции всех коэффициентов смешанной системы линейных уравнений и неравенств по минимуму аддитивной матричной нормы с ограничениями в виде условий принадлежности множеств решений скорректированной системы и множеств оптимальных матриц коррекции заданным линейным подпространствам.

Для задач Vi, V[, V", V2 были получены: значение нижней грани квадрата евклидовой нормы матрицы коррекции, достаточные условия существования решения (оптимальной матрицы коррекции), вид оптимальной матрицы коррекции и вид вектора х - решения скорректированной линейной системы (задачи ЛП). В то же время, такие важные вопросы, как необходимые условия существования решения, условия единственности решения и вид множества решений скорректированной линейной системы (задачи ЛП) для указанных задач, остались не исследованы.

Исследования А.А. Ватолина в конце 90-х годов (XX в.) были продолжены (а также продолжаются в настоящее время) в ВЦ им. А.А. Дородницына РАН и МПГУ В.А. Гореликом и его учениками: В.А. Кондратьевой, О.В. Муравьевой, P.P. Ибатуллиным, Р.В. Печенкиным и другими: [40-56, 110, 112, 124-127, 130-131, 187-189]. Указанными авторами с использованием леммы А.Н. Тихонова, свойств евклидовой нормы и методов математического анализа были уточнены некоторые результаты А.А. Ватолина (в частности, для задач Vt, V были получены необходимые и достаточные условия существования решения) и рассмотрены новые модификации задачи V{, дополняющие указанную задачу новыми условиями - фиксированным вектором правой части и ограничениями в виде совместной подсистемы линейных алгебраических уравнений. На основе решений указанных задач с использованием условий Куна-Таккера удалось получить решения проблем матричной коррекции несобственных задач ЛП в канонической и стандартной форме по минимуму евклидовой нормы в виде сведения указанных задач к задачам вычисления собственных значений и соответствующих собственных векторов некоторого конечного набора вспомогательных квадратных симметричных матриц. Кроме того, с привлечением математической техники, отличной от вышеназванной (с использованием некоторых специфических свойств одноранговых матриц и чебышевской матричной нормы), удалось получить решение задачи минимаксной коррекции матрицы коэффициентов несобственной задачи ЛП в канонической форме в виде сведения ее к задаче линейного программирования. Начата разработка регуляризованных методов коррекции несовместных систем линейных алгебраических уравнений со специальной структурой в различных матричных нормах (RSTLN) и применение указанных методов к обработке временных рядов и идентификации сигналов [49, 50, 53, 89, 94, 131, 189, 210, 211]. Возникающие в подобных задачах СЛАУ, как правило, плохообусловлены. Это свойство передается соответствующим проблемам матричной коррекции и заставляет прибегать к различным методам регуляризации (например, описанным в работах [31, 32, 39]). В отношении достижений и нерешенных проблем в данном случае можно высказать те же комментарии, что и при анализе всей совокупности исследований, посвященных STLS и STLN.

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

Следующий класс проблем связан как с требованиями возможных приложений, так и с внутренней логикой математического исследования проблем оптимальной матричной коррекции линейных моделей. Применим приведенную выше схему из цитаты И.И Еремина к самим задачам матричной коррекции. Очевидно, что потребностям практики в наибольшей степени отвечает ситуация, когда задача коррекции имеет единственное решение - единственную оптимальную матрицу коррекции, причем это решение является устойчивым. Также очевидно, что высокую ценность в контексте некоторой прикладной задачи может представлять единственность и устойчивость решения самой скорректированной линейной модели. Итак, мы описали задачу матричной коррекции, решение которой обладает идеальными свойствами. К сожалению, на практике возможны и другие ситуации: неустойчивость решения задачи матричной коррекции, не единственность оптимальной матрицы коррекции, не единственность решения скорректированной линейной модели, отсутствие решения (несобственность) задачи оптимальной матричной коррекции. Следует признать, что несмотря на отдельные результаты, полученные, например, для Nongeneric TLS, систематизированное исследование указанных проблем и путей их преодоления в настоящее время отсутствует.

Еще один аспект нерешенных проблем заключается в том, что выбор показателя качества матричной коррекции, диктуемый прикладной задачей и связанный, например, с некоторой статистической гипотезой (евклидова норма - нормальное распределение ошибок, чебышевская норма - равномерное, октаэдрическая - наличие случайных выбросов), влияет на методы исследования и численного решения задач матричной коррекции. Кроме того, методы исследования и решения задач матричной коррекции несовместных линейных моделей различаются в зависимости от того, является ли исследуемая линейная модель несовместной СЛАУ или несобственной задачей ЛП. Можно ли унифицировать методы решения задач коррекции или хотя бы, методы теоретического исследования указанных задач? До настоящего времени ответа на указанный вопрос не было.

Все вышесказанное и обуславливает актуальность данного диссертационного исследования.

Объектом исследования является теория несовместных систем линейных алгебраических уравнений и несобственных задач линейного программирования.

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

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

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

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

- Впервые показано, что, для преодоления возможной некорректности или несобственности задач матричной коррекции несовместных СЛАУ корме подхода, предложенного для Nongeneric TLS и регуляризации по Тихонову, можно фиксировать (освобождать от коррекции) отдельные столбцы матрицы (или расширенной матрицы) коэффициентов исследуемой системы.

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

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

- Получены неизвестные ранее обобщения на широкий класс аддитивных матричных норм леммы А.Н. Тихонова о решении с минимальной евклидовой нормой СЛАУ относительно неизвестной матрицы; необходимые и достаточные условия невырожденности интервальных матриц специального вида (и возможность проверки указанных условий за полиномиальное время); нижняя оценка нижней грани ||| ^ -нормы некоторой матрицы возмущений, делающей вырожденной заданную матрицу полного столбцевогр ранга; априорная верхняя оценка минимальной нормы матрицы коррекции, базирующаяся на новом алгебраическом результате - верхней оценке минимума квадратичной функции на пересечении единичной сферы с областью неотрицательных координат.

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

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

Концепция заключается в едином подходе к проблемам коррекции как несовместных СЛАУ так и несобственных задач ЛП в канонической форме, базирующимся на широком использовании математического аппарата линейной алгебры: фундаментальных свойств псевдообратных матриц, евклидовой матричной нормы, аддитивных матричных норм и обобщениях на широкий класс аддитивных матричных норм леммы А.Н. Тихонова о решении СЛАУ относительно неизвестной матрицы с минимальной евклидовой нормой.

Внедрение и апробация результатов исследования. Основные результаты, полученные в диссертации, докладывались на Международной конференции "Математика. Образование. Экология. Тендерные проблемы" (Воронеж, 2000 г.), XII Байкальской международной конференции "Методы оптимизации и их приложения" (Иркутск, 2001 г.), XIII Байкальской международной школе-семинаре "Методы оптимизации и их приложения" (Иркутск, 2005 г.), Международной конференции "Некорректные и обратные задачи" (Новосибирск, 2002 г.), Международной научно-технической конференции "Методы и средства измерения в системах контроля и управления" (Пенза, 2002 г.), 4-й Московской международной конференции по исследованию операций (ORM2004) (Москва, 2004 г.), Международной конференции по вычислительной математике МКВМ-2004 (Новосибирск, 2004 г.), Международной конференции "Дискретный анализ и исследование операций (DAOR-2000) (Новосибирск, 2000 г.), Российской конференции "Дискретный анализ и исследование операций (DAOR'02, DAOR'04)" (Новосибирск, 2002, 2004 гг.), Всероссийской конференции "Математическое программирование и приложения" (Екатеринбург, 2003 г.), Всероссийской конференции "Алгоритмический анализ неустойчивых задач" (Екатеринбург, 2004 г.), 1-й Московской конференции "Декомпозиционные методы в математическом моделировании" (Москва, 2001 г.), 2-й Московской конференции "Декомпозиционные методы в математическом моделировании и информатике" (Москва, 2004 г.), Воронежском зимнем симпозиуме "Математическое моделирование в естественных и гуманитарных науках" (Воронеж, 2000 г.), научном семинаре по исследованию операций ВЦ им. А.А. Дородницына РАН, научном семинаре отдела Имитационных систем ВЦ им. А.А. Дородницына РАН, научных конференциях преподавателей и сотрудников Борисоглебского гос. пед. института, научных семинарах каф. прикладной математики и информатики Борисоглебского гос. пед. института.

Основные результаты диссертации опубликованы в 20 печатных работах, в том числе - одной монографии. Еще 20 публикаций по теме диссертации - тезисы различных конференций.

Результаты диссертационной работы вошли в состав проекта «Исследование и оптимизация сложных управляемых систем при нечетких или некорректных данных» (поддержан ФАП, 2005 г., (рук. проф. Тараканов А.Ф., исполнители Тараканов А.Ф., Ерохин В.И) и в тематику НИР Отдела Имитационных систем ВЦ им. А.А. Дородницына РАН (поддержка Программы поддержки ведущих научных школ).

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

ЗАКЛЮЧЕНИЕ

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

2. Для случая некорректности или несобственности указанных выше задач оптимальной матричной коррекции впервые показано, что корме подхода, получившего название "Nongeneric TLS" и регуляризации задачи матричной коррекции по Тихонову, можно использовать еще один подход - фиксировать (освобождать от коррекции) отдельные столбцы матрицы (или расширенной матрицы) коэффициентов исследуемой системы.

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

4. Для проблем коррекции несовместных систем линейных алгебраических уравнений по минимуму обобщенной матричной нормы впервые получены необходимые и достаточные условия существования решения, вид оптимальных матриц коррекции и решений скорректированных систем. Показано, что полнота столбцевого ранга матрицы коэффициентов корректируемой системы является необходимым условием существования решений рассматриваемых задач матричной коррекции. Получены достаточные условия единственности решения скорректированной системы. Для норм Гёльдера с показателем 1 < р < со показана единственность оптимальной матрицы коррекции. Рассматриваемые задачи матричной коррекции сведены к задачам минимизации отношений векторных норм. Предложены методы регуляризации указанных задач матричной коррекции, которые сводятся либо к нахождению условного экстремума с ограничением в форме равенства, либо к минимаксной задаче без ограничений.

5. В качестве вспомогательных получены новые и достаточно интересные результаты из области линейной алгебры и ее приложений: обобщение на случай произвольных |j-j|f , и ^ -норм леммы А.Н. Тихонова о решении с минимальной евклидовой нормой системы линейных алгебраических уравнений относительно неизвестной матрицы; необходимые и достаточные условия невырожденности интервальных матриц специального вида (и возможность проверки указанных условий за полиномиальное время); нижняя оценка нижней грани ^ -нормы некоторой матрицы возмущений, делающей вырожденной заданную матрицу полного столбцевого ранга.

6. Рассмотрены задачи матричной коррекции несовместных систем линейных алгебраических уравнений, матрицы (расширенные матрицы) которых имеют специальную структуру: системы, матрицы которых имеют корректируемые и некорректируемые (нулевые) блоки, и системы с матрицами Теплица (Ганкеля). "Блочные" задачи рассмотрены впервые. При использовании евклидовой нормы и ее модификаций, получаемых взвешиванием с помощью левого и правого умножения на невырожденные матрицы, для указанных задач матричной коррекции получены необходимые условия существования решения, вид оптимальных матриц коррекции и множеств решений скорректированных систем, а сами задачи коррекции сведены к задачам минимизации квадратичных функций, причем в терминах некоторых вспомогательных матриц получены формулы для вычисления соответствующих частных производных первого и второго порядка, открывающие возможность эффективного решения задач минимизации норм корректирующих матриц градиентными методами и методом Ньютона. При использовании минимаксного критерия коррекции (минимизируется максимальная взвешенная евклидова норма ненулевого корректирующего блока) задача коррекции сведена к минимаксной дифференцируемой задаче, для которой известны эффективные методы численного решения, разработанные В.Ф. Демьяновым и В.Н. Малоземовым. Проведены соответствующие вычислительные эксперименты, давшие положительные результаты.

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

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

9. Получены необходимые и достаточные условия разрешимости задач оптимальной матричной коррекции по минимуму ||| -нормы несовместных систем линейных алгебраических уравнений с условием неотрицательности, вид оптимальных матриц коррекции и множеств решений скорректированных систем. Приведены утверждения, характеризующие достаточные условия единственности решений соответствующих скорректированных систем. Указанные утверждения являются, в частности, достаточными условиями собственности соответствующих скорректированных задач ЛП. Получены также достаточные условия собственности скорректированных по минимуму евклидовой и произвольной II -нормы несобственных задач ЛП 1-го и 3-го рода в канонической форме.

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

II \\'Я II \\и< II \\Ц< II II7'й тттт качества коррекции в виде ■ , • и • -норм получены редукции к задачам ЛП. и п С ^ Ul't| М II i 91 (ft 11 оо

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

1. Алберт А. Регрессия, псевдоинверсия и рекуррентное оценивание. - М.: Наука, 1977. -224 с.

2. Астафьев Н.Н. Линейные неравенства и выпуклость. М.: Наука, 1982. - 153 с.

3. Астафьев Н.Н. Бесконечномерные задачи линейного программирования с разрывом в двойственности // Докл. АН СССР. 1984. - Т. 275, № 5. - С. 1033-1036.

4. Астафьев Н.Н. Бесконечные системы линейных неравенств в математическом программировании. М.: Наука, 1991. - 136 с.

5. Астафьев Н.Н. Чебышевские меры для систем аффинных функций // Математическое программирование и приложения: Тез. докл.12-й Всеросс. конф. Екатеринбург: УрО РАН, 2003.-С. 35-36.

6. Астафьев Н.Н. Некоторые элементарные преобразования двойственных задач линейного программирования. Попарная альтернативность // Современные методы оптимизации и их приложения к моделям энергетики: сб. науч. тр. Новосибирск: Наука, 2003.-С. 46-55.

7. Астафьев Н.Н. Одновременная регуляризация пары двойственных задач линейного программирования // Алгоритмический анализ неустойчивых задач: Тез. докл. Всероссийской конф. Екатеринбург: Изд-во Урал, ун-та, 2004. - С. 250-251.

8. Астафьев Н.Н. О мере несовместности системы линейных уравнений с требованием неотрицательности // Дискретный анализ и исследование операций: М-лы Российской конф. Новосибирск: Изд-во Ин-та математики СО РАН, 2004. - С. 120.

9. Ю.Астафьев Н.Н. Двойственная регуляризация, маргинальные (повторные) значения задач линейного программирования // Автоматика и телемеханика. 2004. - № 2. - С. 715.

10. Ашманов С.А. Линейное программирование. М.: Наука, 1982. - 134 с.

11. Ашманов С.А., Тимохов А.В. Теория оптимизации в задачах и упражнениях. М.: Наука, 1991.-448 с.

12. Беклемишев Д.В. Дополнительные главы линейной алгебры. М.: Наука, 1983. - 336 с.

13. Беллман Р. Введение в теорию матриц. М.: Наука, 1969. - 368 с.

14. Васильев Ф.П., Иваницкий А.Ю. Линейное программирование. М.: Факториал Пресс, 2003.-352 с.

15. Васин В.В., Агеев А.Л. Некорректные задачи с априорной информацией. -Екатеринбург: Уральская изд. ф-ма. "Наука", 1993,-263 с.

16. Ватолин А.А. Метод аппроксимации несобственной задачи выпуклого программирования. В кн.: Несобственные задачи оптимизации. Свердловск: УНЦ АН СССР, 1982.-С. 67-74.

17. Ватолин А.А. Об аппроксимации несобственных задач линейного программирования.- Деп. в ВИНИТИ, № 3501-84 Дел., 1984. 31 с.

18. Ватолин А.А. О задачах линейного программирования с интервальными коэффициентами // Журн. вычисл. матем. и матем. физ. 1984. - Т. 24, № 11. - С. 16291637.

19. Ватолин А.А. Аппроксимация несобственных задач линейного программирования по критерию евклидовой нормы // Журн. вычисл. матем. и матем. физ. 1984. - Т. 24, № 12. -С. 1907-1908.

20. Ватолин А.А. Методы анализа несобственных задач математического программирования: Дисс. . канд. физ.-мат. наук: 01.01.09. Свердловск, 1984.

21. Ватолин А.А. Об одной общей реализации схемы двойственнности для несобственной задачи линейного программирования. В кн.: Противоречивые модели оптимизации. -Свердловск: УНЦ РАН, 1987. С. 21-27.

22. Ватолин А.А. Множества разрешимости и коррекция седловых функций и систем неравенств. Препринт. Свердловск: ИММУрОРАН, 1989. 90 с.

23. Ватолин А.А. О коррекции расширенной матрицы несовместной системы линейных неравенств и уравнений // Комбинаторные, алгебраические и вероятностные методы дискретного анализа. Горький, 1989. - С. 40-54.

24. Ватолин А.А. Несобственные задачи математического программирования и методы их коррекции: Дисс. д-ра физ.-мат. наук: 01.01.09. Екатеринбург, 1992.

25. Величко А.С., Нурминский Е.А. Прямая-двойственная декомпозиция для жестких экстремальных задач // Математическое программирование и приложения: Тез. докл. 12-й Всероссийской конф. Екатеринбург: УрО РАН, 2003. - С. 65-68.

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

27. Воскобойников Ю.Е. Численная реализация и сравнение четырех способов выбора параметра регуляризации в устойчивых алгоритмах деконволюции // Научный вестник НГТУ. 2004. - Т. 17, № 2. fhttp://www.ngasu.nsk.su/prikl/deconv04.htmn

28. Гантмахер Ф.Р. Теория матриц. М.: Наука, 1988. - 552 с.

29. Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. М.: Мир, 1985. - 509 с.

30. Голиков А.И., Евтушенко Ю.Г. Новый метод решения систем линейных равенств и неравенств // ДАН. 2001. - Т. 381, № 4. - С. 444-447.

31. Голиков А.И., Евтушенко Ю.Г. Применение теорем об альтернативах к нахождению нормальных решений линейных систем // Известия ВУЗов, Математика. 2001. - Т. 475, № 12.-С. 21-31.

32. Голиков А.И., Евтушенко Ю.Г. Теоремы об альтернативах и их применение в численных методах // Журн. вычислит, математики и матем. физики. 2003. - Т. 43, № 3.-С. 354-375.

33. Голуб Дж., Ван Лоун Ч. Матричные вычисления. М.: Мир, 1999. - 548 с.

34. Горбунов В.К. О регуляризации экстремальных задач // Журн. вычисл. матем. и матем. физ. 1991. - Т. 31, № 2. - С. 235-248.

35. Горелик В.А., Кондратьева В.А. Параметрическое программирование и несобственные задачи линейной оптимизации // Моделирование, декомпозиция и оптимизация сложных динамических процессов. М.: ВЦ РАН, 1999. С.57-82.

36. Горелик В.А., Муравьева О.В. Задача аппроксимации с коррекцией всех данных. // Моделирование, декомпозиция и оптимизация сложных динамических процессов. М.: ВЦ РАН, 2000. С. 21-32.

37. Горелик В.А. Матричная коррекция задачи линейного программирования с несовместной системой ограничений // Журн. вычисл. матем. и матем. физ. 2001. - Т. 41, № 11.-С. 1697-1705.

38. Горелик В.А., Ерохин В.И. О верхней оценке минимума квадратичной формы на пересечении единичной сферы с областью неотрицательных координат. //Моделирование, оптимизация и декомпозиция сложных динамических процессов. М.: ВЦ РАН, 2001. - С.30-50.

39. Горелик В.А., Ерохин В.И. Интервальная коррекция непродуктивной матрицы прямых затрат в линейной модели межотраслевого баланса // Моделирование, оптимизация и декомпозиция сложных динамических процессов. М.: ВЦ РАН, 2001. -С.51-56.

40. Горелик В.А., Ибатуллин P.P. Коррекция системы ограничений задачи линейного программирования с минимаксным критерием.//Моделирование, декомпозиция и оптимизация сложных динамических процессов. Москва: ВЦ РАН, 2001. - С. 89-107.

41. Горелик В.А., Муравьева О.В. Коррекция несовместной системы линейных уравнений с дополнительными ограничениями // Декомпозиционные методы в математическом моделировании. Тез. докл. 1-й Московской конференции. М.: ВЦ РАН, 2001. - С.36-37.

42. Горелик В.А., Ерохин В.И., Печенкин Р.В. Матричная коррекция несовместных линейных систем с матрицами Теплица (Ганкеля) // Моделирование, декомпозиция и оптимизация сложных динамических процессов. М: ВЦ РАН, 2003. С. 41-73.

43. Горелик В.А., Ерохин В.И. Оптимальная матричная коррекция несовместных систем линейных алгебраических уравнений по минимуму евклидовой нормы. М.: ВЦ РАН, 2004.-193 с.

44. Горелик В.А., Ерохин В.И., Печенкин Р.В. Использование Ц и Lm норм в регуляризованном структурном нелинейном алгоритме обобщенной наименьшей нормы // Моделирование, декомпозиция и оптимизация сложных динамических процессов. М: ВЦ РАН, 2004. С. 64-77.

45. Горелик В.А., Муравьева О.В. Методы коррекции данных в задаче распознавания образов // Декомпозиционные методы в математическом моделировании и информатике. Тез. докл. 2-й Московской конференции. М.: ВЦ РАН, 2004. - С.39.

46. Горелик В.А., Муравьева О.В. Устойчивость решения системы линейных неравенств // Декомпозиционные методы в математическом моделировании и информатике. Тез. докл. 2-й Московской конференции. М.: ВЦ РАН, 2004. - С.40.

47. Горелик В.А., Муравьева О.В. Матричная коррекция данных в задачах оптимизации и классификации // Моделирование, декомпозиция и оптимизация сложных динамических процессов. М.: ВЦ РАН, 2004. - С.94-120.

48. Давыдов Э.Г. О системах несовместных линейных уравнений // Вестник МГУ. 1989. -Сер. 15, №2.-С. 76-79.

49. Демьянов В.Ф., Малоземов В.Н. Введение в минимакс. М.: Наука, 1972. 368 с.

50. Деннис Дж. Шнабель Р. Численные методы безусловной минимизации. М.: Мир,1998.-440 с.

51. Еремин И.И., Мазуров В.Д. Нестационарные процессы математического программирования . М.: Наука, 1979. - 288 с.

52. Еремин И.И. Двойственность для несобственной задачи линейного программирования. В кн.: Несобственные задачи оптимизации. Свердловск: УНЦ АН СССР, 1982.-С. 3-10.

53. Еремин И.И. Двойственность для несобственных задач линейного и выпуклого программирования и методы их коррекции // Изв. АН СССР. Сер. Техн. киберн. 1983, №1. - С. 20-32.

54. Еремин И.И., Мазуров Вл. Д., Астафьев Н.Н. Несобственные задачи линейного и выпуклого программирования. М.: Наука, 1983. - 336 с.

55. Еремин И.И., Ватолин А.А. Двойственность для несобственных бесконечномерных задач линейного и выпуклого программирования. В кн.: Методы аппроксимации несобственной задачи линейного программирования. Свердловск: УНЦ АН СССР,1984.-С. 3-20.

56. Еремин И.И. Несобственная задача квадратичного программирования и вопросы регуляризации. В кн.: Параметрическая оптимизация и методы аппроксимации несобственных задач математического программирования. Свердловск: УНЦ АН СССР,1985.-С. 47-50.

57. Еремин И.И. Противоречивые модели планирования и управления. В кн.: Противоречивые модели оптимизации. Свердловск: УНЦ АН СССР, 1987. - С. 28-37.

58. Еремин И.И. Двойственность и аппроксимация для несобственных задач математического программирования // Изв. АН СССР. Сер. Техн. киберн. 1987, № 1. -С. 70-81.

59. Еремин И.И. Вопросы двойственности для несобственной задачи многокритериальной линейной оптимизации. В кн.: Исследования по несобственным задачам оптимизации. Свердловск: УНЦ АН СССР, 1988. - С. 27-33.

60. Еремин И.И. Противоречивые модели оптимального планирования. М.: Наука, 1988. -160 с.

61. Еремин И.И. Теория линейной оптимизации. Екатеринбург: Изд-во "Екатеринбург",1999.-312 с. »

62. Еремин И.И. Двойственность в линейной оптимизации. Екатеринбург: УрО РАН, 2001.-179 с.

63. Еремин И.И. Синтез фейеровских отображений с несовпадающими пространствами их образов //ДАН. -2001. -Т. 378, № 1.-С. 11-13.

64. Еремин И.И., Соколинская И.М. Фейеровские итерационные процессы для несобственных задач линейного программирования // Математические структуры и моделирование: Сб. научн. тр. Омск: Омск. гос. ун-т. - 2002. - Вып. 9. - С. 10-26.

65. Ерохин В.И., Лисицын Н.В., Кашмет В.В. Модификация алгоритма Гревилля для удаления столбцов (строк) при построении псевдообратной матрицы / Ред. Журн. вычисл. матем. и матем. физ., 1989. 10 с. - Деп. в ВИНИТИ 29.06.89 , №4302-В89 деп.

66. Ерохин В.И., Кашмет В.В., Лисицын Н.В. Модификация алгоритма Гревилля для удаления столбцов (строк) при построении псевдообратной матрицы // Журн. вычисл. матем. и матем. физ. 1989. - Т.29, №11. - С.1753.

67. Ерохин В.И. Рекурсивный алгоритм решения общей задачи линейного программирования / Борисоглебский гос. пед. ин-т. Борисоглебск, 1995. - 78 с. - Деп. в ВИНИТИ 17.10.95 , №2758-В95 деп.

68. Ерохин В.И. О некоторых достаточных условиях неуправляемости линейных стационарных систем. Совершенствование преподавания физико-математических и общетехнических дисциплин в педвузе и школе: Сб. науч. тр. Борисоглебск: БГПИ, 1996, С. 74-75.

69. Ерохин В.И. Обобщение тождества Шермана-Моррисона на случай одноранговой модификации псевдообратной матрицы полного ранга // Журн. вычисл. матем. и матем. физ. 1999. - Т.39, № 8. - С.1280 - 1282.

70. Ерохин В.И. Исследование и оптимальная многопараметрическая коррекция несовместных линейных моделей // Математическое моделирование в естественных игуманитарных науках: Тез. докл. Воронеж, ВГУ, 2001. - С. 95.

71. Ерохин В.И. О коррекции матрицы коэффициентов несовместной линейной модели. М-лы ежегодной научной конференции преподавателей и студентов БГПИ 2001 г., Борисоглебск: БГПИ, 2002, С. 74.

72. Ерохин В.И. О достижимости нижней грани нормы матрицы коррекции матрицы коэффициентов несовместной линейной системы. Дискретный анализ и исследование операций (DAOR'02): М-лы международ конф. Новосибирск: Изд-во Ин-та математики СО РАН, 2002.-С. 156.

73. Ерохин В.И. Свойства оптимальной одноранговой коррекции матриц коэффициентов несовместных неоднородных линейных моделей // Дискрет, анализ и исслед. операций. Сер. 2. 2002. - Т. 9, № 1. - С. 33-60.

74. Ерохин В.И. Оптимальная матричная коррекция и регуляризация несовместных линейных моделей // Дискретный анализ и исследование операций. Сер. 2. 2002. - Т. 9, №2.-С. 41-77.

75. Ерохин В.И. О нижней оценке нижней грани нормы матрицы, корректирующей несовместную систему линейных алгебраических уравнений // Математическое программирование и приложения: Тез. докл. 12-й Всероссийской конф. Екатеринбург: УрО РАН, 2003.-С. 103-104.

76. Ерохин В.И., Печенкин Р.В. Идентификация сигнала в виде суммы экспонент с помощью метода TLN // Математическое программирование и приложения: Тез. докл. 12-й Всероссийской конф. Екатеринбург: УрО РАН, 2003. - С. 105-106.

77. Ерохин В.И. Об условиях невырожденности интервальных матриц // Электронный журнал "Исследовано в России". 2003. - С. 2488-2508. (http://zhurnal.ape.relarn.ru/articles/2003/214.pdf)

78. Ерохин В.И., Волков В.В. О сведении решения интегрального уравнения к задаче матричной коррекции. М-лы ежегод. науч. конф. преподавателей и студентов БГПИ 2004 года: Борисоглебск, БГПИ, 2004. С. 95-96.

79. Ерохин В.И. Аналог нормального решения в задаче матричной коррекции несовместной системы линейных алгебраических уравнений // Алгоритмический анализ неустойчивых задач: Тез. докл. Всерос. конф. Екатеринбург: Изд-во Урал, ун-та. - 2004. - С. 266-267.

80. Ерохин В.И. Регуляризация матричной коррекции несовместной системы линейных алгебраических уравнений // Алгоритмический анализ неустойчивых задач: Тез. докл. Всерос. конф. Екатеринбург: Изд-во Урал, ун-та. - 2004. - С. 268-269.

81. Ерохин В.И. Декомпозиция матричной коррекции несовместных систем линейных алгебраических уравнений. Декомпозиционные методы в математическоммоделировании и информатике: Тез. докл. 2-й Московской конф. М.: ВЦ РАН, 2004. -С. 60-61.

82. Ерохин В.И. Минимаксная матричная коррекция несовместных систем линейных алгебраических уравнений. Дискретный анализ и исследование операций (DAOR'04): М-лы Российской конф. Новосибирск: Изд-во Ин-та математики СО РАН, 2004. - С. 126.

83. Ерохин В.И. Необходимые и достаточные условия невырожденности интервальных матриц Международная конф. по вычислительной математике МКВМ 2004: Труды. -Новосибирск, Изд.-во ИВМ и МГ СО РАН, 2004. - С. 193-200.

84. Журавлев Ю.И. Об алгебраическом подходе к решению задач распознавания или классификации // Проблемы кибернетики. 1978. - Т. 33. - С. 5-68.

85. Зоркальцев В.И., Ковалев Г.Ф., Лебедева Л.М. Исследование моделей оценки дефицита мощности электроэнергетических систем // Известия РАН. Энергетика. 2002.- №5. С. 76-88.

86. Зоркальцев В.И. Решение систем двухсторонних линейных неравенств алгоритмами внутренних точек на примере модели расчета режимов электроэнергетических систем // Дискретный анализ и исследование операций. Сер. 2. 2004, Т. 11, № 1, - С. 62-78.

87. Зыкина А.В. Анализ решений в противоречивых моделях оптимального планирования // Доклады СО АН ВШ. 2001. - Т. 3, № 1. - С. 11-16.

88. Зыкина А.В. Обобщенное решение при ограничениях // Математическое программирование: Труды XII Байкальской международной конференции "Методы оптимизации и их приложения". Иркутск: Изд-во ИСЭМ СО РАН, 2001. - Т. 1. - С. 324-329.

89. Ибатуллин P.P. Методы коррекции и аппроксимации несобственных задач оптимизации и управления с минимаксным критерием: Дисс. . канд. физ.-мат. наук: 05.13.17.-М., 2002.

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

91. Кондратьева В.А. Несобственные задачи линейной оптимизации и параметрическое программирование: Дисс. . канд. физ.-мат. наук: 05.13.17. -М., 2000.

92. Краснощеков П.С., Петров А.А. Принципы построения моделей. М.: Фазис; М: ВЦ РАН, 2000.-411 с.

93. Ланцош К. Практические методы прикладного анализа. М.: Физматгиз, 1961. -524 с.

94. Левитин Е.С. Теория возмущений в математическом программировании и ее приложения. М.: Наука, 1992. - 360 с.

95. Лопатников И.Л. Экономико математический словарь. - М.: Наука, 1987. - 510 с.

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

97. Льюнг Л. Идентификация систем. Теория для пользователя. М.: Наука, 1991. -432 с.

98. Мазуров Вл.Д. Метод допустимых коррекций. В кн.: Несобственные задачи оптимизации. Свердловск: УНЦ АН СССР, 1982. - С. 11-22.

99. Мазуров Вл. Д. Метод комитетов в задачах оптимизации и классификации. М.: Наука, 1990.-246 с.

100. Мазуров Вл. Д., Хачай М.Ю. Комитеты систем линейных неравенств // Автоматика и телемеханика, 2004, вып. 2, С. 43-54.

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

102. Марпл-мл. С.Л. Цифровой спектральный анализ и его приложения. М.: Мир, 1990. -584 с.

103. Матросов В.Л., Горелик В.А., Жданов С.А., Муравьева О.В. Коррекция данных в задаче классификации // Математические методы распознавания образов: Доклады XI Всероссийской конф. (ММРО-11).- М.: ВЦ РАН, 2003. С. 136-137.

104. Муравьева О.В. Матричная коррекция данных для несовместных систем линейных уравнений и ее применение в задачах оптимизации и классификации: Дисс. . канд. физ.-мат. наук: 05.13.17.-М., 2002.

105. Павловский Ю.Н. Имитационные модели и системы. М.: Фазис, 1998. - 266 с.

106. Павловский Ю.Н., Смирнова Т.Г. Проблема декомпозиции в математическом моделировании. М.: Фазис, 2000. - 265 с.

107. Печенкин Р.В. Задача идентификации сигнала с использованием регуляризованного алгоритма SNTLN // Алгоритмический анализ неустойчивых задач. Тез. докл. Всеросс. конф. Екатеринбург: Изд-во Урал, ун-та. - 2004. - С. 362-363.

108. Попов Л.Д. Об одном методе декомпозиции в несобственном линейном программировании. В кн.: Нерегулярная двойственность в математическом программировании. Свердловск: УрО РАН, 1990. - С. 42-45.

109. Попов Л.Д. Несобственные задачи оптимизации, методы их оптимальной коррекции и приложения. Дисс. докт. физ.-мат. наук: 01.01.09. Новосибирск, 1997.

110. Попов J1.Д. Об одноэтапном методе решения лексикографических вариационных неравенств // Известия вузов. Математика, 1998, Т. 439, № 12, С. 71-81.

111. Рудаков К.В. Об алгебраической теории универсальных и локальных ограничений для задач классификации// Распознавание, Классификация, Прогноз. 1988. - Т. 1. -С. 176-200.

112. Скарин В.Д. О применении метода регуляризации для коррекции несобственной задачи линейного программирования первого рода. В кн.: Методы аппроксимации несобственной задачи линейного программирования. Свердловск: УНЦ АН СССР, 1984.-С. 39-54.

113. Скарин В.Д. Об одном подходе к анализу несобственных задач линейного программирования. //Журн. вычисл. матем. и матем. физ. 1986. - Т. 26, №3. - С. 439448.

114. Скарин В.Д. Об одном регуляризующем алгоритме коррекции противоречивых задач выпуклого программирования с линейными ограничениями. В кн.: Исследования по несобственным задачам оптимизации. Свердловск: УНЦ АН СССР, 1988. - С. 48-56.

115. Схрейвер А. Теория линейного и целочисленного программирования: в 2-х т. Т. 1. -М.: Мир, 1991. 360 е., Т.2. - М.: Мир, 1991. - 342 с.

116. Тихонов А.Н. О нормальных решениях приближенных систем линейных алгебраических уравнений // Докл. АН СССР. 1980. - Т. 254, №3. - С.549-554.

117. Тихонов А.Н., Морозов В.А., Карамзин В.И. О задачах коррекции линейных неравенств // Численный анализ: методы, алгоритмы, приложения. М., 1985. - С. 3-13.

118. Тихонов А.Н., Арсенин В .Я. Методы решения некорректных задач. М.: Наука, 1986.-288 с.

119. Трофимов С.П. О задачах линейного программирования с разрывом двойственности в общих пространствах // Сб. научн. тр. Свердловск: УрО АН СССР, 1987, С. 64-70.

120. Трофимов С.П. Анализ соотношений двойственности для задач полубесконечного и бесконечного линейного программирования. Дисс. . канд. физ.-мат. наук: 01.01.09. -Свердловск, 1988.

121. Уилкинсон Дж. X, Алгебраическая проблема собственных значений. М.: Наука, 1970.-564 с.

122. Фаддеев Д.К., Фадцеева В.Н. Вычислительные методы линейной алгебры. М.-Л.:Физматгиз, 1963. - 734 с.

123. Форсайт Дж., Моулер К. Численное решение систем линейных алгебраических уравнений. М.: Мир. 1969. - 168с.

124. Фролов В.Н. Оптимизация плановых программ при слабо согласованных ограничениях. -М.: Наука, 1986. 166 с.

125. Фролов В.Н., Ватолин А.А. Анализ противоречивых ситуаций в задачах текущего планирования производства. В кн.: Противоречивые модели оптимизации. Свердловск: УНЦ РАН, 1987.-С. 79-92.

126. Фролов В.Н. Оптимизация плановых программ при слабо согласованных ограничениях. Дисс.докт. эконом, наук. М., 1987.

127. Фролов В.Н., Чернавин П.Ф. Построение непротиворечивых программ развития производственно-экономических объектов // Экономика и матем. методы. 1987. - Т. 23, №6,-С. 1069-1076.

128. Химмельблау Д.Анализ процессов статистическими методами. М.: Мир, 1993, -956 с.

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

130. Цурков В.И. Декомпозиция в задачах большой размерности. М.: Наука, 1981. - 352 с.

131. Шамрай Н.Б. Вариационный подход к решению несобственных задач линейного программирования // Математическое программирование: Труды XIII Байкальской международной школы-семинара ". Иркутск: Изд-во ИСЭМ СО РАН, 2005. - Т. 1. - С. 155-160.

132. Шамрай Н.Б. О двух подходах к решению систем неравенств // Омский научный вестник. 2003. - Т. 24, № 3. - С. 55-57.

133. Эйкхофф П., Ванечек А., Савараги Е. и др. Современные методы идентификации систем. М.: Мир, 1983. - 400 с.

134. Baumgart R., Beer К. Ein Dekompositionszugang in inkonsistenten linearen Optimierungsaufgaben // Wiss. Z. d. TU karl-Marx-Stadt. 1990. - Vol. 32, No. 1. - P. 56-64.

135. Beeck H. Zur Problematik der Hullenbestimmung von Intervallgleichungssystemen // Interval Mathematics. K. Nickel ed. Lecture Notes in Computer Science. Berlin: Springer-Verlag. 1975. - Vol. 29. - P. 150-159.

136. Bjorck A. A bidiagonalization algorithm for solving large and sparse ill-posed systems of linear equations // BIT. 1988. - Vol. 18. - P. 659-670.

137. Branham R. Jr. Astronomical data reduction with total least squares // New Astronomy Reviews. 2001. Vol.45. - P. 649-661.

138. Calvetti D., Morigi S., Reichel L., Sgallari F. Tikhonov regularization and the L-curve for large discrete ill-posed problems // J. of Computational and Appl. Mathematics. 2000. - Vol. 123.-P. 423-446.

139. Coxson G.E. Computing exact bounds on elements of an inverse interval matrix in NP-hard // Reliable Computing. 1999. - Vol. 5, No. 2. - P. 137-142.

140. De Groen P. An introduction to total least squares // Niew Archief voor Wiskunde. 1996. -Vol. 14, No 2.-P. 237-254.

141. De Moor B. Total least squares for affinely structured matrices and the noisy realization problem // IEEE Trans. Signal Process. 1994. - Vol. 42, No. 11. - P. 3004-3113.

142. Eckart, C., Young, G. The approximation of one matrix by another of lower rank // Psychometrika. 1936. - Vol 1. - P. 211-218.

143. Erokhin V.I. Optimum correction for matrix of parameters of improper linear programming problem // Дискретный анализ и исследование операций (DAOR'2000): М-лы международ конф. Новосибирск: Изд-во Ин-та математики СО РАН, 2000. - С. 132.

144. Erokhin V.I. On regularization of the problems of optimum matrix correction for incompatible linear systems. Некорректные и обратные задачи: Тез. докл. Международ, конф. Новосибирск, Изд-во ин-та математики СО РАН, 2002. - С. 54.

145. Erokhin V.I., Tarakanov A.F. On Minimax Matrix Correction of Matrix Game. 4-я Московская международная конференция по исследованию операций (ORM 2004): Труды. М.: МАКС Пресс, 2004. - С. 81-82.

146. Evans J.W., Gragg W.B., LeVeque W.B. On least squares exponential sum approximation with positive coefficients // Mathematics of Computation. 1980. - Vol. 34, No. 149. - P. 203211.

147. Fierro R.D., Golub G.H., Hansen P.C., O'Leary D.P. Regularization by truncated total least squares // SIAM J. Sci. Comput. 1997. - Vol. 18, No. 4. - P. 1223-1241.

148. Golub G.H., Reinsch C. Singular value decomposition and least squares solutions // Numerishe Mathematik. 1970. - Vol. 14. - P. 403-420.

149. Golub G.H. Some modified matrix eigenvalue problems // SIAM Rev. 1973. - Vol. 15, No2.-P. 318-344.

150. Golub G.H., Pereyra V. The differentiation of pseudo-inverses and nonlinear least squares problems whose variables separate // SIAM J. Numer. Anal. 1973. - Vol. 10, No. 3. — P. 413— 432.

151. Golub G.H., Van Loan C.F. An analysis of the total least squares problem // SIAM J. Numer. Anal. 1980. - Vol. 17, No. 3. - P. 883-893.

152. Golub G.H., Hoffman A., Stewart G.W. A generalization of Eckart-Young-Mirsky matrix approximation theorem // Linear Algebra and Its Applications. 1987. - Vol. 88/89. - P. 317— 327.

153. Gorelik V.A., Ibatullin R.R. Correcting the system of constraints of a linear program with the aid of minimax criterion // Тезисы докладов 3-й международной конференции по исследованию операций. М.: ВЦ РАН, 2001. - С. 42.

154. Gorelik V.A., Muravyova O.V. Problem of approximating with variation of all data. //Тезисы докладов 3-й международной конференции по исследованию операций. -М.: ВЦ РАН, 2001.-С. 43.

155. Gorelik V.A. , Pechenkin R.V. Decomposition approach for solving signal identification problem // Декомпозиционные методы в математическом моделировании и информатике. Тез. докл. 2-й Московской конференции. М.: ВЦ РАН, 2004. - С.41-42.

156. Hager W.W. Minimizing a quadratic over a sphere // SIAM J. Optim. 2001. - Vol. 12, No l.-P. 188-208.

157. Hager W.W., Park S.C. Global convergence of SSM for minimizing a quadratic over a sphere, Department of Mathematics, University of Florida, Gainesville, FL 32611, August 12, 2003.

158. Hansen P.C. Regularization Tools. A Matlab package for analysis and Solution of Discrete ill-posed problems, Department of Mathematical Modeling, Technical University of Denmark, June 1992 September 2001,109 p. http://www.imm.dtu.dk/~pch

159. Hestenes Magnus R. and Karush W. A method of gradients for the calculation of the characteristic roots and vectors of a real symmetric matrix //J. Res. Nat. Bur. Standards. -1951. -Vol. 47.-P. 45-61.

160. Holmstrom K., Petersson J. A review of the parameter estimation problem of fitting positive exponential sums to empirical data // Applied Mathematics and Computation. 2002. -Vol. 126.-P. 31-61.

161. Householder A.S. On Prony's Method of Fitting Exponential Decay Curves and Multiple-Hit Survival Curves // Oak Ridge National Laboratory Report ORNL-455, Oak Ridge, Tenn., 1950.

162. Khachay M. Yu. On Approximate Algorithm of a Minimal Committee of a Linear Inequalities System // Pattern Recognition and Image Analysis. 2003. - Vol. 13, No. 3. - P. 459^164.

163. Lemmerling P. Structured total least squares: analysis, algorithms and applications // Ph. D. dissertation. Kattholieke Universiteit Leuven, Arenbergkasteel, Belgium, 1999,189 p.

164. Lemmerling P., Mastronardi N., Van Huffel S. Fast algorithm for solving Hankel/Toeplitz structured total least squares problem // Numer. Alg. 2000. - Vol. 23. - P. 371-392.

165. Mastronardi N., Lemmerling P., Van Huffel S. Fast structured total least squares algorithm for solving the basic deconvolution problem // SIAM J.Matrix Anal. Appl. 2000. - Vol. 22, No. 2. - P. 533-553

166. Mazurov VI. D., Khachai M. Yu., Rybin A.I. Committee Constructions for Solving Problems of Selection, Diagnostics and Prediction // Proceedings of the Steklov Institute of mathematics. 2002. - Suppl. 1. - P. 67-101.

167. Mirsky L. Symmetric gauge functions and unitarily invariant norms. Quart. J. Math. Oxford. Ser.2. 1960. - Vol. 11,No. 41.-P. 50-59.

168. Nemirovskii A. Several NP-hard problems arising in robust stability analysis // Mathematics of Control, Signals and Systems. 1993. - Vol. 6, j 1. - P. 99-105.

169. Neumaier A. Linear interval equations // Interval Mathematics. K. Nickel ed. Lecture Notes in Computer Science. Berlin: Springer-Verlag. 1985. - Vol. 212. - P. 109-120.

170. Nievergelt Y. A tutorial history of least squares with applications to astronomy and geodesy // Journal of Computational and Applied Mathematics. 2000. - Vol. 121, Issues 1-2. -P. 37-72.

171. Park H., Zhang L., Rosen J.B. Exponential modeling with unknown model order using structured nonlinear total least norm // Advances in Computational Mathematics. 2003. - Vol. 19,No. 1-3.-P. 307-322.

172. Pechenkin R. The Signal Identification Problem Using Regularized SNTLN Algorithm // Journal of Electical Engineering. 2004. - Vol. 55, No. 12/s. - P. 3-7.

173. Petersson J., Holmstrom K. Methods for Parameter Estimation in Exponential Sums // IMa-TOM technical report. Vasteras Univ. Dept. of Math, and Phys. 1997. Vol. 5. - 16 p.

174. Pruessner A., O'Leary D.P. Blind Deconvolution Using a Regularized Structured Total Least Norm Algorithm // SIAM J. Matrix Anal. Appl. 2003. - Vol. 24, No. 4. - P. 1018-1037.

175. Renaut R.A., Guo H. Efficient algorithms for solution of regularized total least squares // SIAM J. Matrix Anal. Appl. 2005. - Vol. 26, No. 2. - P. 457-476. (http://math.la.asu.edu/~rosie/), (http://math.la.asu.edu/~hongbin/)

176. Rex G., Rohn J. Sufficient conditions for regularity and singularity of interval matrices // SIAM J. Matrix Anal.Appl. 1999. Vol. 20, No. 2. - P. 437-445.

177. Ris F.N. Interval Analysis and Applications to Linear Algebra // PhD thesis. Oxford: Oxford University. -1972.

178. Rohn J. Systems of linear interval equations // Linear Algebra and Its Applications. 1989. -Vol. 126.-P. 39-78.

179. Rohn J. Checking positive definiteness or stability of symmetric interval matrices is NP-hard // Commentationes Mathematicae Universitatis Carolinae. 1994. Vol. 35, j 4. - P. 795797.

180. Rosen J.B. Park H. Glick J. Total least norm problems: formulation and solution // illUMSI reserch report. Minneapolis (Mn): Univ. of Minnesota. Supercomput. inst. 1993. - Vol. 93/223.- 18 p.

181. Rosen J.B. Park H. Glick J. Structured nonlinear total least norm problems// UMSI reserch report. Minneapolis (Mn): Univ. of Minnesota. Supercomput. inst. 1995. - Vol. 95/152. - 11 P

182. Rosen J.B. Park H. Glick J. Total least norm formulation and solution for structured problems // SIAM J. Matrix Anal. Appl. 1996. - Vol. 17, No.l. - P. 110-128.

183. Rosen J.B. Park H. Glick J. Total least norm for linear and nonlinear structured problems, Recent advances in total least squares techniques and errors-in-variables modeling. Ed. S. Van Huffel // SIAM. 1997. - P, 203-214.

184. Rosen J.B., Park H., Glick J. Structured total least norm for nonlinear problems // SIAM J. Matrix Anal. Appl. 1999. - Vol. 20, No. 1. - P. 14-30.

185. Rump S.M. Solving algebraic problems with high accuracy // A New Approach to Scientific Computation, U. Kulisch and W. Miranker eds. New York: Academic Press. 1983. -P. 51-120.

186. Rump S.M. Verification methods for dense and sparse systems of equations // Topics in Validated Computations. J. Herzberger ed. North-Holland. Amsterdam. 1994. - P. 63-135.

187. Rump S.M. Bounds for the componentwise distance to the nearest singular matrix // SIAM J. Matrix Anal. Appl.- 1997.-Vol. 18,j. l.-P. 83-103.

188. Schmidt E. Zur Theorie der linearen und nichtlinearen Integralgleichungen. 1. Teil: Entwicklung willktirlicher Funktionen nach Systemen vorgeschriebener // Math. Ann. 1907. -Vol. 63.-P. 433-476.

189. Seif N.P., Hassanein M.A., Deif A.S. Inverse problem of the interval linear system of equations // Computing. 1999. - Vol. 63, No. 2. - P. 185-200.

190. Stewart G.W. On the early history of the singular value decomposition // SIAM Rev. -1993. Vol. 35, No 4. - P. 551-566.

191. Van Huffel S. Analysis of the total least squares problem and its use in parameter estimation //PhD thesis, Dept. of Electr. Eng., K.U.Leuven, Belgium, June 1987.

192. Van Huffel S., Vandewalle J. Analysis and solution of the nongeneric total least squares problem // SIAM J. Matrix Anal. Appl. 1988. - Vol. 9, No. 2. - P. 360-372.

193. Van Huffel S., Vandewalle J., The Total Least Squares Problem: Computational Aspects and Analysis, Frontiers in Applied Mathematics series, Vol. 9, SIAM, Philadelphia, 1991.

194. Van Huffel S. On the significance of nongeneric total least squares problems // SIAM J. Matrix Anal. Appl.-1992.-Vol. 13,No l.-P. 20-35.

195. Vandewalle J. Linear concepts and methods for data processing // Lecture presentations on Belgian Francqui Chair 2001-2002 (http://www.cs.kuleuven.ac.be/~stefan), (http://www.etro.vub.ac.be/communications/Francqui2002/Francqui2002 page.htm)

196. Watson G.A. On a Class of Matrix Nearness Problems // Const. Approx. 1991. - No. 7. -P. 299-314.

197. Watson G.A. Data Fitting Problems with Bounded Uncertainties in the Data, SIAM J. Matrix Anal. Appl. 2001. - Vol. 22, No. 4. - P. 1274-1293.

198. Weyl H. Das asymptotische Vertielungsgesetz der Eigenwert linearer partieller Differentialgleichungen (mit einer Anwerndung auf der Theorie der Hohlraumstrahlung) // Math. Ann. 1912. - Vol. 71. - P. 441-479.

199. Zhu Wenwu, Wang Y., Galatsanos N.P., Zhang J. Regularized total least squares for nonconvolutional linear inverse problems // IEEE Transactions on Image Processing. 1999. -Vol. 8, No 11.-P. 1657-1661.