Знаймо

Додати знання

приховати рекламу

Цей текст може містити помилки.

Визначник



План:


Введення

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

Визначник матриці А позначається як: det (A), | А | або Δ (A).


1. Визначення через розкладання по першому рядку

Схема розрахунку визначника матриці 2 \ times 2 .

Для матриці першого порядку детермінантом є сам єдиний елемент цієї матриці:

\ Delta = \ begin {vmatrix} a_ {11} \ end {vmatrix} = a_ {11}

Для матриці 2 \ times 2 детермінант визначається як

\ Delta = \ begin {vmatrix} a_ {11} & a_ {12} \ \ a_ {21} & a_ {22} \ end {vmatrix} = a_ {11} a_ {22}-a_ {12} a_ {21 }

Для матриці n \ times n визначник задається рекурсивно:

\ Delta = \ sum_ {j = 1} ^ n (-1) ^ {1 + j} a_ {1j} \ bar M_j ^ 1 , Де \ Bar M_j ^ 1 - додатковий мінор до елемента a 1 j . Ця формула називається розкладанням по рядку.

Зокрема, формула обчислення визначника матриці 3 \ times 3 така:

\ Delta = \ begin {vmatrix} a_ {11} & a_ {12} & a_ {13} \ \ a_ {21} & a_ {22} & a_ {23} \ \ a_ {31} & a_ {32} & a_ {33} \ end {vmatrix} = a_ {11} \ begin {vmatrix} a_ {22} & a_ {23} \ \ a_ {32} & a_ {33} \ end {vmatrix}-a_ {12} \ begin {vmatrix} a_ {21} & a_ {23} \ \ a_ {31} & a_ {33} \ end {vmatrix} + a_ {13} \ begin {vmatrix} a_ {21} & a_ {22} \ \ a_ {31} & a_ {32} \ end {vmatrix} =
= A 11 a 22 a 33 - a 11 a 23 a 32 - a 12 a 21 a 33 + a 12 a 23 a 31 + a 13 a 21 a 32 - a 13 a 22 a 31


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

\ Delta = \ sum_ {i = 1} ^ n (-1) ^ {i +1} a_ {i1} \ bar M_1 ^ i
Доказ

Нехай \ Tilde {\ Delta} = \ sum_ {i = 1} ^ n (-1) ^ {i +1} a_ {i1} \ bar M_1 ^ i .


Доведемо, що \ Tilde {\ Delta} = \ Delta по індукції. Видно, що для матриці 2 \ times 2 це вірно:

\ Tilde {\ Delta_2} = \ sum_ {i = 1} ^ n (-1) ^ {i +1} a_ {i1} \ bar M_1 ^ i = a_ {11} a_ {22}-a_ {21} a_ {12} = \ Delta_2

Предполжім, що для матриці порядку n-1 \ Tilde \ Delta_ {n-1} = \ Delta_ {n-1} - Вірно.


\ Tilde {\ Delta_n} = \ sum_ {i = 1} ^ n (-1) ^ {i +1} a_ {i1} \ bar M_1 ^ i = a_ {11} \ bar M_1 ^ 1 + \ sum_ {i = 2} ^ n (-1) ^ {i +1} a_ {i1} \ bar M_1 ^ i = a_ {11} \ bar M_1 ^ 1 + \ sum_ {i = 2} ^ n (-1) ^ { i +1} a_ {i1} \ sum_ {j = 2} ^ n (-1) ^ j a_ {1j} \ bar M_ {1j} ^ {i1} =
= A_ {11} \ bar M_1 ^ 1 + \ sum_ {i = 2} ^ n \ sum_ {j = 2} ^ n (-1) ^ {i + j +1} a_ {i1} a_ {1j} \ bar M_ {1j} ^ {i1}


{\ Delta_n} = \ sum_ {j = 1} ^ n (-1) ^ {1 + j} a_ {1j} \ bar M_j ^ 1 = a_ {11} \ bar M_1 ^ 1 + \ sum_ {j = 2 } ^ n (-1) ^ {1 + j} a_ {1j} \ bar M_j ^ 1 = a_ {11} \ bar M_1 ^ 1 + \ sum_ {j = 2} ^ n (-1) ^ {1 + j} a_ {1j} \ sum_ {i = 2} ^ n (-1) ^ i a_ {i1} \ bar M_ {j1} ^ {1i} =
= A_ {11} \ bar M_1 ^ 1 + \ sum_ {j = 2} ^ n \ sum_ {i = 2} ^ n (-1) ^ {i + j +1} a_ {1j} a_ {i1} \ bar M_ {j1} ^ {1i} = \ tilde {\ Delta_n}


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

\ Delta = \ sum_ {j = 1} ^ n (-1) ^ {i + j} a_ {ij} \ bar M_j ^ i
Доказ

