线性方程组的求解

这篇具有很好参考价值的文章主要介绍了线性方程组的求解。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

克莱姆法则

求解线性方程组有一种比较简单易行的方法就是用克莱姆法则通过行列式的计算以解出方程,下面给出行列式解方程的代码并分析优缺点;

对于一个n元一次方程组,如果可以将其化为n阶行列式就能使用克莱姆法则;例如:

线性方程组的求解

有 D=  

线性方程组的求解

 用(b1,b2,...bn)T替换D的第一列、第二列、。。第n列得到D1D2。。Dn

行列式计算的代码:

double rec(int n, vector<double>D) {
	if (n == 1) {
		return D.back();
	}
	int e = 1;//设置符号
	double sum = 0;
	for (int k = 0; k < n; k++) {
		vector<double>d;
		for (int i = 1; i < n; i++) {//i==1表示从第一行开始,因为第0行是被展开的量;
			for (int j = 0; j < n; j++) {
				if (k == j)continue;     //划去同列元素;
				d.push_back(D[i*n + j]);
 
			}
		}
		sum += D[k] * e*rec(n - 1, d);
		e *= -1;
	}
	return sum;
}

分别计算出各个行列式的值后

X1=D1/D,X2=D2/D..Xn=Dn/D;非常的简单;

#include<iostream>
#include<vector>
using std::vector;
double rec(int n, vector<double>D) {
	if (n == 1) {
		return D.back();
	}
	int e = 1;//设置符号
	double sum = 0;
	for (int k = 0; k < n; k++) {
		vector<double>d;
		for (int i = 1; i < n; i++) {//i==1表示从第一行开始,因为第0行是被展开的量;
			for (int j = 0; j < n; j++) {
				if (k == j)continue;     //划去同列元素;
				d.push_back(D[i*n + j]);

			}
		}
		sum += D[k] * e*rec(n - 1, d);
		e *= -1;
	}
	return sum;
}
int main() {
	int n;
	std::cin >> n;
	vector<double>D[20], B;
	//得到D的行列式与B
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			double d;
			std::cin >> d;
			D[0].push_back(d);
		}
		double d;
		std::cin >> d;
		B.push_back(d);
	}
	//利用B得到Di
	for (int k = 0; k < n; k++) {
		D[k + 1] = D[0];
		for(int i=0;i<n;i++)
		D[k + 1][i*n + k] = B[i];
	}
	//求解;
	double d = rec(n, D[0]);
	for (int i = 1; i <= n; i++) {
		double x = rec(n, D[i]) / d;
		std::cout << "x" << i << "=" << x << "\n";
	}
	return 0;
}

 克莱姆法则计算的优点:

1:不会在中间计算中丢失精度,对于整数系数的方程可比较简单地通过gcd直接消除精度差

2:行列式计算的代码写好后,整个的代码就很好写了,没多少细节处理;

缺点:

时间复杂度为阶乘,无法求出10组以上的方程组 

高斯消元

先看简单的情况,n个方程组:

对于上面的方程组可以写成一个增广矩阵;

若将其化为如下的上三角矩阵,就能很容易的进行求解了:

从第一行第一列开始,设当前行为r,列为c,

找行:找出r及r下面所有行中,第c列元素绝对值最大的一行,与当前行交换;

消元:对于该行的第一个非0元素,即第c列,将其化为1,利用该行将下面所有与这个1所在的列的元素消为0;(若该行第c列为0,也就是找出的绝对值最大值为0,说明有一组无效方程,则将c进行+1);

开一个二维数组存储一个n行n+1列的矩阵:

算法流程:为方便计算将行列从0开始

for(r=0,c=0;c<n;c++)://r表示当前行,c表示当前列,r同时计算矩阵的有效方程数;

1:k=r

2:for(i=r+1;i<n;i++):if(|akc|<|aic|)k=i//得到第c列元素绝对值最大的行;

3:if(|akc|==0)continue;//第c列最大值为0,则该列全为0直接进行下一层循环;

4:swap(ar,ak)//交换这两行;

5:arj/=arc//使该行第一个非0元素,即第c列化为1

6:for(i=r+1,i<n;i++):aij-=aic*arj//利用第r行将下面的第c列消为0;

7:r++//有效方程数加一

 矩阵变换代码:

for (r = 0, c = 0; c < n; c++) {
		int k = r;
		for (int i = r + 1; i < n; i++)
			if (fabs(a[i][c]) > fabs(a[k][c]))
				k = i;
		if (fabs(a[k][c]) < eps)continue;//如果c列最大的一行趋于0,之后的行同样趋于0,则该行视为无效方程组
		for (int i = c; i <= n; i++)std::swap(a[r][i], a[k][i]);//交换第r行与第k行
        for (int i = n; i >= c; i--)a[r][i] /= a[r][c];//c列元素归一:
		for (int i = r + 1; i < n; i++) 
			for (int j = n; j >= c; j--) 
				a[i][j] -= a[i][c] * a[r][j];//消元
			 
		
		r++;//秩+1
	}

