ИТЕРАЦИОННЫЕ МЕТОДЫ РЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХ УРАВНЕНИЙ

В разд. 8.2 мы рассмотрели метод исключения (конечный метод), с помощью которого можно решить систему линейных алгебраических уравнений. Затем в разд. 8.4 мы увидели, как можно уточнить решение, повторно используя метод исключения. В сущности, этот метод уточнения решения является итерационным. Таким образом, и здесь проявляется обычное противоречие между теорией и практикой вычислений на ЭЦВМ — благодаря ошибкам округления решение, получаемое с помощью конечного и точного метода, может сильно отличаться от истинного, с помощью же итерационного метода это решение можно существенно улучшить.

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

Оказывается, что условия сходимости этого итерационного метода очень часто выполняются тогда, когда с помощью определенных приемов решаются уравнения в частных производных. К этому вопросу мы еще вернемся в гл. 11.

Рассмотрим систему из трех уравнений с тремя неизвестными (8.5), (8.6) и (8.7). Предположим, что а_ij≠0, с₂₂≠0, а₃₃≠0, и перепишем систему в следующем виде:

(8.32) (8.33)(8.34)

Теперь возьмем некоторое первое приближение к решению этой системы, обозначив его через х⁰₁, х⁰₂, х⁰₃. Подставим это решение в (8.32) и вычислим новое значение х₁:

Используя только что вычисленное значение x⁽¹⁾₁ и начальное значение x⁰₃, вычислим из уравнения (8.33) новое значение х₂:

Наконец, используя только что вычисленные значения x⁽¹⁾₁ и x⁽¹⁾₂ найдем из (8.34) новое значение х₃:

Этим заканчивается первая итерация. Теперь можно заменить исходные значения x⁽⁰⁾₁, x⁽⁰⁾₂, и x⁽⁰⁾₃ на x⁽¹⁾₁, х⁽¹⁾₂, х⁽¹⁾₃ и вычислить следующее приближение. В общем случае k -e приближение определяется формулами

(8.35)

Заметим, что текущие значения неизвестных сразу же используются для последующих вычислений и что, например, нельзя вычислять x^(k)₂, пока не получено х^(k)₁. Аналогично этому для вычисления х^(k)₃ необходимо сначала определить x^(k)₁ и x^(k)₂.

Только что описанный здесь метод известен как итерационный метод Гаусса — Зейделя. Этот метод исключительно удобен для использования на ЭЦВМ. Перед обобщением на случай n уравнений с n неизвестными и выводом условия сходимости метода рассмотрим простой численный пример

Нетрудно убедиться, что точное решение этой системы равно x₁=1, х₂=1, х₃=1. Положим х⁰₁=x⁰₂=х⁰₃=0, как это обычно делается для начального приближения. Тогда, вычисляя согласно формулам

получаем следующее приближение:

Последовательные приближения, вычисленные каждый раз с точностью до четырех значащих цифр, приведены в табл. 8.1.

Таблица 8.1

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

Рассмотрим теперь систему (8.13) из n уравнений с n неизвестными. Мы по-прежнему предполагаем, что диагональные коэффициенты a_ij отличны от нуля для всех i. Тогда k -e приближение к решению будет задаваться формулой

Итерационный процесс продолжается до тех пор, пока все х^(k)_i не станут достаточно близки к x^(k-1)_i. Критерий близости можно, например, задать в следующем виде:

где определяется максимальное значение разности для всех i, а ε — некоторое положительное число. При выполнении критерия итерационный процесс следует остановить. Можно заменить этот критерий близости, сравнивая с ε не абсолютные, а относительные разности

Блок-схема программы для вычислений по методу Гаусса-Зейделя приведена на рис. 8.9. Она вовсе не так сложна, как это может показаться с первого взгляда. Вспомним хотя бы, что блок-схема для метода исключения заняла три рисунка—8.5, 8.6 и 8.8.

В левой части рисунка изображены действия, связанные со вводом исходных данных и подготовкой к вычислениям. В этой части рисунка указано, что начальное приближение принимается равным нулю, а счетчику количества итераций присваивается значение 1. Как обычно, для подсчета количества итераций используется целая переменная ITER. При дальнейших вычислениях эти начальные действия не повторяются. В конце этой части блок-схемы стоит кружок с цифрой внутри, так называемая связка. Эта связка означает, что блок-схема продолжается, начиная с кружка, содержащего ту же цифру, в нашем случае со средней части рисунка, где вверху поставлен кружок с цифрой 1. Связки часто используются в блок-схемах, чтобы не проводить длинных пересекающихся линий.

Переменная BIG используется для того, чтобы определять наибольшее значение разности между x^(k)_i и х^(k-1)_i. Сначала этой переменной присваивается значение нуль, а затем с ней сравниваются абсолютные значения разностей |x^(k)_i-x^(k-1)_i|. Если какая-либо разность оказывается по абсолютной величине больше BIG, то прежнее значение BIG заменяется этой разностью. После вычисления всех x^(k)_i наибольшая разность будет равна значению переменной BIG.

