Вопрос. Точнее, задачка.

Есть некоторое количество однородных линейных уравнений (уравнений в несколько раз больше, чем переменных), в которых коэффициенты известны лишь с сильным округлением. Т.е., например, первое ур-ние выполняется с коэффициентом при x1, равным 1,47268761, а нам он известен как 1. Решение существует - факт. Более того, существует даже целочисленное в небольших (в пределах 10 000) числах, но по большому счету переживу и нецелочисленное, без нормировки, все равно их бесконечно много. Переменных по порядку величины десяток, уравнений - два-три десятка.

Чем такое решать?

Методом наименьших квадратов? По-научному что-то с регрессией, точного названия не помню.


Вот:
http://ru.wikipedia.org/wiki/%D0%A0%D0%B5%...%BB%D0%B8%D0%B7

из того, что прямо щас взбрело в голову:
если матрица, скажем, положительно-определенная, то можно сформулировать как задачу линейного или целочисленного программирования -- получается интервальное решение.
если нет -- что-то подобное можно придумать, но прямо щас мне лень. :-)

если припрода коэффициентов в матрице стохастическая -- тогда еще проще, через процедуру робинса-монро.

Сделал методом быстрейшего спуска или как там он называется... В общем, беру числа, идейно не особо далекие от решения, смотрю, какие правые части получаются, считаю сумму квадратов правых частей, пробую каждую из переменных туда-сюда подвигать, смотрю, когда уменьшение суммы квадратов максимально, повторяю итерацию. Изредка уменьшаю шаг изменения переменных. Все отлично =)

2 SHiFT

косвенный намек на linprog?
можно и на матлабе пошаманить)

Не все так просто оказалось =( У системы есть куча "лишних" локальных минимумов, раскиданных по 9-мерному пространству решений... =(

В линале помнится упомянался метод регуляризайии Тихонова для отыскания решения линейной системы с приближенно заданной матрицей. Точночть решения соответствует точности задания матрицы. В книге Илиьна Поздняка по линалу должен быть либо метод описан либо ссылка дана.

Я чего-то не понимаю, но как у квадратичной функции оказалось более одного минимума? И зачем искать минимум квадратичной функции методом спуска? Он ведь определяется из линейного уравнения. Другое дело, что матрица этого уравнения может быть плохо обусловлена --- тут уж какие входные данные.