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

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

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

е. det G 6= 0.Если известно некоторое расщепление матрицы A,A = G − H,то вместо исходной системы Ax = b можем рассмотреть(G − H) x = b,которая равносильнаGx = Hx + b,так чтоx = G−1 Hx + G−1 b.Если известно некоторое расщепление матрицы 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,k = 0, 1, 2, .

. . ,взяв какое-то начальное приближение x(0) .Иногда невыгодно обращать матрицу G явно, так что расчётныеформулы итерационного метода основывают на равенствеGx = Hx + b.Они могут выглядеть следующим образом y ← Hx(k) + b,x(k+1) ← ( решение системы Gx = y ),k = 0, 1, 2, . . .

.Итерационные методы с такой организацией называют неявными.Иногда невыгодно обращать матрицу G явно, так что расчётныеформулы итерационного метода основывают на равенствеGx = Hx + b.Они могут выглядеть следующим образом y ← Hx(k) + b,x(k+1) ← ( решение системы Gx = y ),k = 0, 1, 2, .

. . .Итерационные методы с такой организацией называют неявными.В целом, всякое расщепление матрицы СЛАУпомогает конструированию итерационных процессов.Практическое значение имеют не все расщепления, а лишь те,в которых матрица G обращается «относительно просто», чтобыорганизация итерационного процесса не сделалсь более сложной,чем решение исходной системы уравнений.Практическое значение имеют не все расщепления, а лишь те,в которых матрица G обращается «относительно просто», чтобыорганизация итерационного процесса не сделалсь более сложной,чем решение исходной системы уравнений.Другое требование к матрицам, образующим расщепление,состоит в том, чтобы kG−1 k была «достаточно малой», посколькуkG−1 Hk ≤ kG−1 k kHk.Если kG−1 k велика, то может оказатьсяρ(G−1 H) > 1,и для итерационного процессаx(k+1) ← G−1 Hx(k) + G−1 b,не выполнены условия сходимости.k = 0, 1, 2, .

. . ,Матрицы, для которых несложно находится обратная матрица:диагональные матрицы,треугольные матрицы,трёхдиагональные матрицы,...Матрицы, для которых несложно находится обратная матрица:диагональные матрицы,треугольные матрицы,трёхдиагональные матрицы,...Далее мы подробно рассмотрим итерационные процессы,соответствующие первым двум пунктам этого списка.Скалярный предобуславливательи его оптимизацияОпределениеСкалярными матрицами называются матрицы, кратныеединичным, т. е. имеющие вид τ I, где τ ∈ R или C.Скалярный предобуславливательи его оптимизацияОпределениеСкалярными матрицами называются матрицы, кратныеединичным, т.

е. имеющие вид τ I, где τ ∈ R или C.Исследуем управление итерационным процессомс помощью простейшего предобуславливания,когда предобуславливатель равен скалярной матрице:Λ = τ I,τ ∈ R и τ 6= 0.Тогда получаем итерационный процессx(k+1) ← (I − τ A) x(k) + τ b,k = 0, 1, 2, . . . .Скалярный предобуславливательи его оптимизацияОпределениеИтерационный процесс видаx(k+1) ← (I − τ A) x(k) + τ b,k = 0, 1, 2, . . . ,где τ = const, называют методом простой итерации илистационарным методом Ричардсона.Скалярный предобуславливательи его оптимизацияОпределениеИтерационный процесс видаx(k+1) ← (I − τ A) x(k) + τ b,k = 0, 1, 2, .

. . ,где τ = const, называют методом простой итерации илистационарным методом Ричардсона.Матрица оператора переходаметода простой итерацииравна (I − τ A).Скалярный предобуславливательи его оптимизацияЕсли λi , i = 1, 2, . . . , n, — собственные числа матрицы A, тособственные числа матрицы (I − τ A) равны (1 − τ λi ).Скалярный предобуславливательи его оптимизацияЕсли λi , i = 1, 2, . . . , n, — собственные числа матрицы A, тособственные числа матрицы (I − τ A) равны (1 − τ λi ).Ясно, что если среди λi имеются числас разным знаком вещественной части Re λi , то выражениеRe (1 − τ λi ) = 1 − τ Re λiпри любом фиксированном τ ∈ R будет иметькак меньшие 1 значения для каких-то λi ,так и бо́льшие чем 1 значения для некоторых других λi .Скалярный предобуславливательи его оптимизацияЕсли λi , i = 1, 2, .

