Розробка програми для алгоритму знаходження власних векторів і власних значень методом обертань Якобі
Зміст
Вступ
. Постановка задачі
. Опис алгоритмів і програм
.1 Основні відомості з лінійної алгебри. Власні значення та власні
вектори матриці
1.2 Знаходження власних векторів і власних значень матриць. Метод обертання Якобі
.3 Засоби формування інтерфейсу користувача
. Текст програми алгоритму методу обертання Якобі
. Результат роботи
. Вимоги до програмно-технічного забезпечення
. Інструкція користувача
Список використаних джерел
Вступ
Чисельні методи є одним з потужних
математичних засобів вирішення задачі. Найпростіші чисельні методи ми
використовуємо всюди, наприклад, витягуючи квадратний корінь на листку паперу.
Системи лінійних алгебраїчних рівнянь
виникають як проміжний або остаточний етап при вирішенні ряду прикладних задач,
що описуються диференціальними, інтегральними або системами нелінійних
(трансцендентних) рівнянь. Вони можуть з'являтися як етап в задачах
математичного програмування, статистичної обробки даних, апроксимації функцій,
при дискретизації крайових диференціальних задач методом кінцевих різниць,
методом кінцевих елементів, проекційними методами, в методі граничних
елементів, дискретних особливостей, панельному методі аеродинамічного
компонування літального апарату і т. д.
Матриці виникаючих систем можуть мати
різні структури і властивості. Вже зараз є потреба у вирішенні систем лінійних
алгебраїчних рівнянь з матрицями повного заповнення порядку декількох тисяч.
При вирішенні низки прикладних задач методом кінцевих елементів в ряді випадків
є системи, що володіють симетричними позитивно визначеними стрічковими
матрицями порядку декілька десятків тисяч з половиною ширини стрічки до тисячі.
І, нарешті, при використанні в ряді завдань методу скінченних різниць необхідно
вирішити системи різницевих рівнянь з розрідженими матрицями порядку мільйон.
Одним з найпоширеніших методів
вирішення систем лінійних рівнянь є метод обертань Якобі. Цей метод (який також
називають методом простих ітерацій) відомий в різних варіантах вже більше 200
років.
1. Постановка задачі
Завдання даної курсової роботи
полягає в розробці програми для алгоритму знаходження власних векторів і
власних значень методом обертань Якобі.
Першим завданням проекту є створення
зрозумілого меню користувача.
Ввід даних та отримання вірного
результату. Код меню користувача в додатку Б.
Друге завдання розробка функції що
дозволяє знаходити власні вектори та власні значення методом Якобі. Код
алгоритму в додатку А.
2. Опис алгоритмів і програм
.1 Основні відомості з лінійної алгебри.
Власні
значення та власні вектори матриці
Якщо А - квадратна матриця n-го
порядку і 
при 
, то число l називається власним значенням матриці, а ненульовий
вектор х - відповідним йому власним вектором. Перепишемо задачу в такому вигляді
(1)
Для існування нетривіального
розв’язку задачі (1) має виконуватися умова 
(2) Цей визначник являє собою
многочлен n-ї степені від l; його називають характеристичним многочленом.
Значить, існує n власних значень - коренів цього многочлена, серед яких можуть
бути однакові (кратні). Якщо
знайдено деяке власне значення, то, при підстановці його в однорідну систему
(1), можна визначити відповідний власний вектор. Будемо нормувати власні
вектори. Тоді кожному простому (не кратному) власному значенню відповідає один
(з точністю до напрямку) власний вектор, а сукупність всіх власних векторів, що
відповідають сукупності простих власних значень, лінійно-незалежна. Таким
чином, якщо всі власні значення матриці прості, то вона має п
лінійно-незалежних власних векторів, які утворюють базис простору.
Кратному власному значенню кратності
р може відповідати від 1 до р лінійно-незалежних власних векторів. Наприклад,
розглянемо такі матриці четвертого порядку:
(3)
В кожної з них характеристичне
рівняння приймає вигляд 
, а отже, власне значення 
і має кратність р=4. Проте в першої
матриці є чотири лінійно-незалежних власних вектора
(4)
У другої матриці є тільки один
власний вектор е1. Другу матрицю називають простою жордановою (або
класичною) підматрицею. Третя матриця має так звану канонічну жорданову форму
(по діагоналі стоять або числа, або жорданові підматриці, а інші елементи
дорівнюють нулеві).
Таким чином, якщо серед власних
значень матриці є кратні, то її власні вектори не завжди утворюють базис. Однак
і в цьому випадку власні вектори, що відповідають різним власним значенням,
являються лінійно-незалежними.[3, стор 156]
При розв’язуванні теоретичних і
практичних задач часто виникає потреба визначити власні значення даної матриці
А, тобто обчислити корені її вікового (характеристичного) рівняння
(A - lE) = 0 (2)
а також знайти відповідні власні
векторі матриці А. Друга задача є простішою, оскільки якщо корені
характеристичного рівняння відомі, то знаходження власних векторів зводиться до
відшукання ненульових розв’язків деяких однорідних лінійних систем. Тому ми в
першу чергу будемо займатися першою задачею - відшуканням коренів
характеристичного рівняння (2).
Тут в основному застосовуються два
прийоми: 1) розгортання вікового визначника в поліном n-го степеня D(l) = det(A - lE) з подальшим розв’язком
рівняння D(l) = 0 одним з відомих наближених, взагалі кажучи, способів (наприклад,
методом Лобачевського-Греффе) наближене визначення коренів характеристичного
рівняння (найчастіше найбільших по модулю) методом ітерації, без попереднього
розгортання вікового визначника.
Розгортання вікового визначника.
Як відомо, віковим визначником
матриці А = [aij] називається визначник вигляду
(l) = det(A - lE) = 
(1)
Прирівнюючи цей визначник до нуля,
одержуємо характеристичне рівняння
(l) = 0
Якщо потрібно знайти все коріння характеристичного
рівняння, то доцільно заздалегідь обчислити визначник (1).
Розгортаючи визначник (1), одержуємо
поліном n-го степеня
(2)
Де 
є сума усіх діагональних мінорів першого
порядку матриці А.
є сума всього діагонального мінору
другого порядку матриці А;
сума всіх діагональних мінорів
третього порядку матриці А і т.д. Нарешті
sn = det A.
Легко переконатися, що число
діагональних мінорів k-го порядку матриці А дорівнює
(k = 1, 2, …, n ).
Звідси одержуємо, що безпосереднє
обчислення коефіцієнтів характеристичного полінома (2) еквівалентно обчисленню
визначників різних порядків. Остання
задача, взагалі кажучи, технічно важко здійснена для скільки-небудь великих
значень n. Тому створені спеціальні методи розгортання вікових визначників
(методи обертання Якобі, А. М. Данілевського, Леверье, метод невизначених
коефіцієнтів, метод інтерполяції та ін.).
2.2 Знаходження власних векторів і
власних значень матриць. Метод обертання Якобі
Метод обертань Якобі застосовується
тільки для симетричних матриць 
(
= 
) і вирішує повну проблему власних значень і власних векторів
таких матриць. Він заснований на знаходженні за допомогою ітераційних процедур
матриці U в перетворенні подібності Λ = 
, а оскільки для симетричних матриць
А матриця перетворення подібності 
є ортогональною (
=
), то Λ = 
, де Λ - діагональна матриця з
власними значеннями на головній діагоналі
Нехай дана симетрична матриця А.
Потрібно для неї обчислити з точністю ε всі власні значення і
відповідні їм власні вектори. Алгоритм методу обертання наступний:
Нехай відома матриця
на k-й ітерації, при цьому для k = 0
= А.
. Вибирається максимальний по
модулю недіагональні елемент 
матриці 
.
Ставиться завдання знайти таку
ортогональную матрицю 
, щоб в результаті перетворення подібності 
=
відбулося обнулення елемента 
матриці . В якості ортогональної матриці
вибирається матриця обертання, що має наступний вигляд:
У матриці обертання на перетині i -
го рядка і j - го стовпця знаходиться елемент 
де 
- кут обертання, що підлягає
визначенню. Симетрично щодо головної діагоналі (j -й рядок, i -й стовпець)
розташований елемент 
. Діагональні елементи 
дорівнюють відповідно 
; інші діагональні елементи 
інші елементи у матриці обертання U(к)
дорівнюють нулю.
Кут обертання 
визначається з умови
:
,
причому якщо 
. Будується матриця , =,
в якій елемент 
.
Якщо 
то ітераційний процес:
=
триває. Якщо 
,то ітераційний процес зупиняється, і
в
якості шуканих власних значень
приймаються 
. Координатними стовпчиками власних
векторів матриці А в одиничному базисі будуть стовпці матриці
,тобто 
причому ці власні вектори будуть
ортогональні між собою, тобто
.
2.3 Засоби формування інтерфейсу
користувача
В додатку Б показаний код консольної
програми для взаємодії з користувачем. Користувач вводить розмірність
матриці(N). Після чого вводятся значення матриці. Коли значення введені
перевіряється функцією(isSimmetrial) чи
матриця симетрична. Якщо вона не симетрична програма почне роботу спочатку і
запропонує ввести дані знову. Якщо ж матриця симетрична програма за допомогою
функції(wrachenie) знайде власні вектори
та власні значення та видасть їх на екран.
обертання якобі інтерфейс
матриця
3. Текст програми алгоритму методу
обертання Якобі
using
System;System.Collections.Generic;System.Linq;System.Text;System.Threading.Tasks;yacobi_sharp
{Program
{void Main(string[]
args)
{i,
j;size;precision;.Write("Метод обертання
Якобi.");:.Write("\nВведiть розмiрнiсть матрицi(NxN) N = ");=
int.Parse(Console.ReadLine());[,] coefficients = new double[size, size];[,]
solution = new double[size, size];.Write("\nВведiть елементи матрицi:
\n");(i = 0; i < size; i++)
{(j = 0; j <
size; j++)
{[i, j] = 0;
}[i, i] = 1;
}(i = 0; i <
size; i++)
{(j = 0; j <
size; j++)
{.Write("A[{0}][{1}]:
", i + 1, j + 1);[i, j] = double.Parse(Console.ReadLine()); ;
}
}.Write("Сформована
матриця:\n");(i = 0; i < size; i++)
{(j = 0; j <
size; j++)
{.Write(" [{0}]
", coefficients[i, j]);
}.WriteLine();
}(!isSimmetrial(coefficients,
size))
{.Write("Матриця
не симетрична\n");.Write("Введіть данні матриці
знову!\n");error1;
}
{.Write("Введiть
точнiсть розрахунку(е): \n");= double.Parse(Console.ReadLine());steps =
wrachenie(coefficients, size, solution, precision);.Write("Рiшення:\n");(i
= 0; i < size; i++)
{.Write("Власний
вектор k {0} :\n", i + 1);(j = 0; j < size; j++)
{.Write(solution[j,
i] + "\n");
}
}.Write("Власні
значення:\n");(i = 0; i < size; i++)
{.Write(coefficients[i,
i] + "\n");
}.Write("Загальна
кiлькiсть крокiв: " + steps);.Write("\nPress \"Enter\" to
continue...");
}.ReadKey();
}static bool
isSimmetrial(double[,] coefficients, int numberOfEquation) /*функція перевірки
симетричності
матриці*/
{result = true;i,
j;(i = 0; i < numberOfEquation; i++)/*перевірка усіх елементів
матриці крім
головної дівгоналі*/
{(j = i + 1; j <
numberOfEquation; j++)
{(coefficients[i, j]
!= coefficients[j, i])
{= false;;
}
}(!result) { break;
}
}result;
}static int
wrachenie(double[,] coefficients, int numberOfEquation,[,] solution, double
precision)/*алгоритм обертання*/ {result = 1;i, j, k;maxI=0, maxJ=0;max, fi;[,]
matricaPoworota = new double[numberOfEquation, numberOfEquation];[,] temp = new
double[numberOfEquation, numberOfEquation];fault = 0.0;(i = 0; i < numberOfEquation;
i++)
{(j = i + 1; j <
numberOfEquation; j++)
{= fault +
coefficients[i, j] * coefficients[i, j];
}
}= Math.Sqrt(2 *
fault);(fault > precision)
{= 0.0;(i = 0; i
< numberOfEquation; i++)
{(j = i + 1; j <
numberOfEquation; j++)
{(coefficients[i, j]
> 0 && coefficients[i, j] > max)
{= coefficients[i,
j];= i;= j;
}if (coefficients[i,
j] < 0 && -coefficients[i, j] > max)
{= -coefficients[i,
j];= i;= j;
}
}
}(i = 0; i <
numberOfEquation; i++)
{(j = 0; j <
numberOfEquation; j++)
{[i, j] = 0;
}[i, i] = 1;
}(coefficients[maxI,
maxI] == coefficients[maxJ, maxJ])
{[maxI, maxI] =
matricaPoworota[maxJ, maxJ] =[maxJ, maxI] = Math.Sqrt(2.0) / 2.0;[maxI, maxJ] =
-Math.Sqrt(2.0) / 2.0;
}
(coefficients[maxI,
maxI] - coefficients[maxJ, maxJ]));[maxI, maxI] = matricaPoworota[maxJ, maxJ] =
Math.Cos(fi);[maxI, maxJ] = -Math.Sin(fi);[maxJ, maxI] = Math.Sin(fi);
}(i = 0; i <
numberOfEquation; i++)
{(j = 0; j <
numberOfEquation; j++)
{[i, j] = 0.0;
}
}(i = 0; i <
numberOfEquation; i++)
{(j = 0; j <
numberOfEquation; j++)
{(k = 0; k <
numberOfEquation; k++)
{[i, j] = temp[i, j]
+ matricaPoworota[k, i] * coefficients[k, j];
}
}
}(i = 0; i <
numberOfEquation; i++)
{(j = 0; j <
numberOfEquation; j++)
{[i, j] = 0.0;
}
}(i = 0; i <
numberOfEquation; i++)
{(j = 0; j <
numberOfEquation; j++)
{(k = 0; k <
numberOfEquation; k++)
{[i, j] =
coefficients[i, j] +[i, k] * matricaPoworota[k, j];
}
}
}= 0.0;(i = 0; i
< numberOfEquation; i++)
{(j = i + 1; j <
numberOfEquation; j++)
{= fault +
coefficients[i, j] * coefficients[i, j];
}
}= Math.Sqrt(2 *
fault);(i = 0; i < numberOfEquation; i++)
{(j = 0; j <
numberOfEquation; j++)
{[i, j] = 0.0;
}
}(i = 0; i <
numberOfEquation; i++)
{(j = 0; j <
numberOfEquation; j++)
{(k = 0; k <
numberOfEquation; k++)
{[i, j] = temp[i, j]
+ solution[i, k] * matricaPoworota[k, j];
}
}
}(i = 0; i <
numberOfEquation; i++)
{(j = 0; j <
numberOfEquation; j++)
{[i, j] = temp[i,
j];
}
}++;
}result;
}
}
}
4. Результат роботи
Запуск програми
Введення значень
Якщо матриця не симетричнa
Після правильно введених даних ввести
точність визначення
Результат
5. Вимоги до програмно-технічного
забезпечення
Створена програма не потребує високих
системних вимог для її функціонування, оскільки була протестована на комп’ютері
з наступними характеристиками:
операційна система -
Windows XP Professional;
частота процесора - 1,09
ГГц;
об’єм оперативної пам’яті -
512 Мб;
відеопам’ять відеокарти -
256 Мб.
Враховуючи, що програму було
розроблено на платформі.NET Framework 4.0, яка сумісна з операційними системами
Windows XP Professional та вище, мінімальні вимоги до системи наступні:
операційна система -
Windows: XP Professional, Vista, 7, 8;
частота процесора - 1 ГГц
та вище;
об’єм оперативної пам’яті -
512 Мб та вище;
відеопам’ять відеокарти -
256 Мб та вище;
вільна пам’ять на диску - 2
Мб;
програмна платформа -.NET
Framework 4.0 або вище.
6. Інструкція користувача
Запуск програми
Введення значень матриці А
Після величини матриці потрібно
ввести значення матриці.
Перевірка симетричності
Після введених даних йде перевірка
симетричності матриці оскільки тільки з такою матрицею працює метод Якобі. Якщо
матриця не симетрична програма повертається на момент введення величина
матриці. Якщо ж симетрична алгоритм
йде далі.
Введення точності
Після перевірки в минулому кроці
потрібно ввести точність ε.
Результат
Після правильного введення всіх даних
на екрані висвітиться результат
на екран. Буде показано власні
вектори та власні значення вказаної матриці.
Висновок
При виконанні даної курсової роботи
було вивчено метод обертання Якобі рішення симетрично повної проблеми власних
значень.
Цей метод при невеликих розмірах
матриць дає непогані результати, і дозволяє з великою точністю обчислювати
власні значення. При великих розмірах матриць реалізація методу наштовхується
на великі втрати машинних ресурсів (через необхідність пошуку максимального
елемента матриці, і перемноження матриць великої розмірності). Також різко
звужує можливість застосувати даний метод на практиці тому, що він може бути
застосований лише до симетричних матриць.
Зважаючи на вищесказане, цей метод на
практиці застосовується рідко, частіше застосовується циклічний метод Якобі з
бар'єрами. Швидкість збіжності якого так само асимптотично квадратична.
Список використаних джерел
1. Демидович Б. П., Марон І. А. Основи обчислювальної
математики. - 3-е вид. - М.: Наука, 1966. - 560 с.
. Ільїн В. А., Позняк Е. Г. Лінійна алгебра: Підруч.
Для вузів - 4-е вид. - М.: Наука. Фізмат.літ, 1999. - 296 с.
. Каліткін Н. Н. Чисельні методи. - М.: Мир, 1988. -
512 с.
. Мальцев А. І. Основи лінійної алгебри. - 3-вид. -
М.: Наука, 1968. - 402 с.
. Марчук Г. И. Методи обчислювальної математики - М.:
Наука, 1977. - 392с.
. Форсайт Дж., Малькольм М., Моулер К. Машинні методи
математичних обчислень: Пер. з англ. - М.: Мир, 1980. - 277 с.