Введение в численные методы. Дулов Е.Н. - 39 стр.

    7. Численные методы линейной алгебры: обратные матрицы

    Решение     систем   линейных     алгебраических    уравнений      (СЛАУ)    или
эквивалентная задача нахождения обратной матрицы – ключевая в численных
методах линейной алгебры. Матричные уравнения могут встретиться в любой
численной задаче, где возникает упорядоченная совокупность значений, и эту
совокупность можно рассматривать как вектор.
    Умение находить обратную матрицу фактически дополняет операцией деления
набор таких легко реализуемых операций над матрицами, как сложение, вычитание
и умножение. После этого, решение задач с векторами и матрицами становится не
намного сложнее решения обычных скалярных линейных уравнений. Нужно лишь
учитывать некоммутативность операции умножения матриц.
    Почему нахождение обратной матрицы может представлять трудность?
Хорошо известный из линейной алгебры метод Крамера позволяет просто находить
обратную матрицу через ее детерминант и алгебраические дополнения. Однако
число слагаемых в детерминанте матрицы зависит от размера матрицы n как n! и
уже при n = 10 метод Крамера будет занимать слишком много времени. Такие
алгоритмы, в которых объем вычислений растет как O(n!) или пропорционален O(e n )
называются    неполиномиальными.      Задачей   численных    методов       нахождения
обратных матриц является нахождение полиномиального алгоритма, т.е. такого, в
котором число арифметических операций будет зависеть от размерности задачи как
 ( )
O n k , k - некоторое число, постоянное для алгоритма. Так, операция сложения

матриц подразумевает сложность алгоритма O(n 2 ) а умножения - O(n 3 ) .



    7.1 Метод Гаусса
    Метод Гаусса представляет собой метод последовательного исключения
переменных, схожие действия обычно используются при решении СЛАУ вручную.
Именно поэтому алгоритм Гаусса очень легко запоминается. Чтобы найти обратную
матрицу      последовательным     исключением      переменных,      нужно      ввести
вспомогательную единичную матрицу. После чего операциями умножения строк на
число и сложения строк добиваются сведения оборачиваемой матрицы к
                                           39