Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Курсовая работа

по дисциплине «Вычислительная математика»

на тему: «Численное решение некоторых задач линейной алгебры»

Выполнил: Пупышев В.Д.

Глазов 2012 г.



Содержание

Введение

1. Теоретическая часть

1.1 Вычисление точного значения определителей

1.2 Нахождение обратной матрицы методом Гаусса

2. Практическая часть

2.1 Вычисление определителей

2.2 Пример нахождения обратной матрицы

Заключение

Список литературы

Приложения



Введение

Линейная алгебра - часть алгебры, изучающая векторные (линейные) пространства и их подпространства, линейные отображения (операторы), линейные, билинейные, и квадратичные функции на векторных пространствах.

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

Наиболее важными являются задачи линейной алгебры - вычисление определителя, обратной матрицы, собственных значений и др.

Целями работы являются:

· изучить методы нахождения определителя и обратной матрицы методом Гаусса;

· разработать вычислительный алгоритм в программе Pascal ABC для вычисления определителей и для нахождения обратной матрицы.



1. Теоретическая часть

1.1 Вычисление точного значения определителей

Вычисление определителей основывается на их известных свойствах, которые относятся к определителям всех порядков. Вот эти свойства:

1. Если переставить две строки (или два столбца) определителя, то определитель изменит знак.

2. Если соответствующие элементы двух столбцов (или двух строк) определителя равны или пропорциональны, то определитель равен нулю.

3. Значение определителя не изменится, если поменять местами строки и столбцы, сохранив их порядок.

4. Если все элементы какой-либо строки (или столбца) имеют общий множитель, то его можно вынести за знак определителя.

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

6. Определитель второго порядка вычисляется по формуле

7. Определитель третьего порядка вычисляется по формуле



Существует удобная схема для вычисления определителя третьего порядка (см. рис. 1 и рис. 2).

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

В определителе порядка n алгебраическим дополнением элемента, стоящего на пересечении k-го столбца и l-й строки, называется определитель порядка (n - 1), получаемый из данного вычеркиванием в нем строки и столбца, на пересечении которых стоит этот элемент, причем к этому определителю присоединяется множитель (-1)k+l, где (k + l) - сумма номеров вычеркнутой строки и столбца. Алгебраическое дополнение элемента, рассматриваемое без множителя (-1)k+l, называется минором этого элемента.

8. Теорема Лапласа.

Определитель равен сумме произведений каждого элемента некоторой строки (или столбца) на его алгебраическое дополнение.

Условимся обозначать элементы определителя маленькими буквами, а их алгебраические дополнения - соответствующими большими буквами с теми же индексами. Так, как алгебраическое дополнение элемента a3 будем обозначать через A3, алгебраическое дополнение элемента d4 - через D4 и т. д. На основании свойства 8 определитель (3) может быть представлен, например, в таком виде:

D = a3A3 + b3B3 + c3C3 + d3D3 + e3E3

Это равенство представляет собой разложение определителя по элементам третьей строки. По свойству 8 вычисление определителя порядка n сводится к вычислению определителей порядка (n - 1).

9. Если все элементы какого-нибудь ряда определителя, кроме одного, равны нулю, то определитель равен этому не равному нулю элементу, умноженному на его алгебраическое дополнение.

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

1.2 Нахождение обратной матрицы методом Гаусса

линейный алгебра гаусс матрица определитель

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

Теорема:

Пусть А квадратная невырожденная матрица. Если матрица (А | E) приведена с помощью элементарных преобразований строк к виду (Е | A-1), где Е - единичная матрица того же порядка, что и матрица А.

Из теоремы следует метод нахождения обратной матрицы методом Гаусса:

1) к матрице А приписать справа единичную матрицу Е той же размерности;

2) путем преобразований методом Гаусса над строками расширенной матрицы (А | E) матрица А приводится к единичной матрице;

3) в результате вычислительного процесса на месте приписанной справа матрицы Е получится обратная матрица A-1.

Схематично процесс нахождения обратной матрицы выглядит следующим образом: (А | E) (E | A-1).



2. Практическая часть

2.1 Вычисление определителей

Пример 1: Вычислить определитель:

