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

4.3.3. Прямые методы решения систем линейных алгебраических уравнений

Правило Крамера. Это один из самых простых методов. Все студенты наверняка слышали о нем, и большинство из них знакомы с процедурой этого метода. К сожалению, он требует чрезвычайно больших затрат машинного времени. Число операций, необходимых для решения системы уравнений, пропорционально (Л + 1)» где - число неизвестных. Много ужасных историй рассказывалось о большом времени, затрачиваемом на решение уравнений по правилу Крамера. Излюбленный пример приводится Роучем [Roache, 1972]. Для решения по правилу Крамера системы 26 уравнений с 26 неизвестными на ЭВМ CDC6600 потребуется 10 лет. Это в 10 раз больше оцениваемого современной наукой времени существования Вселенной! Не вызывает сомнения, что до тех пор, пока выбор метода в наших руках, мы никогда не воспользуемся для решения уравнений правилом Крамера.

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

1-е опорное уравнение

Рис. 4.20. Метод исключения Гаусса, неизвестная Ui под главной диагональю исключена.

рых уравнений. Выберем, например, в качестве опорного первое уравнение (строку) рассматриваемой системы и используем его для исключения неизвестной щ из расположенных ниже уравнений. Для этого сначала умножим первое уравнение на а2\1а\\ ) и вычтем его из второго уравнения системы, что позволит исключить u\ из второго уравнения. Умножая опорное уравнение на az\/a\\ и вычитая результат из третьего уравнения, исключим из него u\. Таким образом, можно исключить u\ из всех уравнений от 2-го до п-го. В результате система уравнений примет вид, изображенный на рис. 4.20.

Теперь второе уравнение (в том виде, какой оно приняло после применения описанной выше процедуры исключения) ис-

Чтобы избежать деления на нуль, мы всегда можем поменять уравнения местами.

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

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

«111+«12«2+........=Си

а2хЩ + 022/2 +........= 2,

; (4.118)

«,11,1+..............=п.

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

пользуем в качестве опорного* для исключения неизвестной U2 во всех ниже расположенных уравнениях, что приведет систему уравнений к виду, показанному на рис. 4.21. Третье уравнение получившейся системы используется как опорное для исключе-

I 1-е опорное уравнение

1 j I 2-6 опорное цравненйГ

1§

I г=

Рис. 4.21. Метод исключения Гаусса, неизвестные Ui и «2 под главной диагональю исключены.

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

ailWl + «12«2+...........=Си

22«2 + 2з"з+ •••• =4

зз"з+ .... = 4» (4.119)

пп п п*

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

В качестве числового примера рассмотрим систему трех уравнений

f/i + 4f/2 + f/3 = 7,

f/l + 6f/2-f/3=13,

2f/i-f/2 + 2f/3 = 5.

Используя первое уравнение в качестве опорного, исключим Ui из двух последних уравнений:

f/,-f 4[/2 + f/3 = 7, 2[/2-2f/3 = 6, -9[/2 + 0 = -9.

Теперь выберем опорным второе уравнение и приведем систему