Вычисление обратной матрицы квадратной матрицы высокого порядка, а именно, вычисление алгебраических дополнений и определителя матрицы займёт большое количество машинных ресурсов. Поэтому обращение матрицы при помощи алгебраических дополнений нерационально. В этой статье для вычисления обратной матрицы были использованы нижеследующие методы:
Решение системы AX = E, где A, X, E - квадратные матрицы порядка n, X - обратная A матрица, E - единичная матрица,
-
Использование LU разложения матрицы A = LU [1,2,3]
Обращение матриц было реализовано в виде шаблонов функций шаблона класса MATRIX<T>. В данной статье обсуждается решение вышеуказанными методами обращения квадратной матрицы порядка n и полученные результаты.
Решение системы AX = E
Решение матричного уравнения AX = E для матрицы порядка n A сводится к решению n систем линейных уравнений:
Код реализации решения приводится ниже:
/// <summary>
/// Формирование матриц alpha и gamma в компактной схеме исключения
/// Матрица alpha верхняя треугольная, gamma - нижняя треугольная
/// </summary>
/// <param name="alpha">формируемые матрицы</param>
/// <returns>значение определителя матрицы</returns>
template <typename T>
T MATRIX<T>::FormMatrixCompactScheme(MATRIX& alpha)
{
if (this->m_columns != this->m_rows) return NAN;
int n = this->m_rows;
for (int i = 0; i < n; i++)
{
*(alpha.m_data + i * n) = *(this->m_data + i * n);
if (i > 0) *(alpha.m_data + i) = *(this->m_data + i) / *this->m_data;
}
T sum = 0;
int k = 1, i = 1;
while (i < n)
{
if (k >= n)
{
k = 1; i++;
if (i >= n) break;
}
if (i >= k)
{
sum = 0.0;
for (int j = 0; j <= k - 1; j++)
{
sum += *(alpha.m_data + i * n + j) * *(alpha.m_data + j * n + k);
}
*(alpha.m_data + i * n + k) = *(this->m_data + i * n + k) - sum;
}
else
{
sum = 0.0;
for (int j = 0; j <= i - 1; j++)
{
sum += *(alpha.m_data + i * n + j) * *(alpha.m_data + j * n + k);
}
if (abs(*(alpha.m_data + i * n + i)) < 1.0e-18)
{
return 0.0;
}
*(alpha.m_data + i * n + k) = (*(this->m_data + i * n + k) - sum) / *(alpha.m_data + i * n + i);
}
k++;
}
// вычисление определителя
T det = 1;
for (int i = 0; i < n; i++)
det *= *(alpha.m_data + i * n + i);
return det;
}
/// <summary>
/// Решение системы линейных алгебраических уравнений A*x = b с
/// верхней треугольной матрицей
/// </summary>
/// <param name="A">верхняя треугольная матрица системы</param>
/// <param name="b">вектор правой части системы</param>
/// <param name="x">решение системы</param>
template <typename T>
void TriangleSolve(MATRIX<T>& A, VECTOR<T>& b, VECTOR<T>& x)
{
int n = b.m_size;
VECTOR<T> beta(n);
T sum = 0;
*beta.m_data = *b.m_data / *A.m_data;
for (int i = 1; i < n; i++)
{
sum = 0.0;
for (int j = 0; j <= i - 1; j++)
sum += *(A.m_data + i * n + j) * *(beta.m_data + j);
*(beta.m_data + i) = (*(b.m_data + i) - sum) / *(A.m_data + i * n + i);
}
// решение системы уравнений с труегольной матрицей
*(x.m_data + n - 1) = *(beta.m_data + n - 1);
for (int i = n - 2; i >= 0; i--)
{
sum = 0.0;
for (int j = n - 1; j > i; j--)
sum += *(A.m_data + i * n + j) * *(x.m_data + j);
*(x.m_data + i) = *(beta.m_data + i) - sum;
}
}
/// <summary>
/// Копировать вектор в j-ю колонку матрицы
/// </summary>
/// <param name="v">вектор</param>
/// <param name="j">номер колонки</param>
template <typename T>
void MATRIX<T>::CopyColumn(VECTOR<T>& v, int j)
{
if (m_columns < j)
{
return;
}
if (m_rows != v.size())
{
return;
}
for (int i = 0; i < m_rows; i++)
*(m_data + i * m_columns + j) = v[i];
}
/// <summary>
/// Вычисляет первую норму матрицы
/// </summary>
/// <returns>значение первой нормы матрицы</returns>
template <typename T>
T MATRIX<T>::normI()
{
T norm = 0;
for (int i = 0; i < m_rows; i++)
{
T sum = 0;
for (int j = 0; j < m_columns; j++)
sum += abs(*(m_data + i * m_columns + j));
if (sum > norm) norm = sum;
}
return norm;
}
/// <summary>
/// Обращение марицы при помощи решения систем уравнений A*X = E,
/// столбцы матрицы X - столбцы обратной к A матрицы,
/// E - единичная матрица
/// </summary>
/// <returns>обратную матрицу</returns>
template <typename T>
MATRIX<T> MATRIX<T>::Invert()
{
MATRIX A(m_rows, m_columns);
if (m_rows != m_columns)
return A;
MATRIX alpha(m_rows, m_columns);
T det = FormMatrixCompactScheme(alpha);
if (abs(det) < 1.0e-36)
return A;
for (int i = 0; i < m_rows; i++)
{
VECTOR<T> e(m_rows), x(m_rows);
e[i] = 1;
TriangleSolve(alpha, e, x);
A.CopyColumn(x, i);
}
// итерационное уточнение обратной матрицы
if (m_rows >= MIN_SIZE_INVERSION)
{
MATRIX E(m_rows, m_columns);
for (int i = 0; i < m_rows; i++)
*(E.m_data + i * m_columns + i) = 1;
int iter = 0;
T norm;
do
{
MATRIX R(E - *this * A);
A = A * (E + R);
norm = R.normI();
if (++iter > MAX_ITER_NUMBER) break;
} while (norm < 1.0e-17);
}
return A;
}
Перегрузка операторов *, =, +, - реализована в шаблоне класса MATRIX<T>. Решение системы уравнений осуществлялось с использованием компактной схемы исключения [4].
Обращение матрицы с использованием LU разложения матрицы
Разложение матрицы A = LU на произведение нижней треугольной L и верхней треугольной U может быть использовано не только для решения системы линейных алгебраических уравнений, но и для обращения матрицы. Описание метода обращения матрицы при помощи LU разложения приведён в источниках [2,3] и заключается в следующем:
Обозначая искомые элементы матрицы через
и учитывая, что треугольные матрицы при обращении сохраняют свою структуру, последние соотношения можно записать в виде:
где символом '*' обозначены элементы, знание значений которых для нахождения обратной матрицы не требуется.
Из этих соотношений можно получить выражения для коэффициентов обратной матрицы :
Код реализации решения приводится ниже:
/// <summary>
/// Декомпозиция матрицы A = LU
/// L - нижняя треугольная матрица, на главной диагонали которой расположены единицы
/// U - верхняя треугольная матрица
/// </summary>
/// <param name="alfa">Матрицы L и U, ниже главной диагонали которой
/// расположены внедиагональные элементы L,
/// на главной диагонали и выше расположены элементы матрицы U</param>
/// <returns>Определитель матрицы</returns>
template <typename T>
T MATRIX<T>::LUDecomposition(MATRIX& alfa)
{
T det = 0;
if (m_rows != m_columns) return det;
// декомпозиция матрицы
for (int i = 0; i < m_rows; i++)
for (int j = 0; j < m_columns; j++)
{
T val = 0;
if (i <= j)
{
for (int k = 0; k <= i - 1; k++)
val += *(alfa.m_data + i * alfa.m_columns + k) * *(alfa.m_data + k * alfa.m_columns + j);
*(alfa.m_data + i * alfa.m_columns + j) = *(m_data + i * m_columns + j) - val;
}
else
{
for (int k = 0; k <= j - 1; k++)
val += *(alfa.m_data + i * alfa.m_columns + k) * *(alfa.m_data + k * alfa.m_columns + j);
if (abs(*(alfa.m_data + j * alfa.m_columns + j)) < 1.0e-36) return 0;
*(alfa.m_data + i * alfa.m_columns + j) = (*(m_data + i * m_columns + j) - val) / *(alfa.m_data + j * alfa.m_columns + j);
}
}
det = 1;
for(int i = 0; i < alfa.m_rows; i++)
det *= *(alfa.m_data + i * alfa.m_columns + i);
return det;
}
/// <summary>
/// Вычисляет первую норму матрицы
/// </summary>
/// <returns>значение первой нормы матрицы</returns>
template <typename T>
T MATRIX<T>::normI()
{
T norm = 0;
for (int i = 0; i < m_rows; i++)
{
T sum = 0;
for (int j = 0; j < m_columns; j++)
sum += abs(*(m_data + i * m_columns + j));
if (sum > norm) norm = sum;
}
return norm;
}
/// <summary>
/// Обращение матриы с пощью LU разложения
/// </summary>
/// <returns>обратную матрицу</returns>
template <typename T>
MATRIX <T> MATRIX <T>::InvertLT()
{
MATRIX D(m_rows, m_columns), alpha(m_rows, m_columns);
if (m_rows != m_columns) // матрица должна быть квадратной
return D;
T det = LUDecomposition(alpha); // декомпозиция A = LU
if (abs(det) < 1.0e-36)
return D;
// формирование элементов обратной матрицы
int n = m_rows;
for (int i = n-1; i >= 0; i--)
for(int j = n-1;j >= 0; j--)
{
T sum = 0;
if (i < j)
{
for (int k = i + 1; k < n; k++)
sum -= *(alpha.m_data + i * alpha.m_columns + k) * *(D.m_data + k * D.m_columns + j);
*(D.m_data + i * D.m_columns + j) = sum / *(alpha.m_data + i * alpha.m_columns + i);
}
else if (i == j)
{
for (int k = j + 1; k < n; k++)
sum += *(alpha.m_data + j * alpha.m_columns + k) * *(D.m_data + k * D.m_columns + j);
*(D.m_data + j * D.m_columns + i) = (1-sum) / *(alpha.m_data + j * alpha.m_columns + j);
}
else
{
for (int k = j + 1; k < n; k++)
sum -= *(alpha.m_data + k * alpha.m_columns + j) * *(D.m_data + i * D.m_columns + k);
*(D.m_data + i * D.m_columns + j) = sum;
}
}
// итерационное уточнение обратной матрицы
if (m_rows >= MIN_SIZE_INVERSION)
{
MATRIX E(m_rows, m_columns);
for (int i = 0; i < m_rows; i++)
*(E.m_data + i * m_columns + i) = 1;
int iter = 0;
T norm;
do
{
MATRIX R(E - *this * D);
D = D * (E + R);
norm = R.normI();
if (++iter > MAX_ITER_NUMBER) break;
} while (norm < 1.0e-17);
}
return D;
}
Результаты расчётов
Расчёты по обращению квадратной матрицы порядка n проводились обоими методами для разных значений n. Исходная матрица A порядка n заполнялась при помощи генератора случайных чисел в интервале от -1000 до 1000. В качестве меры погрешности вычислений была использована I-норма
матрицы , где E - единичная матрица.
Расчёты проводились без итерационного уточнения и с итерационным уточнением обратной матрицы.
Итерационное уточнение осуществлялось следующим образом [2]. Пусть первое приближение матрицы
. Если при этом
, то можно построить итерационный процесс:
Непосредственной проверкой можно убедиться в том, что [2]:
Откуда далее следует оценка погрешности [2]:
Расчёт без итерационного уточнения
Результаты расчётов без итерационного уточнения матрицы приведены в нижеследующей таблице:
Порядок матрицы A |
Решение уравнения AX=E |
Декомпозиция A=LU |
||
Время, сек |
Погрешность |
Время, сек |
Погрешность |
|
50 |
0,0007115 |
0,0003418 |
||
100 |
0,0030217 |
0,0024037 |
||
200 |
0,0238938 |
0,0193017 |
||
500 |
0,349852 |
0,288407 |
||
1000 |
2,83838 |
2,36379 |
0,0509241 |
|
2000 |
27,9798 |
33,5439 |
0,00136141 |
|
Расчёт с итерационным уточнением
По приведённым результатам расчёта без итерационного уточнения было сделано заключение о нецелесообразности итерационного уточнения обращения квадратной матрицы порядка ниже 200. Результаты расчётов с итерационным уточнением матрицы приведены в нижеследующей таблице:
Порядок матрицы A |
Решение уравнения AX=E |
Декомпозиция A=LU |
||
Время, сек |
Погрешность |
Время, сек |
Погрешность |
|
200 |
0,0981653 |
0,0836408 |
||
500 |
1,44216 |
1,31034 |
||
1000 |
11,4696 |
10,9775 |
||
2000 |
106,481 |
109,584 |
||
Выводы
Обращение матрицы без итерационного уточнения метод LU декомпозиции показывает лучшие результаты по времени, а метод решения системы AX = E демонстрирует лучшие результаты по точности. При этом, с ростом порядка квадратной матрицы разница в точности расчёта методом LU декомпозиции и методом решения системы AX = E возрастает на несколько порядков, а при обращении матрицы порядка 2000 метод решения системы AX = E демонстрирует лучшие результаты как по времени, так и по точности.
Сравнительный анализ обращения матрицы с итерационным уточнением методом LU декомпозиции и методом решения системы AX = E показывает, что разница как по точности расчёта, так по времени несущественна, а итерационное уточнение вычисления обратной матрицы даёт хорошие результаты по точности методом LU в сравнении с решением без итерационного уточнения.
Список источников
Википедия. LU - разложение/ URL: https://ru.wikipedia.org/wiki/LU-разложение (дата посещения 18.12.2022)
Фаддеев, Д.К. Вычислительные методы линейной алгебры: Учебник/ Фаддеев Д.К, Фаддеева В.Н. — 4‑е изд.— СПб : Лань, 2009. — 736 с.
Численные методы на Python: LU разложение/ URL: https://orion1401.gitbooks.io/numerical_analysys_python/content/lu_razlozhenie.html (дата посещения 22.12.2025)
Корн, Г. Справочник по математике для научных работников и инженеров : определения, теоремы, формулы / Г. Корн, Т. Корн ; пер. с англ. под общ. ред. И. Г. Арамановича. — 3‑е изд. — Москва : Наука, 1973. — 832 с.
Комментарии (7)

