В.А. Ильин, Э.Г. Позняк - Линейная алгебра (1152751), страница 35
Текст из файла (страница 35)
Так как матрица ВПа является положительно определенной и симметричной, то для нее существует ограниченная и симметричная обратная матрица, которую мы обозначим через В Пз. Заметим далее, что с помощью замены Х = В ПаУ и умножения слева на матрицу В Па задача на собственные значения СХ = =- ЛВХ переходит в эквивалентную задачу на собственные значения В ПзСВ ПаУ, так что для доказательства леммы остается убедиться в том, что заведомо симметричная матрица В ПаСВ Оа является положительно определенной тогда и только тогда, когда является положительно определенной матрица С.
Это последнее сразу вытекает из того, что для любых ненулевых векторов Х и У, связанных соотношением У = В ПаХ, справедливо равенство (В-П'СВ-П'Х, Х) = (СВ-П'Х, В-П'Х) = (СУ, 1). Лемма доказана. Теперь мы можем перейти к доказательству необходимости условий (6.14) теоремы 6.2 при дополнительном предположении о том, что матрица В является симметричной. 2) Необходимость. Будем опираться на следующее утверждение из доказанной выше леммы: если матрица В является симметричной и положительно определенной, а матрица С является симметричной и не является положительно определенной, то за- !6! МЕТОДЫ РЕШЕНИЯ ЛИНЕИНЫХ СИСТЕМ дача на собственные значения СХ = ЛВХ имеет хотя бы одно неположительное собственное значение Л,.
Предположим, что не выполнено первое из условий (6.14), т.е. не выполнено требование 2 — тА ) О. Полагая в проведенных выше рассуждениях С = 2 — ТА, мы получим, что задача на собственные значения (2 — ТА)Х = ЛВХ имеет хотя бы одно неположительное собственное значение Л,. Обозначим через Х!"! отвечающий Л, собственный вектор и выберем нулевое приближение Хб так, чтобы было выполнено условие Хб = Х!'1. Тогда, переписав уравнение для погрешности (6.15) в виде ВУьч! = = — ВХь + (2 — тА)7ь мы получим, последовательно полагая !г равным О, 1,..., я! = ( — 1+ Л,)Х!'1, Уз = ( — 1+ Л,)аХ!'1, 2, = (-1+ л,)'х», Поскольку — 1+ Л, < — 1, то очевидно, что !!ль!! не стремится к нулю при й — е оо.
Аналогично рассматривается случай невыполнения второго условия (6.14), т.е. условия тА > О. В этом случае в проведенных выше рассуждениях следует положить С = тА. Мы получим при этом, что задача ТАХ = ЛВХ имеет хотя бы одно неположительное собственное значение Л, с собственным вектором Х!'1. Выбирая нулевое приближение Хг! так, чтобы было справедливо равенство 2о = Х!'! и переписывая (6.15) в эквивалентном виде ВЯьч! = ВЯь — тАХь мы получим, что у! = (! — Л.) Х!'1, 7, = (! — Л.)аХ!'1, ..., 2ь = (! — Л,)" Х!'1, Так как Л < О, то очевидно, что !1г5ь)! не стремится к нулю при й -е оо. Теорема 6.2 полностью доказана.
Перейдем теперь к оценке скорости сходимости общего неявного метода простой итерации. Следуя А.А. Самарскому '), выясним вопрос о выборе такого значения параметра т, которое обеспечивает наиболее быструю сходимость. Предположим, что матрица В является симметричной и положительно определенной. С помощью такой матрицы естественно ввести так называемое энергетическое скалярное произведение двух произвольных векторов Х и У, положив его равным (ВХ, У) = (Х, ВУ). Такое скалярное произведение будем обозначать символом (Х, У)в. С помощью матрицы Вг7а это скалярное произведение можно записать в виде (Х, У)в = (В!7аВг7ах, У) = (Вг7ах, В!7аУ).
С помощью последнего равенства легко проверяется справедливость для ') Самарский А.А. Введение в теорию разностных схем. — Мл Наука, 1971. Самарский А.А., Гулин А. В. Устойчивость разностных схем. — М.. Наука, 1973. б Лннейнан алгебра 162 ИТЕРАЦИОННЫЕ МЕТОДЫ РЕШЕНИЯ ЛИНЕИНЫХ СИСТЕМ (гл. 6 введенного нами скалярного произведения четырех аксиом скалярного произведения (см. и. 1 В 1 гл.4). Далее естественно ввести энергетическую норму вектора Х, поло° - р-. р,тх, хр, =,ртвх, хр. в*р -ьр.*. - р .р р мы обозначим символом йХйв. Две различные нормы одной и той же совокупности векторов ()Х()! и ()Х!)п называют эквивалентными, если сугцествуют такие положительные постоянные ур и Та, что справедливы неравенства у,~~Х~~, < ~~Х~~И < Т,~~Х~~И Заметим, что энергетическая норма вектора Х и обьтная его норма являются эквивалентными. В самом деле, справедливость неравенства ур~~Х~~ < ~~Х~~в, т.е.
неравенства у~(Х, Х) < (ВХ, Х) вытекает нз положительной определенности матрицы В, а справедливость неравенства ~~Х~~н < ТЕ~~Х~~, т.е. неравенства (ВХ, Х) < < Тз))Х()~ вытекает из неравенства Коши — Буняковского и оценки (6.7) (достаточно положить !г~ = ~еВй).
Установленная эквивалентность обычной и энергетической норм позволяет утверждать, что последовательность ~~Хь~~ сходится к нулю тогда и только тогда, когда сходится к нулю последовательность ))Хь()в. Для дальнейших рассуждений энергетическая норма является более удобной, чем обычная норма. Докажем следующую фундаментальную теорему. Теорема 6.3 (теорема Л.А. Самарского). Пусть матрицы А и В симметричны и положительно определены, Хь обозначает погрешность общего неявного метода простой итерации. Тогда для того чтобы при р < 1 было справедливо неравенство ((Хь))в < р")(Хь!)в, достаточно, чтобы было выполнено условие В<А< В.
(6.21) т т Замечание. А.А. Самарским доказано, что условие (6.21) не только достаточно, но и необходимо для справедливости неравенства ~~Хь~~в < Рь~~Хо~~н, но мы на этом останавливатьсЯ не бУдем. Доказательство теоремы 63. Для удобства разобьем доказательство на два шага. !'. Сначала докажем, что если симметричные и положительно определенные матрицы А и В удовлетворяют условиям Самарского (6.14), то (ВХьхн Хячз) < (ВХЫ Хь).
Умножая равенство (6.!5) скалярно на 2ТХьч.1 = т(Хь„,| + Хь) + т(ХЕР1 — Хь), получим (В(Хне — 7ь), Хь~|+ Х~) + (В(Хьт — Х~), Хьтр — 7 ) + + т(АХвьь 7~т~ + Хь) + т(АХЫ Х~~ — Хь) = О. !63 МЕТОДЫ РЕШЕНИЯ ЛИНЕИНЫХ СИСТЕМ В последнем равенстве заменим А7ь на разность ! 1 — А(г +Я ) — — А(Я . — К ). 2 2 Тогда, учитывая вытекающее из симметрии матрицы А равенство (А(7ьэ ! — 7ь), кь.г! + Яь) = (ль.ь! — 7ь, А(ль ь! + .Оь)), мы получим тождество (В(7ь Р! — 7ь), 7ь Р! + 7ь) + + (( — — А) (Л~+ ! — Хь), Яь~ + 7~) + ! + — (ТА(Хь.ь! + 7ь), 7ь.ь! + 7ь) = О.
2 Учитывая, что (в силу условий Самарского (6.14)) операторы ТА и В— — (т/2)А являются положительно определенными, мы получим из последнего тождества следующее неравенство; (В(кь., — 7),2ь., +К)<О. Это неравенство эквивалентно доказываемому неравенству (Вя„н К„,) < (Вг,, Я,) (в силу вытекающего из симметрии оператора В тождества (Вгь„, г,) = (г„н Веь)). 2'. Пусть теперь при р < 1 выполнены условия Самарского (6.21). докажем справедливость неравенства ()уь)(н < рь!)Ло()в. Положим Ль = р" $'ь. То~да, очевидно, Х„., — Кь = р""1гь„— р"~„= р""(1„! — 1„) — (! — р)р"1ь.
Подставляя эти значения 7ь и 7ьт! — 7ь в равенство (6.15) и производя сокращение на р", получим для величин 1гь следующее соотношение: (6.22) т в котором В = рВ, А = А — — — В. ! — р т В силу условий (6.21) операторы В и А удовлетворяют условиям тА ) О, 2В > ТА. Из этих условий и из того, что уравнение (6.22) для 1Хь совершенно идентично уравнению (6.15) для Яь, в силу первого шага длЯ аз вытекает следУющаЯ оценка: (В\газ.!, 'Рь.ь!) < (В1ь, 1гь). Из этой оценки в свою очередь, учитывая, что В = рВ, получим неравенство (В1гь,!, 1Гьь!) < ( В1гь, 1гь). Последовательное применение указанного неравенства для номеров к = О, 1, ... приводит нас к соотношению (В1Хь, 1гь) < (Вгш Цо), 164 ИТЕРАЦИОННЫЕ МЕТОДЫ РЕШЕНИЯ ЛИНЕИНЫХ СИСТЕМ ) гл. 6 а умножение последнего соотношения на ра" приводит к окончательной оценке ') (Вюю Яь) < йдь(ВХо, юо).
Тем самым неравенство ~~Яь~~и < < р" ~~Яо~~в доказано. Доказательство теоремы 6.3 завершено. В заключение применим теорему Самарского 6.3 для выяснения вопроса о выборе такого значения параметра т, при котором скорость сходимости является максимальной. Из доказанной в теореме 6.3 оценки ЕЯьян < р ~~2ояв вытекает, что эта задача сводится к нахождению такого значения т, при котором достигается минимальное значение функции р = р(т). Так как обе матрипы А и В симметричны и положительно определены, то существуют положительные постоянные Т1 и Тя такие, что справедливы неравенства у~В < А < .ТаВ. Будем считать, что постоянные т1 и тз в этих неравенствах нам заданы ). Сопоставляя только что написанные неравенства с условиями (6.21), мы получим, что минимальное значение р достигается при условии (! — р)!т = Ти (1+ р) (т = Тю откуда получаем оптимальное значение т = 2Ччч + Тз) и минимальное значение р, равное (Тя — Т1)г(Тя+Т1).
Частным случаем проведенного нами рассмотрения является явный метод простой итерации, изученный в п. 1. Для этого метода справедливы все полученные нами результаты. В следующих трех пунктах с помощью общего неявного метода простой итерации и теоремы Самарского 6.2 мы рассмотрим несколько наиболее употребительных итерационных методов и установим условия их сходимости. 3. Модифицированный метод простой итерации.
Этот метод получается из общего неявного метода простой итерации в том случае, когда стационарный параметр т равен единице, а матрица В представляет собой диагональную матрицу Р, состоящую из элементов матрицы А, лежащих на главной диагонали, т.е. В = Р, где аи О ... О О азз ... О (6.23) О О ... а„„ При этом, конечно, предполагается, что матрица А является симметричной и что все ее диагональные элементы аи, азю ...,а„„ являются положительными (последнее требование необходимо и достаточно для положительной определенности диагональной матрицы В = Р). Из теоремы 6.2 сразу же вытекает, что для сходимости модифицированного метода простой итерации при любом выборе нуле- ') Мы учитываем, что Яь =' рьИИ Уэ =- Ъщ ) Постоянные Т~ и Т естественно назвать константами экзиеалеиглности матриц А и В.
Для коммутирующих матриц А и В постоянные гп и Тз соответственно равны наименьшему и наибольшему собственным значениям задачи АХ = ЛВХ. !65 МЕТОДЫ РЕШЕНИЯ ЛИНЕИНЫХ СИСТЕМ ного приближения достаточно, чтобы были выполнены два условия: 2Р>А,А>0. Теорема 6.1 позволяет выразить достаточное условие сходимости модифицированного метода простой итерации и в другой форме '): )(Š— Р 'Ай < 1 (6.24) (под нормой матрицы, как и выше, понимается операторная норма). Так как йŠ— Р !А)! = ))Р"!(Р— А))! = 'йР '(А — Р)й, то достаточное условие сходимости (6.24) можно переписать в эквивалентном виде 'йР !(А — Р)й < 1.
(6.25) Неравенство (6.25) позволяет получить различные достаточные условия сходимости модифицированного метода простой итерации. Прежде всего заметим, что если наряду с операторной нормой матрицы (6.2), которую мы, как н выше, будем обозначать символом ~~Ай, ввести так называемую сферическую норму этой матрицы, обозначаемую символом йАй,ф и определяемую равенством йАй,ф = и и 1!Л = [ 2 2' пз.~, то, как доказано в а4 гл.4 (см. формулу (4.28)), для з=!з=! любого вектора Х пространства Е" будет справедливо неравенство а) 'йАХ(! < йА)(,фйХ(!. (6.26) Из (6.26) и (6.5) сразу же вытекает, что операторная и сферическая нормы матрицы связаны соотношением !!А~~ < ~(А~( ф. Таким образом, в силу (6.25) достаточное условие сходимости модифицированного метода простой итерации выражается неравенством ~~Р '(А — Рн,ф < 1, которое в развернутой записи имеет вид и, !!а! < 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