得到该矩阵后,

若r==n,显然xn=bn;解得xn后可以代到上一行解出xn-1。。。。最后解出x1

因此可以从下往上依次算出所有x

回代代码块:

for (int i = n - 1; i >= 0; i--) {
			for (int j = i + 1; j < n; j++) {
				a[i][n] -= a[i][j] * a[j][n];
			}
		}

解得xi=ain

若r<n,如果存在第r行后的b不为0,则左右两式矛盾(等式左边全部系数消为0,则等式左边为0)

否则有无穷多个解

完整代码:

#include<iostream>
#include<vector>
#include<cstring>
#include<iomanip>
const double eps = 1e-5;
using std::vector;
double a[107][107];
int n;
void read() {
	std::cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j <= n; j++) {
			std::cin >> a[i][j];
		}
	}
}
void print() {
	for (int i = 0; i < n; i++) {
		std::cout << "x" << i + 1<<" = " << a[i][n] << "\n";
	}
}

void solve() {
	read();//读入数据
	int r, c;
	for (r = 0, c = 0; c < n; c++) {
		int k = r;
		for (int i = r + 1; i < n; i++)
			if (fabs(a[i][c]) > fabs(a[k][c]))
				k = i;
		if (fabs(a[k][c]) < eps)continue;//如果c列最大的一行趋于0,之后的行同样趋于0,则该行视为无效方程组
		for (int i = c; i <= n; i++)std::swap(a[r][i], a[k][i]);//交换第r行与第k行
        for (int i = n; i >= c; i--)a[r][i] /= a[r][c];//c列元素归一:
		for (int i = r + 1; i < n; i++) 
			for (int j = n; j >= c; j--) 
				a[i][j] -= a[i][c] * a[r][j];//消元
			 
		
		r++;//秩+1
	}
    //得到一个上三角的矩阵:

	if (r < n) {//无解或无穷解
		for (int i = r ; i < n; i++) {
			if (fabs(a[i][n]) > eps) {
				std::cout << "方程无解\n";
				return;
			}
		}
		//不存在矛盾式子则有无穷解
		std::cout << "方程有无穷解\n";
	}
	else {
		//利用上三角的性质,解出最后一项从下到上往回代
		for (int i = n - 1; i >= 0; i--) {
			for (int j = i + 1; j < n; j++) {
				a[i][n] -= a[i][j] * a[j][n];
			}
		}
		print();//输出解
	}
}
int main() {
	solve();
	return 0;
}

现在看n元,m个方程组的情况;

若m<n;那么就将上面的代码行数改为m就行,最后就会得出有解或无解的答案;

若m>n; r<n依然得到正解,r==n,因为下面还会有方程组即:

线性方程组的求解

还需要判断是否矛盾;因此将判断无解的代码提出来;

for (int i = r; i < m; i++) {
		if (fabs(a[i][n]) > eps) {
			std::cout << "无解";
			return;
		}
	}
	if (r < n) {
		std::cout << "无穷解";
	}
	else {
		for (int i = n - 1; i >= 0; i--) {
			for (int j = i + 1; j < n; j++) {
				a[i][n] -= a[i][j] * a[j][n];
			}
		}
		print();
	}

 实际上最开始n个方程组的代码也可这样写,这是因为将数组定义再全局中自动初始化为0了;

最终代码:

#include<iostream>
#include<vector>
#include<cstring>
#include<iomanip>
#include<cmath>
const double eps = 1e-9;
using std::vector;
double a[107][107];
int n, m;
void read() {
	std::cin >> m >> n;//m个方程组,n个元;
	for (int i = 0; i < m; i++) {
		for (int j = 0; j <= n; j++) {
			std::cin >> a[i][j];
		}
	}
}
void print() {
	for (int i = 0; i < n; i++) {
		std::cout << "x" << i + 1 << " = " << a[i][n] << "\n";
	}
}
void solve() {
	read();
	int r, c;
	for (r = 0, c = 0; c < n; c++) {
		int k = r;
		for (int i = r + 1; i < m; i++)
			if (fabs(a[i][c]) > fabs(a[k][c]))
				k = i;
		if (fabs(a[k][c]) < eps)continue;
		for (int i = c; i <= n; i++)std::swap(a[r][i], a[k][i]);
		for (int i = n; i >= c; i--)a[r][i] /= a[r][c];
		for (int i = r + 1; i < m; i++)
			for (int j = n; j >= c; j--)
				a[i][j] -= a[i][c] * a[r][j];
		r++;
	}
	for (int i = r; i < m; i++) {
		if (fabs(a[i][n]) > eps) {
			std::cout << "无解";
			return;
		}
	}
	if (r < n) {
		std::cout << "无穷解";
	}
	else {
		for (int i = n - 1; i >= 0; i--) {
			for (int j = i + 1; j < n; j++) {
				a[i][n] -= a[i][j] * a[j][n];
			}
		}
		print();
	}
}
int main() {
	solve();
	return 0;
}

