Системы линейных алгебраических уравнений .

Метод Гаусса, схема единственного деления.

 

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

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

Пусть для нахождения решения мы хотим воспользоваться теоремой Крамера, при этом детерминанты будем вычислять по их обычному определению, как сумму со знаками п! Произведений элементов по одному из каждой строки и каждого столбца. Легко можно подсчитать, что для нахождения решения нужно будет приблизительно п2п! умножении и делений. Уже при п = 20 это число приблизительно равно 1021 и является настолько большим, что становится ясней невозможность решать указанным путем на современных машинах систему даже двадцати уравнений.

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

Какого сокращения вычислительной работы здесь можно достигнуть, мы поясним следующим примером: в методе исключения при применении схемы единственного деления для решения системы п уравнений требуется, как выяснится ниже,   умножений и делений. При больших п эта величина во много раз меньше, чем n2n!. Так, для п = 20 она имеет значение 3270, и поэтому система двадцати уравнений по этому методу может быть быстро решена.

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

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

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

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

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

 

                                        

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

Выберем какое-либо уравнение и какое-либо неизвестное в нем. Единственное условие, которое должно быть соблюдено при выборе, состоит в том, что коэффициент при избранном неизвестном должен быть отличен от нуля. Переставляя, если необходимо, уравнения и изменяя места неизвестных, можно считать, что избрано первое уравнение, неизвестное х1, и при этом  a11≠0.   Разделим уравнение на a11  и приведем его к виду

 

x1+b12x2+…+ b1nxn=g1.                                           

Исключим теперь х1 из остальных уравнений системы. Будем умножать (3.46) последовательно на а21, а31, ...,аn1 и вычитать из второго, третьего ..., последнего уравнения системы. Преобразованные так уравнения будут иметь форму

 

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

Предположим, что было проделано т шагов преобразований, где т<п, и при этом новая система приняла вид

 

 

 

                                        

Если среди свободных членов fm+1,m, …, fn,m   будут отличные от нуля, система не имеет решения, и уравнения заданной системы (3.45) являются несовместными. Если же свободные члены fm+1,m, …, fn,m все равны нулю, последние п — т уравнений системы (3.48) выполняются тождественно, и система приводится к первым т уравнениям. Из них могут быть найдены неизвестные x1, …, хт. Другие неизвестные хт+1, ..., хп остаются произвольными и им можно придавать любые значения. В этом случае заданная система является неопределенной.

         Пусть т = п. Тогда после преобразований получится система

 

                                           

Последнее уравнение дает значение хn, из предпоследнего уравнения находится xn-1  и т. д.

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

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

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

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