My Blogs
Posts tagged with "Python"
牛顿法从放弃到入门
Published 2017年09月17日 23:00 by james
问题
科学或工程问题的求解和模拟最终往往都要解决求根或优化问题，前一种情形要求出方程或方程组的解；后一种情形则要找出使函数取极大或极小值的点，即使是对实验数据进行拟合或数值求解微分方程，也总是将问题简化成上述两类问题。
第一类问题本质是求出$f(x) = 0$的解，第二类问题则可以转化为求$g(x) = f^{'}(x) = 0$的解，其实本质我们都可以转化为求解方程根的问题。
对分法
在解方程的问题上，我们最容易会想到就是通过对分法迭代逐步逼近方程的根，最终达到求解方程的根的目的。他的基本思想如下：
如果$f$在所考虑的区间上连续，且$[x_0, x_1]$是有根区间，即$f(x_0) \cdot f(x_1) < 0$，则取
$$ x_2 = \frac{x_0 + x_1}{2} $$
并计算$f(x_2)$，如果$f(x_2) = 0$则结束，否则或者$f(x_2)$与$f(x_0)$符号相反，此时$[x_0, x_2]$是新的有根区间，长度为原来的一半，或者$f(x_2)$与$f(x_1)$符号相反，此时$[x_2, x_1]$是新的有根区间，长度也为原来的一半，不管哪种情形，都通过计算一个新的函数值（$f(x_2)$的计算）将零点$x^*$的不确定性降低了50%，接下来在新的区间上重复这一过程，直到有根区间的长度充分小。
算法描述如下： …
不动点迭代及其收敛性
Published 2017年09月16日 23:00 by james
什么是不动点迭代法
函数$f$的不动点是一个值$x$使得$f(x) = x$。例如，0和1是函数$f(x) = x^2$的不动点，因为$0^2 = 0$而$1^2 = 1$，即曲线$y = f(x)$与直线$y = x$存在交点$P(x^{\ast}, x^{\ast})$。
对于某些函数，通过某些初始猜测出发，反复地应用$f$，
$$ f(x), f(f(x)), f(f(f(x))),\cdots $$
直到值的变化不大时，就可以找到它的一个不动点。
算法描述如下：
def solve(f, guess, …泰勒级数从放弃到入门
Published 2017年09月16日 21:00 by james
知识准备
极限
设函数$f(x)$在点$x_0$的某一去心邻域内有定义，如果存在常数$a$，对于任意给定的正数$\epsilon$，总存在正数$\delta$，使得当$x$满足不等式$0 < |x - x_0| < \delta$时，对应的函数值$f(x)$都满足不等式$|f(x) - a| < \epsilon$，那么常数$a$就叫做函数$f(x)$当$x \to x_0$时的极限，记作：
$$ \lim_{x \to x_0} f(x) = a $$
导数
设函数$y = f(x)$在点$x_)$的某个邻域内有定义，当自变量$x$在$x_0$处取得增量$\Delta x$（点$x_0 + \Delta …
朴素贝叶斯从放弃到入门
Published 2017年09月10日 23:00 by james
理论基础
联合概率
联合概率表示两个事件共同发生的概率。A与B的联合概率表示为$P(AB)$，$P(A,B)$或者$P(A \bigcap B)$。
联合概率可以推广到任意又穷多个事件出现的情况，设（$A_1,A_2,\cdots,A_n$）为任意n个事件（$n\ge2$），事件$A_1,A_2,\cdots,A_n$共同发生的概率记为$P(A_1A_2 \dots A_n)$，$P(A_1,A_2,\dots,A_n)$或者$P(A_1 \bigcap A_2 \bigcap \dots \bigcap A_n)$
条件概率
设A，B 是两个事件，且$P(A) > 0$，则称$P(B|A) = \frac{P(AB)}{P(A)}$为在事件A发生的条件下，事件B发生的条件概率。一般地，$P(B|A) \not= P(B)$ ，且它满足以下三条件：（1）非负性；（2）规范性；（3）可列可加性。
设E为随机试验，Ω为样本空间，A，B为任意两个事件，设$P(A)>0$，称$P(B|A) = \frac{P(AB)}{P(A)}$为在事件A发生的条件下事件B的条件概率。
上述乘法公式可推广到任意有穷多个事件时的情况。 设（$A_1,A_2,\cdots,A_n$）为任意n个事件（$n\ge2$）且$P(A_1,A_2,\cdots,A_n)>0$，则$P(A_1A_2 \cdots …
回溯算法Python实现
Published 2010年01月01日 19:52 by james
什么是回溯法
回溯法（探索与回溯法）是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。
包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去，如果该结点不包含问题的解，则逐层向其祖先结点回溯。（其实回溯法就是对隐式图的深度优先搜索算法）。 若用回溯法求问题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束。 而若使用回溯法求任一个解时，只要搜索到问题的一个解就可以结束。
算法实现
算法准备
准备一个默认的打印函数，把数组a中的数组转换成字母打印出来。
def display(a):
l = ['A', 'B', 'C', 'D', 'E', 'F', 'G', …