高斯消元法的缺点:需要处理的细节较多,中间计算过程对精度的处理需要一定的技巧(例如不使用临时变量保存double型变量)

优点:1:时间复杂度为

           2:可以解n元m个方程组文章来源地址https://www.toymoban.com/news/detail-450151.html

到了这里,关于线性方程组的求解的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 线性代数代码实现(七)求解线性方程组(C++)

    前言:         上次博客,我写了一篇关于定义矩阵除法并且代码的文章。矩阵除法或许用处不大,不过在那一篇文章中,我认为比较好的一点是告诉了大家一种计算方法,即:若矩阵  已知且可逆,矩阵  已知,并且  ,求解矩阵 B 。我认为这种初等行变换的方法还是挺

    2023年04月23日
    浏览(48)
  • matlab使用教程(6)—线性方程组的求解

            进行科学计算时,最重要的一个问题是对联立线性方程组求解。在矩阵表示法中,常见问题采用以下形式:给定两个矩阵 A 和 b,是否存在一个唯一矩阵 x 使 Ax = b 或 xA = b?         考虑一维示例具有指导意义。例如,方程         7x = 21         是否具

    2024年02月14日
    浏览(43)
  • 【算法竞赛模板】求解线性方程组是否有解(求解矩阵的秩)

        在实际运用中需判断线性方程组有无解,可以通过矩阵运算判断线性方程组是否有解 线性方程组有无解总结: 矩阵求解秩流程:    所以:当我们遇到题目问线性方程组是否有解时,只需求解系数矩阵的秩与增广矩阵的秩的关系 。我们可以通过分别求系数矩阵与增

    2024年02月12日
    浏览(39)
  • 牛顿-拉普森法求解线性方程组原理及matlab程序

      在多变量微积分和矩阵理论的交叉点是求解非线性代数方程的迭代方法。设是的 n n n 个未知向量 x ,有 F ( x ) = 0 ∈ R n mathbf{F}left( mathbf{x} right) =0in text{R}^{text{n}} F ( x ) = 0 ∈ R n 就是求解 x 的 n n n 个非线性方程组,其中向量函数具有连续导数,并且雅可比矩阵 F x ( x

    2024年02月05日
    浏览(40)
  • 牛顿(Newton)迭代法求解非线性方程以及方程组的Matlab实现

    必做题目比较简单,写得有些随意,主要还是第二个拓展题目的难度比较高 传入题设数据有: 另附运行截图  

    2024年02月11日
    浏览(49)
  • 线性代数的学习和整理14: 线性方程组求解的3种方法,重点讲矩阵函数求解

    目录 0 写在前面的一些内容 0.1 学习心得: 0.2 参考其他书籍总结的知识点,对照学习 1 线性方程组求解 1.1 常见的线性方程组如下 1.2 记住常见的 矩阵函数的维数的关系 1.3  需要求解的方程组和矩阵的对应关系,需要先厘清 1.3.1 如果只需要求解x,是类 Ax=b的形式 1.3.2   如

    2024年02月05日
    浏览(59)
  • 【学习笔记】求解线性方程组的G-S迭代法

    matlab中调用上述函数结果显示: 哪里出问题了啊?

    2024年02月10日
    浏览(38)
  • 数值分析第二次作业-求解系数矩阵为Hilbert 矩阵的线性方程组

    现要求解系数矩阵由16 阶Hilbert 方程组构成的线性方程组,右端项为  即要求解方程组Ax = b,其中 A=A0,b=b0  分别用高斯-赛德尔方法、最速下降法、共轭梯度法求解如下。 2.1. 高斯-赛德尔方法     2.2. 最速下降法    2.3. 共轭梯度法  在最速下降法中,搜索方向p取的是函数减

    2024年02月05日
    浏览(82)
  • MATLAB数值分析学习笔记:线性代数方程组的求解和高斯消元法

    工程和科学计算的许多基本方程都是建立在守恒定律的基础之上的,比如质量守恒等,在数学上,可以建立起形如 [A]{x}={b} 的平衡方程。其中{x}表示各个分量在平衡时的取值,它们表示系统的 状态 或 响应; 右端向量{b}由无关系统性态的常数组成通常表示为 外部激励。 矩阵

    2023年04月15日
    浏览(63)
  • MATLAB数值分析学习笔记:线性代数方程组的求解和高斯-赛德尔方法

    迭代法是前面介绍的消元法的有效替代,线性代数方程组常用的迭代法有 高斯-赛德尔方法 和 雅克比迭代法, 下面会讲到二者的不同之处,大家会发现两者的实现原理其实类似,只是方法不同,本篇只重点介绍高斯-赛德尔方法。 看了我之前的笔记的同学应该已经对迭代法不

    2024年02月05日
    浏览(60)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包