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

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

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

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

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

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

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

        a₁₁x₁+a₁₂x₂+ … +a_1nx_n=b₁;

        a₂₁x₁+a₂₂x₂+ … +a_2nx_n=b_n;

        . . . . . . . . . . .

        a_n1x₁+a_n2x₂+ … +a_nnx_n=b_n;

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

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

       ┌ a₁₁  a₁₂  … a_1n  a_1,n+1 ┐

    R= │ a₂₁  a₂₂  … a_2n  a_2,n+1 │

       │ . . . . . . . . . │

       └ a_n1  a_n2  … a_nn  a_n,n+1 ┘

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

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

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

       a₁₁x₁+a₁₂x₂+a₁₃x₃=b₁;        ┌ a₁₁  a₁₂  a₁₃  a₁₄ ┐

       a₂₁x₁+a₂₂x₂+a₂₃x₃=b₂;      R=│ a₂₁  a₂₂  a₂₃  a₂₄ │

       a₃₁x₁+a₃₂x₂+a₃₃x₃=b₃;        └ a₃₁  a₃₂  a₃₃  a₃₄ ┘

где a₁₄=b₁;  a₂₄=b₂;  a₃₄=b₃.

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

       x₁+a₁₂'x₂+a₁₃'x₃=b₁';        ┌ 1  a₁₂'  a₁₃'   a₁₄' ┐

             x₂+a₂₃'x₃=b₂';      R=│ 0    1     a₂₃'  a₂₄' │

                   x₃=b₃';        └ 0   0      1     a₃₄' ┘

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

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

x₃ = a₃₄'.

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

                  x₂ = (a₂₄' - a₂₃'x₃);

                  x₁ = (a₁₄' - a₁₂'x₂ - a₁₃'x₃).

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

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

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

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

Заполнение массива {a₁₁ .. a_n,n+1}

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

│norm=a_kk

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

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

│  │z=a_ik

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

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

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

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

│s=0

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

│x_i= a_i,N+1 - s

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

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

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

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

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

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

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

                                     detA = ± a₁₁'a₂₂'…a_nn'

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