Самарский А.А. Гулин А.В. - Численные методы (1078412), страница 18
Текст из файла (страница 18)
Пусть А — симметричная пологсителвно определенная матрица, т)0 и пусть вьтолнено неравенство  — 0,5тА ) О. (4) Тогда итерационный метод (2) сходится. Доказательство. Достаточно показать, что среднеквадратичная норма решения г„уравнения (3) стремится к нулю при и- ао и при любой начальной погрешности г,. Покажем сначала, что при условии (4) числовая последовательность У„= (Аг„, г„) является невозрастающей. Из уравнения (3) найдем г,~,=(Š— тВ 'А)г„, Аг„,=(А — тЛВ 'А)г„, откуда получим (Аг„„, г„„) = (Аг„, г„) — т(АВ-'Аг„, г„)— — т(Аг„, В 'Аг„) +т'(АВ-'Аг„, АВ-'Аг„), Вследствие симметричности матрицы А имеем (ЛВ-'Аг„, г„) = (Аг„, В-'Аг„), поэтому (Лг.+о г„~,) = (Аг„, г„) — 2т(( — О,бтА) В-'Аг„, В-'Аг„).
(5) Отсюда, учитывая условие (4), получаем неравенство (Лг„.„, г„„) ( (Аг„, г„). Таким образом, числовая последовательность У„= (Аг„, г„) монотонна и ограничена снизу нулем. Следовательно, существует Вш У, =У. (6) Далее, из положительной определенности матрицы  — 0,5тА следует существование константы 5)0 такой, что (( — 0,5тА)В 'Аг„, В 'Аг„) )Ь!~В-'Аг„'з'. Отсюда и из (5) получаем неравенство У„е,— У„+25тзВ 'Аг„!~'(О. Переходя в этом неравенстве к пределу при п- со и учитывая (6), убеждаемся в том, что существует !пп 1гв„1=0, где гв.=В-'Аг„. Наконец, замечая, что А — положительно опреде 87 ленная и, следовательно, обратимая матрица, получим г„=А 'Вгп„, ][г„[]([[А 'В[]][ге„[! и тем самым !!щ [[ел[! = О.
где ()=д!ад [аго асн ..., а ]. Таким образом, в данном случае В=В, т=1. Следствие 1. Пусть А — симметричная положительна определенная матрица с диагональным преобладанием, т. е. аи),Я, ] ау ], ! = 1, 2,, гп. (8) ] за а Тогда метод Якоби сходится, Д о к а з а т е л ь с т в о.
Условие сходимости (4) в данном случае имеет вид А(2й. Покажем, что это матричное неравенство следует из неравенств (8). Рассмотрим положительно определенную квадратичную форму (Ах, х) = ',"~~ абаях;х! С!=1 и воспользуемся оценками ы ал (Ах, х) = — ~ ] аи [ х', + Х [ау ] х1 а— 11=а С1=а = — 'Я [ ау ] х,'.
+ — ~~~~ ] ар ] х,'. 1 1 С!=а 2 Из условий симметричности и положительной определенности мат- РиЦы А имеем ан=ао, аь)0, 1, /=1, 2„..., пг, и поэтомУ пРеДыДУ- щая оценка приводит к неравенству (Ах, х)( 'Я ]ау [х,'. =',а х,'.~'Я ]аа [+ аи) . С1=-1 а.=1 /ааз 88 Теорема 1 доказана. Замечание. Как показано в [32, с. 827], нря условяях теоремы 1 пля погрешностя г„ х — х ятерацяонпого метода (2) справедлива оценка !]г !!ла ра!!га]]л, гле ры(0, 1), [!г !!л=(Аг, г )'". Эта оценка означает, что метод сходится со скоростью гсометрячсскоя прогрессян со зпанепаяелеи р.
Константа р (1 — 2тб*б/!!В]!а)ь, гпе б — минимальное собственное зпачепяа матрацы А в б, — ыянныааьпое собстаепяое значение матрацы 0,5 (В'+ — тА). Применим теорему 1 к конкретным итерационным методам, рассмотренным в предыдущем параграфе. Метод Якоби имеет следующий канонический вид: О(х.„— х )+Ах =1, (7) Перепишем условие (8) н виде аи + ~~", ) ап ) ( 2аи, 1= 1, 2, ..., гп. гм Тогда из неравенства (9) получим (Ах, х) ( 2 ~ аих,'. = 2 (0х, х), что и требовалось.
Следствие 2. Пусть А — симметричная положительно определенная матрица. Тогда метод верхней релаксации (Р + мАт) "+' " + Ах„= )~ сходатся при условии 0(ы<.2, В частности, метод Зейделя (в= 1) сходится. До к аз а тельство. Метод верхней релаксации приводится к каноническому виду (2) с В=Р+ььАь т=ы, Напомним, что исходная матрица А представляется в виде суммы А=О+А,+А„где А,— нижняя треугольная, А,— верхняя треугольная н 0 — диагональная матрицы (см. (Т) из 9 1).
Для симметричной матрицы А матрица А, является транспонированной н А„ поэтому (Ах, х) = (Рх, х)+ (А х, х)+ (А х, х) = (Рх, х)+2(А х, х). Условие сходимости (4) принимает вид (Вх, х) — О,бв(Ах, х) = =((О+соА,)х, х) — Оба((Рх, х)+2(А,х, х)) =(1 — О 5ы) (Рх, х) >О и выполняется прн 0(а(2. Рассмотрим еше вопрос о сходимости метода простой итерации " + Ах„=( (10) с симметричной положительно определенной матрицей А. Согласно (4) метод сходится при условии Š— 0,5тА ) О. (11) Какие ограничения на параметр т накладывает условие (1!)? Пусть ?.э 1=1, 2, ..., т,— собственные значения матрицы А, расположенные в порядке возрастания. Условие (111 эквивалентно тому, что все собственные значения матрицы Š— 0,5тА положительны.
Достаточно потребовать положительности минимального собственного числа этой матрицы, равного 1 — 0,5т? . Таким образом, итерационный метод (10) сходится, если т<2/?. „, (12) где ? „— максимальное собственное число матрицы А. Условие (12) и необходимо для сходимости метода (10), т. е.
если (12) нарушено, то найдется начальное приближение х„при котором 11х„— х11тьО при а-лоо. Докажем последнее утверждение. Возьмем в качестве начального приближения вектор х,=х+р, где х — точное решение задачи (1), а р — собственный вектор матрицы А, отвечающий собственному числу Х„„,=л„„т. е.
Ар=1.„р,. При таком выборе начального приближения имеем г,=х,— х=р. Из уравнения (3) при В=Е получим г„= (Š— тА) "г„= (Š— гА) "р и, следовательно, х„= (1 — й ) "р, !1з„!1 = (1 — Ю~1 "11лл11. Если т = 2Х ', то 11х„11= 11лл1! т' 0 при и — ео. Если же т) 2) ', то 11 — тХ.,1)! и 11г„11 — ~оо при и- ео. Таким образом, условие (12) необходимо и достаточно для сходимостн метода простой итерации (10).
В заключение параграфа отметим, что теория итерационных методов не заканчивается исследованием сходимости. При наличии хотя бы двух итерационных методов возникает вопрос о том, какой из этих методов сходится быстрее, т, е. для какого метода погрешность 11х„— х11 станет меньше заданного числа е при меньшем числе итераций и.
Сюда же примыкает вопрос о нахождении итерационных параметров, минимизирующих число итераций, необходимых для получения заданной точности. Этот круг вопросов будет подробно рассмотрен в следующих параграфах. б 3. Необходимое и достаточное условие сходимостн стационарных итерационных методов (2) 1. Введение. Некоторые итерационные методы решения систем линейных алгебраических уравнений уже рассматривались в 5 1, 2. Напомним необходимые для дальнейшего сведения. Пусть дана система уравнений Ах=1, (1) где А = (аь), 1, ! = 1, 2, ..., ил, — вещественная квадратная матрица, имеющая обратную, и х= (х„х„..., х )', 1= (1„!н..., 1 )'. Кано- нической формой одношагового итерационного метода называется его запись в виде В„«и« " +Ах,— 1, а=О, 1, ..., та« где и — номер итерации, х, — заданное начальное приближение, х„= (х,", х,", ..., х")т.
МатРицы В„„и числа т.ч,)0 задают тот или иной конкретный итерационный метод. В настоящем параграфе подробно рассматриваются стационар- ные итерационные методы (3) в которых матрица В и числовой параметр т не зависят от номера итерации п. Погрешность итерационного метода (3) о„=х„ — х, где х — точное решение системы (1), удовлетворяет уравнению В "" "+ Аое=О, и=О, 1, ..., оа — — хе — х, (4) которое отличается от уравнения (3) лишь тем, что является однородным. Сходимость итерационного метода (3) означает, что о„- О в некоторой норме при п — ео.
Переписывая уравнение (4) в разрешенной относительно о„„форме о. 1=50., (б) где 5= — тВ-'А, (6) видим, что свойство сходимости итерационного метода целиком определяется матрицей 5. Необходимые и достаточные условия сходимости в терминах матрицы 5 приведены ниже в п. 3, Матрица 5 называется матрицей перехода от п-й итерации к (и+1)-й. 2. Норма матрицы. При исследовании сходимости будем рассматривать векторы х„и х как элементы т-мерного линейного пространства Н, в котором введена норма 11х1) вектора х.
Нормой матрицы А, подчиненной данной норме вектора, называется число '1 А 1 = зцр 11 — "11 хФе !1 х1 Норму вектора в пространстве Н можно ввести различным образом. Нам прежде всего потребуется норма 11х)~= шах )х;). тм/»!!! Подчиненная ей норма матрицы А выражается через элементы матрицы А следующим образом: ю 1!А11с= /пах 'Я 1а//). /=! Докажем вто утверждение. Дла любого вектора х справедливо неравенство 11 Ах)„.= гвах ~~~~ а/;х» н/ах 1х/1 гпах ~1а//1= 1ж!тс и 1 тм/»ш гмщ!! ~);,) 11х)1с. 1 т~(<п! .
/=1 в. е. 1)Ах))с» хнах х' )аи) 1)х)„-. ! !ф'<!а . / =! 91 Чтобы ззвершить доказательство, достаточно построить = (хо, хо„ ..., «о ) , для которого выполняется равенство вектор х,= 1Ахо(с — гпзх Я 1а, 1 )хо11с. ! гж!<о! . /=! (8) Пусть фуикцнв и <р! = Ч!ч 1ап 1, / = 1, 2, ..., !и, г=-! достигает максимума при ! й, т.
е. гази Д'„ 1 а!/ 1 = ~~~ 1 аь/ (. о<гжюь /=1 /=1 Рассмотрим вектор хо, имеющий координаты 1, если аз )О, х; = о — !, если а (О. о/ Очевндно, что 11хо11с=!. Оценим сннзу выражение для 11Ахо1(с. Имеем ) Ахо11с = тзх ~~ а хо ) '~~~ а„хо !к!же ~ 1/= !=-1 Далее, исходя из определения (10) вектора хо, получим ! и о! !ь 'Я а „о ~~,"~ а хо ~~~~ ~~ а /=! /=! /=! (9) (10) в, следовательно, 11 Ахо 1с ~ Я 1а/н1 = шзх ,'~~ 1 а!/ 1, ож!идж . ! — 1 !'=-1 Последнее равенство справедливо в силу (9).
Тем самым нашли вектор хо, для которого о! )Ахо11) шах '~~' 1а; 1(хо1~. !жь<л !'=! Поскольку для каждого вектора х справедлива противоположное неравенство (7), заключаем, что для х, справедливо равенство (8). 3. Теорема о сходимости итерационного метода. Справедлива Теорема !. Итерационный метод (3) сходится при любом начальном приближении тогда и только тогда, когда все собствгнныг значения матрицы Б=Š— тВ-'А по модулю меньше единицы. Доказательство.
Представим уравнение (4) для погрешности о„=х„— х в виде (5) — (6). Докажем сначала необходимость условий теоремы 1. Предположим, что матрица 5 имеет собственное число з, для которого 1з()1, и покажем, что в этом случае можно так подобрать начальное приближение х„, чтобы погрешность о.=х„— х неограниченно возрастала при и-о-оо. Пусть /ь— собственный вектор матрицы 5, отвечающий собственному числу 92 з, 1з~)1. Возьмем в качестве начального приближения вектор х,=х+р, так что начальная погрешность о,=р. Тогда нз уравнения (б) получим и =5"п~=з"о~=а"н и 1!о 11'=-1з1 "111х!~- оь при и — с .
если ~з! =1, то ~~ОД=!~н~!-~ 0 прн Л-ьсю. Доказательство достаточности условий теоремы 1 проведем сначала в предположении, что матрица 5 имеет т линейно независимых собственных векторов. Пусть з„, й=1, 2,, т,— собственные числа матрицы 5 и и„, й=1, 2, ..., т,— отвечающие им линейно независимые собственные векторы. Разложим начальную погрешность о,=х, — х по векторам р„: ь оь=Х СФРЮ Тогда получим т е, = 5 оо = Я сьз"„рм ь — ~ В любой норме справедлива оценка п~ 10„1) ( р'ч~ 1с, И1 рь) ь=1 (11) где р = гпах ~зь~ — спектральный радиус матрицы 5. Из оценки ~мА<а (11) в силу предположения теоремы ! о том, что О~1, и следует сходимость метода.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
