2014 dxdy logo

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

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




 
 Решение нестандартных СЛАУ (несовместные / переопределенные
Сообщение18.01.2006, 15:47 
Я на факультете слышал о решении систем, когда количество уравнений превосходит количество неизвестных или систем вида: x+y=1; x+y=2
Если кто знает, подскажите, в какой литературе можно найти об этом :?:

 
 
 
 
Сообщение18.01.2006, 19:50 
Приведенная вами система не имеет решений. Было бы интересно посмотреть, как кто-нибудь будет ее решать.

 
 
 
 
Сообщение18.01.2006, 20:37 
Аватара пользователя
Возможно имеется в виду задача о максимальной разрешимой подсистеме. Но эта задача NP-полна.

 
 
 
 
Сообщение18.01.2006, 20:55 
Dan_Te писал(а):
Приведенная вами система не имеет решений. Было бы интересно посмотреть, как кто-нибудь будет ее решать.


Методом наименьших квадратов можно искать решение, наименее уклоняющееся от прямых. У меня воспоминание, что об этом я читал у Гельфанда в "Лекциях по линейной алгебре". Возможно, я ошибаюсь.

 
 
 
 
Сообщение18.01.2006, 22:02 
Аватара пользователя
V.V. писал(а):
Методом наименьших квадратов можно искать решение, наименее уклоняющееся от прямых.

Если речь идет о минимизации |Ax-b| для несовместной системы уравнений Ax=b, то проще это делать через псевдообратную матрицу.

 
 
 
 
Сообщение19.01.2006, 11:07 
Система уравнений, в которой число уравнений превышает число неизвестных, называется переопределенной.
Ее решают методом Гаусса. В процессе решения становится понятно, имеет система решения или нет.
В первом случае выявляются и отбрасываются линейно зависимые уравнения и остаются только линейно
независимые, число которых не превышает число неизвестных; во втором - приходим к несовместной системе.
Если же речь идет о "решении" несовместных систем, то сначала надо определить, что это такое.

 
 
 
 
Сообщение19.01.2006, 11:20 
Аватара пользователя
Скорее всего подразумевается наилучшее приближение. В стандартной метрике (см. пост maxal'а) это равносильно отысканию решения совместной системы $A'Ax = A'b$ (штрих - это транспонрование). Если возникающая здесь матрица Грама окажется вырожденной, то это наилучшее решение будет не единственным.

 
 
 
 
Сообщение21.01.2006, 04:44 
Все правильно. Когда выбирается подлежащий минимизации функционал |Ax - b|, тем самым дается определение "решения" несовместной системы Ax=b. А функционал можно выбирать по-разному. Слова "наилучшее приближение" позволяют обратиться к геометрической интерпретации. И если под стандартной метрикой понимать евклидову, то можно еще кое-что обсудить.
Каждое уравнение системы Ax=b задает плоскость. Пусть задача имеет единственное решение - точку пространства, самую близкую к этим плоскостям в смысле функционала |Ax - b|. Функционал является длиной вектора y=Ax-b в евклидовой метрике. Решение задачи будет минимизировать и квадрат функционала, т.е. сумму квадратов компонент вектора y.
Далее, умножение допустим первого уравнения системы Ax=b на не равное нулю число не изменит положения первой плоскости и вся геометрическая "картинка" останется без изменений. Однако это изменит значение функционала в найденной оптимальной точке x - увеличит или уменьшит квадрат первой компоненты вектора y. Малое смещение из точки x к или от первой плоскости приведет к уменьшению длины вектора y, а задача будет иметь другое оптимальное решение, что не удивительно, раз изменился функционал.
Но из геометрических представлений логичнее, чтобы решение задачи - наилучшее приближение - не менялось при таких изменениях системы Ax=b, которые не меняют геометрической "картинки". Логичнее, чтобы сумма квадратов расстояний от оптимальной точки до плоскостей была наименьшей. Хода решения это не изменит, изменит только функционал, в котором строки матрицы А должны быть отнормированы.

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


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