Какие более эффективные методы решения больших систем (например 10000x10000 и более) численные (Зейделя) или точные (Гаусса, Холецкого) с точки зрения времени счета, занимаемой машинной памяти и точности в конечном счете?  

Кажется, эти вопросы в свое время подробно обсуждались при разработке фортрановских библиотек (linpack).  

Это сообщение отредактировал(а) nostromo - 17.4.2006, 14:35

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

для разных видов разреженных систем есть разные способы решения 

Вырождение, в смысле, -- оно решается путем выбора ведущего элемента по строкам и по столбцам.

    

Немного прокоменчу. Все методы численные и все неточные на машине ввиду округлений. Здесь методы делят на прямые и итерационные. Прямые обычно больше учитывают структуру матрицы, но требуют обычно и больше памяти. Например, Гаусса потребует места для хранения всей матрицы. Итерационные более универсальные, но стрктуру матрицы учитывают в меньшей степени. Не портят разреженный вид матрицы, решение получается итерационным способом. Наконец, в "последнее" время все большую популярность получают неявные прямые методы, или "итерационно-прямые": действуют как итерационные, но на каждой итерации решается прямым методом какая-то более простая система.
Если размер матрицы большой, например, для указанной матрицы потребуется 763 Мб, то следует использоватьь итерационные методы, которые потребую хранения только ненулевых элементов и не нарушат структуру матрицы. Все еще зависит от того, откуда произрастает матрица -- очень часто из уравнений мат физики, a la дифуры в частных производных. Для некоторых их видов, например, матрица будет иметь специальный вид и решаться эффективно одним из прямых методов, учитывающих эту структуру.
Для симметричных систем советую использовать метод сопряженных градиентов или т.н. чебышевский, но последний нужно будет подкручивать. Для несимметричных такой вопрос еще не решен, но можно попробовать аналог МСГ -- биортогональный алгоритм. Правда он сходится довольно таки странно.
Во всех итерационных случаях рекомендуется использовать предобуславливание. К сожалению, нормальных книг, где это было бы "популярно" расписано я не встречал. 

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


матрица - один из способов записи линейного отображения - когда f(x+y)=f(x)+f(y) и f(a*x)=a*f(x) для векторных пространств
и если Гаусс манипулирует коэффициентами матрицы, то для некоторых других методов достаточно, чтоб им дали указатель на функцию, которая берет вектор x и возвращает Ax, а как она их вычисляет, для метода абсолютно все равно

можно представить себе такую задачу: у нас есть матрица, которая при действии на вектор сдвигает все его компоненты на 1 вниз, а последний ставит наверх
задача сформулирована для размерности, скажем, тысяча
что нужно? решить Ax=b, как обычно
для использования Гаусса нужно записать матрицу полностью, что потребует миллиона ячеек
при том, любой программист напишет простенькую функцию, которая будет занимать сотню байт... 

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


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

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

В принципе, конечно, можно, имея функцию f(x)=Ax получить все ее коэффициенты, но Гаусс использует кучу таких коэффициентов, которые надо хранить в памяти, а итерационные методы - вычисляют иногда всего один раз, и памяти для хранения этого результата (вектора) надо порядка N, а не N^2, как в Гауссе... 

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


Часто по многу, но зато не заполняют нулевые элементы, в этом их основное преимущество для разряженных систем. 

Ещё как возможно .... просто нужно перед тем как делать треуголное численное разложение нужно найти хорошую перестановку P. Для этого существует специальный класс алгоритмов которые ищат приемлемые по качеству перестановки исходя из графа матрицы или из самой матрицы.
После того ка перестановка найдена .. делаеться след. замена:

C = P*A*PT и   вектор D = b*P

А потом уже решаеться система:

C*X = D

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

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