. . , n, — собственные числа матрицы A, тособственные числа матрицы (I − τ A) равны (1 − τ λi ).Ясно, что если среди λi имеются числас разным знаком вещественной части Re λi , то выражениеRe (1 − τ λi ) = 1 − τ Re λiпри любом фиксированном τ ∈ R будет иметькак меньшие 1 значения для каких-то λi ,так и бо́льшие чем 1 значения для некоторых других λi .Как следствие, добиться соблюдения условия ρ(I − τ A) < 1,никаким выбором τ будет невозможно.Скалярный предобуславливательи его оптимизацияДалее рассмотрим практически важный частный случай, когдаA — симметричная положительно определённая матрица, так чтовсе λi , i = 1, 2, .

. . , n, вещественны и положительны.Скалярный предобуславливательи его оптимизацияДалее рассмотрим практически важный частный случай, когдаA — симметричная положительно определённая матрица, так чтовсе λi , i = 1, 2, . . . , n, вещественны и положительны.Обычно они не бывают известными, но нередко более или менееточно известен интервал их расположения на вещественной оси R.Будем предполагать, чтоλi ∈ [µ, M ] ⊂ R+ ,i = 1, 2, .

. . , n.Матрица (I − τ A) тогда также симметрична,и потому её спектральный радиус совпадает с 2-нормой.Матрица (I − τ A) тогда также симметрична,и потому её спектральный радиус совпадает с 2-нормой.Чтобы обеспечить сходимость итерационного процесса и добитьсяеё наибольшей скорости, нам нужно, согласно Теореме о сходимостистационарного итерационного процесса и оценкам погрешностиkx(k) − x⋆ k ≤ kCk · x(k−1) − x⋆ ≤ kCkk · x(0) − x⋆ найти значение τ , которое доставляет минимум величинеkCk2 = kI − τ Ak2 = max |1 − τ λi |.λiЗдесь максимум в правой части берётся по дискретному множествусобственных значений λi матрицы A, i = 1, 2, . . .

, n.Если о λi ничего не известно кроме того, что λi ∈ [µ, M ], тоестественно заменить максимизацию по множеству всех λi ,i = 1, 2, . . . , n, на максимизацию по их интервалу [µ, M ].Если о λi ничего не известно кроме того, что λi ∈ [µ, M ], тоестественно заменить максимизацию по множеству всех λi ,i = 1, 2, . . . , n, на максимизацию по их интервалу [µ, M ].Итак, будем искать оптимальное значение τ = τопт ,при котором достигаетсяminτmax 1 − τ λλ∈[µ,M ].Если о λi ничего не известно кроме того, что λi ∈ [µ, M ], тоестественно заменить максимизацию по множеству всех λi ,i = 1, 2, . . .

, n, на максимизацию по их интервалу [µ, M ].Итак, будем искать оптимальное значение τ = τопт ,при котором достигаетсяminτmax 1 − τ λλ∈[µ,M ].Обозначимg(τ ) :=max 1 − τ λµ≤λ≤Mи обратимся для минимизации функции g(τ )к наглядной иллюстрации.Пользуясь рисунком, исследуем поведение g(τ ) при изменении τ .10µλMГрафики функций 1 − τ λ для различных τ .При τ ≤ 0 выражение (1 − τ λ) не убывает по λ,и при λ > 0, очевидно, имеет значения не меньше 1.Тогда процесс простой итерации сходиться не будет.10µλMСледовательно, имеет смысл ограничиться только теми τ ,для которых (1 − τ λ) убывает по λ.

