Lecture 6: Bisection methods, Newton/Raphson, Introduction to lists.

本课内容简单明晰，前半部分介绍了牛顿法，举了牛顿法求平方根的例子，然后将其与二分法进行比较。后半部分简单介绍了一些列表的基本操作，主要包括增加和删减列表项。

上节课举的求平方根的例子里面，出现了一个bug而导致程序的崩溃。这也是上节课最后留下的思考题。这个bug是这样的：若所求数x在0-1之间，SquareRootBi(x)会出现错误。最根本的原因在于x的平方根已经超过了原定的上界x。

举个最简单的例子：SquareRootBi(0.25)，在原来的二分法程序中，上界是high = x = 0.25，但是我们知道0.25的平方根是0.5，而0.5大于0.25，那么原定上界是错误的。因此，修改这个程序的关键之处就在于修改上界high。这里只需要比较x和1的大小即可。当x>1时，平方根上界为x，当x<1时平方根上界则为1。那么在Python中一个简单的high = max(x, 1)就可以实现了。

这个例子就给了我们一些警示，即在使用二分法时需要注意以下两点：

• 边界非常重要，在解题时需要慎重考虑边界的选择。


• 在选择边界时往往需要分类讨论，这时比较max的用法和if-else的用法就尤为重要。

 （注意：二分法是非常经典和常用的方法，但仍然存在一些缺陷，如上面所提到的bug。那么在使用二分法之前，需要仔细考虑各种情况，划定边界值，以防止程序崩溃。）

本课后半部分简单介绍了牛顿法(Newton's method)。与二分法相比，牛顿法的优势有以下两点：

• 减少迭代次数


• 提高运算效率


• 运算庞大数据时，牛顿法的优势最为显著

最直观的比较就是在求平方根的运算中，牛顿法的收敛速度(speed of convergence)要比二分法快很多。换句话说，牛顿法做的迭代次数(iteraction times)要比二分法少很多。那么假设在相同时间内做的迭代次数是一样的，牛顿法就比二分法所化的运算时间要少很多。可以说，输入数据越大，运算效率差就越大。牛顿法是编程中的最优化算法之一。

（注意：这里使用的是牛顿切线法，具体定义可参考百度百科）

根据百度百科，牛顿切线法是由开方公式引出的：

        X(n+1) = Xn + (A / X^(k-1) - Xn)(1 / k)       (n,n+1表示下角标，k为指数)

这个公式看上去非常复杂，对于初学者而言只需要记住如下结构即可：

• A = f(guess)


• B = fd(guess)    # B为A的导数表达式


• diff = A - x    # x为输入值/精确值


• guess = guess - diff / B

根据这个结构我们就可以轻松构建出一个开平方函数了（注意：这个函数和本课例举的函数有细微差别），程序如下：

def f(guess):

    return guess ** 2

def fd(guess):

    return 2 * guess

def SquareRootNR(x, epsilon):

    guess = x / 2.0

    diff = f(guess) - x

    ctr = 1

    while abs(diff) > epsilon and ctr <= 100:

         guess = guess - diff / fd(guess)

         diff = f(guess) - x

         ctr += 1

    return guess

（注意：guess的值非常重要，因为某些guess的值会导致程序崩溃，即切线和x轴没有任何交点。所以在输入initial guess的值的时候需要注意避免这些值。）

后半部分简要介绍了列表(List)的基本用法，List是一个非常灵活和强大的工具，可以进行许多神奇的操作。这个会在以后讲到类(Class)和方法(Method)的时候提到。由于本人对于列表的应用进行了较多遍，这里就不重复记录列表的基本用法了。对于初学者来说，可以去参考一下Python基础教程（第二版）中List的应用，非常有帮助。

总结：本课重点为牛顿法，这个并不如二分法那样被人所知。不知道的可以看看这一节课。