ВВЕДЕНИЕ
Численное решение СЛАУ – одна из наиболее часто встречающихся задач в научно-технических исследованиях. Такая задача возникает в математической физике (численное решение дифференциальных и интегральных уравнений), экономике, статистике. При этом прикладные задачи часто требуют решения больших и сверхбольших СЛАУ с числом неизвестных более 1000. К таким СЛАУ, например, приводит численное решение двумерных и особенно трехмерных задач математической физики, в которых условия физической и геометрической аппроксимации двумерной и трехмерной области диктуют использование достаточно мелкой расчетной сетки с большим числом расчетных узлов по линейному размеру.
Существующие библиотеки программ на языках высокого уровня, разработаны на основе, так называемых, прямых методов решения СЛАУ, типа метода Гаусса и его модификаций. Число арифметических операций умножения для численного решения СЛАУ размерностью с помощью прямого метода - . Кубическая зависимость числа арифметических операций от размера матрицы СЛАУ приводит при к нереально большому времени решения даже на самых современных ЭВМ. Кроме того, время решения несоразмерно возрастает при использовании прямых методов в случае по причине недостаточности объема оперативной памяти для хранения данных задачи.
Итерационные методы решения СЛАУ намного экономнее, как по машинному времени решения, так и по использованию оперативной памяти. Так, если итерационный метод является быстро сходящимся с числом итераций , то время решения, пропорциональное уже квадрату размера матрицы ~ , оказывается существенно меньше, примерно в раз для вещественной и раз для комплексной СЛАУ. Кроме того, требуется хранить в оперативной памяти, как правило, только одну матрицу, например, матрицу перехода явного итерационного метода. При использовании быстро сходящихся итерационных методов вполне решаемыми в реальном времени на современных ПЭВМ оказываются СЛАУ с комплексной матрицей размерностью .
В настоящее время отсутствуют библиотеки подпрограмм широкого назначения для численного решения больших и сверхбольших СЛАУ. Таким образом, разработка эффективных итерационных алгоритмов для широкого класса матриц СЛАУ большой размерности и библиотек подпрограмм на их основе является актуальной задачей.
Наиболее алгоритмически простыми среди итерационных методов являются стационарные итерационные методы, такие как оптимальный метод простой итерации и метод релаксации. В то же время показано, что можно добиться их эффективной сходимости для достаточно широкого класса вещественных и комплексных матриц СЛАУ. Для нестационарных итерационных методов, таких как метод с чебышевским набором параметров, минимальных невязок, сопряженных градиентов, сходимость доказана в узком классе матриц, например, таких как вещественные симметричные положительно определенные матрицы. И в этом узком классе матриц сходимость оптимальных стационарных методов, опирающихся на известные спектральные матричные свойства, оказывается в некоторых случаях даже лучшей. При этом число арифметических операций стационарного алгоритма минимально. Еще одним преимуществом оптимального метода простой итерации является возможность естественного распараллеливания алгоритма при постановке его на современные параллельные ЭВМ, так как алгоритм по существу сводится к одному умножению матрицы на вектор. ............
