Узагальнення для несиметричної матриці.

Л.6. Метод квадратного кореня.

[БЖК[М.1] , с. 262-265; СГ[М.2] , с.69-73; ОП[М.3] , с. 95-98]

Це - метод для симетричної матриці , А = А^*.

Варіант 1. Полягає у представленні А = LL^*, де L – нижня трикутна матриця , l_ij= 0 , якщо i < j.

Ax = f; x = f.

Спочатку розв’язують систему:

а потім

В обох системах матриці трикутні , тому розв’язання є простим . Прямий хід:

Зворотній хід:

Формули для одержуємо безпосередньо з виразу А = LL^*:

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

Зауваження 2. Якщо під коренем буде нуль, то = 0 і метод не працює (ділення на нуль). Це означає, що не будь-яку симетричну матрицю можна представити у вигляді добутку LL^*.

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

Варіант 2. Матрицю А представляють у вигляді А = LDL^*, де L – нижня трикутна матриця, D - діагональна матриця, причому , у залежності від знаку виразу під коренем. Формули методу:

Метод працює у множині дійсних чисел незалежно від знаків діагональних елементів. Якщо деяке l_kk = 0, k<n, то представлення А = LDL^* є нездійсненним.

Тоді, вводячи позначення L^*x = z, Dz = y, Ly = f, маємо

Варіант 3. Матрицю А представляють у вигляді А = LDL^*, де L – нижня трикутна матриця з одиницями на головній діагоналі, D - діагональна матриця. При цьому виявляється, що d_ii стає рівним отому виразу, від'ємність якого була критичною у варіанті 1. Формули методу:

Метод працює у множині дійсних чисел незалежно від знаків діагональних елементів і, на відміну від попереднього варіанту, не вимагає використання функції кореня квадратного. Умова l_kk = 0, k<n, залишається критичною.

Узагальнення для несиметричної матриці.

У багатьох задачах, зокрема при обчисленні власних чисел та векторів вимагається представлення матриці у вигляді А = LDU, де L та U – нижня та верхня трикутні матриці з одиницями на головній діагоналі; D – діагональна матриця.

Нехай

Тоді, перемноживши ці три матриці та дорівнявши результ до елементів матриці А, остаточно одержуємо алгоритм:

У циклі для k = 1, …, n

У циклі для j = k+1, …, n

кінець циклу по j;

кінець циклу по k;

Тоді, вважаючи у системі Ax = LDUx = f Ux = z, Dz = y, Ly = f, маємо

Остання модифікація для стрічкової матриці.

Нехай матриця А є (p+1+q)-діагональною, тобто

a_ki = 0 при i - k > p (p верхніх діагоналей) та при k - i > q (q нижніх діагоналей).

Тоді при i - k > p маємо m_ki = 0, а при k - i > q маємо l_ki = 0.

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