Министерство  Образования  Республики  Беларусь 

Белорусский государственный университет информатики и радиоэлектроники 
 
 
 
 
 
 
 
 

Лабораторная  работа №1

“Решение  систем линейных алгебраических уравнений прямыми  методами”

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Выполнила:                                                    Проверил:

  ст. гр. 251001                                   Черкас  Л.А..

Нестерчук А.Г. 
 
 
 
 
 
 
 
 

           Минск 2004

Цель  работы: Изучение одного из прямых методов решения СЛАУ - метода единственного деления, метода Гаусса с выбором главного элемента по столбцу метода оптимального исключения, метода Гаусса-Жордана или метода LU - разложения; применение этого метода для вычисления обратной матрицы; исследование накопления погрешностей округления при решении СЛАУ прямыми методами на ЭВМ. 

Краткие теоретические сведения 

      К прямым (или точным) методам решения СЛАУ относятся алгоритмы, которые в предположении, что вычисления ведутся без округлений, позволяют получить точное решение системы за конечное число арифметических действий. Чаще всего решение задач такими методами осуществляется поэтапно: на первом этапе систему преобразуют к тому или иному простому виду, на втором - решают упрощенную систему и получают значения неизвестных.

      Запишем систему линейных алгебраических уравнений в развернутом виде:

                    

где x₁, x₂,..., x_n - неизвестные величины, b₁, b₂,..., b_n - элементы правой части. Если определитель системы отличен от нуля, то она имеет единственное решение. Для удобства дальнейших преобразований обозначим элементы правой части а_i(n+1) и запишем расширенную матрицу размерами n´(n+1), которая содержит всю информацию о системе:

                  A = .

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

Приведем  формальное описание схем некоторых прямых методов. 

Метод Гаусса (схема единственного  деления). Алгоритм метода состоит из двух этапов. Первый этап называется прямым ходом метода и заключается в последовательном исключении неизвестных из уравнений, т.е. в приведении матрицы А к верхнему треугольному виду (ниже главной диагонали все нули). Для этого на первом шаге разделим первое уравнение системы на а₁₁ (предположим, что коэффициент а₁₁ ¹ 0, в противном случае осуществляем перестановку уравнений системы). Обозначим коэффициенты полученного приведенного уравнения , домножим его на коэффициент а₂₁ и вычтем из второго уравнения системы, исключая тем самым х₁ из второго уравнения (обнуляя коэффициент а₁₂ матрицы). Поступим аналогично с остальными уравнениями и получим новую систему, матрица которой в первом столбце, кроме первого элемента, содержит только нули, т.е. 

                   . 

      Первое  уравнение в дальнейших преобразования не участвует. Описанный выше процесс  исключения неизвестных применим к  матрице  размерами (n-1)´n. После k аналогичных шагов получим k приведенных уравнений с коэффициентами 

        

и матрицу  размерами (n - k)´(n - k+1), элементы которой вычисляются

по формулам  

       . 

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

      Обратный  ход метода Гаусса заключается в последовательном определении компонент решения, начиная с х_n и заканчивая х₁, по следующим формулам:

        

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

Метод оптимального исключения. В целях экономии оперативной памяти (примерно в 4 раза) операции  прямого и обратного хода метода Гаусса выполняются попеременно. На первом шаге после приведения первого уравнения исключается неизвестное x₁ из второго уравнения, а затем с помощью приведенного второго уравнения - неизвестное x₂ из первого. После (k-1) таких шагов матрица системы имеет вид 

             . 

На k-м шаге, используя первые k уравнений, исключаем неизвестные x₁,..,x_k из (k+1)-го уравнения. Затем посредством этого уравнения исключается неизвестное x_k+1 из первых k уравнений и т.д. В результате прямого хода матрица системы приводится к диагональному виду с единицами на главной диагонали. При этом отпадает необходимость обратного хода, поскольку столбец правой части

приведенной матрицы и является вектором решения. 
 
 

  Листинг программы  и результаты вычислений