Метод LU факторизації для розв'язування системи лінійних рівнянь

Ідея методу LU-факторизації, при знаходженні розв'язку системи лінійних алгебраїчних рівнянь, базується на наступному твердженні: будь-яку квадратну дійсну матрицю (матриця коефіцієнтів при невідомих) можна розкласти на дві трикутні — верхньотрикутну унімотарну матрицю (квадратна матриця, в якій всі елементи нижче за головну діагональ дорівнюють нулю, а елементи на головній діагоналі дорівнюють одиниці) та нижньотрикутну матрицю (квадратна матриця, в якій всі елементи вище за головну діагональ дорівнюють нулю) і таким чином спростити процес відшукання коренів. Розглянемо даний процес більш детально. Для цього, систему лінійних алгебраїчних рівнянь запишемо у матричній формі:

де квадратна матриця порядку і

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

Тоді, рівняння (1) можна записати у наступному вигляді . Ввівши у розгляд змінну , рівняння (3) перепишемо наступним чином . Звідси, шуканий вектор  може бути знайдений із ланцюга рівнянь , які виходячи з того, що матриці  та  — трикутні, легко розв'язуються за наступними формулами:

Після того, як основна ідея методу LU-фактризації відома, розглянемо, яким чином обчислюються елементи матриць  та . Для цього, врахувавши рівність (2), послідовно перемножимо рядки матриці  на стовпці матриці . В результаті отримаємо систему, яка складається з рівнянь та  невідомих :

Розв'язавши дану систему, отримаємо розрахункові формули для знаходження елементів трикутних матриць:

Розв'язок системи лінійних алгебраїчних рівнянь методом LU факторизації — приклад:

Використовуючи методом LU-розкладання знайти розв'язок наступної системи лінійних алгебраїчних рівнянь:

Для цього, скориставшись формулами (3), (4) обчислюємо елементи матриць і . В результаті будемо мати:

Далі, використовуючи формули (7), знаходимо рішення системи лінійних алгебраїчних рівнянь виду :

Після чого, за формулами (8) отримаємо розв'язок системи , який і являтиметься шуканим розв'язком заданої системи лінійних алгебраїчних рівнянь:

Блок-схема алгоритму методу LU факторизації: