2014 dxdy logo

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

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




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

 
 
 
 Re: решение системы линейных уравнений асимптотика
Сообщение23.10.2011, 00:32 
Аватара пользователя

(Оффтоп)

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

 
 
 
 Re: решение системы линейных уравнений асимптотика
Сообщение26.10.2011, 13:24 
Чем проще вопрос тем дольше молчание....

 
 
 
 Re: решение системы линейных уравнений асимптотика
Сообщение26.10.2011, 13:36 
2erwins
Цитата:
существует ли метод решения системы линейных уравнений быстрее чем куб?

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

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

 
 
 
 Re: решение системы линейных уравнений асимптотика
Сообщение26.10.2011, 14:40 
Цитата:
Евгений Машеров]
спасибо. Интересена именно минимальная оценка для решения системы. Причем даже если алгоритм не возможно построить.

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

 
 
 [ Сообщений: 7 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group