Методичка 1 Численные

ВСТУП

З розвитком обчислювальної техніки велика увага приділяється чисельним методам, які широко застосовуються для розв’язку математичних, технічних і економічних задач. Серед них виділяють клас чисельних мето-

дів, які називаються чисельними методами лінійної алгебри. Сюди належать методи розв’язування систем лінійних алгебраїчних рівнянь (СЛАР), а також методи знаходження власних значень і векторів матриць.

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

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

У методичних вказівках наведені різні модифікації методу виключення Гаусса, орієнтовані на застосування для матриць різноманітної структури, які часто виникають у практичних завданнях. Також розглянуті питання зумовленості систем лінійних алгебраїчних рівнянь, методи знаходження оберненої матриці, а також принципи побудови ітераційних методів і найпоширеніші ітераційні методи розв’язку СЛАР – це метод простої ітерації та метод Зейделя.

ЛАБОРАТОРНА РОБОТА № 1. ТИПИ МАТРИЦЬ ТА ОСНОВНІ ДІЇ З НИМИ

1.1. Мета роботи

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

1.2. Теоретичний матеріал

1.2.1. Основні визначення Прямокутною матрицею називається сукупність чисел, загалом

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

або скорочено у вигляді

A aij , i 1, m; j 1, n .

Якщо n m , то матриця називається квадратною. У цьому випадку величина n називається її порядком.

Дві матриці називаються рівними, якщо їх відповідні елементи є рівними між собою.

У діагональних матрицях відмінні від нуля тільки елементи, що розташовані уздовж діагоналі:

Якщо всі числа i при цьому рівні між собою та дорівнюють деякому числу α, матриця називається скалярною. У випадку, якщо 1 –

де ij – символ Кронекера, тобто ij 0 при i j , ii 1 .

Матриця, всі елементи якої дорівнюють нулю, називається нульовою. Позначається символом 0.

Переставивши в матриці А рядки зі стовпцями одержимо транспоновану матрицю Ат . Квадратна матриця А дорівнює транспонованої Ат тільки в тому випадку, коли вона симетрична, тобто аij аji .

За допомогою заміни елементів матриці на комплексно-спряжені числа переходимо до комплексно-спряженої матриці А . Якщо елементи ма-

триці дійсні, то А А.

Матриця комплексно-спряжена із транспонованою називається мат-

рицею, спряженою з матрицею А, тобто A* Aт . Очевидно, А* * А.

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

Визначником квадратної матриці А називається число

ai i , i 1, n – елементи визначника.

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

Рангом матриці А називається максимальний порядок відмінних від нуля мінорів матриці. Позначається rg A .

1.2.2. Дії з матрицями Добутком матриці А на скаляр називається матриця, елементи

якої отримані з елементів матриці А множенням на число , тобто

A aij , i 1, m; j 1, n A aij , i 1, m; j 1, n .

Сумою двох прямокутних матриць А і В, що мають однакове число рядків і стовпців, називається матриця С, елементи якої дорівнюють сумам відповідних елементів матриць А і В:

A aij , В bij ,i 1, m; j n C cij aij bij , i 1, m; j 1, n .

Дані операції мають такі властивості:

1.А В С А В С ;

2.А В В А;

3.А 0 А;

4.А А А;

5.А В А В ;

6.1 А А;

7.А А.

Множення матриць А і В визначається тільки в припущенні, що число стовпців матриці А дорівнює числу рядків матриці В. Тоді елементи добутку С визначаються в такий спосіб: елемент i-го рядка й j-го стовпця матриці С дорівнює сумі добутків елементів i-го рядка матриці А на відповідні елементи j-го стовпця матриці В:

n

A aij , i 1, m; j 1, n, В bjk , j 1, n; k 1, p C cik aijbjk .

j 1

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

АпАт Ап т,Ап т Апт,

тобто степені однієї й тієї ж матриці переставні.

Вираз вигляду Рп А 0 Ап 1Ап 1 пЕ , де 0 , 1, , п – комплексні числа, називається поліномом від матриць або матрич-

ним поліномом.

Полином від матриці можна розглядати як результат підстановки матриці А замість змінної x в алгебраїчний поліном

Рп х 0 хп 1хп 1 п .

Правила дій над матричними поліномами аналогічні правилам дій над алгебраїчними поліномами.

1.2.4. Розбиття матриць на клітки. Обведені й квазідіагональні матриці

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

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

Дії над облямованими матрицями проводяться відповідно до загальних правил дій над клітинними матрицями. Нехай А и В – дві облямовані матриці порядку n:

Тут МР і их – матриці (n-1)-го порядку; Му і ub – стовпці, що складаються з (n-1)-го елемента; vР і ax – аналогічні рядки; vy+ab – число.

9

Квазідіагональною матрицею називається квадратна матриця, у якої уздовж головної діагоналі розташовані квадратні клітки, а інші елементи дорівнюють нулю. Наприклад, квазідіагональна матриця 7-го порядку:

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

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

1.2.5. Обернена і приєднана матриці

Квадратна матриця A aij називається неособливою (невиро-

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

необоротною).

Матриця В називається оберненою до квадратної матриці А, якщо

АВ BA Е . Обернена матриця позначається А 1 .

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

Алгебраїчним доповненням Aij елемента aij визначника n-го порядку називається його мінор Mij , взятий зі знаком 1 i j , тобто

Aij 1 i j Mij .

Приєднана матриця являє собою матрицю алгебраїчних доповнень Aij елемента aij у визначнику матриці А:

10

Тоді обернена матриця може бути знайдена через приєднану за наступною формулою:

Обернена матриця має такі властивості:

1. Визначник оберненої матриці є число, зворотне визначнику вихідної матриці, тобто det А 1 det1 A .

2.Обернена матриця від оберненої матриці є вихідна матриця, тобто

А 1 1 А.

3.Обернена матриця від добутку двох матриць є добуток обернених

матриць у зворотному порядку, тобто А1А2 1 А2 1А1 1 .

1.2.6. Характеристичний поліном. Власні значення матриці

Характеристичним або віковим рівнянням матриці A aij

називається рівняння

Ліва частина цього рівняння, яку можна записати скорочено у вигляді det A E , називається характеристичним поліном матриці.

Безпосереднє обчислення характеристичного полінома являє значні технічні труднощі. Дійсно, якщо

det A E 1 n n p1 n 1 p2 n 2 pn ,

тоді

11

p1 a11 a22 ann ,

pn 1 n 1 det A .

Інші коефіцієнти pk є взяті зі знаком 1 k 1 суми всіх мінорів визначника матриці А порядку k, що опираються на головну діагональ. Число таких мінорів дорівнює числу сполучень Cnk .

Корні i характеристичного полінома називаються власними зна-

ченнями або характеристичними числами матриці. З теореми Вієта, що дає зв'язок між коренями рівняння і його коефіцієнтами, витікає, що

1 2 n p1 a11 a22 ann ,1 2 n 1 n 1 pn det A .

Величина p1 a11 a22 ann називається слідом матриці А і позначається Sp A або tr A .

Для будь-якої матриці має місце співвідношення КеліГамільтона: якщо є характеристичним поліном матриці А, тоді

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

Полином найменшого степеня, який має властивість, що матриця є його коренем, називається мінімальним поліномом матриці.

Якщо А – матриця із власними значеннями 1, 2 , , n , серед яких можуть бути кратні, то власними значеннями полінома від матриці f A

є числа k1 , , kn .

1.2.7. Подібні матриці Матриця В називається подібною до матриці А, якщо існує така

неособлива матриця С, що В С 1АС . Говорять при цьому, що матриця В отримана з матриці А перетворенням подібності.

Перетворення подібності має наступні властивості:

12

С 1А1С С 1А2С С 1АnС C 1 А1 А2 Аn C, C 1А1С С 1А2С С 1АnС C 1 А1 А2 Аn C.

Зокрема, для будь-якого полінома f

C 1АС n C 1АnС ; f C 1АС C 1 f А С .

Отже, мінімальні поліноми подібних матриць однакові; подібні матриці мають також однакові характеристичні поліноми.

1.2.8. Ортогональні матриці Дійсна матриця називається ортогональною, якщо сума квадратів

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

Ортогональність матриці може бути охарактеризована матричною рівністю

АтА ААт Е .

Дійсно, діагональні елементи матриці АтА є сумами квадратів елементів стовпців матриці А, а недіагональні – дорівнюють сумам добутків відповідних елементів із двох різних стовпців.

Ортогональні матриці мають наступні властивості:

1.Одинична матриця ортогональна.

2.Якщо А – ортогональна матриця, то А 1 Ат . (Випливає з рівності АтА Е ).

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

виконання тих же умов для рядків Ат . Справді,

Ат т Ат ААт АА 1 Е .

4. Добуток двох ортогональних матриць є ортогональною матрицею. Дійсно, якщо А і В ортогональні матриці, тоді

АВ т АВ ВтАтАВ ВтЕВ Е .

5. Визначник ортогональної матриці дорівнює 1 або –1.

Властивість 5 визначає розбиття ортогональних матриць на два класи

– власно ортогональні з визначником +1 і невласно ортогональні

з визначником –1.

До класу ортогональних матриць належать елементарні матриці поворотів вигляду

де c2 s2 1 . Тобто існує такий кут , що с cos , s sin .

Елементарні матриці поворотів відрізняються від одиничної матриці лише чотирма елементами, що перебувають на перетині двох рядків і двох стовпців з номерами і та j, причому i j . Ці чотири елементи становлять

рення декартових координат на площині при повороті осей на кут . Елементарні матриці поворотів використаються як допоміжні для пе-

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

При лівому множенні матриці A a на матрицю Tij змінюються

Ясно, що якщо хоча б один із двох елементів ai і a j відмінний від нуля, то можна підібрати c і s так, щоб для матриці A(1) Tij A елемент a(j1) виявився рівним нулю. Для цього необхідно взяти

Твердження 1: Будь-яка дійсна невироджена матриця за допомогою ланцюжка множень ліворуч на елементарні матриці поворотів може бути перетворена в праву трикутну матрицю, всі діагональні елементи якої, крім, може бути, останнього, – додатні.

Твердження 2. Усяка невироджена дійсна матриця є добуток власно ортогональної на праву трикутну.

Дійсно, A PA n 1 , де P Tn 1n T12 1 , власно ортогональна матриця.

Твердження 3. Усяка власне ортогональна матриця є добуток елементарних матриць поворотів.

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

тобто якщо AтA AAт .

1.2.9. Ермітові матриці Матриця з комплексними елементами називається ермітовою, як-

що вона співпадає зі своєю спряженою, тобто aij a ji або в скороченому

запису A A* .

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

якої матриці з комплексними елементами матриця A* А буде ермітовою.

15

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

У середовищі візуального програмування створити клас «Матриця», що реалізує основні дії з дійсними прямокутними матрицями. Реалізувати властивості й методи, які дозволяють:

–увести розмір матриці;

–увести матрицю із клавіатури;

–заповнити матрицю випадковими числами в заданому діапазоні;

–автоматично згенерувати одиничну матрицю заданого порядку;

–додати дві матриці;

–помножити матрицю на скаляр;

–перемножити дві матриці;

–знайти слід квадратної матриці;

–транспонувати матрицю;

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

попереджувальних повідомлень про неможливість виконання будь-якої операції.

1.4. Контрольні запитання

1.Що називається матрицею?

2.Які матриці називають діагональними? Як вони позначаються?

3.Які матриці називаються скалярними? Як вони позначаються?

4.Які матриці називаються спряженими, а які комплексноспряженими?

5.Які основні дії з матрицями існують та які мають властивості?

6.Що називають степенем від матриці? Які властивості має степінь матриці?

7.Що називають матричним поліномом? Які існують правила дій з матричними поліномами?

8.Які матриці називають клітинними? Коли вони застосовуються? Які вони мають властивості?

9.Які матриці називають обведеними та які вони мають властивос-

