Общая характеристика проблем решения систем линейных алгебраических уравнений

1.  Общая хар-ка проблем решения СЛАУ

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

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

Примером прямого метода решения СЛАУ служит метод Крамера, в соответствии с которым

                                                 , .

Однако на практике этот метод не используется, так как он требует выполнения очень большого количества арифметических операций. Большая часть существующих прямых методов укладывается в следующую схему. Пусть задана система

                                                                                                                          (4.1)

линейных алгебраических уравнений. Умножим обе части равенства (4.1) слева на такие матрицы , при которых новая система

                                                                            (4.2)

равносильна исходной и легко решается. Для этого достаточно, чтобы матрица

была треугольной или диагональной. Методы, основанные на подобных преобразованиях, составляют в настоящее время самую значительную группу среди численных методов задач алгебры.

                        Одним из старейших является метод Гаусса, в основе которого лежит идея последовательного исключения неизвестных. Он использует левые треугольные матрицы L_i и позволяет свести исходную систему уравнений к системе с правой треугольной матрицей. Этот метод легко реализуется на компьютере, его схема с выбором главного элемента позволяет решать системы с произвольной невырожденой матрицей, а  компактная схема – получить результаты с повышенной точностью. Среди всех прямых методов метод Гаусса требует минимального объема вычислений.

                 Непосредственно к методу Гаусса примыкают метод Жордана и метод оптимального исключения. Эти методы используют треугольные матрицы L_i (как левые, так и правые) и позволяют привести исходную систему к системе с диагональной матрицей. Метод оптимального исключения позволяет при заданном объеме оперативной памяти решать системы более высокого порядка, чем метод Жордана.

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