Как написать программу для вычисления определителя матрицы размером NxN?
Пробовал перебором коэффициентов, получалось только до 4-го порядка, да и то со знаками были некоторые несоответствия.
На крайняк хотелось бы подсчитать определитель трехдиагональной матрицы.

Здравствуйте tolij, Вы писали:

T>Как написать программу для вычисления определителя матрицы размером NxN?

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

Юра.

Здравствуйте tolij, Вы писали:

T>Как написать программу для вычисления определителя матрицы размером NxN?

Через алгебраические дополнения. В чем проблема? Формулы есть во всех учебниках по алгебре, в Куроше например.

Здравствуйте tolij.

Сделайте так: разложите по строке или столбцу, и получится рекурсивная процедурка вычисления определителя, при каждом вызове которой (или серии вызовов) порядок будет понижаться. Остается добавить, что определитель матрицы 1х1 есть сам элемент а(1,1).
Не факт, что данный способ самый эффективный, но своей простотой он мне понравился.
Могу прислать исходники.

Здравствуйте bo, Вы писали:

bo>Сделайте так: разложите по строке или столбцу, и получится рекурсивная процедурка вычисления определителя, при каждом вызове которой (или серии вызовов) порядок будет понижаться. Остается добавить, что определитель матрицы 1х1 есть сам элемент а(1,1).
bo>Не факт, что данный способ самый эффективный, но своей простотой он мне понравился.
bo>Могу прислать исходники. :shuffle:

Есть классическая приколка.
число Фибоначчи
int F(n) { return n < 2 ? 1 : F(n-1) + F(n-2); }

Вопрос: чему равно O( F(n) ), то есть сколько раз вызовется функция?
Понятно, что глубина стека будет n
А вот время вычислений...

Ответ: O( F(n) ) = F(n)
Потому что в конечном счете (если развернуть выражение)
все сведется к F(n) = F(1)+F(0)+F(1)+F(1)+F(0).... = 1+1+....

Так что — аккуратнее с рекурсией!

Здравствуйте bo, Вы писали:

bo>Здравствуйте tolij.

bo>Сделайте так: разложите по строке или столбцу, и получится рекурсивная процедурка вычисления определителя, при каждом вызове которой (или серии вызовов) порядок будет понижаться. Остается добавить, что определитель матрицы 1х1 есть сам элемент а(1,1).
bo>Не факт, что данный способ самый эффективный, но своей простотой он мне понравился.
bo>Могу прислать исходники.

Сложность будет n! — хорошо, если при N=20 посчитает...

Здравствуйте Кодт, Вы писали:

К>Вопрос: чему равно O( F(n) ), то есть сколько раз вызовется функция?
К>Понятно, что глубина стека будет n
К>А вот время вычислений...

К>Ответ: O( F(n) ) = F(n)
К>Потому что в конечном счете (если развернуть выражение)
К>все сведется к F(n) = F(1)+F(0)+F(1)+F(1)+F(0).... = 1+1+....

К>Так что — аккуратнее с рекурсией!

Я полностью с Вами согласен, Кодт. С каждым вызовом порядок будет уменьшаться на один и кол-во вызовов сведется к факториалу. Но вопрос не в этом. Надо ли многоуважаемому tolij замороки, приводя матр. к диагонали стандартным гауссом или еще чем-либо?
Наверняка ведь зачетная неделя на носу, а доброму профессору надо показать классик CMatrix, да еще что бы он правильно посчитал действия над матрицами размером 4х4. Все такие были...
Так что вовсе не обязательно хитрить, можно иногда и "влоб" задачку решить, нагляднее будет...

Здравствуйте tolij, Вы писали:

T>Как написать программу для вычисления определителя матрицы размером NxN?
T>Пробовал перебором коэффициентов, получалось только до 4-го порядка, да и то со знаками были некоторые несоответствия.
T>На крайняк хотелось бы подсчитать определитель трехдиагональной матрицы.

Поищите по сети -- задача стандартная.

Есть такой метод: методом Гаусса привести матрицу к треугольной, а затем посчитать произведение диагональных элементов. Это будет определитель, умноженный на какое-то число. Число должно считаться по ходу гауссовых преобразований — ведь известно, во сколько раз каждое преобразование изменяет определитель матрицы.

