1611688890-f641c9ec8276824e4686da772eb56520 (826652), страница 56
Текст из файла (страница 56)
При выполнении алгоритмаэта информация на каждом шаге вносится в итерационный процесси оказывает влияние на его ход. Напротив, прямые методы решенияСЛАУ этим свойством не обладают, так как, оттолкнувшись от исходной системы, мы далее уже не возвращаемся к ней, а оперируем с еёследствиями, которые никакой обратной связи от исходной системы неполучают.22Нередко итерационные процессы сравнительно несложно программируются, так как представляют собой повторяющиеся единообразныепроцедуры, применяемые к последовательным приближениям к решению. При решении СЛАУ с разреженными матрицами в итерационных процессах нередко можно легче, чем в прямых методах, учитыватьструктуру нулевых и ненулевых элементов матрицы и основывать наэтом упрощённые формулы матрично-векторного умножения, которыесущественно уменьшают общую трудоёмкость алгоритма.Иногда системы линейных алгебраических уравнений задаются воператорном виде, рассмотренном нами в начале §3.6 (стр. 284) т.
е.так, что их матрица и правая часть не выписываются явно. Вместо это22 Для исправления этого положения прямые методы решения СЛАУ в ответственных ситуациях часто дополняют процедурами итерационного уточнения. См.,к примеру, пункт 67 главы 4 в [42].3.9. Стационарные итерационные методы341го задаётся действие такой матрицы (линейного оператора) на любойвектор, и это позволяет строить и использовать итерационные методы.С другой стороны, преобразования матриц таких систем, которые являются основой прямых методов решения систем линейных уравнений,очень сложны или порой просто невозможны.Наконец, быстро сходящиеся итерационные методы могут обеспечивать выигрыш по времени даже для СЛАУ общего вида, если требуютдля практической сходимости небольшое число итераций.То обстоятельство, что искомое решение получается как топологический предел последовательности, порождаемой методом, являетсяхарактерной чертой именно итерационных методов решения уравнений.
Существуют и другие конструкции, по которым решение задачистроится из последовательности, порождаемой методом. Интересныйпример дают методы Монте-Карло, в которых осуществляется усреднение последовательности приближений.3.9бСходимость стационарныходношаговых итерационных методовСистемы линейных уравнений видаx = Cx + d,в котором вектор неизвестных переменных выделен в одной из частей,мы будем называть системами в рекуррентном виде.Теорема 3.9.1 Пусть система уравнений x = Cx + d имеет единственное решение. Стационарный одношаговый итерационный процессx(k+1) ← Cx(k) + d,k = 0, 1, 2, .
. . ,(3.98)сходится при любом начальном приближении x(0) тогда и только тогда, когда спектральный радиус матрицы C меньше единицы, т. е.ρ(C) < 1.Оговорка о единственности решения существенна. Если взять, кпримеру, C = I и d = 0, то рассматриваемая система обратится втождество x = x, имеющее решением любой вектор. Соответствующийитерационный процесс x(k+1) ← x(k) , k = 0, 1, 2, .
. . , будет сходиться излюбого начального приближения, хотя спектральный радиус матрицыперехода C равен единице.3423. Численные методы линейной алгебрыДоказательство Теоремы 3.9.1 будет разбито на две части, результаткаждой из которых представляет самостоятельный интерес.Предложение 3.9.1 Если kCk < 1 в какой-нибудь матричной норме,то стационарный одношаговый итерационный процессx(k+1) ← Cx(k) + d,k = 0, 1, 2, . . .
,сходится при любом начальном приближении x(0) .Доказательство. В формулировке предложения ничего не говорится о пределе, к которому сходится последовательность приближений{x(k) }, порождаемых итерационным процессом. Но мы можем указатьего в явном виде и строить доказательство с учётом этого знания.Если kCk < 1 для какой-нибудь матричной нормы, то в силу результата о матричном ряде Неймана (Предложение 3.3.11, стр. 263)матрица (I − C) неособенна и имеет обратную.
Следовательно, системауравнений (I −C) x = d, как и равносильная ей x = Cx+d, имеют единственное решение, которое мы обозначим x⋆ . Покажем, что в условияхпредложения это и есть предел последовательных приближений x(k) .В самом деле, еслиx⋆ = Cx⋆ + d,то, вычитая это равенство из соотношений x(k) = Cx(k−1) + d, k =1, 2, . .
. , получимx(k) − x⋆ = C x(k−1) − x⋆ .Вспомним, что всякая матричная норма согласована с некоторой векторной нормой (Предложение 3.3.4), и именно эту норму мы применимк обеим частям последнего равенства. Получим (k)x − x⋆ ≤ C x(k−1) − x⋆ ≤ kCk x(k−1) − x⋆ .Повторное применение этой оценки погрешности для x(k−1) , x(k−2) , . . .
,и т. д. вплоть до x(1) приводит к цепочке неравенствkx(k) − x⋆ k ≤ kCk · x(k−1) − x⋆ ≤ kCk2 · x(k−2) − x⋆ ≤ ......≤ kCkk · x(0) − x⋆ .(3.99)3433.9. Стационарные итерационные методыПравая часть неравенства (3.99) сходится к нулю при k → ∞ в силуусловия kCk < 1, поэтому последовательность приближений {x(k) }∞k=0действительно сходится к пределу x⋆ .Побочным следствием доказательства Предложения 3.9.1 является прояснение роли нормы матрицы перехода kCk как коэффициентаподавления погрешности приближений к решению СЛАУ в согласованной векторной норме.
Это следует из неравенств (3.99): чем меньшеkCk, тем быстрее убывает эта погрешность на каждом отдельном шагеитерационного процесса.Предложение 3.9.2 Для любой квадратной матрицы A и любогоǫ > 0 существует такая подчинённая матричная норма k · kǫ , чтоρ(A) ≤ kAkǫ ≤ ρ(A) + ǫ.Доказательство. Левое из выписанных неравенств было обоснованоранее в Предложении 3.3.9, и потому содержанием сформулированногорезультата является правое неравенство. Оно даёт, фактически, оценкуснизу для спектрального радиуса с помощью некоторой специальнойматричной нормы.С помощью преобразования подобия приведём матрицу A к жордановой канонической формеS −1 AS = J,гдеJ = λ11λ1......0001λ1λ21...000...λ2......,3443. Численные методы линейной алгебрыа S — некоторая неособенная матрица, осуществляющая преобразование подобия.
ПоложимDǫ := diag {1, ǫ, ǫ2 , . . . , ǫn−1 }— диагональной n × n-матрице с числами 1, ǫ, ǫ2 , . . . , ǫn−1 по главнойдиагонали. Тогда нетрудно проверить, что(SDǫ )−1 A(SDǫ ) = Dǫ−1 (S −1 AS)Dǫ= Dǫ−1 JDǫ = λ1ǫλ1......ǫλ1λ2ǫ......λ2......,— матрица в «модифицированной» жордановой форме, которая отличается от обычной жордановой формы присутствием ǫ вместо 1 на верхней побочной диагонали каждой жордановой клетки.Действительно, умножение на диагональную матрицу слева — этоумножение строк матрицы на соответствующие диагональные элементы, а умножение на диагональную матрицу справа равносильно умножению столбцов на элементы диагонали.
Два таких умножения — наDǫ−1 = diag {1, ǫ−1 , ǫ−2 , . . . , ǫ1−n } слева и на Dǫ = diag {1, ǫ, ǫ2 , . . . , ǫn−1 }справа — компенсируют друг друга на главной диагонали матрицы J.Но на верхней побочной диагонали, где ненулевые элементы имеют индексы (i, i + 1), от этих умножений остаётся множитель ǫ−i ǫi+1 = ǫ,i = 0, 1, . . . , n − 1.Определим теперь векторную нормуkxkǫ := (SDǫ )−1 x∞ .Тогда для подчинённой ей матричной нормы справедлива следующая3453.9. Стационарные итерационные методыцепочка оценок(SDǫ )−1 AxkAxkǫ∞kAkǫ = max= max x6=0 kxkǫx6=0(SDǫ )−1 x∞(SDǫ )−1 A(SDǫ )y ∞= maxпосле замены y = (SDǫ )−1 xy6=0kyk∞ −1(Dǫ JDǫ )y ∞= Dǫ−1 JDǫ ∞= maxy6=0kyk∞= максимум сумм модулей элементов в Dǫ−1 JDǫ по строкам≤ max |λi (A)| + ǫ = ρ(A) + ǫ,iгде λi (A) — i-ое собственное значение матрицы A. Неравенство припереходе к последней строке возникает по существу, так как матрицаможет иметь наибольшее по модулю собственное значение в жордановой клетке размера 1 × 1, в которой нет элементов побочной диагонали.Доказательство Теоремы 3.9.1 о сходимости одношагового стационарного итерационного процесса.Сначала покажем необходимость условия теоремы.
Пусть порождаемая в итерационном процессе последовательность {x(k) } сходится. Еёпределом при этом может быть только решение x⋆ системы x = Cx + d,т. е. должно быть limk→∞ x(k) = x⋆ , в чём можно убедиться, переходяв соотношенииx(k+1) = Cx(k) + dк пределу по k → ∞. Далее, вычитая почленно равенство для точногорешения x⋆ = Cx⋆ + d из расчётной формулы итерационного процессаx(k) = Cx(k−1) + d, получимx(k) − x⋆ = C(x(k−1) − x⋆ ),k = 1, 2, . . .
,3463. Численные методы линейной алгебрыоткудаx(k) − x⋆ = C(x(k−1) − x⋆ )= C 2 (x(k−2) − x⋆ )=······= C k (x(0) − x⋆ ).Так как левая часть этих равенств при k → ∞ сходится к нулю, тодолжна сходиться к нулю и правая, причём для любого вектора x(0) .В силу единственности и, следовательно, фиксированности решения x⋆вектор (x(0) − x⋆ ) также может быть произвольным. Но тогда сходимость погрешности к нулю возможна лишь при C k → 0.
На основанииПредложения 3.3.10 (стр. 261) заключаем, что спектральный радиус Cдолжен быть строго меньше 1.Достаточность. Если ρ(C) < 1, то, взяв положительное ǫ удовлетворяющим оценке ǫ < 1 − ρ(C), мы можем согласно Предложению 3.9.2выбрать матричную норму k · kǫ так, чтобы выполнялось неравенствоkCkǫ < 1. Далее в этих условиях применимо Предложение 3.9.1, которое утверждает сходимость итерационного процесса (3.98)x(k+1) ← Cx(k) + d,k = 0, 1, 2, . . . .Это завершает доказательство Теоремы 3.9.1.Доказанные результаты — теорема и два предложения — проясняютроль спектрального радиуса среди различных характеристик матрицы.Мы могли видеть в §3.3ж, что спектральный радиус не является матричной нормой, но, как выясняется, его с любой степенью точностиможно приблизить некоторой подчинённой матричной нормой.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