TimurZhoraev
30.12.2025 13:17Если порассуждать про какие-либо принципиально новые методы вычислений то может обратить внимание на численно-символические. Составим простой скрипт на Maxima или любой другой CAS:
Q:makelist(makelist(a[j,i],i,1,4),j,1,4); A: apply ('matrix,Q); B:A^^-1; horner(num(B[1,1])); horner(denom(B[1,1]));Сформировать например, матрицу 4х4, взять ей обратную и посмотреть что получается с числителем и знаменателем, например, для первого элемента применив схему Горнера.

Исходная матрица 
Числитель первого элемента обратной матрицы 
Знаменатель первого элемента обратной матрицы Разумеется, что это следует из определителей матриц-миноров, однако, можно выявить индексную арифметику для некоего цифрового фильтра с заданными коэффициентами и операцией умножения с накоплением. В этом случае знаменатель считается один раз (он общий для всех элементов обратной матрицы). А вот числители вычисляются для каждого элемента примерно так:

Вычисление числителя Умножение с накоплением идёт по внутренним скобкам как коэффициент умноженный на отсчёт. Иными словами мы представляем матрицу в виде массивов отсчётов как это бы делали для цифрового фильтра - умножение на коэффициент. То есть фактически всё распадается на работу с индексами и формирование промежуточных массивов с результатами. И если расположить элементы как показано то получается что-то вроде "бабочки" для БПФ. Наверняка может быть матрицы с размерностью кратной степени 2 имеют такой сверхбыстрый алгоритм.

Nemoumbra
30.12.2025 13:17Ага, сиквел к прошлой статье подъехал. Зачем это на Хабре? Линал запрогали и выложили... Никаких новых идей, как будто лаба во вычматам.
Так, теперь код-ревью. Иду сверху вниз по файлам.
MatrixVectorTemplate.hpp- тут вижуusing namespace std;. Вас за такое на части разорвать могут. Кстати, инклюдить надо неmath.h, аcmath.
Дальше, у вас умерла кодировка в файле => русский язык выглядит, как тарабарщина.
Зачем метод классаinline int size()? Инлайнить компилятор будет и без ваших подсказок. А почему не помечено словомconst? Хотите, чтобы у константных векторов нельзя было спросить размер?Почему указатель
m_dataинициализируете числовой константой0? У вас отнялиnullptr? Ну хотя быNULL, но всё равно плохо.
А почему не используете списки инициализации в конструкторах?
Из вашей реализации копи-конструктора я вижу, что у вас отвратительные знания основ ООП в C++, т.к. вы зачем-то проверяете, нет ли у вас там аллоцированного массива и предварительно удаляете, если есть.
В реализации оператора присваивания отсутствует защита от присваивания себе.
Почему-то вы считаете, что умножать векторы разной длины - норм (возвращаем ноль), а вот складывать - не норм (делаемthrow "Âåêòîðû èìåþò ðàçíóþ ðàçìåðíîñòü";).
Почему бросаете не что-то, наследующеся отstd::exception? Почему в блоке после выброса исключения какой-то ещё код?
Кстати, почему вы понапихали френдов в код? Обычно бинарные операторы, тип результата которых совпадает с типами обоих аргументов, реализуют через копию + составное присваивание...
А ещё странно, что вы где-то используетеthisдля доступа к полям, а где-то - нет. Нужен общий стиль. C-style касты понапиханы... В целом, очень много непонятных названий, особенно всякие однобуквенные переменные. Дефайны в коде есть для констант - тоже плохо... Магические числа в рандомных местах (всякие эпсилоны в сравнениях).
std::rand используете вместо качественных генераторов, а в функцииrandomDoubleпри неудачном рнг делите на ноль. Кстати, непонятно, почему дабл в названии есть - это можно инстанцировать и для целых типов.Уфф... Язык знаете плохо, общая задумка слабая, совсем непонятно, зачем работаете с голой памятью вместо уже имеющихся в языке классов.
Gay_Lussak
У вас шаблонная функция, а епсилон фиксированная? А вообще для этого есть
std::numeric_limits<T>::epsilonЧто за магическое число?
Уверены, что тут никогда не будет деления на 0?
А что произойдет, если я передам T = std::string?
Для копирования столбцов по-хорошему нужно перегружать оператор присваивания, а не писать отдельную функцию CopyColumn. Еще и VECTOR по неконстантной ссылке.
Да и зачем вам свой matrix класс, если кроме обращения элементов тут почти ничего нет, не все операторы перегружены, безопасности исключений тут нет. Использовали бы тогда уж
std::vector<std::vector>>там хотя-бы более безопасно работать.Или на питоне, на порядки же проще да и не напишите вы на С++ быстрее numpy.
Ну и вы проверяли на численную стабильность? Обычно для этого используют LUP разложение. А у вас вроде такого нет.
А вообще смысл статьи? Нового ничего нет. Если учебный проект, то сделан он халтурно, как в плане кода, так и в плане математики. Особенности вычислений с плавающей точкой не учтены от слова совсем.