МИНОБРНАУКИ РОССИИ САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ ЭЛЕКТРОТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ «ЛЭТИ» ИМ. В.И. УЛЬЯНОВА (ЛЕНИНА) Кафедра физической электроники и технологии
ОТЧЕТ по лабораторной работе №6
по дисциплине «Информационные технологии» Тема: Алгоритмы и программы решения задач комбинаторики
Студентка гр. 0207 |
|
Лиоско Е.П. |
|
Преподаватель |
|
|
Рябцев И.А. |
Санкт-Петербург
2021
Алгоритм вычисления определителя матрицы (метод Гаусса
Цель работы.
Изучение и программирование быстрого алгоритма вычисления определителя матрицы.
Блок-схема программы для сортировки выбором.
2
Текст программы 1.
clear; |
|
|
|
|
|
clc; |
|
|
|
|
|
n=5; |
|
|
|
|
|
a=[1 2 |
3 |
4 |
5 |
|
|
10 |
9 |
8 |
7 |
6 |
|
5 |
9 |
11 |
12 |
13 |
|
20 |
1 |
3 |
17 |
14 |
|
12 |
10 |
4 |
16 |
15]; |
|
tic; da=det_Gauss(a,n); toc;
disp(a)
disp(da)
function[det]=det_Gauss(a,n)
for K=1:n-1 % рассмотрим первые 4 столбца for i=K+1:n % рассмотрим 2-5 строчки
for J=K:n % пробег от K до n (преобразовываем к треугольной матрице)
if J==K % проверка элемента на нахождении на главной диагонали матрицы
aik=a(i,K);
else a(i,J)= a(i,J)-aik/a(K,K)*a(K,J); disp(a(i,J));
end
end
end end det=1;
disp(a) for i=1:n
det=det*a(i,i);
end end
Листинг 1
Columns 1 through 4
1.0000 |
2.0000 |
3.0000 |
4.0000 |
10.0000 |
-11.0000 -22.0000 -33.0000 |
||
5.0000 |
-1.0000 |
-2.0000 |
-5.0000 |
3
20.0000 -39.0000 21.0000 1.5000
12.0000 -14.0000 -4.0000 20.0000
Column 5
5.0000
-44.0000 -8.0000 -14.0000 213.6667
Elapsed time is 0.008386 seconds. 7.0510e+03
Текст программы 2 (библиотечная функция det(а)).
clear; %библиотечная функция det(a) MATLAB clc;
n=5;
a=[1 2 3 4 5; 10 9 8 7 6; 5 9 11 12 13; 20 1 3 17 14 12 10 4 16 15];
da=det(a);
disp(a)
disp(da)
Листинг 2
7.0510e+03
Текст программы 3
clear; % модифицированная Программа 1 clc;
n=1000; % n=1600, 2000 a=rand(n);
tic; da=det_Gauss(a,n); toc;
disp(n)
4
Таблица 1. Алгоритм Гаусса
i |
N |
t1, сек |
t2, сек |
t3, сек |
tmax, сек |
|
|
|
|
|
|
1 |
1000 |
1.5 |
1.6 |
1.58 |
1.6 |
|
|
|
|
|
|
2 |
1600 |
9.06 |
9.06 |
9.07 |
9.07 |
3 |
2000 |
18.6 |
18.6 |
18.8 |
18.8 |
|
|
|
|
|
|
Таблица 2. Алгоритм Гаусса
|
i-j |
|
KN |
|
|
Kt |
|
|
K3 |
|
|
|||
|
1-2 |
|
1,6 |
|
|
5,6 |
|
|
4,1 |
|
|
|||
|
1-3 |
|
2 |
|
11,5 |
|
|
8 |
|
|
|
|||
|
2-3 |
|
1,25 |
|
|
2,1 |
|
|
2 |
|
|
|
||
|
|
Таблица 3. Функция Матлаб |
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
i |
|
N |
t1, сек |
|
|
|
t2, сек |
|
t3, сек |
tmax, сек |
|||
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
1 |
|
1600 |
0.04 |
|
|
|
0.097 |
|
0.06 |
0.097 |
|||
|
2 |
|
2000 |
0.07 |
|
|
|
0.103 |
|
0.09 |
0.10 |
|||
|
3 |
|
4000 |
0.49 |
|
|
|
0.47 |
|
0.50 |
0.50 |
|||
|
|
Таблица 4. Функция Матлаб |
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
||||
|
i-j |
|
KN |
Kt |
|
K3 |
|
|
|
|
||||
|
1-2 |
|
1,25 |
1,06 |
|
|
|
1,18 |
|
|
|
|
||
|
1-3 |
|
2,5 |
5,15 |
|
|
|
136,3 |
|
|
|
|
||
|
2-3 |
|
2 |
4,9 |
|
|
|
115,97 |
|
|
|
|
||
Вывод
С увеличением размерности матрицы время вычисления определителя увеличивается. Библиотечная функция det (M) Матлаба реализует вычисление определителя матрицы по более быстрому алгоритму, чем алгоритм Гаусса
5