Оценка сложности обращения матрицы?

Lika25

сабж
матрица произвольная n x n

kachokslava

В общем случае не быстрее O(N^3)
Если матрица ленточная, с шириной ленты M, то O(M^2*N)
Для ленточной матрицы имеется в виду не обращение, а решение СЛУ (что примерно эквивалентно)

kachokslava

Это точные методы.
Приближённые методы считают по-другому и там сложность (~количество арифметических операций) ~ ln(1/eps)*N^2
eps - нужная точность

Lika25

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

kachokslava

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

Lika25

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

a101

Есть еще методы для обращения разряженных матриц над полем Z_p. Работают за NM, где M - количество не нулей. Обощаются более-менее на кольца Z_K, для целых K с какими-то условиями...

Lika25

спасибо, но меня интересуют матрицы над R
может быть, я не совсем корректно сформулировал вопрос...
на примере: для сортировок есть теорема о сложности - нет алгоритма, который работал бы менее, чем за n log (n) операций (я точно не помню утв-е)
спрашивается, есть ли такая теорема для матриц?

spiritmc

А это разве не опровергли?
Или подразумеваются какие-то ограничения на операции?
---
...Я работаю антинаучным аферистом...

Lika25

если ты про сортировки, то не знаю... было на 2-м курсе, просто помню такую теорему (она вроде давалась с нормальным док-вом)
какие там ограничения не помню

a101

Имеются ввиду сортировки основанные на сравнении.
2Msan
Как я понимаю, тебе ответили. Минимальное количество ар. действий - O(n^3) для точного обращения матрицы. Что еще надо?

sfmike

Мне казалось что где-то в книге Голуба я читал про оценку O(n^(3-eps.

spiritmc

Ясно.
Довольно сильное ограничение.
---
...Я работаю антинаучным аферистом...

a101

Кто же спорит? Без него для целочисленных массивов действительно есть более быстрые (асимптотически) методы.

Lika25

мне надо, чтобы кто-нибудь кинул ссылку на соотв. теоремы как для точных, так и приближенных (!) методов
это нужно хотя бы, чтобы утверждения не были голословными
можно ограничиться решением СЛУ

NHGKU2

Про точные методы в книжке Богачёва "Практикум на ЭВМ. Методы решения линейных систем и нахождения собственных значений" есть вроде.

a101

Там только методы без доказательства, что асиимптотически быстрее никак.

Lika25

почти так
к каждому методу дается асс. оценка и объяснение (можно считать за док-во)
а оценки снизу для методов обращения нет

a101

Я это и имел ввиду Просто написал криво
Оставить комментарий
Имя или ник:
Комментарий: