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