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

Страницы работы

Фрагмент текста работы

ЛАБОРАТОРНАЯ РАБОТА  II-1-12

ЧИСЛЕННЫЕ МЕТОДЫ РЕШЕНИЯ

СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ

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

1. О методах решения систем линейных уравнений

Решение систем линейных алгебраических уравнений:

        a11x1+a12x2+ … +a1nxn=b1;

        a21x1+a22x2+ … +a2nxn=bn;

        . . . . . . . . . . .

        an1x1+an2x2+ … +annxn=bn;

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

Наиболее распространенными среди прямых методов являются метод исключения Гаусса и его модификации. Для упрощения записи отдельных действий метода Гаусса обычно используют т.н. расширенную матрицу, i-я строка которой  содержит коэффициенты и правые части i-го уравнения (an,n+1=bn).

       ┌ a11  a12  … a1n  a1,n+1

    R= │ a21  a22  … a2n  a2,n+1

       │ . . . . . . . . . │

       └ an1  an2  … ann  an,n+1

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

2. Алгоритм метода Гаусса

Рассмотрим применение метода Гаусса для системы уравнений            

       a11x1+a12x2+a13x3=b1;        ┌ a11  a12  a13  a14

       a21x1+a22x2+a23x3=b2;      R=│ a21  a22  a23  a24

       a31x1+a32x2+a33x3=b3;        └ a31  a32  a33  a34

где a14=b1;  a24=b2;  a34=b3.

МетодГаусса основан на приведении расширенной матрицы системы к треугольному виду, в котором все поддиагональные элементы равны 0, а диагональные равны 1 (т.н. схема единственного деления). Это соответствует последова­тельному исключению неизвестных из уравнений систе­мы.

       x1+a12'x2+a13'x3=b1';        ┌ 1  a12'  a13'   a14'

             x2+a23'x3=b2';      R=│ 0    1     a23'  a24'

                   x3=b3';        └ 0   0      1     a34'

Сначала первая строка нормируется (все элементы строки делятся на a11, и на диагонали появляется 1), а затем  с помощью первой строки получаются 0 в элементах первого столбца (при этом первая строка называется ведущей). Затем нормируется вторая строка, и формируются нулевые элементы во втором столбце (ведущая - вторая строка), и так далее. Этот процесс, называе­мый прямым ходом метода Гаусса.

Обратный ход метода Гаусса начинается с решения последнего уравнения

x3 = a34'.

Используя это значение, можно найти x2 из второго урав­нения, а затем x1 из первого:

                  x2 = (a24' - a23'x3);

                  x1 = (a14' - a12'x2 - a13'x3).

Аналогично строится вычислительный алгоритм для линейной системы с произвольным числом уравнений.

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

Алгоритм простого метода Гаусса можно отобразить следующим образом:

Запрос и ввод количества уравнений N

Заполнение массива {a11 .. an,n+1}

Для k=1 до N выполнить               (----прямой ход)

│norm=akk

│Для j=k до N+1 выполнить akj=akj/norm

│Для i=k+1 до N выполнить

│  │z=aik

│  │Для j=k до N+1 выполнить aij=aij-akj*z

│  │Вывод элементов матрицы на экран  

xN=aN,N+1                              (----обратный ход)

Для i=N-1 до 1 шаг (-1) выполнить

│s=0

│Для j=i+1 до N выполнить s=s+aij*xj

│xi= ai,N+1 - s

Вывод массива {xi}

2. Алгоритм метода Гаусса


Он состоит в том, что требование неравенства нулю диагональных элемен­тов akk,  на которые происхо­дит деление в процессе нормирования строк, заменяется более жестким: из всех оставших­ся в k-м столбце элементов нужно  выбрать  наиболь­ший по модулю и переставить уравнения так, чтобы этот элемент оказался диагональным. Это позволяет уменьшить вычислительные погрешности при выполнении операции деления.

4. Метод Гаусса-Жордана

Если с помощью ведущей строки получать 0 не тольно в поддиагональных, но и в наддиагональных элементах расширенной матрицы, то обратный ход становится особенно простым: xi=ai,n+1'.

5. Вычисление определителя матрицы

Непосредственное нахождение определите­ля требует большого объема вычислений. Вместе с тем легко вычисляется определитель треугольной матрицы: он равен произведению ее диагональных элементов. Для приведения матрицы к треугольному виду может быть использован метод исключения, т. е. прямой ход метода Гаусса. В процессе исключения элементов вели­чина определителя не меняется. В схеме единственного деления диагональные элементы z=akk нормируются на 1. Поэтому их произведение будет соответствовать определителю матрицы. Знак определителя ме­няется на противоположный при перестановке его столб­цов или строк. Следовательно, значение определителя по­сле приведения матрицы А к треугольному виду вычис­ляется как произведение диагональных элементов преобразо­ванной матрицы

                                     detA = ± a11'a22'…ann'

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

Похожие материалы

Информация о работе