1)

Решение:

С помощью формулы (правило треугольника):

Получаем:

= 1*2*2 + 0*5*1 + 3*1*4 - 4*2*5 - 0*3*2 - 1*1*1 = -25

С помощью программы (см. Приложение, п.1):



2.2 Пример нахождения обратной матрицы

2. Элементы первой строки умножим на (- 3) прибавим соответственно к элементам второй строки, получим . Затем элементы второй строки прибавим соответственно к элементам первой строки, получим . При выполнении следующего преобразования элементы второй строки умножим на (-1/2). В результате получим матрицу .

3. Итак, обратная матрица имеет вид A-1 = .

С помощью программы найдём обратную матрицу методом Гаусса (см. Приложение, п. 1):



Заключение

В процессе создания курсовой работы было сделано следующее:

1) Изучили методы нахождения определителя и обратной матрицы применяемых при численном решении некоторых задач линейной алгебры.

2) Разработали вычислительный алгоритм в программе Pascal ABC для вычисления определителей и для нахождения обратной матрицы.

3) Решены задачи линейной алгебры и сравнили результаты.

В результате проделанной работы можно сделать следующие выводы: легко вычисляются лишь определители невысоких порядков и некоторые специальные типы определителей. Непосредственное нахождение определителя требует большого объема вычислений. Можно подсчитать время вычисления определителей на ЭВМ с заданным быстродействием. Примем для определенности среднее быстродействие равным 100 000 операций в секунду. Тогда для вычисления определителя 10-го порядка потребуется около 6 мин, а при n = 20 - около 1,4*1011 ч, т.е. свыше 5*109 сут. Приведенные оценки указывают на необходимость разработки и использования экономичных численных методов, позволяющих эффективно проводить вычисления определителей.



Литература

1. Пантина И.В., Синчуков. А.В. - 2-е изд., перераб. и доп. - М.: Московский финансово-промышленный университет «Синерия», 2012. - 176 с. (Университетская серия).

2. Турчак Л.И. Основы численных методов: Учеб. пособие. - М.: Наука. Гл. ред. Физ.-мат. Лит., 1987. - 320 с.

