Главная > Математика > Линейная алгебра
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

2. Общий неявный метод простой итерации.

Снова обратимся к решению линейной системы (6.1), но на этот раз заменим итерационную последовательность (6.3) более общей итерационной последовательностью, определяемой соотношением

в котором В представляет собой некоторую «легко обратимую» квадратную матрицу порядка, — стационарный параметр. Такой метод составления итерационной последовательности и называется неявным методом простой итерации. Рассмотренный в предыдущем пункте явный метод простой итерации получается из неявного метода в частном случае где Е — единичная матрица порядка

Для того чтобы сформулировать в удобной для приложений форме условие сходимости общего неявного метода простой итерации, напомним некоторые понятия, введенные в предыдущей главе.

Напомним, что матрица А называется поло жительно определенной, если для любого ненулевого вектора X. В главе 5 было доказано, что необходимым и достаточным условием положительной определенности симметричной матрицы А (или, что то же самое, самосопряженного линейного оператора А) является положительность всех собственных значений этой матрицы (этого оператора).

Если матрица А является положительно определенной, то мы договоримся писать неравенство Далее договоримся писать неравенство (или ) в случае, если (т. е. если матрица является положительно определенной).

Докажем следующую замечательную теорему.

Теорема 6.2 (теорема А. А. Самарского). Пусть матрица А является симметричной и выполнены условия (симметричность матрицы В, вообиуе говоря, не предполагается)

Тогда для того чтобы итерационная последовательность, определяемая соотношением

при любом выборе нулевого приближения сходилась к точному решению X системы достаточно, чтобы были выполнены условия

При дополнительном предположении о том, что матрица В является симметричной, условия (6.14) не только достаточны, но и необходимы для сходимости указанной итерационной последовательности при любом выборе нулевого приближения

Доказательство. 1) Достаточность. Прежде всего оценим погрешность . Так как X удовлетворяет уравнению соотношению (6.13), то для получим соотношение

Установим для погрешности так называемое основное энергетическое соотношение.

Умножая (6.15) скалярно на вектор

получим равенство

Если воспользоваться обозначением и соотношением

то равенство (6.16) можно переписать в виде

Далее заметим, что в силу симметрии матрицы А второе слагаемое в (6.17) равно Это приводит нас к основному энергетическому соотношению:

Для доказательства достаточности условий (6.14) остается с помощью основного энергетического соотношения доказать сходимость к нулю последовательности

Из основного энергетического соотношения и из положительной определенности матрицы вытекает, что вытекает невозрастание последовательности Из условия вытекает, кроме того, что эта последовательность ограничена снизу нулем, а поэтому сходится.

Но тогда из основного энергетического соотношения следует, что

Напомним, что для положительно определенной матрицы С всегда найдется такое, что для любого вектора X или, что то же самое, с .

Последнее неравенство позволяет заключить, что из равенства нулю указанного выше предела (6.19) следует, что

Для завершения доказательства достаточности следует воспользоваться соотношением

из которого в силу существования для положительно определенной матрицы А ограниченной обратной матрицы вытекает, что

Последнее равенство и соотношение (6.20) дают право заключить, что Достаточность доказана.

Для доказательства необходимости условий (6.14) при дополнительном предположении о том, что матрица В симметрична, привлечем следующую лемму.

Лемма. Пусть С — некоторая симметричная матрица, а В — симметричная положительно определенная матрица. Тогда матрица С является положительно определенной в том и только в том случае, когда являются положительными все собственные значения задачи

Для доказательства леммы заметим, что так как матрица В является симметричной и положительно определенной, то (в силу теоремы 5.24 из п. 6 § 5 гл. 5) существует самосопряженный положительно определенный оператор такой, что для соответствующей ему матрицы справедливо равенство как матрица является положительно определенной и симметричной, то для нее существует ограниченная и симметричная обратная матрица, которую мы обозначим через

Заметим далее, что с помощью замены и умножения слева на матрицу задача на собственные значения переходит в эквивалентную задачу на собственные значения так что для доказательства леммы остается убедиться в том, что заведомо симметричная матрица является положительно определенной тогда и только тогда, когда является положительно определенной матрица С. Это последнее сразу вытекает из того, что для любых двух ненулевых векторов X и связанных соотношением справедливо равенство

Лемма доказана.

Теперь мы можем перейти к доказательству необходимости условий (6.14) теоремы 6.2 при дополнительном предположении о том, что матрица В является симметричной.

2) Необходимость. Будем опираться на следующее утверждение из доказанной выше леммы: если матрица В является

симметричной и положительно определенной, а матрица С является симметричной и не является положительно определенной, то задача на осбственные значения имеет хотя бы одно неположительное собственное значение

Предположим, что не выполнено первое из условий (6.14), т. е. не выполнено требование

Полагая в проведенных выше рассуждениях , мы получим, что задача на собственные значения имеет хотя бы одно неположительное собственное значение Я. Обозначим через отвечающий собственный вектор и выберем нулевое приближение так, чтобы было выполнено условие

