1611688890-f641c9ec8276824e4686da772eb56520 (826652), страница 58

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

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

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

е. соблюдения условия ρ(I − τ A) < 1, никаким выбором τ будетневозможно.Далее рассмотрим практически важный частный случай, когда A— симметричная положительно определённая матрица, так что все λi ,i = 1, 2, . . . , n, вещественны и положительны. Обычно они не бываютизвестными, но нередко более или менее точно известен интервал ихрасположения на вещественной оси R. Будем предполагать, что λi ∈[µ, M ], i = 1, 2, . . . , n.Матрица (I −τ A) тогда также симметрична, и потому её спектральный радиус совпадает с 2-нормой. Чтобы обеспечить сходимость итерационного процесса и добиться её наибольшей скорости, нам нужно,согласно Теореме 3.9.1 и оценкам убывания погрешности (3.99), найтизначение τ , которое доставляет минимум величинеkI − τ Ak2 = max |1 − τ λi |.λiЗдесь максимум в правой части берётся по дискретному множествусобственных значений λi матрицы A, i = 1, 2, .

. . , n. В условиях, когдао расположении λi ничего не известно кроме их принадлежности интервалу [µ, M ], естественно заменить максимизацию по множеству λi ,i = 1, 2, . . . , n, на максимизацию по всему объемлющему его интервалу [µ, M ]. Итак, мы будем искать оптимальное значение τ = τопт , прикотором достигаетсяminmax |1 − τ λ| .τλ∈[µ,M]Обозначивg(τ ) :=max |1 − τ λ|,µ≤λ≤Mобратимся для минимизации функции g(τ ) к геометрической иллюстрации Рис.

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

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

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

Иногда мы даже можемничего не знать о её конкретной величине кроме того, что µ ≥ 0. Вэтих условиях развитая нами теория применима лишь частично. Оптимальным значением параметра τ следует, очевидно, взятьτопт =2,Mметод простой итерации (3.104) будет при этом сходиться, но никакихоценок его скорости сходимости дать уже нельзя.3553.9.

Стационарные итерационные методы3.9дИтерационный метод ЯкобиПусть в системе линейных алгебраических уравнений Ax = b диагональные элементы матрицы A = (aij ) отличны от нуля, т. е. aii 6= 0,i = 1, 2, . . . , n. Это условие нисколько не ограничит общность нашихрассуждений, так как в неособенной квадратной матрице A с помощьюперестановки строк (соответствующей перестановке уравнений системы) всегда можно сделать диагональные элементы ненулевыми.В развёрнутом виде система линейных алгебраических уравненийимеет видnXaij xj = bi ,i = 1, 2, .

. . , n,j=1и, выражая i-ю компоненту вектора неизвестных из i-го уравнения,получимX1 i = 1, 2, . . . , n.xi =bi −aij xj  ,aiij6=iНетрудно понять, что эти соотношения дают представление исходнойСЛАУ в рекуррентном виде x = T (x), необходимом для организацииодношаговых итераций x(k+1) ← T (x(k) ), k = 0, 1, 2, . . . . Здесьи⊤T (x) = T1 (x), T2 (x), . . . , Tn (x)Ti (x) =1 bi −aiiXj6=iaij xj  ,i = 1, 2, . . . , n.Псевдокод соответствующего итерационного процесса представленв Табл. 3.5 (где вспомогательная переменная k — это счётчик числаитераций).

Он был предложен ещё в середине XIX века К.Г. Якоби ичасто (особенно в старых книгах по численным методам) называется«методом одновременных смещений». Под «смещениями» здесь имеются в виду коррекции компонент очередного приближения к решению, выполняемые на каждом шаге итерационного метода. Смещениякоррекции «одновременны» потому, что все компоненты следующегоприближения x(k+1) насчитываются независимо друг от друга по единообразным формулам, основанным на использовании лишь предыдущего приближения x(k) . В следующем параграфе будет рассмотрен3563.

Численные методы линейной алгебрыТаблица 3.5. Итерационный метод Якоби для решения СЛАУk ← 0;выбираем начальное приближение x(0) ;DO WHILE ( метод не сошёлся )DO FOR i = 1 TO nX1(k)(k+1) bi −aij xj ←xiaiij6=iEND DOk ← k +1;END DOитерационный процесс, устроенный несколько по-другому, в которомсмещения-коррекции компонент очередного приближения к решению«не одновременны» в том смысле, что находятся последовательно одназа другой не только из предыдущего приближения, но ещё и друг издруга.Пусть A = L̃ + D + Ũ , гдеL̃ = 00a210a31...a32.........an1an2· · · an,n−1 00D = diag {a11 , a22 , .

. . , ann }— строго нижняятреугольная матрица.— диагональ матрицы A,3573.9. Стационарные итерационные методыŨ = 0 a1200· · · a1,n−1 a1n... a2,n−1 a2n .... ..... 0an−1,n— строго верхняятреугольная матрица.0Тогда итерационный метод Якоби может быть представлен как метод,основанный на таком расщеплении матрицы системы A = G − H (см.§3.9в), чтоG = D,H = −(L̃ + Ũ ).Соответственно, в матричном виде метод Якоби записывается какx(k+1) ← −D−1 (L̃ + Ũ ) x(k) + D−1 b,k = 0, 1, 2, . .

. .Теперь нетрудно дать условия его сходимости, основываясь на общем результате о сходимости стационарных одношаговых итераций(Теорема 3.9.1). Именно, метод Якоби сходится из любого начальньного приближения тогда и только тогда, когдаρ D−1 (L̃ + Ũ ) < 1.Матрица D−1 (L̃ + Ũ ) просто выписывается по исходной системе иимеет вид0a12 /a11 . . . a1n /a110. . . a2n /a22  a21 /a22(3.107).............an1 /ann an2 /ann . .

.0Но нахождение её спектрального радиуса является задачей, сравнимойпо сложности с выполнением самого итерационного процесса, и потому применять его для исследования сходимости метода Якоби непрактично. Для быстрой и грубой оценки спектрального радиуса можновоспользоваться какой-нибудь матричной нормой и результатом Предложения 3.3.9.Полезен также следующий достаточный признак сходимости:Теорема 3.9.2 Если в системе линейных алгебраических уравненийAx = b квадратная матрица A имеет диагональное преобладание, то3583. Численные методы линейной алгебрыметод Якоби для решения этой системы сходится при любом начальном приближении.Доказательство. Диагональное преобладание в матрице A = (aij )означает, чтоX|aii | >|aij |,i = 1, 2, .

. . , n.j6=iСледовательно, X aij < 1, aii i = 1, 2, . . . , n,j6=iчто равносильноmax1≤i≤nX aij aii j6=i!< 1.В выражении, стоящем в левой части неравенства, легко угадать подчинённую чебышёвскую норму (∞-норму) матрицы D−1 (L̃ + Ũ ), которая была выписана нами в (3.107). Таким образом, −1D (L̃ + Ũ ) < 1,∞откуда, ввиду результата Предложения 3.9.1, следует доказываемое. Итерационный метод Якоби был изобретён в середине XIX века исейчас при практическом решении систем линейных алгебраическихуравнений используется редко, так как существенно проигрывает поэффективности более современным численным методам.24 Тем не менее, совсем забывать метод Якоби было бы преждевременным. Лежащая в его основе идея выделения из оператора системы уравнений«диагональной части» достаточно плодотворна и может быть с успехомприменена в различных ситуациях.Рассмотрим, к примеру, систему уравненийAx = b(x),в которой A — n×n-матрица, b(x) — некоторая вектор-функция от неизвестной переменной x.

В случае, когда b(x) — нелинейная функция, никакие численные методы для решения СЛАУ здесь уже неприменимы,24 Примеры применения и детальные оценки скорости сходимости метода Якобидля решения модельных задач математической физики можно увидеть в [37].3593.9.

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

Список файлов книги