【计算方法】#01 高斯消去法和列主元高斯消去法的原理简介及C++实现

满足以下条件任一即可

消元过程(第 k k k次消元)： { a i j ( k ) = a i j ( k ? 1 ) ? a i k ( k ? 1 ) a k k ( k ? 1 ) a k j ( k ? 1 ) = a i j ( k ? 1 ) ? l i k a k j ( k ? 1 ) , i = k 1 , k 2 , . . . , n ; j = k 1 , k 2 , . . . , n b i ( k ) = b i ( k ? 1 ) ? l i k b k ( k ? 1 ) , i = k 1 , k 2 , . . . , n l i k ? a i k ( k ? 1 ) a k k ( k ? 1 ) , i = k 1 , k 2 , . . . , n \begin{cases} &a_{ij}^{(k)}=a_{ij}^{(k-1)}-\frac{a_{ik}^{(k-1)}}{a_{kk}^{(k-1)}}a_{kj}^{(k-1)}=a_{ij}^{(k-1)}-l_{ik}a_{kj}^{(k-1)}, \\ &i=k 1,k 2,...,n; j=k 1,k 2,...,n \\ \\ &b_i^{(k)} = b_i^{(k-1)}- l_{ik}b_{k}^{(k-1)}, i=k 1,k 2,...,n \\ \\ &l_{ik} \triangleq \frac{a_{ik}^{(k-1)}}{a_{kk}^{(k-1)}}, i=k 1, k 2, ..., n \end{cases} ????⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎧​​aij(k)​=aij(k−1)​−akk(k−1)​aik(k−1)​​akj(k−1)​=aij(k−1)​−lik​akj(k−1)​,i=k+1,k+2,...,n;j=k+1,k+2,...,nbi(k)​=bi(k−1)​−lik​bk(k−1)​,i=k+1,k+2,...,nlik​≜akk(k−1)​aik(k−1)​​,i=k+1,k+2,...,n​

回代过程： { x n = b n ( n − 1 ) a n n ( n − 1 ) , x k = b k ( k − 1 ) − ∑ j = k + 1 n a k j ( k − 1 ) x j a k k ( k − 1 ) , k = n − 1 , n − 2 , . . . , 2 , 1 \left\{ \begin{aligned} x_n &= \frac{b_n^{(n-1)}}{a_{nn}^{(n-1)}},\\ x_k &= \frac{b_k^{(k-1)}-\sum\limits_{j=k+1}^{n}a_{kj}^{(k-1)}x_j}{a_{kk}^{(k-1)}}, k=n-1,n-2,...,2,1 \end{aligned} \right. ⎩⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎧​xn​xk​​=ann(n−1)​bn(n−1)​​,=akk(k−1)​bk(k−1)​−j=k+1∑n​akj(k−1)​xj​​,k=n−1,n−2,...,2,1​

令运算量为乘除法个数，则

消元过程： N 1 = ∑ k = 1 n − 1 ( n − k ) 2 + 2 ( n − k ) = n 3 / 3 + n 2 / 2 − 5 n / 6 N_1=\sum\limits_{k=1}^{n-1}(n-k)^2+2(n-k)=n^3/3+n^2/2-5n/6 N1​=k=1∑n−1​(n−k)2+2(n−k)=n3/3+n2/2−5n/6

回代过程： N 2 = 1 + ( n − 1 ) + ∑ k = 1 n − 1 ( n − k ) = n 2 / 2 + n / 2 N_2=1 + (n-1) + \sum\limits_{k=1}^{n-1}(n-k)=n^2/2 + n/2 N2​=1+(n−1)+k=1∑n−1​(n−k)=n2/2+n/2

高斯消去法总运算量： N = N 1 + N 2 = n 3 / 3 + n 2 − n / 3 N=N_1+N_2=n^3/3+n^2-n/3 N=N1​+N2​=n3/3+n2−n/3

时间复杂度：