02.02.2023 в 17:08

Линейная алгебра: LU-разложение с Python

В этой статье будет представлен способ решения линейной системы с использованием LU-декомпозиции.

LU Разложение

Декомпозиция Нижний-верхний (LU) - это способ разложить матрицу на множители как произведение нижней треугольной матрицы и верхней треугольной матрицы. Это можно рассматривать как матричную форму исключения Гаусса и является лучшим способом реализации исключения Гаусса, особенно для задачи с повторяющимся числом уравнений с одной и той же левой частью, т.е. для решения уравнения Ax = b с тем же A и разными значениями b.

Матрица А может быть разложена на произведение нижней и верхней треугольных матриц с использованием элементарных матриц. Вы можете обратиться к предыдущей статье о трех различных элементарных матрицах: замена, масштабирование и поворотная матрица.

Разложение матрицы А на произведение нижней и верхней треугольных матриц.

Теперь давайте рассмотрим, как решить линейную систему с помощью LU-декомпозиции.

Шаг за шагом решать линейную систему с использованием LU-факторизованных матриц.

Пример использования LU-декомпозиции для решения линейной системы:

Дана одна и та же левая сторона и разные правые стороны, т.е. с одним и тем же A и разными значениями b.

Шаг 1, 2, 3: Разложите матрицу A на матрицы L и U

Шаг 4: Используя Lc₁ = b₁ и Lc₂ = b₂, решите c₁ и c₂!

Шаг 5: Используя Ux₁ = c₁ и Ux₂ = c₂, решите x₁ и x₂!

Получив матрицы L и U, мы можем легко решить линейную систему с повторяющейся левой частью, как упоминалось выше.

LU_decomposition.py

import numpy as np

A = np.array([[1, 2, 3], 
              [4, -1, 0],
              [-2, 5, 1]]) 

E1 = np.array([[1,  0, 0], 
               [-4, 1, 0],
               [0,  0, 1]]) 

E2 = np.array([[1, 0, 0], 
               [0, 1, 0],
               [2, 0, 1]]) 

E3 = np.array([[1, 0, 0], 
               [0, 1, 0],
               [0, 1, 1]]) 

E1_inverse = np.linalg.inv(E1)
E2_inverse = np.linalg.inv(E2)
E3_inverse = np.linalg.inv(E3)

U = E3.dot(E2).dot(E1).dot(A)
L = E1_inverse.dot(E2_inverse).dot(E3_inverse)

print("\nStep 1 & 2: Upper traingular matrix of A using elementary matrices:")
print(U)
print("\nStep 1 & 3: Lower traingular matrix of A using inverse elementary matrices:")
print(L)

U_inverse = np.linalg.inv(U)
L_inverse = np.linalg.inv(L)

b1 = np.array([[3], 
               [9], 
               [-8]]) # column vector

c1 = L_inverse.dot(b1)
x1 = U_inverse.dot(c1)
print("\nStep 4a: Solve c1 given same left hand side matrix A but different right hand side b1:")
print(c1)
print("\nStep 5b: Solution x1 given same left hand side matrix A but different right hand side b1:")
print(x1)

b2 = np.array([[28], 
               [22], 
               [-11]]) # column vector

c2 = L_inverse.dot(b2)
x2 = U_inverse.dot(c2)
print("\nStep 4a: Solve c2 given same left hand side matrix A but different right hand side b2:")
print(c2)
print("\nStep 5b: Solution x2 given same left hand side matrix A but different right hand side b2:")
print(x2)

Резюме

Разложение LU используется для решения линейных систем и нахождения обратных матриц. Говорят, что это лучший метод решения линейной системы с повторяющейся левой частью. В этом посте вы узнаете, как решить линейную систему, используя разложение LU вместе с некоторыми кодами.

1972

Войти на сайт

Линейная алгебра: LU-разложение с Python

LU Разложение

Резюме