66 / 66 / 5
Регистрация: 12.03.2008
Сообщений: 392
|
|
1 | |
Сложность алгоритмов Гаусса и Крамера решения СЛАУ21.03.2010, 19:58. Показов 11332. Ответов 4
Метки нет (Все метки)
Прошу знающих людей объяснить мне какую вычислительную сложность имеют вышеуказанные методы и почему. Поиск в инете ничего не дал, т.к. там только указана сложность, а обоснования нет. Заранее спасибо.
0
|
21.03.2010, 19:58 | |
Ответы с готовыми решениями:
4
Метод Крамера и обратной матрицы для решения больших СЛАУ Решение СЛАУ-3 методом Гаусса (Крамера). Решить СЛАУ методом Крамера либо Гаусса Создать программу для решения СЛАУ методом Крамера |
бжни
2473 / 1684 / 135
Регистрация: 14.05.2009
Сообщений: 7,162
|
|
21.03.2010, 23:04 | 2 |
ответа прямо не знаю, но раз у тебя он есть, то можно прикинуть
сложность оценивают в колве операций умножений/сложений, соответственно для метода гаусса матрицы размерности n надо посмотреть сколько умножений сложений происходит при прямом, обратном ходе в методе крамера подобным же образом надо определить сложность вычисления n определителей величины nxn
0
|
5 / 5 / 3
Регистрация: 07.07.2013
Сообщений: 122
|
|
04.05.2016, 21:01 | 4 |
Norby, ,Смотри,чтобы выполнить линейное преобразование над вектором нужно N операций(по размерности вектора),чтобы выполнить метод Гаусса,нужно для каждого из N строк выполнить N-1 линейных преобразований(если приводим к диагональному виду)...
Итого получаем N(строк)*N-1(линейных операций)*N(сложность каждой линейной операции)=O(N^3-N^2)=O(N^3)
0
|
66 / 66 / 31
Регистрация: 11.03.2016
Сообщений: 252
|
|
04.05.2016, 22:01 | 5 |
Norby, вы как-то плохо искали Посмотрите на псведококод метода Гаусса и вы сможете точно подсчитать число операций в нём; в любом случае, асимптотически это - n проходов по строкам, потом ещё n и каждый раз n операций для вычитания ведущей строки. Метод Крамера - это искать определитель, а по определению определителя (да, такой вот каламбур, а телом бел) нужно n! операций. Даже самый экономный метод не посчитает определитель быстрее чем , так что затея эта гиблая.
0
|
04.05.2016, 22:01 | |
04.05.2016, 22:01 | |
Помогаю со студенческими работами здесь
5
Создать форму для решения СЛАУ методом Крамера Метод Крамера решения СЛАУ - функция работает неправильно Реализовать решения СЛАУ методом крамера для четырех уравнений Составить программу для решения методом Крамера СЛАУ 2×2 с произвольными целыми коэффициентами. Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |