Властивості верхньої трикутної матриці. Трикутна матриця

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

Нижньотрикутна матриця- Квадратна матриця, в якій всі елементи вище головної діагоналі дорівнюють нулю.

Унітрекутна матриця(верхня чи нижня) - трикутна матриця, де всі елементи на головній діагоналі рівні одиниці.

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

Рішення систем лінійних рівнянь із трикутною матрицею (зворотний хід) не становить складнощів.

Властивості

Визначник трикутної матриці дорівнює добутку елементів її головної діагоналі.
Визначник унітрекутної матриці дорівнює одиниці.
Безліч невироджених верхньотрикутних матриць порядку nз множення з елементами з поля kутворює групу, яка позначається UT(n, k) або UT n (k).
Безліч невироджених нижньотрикутних матриць порядку nз множення з елементами з поля kутворює групу, що позначається LT(n, k) або LT n (k).
Безліч верхніх унітрекутних матриць з елементами з поля kутворює підгрупу UT n (k) за множенням, що позначається SUT(n, k) або SUT n (k). Аналогічна підгрупа нижніх унітрекутних матриць позначається SLT(n, k) або SLT n (k).
Безліч всіх верхньотрикутних матриць з елементами кільця k утворює алгебру щодо операцій складання, множення на елементи кільця і перемноження матриць. Аналогічне твердження справедливе для нижньотрикутних матриць.
Група UT nможна розв'язати, а її унітрекутна підгрупа SUT nнільпотентна.

Див. також

Wikimedia Foundation. 2010 .

Дивитись що таке "Трикутна матриця" в інших словниках:

трикутна матриця- - Трикутна матриця Квадратна матриця, у якої рівні нулю всі елементи, розташовані під або над головною діагоналлю (СР Діагональна матриця). У першому випадку маємо… …

Трикутна матриця- Квадратна матриця, у якої рівні нулю всі елементи, розташовані під або над головною діагоналлю (СР діагональна матриця). У першому випадку маємо верхню Т.м. у другому нижню …

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

Трикутна матриця МОБ- матриця коефіцієнтів міжгалузевого балансу (МОБ), що відповідає такій виробничій системі, в якій будь-який продукт може витрачатися у своєму власному виробництві та у виробництві будь-якого наступного… Економіко-математичний словник

трикутна матриця МОБ- Матриця коефіцієнтів міжгалузевого балансу (МОБ), що відповідає такій виробничій системі, в якій будь-який продукт може витрачатися у своєму власному виробництві та у виробництві будь-якого наступного за ним продукту, але ніякого… Довідник технічного перекладача

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

Блочно-трикутна матриця- - матриця, яку можна розбити на підматриці таким чином, щоб з одного боку її «головної діагоналі», складеної з підматриць, стояли нулі. Прикладами блочно трикутних матриць можуть служити … Економіко-математичний словник

блочно-трикутна матриця- Матриця, яку можна розбити на підматриці таким чином, щоб з одного боку її «головної діагоналі», складеної з підматриць, стояли нулі. Прикладами блочно трикутних матриць можуть бути трикутна матриця і блочно діагональна матриця … Довідник технічного перекладача

Матриця- Система елементів (чисел, функцій та інших величин), розташованих у вигляді прямокутної таблиці, над якою можна робити певні дії. Таблиця має наступний вигляд: Елемент матриці у загальному вигляді позначається aij це… Економіко-математичний словник

матриця- Логічна мережа, налаштована у вигляді прямокутного масиву перетинів вхідних/вихідних каналів. матриця Система елементів (чисел, функцій та інших величин), розташованих у вигляді прямокутної… Довідник технічного перекладача

Верхня трикутна матриця

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

Приклад верхньотрикутної матриці

Верхньотрикутна матриця- Квадратна матриця , в якій всі елементи нижче головної діагоналі дорівнюють нулю.

Нижньотрикутна матриця- Квадратна матриця, в якій всі елементи вище головної діагоналі дорівнюють нулю.

Рішення систем лінійних рівнянь із трикутною матрицею (зворотний хід) не становить складнощів.

Властивості

Визначник трикутної матриці дорівнює добутку елементів її головної діагоналі.
Визначник унітрекутної матриці дорівнює одиниці.
Безліч невироджених верхньотрикутних матриць порядку nз множення з елементами з поля kутворює групу, яка позначається UT(n, k) або UT n (k).
Безліч невироджених нижньотрикутних матриць порядку nз множення з елементами з поля kутворює групу, що позначається LT(n, k) або LT n (k).
Безліч верхніх унітрекутних матриць з елементами з поля kутворює підгрупу UT n (k) за множенням, що позначається SUT(n, k) або SUT n (k). Аналогічна підгрупа нижніх унітрекутних матриць позначається SLT(n, k) або SLT n (k).
Безліч всіх верхньотрикутних матриць з елементами кільця k утворює алгебру щодо операцій складання, множення на елементи кільця і перемноження матриць. Аналогічне твердження справедливе для нижньотрикутних матриць.
Група UT nможна розв'язати, а її унітрекутна підгрупа SUT nнільпотентна.

Див. також

Wikimedia Foundation. 2010 .

Дивитись що таке "Верхня трикутна матриця" в інших словниках:

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

Для покращення цієї статті бажано?: Знайти та оформити у вигляді виносок посилання на авторитетні джерела, що підтверджують написане. Проставивши виноски, внести точніші вказівки на джерела. Додати ілюстрації … Вікіпедія

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

SFLASH асиметричний алгоритм цифрового підпису, рекомендований проектом NESSIE European у 2003 році. SFLASH заснований на Matsumoto Imai (MI) схемою, так само званою C *. Алгоритм належить до сімейства багатовимірних схем з відкритим ключем, то ... Вікіпедія

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

Коефіцієнт кореляції- (Correlation coefficient) Коефіцієнт кореляції це статистичний показник залежності двох випадкових величин Визначення коефіцієнта кореляції, види коефіцієнтів кореляції, властивості коефіцієнта кореляції, обчислення та застосування. Енциклопедія інвестора

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

Якщо верхня трикутна матриця має n 2 елементів, приблизно половина є нульовими і немає необхідності зберігати їх явно. Конкретно, якщо ми віднімаємо n діагональних елементів із суми n 2 елементів, то половина елементів, що залишилися, є нульовими. Наприклад, при n=25 є 300 елементів зі значенням 0:

(n 2 -n) / 2 = (25 2 -25) / 2 = (625-25) / 2 = 300

Сума або різницю двох трикутних матриць А і В виходить в результаті складання або віднімання відповідних елементів матриць. Результуюча матриця є трикутною.

Додавання С = А + В

Віднімання С = А - В

де С - це трикутна матриця з елементами C i, j = A i, j + B i, j.

Множення С = А * В

Результуюча матриця С - це трикутна матриця з елементами C i , j значення яких обчислюються з елементів рядка i матриці А і стовпця j матриці В:

C i , j =(A i ,0 *B 0, j)+ (A i ,1 *B 1, j)+ (A i ,2 *B 2, j)+…+ (A i , n -1 * B n -1, j)

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

Зберігання трикутної матриці

Застосування для зберігання верхньої трикутної матриці стандартного двовимірного масиву вимагає використання всієї пам'яті розміром n 2 незважаючи на прогнозовані нулі, розташовані нижче діагоналі. Для виключення цього простору ми зберігаємо елементи трикутної матриці в одновимірному масиві М. Всі елементи нижче головної діагоналі не зберігаються. Таблиця 3.1 показує кількість елементів, що зберігаються у кожному рядку.

Зберігання трикутної матриці

Таблиця 1

Алгоритму збереження потрібна функція доступу, яка повинна визначати місце розташування в масиві М елементу A i , j . Для j< i элемент A i , j является равным 0 и не сохраняется в М. Для j ³ i функция доступа использует информацию о числе сохраняемых элементов в каждой строке вплоть до строки i. Эта информация может быть вычислена для каждой строки i и сохранена в массиве (rowTable) для использования функцией доступа.

приклад 4.

З урахуванням того, що елементи трикутної матриці зберігаються рядково в масиві М, функція доступу для A i j використовує такі параметри:

Індекси i та j,

Масив rowTable

Алгоритм доступу до елемента A i j полягає в наступному:

Якщо j

Якщо j³i, то виходить значення rowTable[i], яке є кількістю елементів, що зберігаються в масиві М, для елементів до рядка i. У рядку i перші i елементів є нульовими і зберігаються в М. Елемент A i , j міститься в M+(j-i)].

Приклад 5.

Розглянемо трикутну матрицю Х з прикладу 3.4:

1.Х 0,2 = M = М = М = 0

2.X 1,0 не зберігаються

3.Х 1,2 = M + (2-1)] = М = М = 1

Клас TriMat

Клас TriMat реалізує низку операцій трикутної матриці. Віднімання та множення трикутної матриці залишено для вправ у кінці розділу. Враховуючи те обмеження, що ми повинні використовувати лише статичні масиви, наш клас обмежує розмір рядка та стовпця числом 25. При цьому ми матимемо 300=(25 2 -25)/2 нульових елементів, тому масив М має містити 325 елементів.

Специфікація класу TriMat

ОГОЛОШЕННЯ

#include

// максимальна кількість елементів та рядків

// верхньої трикутної матриці

const int ELEMENTLIMIT = 325;

const int ROWLIMIT = 25;

// Закриті дані-члени

int rowTable; // Початковий індекс рядка в М

int n; // розмір рядка/колонки

double М;

// Конструктор із параметрами TriMat(int matsize);

//Методи доступу до елементів матриці

void PutElement (double item, int i, int j);

double GetElement(int i, int j) const;

// матричні арифметичні операції

TriMat AddMat(const TriMat&A) const;

double DelMat(void) const;

// матричні операції введення/виводу

void ReadMat(void);

void WriteMat(void) const;

// отримати розмірність матриці

int GetDimension(void) const;

ОПИС

Конструктор приймає число рядків та стовпців матриці. Методи PutEle-ment та GetElement зберігають та повертають елементи верхньої трикутної матриці. GetElement повертає 0 для елементів нижче діагоналі. AddMat повертає суму матриці з поточним об'єктом. Цей метод не змінює значення поточної матриці. Оператори введення/виводу ReadMat та WriteMat працюють з усіма елементами матриці n x n. Сам метод ReadMat зберігає лише верхньо-трикутні елементи матриці.

#include trimat.h // увімкнути клас TriMat

TriMat A (10), (10), С (10); // Трикутні матриці 10x10

A.ReadMat(); // Ввести матриці А і В

З = A. AddMat (В); // Обчислити С = А + В

C.WriteMat(); // Друкувати

Реалізація класу TriMat

Конструктор ініціалізує закритий член n параметром matsize. Таким чином задається число рядків та стовпців матриці. Цей же параметр використовується для ініціалізації масиву rowTable, який використовується для доступу до елементів матриці. Якщо matsize перевищує ROWLIMIT, видається повідомлення про помилку та виконання програми переривається.

// ініціалізація n та rowTable

TriMat::TriMat (int matsize)

int storedElements = 0;

// Перервати програму, якщо matsize більше ROWLIMIT

if (matsize > ROWLIMIT)

cerr<< "Превышен размер матрицы" << ROWLIMIT << "x" << ROWLIMIT << endl;

// задати таблицю

for (int i = 0; i< n; i++)

rowTable [i] = storedElements;

викладені елементи += n - i;

