Поиск линейно-зависимых уравнений

[Alik]

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

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

[photon]

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

[Alik]

Я, как человек в меру ленивый, хочу чтобы это была пара команд MATLAB-а и все

[Vassil]

Если не покажется слишком сложно, будет у Вас желание и найдёте как то

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

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

[Vassil]

По линку

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-а, быть может для других подобных задач.

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

[maxal]

Vassil писал(а):

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

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

[Alik]

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
буду очень признателен за помощь.

[Alik]

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

[K-3]

Долго думал писать это, или это и так понятно:

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

[Alik]

Не очень понял, Николай, что такое "угловые клетки", очевидно имеется ввиду столбец в котором есть единица, а все остальное ноль.

Цитата:

Долго думал писать это, или это и так понятно...

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

А вообще, благодарствую, метод действительно работает, возьмем пример из указанной книжки:

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

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

[abc_qmost]

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

[K-3]

Alik:

Цитата:

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

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

abc_qmost:

Цитата:

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

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

[Alik]

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
Помогите пожалуйста со ссылками

[K-3]

Пусть у нас есть векторы $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$.

[Alik]

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