Тогда, переписав уравнение для погрешности (6.15) в виде мы получим, последовательно полагая равным

Поскольку то очевидно, что не стремится к нулю при

Аналогично рассматривается случай невыполнения второго условия (6.14), т. е. условия . В этом случае в проведенных выше рассуждениях следует положить Мы получим при этом, что задача имеет хотя бы одно неположительное собственное значение с собственным вектором . Выбирая нулевое приближение так, чтобы было справедливо равенство и переписывая (6.15) в эквивалентном виде мы получим, что

Так как , то очевидно, что на стремится к нулю при Теорема 6.2 полностью доказана.

Перейдем теперь к оценке скорости сходимости общего неявного метода простой итерации. Следуя А. А. Самарскому, выясним вопрос о выборе такого значения параметра которое обеспечивает наиболее быструю сходимость.

Предположим, что матрица В является симметричной и положительно определенной. С помощью такой матрицы естественно ввести так называемое «энергетическое» скалярное произведение двух произвольных векторов X и Y, положив его равным . Такое скалярное произведение будем обозначать символом

С помощью матрицы это скалярное произведение можно записать в виде . С помощью последнего равенства легко проверяется справедливость для введенного нами скалярного произведения четырех аксиом скалярного произведения (см. п. 1 § 1, гл. 4).

Далее естественно ввести энергетическую норму вектора X, положив ее равной ). Эту энергетическую норму мы обозначим символом

Две различные нормы одной и той же совокупности векторов называют эквивалентными, если существуют такие положительные постоянные и что справедливы неравенства

Заметим, что энергетическая норма вектора X и обычная его норма являются эквивалентными. В самом деле, справедливость неравенства неравенства вытекает из положительной определенности матрицы В, а справедливость неравенства е. неравенства вытекает из неравенства Коши—Буняковского и оценки (6.7) (достаточно положить

Установленная эквивалентность обычной и энергетической норм позволяет утверждать, что последовательность сходится к нулю тогда и только тогда, когда сходится к нулю последовательность

Для дальнейших рассуждений энергетическая норма является более удобной, чем обычная норма.

Докажем следующую фундаментальную теорему.

Теорема 6.3 (теорема А. А. Самарского). Пусть матрицы А и В симметричны и положительно определены, обозначает погрешность общего неявного метода простой итерации. Тогда, для того чтобы при было справедливо неравенство достаточно, чтобы было выполнено условие

Замечание. А. А. Самарским доказано, что условие (6.21) не только достаточно, но и необходимо для справедливости неравенства но мы на этом останавливаться не будем.

Доказательство теоремы 6.3. Для удобства разобьем доказательство на два шага.

1°. Сначала докажем, что если симметричные и положительно определенные матрицы А и В удовлетворяют условиям Самарского (6.14), то

Умножая равенство (6.15) скалярно на получим

В последнем равенстве заменим на разность

Тогда, учитывая вытекающее из симметрии матрицы А равенство мы получим тождество

Учитывая, что (в силу условий Самарского (6.14)) операторы являются положительно определенными, мы получим из последнего тождества следующее неравенство:

Это неравенство эквивалентно доказываемому неравенству (в силу вытекающего из симметрии оператора В тождества

2°. Пусть теперь при выполнены условия Самарского (6.21). Докажем справедливость неравенства Положим Тогда, очевидно,

Подставляя эти значения в равенство (6.15) и производя сокращение на получим для величин следующее соотношение:

в котором

В силу условий (6.21) операторы В и А удовлетворяют условиям Из этих условий и из того, что уравнение (6.22) для совершенно идентично уравнению (6.15) для в силу первого шага для вытекает следующая оценка:

Из этой оценки в свою очередь, учитывая, что получим неравенство

Последовательное применение указанного неравенства для номеров приводит нас к соотношению а умножение последнего соотношения на приводит к окончательной оценке

Тем самым неравенство доказано. Доказательство теоремы 6.3 завершено.

В заключение применим теорему Самарского 6.3 для выяснения вопроса о выборе такого значения параметра при котором скорость сходимости является максимальной. Из доказанной в теореме 6.3 оценки с вытекает, что эта задача сводится к нахождению такого значения при котором достигается минимальное значение функции

Так как обе матрицы А и В симметричны и положительно определены, то существуют положительные постоянные и такие, что справедливы неравенства Будем считать, что постоянные и в этих неравенствах нам заданы. Сопоставляя только что написанные неравенства с условиями (6.21), мы получим, что минимальное значение достигается при условии откуда получаем оптимальное значение и минимальное значение равное

Частным случаем проведенного нами рассмотрения является явный метод простой итерации, изученный в Для этого метода справедливы все полученные нами результаты.

В следующих трех пунктах с помощью общего неявного метода простой итерации и теоремы Самарского 6.2 мы рассмотрим несколько наиболее употребительных итерационных методов и установим условия их сходимости.

<< Предыдущий параграф Следующий параграф >>
Оглавление