решение системы линейных уравнений асимптотика скорости

[erwins]

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

[xmaister]

(Оффтоп)

Я, конечно, плохо разбираюсь в этих делах, но могу посоветовать "C.Bender S. Orszag Advanced mathematical methods for scientists and engineers", мб поможет .

[erwins]

Чем проще вопрос тем дольше молчание....

[Circiter]

2erwins

Цитата:

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

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

[Евгений Машеров]

Существуют методы быстрого обращения матриц, основанные на алгоритмах быстрого умножения матриц (Штрассена и др.). С практической точки зрения они на реально встречающихся размерностях матриц неэффективны, уменьшение показателя степени p в выражении для сложности с 3 до 2.808 с учётом роста коэффициента при $n^p$ окажется полезным только при росте размерности до десятков тысяч, причём численная устойчивость сильно проигрывает.
http://mathworld.wolfram.com/StrassenFormulas.html
Однако системы уравнений такого размера на практике решаемы, только если у них есть разреженность (и тогда чаще решают итеративно), регулярность коэффициентов (например, матрица циркулянтная) или она выражается через матрицы меньшей размерности.

[erwins]

Цитата:

Евгений Машеров]

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

[Hi4ko]

Ну, асимптотика метода Гаусса $O(n^3)$
Метод Крамера: $O(n^4)$ в среднем, в лучшем случае $O(n^3)$
Ну т.е всё-таки минимальная асимптотика будет $O(n^3)$, просто нигде не встречал за "квадрат" даже