MC积分

Monte Carlo方法由冯·诺伊曼于二战时提出,1777年法国人布丰用此思路估计pi值被认为是Monte Carlo的起源,这个方法简单又快速,通过产生随机数,将数值计算问题变成随机变量的某些特征值(比如期望值)。

积分运算,和估计pi值一样,用hit and miss法估计。

hit_miss <- function(fun, lower, upper, n=500) {
    # Monte Carlo integration using the hit and miss method
    x <- runif(n, lower, upper)
    f.value <- sapply(seq(lower, upper, 0.001), fun)
    f.min <- min(f.value)
    f.max <- max(f.value)
    y <- runif(n, f.min, f.max)
    hits <- sum(y <= fun(x))
    area <- (upper-lower) * f.min + hits/n * (upper-lower) * (f.max-f.min)
    return(area)
}

hit and miss方法收敛太慢,效率并不高,通常所说的MC积分是指下面这个方法。

Continue reading

圆和外接正方形的面积比,是$ \frac{\pi r^2}{(2r)^2} = \frac{\pi}{4}$.

通过这一比值,可以使用蒙特-卡罗方法来估计Pi,这是Monte Carlo方法的最经典的一个例子。

getPI <- function(N) {
    x <- runif(N)
    y <- runif(N)
    hits <- sum(sqrt(x^2+y^2) < 1)
    pi <- 4*hits/N
    return(pi)
}

Continue reading

写给某个小朋友看,希望我的一点看法,能有用。欢迎讨论。。

为什么会有编程语言?

计算机史前有过不同的理论,但最后活下来的,只有图灵机一个模型。现在的计算机,都是基于此发展的,跟二战前那个三层楼高的计算机,没啥区别,那个机器一堆开关,人工操作。CPU做的计算也是开关的逻辑计算。所以计算机的语言是01二进制,一开一关,告诉计算机要不要发出电子脉冲。写一个程序全是01数字组成的,对于人来说是mission impossible!所以必须要有编程语言。编程语言就是为了抽象计算机机械原理的一面。

LOAD A ADD B STORE C

实现两个数的加和,这是人类可读的语言,而不是一串01所组成的不可读的机器语言。

抽象是最关键的。所有的编程语言都是为了实现抽象。越是高级的语言,抽象度越高,抽象度越高越好!

Continue reading

翻看了以前写的使用Newton-Raphson Method求一个数的开方,想到其实也可以用中值定理来实现。 中值定理:f(x)是一个连续性的函数,在[u,v]区间内,当c的值位于f(u)和f(v)之间时,至少存在一个点,满足f(x) = c 当f(u)和f(v)一正一负时,那么在[u,v]之间至少有一个根的存在,这个定理本来就是拿来证明根的存在的,但是其实也可以用来求解根。

Continue reading

Newton-Raphson Method

曲线f(x)有根c,取曲线上一点$(x_1,f(x_1))$, 过此点的切线交x轴$x_2$,过曲线上$(x_2,f(x_2))$的切线交x轴$x_3$,如此反复得到一个序列 $x_1,x_2,\cdot \cdot \cdot,x_n$ 逼近c值.

过$(x_n,f(x_n))$的切线方程为 $y-f(x_n) = f’(x_n)\,(x-xn)$,假设此方程与x轴的交点为$x{n+1}$, 即有: $0 - f(x_n) = f’(x_n)(x_n+1 - xn)$, 即$x{n+1} = x_n - \frac{f(x_n)}{f’(x_n)}$ <Eq. 1>.

下面利用此法来求一个数的开方。 $f(x) = x^2 - a$ 有根$\sqrt{a}$, 由$f’(x_n) = 2xn$, 代入式<Eq. 1>可得$x{n+1} = (x_n + a/x_n)/2$; 当i -> INF 时, $x_i$ -> $\sqrt{a}$;

C implementation

Continue reading

Author's picture

Guangchuang Yu

a senior-in-age-but-not-senior-in-knowledge bioinformatician

Postdoc researcher

Hong Kong