Викия

Математика

LU-разложение

1457статей на
этой вики
Добавить новую страницу
Обсуждение0 Поделиться

Обнаружено использование расширения AdBlock.


Викия — это свободный ресурс, который существует и развивается за счёт рекламы. Для блокирующих рекламу пользователей мы предоставляем модифицированную версию сайта.

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

LU-разложение — представление матрицы A в виде LU, где Lнижнетреугольная матрица с единичной диагональю, а U — верхнетреугольная. LU-разложение еще называют LU-факторизацией.

Матрица L является нижнетреугольной с единичной диагональю, поэтому ее определитель равен 1. Матрица U — верхнетреугольная матрица, значит ее определитель равен произведению элементов, расположенных на главной диагонали.

Будем использовать следующие обозначения для элементов матриц L=(l_{ij}), U=(u_{ij}), i,j = 1\dots n; причем диагональные элементы матрицы L: l_{ii} = 1, i = 1\dots n. Тогда, если известно LU-разложение матрицы, её определитель можно вычислить по формуле \det(A) = \det(LU) = \det(L) \det(U) = \det(U)

Найти матрицы L и U можно следующим образом(выполнять шаги следует строго по порядку, т.к. следующие элементы находятся с использованием предыдущих):

  1. u_{1j} = a_{1j},\ j = 1\dots n
  2. l_{j1} = \frac {a_{j1}} {u_{11}},\  j = 2\dots n\  (u_{11} \ne 0)


Для i = 2\dots n

  1. u_{ij} = a_{ij} - \sum_{k=1}^{i-1} l_{ik}u_{kj},\  j = i\dots n
  2. l_{ji} = \frac {1} {u_{ii}}(a_{ji} - \sum_{k=1}^{i-1} l_{jk}u_{ki}),\  j = i+1\dots n

В итоге мы получим матрицы — L и U. В программной реализации данного метода (компактная схема Гаусса) для представления матриц L и U можно обойтись всего одним массивом, в котором совмещаются матрицы L и U. Например вот так(для матрицы размером 3\times 3):

\begin{pmatrix}
  u_{11} & u_{12} & u_{13} \\
  l_{21} & u_{22} & u_{23} \\
  l_{31} & l_{32} & u_{33} \\
\end{pmatrix}

Фрагмент программы на C# для нахождения матриц L и U.

//переменная n(размерность иходной ''квадратной'' матрицы) должна получить значение до этого момента
            double[,] A = new double[n, n];
            double[,] L = new double[n, n];
            double[,] U = new double[n, n];
//до этого момента массив A должен быть полностью определен
            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < n; j++)
                {
                    U[0, i] = A[0, i]
                    L[i, 0] = A[i, 0] / U[0, 0];
                    double sum = 0;
                    for (int k = 0; k < i; k++)
                    {
                        sum += L[i, k] * U[k, j];
                    }
                    U[i, j] = A[i, j] - sum;
                    if (i > j)
                    {
                        L[j, i] = 0;
                    }
                    else
                    {
                        sum = 0;
                        for (int k = 0; k < i; k++)
                        {
                            sum += L[j, k] * U[k, i];
                        }
                        L[j, i] = (A[j, i] - sum) / U[i, i];
                    }
                }
            }
//после выполнения цикла в массиве L - элементы матрицы L, в массиве U - элементы матрицы U.
 
//Теперь можно вычислять определитель

Викия-сеть

Случайная вики