第 3 章 一些简单的数值程序
SOME SIMPLE NUMERICAL PROGRAMS
曲政 / 2018-04-10
3.1 Exhaustive Enumeration
用 while
的时候必须想好什么?
decrement function,什么时候停下来。
decrementing function 有哪四个属性?
从问题中提取一组变量,把它映射到一个变量; 这个变量的初始值非负; 每次运算这个变量都会变小; 小于等于零,就停止循环。
可以使用猜试法的问题,有什么特征?
猜试系:猜一个结果,试一下对不对,不对就再猜。
前提
- 试起来很容易。
- 错了没惩罚。
- 以可以接受的成本,有望得到答案。
猜试法中有一种什么有效的 “笨” 办法?
穷举法 —— 把答案空间中的所有可能都试一下,要么找到答案,要么证明没有。
为什么有效呢?
- 方法简单粗暴,相对于手工推演等算法,实现更容易。
- 节省了想算法的时间。
- 计算机的速度很快。
3.2 For Loops
range (start, stop, step)
的三个参数怎么理解,输出什么结果?
start 是砖,肯定能踩准;stop 是墙,以 step 来走,永远不会触碰。
在 python3 里,range (100000)
会占用很多空间吗?
不会。
be generated on an “as needed” basis.
这个功能在 Python2 中需要使用 xrange ()
。
用计算机解平方根,与手工解法一样吗?
手工一步步试商;计算机小步走,乘方后检验是否足够接近。
计算机的解题方法经常与手工不一样。
什么样就算是一个好答案?
按照问题定义的程度,足够接近,就是好答案。
更接近,或者完全吻合,并不会更好 * no better than*。
3.3 Approximate Solutions and Bisection Search
二分查找与齐步走查找本质区别在哪里?
步长不同。
- 齐步走每次迈一小步,保证不漏过真正的正确值。
- 二分法每次排除一半的空间,越来越接近正确值。
这就带来几个不同的表现。
- 齐步走可能漏过;二分法不会漏过。
- 齐步走的计算量可以估计,二分法变动比较大。
二分法有个前提:可能空间和比较空间都是有序的。
二分查找法仅仅限于解平方根吗?它属于哪个系列?
不限于解平方根,也可以解立方根,只要结果空间的大小比较,可以用来指导选择可能空间的哪一半,就可以使用。也就是说,“大了,就往小里找”,或者相反。
它属于猜试法。
3.4 A Few Words About Using Floats
“重构的我不是我” 的代码结果
x = 0.0
for i in range (10):
x = x + 0.1
if x == 1.0:
print (x, '= 1.0')
else:
print (x, 'is not 1.0')
print (x)
在 Python2.7 中的运行结果
(0.9999999999999999, 'is not 1.0')
1.0
在 Python3.6 中的运行结果
0.9999999999999999 is not 1.0
0.9999999999999999
因为
- Python2.7 中,
print
是 statement,而不是 function; - Python2.7 中,
print
会自动圆整。 0.1
这样的数在计算机中存储时,一定有截断。
什么是浮点数?计算机里的浮点数什么样?
We would represent a number with a pair of integers
- the significant digits
- an exponent
十进制浮点数
1.949 = (1949, -3) = 1949*10**(-3)
二进制浮点数
0.625 = 5/8 =
(101, -11) =
5*2**(-3)
计算机中的0.1
0.1 = 1/10
(0011, -101) = 3/32 = 0.09375
(11001, -1000) = 25/256 = 0.0976525
不存在这样的sig
和exp
,使得sig*2**(-exp) == 0.1
。
在 Python 系统里,这个 significant digits 是 53 位。
舍入误差对程序有影响吗?
注意避免直接比较两个实数是否 ==
,而用 “差值足够小” 来表达。
x == y
v.s. abs (x - y) < 0.0001
在某些设计不良的程序里,也会发生误差向一个方向积累的情况。
3.5 Newton-Raphson
最常用的近似算法叫什么?
通常归功与 Issac Newton,但是 Raphson 几乎同时也发表了这个算法。
也叫 “切线法”,基本思想是以直代曲,每一步近似为线性方程来求解。
任意函数,做 Taylor 一阶展开,解出 x 作为新的近似根。
在多项式函数里,有哪些术语?
注意:N-R 法不只用来解一元多项式方程,还可以解多元方程、非线性方程。它只有局部收敛性,没有全局收敛性。
- polinomial of one varialbe
- term
- coefficient
- nonnegative integer exponent
- degree of term
- degree of polynomial
- value of polynomial
- root of the polynomial
同样的精度,Bisecton Search 与 Newton-Raphson 方法各自的收敛速度怎么样?
快三倍?
y = 54.0
epsilon = 0.01
numGuesses = 0
low = 0.0
high = y
ans = (high + low)/2.0
while abs (ans**2 - y) >= epsilon:
print ('low = ' + str (low) + ' high = ' + str (high) + ' ans = ' + str (ans))
numGuesses += 1
if ans**2 < y:
low = ans
else:
high = ans
ans = (high + low)/2.0
print ('Bisection search numGuesses = ' + str (numGuesses))
print (str (ans) + ' is close to square root of ' + str (y))
guess = y/2.0
numGuesses = 0
while abs (guess*guess - y) >= epsilon:
numGuesses += 1
guess = guess - (((guess**2) - y)/(2*guess))
print ('Newton-Raphson numGuesses = ' + str (numGuesses))
print ('Square root of ' + str (y) + ' is about ' + str (guess))
输出结果:
Bisection search numGuesses = 14
7.34820556641 is close to square root of 54.0
Newton-Raphson numGuesses = 5
Square root of 54.0 is about 7.34846948355