Глава 6 итерациональные методы решения линейных алгебраических систем

МЕТОД ПРОСТЫХ ИТЕРАЦИЙ

Рассмотрим систему вида

, (6.1)

где – матрица, а и – -мерные векторы-столбцы.

Преобразуем (6.1) к эквивалентной ей системе вида

(6.2)

где и — некоторые новые матрица и вектор соответственно.

Определим последовательность приближений к неподвижной точке рекуррентным равенством

(6.3)

Итерационный процесс (6.3), начинающийся с некоторого вектора , называется методом простых итераций (МПИ).

Условия сходимости МПИ представлены в следующих теоремах.

Теорема 6.1. Необходимым и достаточным условием сходимости метода простых итераций (6.3) при любом начальном векторе к решению системы (6.2) является требование, чтобы все собственные числа матрицы были во модулю меньше 1.

Теорема 6.2.Пусть . Тогда, при любом начальном векторе МПИ (6.3) сходится к единственному решению задачи (6.2) и, при всех , справедливы оценки погрешности:

1. (апостериорная);

2. (априорная).

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

Замечание 6.1. Априорная оценка позволяет подсчитывать заранее число итераций k, достаточное для получения решения с заданной точностью (в смысле допустимого уровня абсолютных погрешностей) при выбранном начальном векторе . Для этого нужно найти наименьшее целое решение неравенства

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

Отметим, что неравенство будет гарантией выполнения неравенства только в том случае, когда .

Априорная оценка, как правило, грубее апостериорной.

Замечание 6.2. Как установлено выше, сходимость МПИ (6.3) при условии гарантируется при любом начальном векторе . Очевидно, итераций потребуется тем меньше, чем ближе к .Если нет никакой дополнительной информации о решении задачи (6.2), за х⁽⁰⁾ обычно принимают вектор свободных членов системы (6.2) .Мотивация этого может быть такой: матрица «мала», значит вектор «мал», следовательно и вектор не должен сильно отличаться от вектора . При выборе фигурирующая в теореме 6.2 априорная оценка принимает вид

МЕТОД ЯКОБИ

Рассмотрим один из способов приведения системы (6.1) к виду (6.2).

Представим матрицу системы (6.1) в виде

,

где — диагональная, а и— соответственно левая и правая строго треугольные (т.е. с нулевой диагональю) матрицы. Тогда система (6.1) может быть записана в виде

(6.7)

и если на диагонали исходной матрицы нет нулей, то эквивалентной (6.1) задачей вида (6.2) будет

, (6.8)

т.е. в равенствах (6.2) и (6.3) следует положить

Основанный на таком приведении системы (6.1) к виду (6.2) метод простых итераций (6.3) называют методом Якоби.

В векторно-матричных обозначениях он определяется формулой

(6.9)

Чтобы записать метод Якоби (6.9) решения системы (6.1) в развернутом виде, достаточно заметить, что обратной матрицей к матрице служит диагональная матрица с элементами диагонали . Поэтому представление (6.8) системы (6.1), записанной в виде (6.7), равнозначно выражению «диагональных неизвестных» через остальные:

(6.10)

При этом итерационный процесс имеет вид

(6.9а)

Теорема 6.3. В случае диагонального преобладания в матрице системы (6.1) метод Якоби (6.9) сходится.

Замечание 6.3. К методу Якоби при условии диагонального преобладания в матрице относится полностью заключение теоремы 6.2, а также предыдущие замечания; нужно лишь учесть в них, что матрица определяется с помощью (6.11), а вектор – равенством

.

Теорема 6.4.Метод Якоби (6.9) сходится к решению системы (6.1) в том и только том случае, когда все корни уравнения

по модулю меньше единицы.

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

.

Последнее же эквивалентно уравнению

,

которое в записи через элементы исходной матрицы и фигурирует в формулировке теоремы.

МЕТОД ЗЕЙДЕЛЯ

Под методом Зейделя обычно понимается такое видоизменение метода простых итераций (6.3) решения СЛАУ, приведенных к виду (6.2), при котором для подсчета -й компоненты -го приближения к искомому вектору используются уже найденные на этом, т.е. -м шаге, новые значения первых компонент. Это означает, что если система (6.1) тем или иным способом сведена к системе (6.2) с матрицей коэффициентов и вектором свободных членов ,то приближения к ее решению по методу Зейделя определяются системой равенств

(6.12)

где , a – компоненты заданного (выбранного) начального вектора .

Остановимся подробнее на случае, когда приведение системы (6.1) к виду (6.2) основано на представлении (6.7), т. е. когда метод Зейделя есть модификация метода Якоби. Запись соответствующих расчетных формул здесь сводится к верхней индексации системы (6.10) по типу (6.12):

(6.13)

где ; задается.

Для анализа сходимости метода Зейделя (6.13) обратимся к его векторно-матричной форме. Легко видеть, что если неявный вид метода Якоби, вытекающий из представления (6.7) системы (6.1), есть

(сравните с (6.9)),

то равнозначный (6.13) неявный вид метода Зейделя в векторно-матричных обозначениях суть

.