Матричні методи доступу. Ключовим моментом під час роботи з трикутними матрицями є можливість ефективного зберігання ненульових елементів у лінійному масиві. Щоб досягти такої ефективності і все ж таки використовувати звичайні двовимірні індекси i і j для доступу до елемента матриці, нам необхідні функції PutElement і GetElement для збереження та повернення елементів матриці в масиві.

Метод GetDimension надає клієнту доступ до розміру матриці. Ця інформація може використовуватися для забезпечення того, щоб методам доступу передавалися параметри, що відповідають правильному рядку та стовпцю:

// Повернути розмірність матриці n

int TriMat::GetDimension(void) const

Метод PutElement перевіряє індекси i та j. Якщо j ³ i, ми зберігаємо значення даних М, використовуючи функцію доступу до матриці для трикутних матриць: Якщо i чи j немає у діапазоні 0 . . (n-1), то програма закінчується:

// записати елемент матриці масив М

void TriMat::PutElement (double item, int i, int j)

// Перервати програму, якщо індекси елемента поза

// Індексного діапазону

if ((i< 0 || i >= n) | (j< 0 |1 j >= n))

cerr<< "PutElement: индекс вне диапазона 0-"<< n-1 << endl;

// Усі елементи нижче діагоналі ігноруються if (j >= i)

M + j-i] = item;

Для отримання будь-якого елемента метод GetElement перевіряє індекси i та j. Якщо i або j не в діапазоні 0…(n - 1), програма закінчується. Якщо j

// отримати матричний елемент масиву М

double TriMat::GetElement(int i, int j) const

// Перервати програму, якщо індекси поза індексним діапазоном

if ((i< 0 || i >= п) | (j< 0 |I j >= n))

cerr<< "GetElement: индекс вне диапазона 0-"<< n-1 << endl;

// Повернути елемент, якщо він вище діагоналі

return M+j-i];

// Елемент дорівнює 0, якщо він нижче діагоналі

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

// всі (n x n) елементів

void TriMat::ReadMat (void)

