2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Поиск линейно-зависимых уравнений
Сообщение20.12.2007, 01:12 
Аватара пользователя


05/02/06
387
Подскажите пожалуйста как в MATLAB сделать следующее:

Имеется система из скажем 100 линейных уравнений, число неизвестных при этом - всего 10.
Требуется найти все (90) линейно-зависимые уравнения (строчки в матрице коэффициентов), исключить их и сформировать новую матрицу.
Понятно, что вычисление ранга матрицы даст 10, нечто похожее - rref(A) produces the reduced row echelon form.
Требуется, однако, указать на номера зависимых строк.

 Профиль  
                  
 
 
Сообщение20.12.2007, 01:22 
Экс-модератор
Аватара пользователя


23/12/05
12046
Хм, а их же можно выбрать различными способами

 Профиль  
                  
 
 
Сообщение20.12.2007, 01:27 
Аватара пользователя


05/02/06
387
Я, как человек в меру ленивый, хочу чтобы это была пара команд MATLAB-а и все :)

 Профиль  
                  
 
 Для индустриальных целей, было указан способ ...
Сообщение20.12.2007, 11:38 


03/09/05
217
Bulgaria
Если не покажется слишком сложно, будет у Вас желание и найдёте как то

J. Gondzio, Presolve analysis of linear programs prior to applying an interior point method, INFORMS Journal on Computing 9, No 1, Winter 1997, 73-91

то думаю можно аналогичным способом попробовать сделать.

 Профиль  
                  
 
 Еще одна ссылка ...
Сообщение21.12.2007, 15:39 


03/09/05
217
Bulgaria
По линку

http://ioe.engin.umich.edu/people/fac/b ... oph1-0.pdf

легко найти вступление интересного е-самоучителя, озаглавленного

Computational and Algorithmic Linear Algebra and n-Dimensional Geometry

Он разработан проф. Katta G. Murty

На стр. 14 вопросного pdf-а сказано, что далее в е-самоучителе указано как можно получить т.наз. "сертификаты" линейно-зависимых строк и столбцов системы линейных уравнений (т.е. соответствующие коэффициенты линейной комбинации строк или столбцов). Рассмотрены и эффективные способы сделать этого при решении реальных больших задач.

Упоминается использование MATLAB-а, быть может для других подобных задач.

Не знаю можно ли и как прочитать остальные части е-самоучителя?

 Профиль  
                  
 
 Re: Еще одна ссылка ...
Сообщение21.12.2007, 17:00 
Модератор
Аватара пользователя


11/01/06
5660
Vassil писал(а):
Не знаю можно ли и как прочитать остальные части е-самоучителя?

Вот тут он весь: http://ioe.engin.umich.edu/people/fac/b ... r_algebra/

 Профиль  
                  
 
 
Сообщение24.12.2007, 15:29 
Аватара пользователя


05/02/06
387
Vassil, maxal, спасибо за идею и ссылки!

Я тут разбирался с пошаговой реализацией команды rref под названием rrefmovie(A)
http://lcvmwww.epfl.ch/~lcvm/linalg/exo ... refmovie.m

сейчас пытаюсь на этой основе сделать Memory Matrix GJ Elimination
описанный в разделе 4.11 пособия, страницы 68-72
http://ioe.engin.umich.edu/people/fac/b ... oph1-4.pdf
буду очень признателен за помощь.

 Профиль  
                  
 
 
Сообщение25.12.2007, 23:13 
Аватара пользователя


05/02/06
387
Сейчас только обратил внимание, что треть из коэффициентов - нули, т.е разновидность sparse matrix. Насколько эффективны предложенные алгоритмы в этом случае я не знаю, но это и не критично. :)

 Профиль  
                  
 
 
Сообщение27.12.2007, 20:59 


10/11/06
64
Долго думал писать это, или это и так понятно:

Достаточно транспонировать матрицу и выполнить все ту же команду rref. Столбцы, где будут угловые клетки этой самой reduced echelon form (по-русски, приведенная ступенчатая матрица) и есть те самые линейно независимые. Понятно, что здесь будут мешать ошибки округления, но можно попытаться решить проблему настройкой параметра tol в rref(A,tol).

 Профиль  
                  
 
 
Сообщение27.12.2007, 23:03 
Аватара пользователя


05/02/06
387
Не очень понял, Николай, что такое "угловые клетки", очевидно имеется ввиду столбец в котором есть единица, а все остальное ноль.
Цитата:
Долго думал писать это, или это и так понятно...

Откуда следует, что метод должен указывать на индексы независимых строк? :?
Можно попросить источник (желательно английский) на который можно сослаться?

