тематических и программно вычислительных дисциплин 2012г

Работа добавлена на сайт samzan.net:

ФЕДЕРАЛЬНОЕ АГЕНТСТВО СВЯЗИ

СМОЛЕНСКИЙ КОЛЛЕДЖ ТЕЛЕКОММУНИКАЦИЙ

(филиал) ФЕДЕРАЛЬНОГО ГОСУДАРСТВЕНННОГО ОБРАЗОВАТЕЛЬНОГО БЮДЖЕТНОГО УЧРЕЖДЕНИЯ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ТЕЛЕКОММУНИКАЦИЙ ИМ. ПРОФ. М.А.  БОНЧ-БРУЕВИЧА»

УТВЕРЖДАЮ Зам. директора по УПР _____________ И. В. Иванешко «___» ___________ 2012г

РАССМОТРЕНО на  заседании цикловой комиссии математических и программно - вычислительных дисциплин «___»___________2012г. Председатель комиссии __________Мохнач О.А.

ПРАКТИЧЕСКАЯ РАБОТА 8

                        

 

      По дисциплине:  Теория алгоритмов 

                   

Наименование работы:   Вычисление обратной матрицы и определителя.

    

                 Для специальности: 230115     

        Работа рассчитана на 2 часа

Составлена преподавателем Мохнач О.А.

г. Смоленск

2012 г.

1.  ЦЕЛЬ РАБОТЫ: изучить алгоритмы вычисления обратной матрицы и определителя матрицы.

2. ЛИТЕРАТУРА   Конспект.

3.  ВОПРОСЫ ДЛЯ ДОМАШНЕЙ ПОДГОТОВКИ:

1.  Суть метода Гаусса.
   1.  Какие методы решения СЛАУ вы знаете?
   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. Оформить отчет.

1.  СОДЕРЖАНИЕ ОТЧЕТА.
   1.  Цель работы.
   2.  Текст программы с комментариями.
2.  КОНТРОЛЬНЫЕ ВОПРОСЫ

8.1. Понятие и цель алгоритма Гаусса.

8.2. Вычисление определителя матрицы методом разложения по строке.

              8.3. Методы преобразования задачи.

1.  ПРИЛОЖЕНИЕ

Вычисление обратной матрицы Методом Гаусса

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

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

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

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

Алгоритм метода Гаусса для обратной матрицы

1.  Нужно записать рядом две матрицы - слева данную матрицу, а справа единичную.
2.  Дальнейшие преобразования проводить как для левой матрицы, так и для правой одновременно.
3.  Умножить первую строку исходной матрицы на число обратное первому элементу. В результате элемент первой строки станет равным единице, а для второй матрицы - обратному первому элементу первой строки исходной матрицы.
4.  Умножить первую строку на число, равное первому элементу второй строки. Первый элемент первой строки станет равным первому элементу второй строки. Для второй матрицы первый элемент будет равен отношению первых элементов второй и первой строки исходной матрицы.
5.  Вычесть из второй строки первую строку. На первом месте второй строки окажется 0. Первый элемент второй строки правой матрицы станет равным противоположному для первого элемента первой строки.
6.  Вычесть из третьей и всех последующих строк первую строку, предварительно умножив ее на элемент уменьшаемой строки. Первый столбец на этом этапе будет обнулен, а в правой матрице в первом столбце ниже первой строки появятся отличные от нуля элементы.
7.  Вычеркнуть первую строку и первый столбец из полученных матриц на 6 этапе.
8.  К полученной матрице на единицу меньшего порядка применить действия по пунктам 3-7 Метода Гаусса не забывая при этом производить указанные действия над полными строками обеих матриц. В результате первый столбец правой матрицы уже будет алгебраической суммой двух слагаемых.
9.  Повторить пункт 9 ко всем подматрицам более низкого порядка. В результате выполнения пунктов 1-11 мы получим матрицу ниже главной диагонали которой все элементы равны нулю, тем не менее в правой матрице элементы ниже главной диагонали станут отличными от нуля.
10.  Выполнить аналогичные действия по обнулению элементов левой матрицы в обратном порядке снизу вверх.
11.  Разделить все строки матриц на значения диагональных элементов.

                  Слева получилась единичная матрица, а справа обратная матрица.

Решение можно разбить на два этапа: "прямой" и "обратный" ход.

Есть исходная матрица, приписываем к ней единичную:

а[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.

1. Введение Холодильная установка представляет собой совокупность машин аппаратов приборов и сооружени
2. Кластерная теория интеграции
3. тема Пикассо и Россия взаимосвязи испанского мастера с лидерами русского авангарда М
4. а похожи на Солнце но гораздо моложе его
5. Тема 12 Россия во второй половине 18 в
6. Джума-Джами в Евпатории
7. Назначение 10
8. Александр I
9. Социальное партнёрство
10. культурные процессы в культурологии.
11. Маркетинговые стратегии фирмы
12. Пользовательский интерфейс операционной системы Windows
13. Лекция 5. СОЦИАЛЬНАЯ ФИЛОСОФИЯ
14. Темы рефератов (контрольной работы) по дисциплине «Социология рынков»
15. Бизнес-план предприятия для организации коммерческой деятельности в отрасл
16. Есенин- стихи-письма
17. Тема занятия Форма проведения Программное содержание Взаимосвязь с д.html
18. ПЗ АНАЛИЗ СОВРЕМЕННОГО СОСТОЯНИЯ БИЧЕВЫХ МАШИН Назначение и классификаци
19. РЕФЕРАТ дисертації на здобуття наукового ступеня
20. И Скрыпник Россия встает на путь целостного и гармоничного развития общества Российская национальная ид

Материалы собраны группой SamZan и находятся в свободном доступе