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

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

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

Оно даёт, фактически, оценку снизу дляспектрального радиуса с помощью некоторой специальнойматричной нормы.С помощью преобразования подобия приведём матрицу 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.В таких клетках нет элементов наддиагонали.Предложение доказано.Доказательство теоремы о сходимости одношаговогостационарного итерационного процесса.Сначала покажем необходимость условия теоремы.Доказательство теоремы о сходимости одношаговогостационарного итерационного процесса.Сначала покажем необходимость условия теоремы.Пусть порождаемая в итерационном процессепоследовательность {x(k) } сходится.Доказательство теоремы о сходимости одношаговогостационарного итерационного процесса.Сначала покажем необходимость условия теоремы.Пусть порождаемая в итерационном процессепоследовательность {x(k) } сходится.Её пределом при этом может быть только решение x⋆ системыx = Cx + d, т.

е. должно бытьlim x(k) = x⋆ ,k→∞в чём можно убедиться, переходя в соотношении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, . . . .Вычитая почленно равенство для точного решенияx⋆ = Cx⋆ + dиз расчётной формулы итерационного процессаx(k) = Cx(k−1) + d,получимx(k) − x⋆ = C(x(k−1) − x⋆ ),k = 1, 2, . . .

.Поэтомуx(k) − x⋆ = C(x(k−1) − x⋆ )= C 2 (x(k−2) − x⋆ )=······= C k (x(0) − x⋆ ).Левая часть этих равенствx(k) − x⋆при k → ∞ сходится к нулю, поэтому должна сходиться к нулю иправая часть —C k (x(0) − x⋆ ),причём для любого начального вектора x(0) .Левая часть этих равенствx(k) − x⋆при k → ∞ сходится к нулю, поэтому должна сходиться к нулю иправая часть —C k (x(0) − x⋆ ),причём для любого начального вектора x(0) .В силу единственности и, следовательно, фиксированности решенияx⋆ вектор (x(0) − x⋆ ) также может быть произвольным.

Но тогдасходимость погрешности к нулю возможна лишь при C k → 0.Левая часть этих равенствx(k) − x⋆при k → ∞ сходится к нулю, поэтому должна сходиться к нулю иправая часть —C k (x(0) − x⋆ ),причём для любого начального вектора x(0) .В силу единственности и, следовательно, фиксированности решенияx⋆ вектор (x(0) − x⋆ ) также может быть произвольным. Но тогдасходимость погрешности к нулю возможна лишь при C k → 0.На основании доказанного ранее Предложения о спектральномрадиусе матрицы, степени которой сходятся к нулю, заключаем,что ρ(C) < 1.Это и требовалось установить.Достаточность.Достаточность.Пусть ρ(C) < 1.Взяв положительное ǫ удовлетворяющим оценкеǫ < 1 − ρ(C),мы можем согласно Предложению 2 выбрать матричную нормуk · kǫ так, чтобы выполнялось неравенствоkCkǫ < 1.Достаточность.Пусть ρ(C) < 1.Взяв положительное ǫ удовлетворяющим оценкеǫ < 1 − ρ(C),мы можем согласно Предложению 2 выбрать матричную нормуk · kǫ так, чтобы выполнялось неравенствоkCkǫ < 1.Далее в этих условиях применимо доказанное Предложение 1,которое утверждает сходимость итерационного процессаx(k+1) ← Cx(k) + d,k = 0, 1, 2, .

. . .Это завершает доказательство теоремы.Итерационные методы для решениясистем линейных алгебраических уравненийИщем решение системы линейных алгебраических уравненийAx = bc квадратной неособенной матрицей Aс помощью итерационного процессаx(k+1) ← Cx(k) + d,k = 0, 1, 2, . . . .Подготовка системы линейных уравненийк итерационному процессуИсследуем различные способы приведениясистемы линейных алгебраических уравненийAx = bк равносильной системе в рекуррентном видеx = Cx + d,на основе которой можно организовыватьодношаговый стационарный итерационный процесс.Фактически, это вопрос о том, как связан предел стационарногоодношагового итерационного процессаx(k) ← Cx(k−1) + d,k = 0, 1, 2, .

. . ,с решением исходной системы линейных уравнений Ax = b.Фактически, это вопрос о том, как связан предел стационарногоодношагового итерационного процессаx(k) ← Cx(k−1) + d,k = 0, 1, 2, . . . ,с решением исходной системы линейных уравнений Ax = b.Практический интерес представляетне всякое приведение системы Ax = b к видуx = Cx + d.Необходимо, чтобы оно удовлетворяло условию сходимостистационарного одношагового итерационного процесса:ρ(C) < 1.Подготовка системы линейных уравненийк итерационному процессуСуществует большое количество различных способовприведения исходной системы линейных уравнений к виду,допускающему применение итераций,Подготовка системы линейных уравненийк итерационному процессуСуществует большое количество различных способовприведения исходной системы линейных уравнений к виду,допускающему применение итераций,большое разнообразие способов организацииэтих итерационных процессов и т.

