使用Playground学习数值算法.docxVIP

使用Playground学习数值算法中学时，没有什么比数学图纸更恐怖的了。许多问题没有现成解析方案，还有一些问题虽然可以解决，但需要大量的计算工作。这种情况下，你需要算法来辅助。希望你没被算法整吐。万一你真的吐了，也要看到好的一面：又可以再吃顿午餐了:]在这个教程中，你将学习到算法的概念，以及如何使用它们来解决难以分析的问题。通过playground，很容易使解决方案可视化，易于查看。即使你不是个数学爱好者，对物理或计算机科学也不大感兴趣，你仍会在这个教程中找到一些有意思的东西。你只需要有一些微积分和基础物理学的知识。你将学到如何使用数值算法解决两个困难问题。但是为了讲的更清楚点，这两个问题也可通过解析法解决。算法在解析法无法工作时更为理想，即便如此，通过比较两种方法，也能更加容易的理解它们的本质。数值算法是什么？简单说来，数值算法是一类解决数学问题的方法，它们不依赖于闭式解析解。问题来了，什么是闭式解析解？若有一个公式，我们可以使用已知数，通过有限的操作步骤，可以获得一个准确的结果，即称之为闭式解析解。再简单点来理解一下：如果你可以使用代数的方式，找到一个表达式来解决一个未知量问题，代入某些已知数即可得到结果，就说明你已经得到了一个闭式解析方法。何时使用数值算法？许多问题没有现成解析方案，还有一些问题虽然可以解决，但需要大量的计算工作。这种情况下，你需要算法来辅助。例如，假定你需要编写一个物理引擎，用来计算许多物体在有限时间内的行为。这时你就可以使用数值算法来更快地得到结果。这样做也有副作用，更快的计算速度意味着结果不会十分精确。然而，大多数情况下，这样的结果已经够用了。天气预报就得益于数值计算。天气变化的速度、影响因素的数量都是十分惊人的。这是一个非常复杂的系统，只有数值模拟才能完成预知未来的任务。可能正是因为缺乏这些算法，你的iPhone总是告诉你要下雨了，而外面还是艳阳高照。开始作为热身活动，我们来玩个游戏，接下来，你将计算出一个给定数字的平方根。这两个方法都将使用二分法（bisection method）。神奇的是，你可能已经知道了这个方法，但是不知道它的名字。回想一下，在儿童时代，我们可能玩过这样的游戏：选中100以内的一个数字，另外一个人来猜。你只会提示他猜的数字大了或者小了。游戏开始。小明告诉小强开始猜，小强说我猜1，小明说小了，小强又猜2，小明说小了。小强接下来再猜3,4...最后选中了5，终于对了。5步就猜中了，不错。但是如果小明选的是78，猜中就需要花点时间。这个游戏如果使用二分法（bisection method）来玩的话，猜中的速度会快很多。二分法我们知道数字介于1和100之间，因此除了一个一个的猜，或者随便瞎猜外。我们把数字分为两个区间：a = [1,50], b = [51, 100]。接下来我们判断数字是介于哪一个区间，这很简单，只用问数字是不是50。如果数字小于50，那么区间b就不用考虑了。接下来我们继续把a区间分成两半，再重复这个步骤。例如：数字是60.区间为：a = [1,50], b = [51, 100]。第一步，小强说50（也即是a区间的上限），小明说小了。这时小强就知道了数字肯定在b区间上。第二步，分解b区间为：?c=[51,75]，d=[76,100]。还是选择c区间的上限75，小强告诉他大了。这就意味着数字肯定在c区间上。继续分解。。。使用这个方法，7次尝试即可得到正确答案，一个一个试则需要60次。1. 50 - 小了2. 75 - 大了3. 62 - 大了4. 56 - 小了5. 59 - 小了6. 61 - 大了7. 60 - 对了！计算x的平方根，过程也类似。数字x的平方根介于0和x之间。也可以记做：(0,x]。如果数字x大于或等于1，可以记做：[1, x]。分解区间，得到a=(0, x/2]，b=(x/2, x]。如果数字x是9，区间是[1, 9]，分解后的区间为a=[1, 5]，b=(5, 9]，中间值m为(1+9)/2 = 5。下一步，检查m * m - x，是否大于期望的精度。在这里，我们检查m * m 大于或小于等于x。如果大于，我们使用(0, x/2]区间继续检查，否则，使用(x/2, x]区间。看一下实际步骤，初始化m=5, 期望准确值为0.1:1. 计算m * m - x: 5 * 5 - 9 = 112. 检查结果是否小于等于期望值：25 - 11 = 0.1?3. 显然不满足，继续下一个区间：m * m是否大于9？是。接下来使用区间[1, 5]，测试值为(1+5)/2=3。4. 计算m * m - x：３* 3 - 9 = 05. 查查是否满足期望值：9 - 9 = 0.1?6. 搞定。备注：你可能想知道括号是什么意思？区间有固定的格式（下限和上限）。