Тоді можна записати, що

L · у = b. (4)

Розв’язування системи (1) або (2) відбувається в два етапи: спочатку розв’язується система L · у = b, а потім U · x = у. Така послідовність розв’язку дає перевагу методу (в порівнянні з методом Гауса) – якщо потрібно розв’язати декілька систем з однією і тією ж матрицею А, задача суттєво спрощується, оскільки зберігаються матриці L та U.

Розв’язок системи L · у = b називається прямим ходом, а системи U · x = у – оберненим ходом.

Розглянемо прямий хід. Завдяки спеціальній формі матриці L вектор у можна легко визначити. Для цього (4) перепишемо у вигляді системи рівнянь

Звідси можна одержати, що в загальному вигляді

(5)

для

При оберненому ході вектор х визначається з системи рівнянь (3)

x ₁ + u ₁₂ x ₂ + u ₁₃ x ₃ + … + u _{1 n} x_n = y ₁

x ₂ + u ₂₃ x ₃ + … + u _{2 n} x_n = y ₂

x ₃ + … + u _{3 n} x_n = y ₃

………………………………

x_n = y_n.

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

для (6)

Тепер розглянемо LU – розклад матриці А.

У варіанті методу, що називається методом Крута, використовується наступна послідовність знаходження елементів матриць L та U () – де k – крок.

Для всіх

де (7)

де (8)

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

Алгоритм

1) k =1

Обчислюємо

для всіх

для всіх .

2) k = k + 1

де

де .

Продовжуємо до тих пір, доки k = n.

Зауваження щодо алгоритму побудови програми:

1) Необхідні в цих співвідношеннях значення елементів матриць L та U обчислюються на попередніх етапах процесу.

2) Кожний елемент a_ij матриці А потрібен тільки для обчислення відповідних елементів матриці L та U (тобто, в подальшому процесі a_ij не потрібні). Оскільки нульові елементи матриць L та U, а також одиничну діагональ матриці U запам’ятовувати не потрібно, тобто в процесі обчислення матриці L та U можуть бути записані на місце матриці А. Причому матриця L розташована в нижньому трикутнику (i ≥ j), U – відповідно в верхньому трикутнику (i < j) матриці А.

3) Розклад матриці А на матриці L та U, як правило, об’єднують з прямим ходом. Може бути використана наступна послідовність обчислень: спочатку обчислюється перший стовпець матриці L, потім перший рядок матриці U та перший елемент вектора у; далі – другий стовпець матриці L, другий рядок матриці U та другий елемент вектора у і т.д.

Дата добавления: 2014-01-11