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

Лекция 7Раздел II. ЧИСЛЕННЫЕ МЕТОДЫ1. ИТЕРАЦИОННЫЕ МЕТОДЫ РЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХАЛГЕБРАИЧЕСКИХ УРАВНЕНИЙПОСТАНОВКА ЗАДАЧИРассматривается проблема решения систем линейных алгебраических уравнений(СЛАУ), записываемых в видеAx  bили a11  a1n   x1   b1               ,   a n1  ann   x n   bn где A  (ai j )  R n  n – действительная матрица размеров (n  n) , i , j – переменные, соответствующие номерам строк и столбцов (целые числа); b  (b1 ,..., bn )T  R n – векторстолбец размеров (n  1) , x  ( x1 ,..., x n )T  R n – вектор-столбец неизвестных, R n – n мерное евклидово пространство, верхний индекс "T " здесь и далее обозначает операциютранспонирования.Требуется найти решение x   ( x 1 ,..., x  n )T  R n системы, подстановка которогов систему приводит к верному равенству A x   b .З а м е ч а н и я.1.

Из курса линейной алгебры известно, что решение задачи существует и единственно, если определитель (детерминант) матрицы A отличен от нуля, т.е. det A  A  0( A – невырожденная матрица, называемая также неособенной).Классификация численных методов решения СЛАУПри решении СЛАУ используются два класса численных методов:1. Прямые методы, позволяющие найти решение за определенное число операций.К прямым методам относятся: метод Гаусса и его модификации (в том числе метод прогонки), метод LU – разложения и др.

Изучаются в курсе линейной алгебры.2. Итерационные методы, основанные на использовании повторяющегося (циклического) процесса и позволяющие получить решение в результате последовательныхприближений. Операции, входящие в повторяющийся процесс, составляют итерацию.К итерационным методам относятся: метод простых итераций, метод Зейделя и др.ИТЕРАЦИОННЫЕ МЕТОДЫА. МЕТОД ПРОСТЫХ ИТЕРАЦИЙАльтернативой прямым методам являются итерационные методы, основанные намногократном уточнении x (0) – приближенно заданного решения задачи A x  b . Верх-74ним индексом в скобках здесь и далее по тексту обозначается номер итерации (совокупности повторяющихся действий).Методика решения задачиШаг 1.

Исходная задача A x  b преобразуется к равносильному виду:x   x  ,где     ij  – квадратная матрица,     i  – вектор, i, j  1,..., n . Это преобразованиеможет быть выполнено различными путями, но для обеспечения сходимости итераций(см. процедуру 2) нужно добиться, чтобы   1 (чтобы норма  была меньше единицы.Понятие нормы вводится ниже.)Шаг 2. Вектор  принимается в качестве начального приближения x (0)   и далее многократно выполняются действия по уточнению решения согласно рекуррентномусоотношениюx ( k 1)   x ( k )  ,k  0,1,...или в развернутом видеx1(k 1)  11 x1(k )  12 x 2(k )  ...

 1n x n(k )  1 ,x 2(k 1)   21 x1(k )   22 x 2(k )  ...   2n x n(k )   2 ,x n(k 1)   n1 x1(k )   n 2 x 2(k )  ...   nn x n(k )   n .Шаг 3. Итерации прерываются при выполнении условияx (k 1)  x (k )   ,где   0 – заданная точность, которую необходимо достигнуть при решении задачи.З а м е ч а н и я.1. Процесс называется параллельным итерированием, так как для вычисления(k  1) -го приближения всех неизвестных учитываются вычисленные ранее их k -е приближения.2.

Начальное приближение x (0) может выбираться произвольно, или из некоторыхсоображений, например x (0)   . При этом может использоваться априорная информация о решении или просто «грубая» прикидка.75Нормы матриц и векторовНаиболее употребительными являются следующие формулы для вычисления значений норм матриц и векторов, образованных действительными компонентами.Нормы матрицы A1)2)3)A1 maxnНормы вектора xaij ;x max  aij ;xij 1 max x i ;1inAA23j2i 1nn  aij2 ;x3i 1 j 1ni 1xi ;n xi2 .i 1Скорость сходимости Рассмотрим последовательность x (k ) , сходящуюся к x  .

Предположим, что всеее элементы различны и ни один из них не совпадает с x  . Наиболее эффективный способ оценивания скорости сходимости состоит в сопоставлении расстояния между x (k 1)и x  с расстоянием между x (k ) и x  . Последовательность x (k )симальное число, для которогоназывается сходящейся с порядком p , если p – мак-0  limk x (k 1)  x x(k ) xp .Поскольку величина p определяется предельными свойствамивается асимптотической скоростью сходимости. x  , она назы(k ) Если последовательность x (k ) – сходящаяся с порядком p , то числоc  limk x (k 1)  x x (k )  x pназывается асимптотическим параметром ошибки.Если p  1 , c  1 , то сходимость линейная, если p  2 – квадратичная, если p  3– кубичная и т.д.

Если p  1 или p  1, c  0 , то сходимость сверхлинейная. Линейнаясходимость является синонимом сходимости со скоростью геометрической прогрессии.Сверхлинейная сходимость является более быстрой, чем определяемая любой геометрической прогрессией.76Теоремы о сходимостиТеорема (о достаточном условии сходимости метода простых итераций).

