1611688890-f641c9ec8276824e4686da772eb56520 (826652), страница 57
Текст из файла (страница 57)
Кроме того, понятие спектрального радиуса оказывается чрезвычайно полезным при исследовании итерационных процессов и вообще степенейматрицы.Следствие из Предложения 3.9.2. Степени матрицы Ak сходятся кнулевой матрице при k → ∞ тогда и только тогда, когда ρ(A) < 1.В самом деле, ранее мы установили (Предложение 3.3.10), что изсходимости степеней матрицы Ak при k → ∞ к нулевой матрице вытекает ρ(A) < 1.
Теперь результат Предложения 3.9.2 позволяет сказать,3.9. Стационарные итерационные методы347что это условие на спектральный радиус является и достаточным: если ρ(A) < 1, то мы можем подобрать матричную норму так, чтобыkAk < 1, и тогда kAk k ≤ kAkk → 0 при k → ∞.С учётом Предложения 3.9.2 более точно переформулируются условия сходимости матричного ряда Неймана (Предложение 3.3.11): онсходится для матрицы A тогда и только тогда, когда ρ(A) < 1, а условие kAk < 1 является всего лишь достаточным.Заметим, что для несимметричных матриц нормы, близкие к спектральному радиусу, могут оказаться очень экзотичными и даже неестественными. Это видно из доказательства Теоремы 3.9.1.
Как правило, исследовать сходимость итерационных процессов лучше всё-таки вобычных нормах, часто имеющих практический смысл.Интересен вопрос о выборе начального приближения для итерационных методов решения СЛАУ. Иногда его решают из каких-то содержательных соображений, когда в силу физических и прочих содержательных причин бывает известно некоторое хорошее приближение крешению, а итерационный метод предназначен для его уточнения. Приотсутствии таких условий начальное приближение нужно выбирать наоснове других идей.Например, если в рекуррентном виде x = Cx + d, исходя из которого строятся сходящиеся итерации, матрица C имеет «малую» норму(относительно неё мы вправе предполагать, что kCk < 1), то тогдачленом Cx можно пренебречь. Как следствие, точное решение не сильно отличается от вектора свободных членов d, и поэтому можно взятьx(0) = d.
Этот вектор привлекателен также тем, что получается какпервая итерация при нулевом начальном приближении. Беря x(0) = d,мы экономим на этой итерации.3.9вПодготовка линейной системык итерационному процессуВ этом параграфе мы исследуем различные способы приведениясистемы линейных алгебраических уравненийAx = b(3.100)к равносильной системе в рекуррентном видеx = Cx + d,(3.101)3483. Численные методы линейной алгебрына основе которого можно организовывать одношаговый итерационныйпроцесс для решения (3.100). Фактически, это вопрос о том, как связанпредел стационарного одношагового итерационного процесса (3.98) синтересующим нас решением системы линейных алгебраических уравнений Ax = b. При этом практический интерес представляет, естественно, не всякое приведение системы (3.100) к виду (3.101), но лишь такое,которое удовлетворяет условию сходимости стационарного одношагового итерационного процесса. В предшествующем разделе мы показали, что им является неравенство ρ(C) < 1.Существует большое количество различных способов приведенияисходной СЛАУ к виду, допускающему применение итераций, большое разнообразие способов организации этих итерационных процессов и т.
п. Не претендуя на всеохватную теорию, мы рассмотрим нижелишь несколько общих приёмов подготовки и организации итерационных процессов.Простейший способ состоит в том, чтобы добавить к обеим частямисходной системы по вектору неизвестной переменной x, т. е.x + Ax = x + b,(3.102)а затем член Ax перенести в правую часть:x = (I − A)x + b.Иногда этот приём работает, но весьма часто он непригоден, так какспектральный радиус матрицы C = I − A оказывается не меньшимединицы.В самом деле, если λ — собственное значение для A, то для матрицы(I − A) собственным значением будет 1 − λ, и тогда 1 − λ > 1 привещественных отрицательных λ.
С другой стороны, если у матрицы Aесть собственные значения, вещественные или комплексные, бо́льшиепо модулю, чем 2, т. е. если |λ| > 2, то|1 − λ| = |λ − 1| ≥ |λ| − 1 > 1,и сходимости стационарных итераций мы также не получим.Из предшествующих рассуждений можно ясно видеть, что необходим активный способ управления свойствами матрицы C в получающейся системе рекуррентного вида x = Cx + d. Одним из важнейшихинструментов такого управления служит предобуславливание исходнойсистемы.3.9. Стационарные итерационные методы349Определение 3.9.1 Предобуславливанием системы линейных алгебраических уравнений Ax = b называется умножение слева обеих еёчастей на некоторую матрицу Λ.
Сама эта матрица Λ называетсяпредобуславливающей матрицей или, коротко, предобуславливателем.Цель предобуславливания — изменение (вообще говоря, улучшение)свойств матрицы A исходной системы Ax = b, вместо которой мы получаем систему(ΛA) x = Λb.Продуманный выбор предобуславливателя может, к примеру, изменитьвыгодным нам образом расположение спектра матрицы A, так необходимое для организации сходящихся итерационных процессов.Естественно выполнить предобуславливание до перехода к системе(3.102), т. е. до прибавления вектора неизвестных x к обеим частямисходной СЛАУ.
Поскольку тогда вместо системы Ax = b будем иметь(ΛA)x = Λb, то далее получаемx = (I − ΛA)x + Λb.Теперь в этом рекуррентном виде с помощью подходящего выбора Λможно добиваться требуемых свойств матрицы (I − ΛA).Каким образом следует выбирать предобуславливатели? Совершенно общего рецепта на этот счёт не существует, и теория разбиваетсяздесь на набор рекомендаций для ряда более или менее конкретныхважных случаев.Например, если в качестве предобуславливающей матрицы взятьΛ = A−1 или хотя бы приближённо равную обратной к A, то вместосистемы Ax = b получим (A−1 A)x = A−1 b, т. е.
систему уравненийIx = A−1 bили близкую к ней. Её матрица обладает всеми возможными достоинствами (хорошим диагональным преобладанием, малой обусловленностью и т. п.). Ясно, что нахождение подобного предобуславливателяне менее трудно, чем решение исходной системы, но сама идея примера весьма плодотворна. На практике в качестве предобуславливателей часто берут несложно вычисляемые обратные матрицы к той илииной «существенной» части матрицы A. Например, к главной диагонали матрицы или же к трём диагоналям — главной и двум побочным.3503.
Численные методы линейной алгебрыДругой способ приведения СЛАУ к рекуррентному виду основан нарасщеплении матрицы системы.Определение 3.9.2 Расщеплением квадратной матрицы A называется её представление в виде A = G + (−H) = G − H, где G — неособенная матрица.Если известно некоторое расщепление матрицы A, A = G − H, товместо исходной системы Ax = b мы можем рассмотреть(G − H) x = b,которая равносильнаGx = Hx + b,так чтоx = G−1 Hx + G−1 b.На основе полученного рекуррентного вида можно организовать итерацииx(k+1) ← G−1 Hx(k) + G−1 b,(3.103)задавшись каким-то начальным приближением x(0) .Иногда по ряду причин невыгодно обращать матрицу G явно, такчто расчётные формулы итерационного метода основывают на равенствеGx = Hx + b.Они могут выглядеть следующим образом(y ← Hx(k) + b,x(k+1) ← ( решение системы Gx = y ).Итерационные методы с такой организацией называют неявными.
В целом можно сказать, что всякое расщепление матрицы СЛАУ помогаетконструированию итерационных процессов.Но практическое значение имеют не все расщепления, а лишь те, вкоторых матрица G обращается «относительно просто», чтобы организация итерационного процесса не сделалсь более сложной задачей, чемрешение исходной СЛАУ. Другое требование к матрицам, образующимрасщепление, состоит в том, чтобы норма обратной для G, т.
е. kG−1 k,была «достаточно малой», поскольку kG−1 Hk ≤ kG−1 k kHk. Если G−13.9. Стационарные итерационные методы351имеет большую норму, то может оказаться ρ(G−1 H) > 1, и для итерационного процесса (3.103) не будут выполнены условия сходимости.Очень популярный способ расщепления матрицы A состоит в том,чтобы сделать элементы в G = (gij ) и H = (hij ) взаимнодополнительными, т.
е. такими, что gij hij = 0 для любых индексов i и j. Тогданенулевые элементы матриц G и (−H) совпадают с ненулевыми элементами A.В качестве примеров несложно обращаемых матриц можно указать1) диагональные матрицы,2) треугольные матрицы,3) трёхдиагональные матрицы,4)...23.Ниже в §3.9д и §3.9е мы подробно рассмотрим итерационные процессы,соответствующие первым двум пунктам этого списка.3.9гСкалярный предобуславливательи его оптимизацияНапомним, что скалярными матрицами (из-за своего родства скалярам) называются матрицы, кратные единичным, т. е.
имеющие видτ I, где τ ∈ R или C. Сейчас мы подробно исследуем описанную в предшествующем разделе возможность управления итерационным процессом на простейшем примере предобуславливания с помощью скалярнойматрицы, когда Λ = τ I, τ ∈ R и τ 6= 0.Итак, рассматриваем итерационный процессx(k+1) ← (I − τ A) x(k) + τ b,(3.104)τ = const, который часто называют методом простой итерации. Еслиλi , i = 1, 2, . .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
