Remkomplekty.ru

IT Новости из мира ПК
27 просмотров
Рейтинг статьи
1 звезда2 звезды3 звезды4 звезды5 звезд
Загрузка...

Обратная матрица методом гаусса паскаль

Turbo Pascal Examples

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

В первой программе используется псевдо-метод Гаусса. Известно, что если к матрице приписать справа единичную матрицу, а затем с помощью линейных преобразований привести левую матрицу к единичной, проводя те же преобразования над правой (изначально единичной) матрицей, то на ее месте образуется матрица, обратная к исходной. К линейным преобразованиям относятся прибавление одной строки, умноженной на произвольный коэффициент, к другой. Решение можно разбить на два этапа: «прямой» и «обратный» ход.
Есть исходная матрица, приписываем к ней единичную:
а[1,1], а[1,2], . а[1,n]; 1, 0, . 0;
а[2,1], а[2,2], . а[2,n]; 0, 1, . 0;
.
а[n,1], а[n,2], . а[n,n]; 0, 0, . 1;
Во время «прямого» хода необходимо добиться нулей под главной диаганалью левой матрицы. Берем первую строку и делим ее на а[1,1]. Теперь на месте а[1,1] стоит 1. Вычитаем из второй строки первую умноженную на а[2,1] — на месте этого эл-та образуется ноль. Аналогично для всех строк до n-ной. Теперь в первом столбце матрицы ниже единицы стоят нули.
Переходим ко второй строке и для всех строк ниже второй повторям описанную процедуру. Теперь ниже диагонали и во второй строке нули. Так продолжаем до (n-1)-ой строки. Для n-ной строки достаточно разделить ее на а[n,n]. Матрица а приведена к верхней треугольной. На месте единичной образовалась некая матрица.
Примечание 1. Если на месте диагонального элемента левой матрицы образуется число близкое к нулю, то деление на малое число приведет к значительной погрешности вычисления. Поэтому необходимо, чтобы это число было «далеко» от нуля. С этой целью предпринимается следующий шаг: перед тем, как разделить строку на этот элемент, прибавим к строке все нижележащие строки (умноженные на -1 если в этом столбце стоит отрицательный элемент).
Обратный ход. Здесь сначала добвиваемся нулей в последнем столбце матрицы а. Для этого из каждой строки (i) выше n-ной вычитаем n-ную умноженную на а[i,n]. Затем добиваемся нулей в (n-1)-ом столбце и так далее до второго столбца.
Все. Теперь слева имеем единичную матрицу, а справа, на месте единичной — искомая обратная матрица. Для проверки перемножим ее на начальную — должна получиться единичная.

const n=5;
eps=0.00001; < 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 строке матрицы a i2-ю умноженную на 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;
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]:= 3; a[1,2]:=-1; a[1,3]:= 2; a[1,4]:= 0;
a[2,1]:=-2; a[2,2]:= 1; a[2,3]:= 0; a[2,4]:= 5;
a[3,1]:= 1; a[3,2]:= 4; a[3,3]:=-2; 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(‘Starting matrix:’); np:=0;
PrintMatr(a,b,n,6,1);
for i:=1 to n do
begin
< К i-той строке прибавляем (или вычитаем) j-тую строку
взятую со знаком i-того элемента j-той строки. Таким образом,
на месте элемента a[i,i] возникает сумма модулей элементов i-того
столбца (ниже i-той строки) взятая со знаком бывшего элемента a[i,i],
равенство нулю которой говорит о несуществовании обратной матрицы >
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;

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);
< Выполним еще проверку насколько полученная проверочная матрица
близка к единичной. Сложим отдельно суммы модулей диагональных
и недиагональных элементов. По диагонали должно быть n, а не по
диагонали 0 >
s0:=0; s1:=0;
for i:=1 to n do
for j:=1 to n do
if (i=j) then s1:=s1+abs(a[i,j])
else s0:=s0+abs(a[i,j]);
writeln(‘Сумма модулей диагональных элементов: ‘,s1);
writeln(‘Сумма модулей недиагональных эл-тов : ‘,s0);
end.

