Итерационные методы решения систем линейных алгебраических уравнений

ЛЕКЦИЯ №4 ИТЕРАЦИОННЫЕ МЕТОДЫ РЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ. Пусть дана система линейных алгебраических уравнений (СЛАУ) вида a11x1  a12 x2  ...  a1n xn  b1, a x  a x  ...  a x  b ,  21 1 22 2 2n n 2  ... an1x1  a2n x2  ...  ann xn  bn . (4.1) Вводя в рассмотрение матрицы  a11 a12 a a A   21 22  ... ...   an1 an 2 ... a1n   x1   b1      ... a2 n  x2  b  , x , B 2  ...   ...  ... ...       ... ann   xn   bn  (4.2) систему (4.1) можно записать в виде матричного уравнения Ax  B . Для решения систем линейных (4.3) алгебраических уравнений существуют точные методы: метод Гаусса, с помощью обратной матрицы (матричный метод), по формулам Крамера. Однако, при большом числе неизвестных применение точных методов решения затруднено. В этом случае для нахождения корней системы (4.1) целесообразнее пользоваться приближенными (численными) методами. 1 Метод простых итераций для решения систем линейных алгебраических уравнений. Пусть дана система линейных алгебраических уравнений вида (4.1). Предположим, что диагональные элементы матрицы A не равны нулю, т.е. aii  0, i  1, n (в случае равенства одного или нескольких из них нулю, с помощью перестановки уравнений или других эквивалентных преобразований можно добиться, чтобы они были отличны от нуля). Разделив i -ое уравнение системы на aii , получим:  x1  1  12 x2  13 x3  ...  1n xn ,  x     x   x  ...   x ,  2 2 21 1 23 3 2n n  .............................................................  xn   n   n1x1   n 2 x2  ...   nn 1xn 1, где коэффициенты i  (4.4) aij bi , ij   при i  j,ii  0 . aii aii Введем обозначения:  1   11 12      22 2     ,    21  ...   ... ...      n1  n 2  n  ... 1n  ...  2 n  ... ...   ...  nn  (4.5) Тогда система (4.4) примет вид: x   x Систему приближений. (4.6) будем Выбираем решать начальное (4.6) методом последовательных приближение x    ; далее вычисляем следующие приближения: 1 2 1 k 1 k x      x  , x      x  ,…, x      x  , … Если последовательность приближений 2 (4.7) 1 2 k x  , x  , x  ,..., x  ,... является сходящейся, т.е. у нее существует предел   lim x k  , то этот k  предел  является решением системы (4.6). Действительно,     lim x k 1  lim    x k      . k  k  Получили      , т.е.  – является решением системы (4.6), а система (4.6) получена из системы (4.1), следовательно,  будет являться решением исходной системы (4.1). Теорема 4.1 (достаточное условие сходимости итерационного процесса). Если для приведенной системы x     x выполнено хотя бы одно из условий: n а)  ij  1, i  1, n; j 1 n б)  ij  1, j  1, n , i 1 то процесс итерации, заданный формулой x k 1 k     x  , сходится к единственному решению этой системы, независимо от выбора начального приближения. В частности процесс итерации заведомо сходится, если элементы  ij 1 приведенной системы (4.4) удовлетворяют неравенству  ij  , где n n число неизвестных системы. Следствие. Для исходной системы (4.1) итерационный процесс сходится, если n выполнены неравенства aii   aij , i  1, n (то есть модули диагональных i  j 1 3 коэффициентов для каждого уравнения системы больше суммы модулей всех остальных коэффициентов, не считая свободных членов). Теорема 4.2 (необходимое и достаточное условие сходимости процесса итерации для системы линейных уравнений). Для сходимости процесса итераций x k 1 k     x  при любом выборе начального приближения x  и любом свободном члене  необходимо и достаточно, чтобы собственные значения матрицы  (т.е. корни характеристического уравнения det    E   0 ) были по модулю меньше единицы. ПРИМЕР 4.1. Пусть известна матрица коэффициентов при неизвестных СЛАУ, а также задана единичная матрица Е: ( ) ( ). Тогда получим, ( ) ( ) ( ( ) ) ) ). Вычислим определитель данной матрицы ( ( ( ( : ( . Приравняв полученное выражение к 0 найдем собственные значения матрицы : D=0,36. . Таким образом условия теоремы 4.2 выполнены: 4 , Приведение исходной системы к виду, удобному для применения сходящегося итерационного процесса. Теорема сходимости итерационного процесса накладывает жесткие условия на коэффициенты системы (4.3). Однако, если det A  0 , то с помощью элементарных преобразований системы (4.3) ее можно заменить эквивалентной x   x , системой такой, что условия теоремы сходимости будут выполнены. Умножим левую и правую часть соотношения (4.3) слева на матрицу A 1      , где    ij , i, j  1, n - матрица с малыми по модулю элементами. Проведем преобразования: A 1      Ax  A1   B,   x   Ax  A1   B,  Если обозначить    A     B ,    A , то получим x     x . x  A1   B   Ax. 1 Если элементы матрицы  достаточно малы по модулю, т.е.  ii  0 , то элементы матрицы  будут удовлетворять достаточному условию сходимости итерационного процесса. Итерационный процесс заканчивается, если для двух приближений x k 1 n k k 1 k k 1 k и x  выполнено условие x   x    xj   xj    , где  j 1 заданная точность. 5 Метод Зейделя. Метод Зейделя представляет собой некоторую модификацию метода простых итераций. Основная его идея состоит в том, что при вычислении  k  1 -го ранее приближения неизвестной xi учитываются уже вычисленные  k  1 -е приближения неизвестных x0 , x1,..., xi 1 . Т.е. найденное Рис.4.1  k  1 -е приближение сразу же используется для получения  k  1 -го приближения последующих координат (Рис.4.1). Предполагая, что k -е приближения xi k  корней системы (4.4) известны,  k  1 -е приближения корней будут находиться по следующим итерационным формулам метода Зейделя: (4.8) 6 Теорема 4.3 (достаточное условие сходимости метода Зейделя). Если для приведенной системы x     x выполнено хотя бы одно из условий: 1)  n  1 , где  m  max  ij ; m 1i  n j 1 n 2)  l  1 , где  l  max  ij ; 1 j  n i 1 3)  k  1 , где  k  n 2  ij , i , j 1 то процесс Зейделя сходится к единственному решению системы при любом выборе начального вектора. Запишем систему (4.8) в сокращенном виде: xi k 1 i 1  i   ij xj k 1 j 1 n k   ij xj  , i  1, n (4.9) j i   Введем обозначения:   ij  B  C , где  0  B   21  ... ...    n1  n 2 ... 0 0 ... 0 0  , ... 0 0  ...  nn 1 0  . Тогда формулу (4.9) можем переписать в матричном виде: x k 1    Bx где 7 k 1 k  Cx  , (4.10)  x k    x k 1  1  1     1    k k  1     x  x      2  , x k    2  , x k 1   2  .  ...   ...   ...        x k    x k 1   n   n   n  Теорема 4.4 (необходимые и достаточные условия сходимости метода Зейделя). Для сходимости процесса Зейделя, заданного формулой (4.9), для приведенной системы линейных уравнений (4.4) при любом выборе свободного члена  и начального вектора x  необходимо и достаточно, чтобы все корни 1, 2 ,..., n уравнения det  C   E  B     0 были по модулю меньше единицы. Пример 4.2. Построить рабочие формулы метода простых итераций и метода Зейделя для численного решения СЛАУ вида: 8 x  5 y  z  1;   x  6 y  2 z  7;  x  y  4 z  9.  (4.11) Решение. Заметим, что система (4.11) имеет точное решение x  1; y  2; z  3 . Из системы (4.11) видно, что модули диагональных коэффициентов в каждом уравнении отличны от нуля и больше суммы модулей всех остальных коэффициентов, не считая столбца свободных членов. Тогда, разделим каждое уравнение системы (4.11) на соответствующий диагональный коэффициент, сформируем столбец ( x, y, z) в левой части и перенесем остальные слагаемые в правую часть, получим рабочие формулы метода простых итераций вида: 8   k 1 1 5  k  1  k    y  z ; x 8 8 8    k 1 7 1  k  1  k    x  z ; y 6 6 3    k 1 9 1  k  1  k    x  y , k  0,1,2,... z 4 4 4  Начальное приближение обычно выбирают равным  столбцу  1 7 9 свободных членов преобразованной системы x(0) , y (0) , z (0)   , ,  . 8 6 4 Рабочие формулы метода Зейделя запишутся так:   k 1 1 5  k  1  k    y  z ; x 8 8 8    k 1 7 1  k 1 1  k    x  z ; y 6 6 3    k 1 9 1  k 1 1  k 1   x  y , k  0,1,2,... z 4 4 4  ЗАДАНИЕ. Построить рабочие формулы метода простых итераций и метода Зейделя для численного решения СЛАУ вида: { . Метод релаксации. Рассмотрим систему линейных алгебраических уравнений (4.1) a11x1  a12 x2  ...  a1n xn  b1, a x  a x  ...  a x  b ,  21 1 22 2 2n n 2  ... an1x1  a2n x2  ...  ann xn  bn , в которой aii  0, i  1, n . Сделаем преобразования: свободные члены перенесем в левую часть 9 и каждое i -ое уравнение поделим на  1 aii , i  1, n . Таким образом, получим систему, удобную для релаксации:  x1  b12 x2  ...  b1n xn  c1  0, b x  x  ...  b x  c  0,  21 1 2 2n n 2  ... bn1x1  bn 2 x2  ...  xn  cn  0. где bij  aij aii , i  j , ci  (4.12) bi . aii Введем понятие невязки для приближенного решения x0 . Пусть дана система Ax  B , тогда точное решение x можно записать  1    в виде x  x0   , где    ...  -правка корня x0 . Подставим x  x0   в    n систему, получим A  x0     B, Ax0  A  B, A  B  Ax0 . Введем обозначение B  Ax0   . Тогда A   . Выражение   B  Ax0 называется невязкой для приближенного решения x0 . Пусть задано начальное приближение системы (4.12):   x   x1  , x2  ,..., xn  . Подставим данное приближение в систему (4.12) и получим невязки Ri  , i  1, n : 10 n R1   c1  x1    b1 j xj  , j 2 R2   c2  x2   0  b2 j x j , n j 1, j  2 (4.13) ... n 1 Rn   cn  xn    bnj xj  . j 1 Если одной из неизвестных xk  дать приращение xk  , то соответствующая невязка Rk  уменьшится на величину xk  , а все остальные невязки Rq  , q  k изменятся на величину bqk xk  . Чтобы 1 обратить очередную невязку Rk  в нуль, нужно величине xk  дать 1 приращение xk   Rk  , следовательно, Rk   0 , а остальные невязки будут равны 1 Rq   Rq   bqk xk  , q  k . Метод релаксации (метод ослабления) заключается в том, что на каждом шаге обращают в нуль максимальную по модулю невязку путем изменения значения соответствующей компоненты приближения. Процесс заканчивается, когда все невязки последней преобразованной системы будут равны нулю с заданной точностью. Пример 4.3. Решить систему методом релаксации, производя вычисления с двумя десятичными знаками. 10 x1  2 x2  2 x3  6,   x1  10 x2  2 x3  7,  x  x  10 x  8. 3  1 2 Решение. Приведем систему (4.14) к виду, удобному для релаксации 11 (4.14)  x1  0.2 x2  0.2 x3  0.6  0,  0.1x1  x2  0.2 x3  0.7  0, 0.1x  0.1x  x  0.8  0. 1 2 3  (4.15) В качестве начального приближения выбираем x1   x2   x3   0 . Находим соответствующие невязки: R1   0.60 , R2   0.70 , R3   0.80 . Выбираем максимальную невязку и полагаем x3   0.80 , тогда R3   0, 1 1 R1   R1   b13x3   0.6  0.2  0.80  0.76, 1 R2   R2   b23x3   0.7  0.2  0.80  0.86. Опять выбираем максимальную невязку и полагаем x2   0.86 , тогда 1 2 R2   0, 2 2 2 R1   R1   b12x2   0.76  0.2  0.86  0.93, 2 1 1 R3   R3   b32x2   0  0.1  0.86  0.09. 2 Далее x1   0.93 и 3 R1   0, 3 2 2 R2   R2   b21x1   0  0.1  0.93  0.09, 3 2 2 R3   R3   b31x1   0.09  0.1  0.93  0.18. 3 x3   0.18 , 4 R3   0, 4 3 3 R1   R1   b13x3   0  0.2  0.18  0.04, 4 3 3 R2   R2   b23x3   0.09  0.2  0.18  0.13. 4 x2   0.13 , 12 5 R2   0, 5 4 4 R1   R1   b12x2   0.04  0.2  0.13  0.07, 5 4 4 R3   R3   b32x2   0  0.1  0.13  0.01. 5 x1   0.07 , 6 R1   0, 6 R2   0  0.1  0.07  0.01, 6 R3   0.1  0.1  0.07  0.02. 6 x3   0.02 , 7 R3   0, 7 R1   0  0.2  0.02  0.004  0.00, 7 R2   0.01  0.2  0.02  0.01. 7 x2   0.01 , 8 R2   0, 8 R1   0  0.2  0.01  0.00, 8 R3   0  0.1  0.01  0.00. Окончательно получим: 2 5 x1  x1   x1   x1   0  0.93  0.07  1.00, 1 4 7 x2  x2   x2   x2   x2   0  0.86  0.13  0.01  1.00, 3 6 x3  x3   x3   x3   x3   0  0.80  0.18  0.02  1.00. 13