Метод Гаусса

 

Содержание

Введение……………………………………………………………….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

          for j:=i+1 to n do

          begin

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

               a[j,i]:=0;

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

для просмотра  элементов,лежащих ниже диагонального}

               a[j,k]:=a[j,k]-c*a[i,k];

               b[j]:=b[j]-c*b[i];

          end;

          for i:= n downto 1 do

          begin

               for j:= i+1 to n do

               b[i]:=b[i]-a[i,j]*x[j];

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

          end;

          for i:= 1 to n do

          begin

               if x[i]<0 then

               begin

                    writeln('Корни уравнения,''X',i,'= ',x[i]:3:6);

                    writeln(rez,',Корни уравнения''X',i,'= ',x[i]:3:6);

               end

               else

               begin

                    writeln('Корни уравнения,''X',i,'= ',x[i]:3:6);

                    writeln(rez,'Корни уравнения,''X',i,'= ',x[i]:3:6);

               end;

          end;

end;

begin

clrscr;

assign(rez,'Gaus.dat');

rewrite(rez);

vvod(a,b);

vivod(a,b,rez);

Gaus(a,b,rez);

writeln;

writeln('Программу составил:');

writeln('Литвиненко Андрей Алексеевич');

writeln(rez);

writeln(rez,'Программу составил:');

writeln(rez,'Литвиненко Андрей Алексеевич');

readln;

close(rez);

end. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

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

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

+7*X1+2*X2+3*X3+6*X4= 93

+5*X1-6*X2+5*X3-9*X4= -77

-3*X1-6*X2-7*X3-7*X4= -101

-3*X1+4*X2+5*X3+2*X4= 21 
 

Корни уравнения,'X1= 5.000000

Корни уравнения,'X2= 5.000000

Корни уравнения,'X3= 0.000000

Корни уравнения,'X4= 8.000000 

Программу составил:

Литвиненко Андрей Алексеевич 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

 

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

     Program – оператор ввода заголовка программы.

     x_i – неизвестные;

     a_ij – коэффициенты при неизвестных;

     b_i – свободные члены в уравнениях;

     n – размерность;

     i – номера строк;

     j – номера столбцов;

     k – номер обнуляемого столбца;

     c – дополнительная переменная для переставления строк местами;

     ClrScr – процедура очистки экрана и возврата курсора в верхний левый угол.

     Var – зарезервированное слово, которое означает, что далее будут описаны одна или несколько переменных.

     Array [диапазон] of <тип данных> - массив. При описании массива используются зарезервированные слова Array и of (массив, из). За словом Array в квадратных скобках указывается диапазон, с помощью которого компилятор определяет общее число элементов массива. После слова of пишется тип данных, из которых будет состоять массив.

     Begin … End – составной оператор, указывающий на начало и конец программы или составляющей части программы. Именно в этом разделе происходят все действия. Фактически, весь раздел операторов, обрамленный словами Begin . . . End, представляет собой один составной оператор. Поскольку зарезервированное слово End является закрывающей операторной скобкой, оно одновременно указывает и конец предыдущего оператора.

     Writeln – с помощью этого оператора происходит ввод данных. После ввода происходит вывод данных на экран, и перевод курсора в начало следующей строки.

     Readln – оператор используется для вызова встроенной процедуры ввода данных, и программа останавливается в ожидании ввода. В этот момент необходимо набрать на клавиатуре нужное число и нажать клавишу Enter. Сразу после этого программа продолжит работу: проанализирует введенное число и перейдет к вводу следующего числа или вычислению результата. Таким образом, сигналом окончания подготовки очередного числа является нажатие на клавишу Enter, до этого момента можно стирать любой ошибочно введенный символ клавишей Backspace.

     := (знак присваивания) – один из основных операторов. Пара символов «:=» означает «присвоить значение». Из толкования смысла оператора видно, что он используется для присваивания символу какого-либо значения, которое может быть выражено как набором символов, так и математическим выражением.

     If <условие> then <оператор1> else <оператор2> – составной оператор, позволяющий проверить некоторое условие и в зависимости от результатов проверки выполнить то или иное действие. If, then, else - зарезервированные слова (если, то, иначе); <условие> - произвольное выражение логического типа; <оператор1>, <оператор2> - любые операторы языка Turbo Pascal. Условный оператор работает по следующему алгоритму. Вначале вычисляется условное выражение <условие>.

     Если  результат есть TRUE (истина), то выполняется <оператор1>, а <оператор2> пропускается; если результат есть FALSE (ложь), наоборот, <оператор1> пропускается, а выполняется <оператор2>.

     For <пар_цик> := <нач_знач> to <кон_знач> do <оператор> - составной оператор. Здесь for, to, do - зарезервированные слова (для, до, выполнить);

     <пар_цик> - параметр цикла - переменная типа integer;

     <нач_знач> - начальное значение - выражение того же типа;

      <кон_знач> - конечное значение - выражение того же типа; 

     <оператор> - произвольный оператор Borland Pascal.

При выполнении оператора For вначале вычисляется выражение <нач_знач> и осуществляется присваивание <пар_цик>: = <нач_знач>. После этого циклически повторяется:

1. проверка условия <пар_цик> <= <кон_знач>; если условие не выполнено, оператор For завершает свою работу;
2. выполнение оператора <оператор>;
3. наращивание переменной <пар_цик> на единицу.

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

 

 
 

     Заключение

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

     Работа  выполнена на языке Turbo Pascal фирмы Borland, прочно вошедшем в мир программирования в 1983 году и до сих пор являющимся удобным языком программирования для начинающих программистов, а также просто хорошим языком программирования, к которому обращаются как прикладные программисты, так и системные. Однако, при необходимости, данная программа может быть легко переписана на любой другой современный язык программирования.

     Выполнение  курсовой работы позволило углубить знания и расширить навыки по разработке алгоритмов и их реализации на персональном компьютере. 
 
 
 
 
 
 
 
 
 
 
 
 
 

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

1. Ильин В. А., Позняк Э. Г. Линейная алгебра: Учебник  для вузов/6-е изд., стер. – М.: ФИЗМАТЛИТ, 2004. – 280 с.
2. Кассера В.Ф. Turbo Pascal 7.0. – Диасофт, 2003. – 345 с.
3. Кремер Н.Ш. Высшая математика для экономистов: учебник для студентов вузов/3-е издание. – М.:ЮНИТИ-ДАНА,2006. – 471 с.
4. Культин Н.Б. Turbo Pascal в задачах и примерах. – СПб:БХВ – Петербург, 2002. – 256с.: ил.
5. Моргун А. Н. Программирование на языке Паскаль (Pascal). Основы обработки структур данных. – М.: Диалектика, 2006. – 608 с.
6. Фаронов В.В. Turbo Pascal. Наиболее полное руководство. – BHV-Санкт-Петербург, 2007. – 571 с.
7. http://ru.wikipedia.org/wiki/Turbo_Pascal