Нехай \ Tilde {\ Delta} = \ sum_ {j = 1} ^ n (-1) ^ {i + j} a_ {ij} \ bar M_j ^ i .


Доведемо, що \ Tilde {\ Delta} = \ Delta по індукції. Видно, що для матриці 2 \ times 2 це вірно:

\ Tilde {\ Delta_2} = \ sum_ {j = 1} ^ n (-1) ^ {i + j} a_ {ij} \ bar M_j ^ i =- a_ {21} a_ {12} + a_ {22} a_ {11} = \ Delta_2

Припустимо, що для матриці порядку n-1 \ Tilde \ Delta_ {n-1} = \ Delta_ {n-1} - Вірно.

\ Tilde {\ Delta_n} = \ sum_ {j = 1} ^ n (-1) ^ {i + j} a_ {ij} \ bar M_j ^ i = \ sum_ {j = 1} ^ n (-1) ^ {i + j} a_ {ij} \ left (\ sum_ {k <j}(-1)^{1+k}a_{1k}\bar M_{jk}^{i1}+\sum_{k> j } (-1) ^ k a_ {1k} \ bar M_ {jk} ^ {i1} \ right)

Зберемо коефіцієнти при \ Bar M_ {j_0k_0} ^ {i \, \, 1} :


j_0> k_0 \ colon \;


= (-1) ^ {I + j_0 + k_0 +1} M_ {j_0k_0} ^ {1 \, \, i}


j_0 <k_0 \ colon \;


= (-1) ^ {I + j_0 + k_0 +1} M_ {j_0k_0} ^ {1 \, \, i}
\ Tilde {\ Delta_n} = \ sum_ {j \ ne k} (-1) ^ {i + j + k +1} M_ {jk} ^ {1i} \ bar M_ {jk} ^ {1i}


\ Delta = \ sum_ {j = 1} ^ n (-1) ^ {1 + j} a_ {1j} \ bar M_j ^ 1 = \ sum_ {j = 1} ^ n (-1) ^ {1 + j } a_ {1j} \ left (\ sum_ {k <j}(-1)^{i+k-1}a_{ik}\bar M_{jk}^{1i}+\sum_{k> j} ( -1) ^ {i + k-2} a_ {ik} \ bar M_ {jk} ^ {1i} \ right)

Зберемо коефіцієнти при \ Bar M_ {j_0k_0} ^ {i \, \, 1} :


j_0> k_0 \ colon \; (-1) ^ {1 + j_0} a_ {1j_0} (-1) ^ {i + k_0-1} a_ {ik_0} + (-1) ^ {1 + k_0} a_ { 1k_0} (-1) ^ {i + j_0-2} a_ {ij_0} = (-1) ^ {j_0 + i + k_0} (a_ {1j_0} a_ {ik_0}-a_ {1k_0} a_ {ij_0}) =


= (-1) ^ {I + j_0 + k_0 +1} M_ {j_0k_0} ^ {1 \, \, i}


j_0 <k_0 \ colon \; (-1) ^ {1 + j_0} a_ {1j_0} (-1) ^ {i + k_0-2} a_ {ik_0} + (-1) ^ {1 + k_0} a_ { 1k_0} (-1) ^ {i + j_0-1} a_ {ij_0} = (-1) ^ {k_0 + i + j_0} (a_ {1k_0} a_ {ij_0}-a_ {1j_0} a_ {ik_0}) =


= (-1) ^ {I + j_0 + k_0 +1} M_ {j_0k_0} ^ {1 \, \, i}
{\ Delta_n} = \ sum_ {j \ ne k} (-1) ^ {i + j + k +1} M_ {jk} ^ {1i} \ bar M_ {jk} ^ {1i} = \ tilde {\ Delta_n}

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

\ Delta = \ sum_ {1 \ leqslant j_1 <\ ldots <j_k \ leqslant n} (-1) ^ {i_1 +...+ i_k + j_1 +...+ j_k} M_ {j_1 ... j_k} ^ {i_1 ... i_k} \ bar M_ {j_1 ... j_k} ^ {i_1 ... i_k}

2. Визначення через перестановки

Для матриці n \ times n справедлива формула:

\ Delta = \ sum_ {\ alpha_1, \ alpha_2, \ ldots, \ alpha_n} (-1) ^ {N (\ alpha_1, \ alpha_2, \ ldots, \ alpha_n)} \ cdot a_ {\ alpha_11} \ cdots a_ { \ alpha_nn} ,

де α 1, α 2,..., α n - перестановка чисел від 1 до n , N1, α 2,..., α n) - число інверсій в перестановці, підсумовування йде по всіх можливих перестановок порядку n . Таким чином, в визначник увійде n! доданків, які також називають "членами визначника". Важливо зауважити, що в багатьох курсах лінійної алгебри це визначення дається як основне.