Это значения τ > 0.При 0 < τ ≤ M −1 выражение (1 − τ λ) на интервале λ ∈ [µ, M ]неотрицательно и монотонно убывает по λ.10λµMПоэтомуg(τ ) = max |1 − τ λ| = 1 − τ µλи достигается на левом конце интервала [µ, M ].При τ > M −1 велична 1 − τ M отрицательна, так что графикфункции 1 − τ λ на интервале λ ∈ [µ, M ] пересекает ось абсцисс.1µ0λMТогдаg(τ ) = max 1 − τ µ, −(1 − τ M ) ,причём на левом конце (1 − τ µ) убывает с ростом τ ,а на правом конце −(1 − τ M ) растёт с ростом τ .При некотором τ = τопт наступает момент, когда эти значенияна концах интервала [µ, M ] сравниваются друг с другом:1 − τ µ = −(1 − τ M ).Он и является моментом достижения оптимума, посколькудальнейшее увеличение τ приводит к росту −(1 − τ M )на правом конце интервала,уменьшение τ ведёт к росту (1 − τ µ) на левом конце.В любом из этих случаев g(τ ) возрастает.Отсюдаτопт =2.M +µЗначение минимума g(τ ) равно коэффициенту подавлениянормы погрешности (как следствие оценок сходимости):kI − τопт Ak2 = min max |1 − τ λ|τλ∈[µ,M ]= 1 − τопт µ= 1−M −µ2·µ =.M +µM +µЯсно, что kI − τопт Ak2 < 1, т.

е. даже с помощью простейшегоскалярного предобуславливателя мы добились сходимостиитерационного процесса.Оценим kI − τопт Ak2 через число обусловленности cond2 (A).Так какµ ≤ λmin (A) ≤ λmax (A) ≤ M,тоcond2 (A) =λmax (A)M≤.λmin (A)µОценим kI − τопт Ak2 через число обусловленности cond2 (A).Так какµ ≤ λmin (A) ≤ λmax (A) ≤ M,тоcond2 (A) =λmax (A)M≤.λmin (A)µФункцияf (x) =2x−1= 1−x+1x+1возрастает при положительных x, из чего можем заключить, чтоkI − τопт Ak2 =M/µ − 1cond2 (A) − 1M −µ=≥.M +µM/µ + 1cond2 (A) + 1Получается, что чем больше cond(A),т. е. чем хуже обусловленность матрицы A исходной системы,тем медленнее сходимость нашего итерационного процесса.Получается, что чем больше cond(A),т. е. чем хуже обусловленность матрицы A исходной системы,тем медленнее сходимость нашего итерационного процесса.Это характерно для поведения многих итерационных методов.Получается, что чем больше cond(A),т.

е. чем хуже обусловленность матрицы A исходной системы,тем медленнее сходимость нашего итерационного процесса.Это характерно для поведения многих итерационных методов.Иначе говоря, число обусловленности матрицы cond(A)характеризует не только чувствительность решения к возмущениями ошибкам, но и скорость сходимости итерационных процессов!Наибольшую трудность на практике представляет нахождение µ— нижней границы спектра матрицы системы линейных уравнений.Иногда мы можем ничего не знать о её конкретной величинекроме того, что µ ≥ 0.Наибольшую трудность на практике представляет нахождение µ— нижней границы спектра матрицы системы линейных уравнений.Иногда мы можем ничего не знать о её конкретной величинекроме того, что µ ≥ 0.В этих условиях развитая нами теория применима лишь частично.Наибольшую трудность на практике представляет нахождение µ— нижней границы спектра матрицы системы линейных уравнений.Иногда мы можем ничего не знать о её конкретной величинекроме того, что µ ≥ 0.В этих условиях развитая нами теория применима лишь частично.Оптимальным значением параметра τ следует, очевидно, взятьτопт =2.MМетод простой итерации будет при этом сходиться,но никаких оценок его скорости сходимости дать уже нельзя.Для организации итерационных процессов нужнаинформация о спектре матрицы системы уравнений.Как можно получатьоценки спектра матрицы?Круги ГершгоринаТеорема ГершгоринаДля любой вещественной или комплексной n × n-матрицы A = (aij )все собственные значения λ(A) расположены в объединениикруговPкомплексной плоскости с центрами aii и радиусами j6=i |aij |,i = 1, 2, .

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

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