2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

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

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

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



Начать новую тему Ответить на тему
 
 решение проблемы плохой обусловленности для обращения матриц
Сообщение13.08.2012, 23:35 


02/02/09
53
Добрый день!
пишу работу и столкнулся со следующей проблемой -
разработан один статистический алгоритм, но для его реализации необходимо нахождение большого количества обратных матриц (а именно матриц ковариаций).
В теории все замечательно и просто, но вот на практике, при использовании 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

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

 Профиль  
                  
 
 Re: решение проблемы плохой обусловленности для обращения матриц
Сообщение14.08.2012, 09:51 
Заслуженный участник


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

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

 Профиль  
                  
 
 Re: решение проблемы плохой обусловленности для обращения матриц
Сообщение14.08.2012, 14:04 
Аватара пользователя


09/08/11
137
СПб
По вашим вопросам:
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}$ ридж(или гребневой)-регрессией. Современный обзор этого и других методов можно посмотреть, например, в Методы выбора регрессионных моделей.

 Профиль  
                  
 
 Re: решение проблемы плохой обусловленности для обращения матриц
Сообщение14.08.2012, 22:11 


02/02/09
53
ewert в сообщении #605927 писал(а):
Скорее всего это означает, что между какими-то из случайных величин есть прямая линейная зависимость. Найдите собственные числа такой матрицы, и если самые маленькие из них отличаются от остальных на много порядков -- значит, так оно и есть.

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

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

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

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


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

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

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

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 4 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group