» Урок 12. Ранг матриці. Обчислення рангу матриці. Норма матриць

Урок №12. Ранг матриці. Обчислення рангу матриці. Норма матриць.

Якщо всі мінори матриціAпорядкуkрівні нулю, всі мінори порядку k+1, якщо такі існують, теж рівні нулю.
Рангом матриці A називається найбільший із порядків мінорів матриці A , відмінні від нуля.
Максимум ранг може дорівнювати мінімальному числу з кількості рядків чи стовпців матриці, тобто. якщо матриця має розмір 4х5, максимум ранг буде 4.
Мінімум ранг матриці дорівнює 1, якщо ви не маєте справу з нульовою матрицею, там завжди ранг дорівнює нулю.

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

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

Визначник матриці дорівнює нулю.
Мінор другого порядку . Отже, r(A)=2 і базісний мінор.
Базовим мінором є також мінор .
Мінор , т.к. =0, тому буде базисним.
Завдання: самостійно перевірити, які ще мінори другого порядку будуть базисними, а які ні

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

Назвемо елементарними перетвореннями матриць такі дії з них:
1) перестановка рядків чи стовпців;
2) множення рядка або стовпця на число відмінне від нуля;
3) додавання до одного з рядків іншого рядка, помноженого на число або додавання до одного зі стовпців іншого стовпця, помноженого на число.

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

Нехай потрібно обчислити ранг матриці розмірів mxn.

В результаті розрахунків матриця А1 має вигляд

Якщо всі рядки, починаючи з третього, нульові, то , оскільки мінор . Інакше перестановкою рядків та стовпців з номерами, більшими за два, добиваємося, щоб третій елемент третього рядка був відмінний від нуля. Далі, додаванням третього рядка, помноженого на відповідні числа, до рядків з великими номерами отримуємо нулі в третьому стовпці, починаючи з четвертого елемента, і т.д.
На якомусь етапі ми прийдемо до матриці, у якої всі рядки, починаючи з (r+1)-ої, дорівнюють нулю (або відсутні при ), а мінор у перших рядках і перших стовпцях є визначником трикутної матриці з ненульовими елементами на діагоналі . Ранг такої матриці дорівнює. Отже, Rang(A)=r.

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

У лабораторно-практичній роботі розглянемо приклад знаходження рангу матриці.

АЛГОРИТМ ЗНАХОДЖЕННЯ НОРМИ МАТРИЦІ .
Виділяють лише три норми матриці.
Перша норма матриці= максимальному з чисел, отриманих при додаванні всіх елементів кожного стовпця, взятих по модулю.
Приклад: нехай дана матриця розміру 3х2 (рис.10). У першому стовпчику стоять елементи: 8, 3, 8. Усі елементи позитивні. Знайдемо їхню суму: 8+3+8=19. У другому стовпці стоять елементи: 8 -2 -8. Два елементи - негативні, тому при додаванні цих чисел, необхідно підставляти модуль цих чисел (тобто без знаків "мінус"). Знайдемо їхню суму: 8+2+8=18. Максимальне цих двох чисел - це 19. Значить перша норма матриці дорівнює 19.

Малюнок 10.

Друга норма матриціявляє собою квадратний корінь із суми квадратів всіх елементів матриці. А це означає, що ми зводимо в квадрат всі елементи матриці, потім складаємо отримані значення і з результату витягуємо квадратний корінь.
У нашому випадку, 2 норма матриці вийшла дорівнює квадратному кореню з 269. На схемі, я приблизно витягла квадратний корінь з 269 і в результаті отримала приблизно 16,401. Хоча більш правильно не витягувати коріння.

Третя норма матриціявляє собою максимальне з чисел, отриманих при додаванні всіх елементів кожного рядка, взятих по модулю.
У прикладі: у першому рядку стоять елементи: 8, 8. Усі елементи позитивні. Знайдемо їхню суму: 8+8=16. У другому рядку стоять елементи: 3 -2. Один з елементів негативний, тому при складанні цих чисел необхідно підставляти модуль цього числа. Знайдемо їхню суму: 3+2=5. У третьому рядку стоять елементи 8 і -8. Один з елементів негативний, тому при складанні цих чисел необхідно підставляти модуль цього числа. Знайдемо їхню суму: 8+8=16. Максимальне з трьох чисел - це 16. Значить третя норма матриці дорівнює 16.

Укладач: Салій Н.А.

Нормою матриціназвемо поставлене у відповідність до цієї матриці речове число ||A|| таке, що як речовинне число ставиться у відповідність кожної матриці з n-мірного простору і задовольняє 4 аксіомам:

1. ||A||³0 і ||A||=0, тільки якщо A – нульова матриця;

2. ||αA||=|α|·||A||, де a R;

3. ||A+B||£||A||+||B||;

4. ||A·B||£||A||·||B||. (Властивість мультиплікативності)

Норма матриць може бути введена у різний спосіб. Матрицю A можна розглядати як n 2 -мірний вектор.

Ця норма називається евклідовою нормою матриці.

Якщо для будь-якої квадратної матриці A та будь-якого вектора x, розмірність якого дорівнює порядку матриці, виконується нерівність ||Ax||£||A||·||||

то кажуть, що норма матриці A узгоджена із нормою вектора. Зауважимо, що зліва в останній умові стоїть норма вектора (Ax – вектор).

Із заданою векторною нормою узгоджено різні матричні норми. Виберемо серед них найменшу. Такою буде

Ця матрична норма - підпорядкована заданій векторній нормі. Існування максимуму у цьому вираженні випливає з безперервності норми, бо завжди існує вектор x -> ||x||=1 і ||Ax||=||A||.

Покажемо, що норма N(A) не підпорядкована жодній векторній нормі. Норми матриці, підпорядковані раніше введеним векторним нормам, виражаються так:

1. ||A|| ¥ = |a ij | (норма-максимум)

2. ||A|| 1 = | a ij | (норма-сума)

3. ||A|| 2 = , (спектральна норма)

де s 1- найбільше власне значення симетричної матриці A¢A, що є твором транспонованої та вихідної матриць. Т до матриця A A симетрична, то всі її власні значення речові і позитивні. Число l -власне значення, а ненульовий вектор x - власний вектор матриці A (якщо вони пов'язані між собою співвідношенням Ax = lx). Якщо ж матриця A сама є симетричною, A = A, то A = A 2 і тоді s 1 = , де - найбільше за модулем власне значення матриці A. Отже, в цьому випадку ми маємо = .

Власні числа матриці не перевищують будь-якої її узгоджених норм. Нормуючи визначальне власні числа співвідношення, отримаємо ||λx||=||Ax||, |λ|·||x||=||Ax||£||A||·||x||, |λ| £||A||

Бо справедливо ||A|| 2 £||A|| e де евклідова норма обчислюється просто, в оцінках замість спектральної норми можна використовувати евклідову норму матриці.

30. Обумовленість систем рівнянь. Коефіцієнт обумовленості .

Ступінь обумовленості- Вплив рішення на вихідні дані. Ax = b: вектор bвідповідає рішення x. Нехай bзміниться на величину. Тоді вектору b+буде відповідати нове рішення x+ : A(x+ ) = b+. Оскільки система лінійна, то Ax + A = b+тоді A = ; = ; = ; b = Ax; = тоді; * , де - відносна похибка обурення рішення, - коефіцієнт обумовленостіcond(A) (у скільки разів може зрости похибка рішення), - відносне обурення вектора b. cond(A) = ; cond(A)*Властивості коефіцієнта залежить від вибору норми матриці; cond( = cond(A); множення матриці на число не впливає коефіцієнт обумовленості. Чим більший коефіцієнт, тим більше позначається на рішенні СЛАУ помилка у вихідних даних. Число обумовленості не може бути менше 1.

31. Метод прогонки для вирішення систем лінійних рівнянь алгебри.

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

У трьох діагональної матриці ненульових елементів всього (3n-2).

Перевизначимо коефіцієнти матриці:

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

A i * x i-1 + b i * x i + c i * x i+1 = d i , i=1, 2,…, n; (7)

a 1 = 0, c n = 0. (8)

Структура системи передбачає взаємозв'язок між сусідніми невідомими:

x i = x i * x i +1 + hi (9)

x i -1 = x i -1 * x i + h i -1 і підставимо в (7):

A i (x i-1* x i + h i-1)+ b i * x i + c i * x i+1 = d i

(a i * x i-1 + b i) x i = -c i * x i +1 +d i -a i * h i-1

Порівнюючи отриманий вираз з поданням (7), отримуємо:

Формули (10) представляють рекурентні співвідношення для обчислення коефіцієнтів прогонки. Вони потребують завдання початкових значень. Відповідно до першої умови (8) для i = 1 маємо a 1 = 0, а значить

Далі обчислюються і зберігаються інші прогоночные коефіцієнти за формулами (10) для i=2,3,…, n, причому при i=n, ​​з урахуванням другої умови (8), отримуємо x n =0. Отже, відповідно до формули (9) x n = h n .

Після чого за формулою (9) послідовно знаходяться невідомі x n -1 x n -2 ... x 1 . Цей етап розрахунку називається зворотним ходом, у той час як обчислення прогоночних коефіцієнтів називається прямим ходом прогонки.

Для успішного застосування методу прогонки потрібно, щоб у процесі обчислень не виникало ситуацій із розподілом на нуль, а при великій розмірності систем не повинно бути швидкого зростання похибок округлення. Будемо називати прогін коректною, якщо знаменник прогоночних коефіцієнтів (10) не звертається в нуль, та стійкоюякщо ½x i ½<1 при всех i=1,2,…, n. Достаточные условия корректности и устойчивости прогонки, которые во многих приложениях выполняются, определяются теоремой.

Теорема. Нехай коефіцієнти a i і c i рівняння (7) при i=2,3,..., n-1 відмінні від нуля та нехай

½b i ½>½a i ½+½c i ½ при i=1, 2,..., n. (11)

Тоді прогін, що визначається формулами (10), (9) коректна і стійка.

Енциклопедичний YouTube

1 / 1

✪ Норма вектора. Частина 4

Субтитри

Визначення

Нехай K - основне поле (зазвичай K = R або K = C ) і - лінійний простір всіх матриць з m рядками і n стовпцями, що складаються з елементів K . На просторі матриць задана норма, якщо кожній матриці ставиться у відповідність невід'ємне дійсне число ‖ A ‖ (\displaystyle \|A\|), називане її нормою, так, що

У разі квадратних матриць (тобто m = n), матриці можна перемножувати не виходячи з простору, і тому норми у цих просторах зазвичай також задовольняють властивості субмультиплікативності :

Субмультиплікативність може виконуватися також і для норм неквадратних матриць, але визначених одночасно для кількох необхідних розмірів. Саме, якщо A – матриця ℓ  ×  m, і B - матриця m ×  n, то A B- матриця ℓ  ×  n .

Операторні норми

Важливим класом матричних норм є операторні норми, також іменовані підлеглими або індукованими . Операторна норма однозначно будується за двома нормами, визначеними в і, виходячи з того, що будь-яка матриця m ×  nпредставляється лінійним оператором з K n (\displaystyle K^(n))в K m (\displaystyle K^(m)). Саме,

‖ A ‖ = sup ( ‖ A x ‖ : x ∈ K n , ‖ x ‖ = 1 ) = sup ( ‖ A x ‖ ‖ x ‖ : x ∈ K n , x ≠ 0 ). (\displaystyle (\begin(aligned)\|A\|&=\sup\(\|Ax\|:x\in K^(n),\|x\|=1\)\\&=\ sup \left\((\frac (\|Ax\|)(\|x\|)):x\in K^(n),\ x\neq 0\right\).\end(aligned)))

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

Приклади операторних норм

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

1. Спектральна норма оператора дорівнює максимальному сингулярному числу цього оператора.
2. Спектральна норма нормального оператора дорівнює абсолютному значення максимального за модулем власного значення цього оператора.
3. Спектральна норма не змінюється при множенні матриці на ортогональну (унітарну) матрицю.

Неоператорні норми матриць

Існують норми матриць, що не є операторними. Поняття неоператорних норм матриць запровадив Ю. І. Любич та досліджував Г. Р. Білицький.

Приклад неоператорної норми

Наприклад, розглянемо дві різні операторні норми ‖ A ‖ 1 (\displaystyle \|A\|_(1))і ‖ A ‖ 2 (\displaystyle \|A\|_(2)), Наприклад рядкову та стовпцеву норми. Утворимо нову норму ‖ A ‖ = m a x (‖ A ‖ 1 , ‖ A ‖ 2) (\displaystyle \|A\|=max(\|A\|_(1),\|A\|_(2))). Нова норма має кільцеву властивість ‖ A B ‖ ≤ ‖ A ‖ ‖ B ‖ (\displaystyle \|AB\|\leq \|A\|\|B\|), зберігає одиницю ‖ I ‖ = 1 (\displaystyle \|I\|=1)і не є операторною.

Приклади норм

Векторна p (\displaystyle p)-норма

Можна розглядати m × n (\displaystyle m\times n)матрицю як вектор розміру m n (\displaystyle mn)та використовувати стандартні векторні норми:

‖ A ‖ p = ‖ v ec (A) ‖ p = (∑ i = 1 m ∑ j = 1 n | a i j | p) 1 / p (\displaystyle \|A\|_(p)=\|\mathrm ( vec) (A)\|_(p)=\left(\sum _(i=1)^(m)\sum _(j=1)^(n)|a_(ij)|^(p)\ right)^(1/p))

Норма Фробеніуса

Норма Фробеніуса, або евклідова нормаявляє собою окремий випадок p-норми для p = 2 : ‖ A ‖ F = ∑ i = 1 m ∑ j = 1 n a i j 2 (\displaystyle \|A\|_(F)=(\sqrt (\sum _(i=1)^(m)\sum _(j =1)^(n)a_(ij)^(2)))).

Норма Фробеніуса легко обчислюється (порівняно, наприклад, зі спектральною нормою). Має наступні властивості:

‖ A x ‖ 2 2 = ∑ i = 1 m | ∑ j = 1 n a i j x j | 2 ≤ ∑ i = 1 m (∑ j = 1 n | a i j | 2 ∑ j = 1 n | x j | 2) = ∑ j = 1 n | xj | 2 ‖ A ‖ F 2 = ‖ A ‖ F 2 ‖ x ‖ 2 2 . (\displaystyle \|Ax\|_(2)^(2)=\sum _(i=1)^(m)\left|\sum _(j=1)^(n)a_(ij)x_( j)\right|^(2)\leq \sum _(i=1)^(m)\left(\sum _(j=1)^(n)|a_(ij)|^(2)\sum _(j=1)^(n)|x_(j)|^(2)\right)=\sum _(j=1)^(n)|x_(j)|^(2)\|A\ |_(F)^(2)=\|A\|_(F)^(2)\|x\|_(2)^(2).)

• Субмультиплікативність: ‖ A B ‖ F ≤ ‖ A ‖ F ‖ B ‖ F (\displaystyle \|AB\|_(F)\leq \|A\|_(F)\|B\|_(F)), так як ‖ A B ‖ F 2 = ∑ i , j | ∑ k a i k b k j | 2 ? a і k | 2 ∑ k , j | b k j | 2 = ‖ A ‖ F 2 ‖ B ‖ F 2 (\displaystyle \|AB\|_(F)^(2)=\sum _(i,j)\left|\sum _(k)a_(ik) b_(kj)\right|^(2)\leq \sum _(i,j)\left(\sum _(k)|a_(ik)||b_(kj)|\right)^(2)\ leq \sum _(i,j)\left(\sum _(k)|a_(ik)|^(2)\sum _(k)|b_(kj)|^(2)\right)=\sum _(i,k)|a_(ik)|^(2)\sum _(k,j)|b_(kj)|^(2)=\|A\|_(F)^(2)\| B\|_(F)^(2)).
• ‖ A ‖ F 2 = t r ⁡ A ∗ A = t r ⁡ A A ∗ (\displaystyle \|A\|_(F)^(2)=\mathop (\rm(tr)) A^(*)A=\ mathop (\rm (tr)) AA^(*)), де t r ⁡ A (\displaystyle \mathop (\rm(tr)) A)- слід-матриці A (\displaystyle A), A ∗ (\displaystyle A^(*))- ермітово-сполучена матриця.
• ‖ A ‖ F 2 = ρ 1 2 + ρ 2 2 + ⋯ + ρ n 2 (\displaystyle \|A\|_(F)^(2)=\rho _(1)^(2)+\rho _ (2)^(2)+\dots +\rho _(n)^(2)), де ρ 1 , ρ 2 , … , ρ n (\displaystyle \rho _(1),\rho _(2),\dots ,\rho _(n))- сингулярні числа матриці A (\displaystyle A).
• ‖ A ‖ F (\displaystyle \|A\|_(F))не змінюється при множенні матриці A (\displaystyle A)ліворуч або праворуч на ортогональні (унітарні) матриці.

Максимум модуля

Норма максимуму модуля - інший окремий випадок p-норми для p = ∞ .

‖ A ‖ max = max ( | a i j | ) . (\displaystyle \|A\|_(\text(max))=\max\(|a_(ij)|\).)

Норма Шаттена

Узгодженість матричної та векторних норм

Матрична норма ‖ ⋅ ‖ a b (\displaystyle \|\cdot \|_(ab))на K m × n (\displaystyle K^(m\times n))називається узгодженоїз нормами ‖ ⋅ ‖ a (\displaystyle \|\cdot \|_(a))на K n (\displaystyle K^(n))і ‖ ⋅ ‖ b (\displaystyle \|\cdot \|_(b))на K m (\displaystyle K^(m)), якщо:

‖ A x ‖ b ≤ ‖ A ‖ a b ‖ x ‖ a (\displaystyle \|Ax\|_(b)\leq \|A\|_(ab)\|x\|_(a))

для будь-яких A ∈ K m × n , x ∈ K n (\displaystyle A\in K^(m\times n),x\in K^(n)). Операторна норма з побудови є узгодженою з вихідною векторною нормою.

Приклади узгоджених, але не підлеглих матричних норм:

Еквівалентність норм

Усі норми у просторі K m × n (\displaystyle K^(m\times n))еквівалентні, тобто для будь-яких двох норм ‖ . ‖ α (\displaystyle \|.\|_(\alpha ))і ‖ . ‖ β (\displaystyle \|.\|_(\beta ))і для будь-якої матриці A ∈ K m × n (\displaystyle A\in K^(m\times n))Правильно подвійне нерівність.