решение проблемы плохой обусловленности для обращения матриц

[buker]

Добрый день!
пишу работу и столкнулся со следующей проблемой -
разработан один статистический алгоритм, но для его реализации необходимо нахождение большого количества обратных матриц (а именно матриц ковариаций).
В теории все замечательно и просто, но вот на практике, при использовании MATLAB'а сталкиваюсь постоянно с проблемой плохой обусловленности этих самых матриц, а именно система постоянно выдает сообщения типа:Warning: Matrix is close to singular or badly scaled.Results may be inaccurate. RCOND = xxx
Таким образом выходит, что мои результаты могут быть далеки от правды...

Для разрешения ситуации придумал использовать следующий подход:
1. задать некоторое малое eps
2. если rcond(A) меньше этого eps, то вместо обращения матрицы $A$ рассматривать псевдообратную $A^+$

И вот теперь возникло у меня два вопроса:
1. в каком случае погрешность может быть больше: при использовании псевдообратной матрицы или при использовании обращенной матрицы с плохой обусловленностью? т.е. грубо говоря, что "лучше"?
2. существуют ли "механизмы" преобразования матрицы для "улучшения" её обусловленности - данную мысль, в частности, навеяли функция balance и топик http://dxdy.ru/topic9740.html

Заранее благодарен за помощь

[ewert]

buker в сообщении #605855 писал(а):

(а именно матриц ковариаций).
В теории все замечательно и просто, но вот на практике, при использовании MATLAB'а сталкиваюсь постоянно с проблемой плохой обусловленности этих самых матриц, а именно система постоянно выдает сообщения типа:Warning: Matrix is close to singular or badly scaled.Results may be inaccurate. RCOND = xxx

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

[AlexValk]

По вашим вопросам:
1. Преимущество использования псевдообратной матрицы по сравнению с обратной в случае плохой обусловленности задачи - устойчивость результата. Например, если обусловленность матрицы $10^6$, то в при изменении в 6-й значащей цифре одного из элементов матрицы, это может привести к изменению в элементах обратной матрицы в первой значащей цифре (что обычно делает ответ практически неприемлимым). Для псевдообратной матрицы такое же изменение элементов исходной матрице приведет к изменению элементов псевдообратной примерно в 6-й значащей цифре (или чуть хуже).
2.Инструменты для "улучшения" обусловленности матрицы: псевдообратная матрица, метод главных компонент, метод оптимального прореживания, метод регуляризации и др.
Методы главных компонент и оптимального прореживания борются с упомянутой ewert проблемой линейной зависимости (или, что чаще имеет место на практике почти линейной зависимостью,см. Мультиколлинеарность), отбрасывая зависимые величины, оставляя только линейно-независимый "базис", эффективно понижая размерность задачи. Общая идея метода главных компонент - отбросить малые (по тому или иному принципу) собственные числа матрицы ${\bf A}$ (которые для симметричной матрицы неотрицательны), заменив их на ноль, и работать только с в которой отличны от нуля только оставшиеся главные собственные числа.

Про метод регуляризации, применительно к задаче обращения матрицы ${\bf A}$, скажу подробнее - он мне кажется наиболее подходящим к вашей задаче. В нем предлагается заменить ("некорректную" при высокой обусловленности ${\bf A}$) задачу решения системы ${\bf A}{\bf X}={\bf E}$ на ("корректную" при всех ${\bf A}$) задачу минимизации $\|{\bf A}{\bf X}-{\bf E}\|^2+\gamma \|{\bf X}-{\bf X}_0\|^2\xrightarrow[{\bf X}]{} \min$, где ${\bf X}_0$ - "априорная оценка" решения ${\bf X}$ (если ее нет, то обычно берут ${\bf X}_0={\bf 0}$), а скалярный параметр $\gamma>0$ - параметр регуляризации (о его выборе - ниже). Итоговое "регуляризовонное" решение имеет вид

$${\bf X}_\mathrm{reg}=({\bf A}^T{\bf A}+\gamma {\bf E})^{-1}({\bf A}^T+\gamma {\bf X}_0)$$

Если ${\bf X}_0={\bf 0}$, то в пределе $\gamma\to +0$ получим псевдообратную матрицу ${\bf X}_\mathrm{reg}={\bf A}^+$. (В вашем случае симметричной матрицы, естественно, ${\bf A}^T={\bf A}$.)
Метод регуляризации по сравнению с методом псевдообратной матрицы дает возможность более гибко влиять на результат, управляя параметром $\gamma$ (а также учитывать априорную информацию о предполагаемом решении через ${\bf X}_0$, если таковая имеется). Чем больше $\gamma$ - тем выше устойчивость решения, но тем больше и отличие регуляризованной задачи от исходной. Поэтому общий принцип подбора параметра регуляризации - брать минимально необходимое $\gamma$ или чуть больше. На практике в качестве $\gamma$ может выступать величина порядка квадрата абсолютной допустимой ошибки в ответе ${\bf X}$ или несколько меньшая величина (тут могут помочь численные эксперименты). (В литературе по методам регуляризации описаны автоматизированные процедуры подбора $\gamma$).

В заключение: метод регуляризации применительно к задаче анализа матриц ковариаций случайных величин называется для случая ${\bf X}_0={\bf 0}$ ридж(или гребневой)-регрессией. Современный обзор этого и других методов можно посмотреть, например, в Методы выбора регрессионных моделей.

[buker]

ewert в сообщении #605927 писал(а):

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

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

-- Вт авг 14, 2012 23:28:09 --

прежде всего огромное спасибо за столь подробный и полезный ответ

AlexValk в сообщении #606002 писал(а):

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

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

P.S.Обязательно отпишусь по факту проведенных экспериментов, чтобы помочь возможно последователям

-- Ср авг 15, 2012 00:04:23 --

поискал в литературе и нашел довольно простой и логичный способ нахождения параметра регуляризации - т.н. квазиоптимальный метод. Суть его состоит в минимизации функции невязки, зависящей от величины параметра регуляризации $\gamma$. Таким образом необходимо решить две задачи минимизации. Данное решение, очевидно более ресурсозатратное, чем метод псевдообратных