решение СЛАУ методом итераций, вопрос

[R.Deyanov]

Всем привет,
кто подскажет метод/алгоритм итерационного решения недоопределенной СЛАУ - число строк порядка 256*256/4, число неизвестных порядка 256*256
(прямые методы - QR, SVD, модификации псевдообращения, регуляризации по Тихонову не катят - перепробовал). Для переопределенной или (n,n) понимаю - могу использовать классику.

Спасибо.
Рамиль.

[PAV]

Перенесено из CS в математический раздел

[svv]

Те методы, которые Вы пробовали, не катят по какой причине? Считаются медленно или точность низкая?
Если низкая точность, может, дело в матрице -- матрица плохая?

[dvorkin_sacha]

R.Deyanov

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

[R.Deyanov]

svv в сообщении #383687 писал(а):

Те методы, которые Вы пробовали, не катят по какой причине? Считаются медленно или точность низкая?
Если низкая точность, может, дело в матрице -- матрица плохая?

спасибо з авнимание.

Матрица А точная(после квадратур). Очевидно ядро вырождено. Заказчик саму функцию(ядро) не показывают (О, великие физики...), но, при этом допускают распространенную ошибку - мельчат сетку.

У них есть точное(модельное) решение, с ним сравнивают полученные результаты.
svd и регуляризация дают 5% - их не устраивает.
по времени svd пилит 1,5 часа - не устраивает.
с регуляризацией добился времени менее 1мин. (честно обращал матрицу 2561*2561, потом справа умножал ею на транспонированную 10201*2561)
Теперь надо итерить полученное решение к 0.5-1%
думаю как итерить систему с недоопределенной матрицей и хорошим приближением
надо покопаться с методом Ньютона

[dvorkin_sacha]

R.Deyanov в сообщении #383780 писал(а):

Очевидно ядро вырождено.

Это понятно.

R.Deyanov в сообщении #383780 писал(а):

Матрица А точная(после квадратур)... Заказчик саму функцию(ядро) не показывают (О, великие физики...), но, при этом допускают распространенную ошибку - мельчат сетку.

Как это точное, если нет формул, и Вы, как я понял, вынуждены пользоваться 2-ой точностью.

R.Deyanov в сообщении #383780 писал(а):

svd и регуляризация дают 5% - их не устраивает.
по времени svd пилит 1,5 часа - не устраивает.
с регуляризацией добился времени менее 1мин. (честно обращал матрицу 2561*2561, потом справа умножал ею на транспонированную 10201*2561)
Теперь надо итерить полученное решение к 0.5-1%

Что за программу svd использовали, что она у Вас так медленно "пилит"? Да и с регуляризацией тоже со скоростью проблемы. Судя по Вашим предварительным результатам, переход к четверной точности решит все проблемы без всяких итераций. Разумеется, для увеличения скорости расчета желательно использовать распараллеливание: матричные операции Вашего типа прекрасно распараллеливаются.

[dvorkin_sacha]

dvorkin_sacha в сообщении #383807 писал(а):

переход к четверной точности решит все проблемы без всяких итераций.

Грамотно реализованный алгоритм с четверной точностью будет работать быстрей, чем Ваш алгоритм регуляризации с двойной точностью.

[R.Deyanov]

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

но, чтобы не оставаться в долгу, на днях выложу на свой сайт и матрицу А(весит 300мегов), и правую часть, и точное решение - попробуете(используя четверную точность) для спортивного интереса получить гладкое решение быстро(без распаралл.) - 1-2мин., и лучше 0.5%

почему 0.5% ? - это я уже проитерил от 5.5% к 0.5%, но, за 4мин. (домашний комп, 2.94GHz).
Буду дожимать.

[мат-ламер]

R.Deyanov. Из Ваших постов я не понял, была ли у вас попытка воспользоваться просто каким-нибудь итерационным методом мез регуляризации. Например, решение системы линейных уравнений можно свести к задаче наименьших квадратов. Явно матрицы можно не умножать. А уж полученную задачу наименьших квадратов решать методом сопряжённых градиентов. Понятно, что он не сойдётся к единственной точке. Но ведь невязки сойдутся к нулю (т.е. минимизируемый функционал сойдётся к нулю).

