МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
Федеральне агентство з освіти
Державна освітня установа
Вищої професійної освіти
«Оренбурзький державний університет»
Факультет економіки і управління
Кафедра математичного забезпечення інформаційних систем
Курсова робота
з дисципліни «Чисельні методи»
Прямий метод обертання вікового визначника
ОДУ 061800.8006.18 ТОВ
Керівник роботи
____________________Ващук І.М.
«_____» _______________ 2006
Виконавець студент гр. 04ММЕ
________________Шіробоков П.Д.
«_____» ________________ 2006
Оренбург 2006

Зміст
Введення. 3
Постановка завдання .. 4
Опис методу. 5
Збіжність методу. 8
Опис вхідних та вихідних даних .. 9
Висновок. 10
Список літератури .. 11
Додаток А. .. 12
Додаток Б.. 19

Введення

Чисельні методи вирішення проблеми власних значень до кінця 40-х років, зводилися, в основному, до вирішення характеристичного рівняння. При реалізації такого підходу, основні зусилля були спрямовані на розробку ефективних методів швидкого обчислення коефіцієнтів характеристичного рівняння. Такі методи мають назви прямих. Популярним методом цього типу є метод Данилевського. Він давав досить велику похибку, але в той же час мав дуже велику швидкість отримання результату.
Ми зробимо спробу аналізу можливості використання цього методу в сучасних умовах. Спробуємо визначити можливі межі застосування цього методу, і так само знайти галузі науки, де користуватися методом Данилевського було б дуже зручно.

Постановка завдання

Велика кількість задач математики і фізики вимагає відшукання власних значень і власних векторів матриць, тобто відшукання таких значень + , Для яких існують нетривіальні рішення однорідної системи лінійних алгебраїчних рівнянь
, (1)
і відшукання цих нетривіальних рішень.
Тут -Квадратна матриця порядку m, - Невідомий вектор - стовпець.
З курсу алгебри відомо, що нетривіальне рішення системи (1) існує тоді і тільки тоді, коли
, (2)
де Е - одинична матриця. Якщо розкрити визначник , Отримаємо алгебраїчне рівняння ступеня m щодо . Таким чином проблема віднайдення власних значень зводиться до проблеми розкриття визначника за ступенями і подальшого рішення алгебраїчного рівняння m - го ступеня.
Визначник називається характеристичним (чи віковим) визначником, а рівняння (2) називається характеристичним (чи віковим) рівнянням.
Розрізняють повну проблему власних значень, коли необхідно відшукати всі власні значення матриці А і відповідні власні вектори, і часткову проблему власних значень, коли необхідно відшукати тільки деякі власні значення, наприклад, максимальне по модулю власне значення.

Опис методу

Ідея методу Данилевського полягає в тому, що матриця А приводиться до "нормальної формі Фробеніуса", яка має вигляд: .
Характеристичне рівняння для матриці Р має простий вигляд

тобто коефіцієнти при ступенях характеристичного полінома безпосередньо виражаються через елементи першого рядка матриці Р.
Приведення матриці А до нормальної форми Фробеніуса Р здійснюється послідовно построк, починаючи з останнього рядка.
1. Наведемо матрицю
до виду
Нехай Можна перевірити, що такий вигляд має матриця , Яка дорівнює
де

Наступний крок - приведення подібним перетворенням до .
Таким чином
І так далі:
2. Розглянемо нерегулярний випадок, коли матриця, отримана в результаті таких перетворень наведена вже до виду
і елемент .
Таким чином звичайна процедура методу Данилевського не підходить із-за необхідності поділу на нуль. У цій ситуації можливе два випадки.
2.1 Припускаємо, що лівіше є елемент Тоді домножимо матрицю ліворуч і праворуч на елементарну матрицю перестановок , Отримуємо матрицю .
У результаті на необхідному нам місці виявляється ненульовий елемент , Вже перетворена частина матриці не змінюється, можна застосовувати звичайний крок методу Данилевського до матриці .
2.2 Розглянемо другий нерегулярний випадок, коли в матриці елемент і всі елементи лівіше, теж нульові. У цьому випадку характеристичний визначник матриці можна представити у вигляді
де і - Одиничні матриці відповідної розмірності, а квадратні матриці і імєєют вигляд:
Звернемо увагу на те, що матриця вже має нормальну форму Фробеніуса, і тому співмножники просто розгортається у вигляді многочлена з коефіцієнтами, рівними елементам першого рядка.
Співмножник потрібно перетворювати. Для розгортання можна застосовувати метод Данилевського, приводячи матрицю подібними перетвореннями до нормальної форми Фробеніуса.
Зазначений підхід стає незадовільним при обчисленні власних значень матриць, що мають порядок m в кілька десятків (і тим більше сотень). Зокрема, одним з недоліків є також те, що точність обчислення коренів многочлена високого ступеня даним методом надзвичайно чутлива до похибки (накапливающейся зі швидкістю геометричної прогресії) в коефіцієнтах, і на етапі обчислення останніх може бути в значній мірі загублена інформація на власні значення матриці .
Тести методу, ПЗ см. У Додатку Б.

Збіжність методу

Визначення. Квадратна матриця Р порядку m називається подібної матриці А, якщо вона представлена ​​у вигляді , Де S - невиродженная квадратна матриця порядку m.
Теорема. Характеристичний визначник вихідної і подібної матриці співпадають.
Доказ.

Ідея методу Данилевського полягає в тому, що матриця А подібним перетворенням наводиться, до так званої нормальної формі Фробеніуса
.
Теорема. Нехай є є власне значення, а є відповідний власний вектор матриці Р, яка подібна до матриці А, тобто
Тоді є власний вектор матриці А, відповідний власному значенню
Доказательство.Трівіально випливає з того, що
Домножимо ліву і праву частину цієї рівності зліва на S, маємо
А це і означає, що -Власний вектор матриці А, що відповідає власному значенню

Опис вхідних та вихідних даних

Вхідні параметри:
Квадратна матриця порядку n * n. Рекомендується, щоб вона була добре обумовлена.
Вихідні параметри:
Отримуємо коефіцієнти при ступенях характеристичного полінома. Вирішуючи дане рівняння отримуємо власні значення вихідної матриці. Наступним кроком є ​​визначення власних векторів.
.

Висновок

Позначимо деякі висновки по виконаній роботі:
Під час освоєння даного методу ми не могли пропустити деякі мінуси методу Данилевського:
- Похибка накопичується зі швидкістю геометричної прогресії.
- Доводиться вирішувати досить складне рівняння порядку n (якщо вирішувати за допомогою наближених метод, знову отримуємо деяку похибка)
- У програмному варіанті використовуються досить великі обсяги оперативної пам'яті, наприклад, доводиться зберігати до 4 матриць порядку n * n.
Але так само не можна не зупинитися на очевидних плюсах методу:
- Метод зручний для знаходження власних векторів практично будь-якої матриці. Рекомендується розглядати матриці менше порядку декількох десятків.
- Цей метод дуже зручний у програмуванні (на етапі розробки ПЗ проблем практично не виникало).
У цілому метод все-таки не рекомендується для вирішення завдань, що вимагають високих точностей. Але через свою простоту, і високої швидкості, підходить для великих масивів, що не вимагають відсутність похибки.

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

1. Основи чисельних методів: Підручник для вузів / В.М. Вержбицький. - М.: Вищ. Шк., 2002. - 840 с.: Іл.
2. Вища математика для економістів: Підручник для вузів / Н.Ш. Кремер, Б.А. Путко, І.М. Тришин, М.М. Фрідман; Під ред. проф. Н.Ш. Кремера. - 2-е вид., Перераб. і доп. - М.: ЮНИТИ, 2004. - 471 с.
3. Інтернет.
4. Біблія Delphi / М.Є. Флен - СПб.: БХВ-Петербург, 2005. - 880 с.: Іл.

Додаток А