Затем в блок-схеме следует группа действий, с помощью которых вычисляется сумма всех членов уравнения, кроме диагонального. По ходу программы удобнее сначала вычислять и суммировать члены, стоящие перед диагональным (так как в них используются новые значения x^(k)_i), а уже потом — члены, идущие после него (так как в них используются старые значения x^(k-1)_i). Необходимо также несколько усложнить эту логику в связи с тем, что в первом и последнем уравнениях отсутствуют члены, стоящие соответственно до и после диагонального.

В правой части блок-схемы указана группа действий, начинающаяся с вычисления нового значения x^(k)_i; определяется максимальная разность и запоминается новое значение х^(k)_i. Если это было не последнее уравнение, то мы увеличиваем индекс i и начинаем вычислять очередное

Рис. 8.9. Блок-схема программы для решения системы линейных уравнений итерационным методом Гаусса — Зейделя.

приближение для следующего неизвестного. В случае последнего уравнения мы сравниваем максимальную разность с ε и печатаем результаты, если процесс сошелся. Если же итерационный процесс не сошелся, то мы производим операции, относящиеся к самому программированию, но не к численному методу. Дело в том, что процесс, который должен сходиться, в действительности не всегда сходится. Причин этому может быть очень много: от ошибок в программе до неверных исходных данных. Поэтому в начале программы с перфокарты было прочитано целое число МАХ, которое определяет максимально допустимое число итераций. Обычно это число выбирается несколько большим необходимого количества итераций. (Ориентировочно для МАХ можно принять значение 50 при решении системы из 50 уравнений.) Тогда, если по какой-либо причине итерационный процесс не сошелся, ЭЦВМ не будет работать бесконечно долго. Практически для любого итерационного метода необходимо предусматривать в программе такой счетчик в той или иной форме.

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

Теперь обратимся к вопросу сходимости метода. Перед обобщением на случай n уравнений подробно рассмотрим более простой пример — систему из двух уравнений. Запишем уравнения в виде

(8.36) (8.37)

так что

(8.38) (8.39)

Если обозначить

то из (8.36) и (8.38) следует

а из (8.37) и (8.39)

Сравнивая последние два уравнения, нетрудно получить, что

Аналогично

так что

Продолжая дальше таким же образом, получим

Аналогично

Поэтому если

(8.40)

то итерационный метод Гаусса — Зейделя сходится к решению уравнений (8.36) и (8.37).

Нетрудно увидеть аналогию между выкладками, произведенными в этом разделе, и теми, которые были использованы при решении вопроса о сходимости метода последовательных приближений в разд. 5.2.

Соотношение (8.40) можно удовлетворить, если

(8.41)

или если

(8.42)

Рис. 8.10. Геометрическое представление итерационного метода Гаусса-Зейделя для случая сходимости.

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

Точное решение равно х=2/5, у=6/5, как показано на рис. 8.10. Результаты последовательных итераций составляют

Полезно представить себе процесс решения геометрически. Мы начинаем искать решение от начала координат (0, 0). Так как при вычислении x мы сохраняем неизменным значение y, то геометрически это соответствует движению по горизонтали до пересечения ее с прямой, соответствующей первому уравнению (2x+у=2). Затем, сохраняя неизменным только что найденное значение x, мы начинаем двигаться по вертикали, пока не пересечем прямую, соответствующую второму уравнению (x-2у=-2). На рис. 8.10 такому процессу соответствует путь ОАВ. На этом заканчивается одна итерация.

Дальнейшие итерации производятся точно таким же образом; на рис. 8.10 их последовательность представлена горизонтальными и вертикальными линиями со стрелками. Заметим, что процесс сходится к решению системы уравнений. Отметим также сходство между рис. 8.10 и рис. 5.2.

Посмотрим теперь, что случится, если мы переставим уравнения:

Результаты последовательных итераций составляют

Геометрически этот случай проиллюстрирован на рис. 8.11. Снова можно отметить сходство с рис. 5.4. Трудность на этот раз состоит в том, что угол наклона прямой, соответствующей первому уравнению, меньше 1 и поэтому Δх получается чересчур большим. Аналогично, большой угол наклона прямой, соответствующей второму уравнению, приводит к слишком большой величине Δy. Короче говоря, процесс расходится.

Очевидно, что для сходимости процесса первая прямая

Рис. 8.11. Геометрическое представление итерационного метода Гаусса — Зейделя для случая расходимости.

должна иметь наклон больше 1, а вторая — меньше 1. Эти условия полностью эквивалентны условиям (8.41) и (8.42), записанным в аналитическом виде.

