Обчислення рангу матриці за допомогою обчислення її мінорів

2

Міністерство освіти і науки України

Закарпатський державний університет

ФАКУЛЬТЕТ ІНФОРМАТИКИ

КАФЕДРА ФІЗИКО-МАТЕМАТИЧНИХ ДИСЦИПЛІН

Реєстраційний №____

Дата ______________

КУРСОВА РОБОТА

з дисципліни «Вища математика»

Обчислення рангу матриці за допомогою обчислення її мінорів

Рекомендовано до захисту

«__» ____________ 2006 р.

Робота захищена

«__» ____________ 2006 р.

з оцінкою

Підписи членів комісії:

cтудента II курсу

денного відділення

Науковий керівник

Ужгород 2006 р.

Зміст

1. Вступ

2. Теоретичний виклад матеріалу

2.1 Означення мінору k-го порядку матриці

2.2 Теорема про ранг матриці

2.3 Правила обчислення рангу матриці

2.4 Приклади розв'язання завдань

3. Самостійна частина роботи

3.1 Опис програми

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

3.3 Приклад роботи програми

3.4 Контрольні приклади

4. Висновок

5. Використана література

1. Вступ

Означення рангу матриці випливає з означення рангу системи n-вимірних векторів.

Якщо задана деяка система n-вимірних векторів, то виникають питання:

1) Чи буде ця система векторів лінійно залежною, чи ні?

2) Як із будь-якої системи виділити максимальну лінійно- незалежну підсистему?

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

Наприклад, якщо задана така система векторів:

б = (2, -5, 1, -1), в = (1, 3, 6, 5), г = (-1, 4, 1, 2)

то на перший погляд важко знайти в ній якусь лінійну залежність, але насправді ці вектори зв'язані співвідношенням :

7б - 3в + 11г = 0

Це питання можна вирішити таким способом: оскільки компоненти заданих векторів нам відомі, то, враховуючи невідомими коефіцієнти шуканої лінійної залежності, ми отримаємо систему лінійних однорідних рівнянь, яку ми розв'язуємо методом Гаусса.

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

Як із будь-якої множини векторів виділити максимальну лінійно-незалежну підсистему підсистему? Довільну множину з s n-вимірних векторів довільним чином впорядковуємо. Ми дістанемо s! систем n-вимірних векторів. Нехай одна із таких систем. Для знаходження її максимальної лінійно-незалежної підсистеми векторів вилучаємо з даної системи всі нульові вектори. Далі вилучаємо всі ті вектори системи, які лінійно виражаються через попередні вектори цієї системи. Для кожної із s! систем вибираємо максимальну лінійно-незалежну підсистему. Зрозуміло, що вектори різних підсистем можуть не співпадати. Для лінійно-незалежних підсистем спільним є те, що кількість векторів є однаковою. Цю кількість векторів, тобто кількість векторів будь-якої максимальної лінійно-незалежної підсистеми називається рангом цієї множини векторів.

2. Теоретичний виклад матеріалу

2.1 Означення мінору k-го порядку матриці

Нехай дано матрицю

A = ,

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

Ранг системи стовбців, тобто максимальне число лінійно-незалежних стовбців матриці А, називається рангом цієї матриці.

Зрозуміло, що таким самим способом можна розглядати рядки матриці А, як n-вимірні вектори

Спочатку розглянемо поняття мінора прямокутної матриці. Виберемо в матриці А будь-які k-рядків і k-стовбців, k ? min(s,n).

Елементи, які стоять на перетині цих рядків і стовбців, утворюють квадратну матрицю k-го порядку, детермінант якої називається мінором k-го порядку матриці А. Далі нас будуть цікавити порядки тих мінорів матриці А, які відмінні від нуля, а точніше найвищий серед цих порядків. При його знаходженні можна користуватися тим, що якщо всі мінори k-го порядку матриці А рівні нулю, то рівні й нулю всі мінори більш високих порядків. Насправді, розкладаючи будь-який мінор порядку k+j, k < k+j ? min(s,n), використовуючи терему Лапласа по будь-яким k рядкам ми представимо цей мінор у вигляді суми мінорів порядку k, помножених на деякі мінори порядку j, і цим доведемо, що він рівний нулю.

2.2 Теорема про ранг матриці

Доведемо тепер теорему про ранг матриці:

Найвищий порядок відмінних від нуля мінорів матриці А рівний рангу цієї матриці.

Доведення:

Нехай, найвищий порядок відмінних від нуля мінорів матриці А рівний нулю. Виберемо мінор n-го порядку D

A = ,

відмінний від нуля, D?0. Будемо вважати, що це не порушить загальності доведення. D?0, тоді перші n стовбців матриці А будуть між собою лінійно-незалежні: якби між ними існувала лінійна залежність, то так як при додаванні векторів додається відповідні компоненти між стовбцями мінора D існувала б та ж лінійна залежність і тому мінор D був би рівен нулю.

Доведемо тепер, що всякий l-ий стовбець матриці А, r < l ? n, буде лінійною комбінацією перших n стовбців. Беремо будь-яке і, 1 ? i ? s, і будуємо додатковий детермінант (r+1)-го порядку

Д_i = ,

отриманий обведенням мінору D елементами l-го стовбцю і і-го рядка. При будь-якому i детермінант Д_i рівний нулю. Дійсно, якщо і > r, то Д_i буде мінором (r+1)-го порядку нашої матриці А і тому рівний нулю через вибраний нами r. Якщо ж і ? r то Д_i вже буде мінором матриці А, так як не може бути отриманий ви кресленням з цієї матриці деяких її рядків і стовбців; але детермінант Д_i тепер буде містити два рівні рядки і, звідси, знову рівний нулю.

Розглянемо алгебраїчне доповнення елементів останнього рядка детермінанту Д_i . Алгебраїчним доповненням до елемента a_il служить, очевидно мінор D. Якщо ж 1 ? j ? r, то алгебраїчним доповненням до елемента a_ij в Д_i буде число

A_j = (-1)^(r+1)+j ;

воно не залежить від і і тому позначене через А_j. Таким чином, розкладаючи детермінант Д_i по його останньому рядку і прирівнюючи цей розклад нулю, так як Д_i=0 ми отримаємо

a_i1A_i + a_i2A₂ + … + a_irA_r + a_ilD = 0,

звідки D?0 ;

a_i1 = ,

Ця рівність справедлива при всіх і, і=1,2,…,S, а так як його коефіцієнти від і не залежать, то весь l-ий стовбець матриці А буде сумою її перших r стовбців, взятих відповідно з коефіцієнтами . Таким чином в системі стовбців матриці А ми знайшли максимальну лінійно-незалежну підсистему, утворену з r стовбців. Цим доказано, що ранг матриці А рівний r, тобто теорема доведена.

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

2.3 Правила обчислення рангу матриці.

Метод знаходження рангу матриці, оснований на теоремі про ранг вимагає обчислення хоча і кінцевої, але, може бути і дуже великої кількості мінорів цієї матриці. Наступне зауваження дозволяє внести в цей метод значні спрощення. Якщо ще раз передивитися доведення теореми про ранг, то можна побачити, що ми не використовували при його проведенні рівність нулю всіх мінорів (r+1)-го порядку матриці А- в дійсності використовувалися лише ті мінори (r+1)-го порядку, котрі обводять даний не рівний нулю мінор r-го порядку D ( тобто мітять його повністю всередині себе), і тому з рівності нулю лише цих мінорів витікає, що r - це максимальне число лінійно-незалежних стовбців матриці А; останнє веде за собою рівність нулю всіх мінорів (r+1)-го порядку цієї матриці. Ми приходимо до наступного правила обчислення рангу матриці :

При обчисленні рангу матиці потрібно переходити від мінорів менших порядків до мінорів більших порядків. Якщо вже знайдений мінор k-го порядку D, відмінний від нуля, то потребують обчисленню лише мінори (k+1)-го порядку, які обводять мінор D: якщо всі вони рівні нулю, то ранг матриці рівний k.

В ролі наслідку з теореми про ранг матриці доведемо твердження:

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

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

2.4 Приклади розв'язання завдань

Приклад 1.

Знайти ранг матриці :

А = .

Розв'язання:

Мінор 2-го порядку, який стоїть в лівому верхньому куті матриці рівний 0. Але в матриці є і відмінні від нуля мінори другого порядку, наприклад

= ?0.

Мінор 3-го порядку

= ,

Який обводить мінор d , відмінний від нуля, , але обидва мінори 4-го порядку, які обводять мінор , рівні нулю :

= 0, = 0.

Таким чином, ранг матриці А рівний трьом.

Приклад 2.

Знайти максимальну лінійно-незалежну підсистему в системі векторів:

Розв'язання:

Складаємо матрицю

A = ,

для якої вектори служать стовбцями . Ранг цієї матриці рівний двом: мінор 2-го порядку, який стоїть в лівому верхньому куті, відмінний від нуля, але обидва мінори третього порядку, які його обводять, рівні нулю. Звідси випливає, що вектори , складають в заданій системі одну з максимальних лінійно-незалужних підсистем.

Приклад 3.

Знайти ранг матриці:

А = ,

Розв'язання: Кількість рядків матриці А дорівнює 3. Кількість її стовбців дорівнює 4. Отже, R(A) ? min{3,4} = 3. Матриця А - ненульова матриця, тому R(A) ? 1. Таким чином, 1 ? R(A) ? 3

Мінор 2-го порядку

= 1 ? 0.

Отже R(A) ? 2. Мінори третього порядку,які утворені обведенням цього, відмінного від нуля, мінору другого порядку, дорівнюють:

= 0, = 0, = 0,

таким чином, R(A) = 2.

3. Самостійна частина роботи

3.1 Опис програми

Програма по обчисленню рангу введеної матриці, текст якої наведений нижче написана на мові програмування Pascal в середовищі програмування Delphi 7. Вона складається з основної програми - Main.pas і модуля Rank.pas. Все обчислення проходить в модулі Rank.pas.

В ньому знаходяться: функція по обчисленню детермінанта введеної матриці, процедури по заміні місцями рядків і стовбців матриці, а також процедура обчислення рангу матриці. Всі інші процедури є додатковими - їхня роль тільки в візуальному оформленні програми.

При запуску програми з самого початку на екрані комп'ютера створюється пустее вікно. Спочатку потрібно задати параметри матриці і ввести її значення.

Це можна зробити двома способами:

1) Вибрати закладку «Файл», потім вибрати з меню «Задати параметри» і ввести кількість рядків і кількість стовбців матриці.

2) Після цього потрібно буде ввести значення матриці.

3) Вибрати закладку «Файл», потім вибрати з меню «Додати рядок» або «Додати стовбець «. Після цього потрібно ввести значення матриці.

Після введення значень матриці потрібно вибрати закладку «Файл» і вибрати з меню «Обчислити».

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

Якщо після обчислення рангу введеної матриці, користувач хоче знайти ранг іншої матриці, то потрібно вибрати закладку «Файл» і потім вибрати з меню «Очистити», після цього програма забере з вікна введену матрицю і можна вводити нову матрицю.

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

Модуль Rank.pas

unit Rank;

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

Dialogs, Grids, Menus, StdCtrls, Spin, Calendar, ExtCtrls;

Type

TArray=Array[1..20,1..20]of Real;

type

TForm1 = class(TForm)

StringGrid1: TStringGrid;

MainMenu1: TMainMenu;

N1: TMenuItem;

N2: TMenuItem;

N3: TMenuItem;

N4: TMenuItem;

N5: TMenuItem;

N6: TMenuItem;

N7: TMenuItem;

Label1: TLabel;

Label2: TLabel;

SpinEdit1: TSpinEdit;

SpinEdit2: TSpinEdit;

Label3: TLabel;

Label4: TLabel;

Button1: TButton;

Label5: TLabel;

N8: TMenuItem;

N9: TMenuItem;

procedure N2Click(Sender: TObject);

procedure N3Click(Sender: TObject);

procedure N4Click(Sender: TObject);

