高斯消元法

OI Monthly oiers from OIBH 2009年 2月 2日 2009年第1期 总第1期 版权所有，不得随意转载 - 2 - 高斯消元法简介 by 吴豪 摘要 在信息学竞赛中，很多问题都可以转化成线性方程组或者与之相关的问题。因此，我们需要了解线性方程组的各种解 法。在本文中，我将主要对线性方程组最常见的解法——高斯消元法进行初步的介绍。希望能借此让大家对线性方程组 及其解法有进一步的了解。 高斯消元法  a11x1 + a12x2 + ...+ a1nxn = b1 a21x1 + a22x2 + ...+ a2nxn = b2 · · · · · · an1x1 + an2x2 + ...+ annxn = bn (1) 对于形如(1)的线性方程组，我们通常可以按照以下步骤求 出解集{x1, x2, ..., xn}: 1.建立增广矩阵 我们把方程组中的系数与常数直接取出，得到这样一 个矩阵  a11 a12 · · · a1n b1 a21 a22 · · · a2n b2 · · · · · · · · · · · · · · · an1 an2 · · · ann bn 。 2.消元 对于刚才构建的矩阵，我们反复实施初等变换，即将某 一行乘上一个数加到另一行上，得到一个这样的一个三角 矩阵  c11 c12 · · · c1n d1 0 c22 · · · c2n d2 · · · · · · · · · · · · · · · 0 · · · 0 cnn dn ,即得到了一个与原方程 组同解的方程组 c11x1 + c12x2 + ...+ c1nxn = d1 c22x2 + ...+ c2nxn = d2 · · · · · · cnnxn = dn (2) 3.回代 由方程组(2)的最后一个方程，我们可以很容易 得到xn = dncnn，将xn带入倒数第二个方程可以得 到xn−1,将xn和xn−1 带入倒数第三个方程可以得到xn−2， ⋯⋯，依次类推，我们即可求出解集{x1, x2, ..., xn}。 像上面这样通过初等变换构造同解方程组来解线性方 程组的 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 ，我们称之为高斯消元法，一般来说，高斯消元 法的时间复杂度是O(n3)。 选取主元 在消元过程进行到第k步时，即正要用第k行去消后面 的行时。我们需要把第k行除以akk然后乘上aik加到第i行 上(i>k)。显然如果akk特别小的话，不仅有可能损失精度， 还有可能造成溢出。为了避免这种情况，我们需要选取主 元: 在系数矩阵右下角选取n-k+1阶子矩阵中绝对值最大 的元素aij，交换第k行与第i行，交换第k列与第j列。注意到 列的交换会使得解的顺序混乱，因此我们需要记录列的交 换过程，以便最后还原。当然由于交换后akk的绝对值是最 大的，所以如果akk=0我们就可以直接终止计算了，因为这 时无法找到唯一的一组解。（选取主元的过程并不影响时间 复杂度，整个过程的时间复杂度仍然是O（n3)） 高斯约当消元法 高斯约当消元法是一种不需要回代的消元法，可以算 是高斯消元法的一种改进，它与高斯消元法唯一的不同是： 高斯约当消元法每次不仅要把主对角线以下的元素消为0 ,还要把主对角线以上的元素消为0。自然消完后系数矩阵只 有主对角线上有非0元素，所以就不需要回代了。 其他解法 除了高斯消元法与高斯约当消元法外，我们还可以使 用迭代法或者共轭梯度法来解线性方程组，限于篇幅这里 不作介绍，有兴趣的同学可阅读相关资料。 练习题 1. zoj2296 Spread Sheet 2. hdu2449 Gauss Elimination 3. NOIP2004 虫食算 参考资料 [1] 徐士良 数值分析与算法机械工业出版社 [2] 何江舟 用高斯消元法解线性方程组 - 2 - - 3 - 大牛的足迹：董华星 个人档案 姓名：董华星 头衔：NOI08浙江队队长 常见ID：ddjdhx，rpg Blog：校内网 爱好：爬山，唱歌 座右铭：相信自己 现居地：浙江省绍兴市越城区 学校：浙江省绍兴市第一中学 “用周梦宇的话说：‘OI是我的初恋。’而我想补充一 句：‘爱没有理由。’” 爱上OI 董华星从很小的时候就对计算机有着浓厚的兴趣，他 的老师也注意到了这一点，所以一直以来都给予了他很大 的支持。用他自己的话说就是：“简单的说呢，我喜欢计算 机，于是老师就让我尝试。” 董华星是个喜欢实践的孩子。当我们问到他最喜欢的 算法时，他很坦然地告诉我们：“其实我最喜欢‘模拟’，但 是它准确地讲并不是算法。因为我觉得它更是一种实践过 程。而它让我明白了‘千里之堤溃于蚁穴’、‘千里之行始于 足下’的道理。同时，还让我明白了‘实践出真理’。”他之 所以青睐于“模拟”，正是因为他对实践的热爱。在信息学 竞赛的学习过程中，他体会到了实践的快乐，受益良多。 “我有过失败，但是我也并不失败——失败也是一种成 功。” 正确对待成败 每个成功的人对于成败都有自己独到的见解，董华星 也不例外。在他看来，失败并不仅仅是失败，在其中能够发 现自己的不足再加以改进，这也便是一种成功。 董华星也曾经有过“考砸”的经历，他告诉我 们：“NOI07时，无论是Day1还是Day2，我都有得满分的 题，但也都有得0分的题。比赛气氛让我没有仔细看题、分 析题目，这归根到底是心态问题。” 金牌是另人羡慕的，为什么他能够拿到，而我们却不 能？我们向他提起这一点时，他笑了笑，说：“我认为，我的 金牌=一定能力+心态+状态+运气”。 “我带着梦想来到这个世界。我捧着希望接近这个梦 想。我揣着真情实践这个希望。” 广泛的爱好 董华星除了OI，还对文学有着一定的兴趣。他告诉我 们，他最近在看《追风筝的人》，书是朋友推荐的。他觉得这 是一本很好的书，给了他很多启示。 他也喜欢唱歌。他不好意思地告诉我们：“这是一个一 直被我压制着的爱好。我比较喜欢一些老歌，但由于长期被 我自己压制着，很多歌现在唱得已经没法和原来相比，应该 说唱得相当不好，而且歌词也基本没记住的。不过我也有 自己非常喜欢的歌，如满文军的《懂你》、周华健的《朋友》 等。” “在幸福中痛苦挣扎，在痛苦中快乐成长。” 对一些问题的辩证思考 我们向董华星询问他对理性、感性与OI的看法，他思 考了片刻，告诉我们：“我愿意理性，但充满感性。OI是理性 的，我学习OI是感性的。我学习OI，最终都受自己的想法支 配。只有要学、想学，才会学，并且才能学。当然啦，只是针 对我而言⋯⋯” 说到OI，大家自然会想到RP，那么董华星对RP有着怎 样的看法呢？我们向他提出了这个疑问。他告诉我们：“事 实上，如果把它只是作为运气理解，我并不相信。如果理解 成人品，我还是愿意相信‘好人有好报，坏人有坏报’。” e 本报记者 于野 (下期人物：刘聪) - 3 - - 4 - 我们的感言 by Mr Joke 冬去春来，转眼鼠年已经过去。在此新春佳节之际，我 谨代表OIBH管理团队恭祝各位牛年快乐！ 在过去的一年里，我们OIBH管理团队在坚持做好日常 论坛管理的同时，积极探索。尝试了建立同城区、交流区、 宠物中心、打造OOJ等一些列管理措施。在过去的一年里， 我们有失败也有成功。然而我们胜不骄败不馁，在成功中总 结经验，在失败里总结教训。在新的一年里，我们将立足于 现在，以求真务实的态度审视未来。将团队管理理念转变为 少而精。我们力求每年认真的做好一两件事实。 同时我们将舍弃无用而庞大的部分，打造精品论坛。然 而这并不意味着，我们会改变论坛定位。OIBH始终要秉承 信息学初学者之家的定位。家是最根本的定义。我们力求提 供人性化的管理，使每一位oier体会到家的感觉。其次是初 学者。我们论坛的主要群体应该是针对信息学初学者，是给 大家一个入门的平台，打造一个交流的平台。我们不能因为 论坛大牛的人数增多而放弃基础区的建设。基础区的建设， 永远是我们工作的重中之重。与此同时，我们立志为给大家 进一步学习提供一个良好的平台。如果您对我们的管理有 任何意见或建议，请与我们联系。 OI Monthly 创刊感言 by 吴豪 趁着新年之际，在Mr Joke学长的提议下，我们开始着 手OI Monthly第一期刊物的筹备。由于人手稀缺，以及一 些各方面的问题，第一期刊物的编写遇到了很大的阻碍。 不过想到能真正为OIer们做件实事、做件好事，这种兴 奋的心情就使人充满的了动力。 当然，由于毕竟我们作为业余的记者、编辑，概念和经 验几乎都是一片空白。我们一边学习相关知识，一边试着收 集材料，制作这一期刊物。 经过几天加班加点的奋战，基本搭建出了初刊的雏形。 虽然内容还很单薄，各方面也还有很大的问题，不过这期刊 物我们确实是在认真地做。选材、编写、校对以及审核，每 个步骤我们都有严格地进行。 欢迎各位有兴趣的同学踊跃给OI Monthly投稿或者报 名加入OI Monthly编辑团队。相信在我们的不懈努力以及 各位读者的支持下，OI Monthly一定能够办得更好！ OI Monly第一期主要负责人 e 总编辑 吴豪e 编辑 于野、Mr Jokee 校对 Mr Joke,rpg 致谢 在这里，感谢Mr Joke学长提出创办OI Monthly的倡议 感谢于野同学牺牲自己的休息时间进行采访工作 感谢董华星同学对我们采访工作的支持与配合 也感谢各位看到这里的热心读者 祝你们新的一年里学习进步，心想事成！ - 4 -