86114 (Стійкість системи лінійних алгебраїчних рівнянь)

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ

СУМСЬКИЙ ДЕРЖАВНИЙ УНІВЕРСИТЕТ

КАФЕДРА ІНФОРМАТИКИ

Курсова робота

по чисельним методам

на тему:”Стійкість СЛАР”

Суми 2005

Зміст

1. Постановка задачі.

2. Теоретична частина.

а) характеристичний многочлен

в) метод Левeр’є

б) критерій Калашнікова

Текст програми

Приклад

Список літератури

Постановка задачі

Дана система лінійних алгебраїчних рівнянь. Необхідно дослідити її на стійкість. Знайти характеристичний многочлен методом Левур’є. Зробити відповідні висновки щодо її стійкості.

Теоретична частина

Характеристичний многочлен

Нехай дана квадратна матриця А=[aij]. Розглянемо лінійне перетворення

у=Ах (1)

де х,у n-вимірні вектори (стовпові матриці) деякого, взагалі кажучи, комплексного n-вимірного простору.

Ненульовий вектор називається власним вектором даної матриці (або визначуваного нею лінійного перетворення), якщо в результаті відповідного лінійного перетворення цей вектор переходить в колінеарний йому, тобто якщо перетворений вектор відрізняється від початкового тільки скалярним множником.

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

Ах=x (2)

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

Теорема 1. В комплексному векторному просторі кожне лінійне перетворення (матриця) має щонайменше один дійсний або комплексний власний вектор.

Доведення. нехай А матриця лінійного перетворення. Власні вектори матриці А є ненульовими розв'язками матричного рівняння

Ах=х

або

(А- Е)х=0 (3)

де матриця (А- Е) називається характеристичною матрицею. Рівняння (3) представляє собою лінійну однорідну систему, яка має ненульові розв'язки тоді і лише тоді, коли визначник системи рівний нулю, тобто повинна виконуватися умова

det(А- Е)=0. (4)

Визначник (4) називається характеристичним (віковим) визначником матриці А, а рівняння (4) називається характеристичним (віковим) рівнянням матриці А. В розгорненому вигляді характеристичне рівняння (4) запишеться таким чином:

а11- а12 ... а1n

а21 а22- ... а2n =0

an1 an2 ann-

або

^n-₁^n-1+₂^n-2- ...+(-1)^n-1_n-1+(-1)ⁿ_n=0. (5)

Поліном, що стоїть в лівій частині рівняння (5), називається характеристичним поліномом матриці А. Коефіцієнти його i(i=1,2,…,n) визначаються за наступними правилами. Коефіцієнт ₁₌.

Це число називається услід матриці А і позначається так: _1=Sp А. Коефіцієнт ₂ є сума всіх діагональних мінорів другого порядку матриці А. Взагалі, коефіцієнт є сума всіх діагональних мінорів -го порядку матриці А. Зрештою, вільний член _n рівний визначнику матриці А:

_n=det А.

Характеристичне рівняння (5) є алгебраїчне рівняння n-ої степені відносно і, отже, як доводиться в алгебрі, має щонайменше один дійсний або комплексний корінь. Нехай _{1 2,… m(m}n) — різні корені рівняння (5). Ці корені називаються власними значеннями, або характеристичними числами, матриці А, а сукупність всіх власних значень називається спектром матриці А. Візьмемо який-небудь корінь =_j і підставимо його в рівняння (4). Тоді будемо мати (А-_jЕ)х=0 або, в розгорненому вигляді

( а11-_j)х₁+а₁₂х₂+…+а_1nx_n=0

а21х1+(а22-_j)х₂+ ...+а_2nx_n=0

an1х1+an2х2+ ...+(a_nn-_j)x_n=0. . . . . . . . . . . . (6)

Оскільки визначник системи (6) det(А-_jЕ)=0, то ця система явно має ненульові розв'язки, які і є власними векторами матриці А, відповідними власному значенню _j. Якщо ранг матриці А-_jЕ рівний r(r

х^(1j), х^(2j) ...,х^(kj)

відповідаючих кореню _j. Теорема доведена.

Метод Левер’є

Відомо багато інших способів одержання характеристичного многочлена.

Розглянемо метод Левер’є, що дозволяє вирішити проблему власних значень, в основу якого покладено обчислювання слідів степенів матриці А. Вказаний метод потребує більшої кількості операцій, ніж метод Данилевського, але зовсім не чутливий до частинних особливостей матриці, зокрема ”провалів” проміжних визначників.

Нехай характеристичний поліном матриці А записано у вигляді (5) де

_{1, 2, 3, .........n} – його корені, серед яких деякі можуть бути рівні. Позначимо

