C++ 程序计算矩阵的行列式

2024年8月28日 | 阅读 8 分钟

在本文中，我们将使用不同的方法来计算矩阵的行列式。在求行列式的值之前，我们必须了解矩阵行列式。矩阵的行列式是一个特定的整数，只适用于方阵（行数和列数相同的矩阵）。行列式在微积分和其他代数矩阵中经常使用；它描述了矩阵在一个实数上下文中的情况，该实数可用于求解线性方程组并识别矩阵的逆矩阵。

如何计算？

矩阵的行列式可以这样确定：对于第一行或第一列的每个元素，获取这些分量的代数余子式，将分量与其相关代数余子式的行列式相乘，然后以相反的符号将它们相加。在最基本的情况下，1*1 矩阵的行列式就是单个值本身。元素的代数余子式是通过从该矩阵中删除元素的列和行而获得的矩阵。

方法 1

文件名：Determinant.cpp

让我们举一个例子来说明 C++ 中矩阵的行列式。

//Program to find the determinant of the matrix
#include <iostream>
using namespace std;

// declaring the dimensions of the square matrix
#define N 4

// Function for finding the cofactor
// matrix[p][q] in tem[][]. num is
// the current values of matrix[][]
void getCofactorMatrix(int matrix[N][N], 
				int tem[N][N], int p1,
				int q1, int num)
{
	int i = 0, j = 0;
 //Loop for iterating of the matrix
	for (int rows = 0; rows < num; rows++)
	{
		for (int cols = 0; cols < num; cols++) 
		{
			// Transferring into a temporary matrix 
			// just those elements that are not in the supplied row and column
			if (rows != p1 && cols != q1) 
			{
				tem[i][j++] = matrix[rows][cols];

				// Because the row is complete, increase the row index as well as reset the cols index.
				if (j == num - 1) 
				{
					j = 0;
					i++;
				}
			}
		}
	}
}

/* A recursive function for determining the determinant of a matrix, where num is the current length of the matrix[][].*/

int determinantOfMatrix(int matrix[N][N], int num)
{
	// result
	int Determinent = 0; 

	// If the matrix has a single element, this is the default case.
	if (num == 1)
		return matrix[0][0];

	// for storing the co-factors
	int tem[N][N]; 

	//for storing sign
	int signs = 1; 

	//iterating over each element
	for (int f = 0; f < num; f++) 
	{
		
		getCofactorMatrix(matrix, tem, 0, f, num);
		Determinent += signs * matrix[0][f] * 
			determinantOfMatrix(tem, num - 1);

		//Adding opposite sign
		signs = -signs;
	}

	return Determinent;
}
// function to display matrix
void displayMatrix(int matrix[N][N], 
			int rows, int cols)
{
	for (int i = 0; i < rows; i++) 
	{
		for (int j = 0; j < cols; j++)
			cout << " " << matrix[i][j];
		cout << "n";
	}
}

// Main
int main()
{
	int matrix[N][N]= {{1, 3, 4, -1},
					{2, 0, 3, 5},
					{2, 9, 2, -3},
					{1, 2, 1, 1}};

	// function calling
	cout << "The Determinant of the matrix is: " << 
			determinantOfMatrix(matrix, N);
	return 0;
}

输出

The determinant of the matrix is: 10

时间复杂度：O(N!)

说明

getCofactorMatrix() 函数的时间复杂度为 O(N^2)。可以使用以下递归关系来计算 determinantOfMatrix() 方法的时间复杂度：

T(N) =N*T(N-1) + O(N^3)

第一个数字 N*T(N-1) 表示计算 (N-1) x (N-1) 子矩阵的行列式所需的时间。相比之下，第二个值 O(N-3) 表示计算原始矩阵第一行中每个分量所需的代数余子式所需的时间。我们可以将确定 NxN 矩阵的因子计算为其行列式的总和 (N-1)x(N-1) 矩阵，其中每个矩阵都需要 O(N^2) 操作来获取代数余子式，使用按位扩展。因此，determinantOfMatrix() 方法的时间复杂度为 O(N!)，这是矩阵是重组矩阵时最极端的情况。