Если про "число" непонятно, могу рассказать подробнее.

Здравствуйте tolij, Вы писали:

T>Как написать программу для вычисления определителя матрицы размером NxN?
T>Пробовал перебором коэффициентов, получалось только до 4-го порядка, да и то со знаками были некоторые несоответствия.
T>На крайняк хотелось бы подсчитать определитель трехдиагональной матрицы.

Для справки — основным инженерным алгоритмом расчета определителя матрицы, является алгоритм сведения матрицы к треугольной и перемножение элементов главной диагонали. Как одну из реализаций используют метод LU-разложения с выбором ведущего элемента для повышения точности. Расчитывать же определитель через дополнения программно —
откровенная глупость, при порядке матрицы 15 — 20 это просто неприемлимо.

Здравствуйте tolij, Вы писали:

T>Как написать программу для вычисления определителя матрицы размером NxN?
T>Пробовал перебором коэффициентов, получалось только до 4-го порядка, да и то со знаками были некоторые несоответствия.
Самый оптимальный метод: по Гаусу с приведением к треугольной + выбор ведущего элемента, при выборе ведущего надо считать число перестановок, чтоб знак определить. Да! Матрица может оказать вырожденной... Надо по ходу отслеживать.
T>На крайняк хотелось бы подсчитать определитель трехдиагональной матрицы.
Для трёхдиагональных матриц существует метод разностной прогонки, является одним из самых эффективных. В книжицах по численному должен быть описан.

Здравствуйте, bo, Вы писали:

К>>Так что — аккуратнее с рекурсией!

bo>Я полностью с Вами согласен, Кодт. С каждым вызовом порядок будет уменьшаться на один и кол-во вызовов сведется к факториалу. Но вопрос не в этом. Надо ли многоуважаемому tolij замороки, приводя матр. к диагонали стандартным гауссом или еще чем-либо?
bo>Наверняка ведь зачетная неделя на носу, а доброму профессору надо показать классик CMatrix, да еще что бы он правильно посчитал действия над матрицами размером 4х4. Все такие были...
bo>Так что вовсе не обязательно хитрить, можно иногда и "влоб" задачку решить, нагляднее будет...

Алгоритм:
Проверить порядок матрицы (и то что она квадратная). Если порядок равен 1,то вернуть единственный элемент.
Если 2,3,4,можно даже 5 — вычислить по формуле (вывести не сложно).
Если > 5 — случайно сгенерировать ответ, всё равно препод проверять не будет.

Здравствуйте, Кодт, Вы писали:

К>Ответ: O( F(n) ) = F(n)
К>Потому что в конечном счете (если развернуть выражение)
К>все сведется к F(n) = F(1)+F(0)+F(1)+F(1)+F(0).... = 1+1+....

только
O( F(n) ) = F(n + 1)
для F(2) надо же 2 вызова сделать, вернее 3, но сам F(2) пойдет на асимптотику

Здравствуйте, sadomovalex, Вы писали:

S>Здравствуйте, Кодт, Вы писали:

К>>Ответ: O( F(n) ) = F(n)
К>>Потому что в конечном счете (если развернуть выражение)
К>>все сведется к F(n) = F(1)+F(0)+F(1)+F(1)+F(0).... = 1+1+....

S>только
S>O( F(n) ) = F(n + 1)
S>для F(2) надо же 2 вызова сделать, вернее 3, но сам F(2) пойдет на асимптотику

F(n) <= F(n+1) <= 2 * F(n)

Так что это одно и то же

Здравствуйте, Иванков Дмитрий, Вы писали:

ИД>Здравствуйте, sadomovalex, Вы писали:

S>>Здравствуйте, Кодт, Вы писали:

К>>>Ответ: O( F(n) ) = F(n)
К>>>Потому что в конечном счете (если развернуть выражение)
К>>>все сведется к F(n) = F(1)+F(0)+F(1)+F(1)+F(0).... = 1+1+....

S>>только
S>>O( F(n) ) = F(n + 1)
S>>для F(2) надо же 2 вызова сделать, вернее 3, но сам F(2) пойдет на асимптотику

ИД>F(n) <= F(n+1) <= 2 * F(n)

ИД>Так что это одно и то же

для "O( F(n) )" да, для "сколько раз вызовется функция" нет