unit MainUnit;
interface
uses
Windows, ..., Buttons;
type
Matrix = array of array of real;
TForm1 = class (TForm)
...
private
{Private declarations}
/ / Процедура "перестановки" матриці, повертає true якщо все добре
function Remove (Var rez: Matrix; i: integer): boolean;
/ / Множення 2-х матриць
procedure Multiple (a, b: Matrix; Var rez: Matrix);
/ / Повернення рішень
function FindDet (Var a: Matrix): string;
/ / Обнулення матриць
procedure Zero (Var a: Matrix);
public
{Public declarations}
end;
var Form1: TForm1;
implementation
{$ R *. dfm}
function TForm1.FindDet (Var a: Matrix): string;
Var i, j: integer;
M, Mob, bac: Matrix;
flag: boolean;
begin
SetLength (M, Length (a [1]), Length (a [1]));
SetLength (Mob, Length (a [1]), Length (a [1]));
SetLength (bac, Length (a [1]), Length (a [1]));
flag: = true;
for i: = Length (a [1]) -2 downto 0 do
/ / Побудова матриць
BEGIN
/ / Обробка випадку 2.1
if (a [i +1, i] = 0) and (not Remove (a, i)) then
begin
/ / Якщо нічого не допомогло
flag: = false;
Break;
end;
/ / Обнулення всіх матриць
Zero (M); Zero (Mob); Zero (bac);
/ / Побудова матриць М
for j: = 0 to Length (a [i]) -1 do
begin
Mob [j, j]: = 1;
Mob [i, j]: = a [i +1, j];
M [j, j]: = 1;
M [i, j]: =- Mob [i, j] / a [i +1, i];
if i = j then M [i, j]: = 1 / a [i +1, i];
end;
/ / Множення матриці А на М
Multiple (a, M, bac); / / A * M
Multiple (Mob, bac, a); / / M ^ (-1) * (A * M)
END;
/ / Обробка випадку 2.2, якщо треба
if not flag then
begin
M: = nil;
Mob: = nil;
/ / Знаходимо матрицю С і виводимо її коефіцієнти
SetLength (bac, 1, length (a)-i-1);
for j: = i +1 to length (a) -1 do bac [0, ji-1]: = a [i, j]; / / Матриця C
Result :='('+ FloatToStrF (bac [0,0], ffFixed, 10,3);
for i: = 1 to Length (bac) -1 do
Result: = Result +','+ FloatToStrF (bac [0, i], ffFixed, 10,3);
Result: = Result +'),';
/ / "Урізати" матрицю А до стану B, див. 2.2 пункт алгоритму
SetLength (a, i +1, i +1);
/ / Викликаємо рекурсивно процедуру
Result: = Result + FindDet (a);
end
else begin
Result :='('+ FloatToStrF (a [0,0], ffFixed, 10,3);
for i: = 1 to Length (a) -1 do
Result: = Result +','+ FloatToStrF (a [0, i], ffFixed, 10,3);
Result: = Result +')';
end;
bac: = nil;
end;
procedure TForm1.bbPlusClick (Sender: TObject);
begin
sgInData.ColCount: = sgInData.ColCount +1;
sgInData.RowCount: = sgInData.RowCount +1;
if sgInData.ColCount = 11 then ShowMessage ('Attention! Отримані результати мають малу точність');
end;
procedure TForm1.bbMinusClick (Sender: TObject);
begin
if sgInData.ColCount <3 then Exit;
sgInData.ColCount: = sgInData.ColCount-1;
sgInData.RowCount: = sgInData.RowCount-1;
end;
procedure TForm1.bbOpenClick (Sender: TObject);
Var k: real;
f: textfile;
a, i, j: integer;
begin
OpenDialog1.Filter: = 'Всі файли (*.*)|*.*| Файли. Txt (*. txt) | *. TXT';
OpenDialog1.Title: = 'Вибір файлу для цієї проги';
OpenDialog1.FilterIndex: = 2;
if OpenDialog1.Execute then
begin
AssignFile (f, OpenDialog1.FileName);
Reset (f);
end
else Exit;
ReadLn (f, a);
sgInData.ColCount: = a;
sgIndata.RowCount: = a;
for i: = 0 to a-1 do
begin
for j: = 0 to a-1 do
begin
Read (f, k);
sgIndata.Cells [j, i]: = FloattoStr (k);
end;
ReadLn (f);
end;
CloseFile (f);
end;
procedure TForm1.bbFindClick (Sender: TObject);
Var a: matrix;
i, j: integer;
begin
try
SetLength (a, sgInData.ColCount, sgInData.RowCount);
for i: = 0 to sgInData.RowCount-1 do
for j: = 0 to sgInData.RowCount-1 do a [i, j]: = StrToFloat (sgInData.Cells [j, i]);
except
begin
a: = nil;
ShowMessage ('STOP! Неправильний введення, перевірте вхідні дані');
Exit;
end;
end;
OutData.Clear;
OutData.Lines.Add ('Коефіцієнти характеристичного рівняння');
OutData.Lines.Add (FindDet (a));
a: = nil;
end;
procedure TForm1.Multiple (a, b: Matrix; var rez: Matrix);
var i, k, j: word;
Begin
for i: = 0 to Length (a [1]) -1 do
for k: = 0 to Length (a [1]) -1 do
begin
/ / Оновлення зайнятих матриць
rez [i, k]: = 0;
for j: = 0 to Length (a [1]) -1 do rez [i, k]: = rez [i, k] + a [i, j] * b [j, k];
end;
end;
function TForm1.Remove (var rez: Matrix; i: integer): boolean;
Var j, k: integer;
E, bac: Matrix;
begin
Result: = false;
for k: = 0 to i-1 do / / Шукаємо ненульовий елемент зліва
if rez [i +1, k] <> 0 then
begin
Result: = true;
Break;
end;
if not Result then Exit;
SetLength (E, Length (rez [1]), Length (rez [1]));
SetLength (bac, Length (rez [1]), Length (rez [1]));
for j: = 0 to Length (rez [1]) -1 do E [j, j]: = 1;
for j: = 0 to Length (rez [1]) -1 do
begin
/ / Міняємо два рядки місцями в матриці E
E [i, j]: =- E [i, j]-E [k, j];
E [k, j]: =- E [i, j]-E [k, j];
E [i, j]: =- E [i, j]-E [k, j];
end;
Multiple (rez, E, bac); / / A * M
Multiple (E, bac, rez); / / M ^ (-1) * (A * M)
E: = nil;
bac: = nil;
end;
procedure TForm1.Zero (var a: Matrix);
Var i, j: integer;
begin
for i: = 0 to Length (a) -1 do
for j: = 0 to Length (a [0]) -1 do a [i, j]: = 0;
end;
end.

Додаток Б

Результати роботи програми з тими ж вхідними даними:
Рис 1.

Додаток Б
(Продовження)






Результати роботи програми з тими ж вхідними даними:
Рис 2.