for(i = 0; i

for(j = 0; j

//Порядкова видача в потік елементів матриці

void TriMat::WriteMat (void) const

// Встановлення режиму видачі

cout. setf (ios::fixed);

cout.precision (3);

cout.setf (ios:: showpoint) ;

for (i = 0; i< n; i++)

for (j = 0; j< n; j++)

cout<< setw(7) << GetElement (i,j);

cout<< endl;

Матричні операції. Клас TriMat має методи для обчислення суми двох матриць та детермінанту матриці. Метод AddMat приймає єдиний параметр, який є правим операндом у сумі. Поточний об'єкт відповідає лівому операнду. Наприклад, сума трикутних матриць X та Y використовує метод AddMat для об'єкта X. Припустимо, сума зберігається в об'єкті Z. Для обчислення

Z = Х + Y використовуйте оператор

Z = X.AddMat(Y);

Алгоритм складання двох об'єктів типу TriMat повертає нову матрицю з елементами B i , j = CurrentObjecty i , j + A i , j:

// Повертає суму поточної та матриці А.

// Поточний об'єкт не змінюється

TriMat TriMat::AddMat (const TriMat& A) const

double itemCurrent, itemA;

TriMat B(A.n); // В буде шукана сума

for (i = 0; i< n; i++) // цикл по строкам

for (j = i; j< n; j++) // пропускать элементы ниже диагонали

itemCurrent = GetElement i, j);

itemA = A. GetElement (i, j);

B. PutElement (itemCurrent + itemA, i, j);

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

1. Нехай дана матриця рангу. Введемо такі позначення для послідовних головних мінорів цієї матриці:

Допустимо, що мають місце умови здійсненності алгоритму Гауса:

Позначимо через матрицю коефіцієнтів системи рівнянь (18), до якої наводиться система рівнянь

шляхом виключення Гауса. Матриця має верхню трикутну форму, причому елементи її перших рядків визначаються формулами (13), а елементи останніх рядків всі рівні нулю:

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

. (31)

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

Таким чином

де кожна матриця має вигляд (31) і, отже, є нижньою трикутною матрицею з діагональними елементами, рівними 1.

. (32)

Матрицю називатимемо перетворюючої матрицею для матриці методом виключення Гаусса. Обидві матриці і однозначно визначаються завданням матриці . З (32) випливає, що нижня трикутна матриця з діагональними елементами, рівними 1 (див. стор. 28).

Оскільки - неособлива матриця, то з (33) знаходимо:

Ми представили матрицю у вигляді добутку нижньої трикутної матриці на верхню трикутну матрицю. Питання про розкладання матриці на множники такого типу повністю з'ясовується наступною теоремою:

Теорема 1. Будь-яку матрицю рангу , яка має перші послідовних очних мінорів відмінні від нуля,

, (34)

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

. (35)

Першим діагональним елементам матриць можна дати довільні значення, що задовольняють умовам (36).

Завдання перших діагональних елементів матриць і однозначно визначає елементи перших стовпців матриці і перших r рядків матриці . Для цих елементів мають місце формули

, (37)

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

Доведення. Можливість подання матриці, яка задовольняє умові (34), у вигляді твору (35) була доведена вище [див. (33")]

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

Оскільки - верхня трикутна матриця, то перші стовпці матриці містять тільки один відмінний від нуля мінор-го порядку . Тому рівність (38) може бути записана так:

Покладемо спочатку тут. Тоді отримаємо:

звідки вже витікають співвідношення (36).

Не порушуючи нерівності (35), ми можемо в ньому помножити матрицю праворуч на особливу довільну діагональну матрицю , одночасно помножуючи матрицю зліва на . Це рівносильно множенню стовпців матриці відповідно і рядків матриці на . Тому діагональним елементам , , можна надати будь-які значення, що задовольняють умовам (36).

тобто перші формули (37). Абсолютно аналогічно встановлюються другі формули (37) для елементів матриці .

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

Теорему доведено.

З доведеної теореми випливає низка цікавих наслідків.

Наслідок 1. Елементи перших стовпців матриці та перших рядків матриці пов'язані з елементами матриці рекурентними співвідношеннями:

(41)

Співвідношення (41) безпосередньо випливають із матричного рівності (35) ними зручно користуватися для фактичного обчислення елементів матриць і .

Наслідок 2. Якщо - неособлива матриця , що задовольняє умові (34), то у поданні (35) матриці визначаються однозначно, як тільки діагональні елементи цих матриць обрані відповідно до умов (36).

Наслідок 3. Якщо - симетрична матриця рангу та

де - нижня трикутна матриця, в якій

2. Нехай у поданні (35) у матриці елементи останніх стовпців дорівнюють нулю. Тоді можна покласти:

, , (43)

де – нижня, а – верхня трикутна матриця; при цьому перші діагональних елементів у матриць і дорівнюють 1, а елементи останніх стовпців матриці та останніх рядків матриці обрані довільно. Підставляючи в (35) вирази (43) для і використовуючи рівності (36), прийдемо до наступної теореми:

Теорема 2. Будь-яка матриця рангу, у якої

Представимо у вигляді добутку нижньої трикутної матриці, діагональної та верхньої трикутної:

(44)

, (45)

а, довільні при; .

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

Для конкретного обчислення елементів матриці можна рекомендувати наступний прийом.

Ми отримаємо матрицю, якщо до одиничної матриці застосуємо всі ті перетворення (що задаються матрицями), які ми в алгоритмі Гауса робили над матрицею (у цьому випадку замість твору, рівного, ми матимемо твір, рівний). Тому до матриці приписуємо праворуч одиничну матрицю :

. (46)

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

Таким чином, застосування алгоритму Гаусса до матриці (46) дає одночасно матрицю і матрицю .

Якщо - неособлива матриця, т. е. то і . В цьому випадку з (33) випливає . Оскільки матриці і визначені за допомогою алгоритму Гаусса, то знаходження зворотної матриці зводиться до визначення і множення на .