2014 dxdy logo

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

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




 
 Матрица вопрос
Сообщение28.02.2010, 09:53 
Подскажите пожалуйста, вот дали задание.

Дана матрица A. Найти в ней ненулевой минор максимального размера. В случае, если таких миноров несколько, напечатать любой из них.

Как понял, предположим матрица 6, 7.
Т.е. максимальный размер минора 6 на 6?
А если он равен 0, т надо перебрать остальные более маленькие. Но вот как сделать алгоритм, чтобы перебирались все миноры начиная с самого большого до тех пор пока не найдётся не нулевой.
Можете подсказать.

 
 
 
 Re: Матрица вопрос
Сообщение28.02.2010, 10:59 
Задача довольно нетривиальна.

Перебирать все миноры, конечно, -- занятие неблагодарное. Лучше привести матрицу к ступенчатому виду методом Гаусса (можно обойтись без перестановок). Тогда для искомого минора набор первых индексов образуют номера строк, оставшихся ненулевыми. А набор вторых индексов -- это номера первых ненулевых элементов тех строк.

Но тут появляется техническая проблема, и обойти её никак не удастся (вообще ни при каком способе решения не удастся). Если использовать арифметику с плавающей точкой, то возникает вопрос: что считать нулём? Если же арифметика целочисленная, то числа будут довольно быстро возрастать, и очень велика вероятность переполнения.

 
 
 
 Re: Матрица вопрос
Сообщение28.02.2010, 11:21 
Просто думал, что уже есть готовый код , чтобы пробегало по всем минорам, любой матрицы, но похоже такого кода нет?

 
 
 
 Re: Матрица вопрос
Сообщение28.02.2010, 12:42 
Готовый код -- это неспортивно.

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

Теперь дополните её двумя вещами. Во-первых, заставьте её продублировать вычисление многократно -- не только по какой-то одной строке, а по всем задействованным. Во-вторых: если вычисление даст ненулевой результат, то пусть она выведет свои входные аргументы во вспомогательные переменные (например, глобальные) -- при условии, что уже хранящиеся в этих вспомогательных переменных данные отвечают минору меньшего размера.

Теперь запустите эту процедуру в цикле по всем минорам верхнего уровня (если матрица квадратная,то -- просто один раз ко всей матрице). На выходе в тех вспомогательных массивах окажутся индексы одного из ненулевых миноров наибольшего порядка.

(Хранить массив индексов можно по-разному: можно как именно индексы, а можно как булевский массив с флажками "задействован/не задействован". Второе, кажется, эффективнее, хотя не уверен; давно такими вещами не баловался.)

 
 
 
 Re: Матрица вопрос
Сообщение28.02.2010, 17:52 
mycoding в сообщении #293207 писал(а):
Но вот как сделать алгоритм, чтобы перебирались все миноры начиная с самого большого до тех пор пока не найдётся не нулевой.
Можете подсказать.

Метод Гаусса с запоминанем перестановок строк. Как только упретесь в линейную зависимость строк (деление на нуль) так сразу переставив строки найдете положение этого ненулевого минора.
Короче говоря классическая задача на вычисление ранга матрицы.

 
 
 
 Re: Матрица вопрос
Сообщение28.02.2010, 18:51 
Roman Voznyuk в сообщении #293345 писал(а):
Короче говоря классическая задача на вычисление ранга матрицы.

, которая вычислительно некорректна -- ввиду погрешностей округления.

 
 
 
 Re: Матрица вопрос
Сообщение28.02.2010, 22:59 
ewert
в общем, в учебной задаче обычно этим можно пренебречь :)

 
 
 
 Re: Матрица вопрос
Сообщение01.03.2010, 21:34 
А можно попросить написать код который любую квадратичную матрицу считает?
Если не трудно, хоть псевдо-код.

 
 
 
 Re: Матрица вопрос
Сообщение01.03.2010, 21:47 
mycoding в сообщении #293721 писал(а):
А можно попросить написать код который любую квадратичную матрицу считает?

Нельзя категорически. Матрицу невозможно "сосчитать" в принципе. Так же как и "решить" и т.п.. Постарайтесь выражаться яснее.

 
 
 
 Re: Матрица вопрос
Сообщение03.03.2010, 08:18 
А может кто-нибудь помочь с кодом, который будет любую квадратную матрицу считать?
Просто одной из подзадач будет вычисление всех минора,
а минор это квадратная матрица, следовательно, надо будет проверить , что он не нулевой, т.е. вычислить определитель.

 
 
 
 Re: Матрица вопрос
Сообщение03.03.2010, 16:29 
Аватара пользователя
ewert писал(а):
Матрицу невозможно "сосчитать" в принципе. Так же как и "решить" и т.п.. Постарайтесь выражаться яснее.
mycoding писал(а):
А может кто-нибудь помочь с кодом, который будет любую квадратную матрицу считать?
Характер стойкий, нордический :D

 
 
 
 Re: Матрица вопрос
Сообщение03.03.2010, 17:44 
Просто мне то прогу сдавать, а как её делать ???
Если нельзя подсчитать любую квадратную матрицу, то прога не делается?

 
 
 
 Re: Матрица вопрос
Сообщение05.03.2010, 16:04 
Подскажите пожалуйста, а вот как сделать так, если матрица не определена, то ...

Это делать директивами #ifndef ?
Попробовал, что-то не получается.

 
 
 
 Re: Матрица вопрос
Сообщение05.03.2010, 19:38 
mycoding в сообщении #294845 писал(а):
Подскажите пожалуйста, а вот как сделать так, если матрица не определена, то ...Это делать директивами #ifndef ?


А-а, я, кажется понял, это просто была такая шутка юмора.

(невозможно поверить, что человек непонимает (именно так, слитно) разницы между вырожденными матрицами и не определёнными явно системными переменными. Ну т.е. типа между козлами в огороде и бузиной в Киеве)

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


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