Методы численного решения СЛАУ (большие матрицы)

[d.dragon.n76]

Существует ли алгоритм выбора метода решения СЛАУ?

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

И задумался, на какие методы смотреть: прямой, итерационный, вариационный? Какой конкретно выбрать? Решать придется системы от 200X200 до 10000X10000.

[d.dragon.n76]

хе, не думал что масштабирование так влияет.

Решаю систему x=Ax+f, попробовал поступить так ax=aAx+af, затем x=x-ax+aAx+af и при a>0.1 и a<0.9 наблюдаю резкое уменьшение числа итераций. Например, при 200X200 вместо 1133 итерации при a=1; 24 итерации при a=0.5. Где бы почитать (на уровне человека знающего "вышку") об оптимальном подборе коэф. масштабирования a или способа минимизации спектрального радиуса матрицы?

Правда норма всеравно больше 1. Это не страшно?

[AndreyXYZ]

Что такое норма? В чем заключаются прямой, итерационный и вариационный методы и в чем их основные отличия? Итерация --- это то же самое, что и преобразование матрицы (умножение строки на число, прибавление одной строки к другой)?
Я знаю только метод приведения СЛАУ к трапециевидной форме? при котором число преобразований равно

$$(n-1)+(n-2)+(n-3)+\ldots 1=\frac{n(n-1)}{2}$$

Как называется такой метод?

[Really]

d.dragon.n76 в сообщении #171391 писал(а):

Решаю систему x=Ax+f, попробовал поступить так ax=aAx+af, затем x=x-ax+aAx+af и при a>0.1 и a<0.9 наблюдаю резкое уменьшение числа итераций. Например, при 200X200 вместо 1133 итерации при a=1; 24 итерации при a=0.5. Где бы почитать (на уровне человека знающего "вышку") об оптимальном подборе коэф. масштабирования a или способа минимизации спектрального радиуса матрицы?

Это не масштабирование. Это называется SOR (successive over relaxation). Немного об этом
есть в Голуб, Ван Лоун "Матричные вычисления". Но если я не ошибаюсь, то за полным
описанием верхних релаксаций он отсылает к какой-то книге Янга по итерационным методам.
Точнее сейчас не могу сказать, ибо нет под рукой.

[d.dragon.n76]

1. К сожалению Голуб, Ван Лоун не смог найти в сети и скачать

2. скачал книгу Петров И.Б., Лобанов А.И. Лекции по вычислительной математики. В ней во второй лекции говорится об итерационных методах, в частности на стр. 56 о методе минимальных невязок. Причем никаких ограничений на исходную СЛАУ не накладывается.

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

[Really]

d.dragon.n76 в сообщении #171486 писал(а):

1. К сожалению Голуб, Ван Лоун не смог найти в сети и скачать

На английском очень легко найти. http://www.poiskknig.ru/cgi-bin/poisk.cgi?lang=ru&st=Golub&network=1 - вторая в списке Golub G.H. van Loan C.F. Matrix Computations.

d.dragon.n76 в сообщении #171486 писал(а):

Я правильно понимаю. что метод минимальных невязок не накладывает никаких ограничений на матрицу A

Не накладывает. А вот сходиться будет не всегда. Это зависит от подбора итерационных параметров.

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

[vitecer]

Методом Гаусса СЛАУ 200х200 решаются в "лёт" (точность максимально возможная, т.к. метод точный), а вот большая СЛАУ размером 10000х10000 решается очень долго на Athlon'е 64 3500+ заняло 4:33:12 часа (для расчетов использовал свою программу в которой реализован метод Гаусса включающий поиск и размещение на главной диагонали максимального элемента матрицы на каждом из N этапов расчета с дополнительной функцией итерационного уточнения корней по тому же методу). Очень часто встречаются ссылки на метод Ланцоша, его программная реализация (как я видел общий алгоритм) не сложна, можно попробовать написать самому или использовать возможности математических программ.

[yasya17]

d.dragon.n76 в сообщении #171010 писал(а):

Существует ли алгоритм выбора метода решения СЛАУ?

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

И задумался, на какие методы смотреть: прямой, итерационный, вариационный? Какой конкретно выбрать? Решать придется системы от 200X200 до 10000X10000.

Такое ощущение, что не существует пакетов программирования для работы с матрицами...
Матлаб запросто такие системы решит хоть матричным хоть Гауссовым методом...
Команды в Матлабе:
X = A\B; и X = rref([A B]); для метода Гаусса,
где A - матрица коэффициентов, а В - столбец свободных членов.

