1611688847-5b7354cc83380cb6c671f7c9dd5f83f8 (826648), страница 16

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 16)

. . .Сходимость стационарныходношаговых итерационных методовРассмотрим далее стационарный одношаговый итерационныйпроцессx(k+1) ← Cx(k) + d,k = 0, 1, 2, . . . .ОпределениеСистемы линейных уравнений видаx = Cx + d,в котором вектор неизвестных переменных выделен в одной изчастей, мы будем называть системами в рекуррентном виде.Сходимость стационарныходношаговых итерационных методовТеоремаПусть система уравнений x = Cx + d имеет единственное решение.Стационарный одношаговый итерационный процессx(k+1) ← Cx(k) + d,k = 0, 1, 2, . . . ,сходится при любом начальном приближении x(0) тогда и толькотогда, когдаρ(C) < 1,т.

е. когда спектральный радиус матрицы C меньше единицы.Оговорка о единственности решения существенна.Если взять, к примеру, C = I и d = 0, то рассматриваемая системаобратится в тождество x = x, имеющее решением любой вектор.Оговорка о единственности решения существенна.Если взять, к примеру, C = I и d = 0, то рассматриваемая системаобратится в тождество x = x, имеющее решением любой вектор.Соответствующий итерационный процессx(k+1) ← x(k) ,k = 0, 1, 2, .

. . ,будет сходиться из любого начального приближения, хотяспектральный радиус матрицы перехода C равен единице.Оговорка о единственности решения существенна.Если взять, к примеру, C = I и d = 0, то рассматриваемая системаобратится в тождество x = x, имеющее решением любой вектор.Соответствующий итерационный процессx(k+1) ← x(k) ,k = 0, 1, 2, . . .

,будет сходиться из любого начального приближения, хотяспектральный радиус матрицы перехода C равен единице.Доказательство теоремы будет разбито на две части, результаткаждой из которых представляет самостоятельный интерес.Сходимость стационарныходношаговых итерационных методовПредложение 1Если kCk < 1 в какой-нибудь матричной норме, то стационарныйодношаговый итерационный процессx(k+1) ← Cx(k) + d,k = 0, 1, 2, .

. . ,сходится при любом начальном приближении x(0) .Сходимость стационарныходношаговых итерационных методовПредложение 1Если kCk < 1 в какой-нибудь матричной норме, то стационарныйодношаговый итерационный процессx(k+1) ← Cx(k) + d,k = 0, 1, 2, . . . ,сходится при любом начальном приближении x(0) .Доказательство.Сходимость стационарныходношаговых итерационных методовПредложение 1Если kCk < 1 в какой-нибудь матричной норме, то стационарныйодношаговый итерационный процессx(k+1) ← Cx(k) + d,k = 0, 1, 2, . .

. ,сходится при любом начальном приближении x(0) .Доказательство.Мы можем указать в явном виде предел, к которому сходитсяпоследовательность {x(k) }, порождаемая итерационным процессом,и строить доказательство с учётом этого знания.Если kCk < 1 для какой-нибудь подчинённой матричной нормы,то матрица (I − C) неособенна и имеет обратную (I − C)−1 .Если kCk < 1 для какой-нибудь подчинённой матричной нормы,то матрица (I − C) неособенна и имеет обратную (I − C)−1 .В самом деле, если kCk < 1, то и спектральный радиус матрицы Cтоже меньше единицы,ρ(C) < 1,то есть все собственные значения λ(C) матрицы C по модулюменьше единицы:|λ(C)| < 1.Если kCk < 1 для какой-нибудь подчинённой матричной нормы,то матрица (I − C) неособенна и имеет обратную (I − C)−1 .В самом деле, если kCk < 1, то и спектральный радиус матрицы Cтоже меньше единицы,ρ(C) < 1,то есть все собственные значения λ(C) матрицы C по модулюменьше единицы:|λ(C)| < 1.Но у матрицы (I − C) собственные значения равны 1 − λ(C), итогда справедливо1 − λ(C) 6= 0.Поэтому матрица (I − C) не имеет нулевых собственных значений,т.

