Критерий "похожести" СЛАУ

[oleg777]

У меня есть хорошо запрограммированный проекционный алгоритм для решения СЛАУ (размерности m*n, m не обяз-но равно n), формируемых для оценки параметров физического процесса.
Матрицы получаются изрядной размерности, расчеты "жрут время" и для быстрого поиска решения хотелось бы подавать на вход проекционного алгоритма "хороший" стартовый вектор решений.
Так как часто получается система уравнений, очень похожая на какую-то из уже просчитанных, хотелось бы подавать на вход алг-ма старое решение, сохраненное в базе данных.

Вопрос: какой критерий лучше использовать, чтобы можно было делать вывод типа "решение для похожей СЛАУ уже есть в базе"?

[ewert]

А есть ли смысл?... Итерационные методы всё равно медленно работают. Тогда какая разница -- будет ли относительная погрешность начального приближения порядка одного процента или порядка единицы?

[oleg777]

ewert в сообщении #713959 писал(а):

А есть ли смысл?... Итерационные методы всё равно медленно работают. Тогда какая разница -- будет ли относительная погрешность начального приближения порядка одного процента или порядка единицы?

Наверное, метод является итерационным не в том смысле, какой Вы имеете в виду.
Алгоритм такой:
1. Наблюдаем n единиц времени за m параметрами процесса
2. Формируем СЛАУ n на m и решаем ее.
3. Наблюдаем еще k ед. времени. Решаем СЛАУ из n последних уравнений. Для решения СЛАУ используем предыдущее решение.
4. И т.д.

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

[oleg777]

Короче говоря, программа должна работать по такому алгоритму:

1. Не решали ли мы уже похожую СЛАУ?

2. Если решали - немного ее дорешаем.

3. Если не решали - решим ее с нуля.

[Aritaborian]

oleg777 в сообщении #714009 писал(а):

немного ее дорешаем

Что значит «немного дорешаем»?

[oleg777]

Aritaborian в сообщении #714044 писал(а):

oleg777 в сообщении #714009 писал(а):

немного ее дорешаем

Что значит «немного дорешаем»?

Наш проекционный алгоритм должен получить на входе ориентировочный вектор решения.

Используя решение для СЛАУ, похожей на нашу, применим наш алгоритм к нашей СЛАУ.

[Alex_J]

oleg777

Что вы знаете о треугольных матрицах?
Возможно, какие-то из "бумажных" методов упрощения матриц вам помогут.
Вопросик интересный кстати.

-- 22.04.2013, 15:10 --

Похожесть матриц можно сформулировать на основе определителей, характера линейной зависимости строк, столбцов и т.д.

А как вы ищете решение для $n\neq m$?

[oleg777]

Alex_J в сообщении #714056 писал(а):

oleg777

Что вы знаете о треугольных матрицах?
Возможно, какие-то из "бумажных" методов упрощения матриц вам помогут.
Вопросик интересный кстати.

-- 22.04.2013, 15:10 --

Похожесть матриц можно сформулировать на основе определителей, характера линейной зависимости строк, столбцов и т.д.

А как вы ищете решение для $n\neq m$?

О треуг. матрицах мало чего знаю, так, на уровне человека, когда-то получившего специальность "инженер-математик". Гы...

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

[Alex_J]

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

[oleg777]

Re: Вопросик интересный кстати.


Вопросик реальный и чиста конкретный, из разряда "What, on earth, should I like to do...". Практический то есть.

[Aritaborian]

Что за фривольности, да ещё и с ошибками?
А вообще, максимально эффективные алгоритмы решения СЛАУ давно уже известны и реализованы в разных пакетах. Хотите изобретать велосипед? Пожалуйста.

[oleg777]

Re: А вообще, максимально эффективные алгоритмы решения СЛАУ давно уже известны и реализованы в разных пакетах.

Вы и вправду так думаете? Не все с Вами согласны, см. arxiv.org :)

К тому же, речь идет не просто о том, чтобы "быстро решить СЛАУ" (с этим я давно худо-бедно разобрался), а чтобы создать базу данных для решений определенного типа СЛАУ.

[Aritaborian]

oleg777 в сообщении #714109 писал(а):

Не все с Вами согласны, см. arxiv.org :)

Возможно. Но самые крутые алгоритмы рано или поздно включаются в самые крутые программы ;-)

oleg777 в сообщении #714109 писал(а):

создать базу данных для решений определенного типа СЛАУ

Вот это, пожалуйста, поясните. Если выражение «определенный тип СЛАУ» я ещё как-то могу понять, то что такое «база данных для решений определенного типа СЛАУ» я понять не в состоянии.

[oleg777]

Aritaborian в сообщении #714110 писал(а):

oleg777 в сообщении #714109 писал(а):

Не все с Вами согласны, см. arxiv.org :)

Возможно. Но самые крутые алгоритмы рано или поздно включаются в самые крутые программы

oleg777 в сообщении #714109 писал(а):

создать базу данных для решений определенного типа СЛАУ

Вот это, пожалуйста, поясните. Если выражение «определенный тип СЛАУ» я ещё как-то могу понять, то что такое «база данных для решений определенного типа СЛАУ» я понять не в состоянии.

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

P.S. Проверял "вручную": если подаешь "на вход" что надо, решение находится за существенно меньшее время.

[oleg777]

Спасибо всем за умные советы. Собственно, я собираюсь сделать базу данных решений в "умном" формате, например, в таком: mathenglish.ru/taiga/