[nestoklon]

yasya17 в сообщении #310085 писал(а):

Такое ощущение, что не существует пакетов программирования для работы с матрицами...

Вот и выросло новое поколение... Про Lapack хоть раз слышали? Там правда никаких окошек...

[Ajabsandal]

d.dragon.n76 в сообщении #171010 писал(а):

Существует ли алгоритм выбора метода решения СЛАУ?

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

И задумался, на какие методы смотреть: прямой, итерационный, вариационный? Какой конкретно выбрать? Решать придется системы от 200X200 до 10000X10000.

Если спектр собственных значений матрицы действительный и определенный, то весьма эффективен метод Чебышевских ускорений итераций с оптимальным набором параметров. Ваши задачи не очень большие, в физике реакторов Чеб.итер. решают и 100000х100000.

[мат-ламер]

Численное решение таких больших плотно заполненных систем - задача сложная. Слышал о таком методе (возможно предложил Н.Шор). Систему линейных уравнений заменяют задачей чебышевского приближения. Т.е. минимизируют максимальную невязку. Получается задача негладкой оптимизации. К ней можно применить метод субградиента. Подробности поищите в книге Поляка Б.Т. Введение в оптимизацию. Либо в какой-либо книге Шора Н. Попробую завтра на работе в Матлабе проэкспериментировать.

[AlexNew]

В матлабе 10000х10000 решаются просто
методом LU декомпозиции, если матрица разряженная начиная с версии 6 используется новый алгорит толи с Lapack толи еще от куда, (matlab это всеголишь интерфейс к подобным алгоритмам написаным на C)

Аx=b
вот например LU декомпозиции для плотной матрицы матрицы А (для sparse есть другой)
[L,U,P]=lu(A,т)
с перестоновкой строк/столбцов так чтобы избежать накопления ошибок
(t ∈ [0,1] - pivoting treshold for permutation)

дальше просто
PA=LU
PAx=Pb
LUx=Pb
c=Pb
y=L\c
x=U\y

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

[мат-ламер]

Прошу моё предыдущее сообщение о методе субградиента не принимать во внимание. Эксперименты показали его медленную работу. Зато в Матлабе посредством косой черты легко решались системы до 4000*4000 (30 секунд). Дальше начинались тормоза, вызванные нехваткой памяти. Если решать систему 10000*10000, то надо памяти гигабайта полтора. Плохо показал себя итерационный метод бисопряжённых градиентов (Ланцоша?).

[nestoklon]

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

Плохо показал себя итерационный метод бисопряжённых градиентов (Ланцоша?).

Вы просто не умеете их готовить (с).
Эти два метода имеют между собой мало общего. Предназначены для разного, используются в разных случаях.

И пару слов о общей теории "крупными мазками". Для плотных (я надеюсь, правильно перевёл dense) матриц как правило прямые методы работают лучше. Потому что один фиг $n^2$. Итерационные начинают сильно выигрывать на сильно разреженных матрицах, когда прямые методы тривиально перестают работать.
Поэтому пожалуйста уточняйте что за матрицы вы решали. Нет алгоритмов, которые одинаково хорошо решают все задачи.

[Ajabsandal]

AlexNew в сообщении #312196 писал(а):

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

Если посмотреть в ретроспективе эту проблему то увидим, что именно стремление избежать матричных операций и продвинуло итерационные методы. Если еще вспомним, что в начале 70-х самая мощная отечественная ЭВМ - БЭСМ-6 имела всего 32768 машинных слов оперативной памяти, то становится очевидным невозможность (да еще и при той надежности электроники) решать важные и сложные задачи. Например, рассчитывать реактор АЭС (т.е. решать уравнение диффузии нейтронов). Даже 3-х слойный (устойчивый) метод Чебышевских ускорений накладывал жесткие ограничения на расчеты из-за памяти ЭВМ. Прорыв был сделан, когда проф. В.И. Лебедев в ИАЭ им. И.В. Курчатова разработал устойчивый 2-х слойный метод ускорений итераций с Чебышевским набором параметров. При этом СССР опередил другие страны в построении программ расчета водоохлаждаемых реакторов, хотя американские ЭВМ существенно превосходили советские.
Детали таких методов хорошо описаны в книге:
"Г. И. Марчук, В. И. Лебедев. Численные методы в теории переноса нейтронов. - М.: Атомиздат, 1971. "
К сожалению, сейчас многие уповают на вычислительную мощь и огромную память компьютеров и не ищут таких же (как нашел Лебедев), элегантных решений трудных задач