Вспомним, однако, что фактически условие сходимости, которому нужно удовлетворить, выражается формулой (8.40) и что это условие гораздо слабее условий (8.41) и (8.42). Зададимся вопросом: возможен ли случай, когда первая прямая имеет наклон меньше 1, но вторая имеет такой малый угол наклона, что процесс тем не менее сходится? Или, иными словами, если даже Δх велико, то может ли Δy быть достаточно малым, чтобы обеспечить сходимость метода? На этот вопрос можно ответить положительно.

Рассмотрим следующий пример:

Наклон прямых, соответствующий обоим уравнениям, меньше 1. Поэтому

т. е. нарушено и условие (8.41), и (8.42). Заметим, однако, что условие (8.40) для этой системы удовлетворяется.

Рис. 8.12. Геометрическое представление итерационного метода Гаусса — Зейделя для случая, когда достаточные условия сходимости не выполнены, но метод тем не менее сходится.

Геометрическое толкование процесса последовательных приближений показано на рис. 8.12. Результаты последовательных итераций составляют

Решением этой системы являются к= 1, у= 1. Таким образом, условия (8.41) и (8.42) являются достаточными условиями для сходимости, но они не являются необходимыми. Иными словами, выполнение какого-нибудь из них гарантирует сходимость метода, но в то же время существуют системы, для которых эти условия не выполняются, но метод итераций все равно сходится.

Мы рассмотрели пример, где наклон первой прямой был меньше —1, а второй — положителен, но меньше +1, т. е.

Как показывает рис. 8.10, сходимость носила в этом случае колебательный характер. В другом примере, где наклоны удовлетворяли неравенствам

расходимость также являлась колебательной. Можно легко проверить, что при |k₁|>=1, |k₂|<=1, где по крайней мере одно из неравенств является строгим, справедливы следующие утверждения:

1. Если k₁ и k₂ имеют одинаковые знаки, то процесс сходится к решению с одной стороны.

2. Если k₁ и k₂ имеют разные знаки, то сходимость носит колебательный характер.

Теперь мы приведем без доказательства достаточные условия сходимости итерационного метода Гаусса — Зейделя для системы из n уравнений с n неизвестными.

Если система уравнений неприводима[1], если

для всех i и если по крайней мере для одного i

то итерационный метод Гаусса—Зейделя сходится к решению системы уравнений (8.13).

Выполнение этих условий обеспечивает сходимость метода. Мы еще раз подчеркиваем, что эти условия ни в коем случае не являются необходимыми. Они выведены путем соответствующего обобщения условий (8.41) и (8.42).

У читателя может возникнуть вопрос, оставляют ли эти достаточно жесткие условия какую-либо практическую возможность для применения метода Гаусса—Зейделя. Оказывается, что да. Во многих областях прикладной математики возникает необходимость решать системы линейных уравнений, причем коэффициенты этих уравнений получаются такими, что условия сходимости метода Гаусса—Зейделя автоматически выполняются. В частности, именно такими получаются системы, связанные с решением на ЭЦВМ уравнений в частных производных, как мы это увидим в гл. 11.

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

СРАВНЕНИЕ МЕТОДОВ

Мы рассмотрели два основных метода решения систем линейных алгебраических уравнений — метод исключения и итерационный метод Гаусса — Зейделя.. Естественно, возникает вопрос, какой из этих методов предпочтительнее.

Метод исключения имеет то преимущество, что он конечен и теоретически с его помощью можно решить любую невырожденную систему уравнений. Итерационный метод Гаусса — Зейделя сходится только для специальных систем уравнений. Для некоторых систем метод исключения является единственно возможным[2].

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

1. Время вычислений пропорционально n² на итерацию, в то время как для метода исключения время вычислений пропорционально n³; если для решения системы требуется менее n итераций, то общие затраты машинного времени будут меньше.

2. Как правило, ошибки округления при итерационном методе меньше; иногда это соображение может оказаться достаточно важным и оправдывает дополнительные затраты машинного времени.

Многие системы уравнений, возникающие на практике, имеют среди коэффициентов большой процент нулей. В этих случаях итерационные методы — если они сходятся — в высшей степени предпочтительны, так как при использовании метода исключения получается треугольная система уравнений, которая обычно уже не имеет нулей в качестве коэффициентов[3]. При решении системы уравнений на ЭЦВМ система с большим количеством нулей предпочтительна потому, что можно проверять коэффициенты и не производить умножения, если они равны нулю. Уравнения, получаемые при решении уравнений в частных производных, относятся именно к этому классу.

Наконец, некоторые системы уравнений настолько велики, что их не только нельзя точно решить методом исключения, но даже нельзя поместить целиком в оперативную память ЭЦВМ. Если коэффициенты этих уравнений вычисляются самой ЭЦВМ с помощью некоторой программы, то такое затруднение можно обойти при использовании итерационного метода, вычисляя коэффициенты каждого уравнения тогда, когда в них возникает необходимость. Системы, возникающие при решении уравнений в частных производных, опять-таки относятся к этому классу.

Не нашли, что искали? Воспользуйтесь поиском: