Самарский А.А. Гулин А.В. - Численные методы (1078412), страница 17
Текст из файла (страница 17)
Значит, уменьшение шага Л приведет согласно (24) к увеличению погрешностей округления, и при некотором значении Л погрешности округления могут превзойти погрешность ревностного метода, пропорциональную Л'. Оценка (24) позволяет выбрать порядок шага Л, при котором погрешность округления еше не превосходит погрешности метода. Остановимся на этом подробнее. Поскольку матрица А системы (26) симметрична и положительно определена, ее число обусловленности равно отношению максимального собственного значения к минимальному, т. е.
ГЛАВА 2 ИТЕРАЦИОННЫЕ МЕТОДЫ РЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ $1. Примеры и канонический вид итерационных методов решения систем линейных алгебраических уравнений 1. Итерационные методы Якоби и Зейделя. Перейдем к изучению итерационных методов решения систем линейных алгебраических уравнений. Будем рассматривать систему Ах=1, где матрица А=(пн), 1, 1'=1, 2, ..., т, имеет обратную, х= = (хн х„..., х„)',1= (1„1„...,1 )'. Рассмотрим сначала два примера итерационных методов.
Для их построения предварительно преобразуем систему (1) к виду $ — 1 а ап ' ан (2) а- . а а" Ь Ь (при этом предполагается, что все аь отличны от нуля). Условимся, как обычно, считать значение суммы равным нулю, если верхний предел суммирования меньше нижнего. Так, уравнение (2) при 1= 1 имеет вид 1а х,= — '~' — х; + —. ам, 6 ан ан ! — Л В дальнейшем верхний индекс будет указывать номер итерации, например х" =(х"„х,",, „„х"), где х" ,— и-я итерация 1-й компоненты вектора х. В методе Якоби исходят из записи системы в виде (2), причем итерации определяются следуюшим образом: /, н и и п=О, 1,..., п„1=1, 2,..., т Начальные значения хн 1=1, 2, ..., нт задаются произвольно.
Окончание итераций определяется либо заданием максимального числа итераций кн либо услоннем шах ) х',.' " — х", ! ( е, агат где е Π— заданное число. Позже в $2 будет показано, что при определенных условиях на матрицу Л метод Якоби сходится, т. е. 'зх" — хз 0 при л- о (здесь х — точное решение системы (1), а х" — приближенное решение, полученное на л-й итерации). 82 Итерационный метод Зейделя имеет вид 1-1 !л !' 1 а ! -1ы 2! и (4) 1=1, 2,..., п2, п=0, 1,..., и,.
Чтобы понять, как находятся отсюда значения , т, запишем подробнее первые два уравнения ам Х":1= — 3 М Х". + — '1, 1 а1 !' а11 а11 1 —.— 2 Гл а х 1 — 21х У 2!хЛ+ !2 2 — 1 — ~ — ! а21 ~~ а,1 а,2 ! =2 ХЛ21 системы (4): (5) (6) Первая компонента х,""' вектора х'"' находится из уравнения (б) явным образом, для ее вычисления нужно знать вектор х" и значение 1!. При нахождении х,"" из уравнения (б) используются только что найденнос значение х',21 и известные значения х", 1=3, ..., т, с предыдущей итерации. Таким образом, компоненты х,'21 вектора х"" находятся из уравнения (4) последовательно, начиная с 1=1.
2. Матричная запись методов Якоби и Зейделя. Для исследования сходимости итерационных методов удобнее записывать их не в координатной, а в матричной форме. Представим матрицу А системы (1) в виде суммы трех матриц А =А,+2!+А„ (7) где 0=6!ай (а1м а„,, а„,„,) — диагональная матрица с той же главной диагональю, что и матрица А, матрица А,— нижняя треугольная и матрица А,— верхняя треугольная с нулевыми главными диагоналями, Например, при л2=3 матрицы Аь А2, 0 имеют вид А1= а„о О,А,= О О ам,0= О а1, О Представление системы (1) в форме (2) эквивалентно ее записи в виде матричного уравнения х= — 0 'А,х — 2)-'А2х+О !1.
или, что то же самое, Ох""+ (А,+А,) х'* =~. (8) аз Отсюда видно, что метод Якоби (3) в векторной записи выглядит следующим образом; х""= — 1)-'А,х — 0-!АЛхл+О '~, Метод Зейделя (4) записывается в виде х"+'= — Р-'А,х"" — Р-'А,х"+Р-'~ или (Р+А,) х"+'+А,х" =1'.
(9) Учитывая (7), методы (8) и (9) можно переписать соответственно в виде Р (х""' — хл) + Ахл = 1, (19) (Р+ А,) (х"-1 — хл) + Ахл = 7, (1 1) Из этой записи видно, что если итерационный метод сходится, то он сходится к решению исходной системы уравнений. Очень часто для ускорения сходимости в итерационные методы вводят числовые параметры, которые зависят, вообще говоря, от номера итерации. Например, в методы (10), (11) можно ввести итерационные параметры теы следующим образом: хЛ 1 хЛ вЂ” +Ахл=~ хлы Хлы хл (Р+ А,) + Ах" =т". тл+1 Способ выбора итерационных параметров выясняется при исследовании сходимостн. В теории итерационных методов существует два круга вопросов: а) при каких значениях параметров метод сходится, б) при каких значениях параметров сходимость будет наиболее быстрой (соответствующие параметры называются оптимальными).
В дальнейшем (см. й 4) мы подробнее остановимся на этих вопросах в связи с конкретными итерационными методами. Приведенные выше методы Якоби и Зейделя относятся к одношаговым итерационным методам, когда для нахождения х"+' требуется помнить только одну предыдущую итерацию х". Иногда ис пользуются н многошаговые итерационные методы, в которых х"+' определяется через значения х" на двух и более предыдущих итерациях, т. е. х"+'= Г(х', х" ',..., х" 1].
3. Каноническая форма одношаговых итерационных методов. На примере методов Якоби и Зейделя видно, что один и тот же итерационный метод можно записать многими различными способами. Поэтому целесообразно ввести какую-то стандартную форму записи итерационных методов. Условимся прежде всего записи вать итерационный метод ие в координатной форме, а в матричной, Теперь х„будет обозначать вектор, полученный в результате и-й итерации. Канонической формой одношагового итерационного метода решения системы (1) называется его запись в виде (12) Л11 84 с перемекным параметром тл ы называется итерационным методом Ричардсона, Для методов (13), (!4) известен способ выбора оптимальных втервцкокиых параметров в том случае, когда А — симметричная положительно определеквея матраца (см.
й б). Обобщением метода Зейделя (!!) является метод верхней релаксации хл 1 хл (!) + аАг) + Ахл = Е (15) где а)0 — заданный числовой параметр. В $ 2 будет показано, что в случае снмметрвчной положительно определенной матрицы А метод (15) сходятся врв 0<а(2. Для получения рзсчеткых формул перепашем (!5) в ваде (Е+а0-!А!)хл+!=((1 — га)Š— а0-!Ат)хи+ай 'й В покомпоневтпой записи получим !ы а," ! ап = (! — а) х" .— а ~г~ — х" + м —, а" ! а" /=о, н 1=1,2, ...,ы.
Здесь В„е,— матрица, задаю!цая тот или иной итерационный метод, тлю — итерационный параметр. Предполагается, что зада- 1 но начальное приближение х, и что существуют матрицы Вл, н=1, 2, ., п,— 1. Тогда пз уравнения (12) можно последователь- но определить все х„, и=1, 2, ..., пн Для нахождения хлы по из- вестным ) и х. достаточно решить систему уравнений В„„,х„~,=р„, где Е.= (В„ь,— т.ь,А) хл+тл „). Итерационный метод называют явным (неявным), если В„=Е (В„чьЕ), где Š— единичная матрица, Как правило, неявные ите- рационные методы имеет смысл применять лишь в том случае, когда каждую матрицу В„обратить легче, чем исходную матри- цу А (т.
е. когда решение системы уравнений с матрицей В„тре- бует меньше машинной памяти или времени или алгоритмически проще, чем решение исходной системы). Например, в методе Зей- деля приходится обращать треугольную матрицу. В дальнейшем (см. 5 4) будет показано, что преимушеством неявных методов яв- ляется более быстрая сходимость. Итерационный метод (12) называется стационарным, если В„+,— — В и т„+,=т не зависят от номера итерации, и нестационар- ным — в противоположном случае. Приведем еще несколько примеров втерзцвовпых методов.
Методом про- стой итерации кззывзют явный метод +Ахи= ! с постоянным параметром т. Яввый метод Хл ! хл + Ахл = ! (!4) л! Отсюда последовательно, начиная с г= 1, находим все х<ь+'. ю — ю) х — ю р — х;+ю ч чъ М а ь аи /=а х"н = (! 1 аи и ~~~ — хэ+ ив 'и . 1. а„, ' аи (=а «ю ам «ьь 1 (! ) а а 1 аи н т. д.
и 2. Исследование сходимости итерационных методов Рассмотрим систему линейных алгебравческнх уравнений Ах=1 (1) с невырожденной действительной матрицей А н одношаговый стационарный итерационный метод, записанный в каноническом виде В "" "+Ах„=1, и=О, 1, ..., (2) где х, задан. Говорят, что итерационный метод (2) сходится, если !!х„— х!! — 0 при л — оо. Под нормой вектора х будем понимать сейчас среднеквадратичную норму Решение х системы (1) будем рассматривать как элемент тсмерного евклидова пространства Н со скалярным произведе- нием (и, о) = ~ и;о;. При формулировке условий сходимости будут использоваться матричные неравенства. Дчя действительной матрицы С неравенство С~О означает, что (Сх, х) >О для всех хе=Н, хФО. Из неравенства С)0 следует, что существует константа б~О такая, что (Сх, х) =» б!!х!1а.
Действительно, если С)0 — симметричная матрица, то все ее собственные значения положительны и в качестве б можно взять минимальное собственное значение. Если С)0 — несимметричная матрица, то для любого хенН, хФО имеем (Сх, х) = — 1(Сх, х) + (х, С'х)] ) О, 2 где С' — матрица, транспонированная к С. Поэтому в качестве б можно взять минимальное собственное значение матрицы С,= =0,5(С+С'). Из оценки (Сх, х) ~б!!х!!* следует, что существует матрица С-'. Неравенство С)О означает, что (Сх, х) )О для всех х~Н. Если С~О, то С-' может и не существовать. 66 Перейдем к исследованию сходнмости итерационного метода (2). Погрешность метода на п-й итерации характеризуется вектором г„=х„— х, который согласно (1), (2) удовлетворяет однородному уравнению В "" " +Аз„=О, а=О, 1, ..., г,=х„— х. (3) Теорем а 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