п.Подготовка системы линейных уравненийк итерационному процессуСуществует большое количество различных способовприведения исходной системы линейных уравнений к виду,допускающему применение итераций,большое разнообразие способов организацииэтих итерационных процессов и т. п.Не претендуя на всеохватную теорию,мы рассмотрим ниже лишь несколько общихприёмов подготовки и организации итерационных процессов.Простейший способ состоит в том, чтобы добавить к обеим частямисходной системы по вектору неизвестной переменной x, т.

е.перейти отAx = b,к системеx + Ax = x + b,а затем член Ax перенести в правую часть:x = (I − A) x + b.Простейший способ состоит в том, чтобы добавить к обеим частямисходной системы по вектору неизвестной переменной x, т. е.перейти отAx = b,к системеx + Ax = x + b,а затем член Ax перенести в правую часть:x = (I − A) x + b.Иногда этот приём работает, но весьма часто он непригоден,так как ρ(I − A) оказывается не меньшим единицы.Если λ — собственное значение для A,то для матрицы (I − A) собственным значением будет 1 − λ,и тогда 1 − λ > 1 при λ < 0.Если λ — собственное значение для A,то для матрицы (I − A) собственным значением будет 1 − λ,и тогда 1 − λ > 1 при λ < 0.Если у матрицы A есть собственные значения бо́льшие по модулю,чем 2, т.

е. если |λ| > 2, то|1 − λ| = |λ − 1| ≥ |λ| − 1 > 1,и сходимости стационарных итераций мы также не получим.ПредобуславливаниеИз предшествующих рассуждений видно, что необходимактивный способ управления свойствами матрицы Cв системе рекуррентного вида x = Cx + d.ПредобуславливаниеИз предшествующих рассуждений видно, что необходимактивный способ управления свойствами матрицы Cв системе рекуррентного вида x = Cx + d.ОпределениеПредобуславливанием системы линейных алгебраическихуравнений Ax = b называется умножение слева обеих её частейна некоторую матрицу Λ.Сама эта матрица Λ называется предобуславливающей матрицейили, коротко, предобуславливателем.ПредобуславливаниеВместо исходной системыAx = bмы получаем систему(ΛA) x = Λb.Цель предобуславливания — улучшение свойств матрицы Aисходной системы.Продуманный выбор предобуславливателя может, к примеру,изменить выгодным образом расположение спектра матрицы A,необходимое для сходимости итерационных процессов.Естественно выполнить предобуславливание до перехода от Ax = bк системеx = (I − A)x + b.т.

е. до прибавления вектора неизвестных x к обеим частямисходной системы.Естественно выполнить предобуславливание до перехода от Ax = bк системеx = (I − A)x + b.т. е. до прибавления вектора неизвестных x к обеим частямисходной системы.Вместо системы Ax = b получаем (ΛA)x = Λb,и потому новый рекуррентный видx = (I − ΛA)x + Λb.С помощью подходящего выбора Λ можно добиватьсятребуемых свойств матрицы (I − ΛA).Каким образом следует выбирать предобуславливатели?Совершенно общего рецепта не существует.Теория разбивается на набор рекомендацийдля ряда более или менее конкретных важных случаев.Каким образом следует выбирать предобуславливатели?Совершенно общего рецепта не существует.Теория разбивается на набор рекомендацийдля ряда более или менее конкретных важных случаев.Идея.Если в качестве предобуславливающей матрицы взятьΛ ≈ A−1 ,то вместо системы Ax = b получим близкую к системе(A−1 A)x = A−1 b.Матрица системыIx = A−1 bи близких к ней систем обладает всеми достоинствами (хорошимдиагональным преобладанием, малой обусловленностью и т.

п.).Нахождение подобного предобуславливателя не менее трудно,чем решение исходной системы, но сама идея весьма плодотворна.Матрица системыIx = A−1 bи близких к ней систем обладает всеми достоинствами (хорошимдиагональным преобладанием, малой обусловленностью и т. п.).Нахождение подобного предобуславливателя не менее трудно,чем решение исходной системы, но сама идея весьма плодотворна.На практике в качестве предобуславливателей часто берутнесложно вычисляемые обратные матрицы к той или иной«существенной» части матрицы A.Например, к главной диагонали матрицы или же к главнойдиагонали вместе с поддиагональю и наддиагональю.Расщепление матрицы линейной системы— ещё один способ приведения системы линейных алгебраическихуравнений Ax = b к рекуррентному виду.Расщепление матрицы линейной системы— ещё один способ приведения системы линейных алгебраическихуравнений Ax = b к рекуррентному виду.ОпределениеРасщеплением квадратной матрицы A называется её представлениев видеA = G + (−H) = G − H,где G — неособенная матрица, т.

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

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