(7)

С уми , k=1-n степенів коренів многочлена зв’язані з коефіцієнтами рівняння ( 5) формулами Ньютона

k= 1,…..,n (8)

Якщо обчислити сліди , ……. , матриць , ….., ,то з (8) можна послідовно обчислити коефіцієнти

Покажемо, як визначаються числа :

Оскільки матриця має своїми власними значеннями числа , … то

.

Таким чином, процес обчислення зводиться до послідовного обчислення степенів матриці А, обчислення їх слідів (суми діагональних елементів ) і, нарешті , до розв’язання рекурентної системи (8). Обчислення n степенів матриці А (в останньої матриці (А) треба знайти тільки діагональні елементи) потребує великої кіолькості одноманітних операцій , які легко реалізуються за доомогою ПВМ. Кількість необхідних за методом Левер’є множень дорівнює ½( -1)(2 -2 + +2) )

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

Р езультат множення матриці А на цей стовпець повинен збігатися з аналогічним стовпцем матриці . Дійсно, нехай – стовпець сум матриці А : - стовпець сум матриці . Нехай U (1,2….1). Тоді

=AU; = U =A

Очевидно сказане вірне й для інших степенів.

Визначивши з допомогою вказаного методу коефіцієнти характеристичного полінома вигляду (5), знаходимо його кореня, які є шуканими власними значеннями.

Реалізація методу на прикладі.

Знайти характеристичний многочлен методом Левур’є.

1 -1 1

А = 4 6 -1

4 4 1

У відповідності із методом Левер’є будуємо степені (к=2,3)

1 -1 1 1 -1 1 1 -3 3

= 4 6 -1 * 4 6 -1 = 24 28 -3

4 4 1 4 4 1 24 24 1

1 -1 1 1 -3 3 1 -7 7

= 4 6 -1 * 24 28 -3 = 124 132 -7

4 4 1 24 24 1 124 124 1

Звідси

=1+6+1=8;

=1+28+1=30;

=1+132+1=134

Відповідно до формул (8) маємо

=8

1/2(30-8*8)=-17

1/3(134-8*30-17*8)=10

Згідно методу дістанемо

Текст програми

program leverie;

uses wincrt;

type matr=array[1..10,1..10] of real;

mas=array[1..10] of real;

var n,i,j,k,l,g,v:integer;

p,s:mas;

a,b,c:matr;

stiykist:real;

procedure mnogmatr(a,b:matr;n:integer; var c:matr);

begin

for i:=1 to n do

for j:=1 to n do

c[i,j]:=0;

for k:=1 to n do

for i:=1 to n do

for j:=1 to n do

begin

c[k,i]:= c[k,i]+a[j,i]*b[k,j];

end;

end;

begin

writeln('vvedit rozmirnict matrici n=');

readln(n);

writeln('vvedit koeficienti matrici');

for i:=1 to n do

for j:=1 to n do

begin

write('a[',i,',',j,']=');

readln(a[i,j]);

end;

for i:=1 to n do

for j:=1 to n do

c[i,j]:=a[i,j];

for i:=1 to n do

s[1]:=s[1]+a[i,i];

p[1]:=s[1];

for l:=2 to n do

begin

for i:=1 to n do

for j:=1 to n do

b[i,j]:=c[i,j];

mnogmatr(a,b,n,c);

for j:=1 to n do

s[l]:=s[l]+c[j,j];

for k:=1 to l do

p[l]:=p[l]-p[k]*s[l-k];

p[l]:=(s[l]+p[l])/l;

end;

writeln('haracteristichniy mnogochlen');

g:=n; v:=0;

repeat

write(p[g]:2:3,'*l^',v,'+');

g:=g-1; v:=v+1;

until g=0;

writeln('-l^',v,'=0');

for i:=1 to n do

stiykist:=stiykist+abs(p[i]);

if stiykist>1 then writeln('sistema ne stiyka') else writeln('sistema stiyka');

end.

Приклад

Перевірити на стійкість систему Аx=B

-0.77 -0.44 0.21 -0.18 -1,24

А= 0.45 1.23 0.06 0 x= В = 0,88

0.26 0.34 -1.11 0 -0,64

0.05 -0.26 0.34 -1.12 1,17

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

⁴ + 1.77³ - 0.598² - 2.306 - 0.949 = 0.

Список літератури

1. Я.М. Григоренко, Н.Д. Панкратова «Обчислювальні методи» 1995р.

2. В.Д. Гетмнцев «Лінійна алгебра і лінійне програмування» 2001р.

3. Д. Мак-Кракен, У. Дорн «Программирование на ФОРТРАНЕ» 1997г