Введение
Система линейныхалгебраических уравнений – математическая модель, которая описывает состояниеравновесия экономического объекта, которое называется установившимся режимомили статикой объекта. Экономическая статика изучает допустимые и рациональныесостояния экономического объекта.
Пусть дана система n линейных алгебраических уравнений с n неизвестными
(1.1) />
или в матричной форме
Ax = b,
где
/>
— матрица коэффициентов,
/>/>
/>
— столбец свободныхчленов и столбец неизвестных соответственно.
Если матрица Анеособенная, т.е.
/>
то система (1.1) имеетединственное решение. В этом случае решение системы (1.1) с теоретической точкизрения не представляет труда. Значения неизвестных xi (i=1,2,…n)могут быть получены по известным формулам Крамера
/>
крамерквадратный корень матрица
где матрица Ai получается из матрицы А заменой ее i-го столбца столбцом свободныхчленов.
Но такой способ решениялинейной системы с n неизвестнымиприводит к вычислению n + 1определителей порядка n, чтопредставляет собой весьма трудоемкую операцию при сколько-нибудь большом числе n.
Применяемые в настоящеевремя методы решения линейных систем можно разбить на две группы: точные иприближенные.
Точными методаминазываются такие методы, которые в предположении, что вычисления ведутся точно(без округлений), приводят к точным значениям неизвестных xi. Так как на практике все вычисленияведутся с округлениями, то и значения неизвестных, полученные точным методом,неизбежно будут содержать погрешности. К точным методам относятся, например,метод Гаусса, метод квадратных корней.
Приближенными методаминазываются такие методы, которые даже в предположении, что вычисления ведутсябез округлений, позволяют получить решение системы (x1, x2, …, xn) лишь с заданной точностью. Точное решениесистемы в этих случаях может быть получено теоретически как результатбесконечного процесса. К приближенным методам относятся метод простой итерации,метод Зейделя и др. Каждый из этих методов не всегда является сходящимся вприменении к конкретному классу систем линейных уравнений.
Данная контрольная работаимеет следующую структуру: в начале рассматривается математическая постановказадачи для метода квадратных корней при решении систем линейных алгебраическихуравнений. Затем производится реализация данного метода с помощьювычислительных средств ЭВМ, а именно прикладной программой Matlab 6.5. На примере реализациинескольких тестовых задач проводится анализ точности данного метода, а именнокогда наиболее эффективно применять метод квадратных корней при решении системлинейных алгебраических уравнений. Анализ проводится на основе матрицы А (еемерности, разреженности, обусловленности. Результаты, полученные на основеметода квадратных корней, приведены в конце данной работы. Также в работепредставлен графический материал. По окончании проведения исследования работазавершается логическим заключением.
Математическаяпостановка задачи
Метод квадратных корнейиспользуется для решения линейной системы
Ax = b,
(1.2)
у которой матрица Асимметрическая, т.е.
aij =aji (i, j = 1,2, …, n).
Метод является болееэкономным и удобным по сравнению с решением систем общего вида.
Решение системыосуществляется в два этапа.
Прямой ход. Представимматрицу А в виде произведения двух взаимно транспонированных треугольныхматриц:
(1.3) А = Т¢ Т,
где
/>
/>.
Перемножая матрицы T¢ и T и приравнивая матрице A, получим следующие формулы для определения tij:
/>
(1.4) После того, какматрица Т найдена, систему (1.2) заменяем двумя эквивалентными ей системами стреугольными матрицами/>
(1.5)
T¢y = b, Tx = y.
Обратный ход. Записываемв развернутом виде системы (1.5):
/>
/>
Отсюда последовательнонаходим
/>
При вычисленияхприменяется обычный контроль с помощью сумм, причем при составлении суммыучитываются все коэффициенты соответствующей строки.
Заметим, что придействительных aijмогут получиться чисто мнимые tij. Метод применим и в этом случае.
Описаниепрограммного обеспечения (согласно стандартам на ИТ)
Для изучения данногометода было выбрано программное обеспечение: Matlab 6.5, в операционной системе Windows XP Professional. На этапе проектирования быласоздана программа Square(‘квадрат’). Входными переменными для данной программы является матрица A и соответствующая ей матрица B. Результатом выполнения даннойпрограммы является матрица X(выходная переменная), которая является решением системы линейныхалгебраических уравнений.
Ниже описан алгоритмреализации метода квадратных корней на языке программирования в среде Matlab 6.5:
A=input('Введите матрицуA=');
B=input('Введите B=');
if A==A'
if det(A)~=0
s=size(A,1);
if size(B',1)== s
T=zeros(s);
T(1,1)=sqrt(A(1,1));
for k=2:s
T(1,k)=A(1,k)/T(1,1)
end
for j=2:s
for i=2:s
if i==j
sm=0
for k=1:(i-1)
sm=sm+T(k,i)^2
end
T(i,i)=sqrt(A(i,i)-sm)
else
if i
sm=0
for k=1:(i-1)
sm=sm+T(k,i)*T(k,j)
end
T(i,j)=(A(i,j)-sm)/T(i,i)
end
end
end
end
Y=zeros(s,1)
Y(1)=B(1)/T(1,1)
for i=2:s
sm=0
for k=1:(i-1)
sm=sm+T(k,i)*Y(k)
end
sm
Y(i)=(B(i)-sm)/T(i,i)
end
X=zeros(s,1)
X(s)=Y(s)/T(s,s)
for m=1:(s-1)
i=s-m
sm=0
for k=(i+1):s
sm=sm+T(i,k)*X(k)
sm
end
X(i)=(Y(i)-sm)/T(i,i)
E=A*X-B'
end
else
error('B не соответствуетматрице А')
end
else
error('det А = 0')
end
else
B = B*A'
A = A*A'
if det(A)~=0
s=size(A,1);
if size(B',1)== s
T=zeros(s);
T(1,1)=sqrt(A(1,1));
for k=2:s
T(1,k)=A(1,k)/T(1,1)
end
for j=2:s
for i=2:s
if i==j
sm=0
for k=1:(i-1)
sm=sm+T(k,i)^2
end
T(i,i)=sqrt(A(i,i)-sm)
else
if i
sm=0
for k=1:(i-1)
sm=sm+T(k,i)*T(k,j)
end
T(i,j)=(A(i,j)-sm)/T(i,i)
end
end
end
end
Y=zeros(s,1)
Y(1)=B(1)/T(1,1)
for i=2:s
sm=0
for k=1:(i-1)
sm=sm+T(k,i)*Y(k)
end
sm
Y(i)=(B(i)-sm)/T(i,i)
end
X=zeros(s,1)
X(s)=Y(s)/T(s,s)
for m=1:(s-1)
i=s-m
sm=0
for k=(i+1):s
sm=sm+T(i,k)*X(k)
sm
end
X(i)=(Y(i)-sm)/T(i,i)
end
else
error('B не соответствуетматрице А')
end
else
error('det А = 0')
end
end
Описаниетестовых задач
Результатом разработкипрограммы является этап реализации и тестирования метода квадратных корней. Наэтапе выполнения программы может появляться неточность полученного решенияиз-за ошибки вычисления (например, ошибки округления ЭВМ). Исследуем влияниемерности матрицы A, ееобусловленности, разреженности на точность полученного решения. Результат будемоценивать по невязке ε = Ax* — b (x* — полученное решение). Для этогорассмотрим разного рода матрицы:
ü влияние мерности матрицы А;
Рассмотрим матрицымерности 2´2, 3´3, 4´4 и 5´5. Зададим матрицу мерностью 2´2:
/>, ей соответственно зададим />, в результатевыполнения программы получим решение:
X = />
ε = />
Зададим матрицуразмерностью 3´3:
/>, ей соответственно зададим />, в результатевыполнения программы получим решение:
X = />
ε = />
Зададим матрицуразмерностью 4´4:
/>, ей соответственно зададим />, в результатевыполнения программы получим решение:
X = />
ε = />
Зададим матрицуразмерностью 5´5:
/>, ей соответственнозададим />,в результате выполнения программы получим решение:
X = />
ε = />
Сравним полученныерезультаты, для этого проанализируем точность полученного решения. Результат мыможем оценить двумя способами /> и />, где E – матрица, полученная в результате подстановки найденногорешения в систему линейных алгебраических уравнений: Е=A*x-b. Проиллюстрируем результатыграфически. Для этого была разработана программа в среде Matlab 6.5.
E2=input('Введите матрицу Е2=');
E3=input('Введите матрицу Е3=');
E4=input('Введите матрицу Е4=');
E5=input('Введите матрицу Е5=');
Q1=sqrt(sum(power(E2,2)));
Q2=sqrt(sum(power(E3,2)));
Q3=sqrt(sum(power(E4,2)));
Q4=sqrt(sum(power(E5,2)));
Q = [Q1 Q2 Q3Q4];
abs(E2);
abs(E3);
abs(E4);
abs(E5);
a1=max(abs(E2));
a2=max(abs(E3));
a3=max(abs(E4));
a4=max(abs(E5));
A = [a1 a2 a3a4];
E = [2 3 4 5];
plot (Q,E)
pause
plot (A,E)
/>
/>
/>
/>
На основе проведенногоанализа и иллюстрации графиков можно сделать вывод, что с увеличением мерностиматрицы увеличивается неточность решения.
ü влияние обусловленности матрицы А;
Для исследования возьмемматрицу следующего вида, которую в последствии будем заполнять нулями,прослеживая результат изменения ошибки:
/>, ей соответственнозададим />
X =
-6.1000
-2.2000
-6.8000
-0.9000
0.2000
E =
-0.0389
-0.7994
0.2665
-0.0888
0.0888
/>, ей соответственнозададим />
X =
-0.7869
-1.3706
-2.1805
-0.0204
1.5371
E =
0.2665
/>, ей соответственнозададим />
X =
-0.4950
0.1575
5.0050
4.7700
-5.5025
E =
-0.7105
0.4441
/>, ей соответственнозададим />
X =
-4.1125
1.0263
-1.0750
1.2947
-1.2313
E =
-0.0444
0.0888
-0.0888
0.1776
/>, ей соответственнозададим />
X =
0.5000
1.0263
1.6667
1.2947
0.8250
E =
0.8882
-0.8882
Четкой тенденциипроследить невозможно, хотя видно на основе предложенной матрицы А, что сувеличение числа нулей, присутствующих в матрице, точность решенияувеличивается, т.к. уменьшается число элементов задействованных в вычислении,то и снижается ошибка вычислений.
ü обусловленность матрицы А;
Зададим матрицу спрактически равными элементами. В последствии будем увеличивать ее размерность.
/>, ей соответствует />
X =
-1.6499
-1.6501
E =
-0.9313
/>, ей соответствует />
X =
-1.6522
0.7500
2.3978
E =
0.1863
/>, ей соответствует />
X =
0.0018
2.4041
2.3978
0.0033
E =
-0.0167
0.0371
-0.0371
-0.3558
Обусловленность матрицыснижает ошибку вычислений у матриц с более высокой размерностью, т.е. сувеличением размерности разряженной матрицы ее точность увеличивается (ошибкавычислений снижается).
Анализрезультатов
Подводя итоги можносделать следующий вывод. Точность решения зависит как от обусловленности,разреженности и мерности матрицы, так и в целом комбинация этих составляющихвлияет на точность полученного решения. Хотя в некоторых случаях однозначногоответа дать невозможно, так как точность зависит еще и от того, насколькогромоздки были вычисления, и как много требовалось округлений, а также все либыли учтены недочеты. А также если корни будут близки к целым корням, то иточность решения будет выше.
Заключение
В данной контрольнойработе был проанализирован один из методов решения систем линейныхалгебраических уравнений: метод квадратных корней. Метод был предложен длярешения системы Ax=b, где матрица A – симметрическая, хотя не исключено,что метод может использоваться и не для симметрических матриц, тогда исходнуюсистему можно привести к виду AA¢x=b A¢, полученную систему легко можно решить методом квадратныхкорней.
Также в данной системебыли проанализированы разного рода матрицы, и их влияние на точностьполученного решения. Основываясь на полученных выводах, можно контролировать вкаких конкретно моментах удобно решать систему линейных алгебраическихуравнений методом квадратных, а когда лучше использовать другой метод.
Литература
1. Государственные стандарты. ИТ.комплекс стандартов и руководящих документов на АС. Издание официальное.Комплект стандартизации и метрологии СССР. М. – 1991.
2. Копченова Н.В., Марон И.А. Вычислительнаяматематика в примерах и задачах. М.: «Наука», 1972.
3. Писсанецки С. Технология разряженныхматриц. – М.: Мир, 1988.
4. Сарычева О.М. Численные методы вэкономике: Конспект лекций. Новосибирск: НГТУ, 1995.
5. Численные методы. Методические указания.НГТУ, 2002.