2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Матрица вопрос
Сообщение28.02.2010, 09:53 


31/08/09
183
Подскажите пожалуйста, вот дали задание.

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

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

 Профиль  
                  
 
 Re: Матрица вопрос
Сообщение28.02.2010, 10:59 
Заслуженный участник


11/05/08
32166
Задача довольно нетривиальна.

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

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

 Профиль  
                  
 
 Re: Матрица вопрос
Сообщение28.02.2010, 11:21 


31/08/09
183
Просто думал, что уже есть готовый код , чтобы пробегало по всем минорам, любой матрицы, но похоже такого кода нет?

 Профиль  
                  
 
 Re: Матрица вопрос
Сообщение28.02.2010, 12:42 
Заслуженный участник


11/05/08
32166
Готовый код -- это неспортивно.

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

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

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

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

 Профиль  
                  
 
 Re: Матрица вопрос
Сообщение28.02.2010, 17:52 


30/12/09
95
mycoding в сообщении #293207 писал(а):
Но вот как сделать алгоритм, чтобы перебирались все миноры начиная с самого большого до тех пор пока не найдётся не нулевой.
Можете подсказать.

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

 Профиль  
                  
 
 Re: Матрица вопрос
Сообщение28.02.2010, 18:51 
Заслуженный участник


11/05/08
32166
Roman Voznyuk в сообщении #293345 писал(а):
Короче говоря классическая задача на вычисление ранга матрицы.

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

 Профиль  
                  
 
 Re: Матрица вопрос
Сообщение28.02.2010, 22:59 


22/02/10
7
ewert
в общем, в учебной задаче обычно этим можно пренебречь :)

 Профиль  
                  
 
 Re: Матрица вопрос
Сообщение01.03.2010, 21:34 


31/08/09
183
А можно попросить написать код который любую квадратичную матрицу считает?
Если не трудно, хоть псевдо-код.

 Профиль  
                  
 
 Re: Матрица вопрос
Сообщение01.03.2010, 21:47 
Заслуженный участник


11/05/08
32166
mycoding в сообщении #293721 писал(а):
А можно попросить написать код который любую квадратичную матрицу считает?

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

 Профиль  
                  
 
 Re: Матрица вопрос
Сообщение03.03.2010, 08:18 


31/08/09
183
А может кто-нибудь помочь с кодом, который будет любую квадратную матрицу считать?
Просто одной из подзадач будет вычисление всех минора,
а минор это квадратная матрица, следовательно, надо будет проверить , что он не нулевой, т.е. вычислить определитель.

 Профиль  
                  
 
 Re: Матрица вопрос
Сообщение03.03.2010, 16:29 
Заслуженный участник
Аватара пользователя


01/08/06
3049
Уфа
ewert писал(а):
Матрицу невозможно "сосчитать" в принципе. Так же как и "решить" и т.п.. Постарайтесь выражаться яснее.
mycoding писал(а):
А может кто-нибудь помочь с кодом, который будет любую квадратную матрицу считать?
Характер стойкий, нордический :D

 Профиль  
                  
 
 Re: Матрица вопрос
Сообщение03.03.2010, 17:44 


31/08/09
183
Просто мне то прогу сдавать, а как её делать ???
Если нельзя подсчитать любую квадратную матрицу, то прога не делается?

 Профиль  
                  
 
 Re: Матрица вопрос
Сообщение05.03.2010, 16:04 


31/08/09
183
Подскажите пожалуйста, а вот как сделать так, если матрица не определена, то ...

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

 Профиль  
                  
 
 Re: Матрица вопрос
Сообщение05.03.2010, 19:38 
Заслуженный участник


11/05/08
32166
mycoding в сообщении #294845 писал(а):
Подскажите пожалуйста, а вот как сделать так, если матрица не определена, то ...Это делать директивами #ifndef ?


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

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 14 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group