ті?

10.Які матриці називають квазідіагональними та які вони мають властивості?

11.Які матриці називають оберненими та приєднаними? Які властивості оберненої матриці?

16

12.Що називають характеристичним поліномом матриці?

13.Що називають характеристичним рівнянням матриці?

14.Що називають власними значеннями матриці?

15.Що називають мінімальним поліномом матриці?

16.Які матриці називають подібними? Які вони мають властивості?

17.Які матриці називають ортогональними? Які вони мають власти-

вості?

18.На які класи поділяють ортогональні матриці?

19.Які матриці називають елементарними матрицями поворотів? Які вони мають властивості?

20.Які матриці належать до класу нормальних матриць?

21.Які матриці називають ермітовими?

ЛАБОРАТОРНА РОБОТА № 2. НОРМИ ВЕКТОРІВ ТА МАТРИЦЬ

2.1. Мета роботи

Метою роботи є вивчення матричних і векторних норм, що використовуються у практичних обчисленнях.

2.2. Теоретичний матеріал

2.2.1. Поняття норми вектора

Нормою вектора x називається зіставлене цьому вектору число x , що задовольняє наступним вимогам:

1.x 0 і x 0 тоді і тільки тоді, коли x 0 (додатна визначе-

ність);

2.cx c x при будь-якому числовому множнику c (однорід-

ність);

3.x yx y (нерівність трикутника).

Звимог 2 і 3 легко виводиться, що x yx y .

Кожна норма визначає «одиничну сферу» – множину векторів, норма яких не перевищує 1. Скористаємося наступними трьома нормами вектора

17

x x1, x2 , xn T , які визначені як для дійсного, так і для комплексного арифметичних просторів:

де величина x інтерпретується як максимальний за модулем компонент

вектора, тобто max xi . Таким чином, отримаємо:

i

норму також називають нормою найменших абсолютних різниць;

внює довжині вектора. Сукупність векторів, для яких x 2 1 , заповнює

сферу одиничного радіуса. У випадку евклідова простору другу векторну норму називають евклідовою;

1 x1 1, , 1 xn 1 . Іншими назвами кубічної норми вектора є sup-

норма або норма Чебишова.

Для випадку двовимірного арифметичного простору геометрична інтерпретація векторних норм наведена на рис. 2.1.

18

а) 1-норма вектора; б) 2- норма вектора; в) ∞-норма вектора

Рис. 2.1. Геометрична інтерпретація норм вектора

Уведені норми пов'язані між собою наступними нерівностями:

2.cА c А при будь-якому числовому множнику c;

3.А ВАВ ;

4.А ВАВ .

Часто вживаються наступні дві норми матриць:

M A n max aij ;

i, j

Очевидно, що ці норми задовольняють умовам 1–3, тому що вони є з точністю до множника n кубічною й сферичною нормами матриці, розгля-

нутої як вектор n2 -вимірного арифметичного простору. Умова 4 доводиться з нерівності Коши-Буняковського.

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

рма матриць погоджена з даною нормою вектора, якщо для будь-

якої матриці А і будь-якого вектора х виконується нерівність А Аxx.

Так, уведена норма M A погоджена з кубічної, октаедрічною і сферичною нормами вектора, N A – зі сферичної.

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

Внаслідок неперервності норми, для кожної матриці А цей максимум досягається, тобто знайдеться такий вектор x0 , що x0 1 й А 0 А . x

Побудована в такий спосіб норма задовольняє вимогам 1–4 і умові пого-

дженості й називається підпорядкованою даній нормі вектора або операторною нормою.

Таким чином, квадратна матриця А представляє лінійне перетворення (відображення) кожного вектора х одного n-вимірного простора Х у вектор y Ax іншого n-вимірного простора У.

Побудуємо норми матриць, підпорядковані уведеним нормам векто-

рів.

n

1. Октаедрична норма вектора x1 xi . Підлегла норма матриці

i 1

n

А1 maxk aik , тобто максимальна стовпчикова сума модулів елемен-

i 1

тів матриці. Цю норму також називають манхеттенскою;