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的应用，非常有帮助。
总结：本课重点为牛顿法，这个并不如二分法那样被人所知。不知道的可以看看这一节课。
