cosmos 仓库 Tridiagonal Matrix 三对角矩阵算法：基于 Java 的追赶法（Thomas Algorithm）实现详解

教程示例工程【免费下载链接】cosmosWorlds largest Contributor driven code dataset | Used in Quark Search Engine, OpenGenus IQ, OpenGenus Visual Project项目地址https://gitcode.com/gh_mirrors/co/cosmos点击查看免费下载三对角矩阵Tridiagonal Matrix是数值线性代数中一类结构高度稀疏的特殊矩阵其非零元素仅集中于主对角线及相邻的两条次对角线上在差分方程求解、三次样条插值、热传导方程离散化等工程场景中频繁出现。本篇文章基于 cosmos 开源算法仓库中的 tridiagonal_matrix/README.md 及其 tridiagonal_matrix.java 源码系统讲解三对角矩阵的定义、追赶法Thomas Algorithm的两阶段求解原理并逐行剖析仓库 Java 实现中的系数计算与回代逻辑。读完本文你将掌握三对角线性方程组的算法推导过程并能够理解、运行和扩展仓库中的参考实现。三对角矩阵定义与工程意义数学定义三对角矩阵Tridiagonal matrix是一种特殊的带状矩阵band matrix设矩阵 (A) 的规模为 (n \times n)则其满足当 (|i - j| 1) 时元素 (a_{ij} 0)。即只有主对角线(j i)、上对角线(j i 1)与下对角线(j i - 1)上可能存在非零元素其余位置全部为零| b1 c1 0 0 0 | | a2 b2 c2 0 0 | | 0 a3 b3 c3 0 | | 0 0 a4 b4 c4 | | 0 0 0 a5 b5 |其中 (b_i) 为主对角线元素(a_i) 为下对角线元素(c_i) 为上对角线元素。完整的定义与性质可参考 Tridiagonal matrix README。典型应用场景三对角结构之所以重要是因为大量实际问题经离散化后都自然导出三对角线性方程组常微分/偏微分方程数值解如热传导方程、波动方程在均匀网格上的隐式差分格式Crank-Nicolson 等每个时间步都会产生一个三对角方程组三次样条插值Cubic Spline求样条系数时形成的方程组天然是三对角的矩阵特征值问题对称三对角矩阵是许多特征值算法的中间形态如 QR 算法的化简阶段。对这类结构直接使用高斯消元会浪费大量算力在零元素上而**追赶法Thomas Algorithm**能在 (O(n)) 时间内完成求解远优于一般直接法的 (O(n^3))。这正是 tridiagonal_matrix.java 所实现的算法。追赶法Thomas Algorithm原理与两阶段流程仓库实现将求解过程明确分为两个阶段并在控制台分别输出First step:与Second step:两个阶段的结果对应算法中的前向消元追与回代求解赶。第一阶段前向消元追对增广矩阵从第一行开始逐行消去下对角线元素把原方程组化为仅含主对角线与上对角线的上双对角bidiagonal形式。仓库代码为这一阶段维护两个关键系数alpha代码中写作alpha消元过程中第 (i) 行上对角线位置的变换系数其递推公式为 [ \alpha_i -\frac{c_i}{y_i}, \quad y_i b_i a_i \cdot \alpha_{i-1} ] 其中 (y_i) 是消元后第 (i) 行的新主对角线元素代码中的y_ibetta代码中写作betta即 (\beta)消元后增广列右端项的变换系数递推公式为 [ \beta_i \frac{d_i - a_i \cdot \beta_{i-1}}{y_i} ] 其中 (d_i) 为原方程组的右端项代码中取matrix[i][cols - 1]。第二阶段回代求解赶经过前向消元后方程组已被化为上双对角形式可从最后一行开始自下而上逐行回代直接求出未知量 (x_i)。仓库实现中回代的核心递推为 [ x_i \alpha_i \cdot x_{i1} \beta_i ] 即每个解都由下一行的解乘以该行 alpha 系数再加上该行 betta 系数得到这正是追赶法回代阶段的直观体现。源码逐段剖析增广矩阵与系数初始化仓库中的 tridiagonal_matrix.java 将三对角方程组的系数矩阵与右端项以增广矩阵的形式一次性传入算法。以下逐段分析其关键实现。输入形式与输出结构public static void main(String[] args) { double[][] myMatrix {{9.0, 5.0, 0.0, 0.0, 0.0, 4.0}, {3.0, 7.0, 1.0, 0.0, 0.0, 4.0}, {0.0, 5.0, 11.0, 2.0, 0.0, 4.0}, {0.0, 0.0, 5.0, 6.0, 4.0, 4.0}, {0.0, 0.0, 0.0, 4.0, 5.0, 2.0}}; int rows myMatrix.length; int cols myMatrix[2].length; ... TridiagonalMatrix(myMatrix, rows, cols); }以main中的测试数据为例这是一个 (5 \times 6) 的增广矩阵前 5 列为三对角系数矩阵第 6 列为右端项9.0 5.0 0.0 0.0 0.0 | 4.0 3.0 7.0 1.0 0.0 0.0 | 4.0 0.0 5.0 11.0 2.0 0.0 | 4.0 0.0 0.0 5.0 6.0 4.0 | 4.0 0.0 0.0 0.0 4.0 5.0 | 2.0可以验证第 1 行只有主对角线与上对角线非零第 24 行满足 (|i-j| \le 1) 的位置非零其余为零末行同样保持三对角结构完全符合三对角矩阵定义。算法主体TridiagonalMatrix(matrix, rows, cols)首先声明输出矩阵double[][] output new double[rows][cols 1];输出矩阵比输入多一列cols 1用于保存前向消元阶段计算出的 alpha、betta 与中间系数供第二阶段回代使用这是实现两阶段串联的关键数据结构。首行系数初始化double y1 matrix[0][0]; double alpha -matrix[0][1] / y1; alpha new BigDecimal(alpha).setScale(2, RoundingMode.HALF_DOWN).doubleValue(); double betta matrix[0][cols - 1] / y1; betta new BigDecimal(betta).setScale(2, RoundingMode.HALF_DOWN).doubleValue();y1 matrix[0][0]第一行的主对角线元素作为首个基准系数alpha -matrix[0][1] / y1第一行的 alpha 系数即负的上对角线元素除以主对角线元素对应公式 (\alpha_1 -c_1/b_1)betta matrix[0][cols - 1] / y1第一行的 betta 系数即右端项除以主对角线元素对应公式 (\beta_1 d_1/b_1)代码使用BigDecimal.setScale(2, RoundingMode.HALF_DOWN)将每一步中间结果统一保留 2 位小数四舍五入、半数向下取整这是该实现的一个特点以牺牲部分精度为代价换取中间过程数值的规整与输出的可读性。前向消元主循环int countA 0; int countC 2; output[0][0] y1; output[1][0] alpha; output[0][1] betta; output[0][cols] matrix[0][cols - 1]; for (int i 1; i cols - 1; i) { double b_i matrix[i][i]; double alhpa_i matrix[i][countA]; ... double y_i b_i alhpa_i * alpha; ... if (countC cols - 1) { alphaNext -matrix[i][countC] / y_i; ... output[countC][i] alphaNext; } else { alphaNext 1; } double betta_i (matrix[i][cols - 1] - alhpa_i * betta) / y_i; ... output[i][i] y_i; output[i][countC] betta_i; output[i][cols] matrix[i][cols - 1]; countA; countC; alpha alphaNext; betta betta_i; }循环从第 2 行i 1开始对每一行执行如下步骤取出本行主对角线元素b_i matrix[i][i]与下对角线元素alhpa_i matrix[i][countA]。注意countA从 0 递增用于定位第 (i) 行下对角线即左下方的非零元素计算新主对角线系数y_i b_i alhpa_i * alpha这正是前向消元公式 (y_i b_i a_i\alpha_{i-1}) 的直接翻译若本行还存在上对角线元素countC cols - 1计算下一个 alphaalphaNext -matrix[i][countC] / y_i并存入输出矩阵output[countC][i]否则将alphaNext置为 1末行终止条件计算 betta 系数betta_i (matrix[i][cols - 1] - alhpa_i * betta) / y_i即公式 (\beta_i (d_i - a_i\beta_{i-1})/y_i)将y_i、betta_i与右端项写入输出矩阵对应位置随后countA、countC递增并把alpha、betta更新为本次计算值供下一行递推使用。可以看出仓库实现通过output矩阵把每行计算出的 alpha 与 betta 系数完整保存下来为第二阶段回代提供了全部所需数据。回代求解与结果输出System.out.println(Second step:); ArrayListDouble arrayList new ArrayList(); double x output[rows - 1][cols - 1]; int countAlpha rows - 1; int countBetta rows - 1; arrayList.add(x); for (int j cols - 2; j 0; j--) { double alpha_i output[countAlpha][j - 1]; double x_i alpha_i * x output[countBetta - 1][j]; x_i new BigDecimal(x_i).setScale(2, RoundingMode.HALF_DOWN).doubleValue(); arrayList.add(x_i); x x_i; countAlpha--; countBetta--; } System.out.println(arrayList);回代阶段从最后一行开始取最后一个未知量的初始值x output[rows - 1][cols - 1]将其加入结果列表从倒数第二行起自下而上遍历j cols - 2; j 0; j--每次取出前向消元阶段存下的 alpha 系数output[countAlpha][j - 1]与 betta 系数output[countBetta - 1][j]按递推公式x_i alpha_i * x betta计算当前行的解加入结果列表并更新x作为下一轮迭代的已知解两个计数器同步递减完成全部回代后结果以ArrayListDouble形式打印。最终方程组 ((9,5,3,7,1,5,11,2,5,6,4,4,5)) 构成的 5 阶三对角系统在该实现下输出的解向量即回代所得结果。仓库通过First step:前向消元中间矩阵与Second step:解向量两段控制台输出完整呈现了追赶法的两个阶段便于学习与验证。运行与验证方式编译与运行本实现仅依赖 JDK 标准库java.math.BigDecimal、java.util.ArrayList无任何第三方依赖可直接编译运行javac tridiagonal_matrix.java java TridiagonalMatrix程序首先打印Original matrix:与原始增广矩阵随后依次输出前向消元阶段的中间矩阵First step:与回代求得的解向量Second step:。自定义输入如需求解其他三对角方程组只需修改main方法中的myMatrix二维数组每行前n个元素为系数矩阵的三对角非零带其中主对角线元素不可为零代码中作为除法分母使用每行最后一个元素为该行方程组的右端项增广矩阵列数cols由myMatrix[2].length动态获取行数rows由myMatrix.length获取算法对规模无硬编码限制。使用限制说明从源码结构看该实现存在以下几点需要在使用时注意主对角线元素不能为零算法全程以主对角线元素y1、y_i作分母若出现零主元前向消元将产生除零错误此时需先行主元交换该实现未包含选主元逻辑中间结果强制保留 2 位小数BigDecimal.setScale(2, RoundingMode.HALF_DOWN)会对每一步中间计算截断舍入引入累积舍入误差适合教学演示与对精度要求不高的场景不适用于高精度数值计算仅针对三对角结构matrix[i][countA]、matrix[i][countC]等索引方式依赖三对角非零带布局输入若非三对角矩阵算法结果不再成立。在 cosmos 仓库中的定位三对角矩阵主题位于仓库的 mathematical_algorithms/src/tridiagonal_matrix/ 目录下与src中的 2sum、gcd_and_lcm、sieve_of_eratosthenes、tower_of_hanoi 等上百个数学算法目录并列共同构成 cosmos 仓库涵盖各类算法与数据结构的目标。该目录由 OpenGenus 社区协作贡献见 README包含算法说明文档与 Java 参考实现两个文件tridiagonal_matrix/README.md算法主题说明tridiagonal_matrix/tridiagonal_matrix.java追赶法的 Java 完整实现含测试用例数据main中的 5 阶方程组。仓库整体的 mathematical_algorithms/src/README.md 汇总了数学算法目录的完整清单读者可据此定位本主题在算法体系中的位置并对照 gaussian_elimination 等高斯消元类实现理解稀疏结构对消元效率的优化意义。小结本文基于 cosmos 仓库的 tridiagonal_matrix README 与 tridiagonal_matrix.java完整梳理了三对角矩阵的定义、追赶法的数学原理以及仓库 Java 实现中前向消元 回代两阶段的代码细节。通过源码级剖析可以看到该实现以增广矩阵为输入用输出矩阵缓存每行 alpha/betta 系数将 Thomas 算法的时间复杂度控制在 (O(n))并以BigDecimal规整中间结果、以两阶段控制台输出辅助教学理解。对于需要精确计算或应对零主元等边界情况的场景可在此基础上引入选主元与浮点精度控制进行扩展。赞分享教程示例工程【免费下载链接】cosmosWorlds largest Contributor driven code dataset | Used in Quark Search Engine, OpenGenus IQ, OpenGenus Visual Project项目地址https://gitcode.com/gh_mirrors/co/cosmos点击查看免费下载相关推荐LeetCode 59 Spiral Matrix II 螺旋矩阵 II三种解法与多语言实现全解析leetcode 题解仓库实战LeetCode 59 Spiral Matrix II 螺旋矩阵 II三种解法与多语言实现全解析leetcode 题解仓库实战 导读 本文围绕 Leet示例工程教程Grover 量子搜索算法解析与 Python 振幅放大实现——基于 cosmos 量子算法仓库的实战指南Grover 量子搜索算法解析与 Python 振幅放大实现——基于 cosmos 量子算法仓库的实战指南 导读本文以 cosmos 仓库中 Grover 算教程示例工程突破矩阵乘法性能瓶颈CUTLASS 32位三角矩阵乘法全解析突破矩阵乘法性能瓶颈CUTLASS 32位三角矩阵乘法全解析 在科学计算和深度学习中矩阵乘法是核心运算之一。而三角矩阵乘法TRMM作为一种特殊的矩阵运算算子库高性能计算上一篇【亲测免费】 探索高效语言模型评估工具Simple-Evals下一篇Spacedrive VDFS 插件 API 桥接设计一个 spacedrive_call() 打通 WASM 沙箱与 Wire 操作注册表创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考