procedure N5Click(Sender: TObject);

procedure N6Click(Sender: TObject);

procedure N7Click(Sender: TObject);

procedure Button1Click(Sender: TObject);

procedure N8Click(Sender: TObject);

procedure N9Click(Sender: TObject);

private

{ Private declarations }

public

{ Public declarations }

end;

var

Form1: TForm1;

implementation

{$R *.dfm}

procedure TForm1.N2Click(Sender: TObject);

begin

Form1.N8.enabled:=true;

label5.Visible:=true;

form1.N7.Enabled:=false;

stringgrid1.Visible:=true;

stringgrid1.Rowcount:=stringgrid1.Rowcount+1;

stringgrid1.height:=stringgrid1.height+35;

form1.N6.enabled:=true;

end;

procedure TForm1.N3Click(Sender: TObject);

begin

form1.N7.Enabled:=false;

form1.N8.enabled:=false;

label5.Visible:=true;

Form1.N6.enabled:=true;

stringgrid1.Visible:=true;

stringgrid1.ColCount:= stringgrid1.ColCount+1;

stringgrid1.Width:=stringgrid1.Width+65;

stringgrid1.Left:=Trunc((Form1.Width-stringgrid1.Width)/2);

end;

procedure TForm1.N4Click(Sender: TObject);

begin

form1.N7.Enabled:=false;

form1.N8.enabled:=false;

Form1.N6.enabled:=true;

label5.Visible:=true;

stringgrid1.Visible:=true;

stringgrid1.RowCount:=stringgrid1.RowCount-1;

stringgrid1.height:=stringgrid1.height-35;

end;

procedure TForm1.N5Click(Sender: TObject);

begin

form1.N7.Enabled:=false;

form1.N8.enabled:=false;

label5.Visible:=true;

Form1.N6.enabled:=true;

stringgrid1.Visible:=true;

stringgrid1.colcount:=stringgrid1.colcount-1;

stringgrid1.Width:=stringgrid1.Width-65;

stringgrid1.Left:=Trunc((Form1.Width-stringgrid1.Width)/2);

end;

Function Det( n:Byte; c:TArray):Real; {Це функція, яка обчислює детермінант матриці}

Var

i,j,k:Byte;

b,t:Real;l:Integer;s:String;

Label 1,2,3;

Begin

{}

b:=1;k:=1;

Repeat

if c[k,k]=0 then begin

For i:=k+1 to n do

if c[k,i]<>0 then begin

For j:=1 to n do

c[j,k]:=c[j,k]+c[j,i];

goto 1;

End else

if i=n then begin

b:=0;goto 2;

End;

End;

1:For i:=k+1 to n do begin

if c[i,k]<>0 then begin

t:=c[i,k]/c[k,k];j:=k;

Repeat

c[i,j]:=-c[k,j]*t+c[i,j];

inc(j);

Until j>n;

End;

End;

b:=b*c[k,k];

inc(k);

Until k>n;

2:Det:=b;

End;

Procedure r_el_per( s,t:Byte; Var c:TArray); {Це процедура, яка міняє місцями рядки}

Var

j:Byte;Temp:Real;

Begin

Temp:=c[s][j];

c[s][j]:=c[t][j];

c[t][j]:=Temp;

End;

Procedure s_el_per( s,t:Byte; Var c:TArray); {Це процедура, яка міняє місцями стовбці}

Var

i:Byte;Temp:Real;

Begin

Temp:=c[i][s];

c[i][s]:=c[i][t];

c[i][t]:=Temp;

End;

procedure TForm1.N6Click(Sender: TObject); {Це процедура, яка обчислює ранг матриці}

var

t,I,J,k,l,Rank,m,n:Byte;D:Real;

a,b:TArray;

i2,j2:integer;

s:string;

begin

form1.N8.enabled:=true;

for i2:=1 to (stringgrid1.rowcount) do

for j2:=1 to (stringgrid1.colCount) do

begin

a[i2,j2]:=strtofloat(stringgrid1.cells[j2-1,i2-1]);

end;

m:=stringgrid1.RowCount;

