Метод квадратних коренів

Введення

Система лінійних алгебраїчних рівнянь - математична модель, яка описує стан рівноваги економічного об'єкта, яке називається сталим режимом або статикою об'єкта. Економічна статика вивчає допустимі та раціональні стану економічного об'єкта.

Нехай дана система n лінійних алгебраїчних рівнянь з n невідомими

(1.1)

або в матричній формі

Ax = b,

де

- матриця коефіцієнтів,

- стовпець вільних членів і стовпець невідомих відповідно.

Якщо матриця А невироджена, тобто

то система (1.1) має єдине рішення. У цьому випадку рішення системи (1.1) з теоретичної точки зору не представляє праці. Значення невідомих x i (i = 1,2, ... n) можуть бути отримані за відомими формулами Крамера

Крамер квадратний корінь матриця

де матриця A i виходить із матриці А заміною її i-го стовпця стовпцем вільних членів.

Але такий спосіб вирішення лінійної системи з n невідомими призводить до обчислення n + 1 визначників порядку n, що являє собою досить трудомістку операцію при скільки-небудь великому числі n.

Застосовувані в даний час методи рішення лінійних систем можна розбити на дві групи: точні і наближені.

Точними методами називаються такі методи, які в припущенні, що обчислення ведуться точно (Без округлень), приводять до точних значень невідомих x i . Так як на практиці всі обчислення ведуться з заокругленнями, то і значення невідомих, отримані точним методом, неминуче будуть містити похибки. До точних методів відносяться, наприклад, метод Гаусса, метод квадратних коренів.

Наближеними методами називаються такі методи, які навіть в припущенні, що обчислення ведуться без округлень, дозволяють отримати розв'язок системи (x 1 , x 2 , ..., x n ) лише з заданою точністю. Точне рішення системи в цих випадках може бути отримано теоретично як результат нескінченного процесу. До наближених методів відносяться метод простої ітерації, метод Зейделя та ін Кожен з цих методів не завжди є збіжним в застосуванні до конкретного класу систем лінійних рівнянь.

Дана контрольна робота має наступну структуру: на початку розглядається математична постановка завдання для методу квадратних коренів при вирішенні систем лінійних алгебраїчних рівнянь. Потім проводиться реалізація даного методу за допомогою обчислювальних засобів ЕОМ, а саме прикладною програмою Matlab 6.5. На прикладі реалізації декількох тестових завдань проводиться аналіз точності даного методу, а саме коли найбільш ефективно застосовувати метод квадратних коренів при вирішенні систем лінійних алгебраїчних рівнянь. Аналіз проводиться на основі матриці А (її мірності, розрідженості, обумовленості. Результати, отримані на основі методу квадратних коренів, наведені в кінці даної роботи. Також в роботі представлений графічний матеріал. По закінченні проведення дослідження робота завершується логічним висновком.

Математична постановка задачі

Метод квадратних коренів використовується для вирішення лінійної системи

Ax = b,

(1.2)

у якої матриця А симетрична, тобто

a ij = a ji (i, j = 1, 2, ..., n).

Метод є більш економним і зручним у порівнянні з вирішенням систем загального вигляду.

Рішення системи здійснюється в два етапи.

Прямий хід. Уявімо матрицю А у вигляді добутку двох взаємно транспонувати трикутних матриць:

(1.3)

А = Т Вў Т,

де

.

Перемножая матриці T Вў і T і прирівнюючи матриці A, отримаємо наступні формули для визначення t ij :

(1.4)

Після того, як матриця Т знайдена, систему (1.2) замінюємо двома еквівалентними їй системами з трикутними матрицями

(1.5)

T Вў y = b, Tx = y.

Зворотний хід. Записуємо в розгорнутому вигляді системи (1.5):

Звідси послідовно знаходимо

При обчисленнях застосовується звичайний контроль з допомогою сум, причому при складанні суми враховуються всі коефіцієнти відповідного рядка.

Зауважимо, що при дійсних a ij можуть вийти чисто уявні t ij . Метод застосовний і в цьому випадку.

Опис програмного забезпечення (згідно зі стандартами на ІТ)

Для вивчення даного методу було обрано програмне забезпечення: 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 * xb. Проілюструємо результати графічно. Для цього була розроблена програма в середовищі 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 Q3 Q4];

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 a3 a4];

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

0

0.2665

0

0

, їй відповідно задамо

X =

-0.4950

0.1575

5.0050

4.7700

-5.5025

E =

0

0

0

-0.7105

0.4441

, їй відповідно задамо

X =

-4.1125

1.0263

-1.0750

1.2947

-1.2313

E =

-0.0444

0

0.0888

-0.0888

0.1776

, їй відповідно задамо

X =

0.5000

1.0263

1.6667

1.2947

0.8250

E =

0

0

0.8882

-0.8882

0

Чіткої тенденції простежити неможливо, хоча видно на основі запропонованої матриці А, що з збільшення числа нулів, присутніх в матриці, точність рішення збільшується, тому зменшується число елементів задіяних в обчисленні, то і знижується помилка обчислень.

Гј обумовленість матриці А;

Задамо матрицю з практично рівними елементами. У наслідку будемо збільшувати її розмірність.

, їй відповідає

X =

-1.6499

-1.6501

E =

0

-0.9313

, їй відповідає

X =

-1.6522

0.7500

2.3978

E =

0

0.1863

0

, їй відповідає

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.