display() 函数的时间复杂度为 O(N^2)，因为它遍历所有矩阵成员以打印它们。它的计算复杂度为 O(N!)，因为 determinantOfMatrix() 函数支配了程序代码的整个时间复杂度。

空间复杂度：O(N*N)

通过应用行列式性质，我们遍历每个对角线元素，使对角线下方所有元素都变为零。

方法 2

如果此对角线元素为零，我们将查找同一列中的下一个非零元素。

有两种可能性。

情况 1：如果没有非零元素。在这种情况下，矩阵的行列式值为 0。

情况 2：如果存在非零元素，有两种可能性。

情况 a：如果索引与对角线行成员匹配，我们使用行列式性质将所有列项归零。
情况 b：在这里，我们必须交换行与相应的对角线元素列，并继续执行情况 'a' 的过程。

示例

文件名：Determinanat2.cpp

//Program to find the determinant of a matrix
#include <bits/stdc++.h>
using namespace std;

// declaring the dimensions of a matrix
#define N 4

// Function to get determinant of matrix
int detOfMatrix(int matrix[N][N], int n)
{
	// variables initiaiazation
	int nums1, nums2, determinant = 1, in,
					sum = 1; 

	// temp array for storing the rows
	int tem[n + 1];

	// iterating over loop elements
	for (int i = 0; i < n; i++) 
	{
		// index value
		in = i; 

		//Find the index which has non-zero elements
		while (in < n && matrix[in][i] == 0) 
		{
			in++;
		}

		//If no nonzero element is found
		if (in == n) 
		{
			// if it is zero
			continue;
		}
		if (in != i) 
		{
			// looping over the matrix to swap elements
			for (int j = 0; j < n; j++) 
			{
				swap(matrix[in][j], matrix[i][j]);
			}

			//When we move rows through determinant features, the sign of the determinant changes.
			determinant = determinant * pow(-1, in- i);
		}

		//Sorting the diagonal elements
		for (int j = 0; j < n; j++) 
		{
			tem[j] = matrix[i][j];
		}

		// visiting over every element of the below diagonal
		for (int j = i + 1; j < n; j++) 
		{
			// the diagobal element
			nums1 = tem[i]; 

			//the element of the next row
			nums2 = matrix[j][i]; 

			// iterating over a columns
			for (int k = 0; k < n; k++) 
			{
				// Making the diagonal 
				// element and the subsequent row element equal through multiplication 
				matrix[j][k]
					= (nums1 * matrix[j][k]) - (nums2 * tem[k]);
			}
			sum = sum * nums1; 
		}
	}

	//The diagonal elements are multiplied to get the determinant
	for (int i = 0; i < n; i++) 
	{
		determinant = determinant * matrix[i][i];
	}

	
	return (determinant / sum); 
}

// Driver code
int main()
{
	int matrix[N][N] = {{3, 0, 2, -2},
					{3, 0, 3, 4},
					{3, 1, 4, -3},
					{1, 0, 4, 9}};

	// function calling 
	printf("The Determinant of the given matrix is: %d",
			detOfMatrix(matrix, N));
	return 0;
}

输出

The Determinant of the given matrix is: 31

复杂度