е. det(I − C) 6= 0.Из неособенности матрицы (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⋆ ,k = 1, 2, . . . .В самом деле, еслиx⋆ = Cx⋆ + d,то, вычитая это равенство из соотношенийx(k) = Cx(k−1) + d,k = 1, 2, . . .

,получимx(k) − x⋆ = C x(k−1) − x⋆ ,k = 1, 2, . . . .Применим к обеим частям последнего равенства векторную нормуи воспользуемся неравенством согласованности для подчинённойматричной нормы: (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⋆ .Правая часть этого неравенства сходится к нулюпри k → ∞ в силу условия kCk < 1.Повторное применение этой оценки погрешности для 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⋆ .Правая часть этого неравенства сходится к нулюпри k → ∞ в силу условия kCk < 1.Поэтому последовательность приближений {x(k) }∞k=0в самом деле сходится к пределу x⋆ .Побочным следствием доказательства Предложения являетсяпрояснение роли нормы матрицы перехода kCk.Величина kCk при kCk < 1 — коэффициент подавленияпогрешности приближений к решению системы в согласованнойвекторной норме.Это следует из неравенствkx(k) − x⋆ k ≤ kCkk · x(0) − x⋆ — чем меньше kCk, тем быстрее убывает эта погрешность накаждом отдельном шаге итерационного процесса.Сходимость стационарныходношаговых итерационных методовПредложение 2Для любой квадратной матрицы A и любого ǫ > 0 существуеттакая подчинённая матричная норма k · kǫ , чтоρ(A) ≤ kAkǫ ≤ ρ(A) + ǫ.Сходимость стационарныходношаговых итерационных методовПредложение 2Для любой квадратной матрицы A и любого ǫ > 0 существуеттакая подчинённая матричная норма k · kǫ , чтоρ(A) ≤ kAkǫ ≤ ρ(A) + ǫ.Доказательство.Левое из выписанных неравенств было обосновано раньше.Сходимость стационарныходношаговых итерационных методовПредложение 2Для любой квадратной матрицы A и любого ǫ > 0 существуеттакая подчинённая матричная норма k · kǫ , чтоρ(A) ≤ kAkǫ ≤ ρ(A) + ǫ.Доказательство.Левое из выписанных неравенств было обосновано раньше.Потому содержанием сформулированного результата являетсяправое неравенство.

Оно даёт, фактически, оценку снизу дляспектрального радиуса с помощью некоторой специальнойматричной нормы.С помощью преобразования подобия приведём матрицу Aк жордановой канонической формеS −1 AS = J,гдеJ = λ11λ1......0001λ1λ21...0..0.λ20а S — некоторая неособенная матрица подобия.......,ПоложимDǫ := diag {1, ǫ, ǫ2 , . . . , ǫn−1 }— диагональной n × n-матрице с числами 1, ǫ, ǫ2 , .

. . , ǫn−1 поглавной диагонали. Тогда(SDǫ )−1 A(SDǫ ) = Dǫ−1 (S −1 AS)Dǫ−1= Dǫ JDǫ = λ1ǫλ1......ǫλ1λ2ǫ......λ2.......(SDǫ )−1 A(SDǫ ) — матрица, отличающаяся от жордановой формыприсутствием ǫ вместо 1 на наддиагонали жордановых клеток.(SDǫ )−1 A(SDǫ ) — матрица, отличающаяся от жордановой формыприсутствием ǫ вместо 1 на наддиагонали жордановых клеток.Умножение на диагональную матрицу слева — это умножениестрок матрицы на диагональные элементы.Умножение на диагональную матрицу справа равносильноумножению столбцов на диагональные элементы.(SDǫ )−1 A(SDǫ ) — матрица, отличающаяся от жордановой формыприсутствием ǫ вместо 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.Но на наддиагонали, где ненулевые элементы имеют индексы(i, i + 1), от этих умножений остаётся множительǫ−i ǫi+1 = ǫ,i = 0, 1, . . . , n − 1.Определим теперь векторную норму какkxkǫ := (SDǫ )−1 x∞ .Покажем, что она удовлетворяет условию Предложения.Тогда для подчинённой ей матричной нормы справедливаследующая цепочка оценок(SDǫ )−1 AxkAxkǫ∞kAkǫ = max= max x6=0 kxkǫx6=0 (SDǫ )−1 x∞(SDǫ )−1 A(SDǫ )y ∞= maxy6=0kyk∞после замены y = (SDǫ )−1 x −1(Dǫ JDǫ )y ∞= Dǫ−1 JDǫ ∞= maxy6=0kyk∞= максимум сумм модулей элементов в Dǫ−1 JDǫ по строкам≤ max |λi (A)| + ǫ = ρ(A) + ǫ,iгде λi (A) — i-ое собственное значение матрицы A.Неравенство при переходе к последней строке возникает посуществу, так как матрица может иметь наибольшее по модулюсобственное значение в жордановой клетке размера 1 × 1.В таких клетках нет элементов наддиагонали.Неравенство при переходе к последней строке возникает посуществу, так как матрица может иметь наибольшее по модулюсобственное значение в жордановой клетке размера 1 × 1.В таких клетках нет элементов наддиагонали.Предложение доказано.Вычислительные методыанализа и линейной алгебрыКурс лекцийС.П.

ШарыйКафедра математического моделирования НГУЛекция 13 декабря 2017 г.Сходимость стационарныходношаговых итерационных методовПредложение 2Для любой квадратной матрицы A и любого ǫ > 0 существуеттакая подчинённая матричная норма k · kǫ , чтоρ(A) ≤ kAkǫ ≤ ρ(A) + ǫ.Сходимость стационарныходношаговых итерационных методовПредложение 2Для любой квадратной матрицы A и любого ǫ > 0 существуеттакая подчинённая матричная норма k · kǫ , чтоρ(A) ≤ kAkǫ ≤ ρ(A) + ǫ.Доказательство.Левое из выписанных неравенств было обосновано раньше.Сходимость стационарныходношаговых итерационных методовПредложение 2Для любой квадратной матрицы A и любого ǫ > 0 существуеттакая подчинённая матричная норма k · kǫ , чтоρ(A) ≤ kAkǫ ≤ ρ(A) + ǫ.Доказательство.Левое из выписанных неравенств было обосновано раньше.Потому содержанием сформулированного результата являетсяправое неравенство.

Характеристики

Список файлов лекций