Численные методы. Корнюшин П.Н. - 49 стр.

                                                        49




   3.5. Численное решение систем линейных алгебраических уравнений
       В этой главе изучаются методы численного решения систем линейных алгебраических
уравнений, т.е. численные методы линейной алгебры. Существуют два типа методов – прямые и
итерационные. Эффективность прямых методов зависит от порядка системы и структуры
матрицы коэффициентов. При изучении итерационных методов система уравнений трактуется
как операторное уравнение первого рода Au=f и излагается общая теория итерационных методов
для операторных уравнений при минимальных предположениях относительно оператора A. Общая
теория позволяет доказать сходимость итераций для метода Зейделя и метода релаксации при
минимальных ограничениях на оператор A.

                      3.5.1. Системы линейных алгебраических уравнений

                                    3.5.1.1. Системы уравнений

        Основная задача линейной алгебры – решение системы уравнений
                                        Au=f,                         (1)
         где u=(u1,…, uN) – искомый вектор, f=(f1,…, fN) – известный вектор размерности N, A=(aij)
(i, j=1,…, N) – квадратная матрица размера N*N с элементами aij.
        Будем предполагать, что матрица A невырождена; detA ≠ 0, так что уравнение Au=0 имеет
только тривиальное решение, и система (1) имеет единственное решение u=A-1f.
        В курсе линейной алгебры решение системы (1) обычно выражают по формулам Крамера в
виде отношений определителей. Для численного решения системы (1) эти формулы непригодны,
т.к. они требуют вычисления N+1 определителей, для чего необходимо осуществление порядка N!
арифметических операций. Даже при выборе наилучшего метода вычисление одного определителя
требует такого же времени, что и решение системы линейных уравнений современными
численными методами. Кроме того, вычисления по формулам Крамера часто ведут к большим
погрешностям округления.
        Особенность большинства численных методов для решения системы уравнений (1)
состоит в отказе от нахождения обратной матрицы. Основное требование к методу решения –
минимум числа арифметических действий, достаточных для отыскания приближенного решения с
заданной точностью ε>0 (экономичность численного метода).


                                 3.5.1.2. Частные случаи систем

          Несложно решить систему (1) в перечисленных ниже частных случаях. Пусть матрица A –
диагональная, т.е. aij=0, j ≠ i, aii ≠ 0 (i, j=1,…, N). Тогда система имеет вид aiiui=fi, откуда находим
ui=fi/aii, i=1,…, N.
          Если A – нижняя треугольная матрица, т.е. aij=0 при j>i (i, j=1,…, N), aii ≠ 0,
                                          a11          0      ...  0 
                                         a           a 22     ... 0 
                                     A =  21                             ,
                                          ...         ...     ... ... 
                                                                       
                                         a N 1       aN 2     ... a NN 
то система уравнений (1) имеет вид
                                                a11u1                = f1 ,
                                          a 21u1 + a 22 u 2          = f2 ,
                                      ...........................     ......
                                      a N 1u1 + ... + a NN u N       = fN .