「如果你不知道递推式」 - 洛谷帖子保存站

如果你不知道递推式

板块P3389 【模板】高斯消元法
楼主zhang_sans
当前回复2
已保存回复2
发布时间2024/10/9 18:50
上次更新2024/10/9 21:40:17

被骇客银狼阻止的越权访问保存失败

如果你不知道递推式

zhang_sans楼主2024/10/9 18:50

那就看看（正好与定义中的时间复杂度 $O(n^3)$ 一致）：

\begin{bmatrix} b_1\\b_2\\b_3\\\vdots\\b_n \end{bmatrix} \div \begin{bmatrix} a_{1,1} & a_{1,2} & a_{1,3} &\cdots & a_{1,n}\\ a_{2,1} &\ddots & & & \vdots\\ a_{3,1} & & \ddots & & \vdots\\ \vdots & & & \ddots & \vdots\\ a_{n,1} & \cdots & \cdots & \cdots & a_{n,n} \end{bmatrix} = \begin{bmatrix} \begin{bmatrix} b_1-\frac{a_{1,n}b_n}{a_{n,n}}\\ b_2-\frac{a_{2,n}b_n}{a_{n,n}} \\b_3-\frac{a_{3,n}b_n}{a_{n,n}} \\\vdots \\b_{n-1}-\frac{a_{n-1,n}}{a_{n,n}} \end{bmatrix} \div \begin{bmatrix} a_{1,1}-\frac{a_{1,n}a_{n,1}}{a_{n,n}} & a_{1,2}-\frac{a_{1,n}a_{n,2}}{a_{n,n}} & a_{1,3}-\frac{a_{1,n}a_{n,3}}{a_{n,n}} &\cdots & a_{1,n-1}-\frac{a_{1,n}a_{n,n-1}}{a_{n,n}}\\ a_{2,1}-\frac{a_{2,n}a_{n,1}}{a_{n,n}} &\ddots & & & \vdots\\ a_{3,1}-\frac{a_{3,n}a_{n,1}}{a_{n,n}} & & \ddots & & \vdots\\ \vdots & & & \ddots & \vdots\\ a_{n-1,1}-\frac{a_{n-1,n}a_{n,1}}{a_{n,n}} & \cdots & \cdots & \cdots & a_{n-1,n-1}-\frac{a_{n-1,n}a_{n,n-1}}{a_{n,n}} \end{bmatrix}\\ \frac{b_n-\sum_{i=1}^{n-1}a_{n,i}\left( \begin{bmatrix} b_1-\frac{a_{1,n}b_n}{a_{n,n}}\\ b_2-\frac{a_{2,n}b_n}{a_{n,n}} \\b_3-\frac{a_{3,n}b_n}{a_{n,n}} \\\vdots \\b_{n-1}-\frac{a_{n-1,n}}{a_{n,n}} \end{bmatrix} \div \begin{bmatrix} a_{1,1}-\frac{a_{1,n}a_{n,1}}{a_{n,n}} & a_{1,2}-\frac{a_{1,n}a_{n,2}}{a_{n,n}} & a_{1,3}-\frac{a_{1,n}a_{n,3}}{a_{n,n}} &\cdots & a_{1,n-1}-\frac{a_{1,n}a_{n,n-1}}{a_{n,n}}\\ a_{2,1}-\frac{a_{2,n}a_{n,1}}{a_{n,n}} &\ddots & & & \vdots\\ a_{3,1}-\frac{a_{3,n}a_{n,1}}{a_{n,n}} & & \ddots & & \vdots\\ \vdots & & & \ddots & \vdots\\ a_{n-1,1}-\frac{a_{n-1,n}a_{n,1}}{a_{n,n}} & \cdots & \cdots & \cdots & a_{n-1,n-1}-\frac{a_{n-1,n}a_{n,n-1}}{a_{n,n}} \end{bmatrix} \right)_i} {a_{n,n}} \end{bmatrix}

其中，左边表示一个线性方程组的解，即：

\begin{cases} a_{1,1}x_1+a_{1,2}x_2\cdots+a_{1,n}x_n=b_n\\ \cdots\\ （懒得写了） \end{cases}

2024/10/9 18:50