时间复杂度：O(N³⁾

空间复杂度: O(N)

方法 3：高斯-约旦消元法

步骤：

从给定矩阵开始，并将行列式设置为 1。
在跟踪行列式的同时，使用简单的行操作将矩阵转换为其行阶梯形。
如果有任何行交换操作，则将行列式的值乘以 -1。
如果任何行包含导致零值的系数，则行列式为零，我们可以在此处停止。
行列式是行阶梯形中对角线元素的乘积。
返回行列式的值。

示例

文件名：DeterminantByGauss.cpp

#include <iostream>
#include <cmath>
using namespace std;
const int MAXNum = 105;
double array[MAXNum][MAXNum];
double determinantValue(int num) {
	double determinant = 1.0;
	for (int i = 0; i < num; i++) {
		int pivotelement = i;
		for (int j = i + 1; j < num; j++) {
			if (abs(array[j][i]) > abs(array[pivotelement][i])) {
				pivotelement = j;
			}
		}
		if (pivotelement != i) {
			swap(array[i], array[pivotelement]);
			determinant *= -1;
		}
		if (array[i][i] == 0) {
			return 0;
		}
		determinant *= array[i][i];
		for (int j = i + 1; j < num; j++) {
			double fact = array[j][i] / array[i][i];
			for (int k = i + 1; k < num; k++) {
				array[j][k] -= fact * array[i][k];
			}
		}
	}
	return determinant;
}
int main() {
	int num = 4;
	double mat[4][4] = {{2, 1, 2, -1},
						{3, 0, 4, 3},
						{1, 3, 4, -3},
						{1, 0, 7, 1}};
	for (int i = 0; i < num; i++) {
		for (int j = 0; j < num; j++) {
			array[i][j] = mat[i][j];
		}
	}
	double determinant = determinantValue(num);
	cout << "The Determinant value is= " << determinant << endl;
	return 0;
}

输出

The Determinant value is= 85

复杂度

时间复杂度：O(N³)，其中 n 是矩阵中的总行数（或列数）。

辅助空间：O(1)，因为矩阵已就地修改。

方法 4：余子式展开

步骤：

创建一个函数，使用余子式展开计算矩阵的行列式值。
如果正在计算的矩阵不是方阵，则返回错误语句。
如果矩阵为 1×1，则返回一个元素。
如果元素组合为 2×2，则使用 ad-bc 公式返回行列式的值。
如果元素数量大于 2×2，则遍历第一行并计算每个分量的余子式。
将每个余子式乘以其关联元素，并带上元素的符号 (+/-)。
将步骤 6 的结果相加即可获得行列式。

示例

文件名：Cofactor.cpp

#include<iostream>
#include<cmath>
using namespace std;

int determinantValue(int mat[4][4], int num){
	int determinant = 0;
	int submat[4][4];
	
	if(num == 1){
		return mat[0][0];
	}
	else if(num == 2){
		return ((mat[0][0] * mat[1][1]) - (mat[1][0] * mat[0][1]));
	}
	else{
		for(int x = 0; x < num; x++){
			int subin = 0;
			for(int i = 1; i < num; i++){
				int subjn = 0;
				for(int j = 0; j < num; j++){
					if(j == x){
						continue;
					}
					submat[subin][subjn] = mat[i][j];
					subjn++;
				}
				subin++;
			}
			determinant = determinant + (pow(-1, x) * mat[0][x] * determinantValue(submat, num-1));
		}
	}
	return determinant;
}

int main(){
	int mat[4][4] = {{1, 0, 4, 3},
					{6, 1, 0, 4},
					{2, 0, 2, 3},
					{2, 0, 8, 2}};
	int num = 4;
	int determinant = determinantValue(mat, num);
	cout<<"Determinant: "<<determinant<<endl;
	return 0;
}

输出

The Determinant is: 24

复杂度

时间复杂度：O(N!)

空间复杂度：O(N^2)

下一主题C++ 中的地址调用

C++ 程序计算矩阵的行列式

如何计算？

方法 1

方法 2

方法 3：高斯-约旦消元法

方法 4：余子式展开

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

C++ 教程

C++ 控制语句

C++ 函数

C++ 数组

C++ 类和对象

C++ 构造函数

C++ 继承

C++ 多态

C++ 抽象

C++ 命名空间

C++ 模板

C++ 字符串

C++ 指针

信号处理

C++ 异常

C++ 文件与流

C++ STL 教程

面试题

选择题

C++ 程序

C++ STL Stack

C++ STL Bitset

C++ STL Deque

C++ STL List

C++ STL Map

C++ STL Math

C++ STL priority_queue

C++ STL Queue

C++ STL Multiset

C++ STL Multimap

C++ STL Set

C++ STD Strings

C++ STL Vector

C++ 操纵符

C++ STL Algorithms

C++ Algorithm

C++ Iterators

C++ 杂项

C++ 程序计算矩阵的行列式

如何计算？

方法 1

方法 2

方法 3：高斯-约旦消元法

方法 4：余子式展开

相关帖子

C++ 拔河

C++ ios::rdstate() 函数

C++ 中 array::fill() 和 array::swap() 的区别

C++ 反转数字程序

C++ 函数重载与函数重写的区别

C++ 树实现

C++ KMP 算法

C++ npos

C++ ratio_greater() 函数

C++ 银行家算法

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题