Том 2 (1160084), страница 10
Текст из файла (страница 10)
Л Этот ряд будет называться сходящимся, если сходится последовательность его частичных сумм г' (А) =ив)+И,А+игА'+ ° ° ° ... +и А . Найдем условии сходимости такого ряда. Имеет место теорема: Для того чтобы степенной матричный ряд (60) сходился, необходимо и достаточно, чтобы все собственные значения Лг матрицы А лежали внутри круга сходимости степенного ряда (59). Д о к а з а т е л ь с т в о. Приведем матрицу А к нормальной форме Жордана при помощи некоторой неособенной матрицы Т: Т 'АТ=В. Тогда линвйныв опвгьтогы. ногмы опвватогов По индукции нетрудно доказать, что при т ) лп С'Л ' ...
С"г '),т "ч+' ть С' л~ е т ь О Лыь т-и ьв Сг л ь ы Ь ''',в (64) О О О ... Л"; Отсюда Ут(Вь) = (66) г (лд О О О Для того чтобы г (Вь) была сходяшейся последовательностью, необходимо и достаточно, чтобы у„,()ч), з' (Ль) ... гф-ц(Л;) были сходяшимися последовательностями. Последнее будет выполнено в том и только в том случае, если Л; лежат внутри круга сходи- мости ряда У(Л). Возьмем, в частности, ряд У(Л)=1+Л+Лв+ ... +Л" + (66) У(А) =(+А+ Аз+ ... +А + (67) необходимо и достаточно, чтобы собственные значения матрицы А были но модулю меньше единицы. Сделаем еше одно небольшое замечание.
Пусть Л вЂ” произвольное собственное значение матрицы А. Тогда имеется ненулевой вектор х такой, что Ах = Лх. (68) Следовательно, 11Ах11 =1Л111хл. (69) Но /!Ах!!(!/А~/~!х/~. Поэтому получаем !/А!!)~',Л), т. е, любая норма матрицы больше или равна модулю произвольного собственного значения матрицы, т. е. шах(Л;) (()Ал, Его радиус сходимости равен 1, и ряд расходится в каждой точке границы круга сходимости.
Следовательно, имеет место теорема, Для того чтобы сходился матричный ряд 54 гзшвнив систем линвйных ллгзггличвских твлвнзний (гл. 6 ф 8. Разновидности методов последовательных приближений В методах последовательных приближений решения системы Ах=Э исходят из произвольного начального вектора хз и получают векторы х,, х,...,. хк по рекуррентной формуле хк+,— — Ек(хе, х,, ..., хк), (1) хк, = Вкхк+ ск, (2) где Вк — квадратная матрица и ск — вектор. Естественно требовать от методов последовательных приближений, что при подстановке в правую часть (1) и (2) вместо хк точного решения системы А Ь мы слева снова получили А К В случае линейного метода первого — 1 порядка это приведет к равенству А-'К= ВкА-'К +;к (3) или ск —— (! — Вк) А ~Ь = Скд. (4) В этом случае мы можем переписать (2) в виде хк, = Вкхк+-СкК причем Вк и Ск — квадратные матрицы, не зависящие от К и что Вк+ СкА = !.
(6) такие, (6) Выражение (5) можно также записать в виде хк+1 = хк Ск (Ахк — К). (7) Наконец, если существует матрица Ск ', то выражение (б) записать в виде Е)кхкч.~+Екхк= д. можно (8) При этом должно быть )да+Ел — — А, (9) где Гк — некоторая функция, зависящая, вообще говоря, от матрицы системы А, правой части К номера приближения й и предыдущих гриближений хе, х,, ..., хк, Будем говорить, что метод имеет первый порядок, если Ек зависит только от хк и не зависит от х„, х,, ..., хк,. Будем нззывать метод стационарным, если Ек не зависит от й.
Простейшим случаем функций Гк будут линейные функции. Наиболее общий линейный метод последовательных приближений первого порядка должен иметь вил ~ 81 глзновидности катодов послздовлтзльных пгизлижзний 55 Один из способов такой минимизации там был рассмотрен. Этот способ можно обобщить. Выбираем какое-то направление, определяемое вектором с.
так же как и в э 5, найдем, что 7(х+ас) принимает наименьшее значение при а=а*, где (с, Ь вЂ” Ах) а'= (с, Ас) (12) Если возьмем вместо а* величину а=!)а*, то будем иметь: 7(х) — 7 (х+ас) =(2ж* — а) (с, Ас)=р(2 — р)а" (с, Ас). (13) Таким образом, если (с, Ь вЂ” Ах) + О, то 7(х) ) 7'(х+ас) при любом р (О ( р ( 2). Идея многих способов минимизации 7(х), а следовательно и решения системы Ах = Ь, заключается в следующем. Задаются начальным приближением хз. Определяют закон выбора векторов с„(они могут зависеть от хь). Определяют закон выбора коэффициентов рь (онн могут зависеть от хь).
На каждом шаге в качестве последующего вектора рассматривают хь „= ха+ раа'„-сь, (14) где а' было определено выше. Если А не является симметрической положительно определенной матрицей, то можно вместо системы Ах= д рассматривать систему А'7сАх = А')чЬ, где )с — симметрическая положительно определенная При пользовании формулой (8) мы получим х„+, в неявной форме, Поэтому желательно, чтобы матрицу О„было легко обратить. На практике обычно берут г)ь диагональной или треугольной.
В первом случае метод называют полношаговым, во втором — одношаговым. Разнообразные схемы, осуществляющие линейные методы последовательных приближений первого порядка. можно считать реализацией формул (5), (7) или (8). Много линейных и нелинейных методов последовательных приближений можно получить, используя способ наименьших нвад!таглов. При этом минимизируется функция 7'(х) = !(Ах — Ь!!г (! О) или же 7'(х), сложенная с некоторой постоянной. Разным способам минимизации и задания нормы будут соответствовать различные методы решения систем уравнений.
Как мы видели в Э 5, в случае симметрической положительно определенной матрицы А можно минимизировать функцию 7(х) =(х, Ах) — 2(Ь, х), (11) 56 гашение систем линейных ллгевглических гглвнений [гл. 6 матрица, Часто в качестве В берут единичную матрицу /. Это, конечно, не означает, что во всех случаях придется делать предварительное преобразование системы.
Бывает достаточно использовать преобразованную систему лишь для построения алгоритма. ф 9. Линейные полношаговые методы первого порядка !. Сходимость линейных полношаговых методов первого порядка. Простая итерация. Линейные полношаговые методы первого порядка определяются формулами (5) и (7) предыдущего параграфа.
Исследуем сначала сходимость этих методов. Из формулы (5) следует: х — А 'Ь=В х — А 'Ь. (1) вэг в( в ) Применяя формулу (1) при й=О, 1, ..., т, получим; 1 — 1 х,„„,— А Ь = В В,„,... В,Вв(хв — А Ь). Следовательно, (!х э,— А 'Ц<!1В !!!!В„,11 !1В,1!1!Во!!(!хо — А ~Ь!!. (2) 1!Вы!! 1!Вю ь1! . !1В,!1!1Вв1! стремится к нулю при т — +ос, то -1 !.х ь,— А Ь1! стремится к нулю при любом начальном векторе хв. Как мы видели в й 7, из этого будет следовать, что все компо— ! ненты х, будут стремиться к соответствующим компонентам А Ь, Для того чтобы произведение норм матриц, стоящее в правой части(3), стремилось к нулю, достаточно потребовать 11В 11 < 1< 1 (й= 6, 1, 2, ° ° ).
(4) В частности, если процесс стационарен, т. е. В„не зависят от й, В„=В; последнее условие означает, что какая-то из норм В меньше елиницы. Ойнако для стационарного случая можно дать более точные условия, а именно докажем теорему: Стационарный линейный процесс х„„, = Вхв+СЬ (5) сходится при любом начальном векторе и любой правой части тогда й только тогда, когда все собственные значения матрицы В по модулю меныие единицы. Действительно, легко проверить по индукции, что хь,, — — В"+'х, + (В" + В" '+ ... + В+/) СЬ. (6) Очевидно, последовательность (В" +В" '+ ... + В+/)СЬ (й=0, 1, 2...) (7) будет сходящейся для произвольного вектора Ь в том и только в чам случае, если сходится матричный ряд /+В-+Вг+ ...
+В" +... (6) 91 линейные полношАГОВые методы пеРВОГО пОРЯдкА 57 Но при этом В -+ О, Следовательно, хлэ, образуют сходящуюся последовательность при произвольных векторах хз и д в том и только в том случае, когда сходится ряд (8). Как мы видели, ряд (8) сходится в том и только в том случае, если все собственные значения матрицы В по модулю меньше единицы. Утверждение доказано. Полученное нами условие хорошо при теоретических рассуждениях, так как точно отражает положение вещей, Однако оно неудобно для практических применений, ибо в большинстве случаев собственные значения нам неизвестны, а отыскание их представляет задачу более сложную, чем решение системы линейных алгебраических уравнений. В главе 8 мы дадим ряд способов оценки максимального по модулю собственного значения, Пока же будем использовать нормы матриц, данные в 9 7, и неравенство шах(Л! ( (!(В!(.
Прн этом получим следующие три достаточных условия: .~, (дсЕ( <р. 1 (1=1, 2, ..., и), (9) 1 1 ~ ~(81~! (р<! (7=1, 2, ..., П), 1 1 Х дц <р< 1. (1 1) ! У 1 (10) делим на ап и переносим члены с х,, х,, ..., х! О хе+и ..., х„ в правую часть равенства. При этом 1-е уравнение примет вид ит ис х,=- — — — х — =х —... 1 2 и!с им ин а!, 1-1 и1, 1+1 исч — — х — — 'х — .. — — х. (И) асс ' 1 иа ~1 '' и11 Для того чтобы этот прием был осуществим, коэффициенты ас; должны быть отличны от нуля.
Кроме того, для обеспечения Пояснений требует только последнее условие. Оно обеспечивает, что норма КВаз, равная наибольшему собственному значению ),„ матрицы В'В, не превышает единицы. Действительно, все собственные значения матрицы В'В неотрицательны. Поэтому Л, ( Л, -+ Л, +... ... +Л„. Но последняя сумма равна следу матрицы, который и равен д,ы. !81 1 Изложенный метод часто называют простой итерацией. Для применения простой итерации необходимо предварительное преобразование системы, заданной в виде Ах=В, к виду (5). Это можно сделать, например, так. Каждое из уравнений системы апх,+аихз-+ ...
+а;„х„=де (1=1, 2, ..., П) (12) 58 Решение систем линейных АлгеБРАическнх УРАВненнй (гл. 6 сходимости требуется значительное преобладание диагональных элементов над остальными коэффициентами. Так, неравенства (9) — (11) будут выполнены. если для коэффициентов будут выполнены слелуюшие неравенства: ~а((! < ~а((~ ((= 1, 2, ..., и), у ! ОФ1) (! 4) (15) (7'=1, 2,..., и), ~~у )' (а( ~Я( 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