n:=stringgrid1.ColCount;

t:=0;D:=0;Rank:=0;

Repeat

For I:=1 to Rank do

For J:=1 to Rank do

b[I][J]:=a[I][J];

k:=Rank+1;l:=k;D:=0;

Repeat

For I:=1 to Rank do

b[I][Rank+1]:=a[I][l];

For J:=1 to Rank do

b[Rank+1][J]:=a[k][J];

b[Rank+1][Rank+1]:=a[k][l];

D:=Det(Rank+1,b);

if D=0 then Begin

inc(k);

if k>m then Begin

inc(l);k:=Rank+1;

if l>n then t:=1;

End;

End else Begin

inc(Rank);

if Rank<>k then r_el_per(Rank+1,k,a);

if Rank<>l then s_el_per(Rank+1,l,a);

End;

Until (t<>0) or (D<>0);

Until (t<>0) or (Rank=m) or (Rank=n);

str(rank,s);

label1.Visible:=true;

label2.Visible:=true;

label1.Caption:=s;

еnd;

procedure TForm1.N7Click(Sender: TObject);

begin

form1.N7.Enabled:=false;

form1.N8.enabled:=false;

label3.Visible:=true;

label4.Visible:=true;

spinedit1.Visible:=true;

spinedit2.Visible:=true;

button1.Visible:=true;

end;

procedure TForm1.Button1Click(Sender: TObject);

begin

form1.N8.enabled:=false;

label3.Visible:=false;

label4.Visible:=false;

stringgrid1.Visible:=true;

button1.Visible:=false;

stringgrid1.RowCount:=spinedit1.Value;

stringgrid1.ColCount:=spinedit2.Value;

spinedit1.Visible:=false;

spinedit2.Visible:=false;

stringgrid1.Width:=stringgrid1.Width+(stringgrid1.ColCount*35);

stringgrid1.Left:=Trunc((Form1.Width-stringgrid1.Width)/2);

stringgrid1.Height:=stringgrid1.Height+(stringgrid1.RowCount*20);

label5.Visible:=true;

Form1.N6.enabled:=true;

end;

procedure TForm1.N8Click(Sender: TObject);

var i,j:integer;

begin

form1.N7.Enabled:=true;

stringgrid1.Visible:=false;

label2.Visible:=false;

label1.Visible:=false;

for i:=0 to (stringgrid1.rowcount) do

for j:=0 to (stringgrid1.colcount) do

stringgrid1.Cells[i,j]:=' ';

form1.N6.enabled:=false;

spinedit1.Value:=0;

spinedit2.Value:=0;

stringgrid1.rowcount:=3;

stringgrid1.ColCount:=3;

stringgrid1.Width:=200;

stringgrid1.Left:=240;

stringgrid1.Height:=110;

label5.Visible:=false;

end;

procedure TForm1.N9Click(Sender: TObject);

begin

form1.Close;

end;

end.

Основна програма Main.pas

program Main;

uses

Forms,

Rank in 'Rank.pas' {Form1};

Type

TArray=Array[1..20,1..20]of Real;

{$R *.res}

begin

Application.Initialize;

Application.CreateForm(TForm1, Form1);

Application.Run;

end.

3.3 Приклад роботи програми

Так виглядає вікно програми при її запуску.

Таким способом можна ввести параметри матриці.



Це приклад роботи програми. Приклад взято з прикладів розв'язання завдань. Можна перевірити правильність роботи програми.

3.4 Контрольні приклади

Відповідь: 2 Відповідь: 2 Відповідь: 2 Відповідь: 2

Відповідь: 4

Висновок

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

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

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

Використана література

1. Курош А.Г., «Курс высшей алгебры», изд. 10, <<Наука>>, Москва, 1971 г., 432 стр.

2. Ф.Г. Ващук, С.С Поляк, І.О. Пономарьова, «Практикум з алгебри», Ужгород, 1997 р., 147ст.

3. Овчинников П.Ф., Яремчук Ф.П., Михайленко В.М.. Высшая математика - К.: Вища шк. Главное изд., 1987 г., 552 стр.