Метод Гаусса

 

Содержание

Введение……………………………………………………………….3

1. Постановка задачи…………………………………….....................4

2.Алгоритм решения  СЛАУ методом Гаусса……………………….6

    2.1. Описание алгоритма решения СЛАУ методом Гаусса……...6

    2.2. Блок-схема алгоритма…………………………………………9

3.Практическая  реализация  задачи……………………....................10

    3.1.Программа……………………………………………………...10

    3.2.Результат программы………………………………………….13

    3.3. Описание используемых операторов………………………...14

Заключение……………………………………………………………17

Список использованной литературы………………………………...18 
 

 

 

Введение 

     Численные методы являются одним из мощных математических средств решения задачи. Простейшие численные методы мы используем всюду, например, извлекая квадратный корень на листке бумаги. Есть задачи, где без  достаточно сложных численных методов  не удалось бы получить ответа; классический пример – открытие Нептуна по аномалиям  движения Урана.

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

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

     Одним из самых распространенных методов  решения систем линейных уравнений  является метод Гаусса - Зейделя. Этот метод (который также называют методом  последовательного замещения неизвестных) известен в различных вариантах  уже более 2000 лет. 

 

1. Постановка  задачи 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

 

     

     2.Алгоритм  решения СЛАУ методом Гаусса

     2.1.Описание алгоритма решения СЛАУ методом Гаусса 

     Пусть у нас есть система N линейных уравнений:

     a₁₁x₁ + a₁₂x₂ + a₁₃x₃ + ... a_1Nx_N = b₁

     a₂₁x₁ + a₂₂x₂ + a₂₃x₃ + ... a_2Nx_N = b₂

     a₃₁x₁ + a₃₂x₂ + a₃₃x₃ + ... a_3Nx_N = b₃

     ...         …         …       …        …

     a_N1x₁ + a_N2x₂ + a_N3x₃ + ... a_NNx_N = b_N 

     где x_i - неизвестные, a_ij - коэффициенты при неизвестных, b_i - свободные члены в уравнениях, i,j пробегают значения от 1 до N.

     Цель  задачи - зная a_ij и b_i найти x_i.

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

 

     Особенность этой системы - в строках с номером i все коэффициенты a_ij при j<i равны нулю.

     Если  мы смогли привести нашу систему уравнений  к такому треугольному виду, то решить уравнения уже просто. Из последнего уравнения находим x_N= b_N / a_NN. Дальше подставляем его в предпоследнее уравнение и находим из него x_N-1. Подставляем оба найденных решения в следующее с конца уравнение и находим x_N-2. И так далее, пока не найдем x₁, на чем решение заканчивается. Такая процедура называется обратной прогонкой.

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

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

     Нужно, чтобы во второй строке получилось уравнение, в которой отсутствует  член при x₁. Прибавим к этой строке первую строку, умноженную на некоторое число M. 

     (a₁₁x₁ + a₁₂x₂ + a₁₃x₃ + ... a_1Nx_N = b₁)*M +

     a₂₁x₁ + a₂₂x₂ + a₂₃x₃ + ... a_2Nx_N = b₂ 

     Получим

      

     (a₁₁*М + a₂₁) x₁ + ... = b₁*M + b₂ 

     Для того, чтобы член при x₁ равнялся нулю, нужно, чтобы M = - a₂₁ / a₁₁. Проделав эту операцию, получившееся уравнение запишем вместо второго и приступим к третьему уравнению. К нему мы прибавим первое уравнение, умноженное на M = - a₃₁ / a₁₁ и тоже получим ноль вместо члена при x₁. Такую операцию нужно проделать над всеми остальными уравнениями. В результате получим систему такого вида:

 

     

 

     После этого будем избавляться от членов при x₂ в третьем, четвертом, N-ом уравнении. Для этого нужно к уравнению с j-м номером прибавить 2-ое уравнение, умноженное на M = - a_j2 / a₂₂. Проделав эту операцию над всеми остальными уравнениями, получим систему где нет членов с x₂ в уравнениях с номером больше 2.

     И так далее... Проделав это для третьего члена, четвертого... до тех пор, пока не кончатся уравнения, получим в  итоге систему треугольного вида.

     Из  системы уравнений последовательно  можно найти значение всех неизвестных. Из последнего уравнения находим X_n=b_n^(n-1)/a_nn^(n-1).

     Подставляя  Х_n в предпоследние  уравнение, найдем X_n-1 и т.д., до Х1 которое определяется из первого уравнения системы, когда уже известны                 

X_n ,X_n-1 … ,X2. Таким образом,по методу Гаусса на первом этапе, называемом прямым ходом, исходную систему преобразуют в эквивалентную с треугольной матрицей, а на втором этапе называемым обратным ходом, вычисляют неизвестные, решая эквивалентную систему. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

2.2.Блок-схема алгоритма 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

 

3.Практическая  реализация  задачи.

3.1.Программа 
 

program Gauss;

uses crt;

const n=4;

type mas1=array[1..n,1..n] of real;

     mas2=array[1..n] of real;

     mas3=array[1..n] of real;

     var a:mas1;

         b:mas2;

rez:text;

    {Процедура  ввода расширенной матрицы системы}

procedure vvod(var a:mas1; var b:mas2);

          var i,j:integer;

          begin

          for i:= 1 to n do {Открываем внешний цикл по номеру строки}

          begin

               for j:= 1 to n do {Открываем внутрений цикл по номеру

               столбца}

               begin

               write('X[',i,',',j,']= '); {Вводим значение коэффициентов

               при неизвестных}

               read(a[i,j]);

               end;

               write('‚',i,'= ');

               readln(b[i]); {Вводим значение свободного члена}

          end;

end;

     {Процедура  вывода результатов}

procedure vivod(var a:mas1; var b:mas2; var f:text);

          var i,j:integer;

          begin

          writeln('Система линейных алгебраических уравнений:');

          writeln(rez,'Система линейных алгебраических уравнений:');

          for i:= 1 to n do

          begin

               for j:= 1 to n do

               begin

                    if a[i,j]<0 then

                    begin

                         write('-',a[i,j]* -1:1:0,'*X',j);

                         write(rez,'-',a[i,j]* -1:1:0,'*X',j);

                    end

                    else

                    begin

                         write('+',a[i,j]:1:0,'*X',j);

                         write(rez,'+',a[i,j]:1:0,'*X',j);

                    end;

               end;

               write('= ',b[i]:1:0);

               writeln;

               write(rez,'= ',b[i]:1:0);

               writeln(rez);

          end;

          writeln;

          writeln(rez);

end;

           {Процедура,реализующая метод Гаусса-Зейделя}

procedure Gaus(var a:mas1; var b:mas2; var f:text);

          var i,j,k:integer;

              c:real;

              X:mas3;

          begin

          for i:= 1 to n-1 do