1611688890-f641c9ec8276824e4686da772eb56520 (826652), страница 59
Текст из файла (страница 59)
Стационарные итерационные методыно для отыскания решения мы можем воспользоваться незначительноймодификацией итераций ЯкобиX1 (k+1)(k)←xibi x(k) −aij xj ,i = 1, 2, . . . , n,aiij6=ik = 0, 1, 2, . . . , с некоторым начальным приближением x(0) . Если b(x)изменяется «достаточно медленно», так что | b′i (x)/aii | < 1 для любыхx ∈ Rn при всех i = 1, 2, .
. . , n, то сходимость этого процесса для произвольного начального приближения следует, к примеру, из теоремыШрёдера о неподвижной точке (Теорема 4.4.5, стр. 483).Вообще, нелинейный итерационный процесс Якоби в применении ксистеме уравненийF1 ( x1 , x2 , .
. . , xn ) = 0, F2 ( x1 , x2 , . . . , xn ) = 0,.........Fn ( x1 , x2 , . . . , xn ) = 0может заключаться в следующем. Задавшись каким-то начальным приближением x(0) , на очередном k-ом шаге последовательно находят решения x̃i уравнений(k)(k)(k)= 0,Fi x1 , . . . , xi−1 , xi , xi+1 , . . .
, x(k)n(k+1)относительно xi , а затем полагают xi3.9еi = 1, 2, . . . , n← x̃i , i = 1, 2, . . . , n.Итерационный метод Гаусса-ЗейделяВ итерационном методе Якоби при организации вычислений по инструкции!X1(k)(k+1),i = 1, 2, . . . , n,(3.108)bi −aij xj←xiaiij6=iкомпоненты очередного приближения x(k+1) находятся последовательно одна за другой, так что к моменту вычисления i-ой компоненты3603. Численные методы линейной алгебры(k+1)(k+1)(k+1)вектора x(k+1) уже найдены x1, x2, .
. . , xi−1 . Но метод Якоби никак не использует эти новые значения, и при вычислении любой компоненты следующего приближения всегда опирается только навектор x(k) предшествующего приближения. Если итерации сходятсяк решению, то естественно ожидать, что все компоненты x(k+1) ближек искомому решению, чем x(k) , а посему немедленное вовлечение их впроцесс вычислений будет способствовать ускорению сходимости.На этой идее основан итерационный метод Гаусса-Зейделя,25 псевдокод которого представлен в Табл.
3.6 (где, как и ранее, k — счётчикитераций). В нём суммирование в формуле (3.108) для вычисления iой компоненты очередного приближения x(k+1) разбито на две части— по индексам, предшествующим i, и по индексам, следующим за i.(k+1)Первая часть суммы использует новые вычисленные значения x1,(k)(k)(k+1). . . , xi−1 , тогда как вторая — компоненты xi+1 , . . . , xn из старогоприближения. Метод Гаусса-Зейделя иногда называют также итерационным методом «последовательных смещений», а его основная идея —немедленно вовлекать уже полученную информацию в вычислительный процесс — с успехом применима и для нелинейных итерационныхсхем.Чтобы получить для метода Гаусса-Зейделя матричное представление, перепишем его расчётные формулы в виде(k+1)aii xi+i−1Xj=1(k+1)aij xj=−nX(k)aij xj+ bi ,i = 1, 2, .
. . , n.j=i+1Используя введённые в §3.9д матрицы L̃, D и Ũ , на которые разлагаетсяA, можем записать эти формулы в виде(D + L̃) x(k+1) = −Ũ x(k) + b,т. е.x(k+1) = −(D + L̃)−1 Ũ x(k) + (D + L̃)−1 b,k = 0, 1, 2, . . . .(3.109)Таким образом, метод Гаусса-Зейделя можно рассматривать как итерационный метод, порождённый таким расщеплением матрицы СЛАУв виде A = G − H (см. §3.9в), что G = D + L̃, H = −Ũ .25 В отечественной литературе по вычислительной математике нередко используется также термин «метод Зейделя».3.9. Стационарные итерационные методы361Таблица 3.6. Итерационный метод Гаусса-Зейделядля решения линейных систем уравненийk ← 0;выбираем начальное приближение x(0) ;DO WHILE ( метод не сошёлся )DO FOR i = 1 TO nni−1XX1 (k+1)(k) (k+1)←xiaij xj−aij xjbi −aiij=i+1j=1END DOk ← k +1;END DOВ силу Теоремы 3.9.1 необходимым и достаточным условием сходимости метода Гаусса-Зейделя из любого начального приближения является неравенствоρ (D + L̃)−1 Ũ < 1.Но, как и в случае аналогичного условия для метода Якоби, оно имеет,главным образом, теоретическое значение.Теорема 3.9.3 Если в системе линейных алгебраических уравненийAx = b матрица A имеет диагональное преобладание, то метод ГауссаЗейделя для решения этой системы сходится при любом начальномприближении.Доказательство.
Отметим, прежде всего, что в условиях диагонального преобладания в A решение x⋆ линейной системы Ax = b всегдасуществует и единственно (вспомним признак неособенности Адамара,§3.2е). Пусть, как и ранее, x(k) — приближение к решению, полученноена k-ом шаге итерационного процесса. Исследуем поведение погрешности решения z (k) := x(k) − x⋆ в зависимости от номера итерации k.Чтобы получить формулу для z (k) , предварительно перепишем со-3623. Численные методы линейной алгебрыотношения, которым удовлетворяет точное решение x⋆ : вместоnXaij x⋆j = bi ,i = 1, 2, . . . , n.j=1можно придать им следующий эквивалентный вид!ni−1XX1⋆⋆⋆i = 1, 2, . . .
, n.xi =aij xj ,aij xj −bi −aiij=i+1j=1Вычитая затем почленно эти равенства из расчётных формул методаГаусса-Зейделя, т. е. из!ni−1XX1(k+1)(k)(k+1)=xi,i = 1, 2, . . . , n,aij xj−aij xjbi −aiij=i+1j=1можем заключить, что(k+1)zi1=aii−i−1Xj=1(k+1)aij zj−nXj=i+1(k)aij zj!,i = 1, 2, . .
. , n.Возьмём абсолютные значения от обеих частей этих равенств и воспользуемся неравенством треугольника для оценки сумм в правых частях. Мы будем иметь i−1 nXX aij (k+1) (k+1) aij (k) · z ≤z · z +i aii j aii jj=1j=i+1 ni−1 aij (k) X aij (k+1) X ≤ z aii aii + z∞∞j=i+1j=1(3.110)для i = 1, 2, . . . , n.С другой стороны, условие диагонального преобладания в матрицеA решаемой системы уравнений, т. е.X|aij | < |aii |,i = 1, 2, . . . , n,j6=iозначает существование константы κ, 0 ≤ κ < 1, такой чтоX|aij | ≤ κ |aii |,i = 1, 2, .
. . , n.j6=i(3.111)3.9. Стационарные итерационные методы363По этой причинеX aij ≤ κ, aii i = 1, 2, . . . , n,j6=iоткуда следует !i−1 i−1 i−1 nXXXX aij aij aij aij ≤ κ−κ = κ 1− . ≤ κ− aii aii aii aii j=1j=1j=1j=i+1Подставляя полученную оценку в неравенства (3.110), приходим к соотношениям!i−1 i−1 X aij (k+1) X (k+1) aij (k) + κz ≤ zz , (3.112)1−i aii aii ∞∞j=1j=1i = 1, 2, .
. . , n. (k+1) достигается при i = l, так чтоПредположим, что max1≤i≤n zi (k+1) z = z (k+1) .(3.113)l∞Рассмотрим теперь отдельно l-ое неравенство из (3.112). Привлекаяравенство (3.113), можем утверждать, что!l−1 l−1 X alj alj (k+1) X + κ z (k) z ≤ z (k+1) 1− all , all ∞∞∞j=1j=1то есть (k+1) z∞l−1 X alj 1− all j=1!!l−1 X alj (k) .≤ κ z ∞ 1 − all j=1(3.114)Конечно, значение индекса l, на котором достигается равенство (3.113),может меняться в зависимости от номера итерации k. Но так как вплоть(k+1),до оценки (3.112) мы отслеживали все компоненты погрешности ziто вне зависимости от k неравенство (3.114) должно быть справедливым для компоненты с номером l, определяемой условием (3.113).Далее, в силу диагонального преобладания в матрице Al−1 X alj 1− all > 0,j=13643.
Численные методы линейной алгебрыи на эту положительную величину можно сократить обе части неравенства (3.114). Окончательно получаем (k+1) z ≤ κ z (k) ,∞∞что при |κ| < 1 означает сходимость метода Гаусса-Зейделя.Фактически, в доказательстве Предложения 3.9.3 мы получили даже оценку уменьшения чебышёвской нормы погрешности через «мерудиагонального преобладания» в матрице СЛАУ, в качестве которой может выступать величина κ, определённая посредством (3.111).Теорема 3.9.4 Если в системе линейных алгебраических уравненийAx = b матрица A является симметричной положительно определённой, то метод Гаусса-Зейделя сходится к решению из любого начального приближения.Доказательство может быть найдено, к примеру, в [3, 11].
Теорема 3.9.4 является частным случаем теоремы Островского-Райха (теорема 3.9.5), которая, в свою очередь, может быть получена как следствиеиз более общей теории итерационных методов, развитой А.А. Самарским и начала которой мы излагаем в §3.12.Метод Гаусса-Зейделя был сконструирован как модификация метода Якоби, и, казалось бы, должен работать лучше. Так оно и есть«в среднем», на случайно выбранных системах — метод Гаусса-Зейделяработает несколько быстрее, что можно показать математически строго при определённых допущениях на систему.
Но в целом ситуация нестоль однозначна. Для СЛАУ размера 3 × 3 и более существуют примеры, на которых метод Якоби расходится, но метод Гаусса-Зейделясходится, так же как существуют и примеры другого свойства, когдаметод Якоби сходится, а метод Гаусса-Зейделя расходится. В частности, для метода Якоби неверна Теорема 3.9.4, и он может расходиться для систем линейных уравнений с симметричными положительноопределёнными матрицами.По поводу практического применения метода Гаусса-Зейделя можносказать почти то же самое, что и о методе Якоби в §3.9д.
Для решениясистем линейных алгебраических уравнений он используется в настоящее время нечасто, но его идея не утратила своего значения и успешноприменяется при построении различных итерационных процессов длярешения линейных и нелинейных систем уравнений.3.9. Стационарные итерационные методы3.9ж365Методы релаксацииОдним из принципов, который кладётся в основу итерационных методов решения систем уравнений, является так называемый принципрелаксации.26 Он понимается как специальная организация итераций,при которой на каждом шаге процесса уменьшается какая-либо величина, характеризующая погрешность решения системы.Поскольку само решение x⋆ нам неизвестно, то оценить напрямуюпогрешность (x(k) −x⋆ ) не представляется возможным.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
