ТЕМА 2. МЕТОДЫ РЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ

Система линейных алгебраических уравнений (СЛАУ) имеет вид:

Ее можно представить в матричном виде:

A×X = B

где A - матрица коэффициентов, столбец Х^T=(x₁, x₂, … , x_n) – столбец неизвестных переменных, В^T=(b₁, b₂,…, b_n) - столбец правых частей системы.

Для того, чтобы система могла иметь решение, нужно, чтобы ее определитель не был равен нулю, тогда матрица А — будет невырожденной, а сама система называется совместной.

Способы решения СЛАУ.

1. Метод Гаусса.

Он может быть реализован в аналитическом или алгоритмическом виде. Суть аналитического решения по методу Гаусса (МГ):

1) преобразовать СЛАУ к ступенчатому виду – прямой ход МГ;

2) восстановить значения неизвестных переменных с х_n до х₁ –обратный ход МГ.

Алгоритм прямого хода МГимеет три шага:

1. Проверка a_ii=0. Если условие выполняется, то заменить элементы i-ой и (i+1)-ой строк.

2. Преобразовать элементы i-ой строки так, чтобы a_ii =1, то есть поделить элементы этой строки на a_ii.

3. Все строки с номерами i+1, i+2, …, n преобразовать так, чтобы a_i+1,i , a_i+2,i , … , a_n,i были равны нулю, то есть вычесть последовательно из каждой i+1, i+2, …, n-ой строки i-ую строку, умноженную на a_i+1,i.

Пример 2.1:

3x+2y+z=5      (1стр):3            x+2/3y+1/3z=5/3                     (2с)-(1с)

x+y-z=0            ó                 x+y-z=0                      ó

4x-y+5z=3                                      4x-y+5z=3                  (3с)-(1с)*4

x+2/3y+1/3z=5/3                          (2с)*3 x+2/3y+1/3z=5/3 (3с)-(2с)*(-11/3)

1/3y-4/3z=-5/3                      ó      y - 4z = -5                       ó

-11/3y +11/3z=-11/3                    -11/3y +11/3z=-11/3        

x+2/3y+1/3z=5/3                     (3с):(-11)         x+2/3y+1/3z=5/3              

 y - 4z = -5                       ó                      y - 4z = -5        ó

 -11z=-22                                                        z=2

x+2/3y+1/3z=5/3                     x+2/3*3+1/3*2=5/3                     x=-1

 y-4*2=-5         ó      y=3                              ó      y=3

z=2                              z=2                                         z=2

Однако, следует указать недостаток МГ:

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

Для преодоления недостатка между шагами 1 и 2 вводят дополнительный шаг, заключающийся в выборе максимального из элементов a_i,i, a_i+1,i , a_i+2,i , … , a_n,i. После определения такого максимального элемента, находящегося в k-ой строке,  строчки I и k просто меняют местами. Введение дополнительного шага не сказывается на значениях переменных.

Пример 2.1 с устранением недостатка:

3x+2y+z=5      (1c)<->(3c)      4x-y+5z=3       (1c):4                    

x+y-z=0 ó                                 x+y-z=0            ó                          

4x-y+5z=3                                      3x+2y+z=5          

x-1/4y+5/4z=3/4            (2с)-(1с)           x-1/4y+5/4z=3/4 (2)<->(3)

x+y-z=0                      ó                      5/4y-9/4z=-3/4            ó

3x+2y+z=5                     (3с)-(1с)*3      11/4y -11/4z=11/4

x-1/4y+5/4z=3/4 (2с):(11/4)   x-1/4y+5/4z=3/4      (3с)-(2с)*(5/4)

11/4y -11/4z=11/4  ó            y - z=1                           ó

5/4y-9/4z=-3/4                           5/4y-9/4z=-3/4

x-1/4y+5/4z=3/4    (3): (-1)         x-1/4y+5/4z=3/4           x=-1

   y - z=1    ó                y-2=1                ó      y=3

        -z=-2                                   z=2                                   z=2

Как видно, решение в обоих случаях одинаковое.

В случае составления программы алгоритм следующий:

1. Для k от 1 до (n-1) выполнить следующее:
2. Для i от (k+1) до n выполнить следующее:
3.        
4.        
5.          Для j от (k+1) до n выполнить следующее:
6.               
7. Для k от n до 1 выполнить следующее:
8.  

Первые шесть шагов называются прямым ходом метода Гаусса, шаги 7-8- Обратным ходом Метода Гаусса.

Устранение недостатка МГ означает добавление в алгоритм между шагами 1 и 2следующие строчки:

Найти m>=k такое, чтобы |a_mk|=max{|a_ik|} при всех i>=k

Если |a_mk|<eps, то остановить работу (однозначного решения нет), иначе поменять местами b_k и b_m, a_kj и a_mj при k<=j<=n

Программа, написанная на языке Pascal, имеет вид:

Uses crt;

Const n1=10;

Var k,i,j,n:integer; sum:real;

l,a,a1:array[1..n1,1..n1] of real;

b,b1,x:array[1..n1] of real;

BEGIN

Write('n=');read(n);

{БЛОК ВЫВОДА МАТРИЦЫ A}

For i:=1 to n do

begin

For j:=1 to n do

           begin

                           writeln(‘введите a[',i,',',j,'] элемент');

                          readln(a[i,j]);

    end;

writeln('введите b[',i,'] элемент');

readln(b[i]);

end;

{БЛОК ПОКАЗА МАТРИЦЫ А НА ЭКРАНЕ}

writeln(исходная матрица А');

for i:=1 to n do

begin

for j:=1 to n do write(a[i,j],' ');

writeln;

end;

{ БЛОК НАХОЖДЕНИЯ МАТРИЦЫ А'=А1}

For k:=1 to n-1 do

For i:=k+1 to n do

  begin

           l[i,k]:=a[i,k]/a[k,k];

           b[i]:=b[i]-l[i,k]*b[k];

           for j:=k+1 to n do a[i,j]:=a[i,j]-l[i,k]*a[k,j];

  end;

For i:=1 to n do

For j:=1 to n do

           begin

           a1[i,j]:=a[i,j]/a[i,i];

           b1[i]:=b[i]/a[i,i];

           end;

{БЛОК ПОКАЗА МАТРИЦЫ А1 НА ЭКРАНЕ}

writeln('преобразованная матрица А');

For i:=1 to n do

begin

for j:=1 to n do write(a1[i,j],' ');

writeln;

end;

{БЛОК РАСЧЕТА МАТРИЦЫ X}

For k:=n downto 1 do

           begin

for j:=k+1 to n do sum:=sum+a1[k,j]*x[j];

x[k]:=b1[k]-sum; sum:=0;

end;

{БЛОК ВЫВОДА ПЕРЕМЕННЫХ НА ЭКРАН}

writeln('переменные равны:');

For i:=1 to n do writeln('x[',i,']=',x[i]);

Readln;

END.