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