Численное решение некоторых задач линейной алгебры
Работа из раздела: «
Математика»
/
/
Курсовая работа
по дисциплине «Вычислительная математика»
на тему: «Численное решение некоторых задач линейной алгебры»
Выполнил: Пупышев В.Д.
Глазов 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.