Методпростых итераций, реализующийся в процессе последовательных приближений, сходится к единственному решению исходной системы Ax  b при любом начальном приближении x (0) со скоростью не медленнее геометрической прогрессии, если какая-либонорма матрицы  меньше единицы, т.е.  s  1 ( s  { 1,2,3 } ).З а м е ч а н и я.1. Сходящийся процесс обладает свойством самоисправляемости, т.е. отдельнаяошибка в промежуточных вычислениях не отразится на окончательном результате, таккак ошибочное приближение можно рассматривать как новое начальное.2. Условия сходимости выполняются, если в матрице A диагональные элементыпреобладают, т.е.aii  ai1  ...

 ai ,i 1  ai ,i 1  ...  ain , i  1,..., n ,и хотя бы для одного i неравенство строгое. Иначе, модули диагональных коэффициентов в каждом уравнении системы больше суммы модулей недиагональных коэффициентов (свободные члены не рассматриваются).3. Чем меньше величина нормы  , тем быстрее сходимость метода.Способы преобразования системыПреобразование системы Ax  b к виду x  x   с матрицей  , удовлетворяющей условиям сходимости, может быть выполнено несколькими способами. Приведемспособы, используемые наиболее часто.1.

Уравнения, входящие в систему Ax  b , переставляются так, чтобы выполнялось условие преобладания диагональных элементов (для той же цели можно использовать другие элементарные преобразования). Затем первое уравнение разрешается относительно x1 , второе – относительно x 2 и т.д. При этом получается матрица  с нулевымидиагональными элементами.Например, система 2,8x1  x 2  4 x 3  60 ,10 x1  x 2  8 x 3  10 , x1  2 x 2  0,6 x 3  20с помощью перестановки уравнений приводится к виду10 x1  x 2  8 x 3  10 , x1  2 x 2  0,6 x 3  20 , 2,8x1  x 2  4 x 3  60 ,где 10   1  8 , 2   1   0,6 , 4   2,8  1 , т.е.

диагональные элементы преобладают.77Выражая x1 из первого уравнения, x 2 – из второго, а x 3 – из третьего, получаемсистемуx1  0  x1  0,1x 2  0,8x 3  1 ,x 2  0,5x1  0  x 2  0,3x 3  10 ,x 3  0,7 x1  0,25 x 2  0  x 3  15 ,0,1 0,8  01 где    0,500,3  ,   10  . 0,7  0,2515 0  Заметим, что 1 max  0,9 ; 0,8 ; 0,95   0,95  1 , т.е. условие теоремы выполне-но.Проиллюстрируем применение других элементарных преобразований. Так, система4 x1  x 2  9 x 3   7 ,3x1  8x 2  7 x 3   6 ,x1  x 2  8 x 3  7путем сложения первого и третьего уравнений и вычитания из второго уравнения третьего уравнения преобразуется к виду5x1  2 x 2  x 3  0 ,2 x1  7 x 2  x 3  13 ,x1  x 2  8x 3  7с преобладанием диагональных элементов.2.

Уравнения преобразуются так, чтобы выполнялось условие преобладания диагональных элементов, но при этом коэффициенты  ii не обязательно равнялись нулю.Например, систему1,02 x1  0,15 x 2  2,7 ,0,8 x1  1,05 x 2  4можно записать в формеx1   0,02 x1  0,15 x 2  2,7 ,x 2   0,8 x1  0,05 x 2  4 ,для которой  ij 1 max  0,17 ; 0,85   0,85  1 .3. Если det A  0 , систему Ax  b следует умножить на матрицу D  A 1   , где– матрица с малыми по модулю элементами. Тогда получается система78( A 1  ) Ax  D bA 1 A x  A x  D b , которую можно записать в формеилиx  x   , где    A ,   D b . Если ij , i, j  1,..., n , достаточно малы, условиесходимости выполняется.Б.

МЕТОД ЗЕЙДЕЛЯЭтот метод является модификацией метода простых итераций и в некоторых случаях приводит к более быстрой сходимости.Итерации по методу Зейделя отличаются от простых итераций тем, что при нахождении i -й компоненты (k  1) -го приближения сразу используются уже найденныекомпоненты (k  1) -го приближения с меньшими номерами 1,2,..., i  1 . При рассмотрении развернутой формы системы итерационный процесс записывается в видеx1( k 1)  11 x1(k )  12 x 2(k )  13 x 3( k )  ...

 1n x n(k )  1 ,x 2( k 1)   21 x1(k 1)   22 x 2(k )   23 x 3(k )  ...   2n x n(k )   2 ,(1.1)x 3( k 1) 31 x1(k 1) 32 x 2(k 1) 33 x 3(k ) ...   3n x n( k )  3 ,x n( k 1)   n1 x1(k 1)   n 2 x 2( k 1)   n3 x 3( k 1)  ...   nn 1 x n(k11)   nn x n(k )   n .В каждое последующее уравнение подставляются значения неизвестных, полученных из предыдущих уравнений, что показано в записи стрелками.Теорема о сходимостиТеорема (о достаточном условии сходимости метода Зейделя).Если для системы x  x   какая-либо норма матрицы  меньше единицы,т.е.  s  1 ( s  { 1,2,3 } ), то процесс последовательных приближений сходитсякединственному решению исходной системы Ax  b при любом начальном приближенииx (0 ) .Записывая (1.1) в матричной форме, получаемx (k 1)  Lx (k 1)  Ux (k )   ,где L,U являются разложениями матрицы  :79(1.2) 0  21L    31  n1000 320 n20  n3  11 0U  0 0000 ,01213 22 23 33000 1n   2n   3n  .    nn Преобразуя (1.2) к виду x  x   , получаем матричную форму итерационногопроцесса метода Зейделя:11x ( k 1)   E  L  U x ( k )   E  L   .(1.3)З а м е ч а н и я.1.