Примечание 2. При решении систем линейных уравнений методом Гаусса используют так называемый метод «выбора ведущего элемента». Необходимость его обусловлена теми же причинами, что описаны в Примечании 1 — близостью к нулю одного из диагональных элементов. Только если в вышеизложенном примере использовалось прибавление к строке «нижнележащих» строк, то выбор ведущего элемента подразумевает перестановку строк в матрице таким образом, чтобы на месте диагонального элемента была строка с максимальным по модулю значением. На практике при решении систем линейных уравнений эта операция означает лишь перестановку уравнений в системе и не влияет на решение. Однако при нахождении обратной матрицы, казалось бы, так поступать нельзя — ведь будет изменен порядок следования строк. Тогда в конце нужно вернуть первоначальный порядок и все должно быть нормально. Практика показала, что это не совсем так. Первоначально когда писалась программа, порядок строк не восстанавливался. Проверка показала, что искомая матрица найдена. Попытки привести строки матрицы в первоначальный порядок, привели к неправильному решению. А вот если порядок не восстанавливать, то решение оказывается правильным. Может кто-нибудь объяснит, почему так происходит?

Читать еще:  Библиотеки си шарп

const n=4;
eps=0.00001; < all numbers less than eps are equal 0 >
type matr=array[1..n,1..n] of real;
vect=array[1..n] of byte;
var a,b,a0:matr;
v:vect;
i,j,imx,np:integer;
max_v,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(v[i]:nz);
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 строке матрицы a i2-ю умноженную на 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;
procedure SwapRows(var a,b:matr;var v:vect;n,imx,i:integer);
var j,ti:byte;
tr:real;
begin
for j:=1 to n do
begin
tr:=a[imx,j]; a[imx,j]:=a[i,j]; a[i,j]:=tr;
tr:=b[imx,j]; b[imx,j]:=b[i,j]; b[i,j]:=tr;
end;
ti:=v[imx]; v[imx]:=v[i]; v[i]:=ti;
end;
begin
randomize;
for i:=1 to n do
begin
for j:=1 to n do
begin
b[i,j]:=0;
a[i,j]:=random(8);
end;
b[i,i]:=1;
v[i]:=i;
end;
<
a[1,1]:= 3; a[1,2]:=-1; a[1,3]:= 2; a[1,4]:= 0;
a[2,1]:=-2; a[2,2]:= 1; a[2,3]:= 0; a[2,4]:= 5;
a[3,1]:= 1; a[3,2]:= 4; a[3,3]:=-2; 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(‘Starting matrix:’); np:=0;
PrintMatr(a,b,n,6,1);
for i:=1 to n do
begin
< Выбор ведущего элемента >
imx:=i; max_v:=abs(a[imx,i]);
for j:=i+1 to n do
if (abs(a[j,i])>max_v) then
begin
max_v:=abs(a[j,i]);
imx:=j;
end;
< PrintMatr(a,b,n,6,1);>
if (imx<>i) then
SwapRows(a,b,v,n,imx,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;
end;
writeln(‘Returning move:’);
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(‘Matrix doesn»t exists.’);
< return rows order >
if (v[i]<>i) then
SwapRows(a,b,v,n,v[i],i);>
MultMatr(a0,b,a);
writeln(‘Starting matrix, result:’);
PrintMatr(a0,b,n,8,4);
writeln(‘check:’);
PrintMatr(a,a,n,8,5);
s0:=0; s1:=0;
for i:=1 to n do
for j:=1 to n do
if (i=j) then s1:=s1+abs(a[i,j])
else s0:=s0+abs(a[i,j]);
writeln(‘Diagonal summ:’,s1,’ Not diagonal summ:’,s0);
end.

Программирование метода Гаусса на языке Pascal

Если система линейных уравнений совместна (т.е. имеющая решения), то схема программы её решения можно записать так:

· Ввести коэффициенты и правые части уравнений;

· Выполнить прямой ход;

· Выполнить обратный ход;

При прямом ходе нужно: получить первое уравнение в виде, удобном для исключения , разделив полученное 1-е уравнение на коэффициент при ; исключить из уравнений с номерами 2, 3, …,n; получить второе уравнение в виде, удобном для исключения ; исключить из уравнений с номерами 3, …,n; получить n–1 уравнение в виде, удобном для получения ; исключить из уравнения с номером n.

Запишем схему программы этого фрагмента :

Получить i-е уравнение в виде, удобном для исключения : исключить из уравнений с номерами i + 1, …, nс помощью i-го уравнения

При обратном ходе из последнего уравнения находят Используя это значение, из предпоследнего n˗1 уравнения исключают и получают . Найденные значения переменных , , …, позволяют вычислить .

Детализируем этап обратного хода.

получить ;

for i:= n˗1 downto 1 do вычислить ;

вывести , …,

Опираясь на разработанные схемы, запишем программу решенияnлинейных уравнений с nпеременными методом Гаусса в предположении, что система совместна ( n

Найти обратную матрицу (Pascal)

Вообщем задача состоит в том, что надо найти обратную матрицу, по следующему алгоритму:
1. Разбиваем матрицу на 2 треугольные
2. Находим обратные матрицы к треугольным и перемножаем их (должны получить обратную матрицу к той что нам дана)
3. Проверка.

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

13 ответов

Не помню что такое «с алгебраическими дополнениями», но припоминается что можно привести ее к треугольному виду (ето не то что разбить на 2 треугольние, а так чтоб все что под диагоналю было равно 0), а потом перемножыть елементы диагонали.

ЗЫ. ИМХО. А прежний аватар красивее был.

когда я тестирую, вроде все нормально, но когда матрица 2х2 (порядок равен 2), то определитель что-то не считается:confused: не могу найти ошибку, помогите пожалуйста.

(Может не совсем будет роботать потому что я прямо тут и набрал с копипейстом.)

Твоя ошибка в том что после первого ифа надо было остальное в елсе взять. Но ето машинально.
А теперь концептуально. Видиш, у тебя вычисление для н=2 делается два раза (в ифе и после цыкла). Старайся избегать таких ситуаций.

Извени, но помойму я тебе не так подсказал сам метод. Я тут на бумажке пробую и не получается у меня так посчитать. Пошел учить матчасть.

PS Ето у меня руки кривые на бумажке считать, таки правильно сказал. Ложная тривога.
Завтра покажу как без вспомагательной mat11 обойтись. Сегодня не успеваю.

type
Tmatr = array[1..NMAX, 1..NMAX] of real;

const
mat: Tmatr = ((8, 4, 9, 2),
(3, 7, 4, 5),
(3, 6, 9, 8),
(1, 1, 4, 1));

var
mat1: Tmatr;
n, i, j, k, current: integer;
det, buf: real;

BEGIN
mat1 := mat;
n := 4;
det:=1;
current := 1;
while(n > current) do
begin
if mat1[current, current]=0 then
begin
k:=0;
for i:=current to n do
if mat1[i,current] <> 0 then k:=i;
if k=0 then
begin
det:=0;
break;
end;
for j:=current to n do
begin
buf:=mat1[current,j];
mat1[current,j]:=mat1[k,j];
mat1[k,j]:=buf;
end;
det:=(-1)*det;
end;
for i:=current+1 to n do
begin
buf := mat1[i, current] / mat1[current, current];
for j:=current to n do
mat1[i,j]:=mat1[i,j]-buf*mat1[current,j];
end;
current := current + 1;
end;
for i := 1 to n do
det := det * mat1[i,i];
for i := 1 to n do
begin
for j := 1 to n do
write(mat1[i,j]:10:3, ‘, ‘);
writeln;
end;
writeln(‘det=’,det:8:3);
end.

Читать еще:  Ввод массива через процедуру паскаль

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

Замечание тебе
1.

Условие лутше ставить перед обменом местами строк. Кроме того при к=0 нужно прекращать приведение матрицы, а тто потом сразу деление на 0 вылезет.

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

type
Tmatr = array[1..NMAX, 1..NMAX] of real;

const
mat: Tmatr = ((8, 4, 9, 2),
(3, 7, 4, 5),
(3, 6, 9, 8),
(1, 1, 4, 1));

3. Не обязательно роботать через елемент [1,1]. Сделaл через current. Так у тебя остается неиспорченая матрица. (Выводится в конце).

4. Можно убрать вспомагательную матрицу и делать все на одной.

5. Убрал проверку на розмер матрицы ровный 2. Ето конечно лишняя итерацыя цыкла, но мое мнение что надо стараться делать код более универсальным. Тоесть чтоб он обрабатывал любые входные данные одинаково. Так снижается вероятность ошибок. В етом ты уже сам убедился. 🙂

6. Основное замечание. Индексируй масивы с нуля. Ето секономит тебе кучу времени и нервов когда начнеш писать на Си подобных языках.

Надеюсь мой код будет тебе полезным.

procedure output_matrix(n:integer;mat:mat1);<Вывод матрицы>
var i,j:integer;
begin
for i:=1 to n do
begin
for j:=1 to n do
begin
write(mat[i,j]:5:5);
write(‘ ‘);
end;
writeln;
end;
writeln;
end;

procedure bermuda(var nt,vt,d:mat1; n:integer);<Разбиение матрицы на 2 треугольные>
var i,j,k:integer;
s:real;
begin
for i:=1 to n do
begin
nt[i,1]:=d[i,1];
vt[i,1]:=0;
end;
for j:=1 to n do
begin
vt[1,j]:=d[1,j]/nt[1,1];
if j>1 then nt[1,j]:=0;
end;
for i:=2 to n do
for j:=2 to n do
begin
if i>=j then
begin
s:=0;
for k:=1 to j-1 do
s:=s+nt[i,k]*vt[k,j];
nt[i,j]:=d[i,j]-s;
vt[i,j]:=0;
if i=j then vt[i,j]:=1;
end
else
begin
s:=0;
for k:=1 to i-1 do
s:=s+nt[i,k]*vt[k,j];
vt[i,j]:=(d[i,j]-s)/nt[i,i];
nt[i,j]:=0;
end;
end;
end;

procedure ont(n:integer; var mat,obnt:mat1);<нахождение обратной нижней треугольной матрицы>
var i,j,a:integer;
s:real;
begin
for i:=1 to n do
begin
for j:=1 to n do
begin
if i=j then obnt[i,j]:=1/mat[i,j];
if i j then
begin
s:=0;
for a:=j to i-1 do
begin
s:=s+mat[i,a]*obnt[a,j];
obnt[i,j]:=-1*s/mat[i,i];
end;
end;
end;
end;
end;

procedure ovt(n:integer; var mat,obvt:mat1);<нахождение обратной верхней треугольной матрицы>
var i,j,a:integer;
s:real;
begin
for i:=n downto 1 do
begin
for j:=1 to n do
begin
if i>=j then obvt[i,j]:=mat[i,j];
if j=i+1 then obvt[i,j]:=-mat[i,j];
if j>i+1 then
begin
s:=0;
for a:=i+1 to j-1 do
begin
s:=s+mat[i,a]*obvt[a,j];
obvt[i,j]:=-1*(mat[i,j]+s);
end;
end;
end;
end;
end;

procedure multi_matrix(n:integer; m1,m2:mat1; var mm:mat1);<произведение матриц>
var i,j,a:integer;
x:real;
begin
for i:=1 to n do
for j:=1 to n do
begin
x:=0;
for a:=1 to n do x:=x+m1[i,a]*m2[a,j];
mm[i,j]:=x;
end;
end;
end.

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

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

Задачи и методы линейной алгебры. Свойства определителей и порядок их вычисления. Нахождение обратной матрицы методом Гаусса. Разработка вычислительного алгоритма в программе Pascal ABC для вычисления определителей и нахождения обратной матрицы.

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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).

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

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

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

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

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


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

Программирование метода Гаусса на языке Pascal

Если система линейных уравнений совместна (т.е. имеющая решения), то схема программы её решения можно записать так:

· Ввести коэффициенты и правые части уравнений;

· Выполнить прямой ход;

· Выполнить обратный ход;

При прямом ходе нужно: получить первое уравнение в виде, удобном для исключения , разделив полученное 1-е уравнение на коэффициент при ; исключить из уравнений с номерами 2, 3, …,n; получить второе уравнение в виде, удобном для исключения ; исключить из уравнений с номерами 3, …,n; получить n–1 уравнение в виде, удобном для получения ; исключить из уравнения с номером n.

Запишем схему программы этого фрагмента :

Получить i-е уравнение в виде, удобном для исключения : исключить из уравнений с номерами i + 1, …, nс помощью i-го уравнения

При обратном ходе из последнего уравнения находят Используя это значение, из предпоследнего n˗1 уравнения исключают и получают . Найденные значения переменных , , …, позволяют вычислить .

Детализируем этап обратного хода.

получить ;

for i:= n˗1 downto 1 do вычислить ;

вывести , …,

Опираясь на разработанные схемы, запишем программу решенияnлинейных уравнений с nпеременными методом Гаусса в предположении, что система совместна ( n

Ссылка на основную публикацию
ВсеИнструменты
Adblock
detector
×
×