Следовательно, тот же вектор ,который фигурирует в левой части совокупности равенств (6.13), может быть получен по формуле

(6.14)

Последнее выражение определяет не что иное, как МПИ (6.3) для системы вида (6.2), где

,

т. е. результат применения одного шага метода Зейделя (6.13), полученного на основе – разложения матрицы ,можно расценивать, как шаг МПИ для эквивалентной (6.1) задачи о неподвижной точке

(6.15)

(разумеется, если треугольная матрица обратима). Эта связь между методом Зейделя и методом простых итераций позволяет легко переформулировать некоторые утверждения о сходимости МПИ применительно к методу Зейделя (6.13).

Теорема 6.5.Для сходимости метода Зейделя (6.13) необходимо и достаточно, чтобы все корни уравнения

(6.16)

были по модулю меньше единицы.

Прямым следствием теоремы 6.2 для метода Зейделя (6.13) является следующая теорема.

Теорема 6.6.Пусть . Тогда при любом начальном векторе метод Зейделя (6.13) сходится к решению системы (6.1) и справедливы оценки погрешности

(6.17)

Ясно, что для непосредственного использования оценок (6.17) нужно предварительно выполнить обращение треугольной матрицы и перемножить матрицы и . В таком случае частично теряется смысл в поэлементной реализации метода Зейделя (6.13);вместо этого можно проводить итерации по формуле (6.14) до тех пор, пока не выполнится условие , где – требуемая точность. В частности, такой подход может быть рекомендован при решении СЛАУ методом Зейделя на компьютерах с векторной обработкой информации.

Более подходящие для использования оценки погрешности метода Зейделя (6.13) можно получить, разлагая матрицу (см. (6.11)) в сумму двух строго треугольных матриц, т.е. полагая

,

где

,

.

С ними эквивалентное (6.1) уравнение (6.2) приобретает вид

,

т.е. для решения будет точным равенство

,

а метод Зейделя (6.13) – соответственно

.

Из двух последних равенств получаем следующее:

.

Это равенство, записанное в виде

(6.18)

можно расценивать как точную связь между погрешностями -го и -го приближений в методе Зейделя (6.13). Отсюда, переходя к нормам, легко вывести априорную оценку погрешности, что можно оформить в виде следующего утверждения.

Теорема 6.7.Пусть . Тогда метод Зейделя (6.13) определяет сходящуюся последовательность при любом начальном векторе , и имеет место оценка

Как и у предыдущей, у этой теоремы имеются свои недостатки, затрудняющие ее применение: нужно знать меру близости начального приближения к решению . Ценность ее скорее в том, что в ней фигурирует легко вычисляемый коэффициент связи ошибок результатов двух соседних итерационных шагов, характеризующий быстроту сходимости метода Зейделя (6.13). При организации практических вычислений по формулам (6.13) целесообразнее ориентироваться на следующий результат.

Теорема 6.8.Пусть , (где – матрица (6.11)). Тогда для определяемой методом Зейделя (6.13) последовательности приближений справедлива апостериорная оценка погрешности

.

Из теоремы 6.8 вытекает следующая, более удобная на практике, формулировка.

Следствие 6.1. Пусть – первое из натуральных чисел k, с которым при заданном для генерируемой процессом Зейделя (6.13) последовательности векторов некоторых согласованных нормах выполняется равенство

.

Тогда за решение системы (6.1) может быть принят вектор , и абсолютная погрешность при этом не будет превышать (в выбранной норме).

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

Теорема 6.9.Если в матрице системы (6.1)имеет место диагональное преобладание, то метод Зейделя (6.13) сходится, причем быстрее, чем метод Якоби (6.9а).

Замечание 6.4. В соответствии с последней теоремой в методе Зейделя (6.13) вместо оценок (6.17), требующих дополнительных затрат на обращение треугольной матрицы, допустимо использование оценок погрешности метода Якоби. Естественно, они заведомо грубее.

Остановимся еще на одном важном для приложений классе систем вида (6.1), для которых имеет место сходимость метода Зейделя(6.13).

Определение (6.1). Система называется нормальной, если матрица – симметричная положительно определенная.

Теорема 6.10. Если система (6.1) – нормальная, то метод Зейделя (6.13) сходится.

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

Теорема 6.11. Пусть . Тогда система – нормальная.

Таким образом, если, например, известно, что система (6.1) однозначно разрешима, но в ее матрице коэффициентов нет диагонального преобладания, метод Зейделя типа (6.13) можно применять к системе . Правда, здесь возникают трудности со своевременным окончанием процесса итерирования, обеспечивающим заданную точность приближенного решения, так как приведенные ранее оценки погрешности (см. теорему 6.6 и замечание 6.7) в этом случае часто «не работают». Да и сходимость при этом может оказаться весьма медленной.

Наряду с рассмотренными, применяют и другие способы приведения систем (6.1) к виду (6.2) для их решения методами простых итераций и Зейделя. Достаточно общий подход к этой процедуре заключается в том, что эквивалентное (6.1) уравнение умножается на некоторую неособенную матрицу (матричный параметр) и к обеим частям прибавляется вектор х. Полученное уравнение

,

переписанное в виде

,

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