А вообще, благодарствую, метод действительно работает, возьмем пример из указанной книжки:
Код:
A=[   
    -1     0     1     1     2;
     1    -1     2    -1     1;
     1    -2     5    -1     4;
     2     0     0    -2     1;
     3    -2     5    -3     5;
     5    -2     5    -5     6;]

транспонирование матрицы даст
Код:
B=A'
    -1     1     1     2     3     5
     0    -1    -2     0    -2    -2
     1     2     5     0     5     5
     1    -1    -1    -2    -3    -5
     2     1     4     1     5     6

reduced echelon form которой
Код:
rref(B)
     1     0     1     0     1     1
     0     1     2     0     2     2
     0     0     0     1     1     2
     0     0     0     0     0     0
     0     0     0     0     0     0

посморим что написано в ответе на стр. 78
http://ioe.engin.umich.edu/people/fac/b ... oph1-4.pdf
когда строки оригинальной матрицы обозначены сверху вниз как R1-R6
redundant constraints are
Код:
R3 (-1, -2, 1, 0, 0, 0)
R5 (-1, -2, 0, -1, 1, 0)
R6 (-1, -2, 0, -2, 0, 1)

so that
Код:
R3 = R1 + R2.
R5 = R1 + 2R2 + R4
R6 = R1 + 2R2 + 2R4

Будем считать это подарком к Новому Году :D, с Наступающим!!!
P.S. в моем, частном случае для новой матрицы есть условие:
из зависимых строк нужно выбрать ту, которая содержит наибольшее число нулей...

 Профиль  
                  
 
 Re: Поиск линейно-зависимых уравнений
Сообщение28.12.2007, 15:39 


05/08/07

194
Для корректного решения такого типа задач в общем случае более всего подходит сингулярный анализ. Ведь это компьютерная математика с неизбежными ошибками округления.

 Профиль  
                  
 
 
Сообщение29.12.2007, 10:43 


10/11/06
64
Alik:
Цитата:
Откуда следует, что метод должен указывать на индексы независимых строк?
Можно попросить источник (желательно английский) на который можно сослаться?

Наверное, можно указать на любой учебник по линейной алгебре

abc_qmost:
Цитата:
Для корректного решения такого типа задач в общем случае более всего подходит сингулярный анализ. Ведь это компьютерная математика с неизбежными ошибками округления.


Полностью согласен, но иногда и обычный Гаусс работает, если правильно выбрать tol.

 Профиль  
                  
 
 
Сообщение26.01.2008, 02:23 
Аватара пользователя


05/02/06
387
K-3, я честно искал в интернете и в книгах которые у меня есть, а это
Demmel "Applied Numerical Linear Algebra"
Kiusalaas "Numerical methods in engineering with Matlab"
Mathews, Fink "Numerical Methods Using MATLAB"
on-line книга Jim Hefferon "Linear Algebra"
ftp://joshua.smcvt.edu/pub/hefferon/book/book.pdf
какие-то намеки то, почему Ваш метод работает
не находится ничего, кроме разве что вот этого
rational-echelonize-via-solve algorithm
http://www.informatik.uni-bremen.de/cgi ... a-over-gfq
Помогите пожалуйста со ссылками

 Профиль  
                  
 
 
Сообщение26.01.2008, 19:00 


10/11/06
64
Пусть у нас есть векторы $a_1, a_2,\dots,a_n,a_{n+1}$ и $a_{n+1}$ линейно выражается через остальные, т.е. для некоторых $\alpha_1,\alpha_2,\dots,\alpha_n$ верно, что $a_{n+1} = \alpha_1a_1 + \alpha_2a_2 +\dots+ \alpha_na_n$. Как бы мы нашли коэффициенты $\alpha_1,\alpha_2,\dots,\alpha_n$? Наверное, записали бы соответствющую систему линейных уравнений с неизвестными $\alpha_1,\alpha_2,\dots,\alpha_n$ и решили ее. Столбцы матрицы этой системы - это $a_1, a_2,\dots,a_n$, правая часть - $a_{n+1}$, неизвестные - $\alpha_1,\alpha_2,\dots,\alpha_n$. Решать будем методом исключения Жордана, т.е. приведением матрицы системы к виду $(E \mid a')$, где $E$ - единичная матрица, а $a'$ - это столбец из найденных значений $\alpha_1,\alpha_2,\dots,\alpha_n$.

 Профиль  
                  
 
 
Сообщение27.01.2008, 02:24 
Аватара пользователя


05/02/06
387
Насколько я понимаю эти альфы это значения rref, выполненной над транспонированной матрицей коэффициентов. Только все равно не ясно почему отличающиеся от единицы альфы показывают на зависимые уранения первоначальной системы.
Я понимаю, когда долго занимаешся в некоторой области, многие решения приходят интуитивно, но я так пока не умею и всего лишь хочу книжку. :)

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 19 ]  На страницу 1, 2  След.

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



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

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


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

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