[dvorkin_sacha]

R.Deyanov

Что касается точности, то здесь не все так однозначно. Про svd так и не врубился: выложите входные данные, попробую и его применить. Можете и сами воспользоваться пакетом NAG - его последние версии выложены на просторах интернета.

[R.Deyanov]

мат-ламер в сообщении #384402 писал(а):

R.Deyanov. Из Ваших постов я не понял, была ли у вас попытка воспользоваться просто каким-нибудь итерационным методом мез регуляризации. Например, решение системы линейных уравнений можно свести к задаче наименьших квадратов. Явно матрицы можно не умножать. А уж полученную задачу наименьших квадратов решать методом сопряжённых градиентов. Понятно, что он не сойдётся к единственной точке. Но ведь невязки сойдутся к нулю (т.е. минимизируемый функционал сойдётся к нулю).

ну, если $Ax=b$ слева умножить на $A'$, то - да, получим квадратную СЛАУ и можно итерить хоть классикой, хоть по Арнольди, Чебышеву - и нет проблем кроме сходимости и времени счета.
Но у меня недоопределенная система 2561*10201 (далее размерность увеличится в разы). Поэтому приводить ее к квадратной 10201*10201 и итерить неохота.
Сопряженные направления очень легко идут в разнос, тем более, что $AA'$ ранга меньше чем 2561 (по методу холесского).
На данный момент сделал три варианта решения задачи: 0.5%, 3.99%, 4%. Первый хорош и по времени, но заказчик упорно не хочет присутствия минимизации(боится локальных минимумов на реальных данных).
Поэтому, хочу еще поупираться с $Xk+1=F(A,A',b)*Xk+f(b)$ для недоопределенной СЛАУ.

-- Вт дек 07, 2010 20:38:26 --

dvorkin_sacha в сообщении #384403 писал(а):

R.Deyanov

Что касается точности, то здесь не все так однозначно. Про svd так и не врубился: выложите входные данные, попробую и его применить. Можете и сами воспользоваться пакетом NAG - его последние версии выложены на просторах интернета.

лично я svd для этой задачи не гонял и не буду - безнадежно: нет критерия обрубания малых сингулярных. Коллеги с этим подходом так и застряли.

свои результаты как и обещал вскорости выложу на сайте, просто жалко время на оформление
но, данные, пожалуйста -можете скачать:
http://math-lab.ru/slau/x0.zip - точное модельное решение, с чем сравнивать что получите
http://math-lab.ru/slau/b.zip - правая часть
http://math-lab.ru/slau/A.zip - матрица А(2561*10201) (ужал до 8мегов)

матр. А они записали по идиотски: столбцами в строки по 101элементу.

о, кстати, готов купить пакет NAG (в разумных пределах; у нас в универе вместо зарплаты выдают свободным временем) - плиииииииииз!

[dvorkin_sacha]

R.Deyanov

скачал: в выходные посмотрю и отпишусь.

P.S.
NAG в инете совершенно бесплатный и под фортран и под C.

Ясно, почему исходные данные так хорошо сжались: там почти одни нули. Но если не хотят давать формулу, то хотя бы в нормальном виде данные представили: в бинарнике.

[R.Deyanov]

dvorkin_sacha в сообщении #384832 писал(а):

R.Deyanov
Но если не хотят давать формулу, то хотя бы в нормальном виде данные представили: в бинарнике.

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

"P.S.
NAG в инете совершенно бесплатный и под фортран и под C.
"
- извините, а у Вас есть ссылка именно на бесплатные варианты? - я не нашел.
Если не сложно, скиньте плиз.

-- Чт дек 09, 2010 11:47:35 --

dvorkin_sacha в сообщении #384832 писал(а):

R.Deyanov

Ясно, почему исходные данные так хорошо сжались: там почти одни нули.

я совершенно уверен, что матрица ленточная - знать бы структуру, обратить ее можно было бы в ноль секунд.

[dvorkin_sacha]

R.Deyanov

Скиньте Ваше мыло ко мне в личку.