3. Властивості визначників

  • Визначник - кососімметрічная полілінейная функція рядків (стовпців) матриці. Полілінейность означає, що визначник лине по всіх рядках (стовпцям): \ Delta (\ hat A_1, \ ldots, \ alpha \ hat A_i + \ beta \ hat {A '} _i, \ ldots, \ hat A_n) = \ alpha \ Delta (\ hat A_1, \ ldots, \ hat A_i, \ ldots, \ hat A_n) + \ beta \ Delta (\ hat A_1, \ ldots, \ hat {A '} _i, \ ldots, \ hat A_n) , Де \ Hat A_1 і т. д. - рядки матриці, \ Delta (\ hat A_1, \ ldots, \ hat A_i, \ ldots, \ hat A_n) - Визначник такої матриці.
  • При додаванні до будь рядку (стовпцю) лінійної комбінації інших рядків (стовпців) визначник не зміниться.
  • Якщо два рядки (стовпця) матриці співпадають, то її визначник дорівнює нулю.
  • Якщо дві (або декілька) рядок (стовпчик) матриці лінійно залежні, то її визначник дорівнює нулю.
  • Якщо переставити два рядки (стовпця) матриці, то її визначник помножується на (-1).
  • Загальний множник елементів будь-якого ряду визначника можна винести за знак визначника.
  • Якщо хоча б один рядок (стовпчик) матриці нульова, то визначник дорівнює нулю.
  • Сума творів усіх елементів будь-якого рядка на їх алгебраїчні доповнення дорівнює визначник.
  • Сума творів усіх елементів будь-якого ряду на алгебраїчні доповнення відповідних елементів паралельного ряду дорівнює нулю.
  • Визначник твори квадратних матриць однакового порядку дорівнює добутку їх визначників (див. також формулу Біне-Коші).
  • З використанням індексного нотації визначник матриці 3 3 може бути визначений за допомогою символу Леві-Чівіта зі співвідношення:
    \ Begin {vmatrix} a_1 & a_2 & a_3 \ \ b_1 & b_2 & b_3 \ \ c_1 & c_2 & c_3 \ \ \ end {vmatrix} = \ sum_ {i, j, k = 1} ^ 3 \ varepsilon_ {ijk} a_ {i} b_ {j} c_ {k}.

4. Алгоритмічна реалізація

  • Наївні методи для обчислення визначника можуть бути засновані безпосередньо на його визначенні, як суми по перестановок, або на розкладанні Лапласа по визначників меншого порядку. Однак такі методи дуже неефективні, оскільки вимагають Про ( n!) операцій для обчислення визначника n -Го порядку.
  • Один з більш швидких методів полягає в простій модифікації методу Гауса. Дотримуючись методу Гаусса, довільну матрицю A можна привести до ступінчастому увазі (Верхнетреугольная матриця), використовуючи лише дві такі операції над матрицею - перестановку двох рядків і додавання до одного з рядків матриці іншого рядка, помноженої на довільне число. З властивостей означника випливає, що друга операція не змінює визначника матриці, а перша лише змінює його знак на протилежний. Визначник матриці, приведеної до ступінчастому увазі, дорівнює добутку елементів на її діагоналі, так як вона є трикутної, тому визначник вихідної матриці дорівнює:
    \! \ Det A = (-1) ^ s \ cdot \ det A_ {\ mbox {ref}},
де s - Число перестановок рядків, виконаних алгоритмом, а A ref - Ступінчаста форма матриці A , Отримана в результаті роботи алгоритму. Складність цього методу, як і методу Гаусса, становить O (n 3) .
  • Визначник можна обчислити, знаючи LU-розкладання матриці. Якщо A = L U , Де L і U - Трикутні матриці, то det A = (det L) (det U) . Визначник трикутної матриці дорівнює просто твору її діагональних елементів.
  • Якщо доступний алгоритм, що виконує множення двох матриць порядку n за час M (n) , Де M (n) \ geqslant n ^ a , Для деякого a> 2 , То визначник матриці порядку n може бути обчислений за час O (M (n)) . [1] Зокрема це означає, що, використовуючи для множення матриць алгоритм Копперсміта - Винограду, визначник можна обчислити за час O (n 2.376) .

5. Спеціальні види визначників

Примітки

  1. JR Bunch and JE Hopcroft. Triangular factorization and inversion by fast matrix multiplication, Mathematics of Computation, 28 (1974) 231-236.

Література


Цей текст може містити помилки.

Схожі роботи | скачати

Схожі роботи:
Визначник Грама
Визначник Вандермонда
© Усі права захищені
написати до нас
Рейтинг@Mail.ru