3. Электронный ресурс. Определители и системы линейных алгебраических уравнений. [http://www.pm298.ru/reshenie/opredel.php] 10.12.2012

4. Электронный ресурс. Обратная матрица. Нахождение обратной матрицы методом алгебраических дополнений.



Приложение 1

Программый код для вычисления определителей.

program Opredelitel;

uses crt;

const

N1 = 10;

type

Matrice = array[1..N1, 1..N1] of real;

var

A: matrice;

I, J, N: integer;

D: real;

function Det(A: Matrice; N: integer): real;

var

B: matrice;

I: integer;

T, Mn, S: real;

function Minor(var C: matrice; A: Matrice; N, I, J: integer): real;

var

Im, Jm, Ia, Ja, Nm: integer;

begin

Nm := N - 1; Im := 1; Ia := 1;

while Im <= Nm do

if Ia <> I then

begin

Jm := 1; Ja := 1;

while Jm <= Nm do

if Ja <> J then

begin

C[Im, Jm] := A[Ia, Ja];

Ja := Ja + 1; Jm := Jm + 1;

end

else Ja := Ja + 1;

Ia := Ia + 1; Im := Im + 1;

end

else Ia := Ia + 1;

end; {*Minor*}

begin

if N = 1 then Det := A[N, N];

if N = 2 then Det := A[1, 1] * A[2, 2] - A[2, 1] * A[1, 2];

if N > 2 then

begin

S := 0;

for I := 1 to N do

begin

Mn := Minor(B, A, N, I, 1);

if (I mod 2) = 1 then begin

T := Det(B, N - 1);

S := S + T * A[I, 1];

end

else begin

T := Det(B, N - 1);

S := S - T * A[I, 1];

end;

end;

Det := S;

end;

end; {*Determ*}

begin

Write('Введите порядок матрицы N: '); readln(N);

for I := 1 to N do

begin

writeln('Введите элементы строки ', I: 2);

for J := 1 to N do readln(A[I, J]);

end;

D := Det(A, N);

Writeln('Определитель равен: ', D: 7: 4);

readln;

end.



Приложение 2

Программый код для нахождения обратной матрицы.

program Gayss;

uses crt;

const

n=2;

eps = 0.000000001; { all numbers less than eps are equal 0 }

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

var

a,b,a0:matr;

i,j,imx,np:integer;

s0,s1:real;

procedure PrintMatr(m,m1:matr;n,nz,nd:integer);

var

i,j:integer;

begin

for i:=1 to n do

begin

if (i=1) then write(np:2,':') else write(' ');

for j:=1 to n do write(m[i,j]:nz:nd);

for j:=1 to n do write(m1[i,j]:nz:nd);

writeln;

end;

inc(np);

end;

procedure MultString(var a,b:matr;i1:integer;r:real);

var

j:integer;

begin

for j:=1 to n do

begin

a[i1,j]:=a[i1,j]*r;

b[i1,j]:=b[i1,j]*r;

end;

end;

procedure AddStrings(var a,b:matr;i1,i2:integer;r:real);

{ процедура прибавляет к i1 строке матрицы а 2i-ю умноженную на r}

var

j:integer;

begin

for j:=1 to n do

begin

a[i1,j]:=a[i1,j]+r*a[i2,j];

b[i1,j]:=b[i1,j]+r*b[i2,j];

end;

end;

procedure MultMatr(a,b:matr;var c:matr);

var

i,j,k:byte;

s:real;

begin

for i:=1 to n do

for j:=1 to n do

begin

s:=0;

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

c[i,j]:=s;

end;

end;

function sign(r:real):shortint;

begin

if (r>=0) then sign:=1 else sign:=-1;

end;

{MAIN}

begin

randomize;

for i:=1 to n do

begin

for j:=1 to n do

begin

b[i,j]:=0;

a[i,j]:=1.0*random(8)-4;

end;

b[i,i]:=1;

end;

{ отладочные присвоения}

a[1,1]:= 1; a[1,2]:= 2; {a[1,3]:=4; a[1,4]:= 0;}

a[2,1]:= 3; a[2,2]:= 4; {a[2,3]:=4; a[2,4]:= 5;

a[3,1]:= 4; a[3,2]:= 5; a[3,3]:=6; a[3,4]:= 2;

a[4,1]:= 0; a[4,2]:=-2; a[4,3]:= 3; a[4,4]:=-4;

a[1,1]:= 5; a[1,2]:= 7; a[1,3]:= 7; a[1,4]:= 1;

a[2,1]:= 6; a[2,2]:= 6; a[2,3]:= 3; a[2,4]:= 4;

a[3,1]:= 5; a[3,2]:= 1; a[3,3]:= 1; a[3,4]:= 1;

a[4,1]:= 3; a[4,2]:= 3; a[4,3]:= 3; a[4,4]:= 3;

for i:=1 to n do

for j:=1 to n do a0[i,j]:=a[i,j];

writeln('Начальная матрица:'); np:=0;

PrintMatr(a,b,n,6,1);

for i:=1 to n do

begin

for j:=i+1 to n do AddStrings(a,b,i,j,sign(a[i,i])*sign(a[j,i]));

{ PrintMatr(a,b,n,6,1);}

if (abs(a[i,i])>eps) then

begin

MultString(a,b,i,1/a[i,i]);

for j:=i+1 to n do AddStrings(a,b,j,i,-a[j,i]);

{ PrintMatr(a,b,n,6,1);}

end else

begin

writeln('Обратной матрицы не существует.');

halt;

end

end;

{writeln('Обратный ход:');}

if (a[n,n]>eps) then

begin

for i:=n downto 1 do for j:=1 to i-1 do

begin

AddStrings(a,b,j,i,-a[j,i]);

end;

{ PrintMatr(a,b,n,8,4);}

end else writeln('Обратной матрицы не существует.');

MultMatr(a0,b,a);

writeln('Начальная матрица. Обратная к ней матрица.:');

PrintMatr(a0,b,n,7,3);

writeln('Проверка: должна быть единичная матрица.');

PrintMatr(a,a,n,7,3);

end.

Размещено на Allbest.ru