Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
ФЕДЕРАЛЬНОЕ АГЕНТСТВО СВЯЗИ
СМОЛЕНСКИЙ КОЛЛЕДЖ ТЕЛЕКОММУНИКАЦИЙ
(филиал) ФЕДЕРАЛЬНОГО ГОСУДАРСТВЕНННОГО ОБРАЗОВАТЕЛЬНОГО БЮДЖЕТНОГО УЧРЕЖДЕНИЯ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
«САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ТЕЛЕКОММУНИКАЦИЙ ИМ. ПРОФ. М.А. БОНЧ-БРУЕВИЧА»
|
УТВЕРЖДАЮ Зам. директора по УПР _____________ И. В. Иванешко «___» ___________ 2012г |
РАССМОТРЕНО на заседании цикловой комиссии математических и программно - вычислительных дисциплин «___»___________2012г. Председатель комиссии __________Мохнач О.А. |
По дисциплине: Теория алгоритмов
Наименование работы: Вычисление обратной матрицы и определителя.
Для специальности: 230115
Работа рассчитана на 2 часа
Составлена преподавателем Мохнач О.А.
г. Смоленск
2012 г.
2. ЛИТЕРАТУРА Конспект.
3. ВОПРОСЫ ДЛЯ ДОМАШНЕЙ ПОДГОТОВКИ:
4. ОБОРУДОВАНИЕ: ПЭВМ
5. ЗАДАНИЕ.
|
Вариант |
Задача |
|
1 |
Разработать программу, вычисляющую обратную матрицу для матрицы n-го порядка. Написать комментарии к каждой строчке программы. |
|
2 |
Разработать программу, вычисляющую определитель для матрицы n-го порядка. Написать комментарии к каждой строчке программы |
|
3 |
Разработать программу, вычисляющую обратную матрицу для матрицы n-го порядка. Написать комментарии к каждой строчке программы. |
|
4 |
Разработать программу, вычисляющую определитель для матрицы n-го порядка. Написать комментарии к каждой строчке программы |
|
5 |
Разработать программу, вычисляющую обратную матрицу для матрицы n-го порядка. Написать комментарии к каждой строчке программы. |
|
6 |
Разработать программу, вычисляющую определитель для матрицы n-го порядка. Написать комментарии к каждой строчке программы |
|
7 |
Разработать программу, вычисляющую обратную матрицу для матрицы n-го порядка. Написать комментарии к каждой строчке программы. |
|
8 |
Разработать программу, вычисляющую определитель для матрицы n-го порядка. Написать комментарии к каждой строчке программы |
|
9 |
Разработать программу, вычисляющую обратную матрицу для матрицы n-го порядка. Написать комментарии к каждой строчке программы. |
|
10 |
Разработать программу, вычисляющую определитель для матрицы n-го порядка. Написать комментарии к каждой строчке программы |
5.2. Проверить получившиеся решения, решив задачу вручную или в математическом пакете (например, Маткад).
6. ПОРЯДОК ВЫПОЛНЕНИЯ РАБОТЫ.
6.1. Повторить правила техники безопасности:
При работе и техническом обслуживании ПК необходимо соблюдать следующие меры предосторожности:
• Запрещается во время работы ПК размыкать и замыкать разъемные соединения.
• источники света должны быть расположены так, чтобы не засвечивать экран монитора, не создавать резких бликов на экране и не светить из-за монитора в глаза человека, работающего с ПК;
Не кладите на монитор бумагу, ткани и прочее, что может нарушить вентиляцию.
Включение ПК должно производиться в следующей последовательности:
Перед выключением компьютера завершите все работающие программы и подождите 1-2 сек. (это необходимо, если на ва шем ПК предусмотрено кэширование дисков). Далее необходимо:
• выключить системный блок;
• выключить принтер (если он был включен);
• выключить монитор.
6.2. Задать двумерный массив размерности n любым способом.
6.3. Реализовать алгоритм нахождения обратной матрицы.
6.4. Реализовать алгоритм нахождения определителя матрицы.
6.5. Вывести результаты.
6.6. Оформить отчет.
8.1. Понятие и цель алгоритма Гаусса.
8.2. Вычисление определителя матрицы методом разложения по строке.
8.3. Методы преобразования задачи.
Вычисление обратной матрицы Методом Гаусса
Метод Гаусса является поистине универсальным методом в линейной алгебре, поскольку он применим и к решению систем линейных уравнений, и к решению определителей, и к отысканию обратной матрицы.
Идея Гаусса заключается в обнулении элементов матрицы ниже главной диагонали и приведении ее к треугольному виду, то есть к простейшему виду, который позволит вычислить легко вычислить определитель, решить систему линейных алгебраических уравнений. Однако для решения вопроса вычисления обратной матрицы недостаточно привести матрицу к треугольному виду. Поскольку обратная матрица призвана переводить исходную матрицу в единичную, то необходимо преобразовать исходную матрицу в единичную, пользуясь пунктами преобразования матрицы по методу Гаусса.
Таким образом, для вычисления обратной матрицы по методу Гаусса, необходимо применить преобразования Гаусса к исходной матрице дважды: сверху-вниз и снизу-вверх. В итоге мы сначала обнуляем элементы ниже главной диагонали, а затем выше главной диагонали, кроме того в конечном итоге приводим все элементы главной диагонали к единице и получаем из данной матрицы единичную.
Теперь возникает естественный вопрос: ну преобразуем мы двойным методом Гаусса матрицу к единичному виду, а откуда же возьмется обратная матрица? Вопрос вполне резонный, поскольку в ходе преобразований матрицы к единичному виду мы не вычисляем обратную матрицу. Дело в том, что необходимо попутно проводить идентичные преобразования Гаусса с рядом записанной единичной матрицей. Тогда указанные преобразования, переводящие исходную матрицу в единичную, переведут единичную матрицу в обратную исходной.
Алгоритм метода Гаусса для обратной матрицы
Слева получилась единичная матрица, а справа обратная матрица.
Решение можно разбить на два этапа: "прямой" и "обратный" ход.
Есть исходная матрица, приписываем к ней единичную:
а[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;
type matr=array[1..n,1..n] of real;
var a,b,a0:matr;
i,j,imx,np:integer;
s0,s1:real;
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;
for i:=1 to n do
for j:=1 to n do
a0[i,j]:=a[i,j];
writeln('Starting matrix:'); np:=0;
PrintMatr( );
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]));
{ Прямой ход }
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]);
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;
end
else writeln('Обратной матрицы не существует.');
MultMatr(a0,b,a);
writeln('Начальная матрица, обратная к ней матрица:');
PrintMatr( );
writeln('Проверка: должна быть единичная матрица.');
PrintMatr();
end.
Вычисление определителя матрицы.
Из свойств определителя известно, что определитель матрицы порядка N может быть представлен в виде суммы N определителей N-1 порядка (разложение по строке или столбцу). Предположим мы раскладываем по первому столбцу. При этом определитель равен сумме произведений элементов этого столбца на минор данного элемента матрицы и на -1 в степени суммы индексов элемента. Минор элемента а[i,j] матрицы - это определитель матрицы, полученной вычеркиванием i-той строки и j-того столбца.
Таким образом можно воспользоваться рекурсией и написав одну простую процедуру вычислять определители матрицы любого порядка.
const n=4; { размерность матрицы }
type matr=array[1..n,1..n] of longint;
var a,b:matr;
i,j,dt:longint;
procedure PrintMatr(m:matr;n:integer);
{ процедура вывода матрицы на экран }
procedure GetMatr(a:matr; var b:matr; m,i,j:integer);
{ Вычеркивание из матрицы строки и столбца }
var ki,kj,di,dj:integer;
begin
di:=0;
for ki:=1 to m-1 do
begin
if (ki=i) then di:=1;
dj:=0;
for kj:=1 to m-1 do
begin
if (kj=j) then dj:=1;
b[ki,kj]:=a[ki+di,kj+dj];
end;
end;
end;
Function Determinant(a:matr;n:integer):longint;
{ Вычисление определителя матрицы }
var i,j,d,k:longint;
b:matr;
begin
d:=0; k:=1;
if (n<1) then
begin
writeln('Determinant: Cann''t run. N=',n); halt;
end;
if (n=1)
then d:=a[1,1]
else if (n=2)
then d:=a[1,1]*a[2,2]-a[2,1]*a[1,2]
else { n>2 }
for i:=1 to n do
begin
GetMatr(a,b,n,i,1);
{writeln('i=',i,' a[',i,',1]=',a[i,1]);
PrintMatr(b,n-1);}
d:=d+k*a[i,1]*Determinant(b,n-1);
k:=-k;
end;
Determinant:=d;
end;
begin
{ Заполнение матрицы случайными числами }
randomize;
for i:=1 to n do
for j:=1 to n do
a[i,j]:=random(5);
{ Печать исходной матрицы }
PrintMatr(a,n);
{ Вычисление и вывод определителя }
dt:=Determinant(a,n);
writeln('=========');
writeln('Determinant=',dt);
end.