PS Умные учебники по алгебре у меня, к сожалению, вывелись
PPS Пробовал найти инфу на сайтах приведенных в топике "Прежде чем изобретать велосипед" но тоже ни фига не нашел, хотя может плохо искал...
| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Нерекурсивное нахождение определителя матрицы |
| Автор: Royan 14.5.2004, 14:22 |
| Недавно появилось желание вернуться к старой проблеме. А именно найти определитель матрицы но не рекурсивно, а грубо говоря с помощью цикла. Пока идея у меня такова, только как ее реализовать, хотя вроде бы все кажется и очевидно, я не знаю: Имеем матрицу (к примеру 5х5): +++++ +++++ +++++ +++++ +++++ необходимо сначала перебрать все миноры (обозначены ноликами) размерностью 3х3, чтобы вычислить определитель первого минора рангом 3+1 то есть: +++++ +++++ +++++ +++++ +++++ ++ooo ++ooo ++ooo ++ooo +++++ ++ooo ++ooo ++ooo ++ooo +++++ ++ooo ++ooo ++ooo ++ooo +++++ потом для второго минора рангом 3+1 +++++ ++ooo ++ooo ++ooo +++++ +++++ +++++ +++++ ++ooo +++++ ++ooo ++ooo ++ooo ++ooo +++++ ++ooo ++ooo ++ooo ++ooo +++++ ну и так далее. Проблема в том, что нельзя допустить чрезмерного количества итераций. Для чего я исользую вектор "затенения", он содержит как раз идексы рядов, которые трогать не надо (или надо), то есть для рассмотренных выше случаев: 0 1 1 1 1 и соответственно 1 0 1 1 1 На первый взгляд все просто, но если ранг исходной матрицы сделать >5, то вычисление новых значений вектора "затенения" у меня вызывает проблемы. Может кто со свежей головой подкинет пару толковых идей, о том как вычислять вектор? |
| Автор: Akina 14.5.2004, 17:11 |
| Очень хочется спросить - а зачем? не нравится рекурсия - приводи матрицу к диагональному виду... |
| Автор: maxim1000 14.5.2004, 17:43 |
| обычно используется процедура Гаусса |
| Автор: achmed 14.5.2004, 20:14 |
| обычно, чтобы избавиться от рекурсии, я имитирую стек вызовов собственным стеком, т.е. берешь свою рукурсивную функцию и вместо вложенных вызовов складываешь текущую подматрицу (или структури описывающую эту подматрицу ссылаясь на исходную) в стек, ну и конечно нужно предусматреть спуск по стеку вызовов, вот и все. Хотя наверное можно обойтись без этого, через циклы, но все равно в принципе получится то же самое алгоритм вычисления через определители рекурсивный. |
| Автор: Royan 14.5.2004, 22:37 |
| Просто идея в голове родилась и захотелось воплотить ее в жизнь, просто таким алгоритмом можно будет раскрутить матрицу практически любой размерности |
| Автор: maxim1000 15.5.2004, 14:03 |
| можно конечно пользоваться и рекурсивным, но его сложность порядка n!, а сложность Гаусса порядка n^3 |
| Автор: Royan 16.5.2004, 12:58 |
| Пардон за глупый вопрос, а у кого нибудь есть алгоритм привдения матрицы к диаганальному виду или упомянутая выше maxim1000 процедура Гаусса... если будет еще и код, то тоже будте добры скиньте на мыло, а то приспичило мне... а в нете никак толком ничего и не найти PS Умные учебники по алгебре у меня, к сожалению, вывелись PPS Пробовал найти инфу на сайтах приведенных в топике "Прежде чем изобретать велосипед" но тоже ни фига не нашел, хотя может плохо искал... |
| Автор: maxim1000 16.5.2004, 15:43 |
| на форуме был не один вопрос по этой теме кратко можно описать так: определитель матрицы не изменится, если к строке прибавить другую строку, умноженную на какое-нибудь число берут первую строку и прибавляют ее к остальным с такими множителями, чтобы в первом столбце получались нули вот и получается первый столбец с одним единственным ненулевым коэффициентом на первом месте на это тратится порядка n*n операций во втором столбике оставляется ненулевой коэффициент на втором месте, и т.д. для всех n столбцов, получается порядка n*n*n операций... |
| Автор: DenDen 16.5.2004, 21:29 |
| Есть очень простой алгоритм, который просто нужным образом ставит перестановки. Припишем к исходной матрице n*n снизу еще 1 такую же матрицу. получится матрица n*2n Теперь давайте. Давайте пойдем по первому столбцу вниз перемножая Элементы стоящие на диагоналях получившейся матрицы(начиная с главной) до последнего элемента исходной матрицы. Получившиеся произведения сложим. Теперь возьмем последний столбец и пойдем вниз но уже влево также перемножая элементы и складвывая произведения. Вычтем из первой суммы вторую получим определитель. Почему-то начиная с матриц 3*3 этот алгоритм работает.Сложность 2*sqrt(2)*n*n |
| Автор: maxim1000 17.5.2004, 11:39 | ||
такое ощущение, что на матрицах 3*3 его корректная работа и заканчивается... порисовал немного для матрицы 4*4 не нашел такой перестановки: (1,1) (2,3) (3,2) (4,4) |
| Автор: DenDen 17.5.2004, 16:50 |
| Х.з. я когда развлекался с ним просто создавал матрицы произвольного разменра(с разными слуайными числвами) и считал их с помощью гаусса и этой хрени, получалось что сходятся. Мой друган пытался это доказать, что-то у него получилось, но м.б. он просто ХОТЕЛ, чтобы у него чего-то получилось....вообщем у меня он пока работал, а так... |
| Автор: Royan 17.5.2004, 21:24 | ||
Я наверно тупой но я не понял эту фразу, то есть например имеем: a++++ | +a+++ | ++a++ | - матрица А +++a+ | ++++a | b++++ | +b+++ | ++b++ |- ее дубликат, назовем её А' +++b+ | ++++b | То есть получили a*b + a*b + a*b + a*b + a*b а далее как идти вниз? |
| Автор: DenDen 17.5.2004, 23:09 |
| не совсем a_1 a_2 a_3 a_4 a_5 a_6 a_7 a_8 a_9 a_10 a_11 a_12 a_13 a_14 a_14 a_16 b_1 b_2 b_3 b_4 b_5 b_6 b_7 b_8 b_9 b_10 b_11 b_12 p_1=a_1*a_6*a_11*a_16 p_2=a_5*a_10*a_14*b_4 p_3=a_9*a_14*b_3*b_8 |
| Автор: Royan 18.5.2004, 19:13 |
| а тот факт, что ты забил только три строки матрицы b_N это так и задумано или все-таки надо все четыре? |
| Автор: DenDen 19.5.2004, 09:42 |
| Нет, надо, конечно все 4 и еще 4 с другого бока |
| Автор: achmed 19.5.2004, 10:09 |
| да, если использоать алгоритм гауса (преобразование к треугольному виду), нужно помнить про точность машинных вычислений, ИМХО для больших размерностей лучше юзать символьные вычисления. |
| Автор: Royan 21.5.2004, 09:51 | ||
| То есть вот так, a_1 a_2 a_3 a_4 a_5 a_6 a_7 a_8 a_9 a_10 a_11 a_12 a_13 a_14 a_14 a_16 b_1 b_2 b_3 b_4 b_5 b_6 b_7 b_8 b_9 b_10 b_11 b_12 b_13 b_14 b_14 b_16
Чего-то я не понял, с какого бока ты же сказал дописать только снизу а пока выходит так: P1_1=a_1*a_6*a_11*a_16 P1_2=a_5*a_10*a_15*b_4 P1_3=a_9*a_14*b_3*b_8 P1_4=a_13*b_2*b_7*b_12 P1_5=b_1*b_6*b_11*b_16 P1_6=b_5*b_10*b_15 P1_7=b_9*b_14 P1_8=b_13 P2_1=a_4*a_7*a_10*a_13 P2_2=a_8*a_11*a_14*b_1 P2_3=a_12*a_15*b_2*b_5 P2_4=a_16*b_3*b_6*b_9 P2_5=b_4*b_7*b_10*b_13 P2_6=b_8*b_11*b_14 P2_7=b_12*b_15 P2_8=b_16 Хотя я не уверен, что P1_6 -- P1_7 и P2_6 -- P2_7 следует вычислять.... Sum_1 = P1_1 + P1_2 + P1_3 + P1_4 + P1_5 + P1_6 + P1_7 + P1_8 Sum_2 = P2_1 + P2_2 + P2_3 + P2_4 + P2_5 + P2_6 + P2_7 + P2_8 И соответственно Det = Sum_1 - Sum_2 |
| Автор: Sined 21.5.2004, 19:25 | ||||
Наскольео я понял надо вычислять только
и
|