Беклемишев - Дополнительные главы линейной алгебры (947281), страница 37
Текст из файла (страница 37)
1!). !!(ы приведем другое доказательство, позволяющее оценить скорость сходимости. Если для любого й обозначить а!» — Х» — х» », то, как легко видеть, х»=х» + а! + + ... + »4» Следовательно, Х = 1!П! Х» Х»+ ~~' е!» » сю »=1 Пусть в ЕЯ'„выбрана некоторая норма, и матричная норма согласована с ней. Используя критерий Коши (см. Кудрявцев !!61, т. 1, й !8), нетрудно доказать, что для сходнмости ряда достаточно сходимости ряда из норм его членов. Для !»» имеем»1» = Р6» „откуда !~ »»»!!( !! Р ~! ° 1~ !»» ! !й и в случае 11 Р ~~ «1 для ряда из норм выполнен признак Даламбера. Итак, в атом случае последовательность х„сходится не медленнее, чем сумма геометрической прогрессии со знаменателем |~ Р 1~. Предложение доказано. Выше мы говорили о спектральном радиусе матрицы, как о чем!о точно определенном. В действительности, если арифметические операции производятся с округлением, спекгральный радиус, как и многие другие величины, не может быть точно указан.
В самом деле, пусть существует число !. такое, что матрица Р— '~.Е является почти вырожденной. Число к во всех вычислениях ведет себя так же, как характеристическое число. В частности, если Л ) 1, то метод простой итерации с матрицей Р ие сходится с должной точностью. В любом случае для ускорения сходимости процесс должен быть построен так, чтобы норма матрицы Р была возможно меньше. Если вернуться к формулам (3) и (4), то это означает, что нужно выбрать матрицу Н или соответственно параметр т и матрицу В так, чтобы !) Š— НА 1~ или !! Š— В 'ТА ~~ были возможно меньше. Если бы мы могли положить Н = А ', то процесс (при условии точного выполнения операций) сошелся бы за одну итерацию.
$ е итеРАциОнные методы Решения систем 165 В разных итерационных методах выбираются матрицы, как-либо приближающиеся к А ', причем используются свойства заданной матрицы А. Широко известный метод Якоби относится к системам, матрицы которых имеют доминирующую главную диагональ (см. 2 5 гл, П). Обозначим через 0 матрицу б(ая (ап, ..., а„„), т. е. диагональную матрицу, диагональные элементы которой равны соответствующим элементам матрицы А. Метод Якоби определяется формулой (3), в которой Н = 0 '.
Согласно предложению 1 построенная по этому методу последовательность сходится тогда и только тогда„ когда спектральный радиус матрицы Š— 0 'А меньше единицы. Покажем, что для сходимости метода Якоби достаточно, чтобы А имела доминирующую главную диагональ.
Для этого оценим с-норму матрицы Š— О "А. Эта матрица имеет на главной диагонали нули, а ее внедиагональные элементы равны я««= — — '«, Поэтому аа ' 1 Š— 0-«А ), = гпах ~ ! и;«! = шах У ~ — "' ~, Ам ~аа « «~с Если у А доминирующая главная диагональ, то каждая пз сумм меньше единицы, и ~~ Š— 0 'А !1, ( 1. Использование других норм даст другие достаточные условия. Ряд специализаций метода простой итерации связан с положительно определенными симметричными матрицами. Для любой такой матрицы А можно так подобрать матрицу Н, чтобы итерационный процесс (3) сходился. Действятельно, характеристические чи- 2 сла А заключены в некотором интервале (О, а). Положив Н = — Е, а 2 мы получаем матрицу Р =- Š— — „А, характеристические числа которой лежат в интервале ( — 1, 1).
Действительно, если А = =- 5 'А'3, где А' = б!ад (),„..., А„), то Р = Б 'Р'3, причем Р'— 2 диагональная матрица с элементами вида 1 — — Х, на главной диагонали. Мы не будем излагать более подробно применение метода простой итерации и общего неявного метода простой итерации к положительно определенным матрицам. Их изложение можно найти в книгах Д. К. Фаддеева и В. Н. Фаддеевой (35), Самарского 129!.
Отметим, что случай положительно определенной симметричной матрицы является достаточно общим, так как система Ах = д эквивалентна системе АРАХ= Агд с положительно определенной симметричной матрнцей. Однако, как мы видели на стр. 129, матрица А тА является, вообще говоря, значительно хуже обусловленной, чем матрица А. Поэтому практическое значение такого преобразования системы с целью применения итерационных методов невелико. Интерес, проявдыицй к пршкеценню итерационных ГЛ. П!. ВВЕДЕНИЕ В ЧИСЛЕННЫЕ МЕТОДЫ методов к системам с положительно определенными матрицами, связан с тем, что такие системы достаточно часто встречаются в приложения х.
й. Итерационное уточнение. Допустим, что, применяя метод Гаусса, мы получили /.(/-разложение матрицы А. Ошибки округления исказили результат, и потому Ь(/~ А для вычисленных матриц /. и (/. В общем неявном методе простой итерации мы можем положить В = /.(/ и т = 1. Формула (4) примет вид /.(/е(ы! = гы (6) где ге= Т! — Ах~ называется /г-й невязкой, а !1е„ = л„„ †,е„'— (/г + 1)-й поправкой. В качестве начального прнблпзкения берется решение системы / (/х, = д, затем вычисляется соответствующая невязка г,.
Она принимается за столбец свободных членов системы с той же матрицей 1. (/. решение этой системы — первая поправка д!. Следующее приближение х! получается как х„+ 4. Затем находщся невязка этого решения !, = Ь вЂ” Ах! и вторая поправка с/,— как решение системы 1.(/!1! = Ен Вторьв! приближением будет х! =- х! + сЦ и т. д. Если произведение /Л/ близко к А, то норма !! Š— (/.(/) 'А ~( мала, и процесс сходится очень быстро при условии, что вычисления проделываются точно.
Если они проделываютсп с той же точеостью, с какой было найдено /Л/-разложение, то пи к какому уточнешпо они ие приведут, так как в этом случае все приближения имеют ошибку такого же,!прядка, как и ошибка начального гриближеиия. Практически это означает, что при итерационном уточнении вычисления должны проделываться с удвоенной точностью, 1(ак гоказывает более детальный анализ (см. Форсайт и й(олер 1371), особенно важна точность при вычислении невязок и прибавлении гоправок. Если этп вычисления проделываются с точностью 2!/ разрядов (что может быть сделано с использованием режима накопления), а остальные вычисления производятся с д-разрядной точностью, то в результате итерационного уточнения может быть получено истинное решение, округленное до !/ разрядов.
Покажем, что сходимость итерационного уточнения зависит от обусловленности матрицы А и точности полученного разложения. Пусть произведение вычисленных матриц /. и (/ удовлетворяет равенству / (/ = А + 6, Тогда (Ш) 'А =(А+6)-'А =(Е+А-'6)-', Предполагая, что 1А ' 1~ ~! 6 ~) (1, мы можем представить эту матрицу в виде ряда Š— А-'6+ (А-'6)' —... Для матрицы Š— ((.(/) 'А, от которой зависит сходимость! мы получаем ряд А-'6 — (А-'6)'+., ° З 4. ИТЕРАЦИОННЫЕ МЕТОДЫ РЕШЕНИЯ СИСТЕМ 167 Каждая частичная сумма этого ряда по норме не превосходит соответствующей частичной суммы ряда нз норм, и мы получаем (~) — л-' а' Согласно формуле (15) 5 3!! 6 ~!е ~ 6 )! А бе, где 6 = и ри. Значит, для сходимости процесса итерационного уточнения достаточно, чтобы ее (А) 1 — сс (А) ( 1. Мы предположили уже, что (~ А '!~ ~~ 6)) ~ 1, т.
е. 6 се(А) (1. При этом предположении предыдущее условие означает, что 6се(А) ~ —. Итак, доказано 1 П р е д л о ж е и и е 3. Процесс итерационного уточнения сладится, если (при обозначенияк и. 9 6 3) 2присе (А) ( 1. Конечно, итерационное уточнение возможно и в том случае, когда известно не 7.У-разложение, а какое-либо другое разложе- ние, например ())т-разложение. 4. Метод Зейделя. В общем неявном методе простой итерации важно, чтобы матрица В была легко обратимой.
Выберем ее тре- угольной. Если диагональные элементы матрицы А отличны от нуля, то нижняя треугольная матрица ~~ам 0 ... 0 (ам а~а " алп ~ (получаемая из А заменой наддиагональных элементов на нули) будет невырожденной. Метод Зейделя, или глетод последоаательнык смещений, состоит в применении формулы (4) при т = 1 и В = Х, т, е. Е (хы т — х,) + А х, = д, Ех„,+Ух„=д, (7) где матрица У = А — Е отличается от А тем, что элементы на диагонали и ниже заменены на нули.
Формула (7) позволяет легко вычислить хя+т по хм Согласно предложению 1 метод Зейделя сходится тогда и только тогда, когда все характеристические числа матрицы Š— ~;~А = = —,(, "У по модулю меньше единицы. Легко проверить, что эти числа совпадают с корнями уравнения бе1 (У + ят'.) = О, (3) 168 ГП. Н!, ВВЕДЕНИЕ В ЧИСЛЕННЫЕ МЕТОДЫ П р е д л о ж е н и е 4. Для сходимости метода Зейделл до.таточно, чтобы матрица А была симметричной и положительно определенной. Зто предложение является частным случаем доказываемого ниже предложения 6.
Метод Зейделя сходится скорее, чем метод Якоби, и требует несколько меньшего объема памяти. Последнее обстоятельство связано с тем, что при использовании треугольных матриц, после того как вычислена 1-я коьшонента вектора х1, „соответствующая компонента вектора х„становится ненужной (см, формулу (?)). В следующем пункте мы рассмотрим прием ускорения сходимости метода Зейделя при помощи введения параметра. 5. Метод верхней релаксации. Разобьем матрицу А на три слагаемых А = Е + 0 + У.
Матрица 0, как и выше, есть б(аи (ан, ..., а„„), а Е и У получаются из А заменой на нули элементов ам прп 1 =» й и при 1 - й соответственно. Таким образом, матрица Е из предыдущего пункта равна Е + 0. Будем предполагать, что бе! 0 чь О. Метод верхней релаксации определяется формулой (4) при условии с = в и В = 0 + вЕ. Формула (4) принимает вид (О+ вЕ) (хы1 — хь) + в Ах„= вд, или (О+ вЕ) хы1 =1(1 — в) 0 — вУ) хе+ вд. (9) При в = 1 мы получаем отсюда формулу (7) — метод Зейделя. Применяя предложение 1, мы видим, что метод верхней релаксации сходится тогда и только тогда, когда спектральный радиус матрицы Р =Š— (0+вЕ)-' вА меньше единицы. Иначе матрицу Р можно представить в виде (0+вЕ) 1((1 — в) 0 — вУ1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
