【saiyaku】脫線⑨的完美算法教室

saiyaku

開個坑 寫點讀書筆記 預計每週末更新一點

標題加亮 請給我黑又粗 謝謝

估計會寫得很亂 請不要過分期待

saiyaku

最近打算看下sound programming
在此之前複習下微積分和數值解析

微分
比較簡單 基本公式 沒什麽好說的

介紹一個不太有人知道的公式
(fg)'=f'g+fg'
(f/g)'=(f'g-fg')/g^2
這學過微積分的都知道
其實還有個通用的展開公式
(fg)'=fg(f'/f+g'/g)
fg 原式 提出來
f'/f g'/g 括號裏面是每項都是這種形式 如果原式是倒數形式（除法）+負號
(f/g)'=f/g(f'/f-g'/g)
這個方法 還是能簡化不少複雜的微分的
(abc/de)'=abc/de(a'/a+b'/b+c'/c-d'/d-e'/e)

saiyaku

積分

主要提下曲綫長度的積分

雖然有公式


由於輸入比較麻煩 這裡積分用 大寫I來代替 如果定積分以I(a,b) 來寫

簡單解釋一下


如上圖 曲綫可以近似為連續的直線線段組成
這近似的直線線段長度 根據三角形勾股定理
可算出等於√((Δx)^2+(Δy)^2)
這時把Δx提出來 可以算出 Δx√(1+Δy^2/Δx^2)
Δy^2/Δx^2  的部份 (Δy/Δx)^2
Δy/Δx是斜率 換成 f’(x)
Δx√(1+f’(x)^2)
這是部份量的長度
f(x)Δx 這種形式的部份量 其總量等於I(a,b) f(x) dx
要說爲什麽的話 f(x)作為速度v的話 Δx就是單位時間Δt
這樣vΔt雖然是路程 但單位時間的路程 其實就是速度

利用加亮的那句話 很多東西的積分公式就能利用上面的方法推出來
例如我們最常用的曲綫與x軸所圍成的面積
往x軸做矩形的話 Δx是寬 高是y也就是f(x) 這樣面積的部份量就是f(x)*Δx
很自然地就能寫出 I(a,b) f(x) dx

saiyaku

數值解析
數值解析真挺難 我也好多沒弄明白
主要就講下newton法求根和simpson積分法

這周report太多 又得拖進度了 就先講下牛頓法
求方程根的方法有很多的 我學過的就有5，6種 牛頓法最常用



wiki上的圖
原理就如圖上一樣
隨便找個點做切線
找到切線與x軸的交點的橫座標x’ 所對應的曲綫上的點
然後再做過這點的曲綫的切線 如此循環 最後向0收束（趨近於0）
寫程序的時候 判斷個x<10^-6 之類的就可以了
雖說是隨便找個點開始 找的不好的話 也有可能導致結果發散（趨近於無窮）死循環
或者花費大量的時間 這點還是注意一下

這麼說估計也看不太明白 實際舉個例子
這裡就舉個求倒數的例子吧
不知道現在的cpu怎麼弄了 以前好像就用這個算的
除法可以看做乘以該數倒數的原理
這時候你需要一個算法 去求倒數
首先構造一個方程 f(x)=a-1/x=0
解方程你發現這方程解是 1/a 即通過求根 你就能得到a的倒數的值
那麼求導f'(x)=1/x^2
然後根據牛頓法原理寫出y=f'(x0)*(x-x0)+f(x0)
上面那個式子 你可以根據切線斜率和微分的關係(y-f(x0))/(x-x0)=f'(x0)推 也可以直接當成泰勒展開前兩項
嘛 總之得到式子 把 f'(x0)=1/x0^2代入
x=(2-ax0)*x0
循環這個式子
x1=(2-ax0)*x0
x2=(2-ax1)*x1
以下略

判斷xn-xn-1<10^-6的時候
就能得到倒數解xn

那麼就介紹到這裡 有興趣的人可以自己寫成程序試試
另外對於求不出 微分 或者求微分很困難的式子 可以用差分商代替 貌似被稱為割線法
差分商和微分的區別 嘛 差分商就是Δy/Δx 微分就是dx
嗯 大概是這樣 話說中文一樣嗎 有點搞不清楚

saiyaku

嗯 上周論壇開了個會沒更新
不再拖進度了 抽個時間補上

simpson積分法
用法上可能比牛頓法還容易理解

嘛 就是因為用法簡單 2次近似精度也比較好 所以廣泛被使用

通常積分簡單來說理解成算面積就可以了 最初提出這概念貌似就是用來算面積的

嘛 大家高中應該都學過的 分割然後近似成許多長方形 那麼長方形面積的和就是面積了
這是一種近似方法 1次近似精度略低

另外還有如下圖

這樣近似為梯形，同樣1次近似 不過要比上面那個要精確一點

那麼simpson積分的近似是將兩區間（兩長條）近似為2次曲綫
曲綫的地方利用拉格朗日插值法代入曲綫的多項式後得到公式
這地方不具體演示推導了 感覺很難有人理解

那麼來說算法 很簡單而且是萬能型
輸入：a（左端點）,b（右端點）,m（分割數自己定）,f0,…,f2m（各個分割點x對應的y值）
輸出：j（積分結果）
s0=f0+f2m   （兩端點的y值之和）
s1=f1+f3+...+f2m-1 （奇數項y值之和）
s2=f2+f4+...+f2m-2 （ 除去端點偶數項之和）
h=(b-a)/2m #分割條的寬度
j=h/3(s0+4s1+2s2)  #純粹公式 原理省略
結束

wiki上居然放了個python的例子 想套用可以直接用

1. def simpson(f, a, b, n):
   
2.     """f=function, a=initial value, b=end value, n=number of intervals of size h, n must be even"""
   
3. 
   
4.     h = float(b - a) / n
   
5.     S = f(a)
   
6. 
   
7.     for i in range(1, n, 2):
   
8.         x = a + h * i
   
9.         S += 4 * f(x)
   
10. 
    
11.     for i in range(2, n-1, 2):
    
12.         x = a + h * i
    
13.         S += 2 * f(x)
    
14. 
    
15.     S += f(b)
    
16.     F = h * S / 3
    
17. 
    
18.     return F

复制代码

saiyaku

http://www.donews.com/it/201211/1692777.html

微軟的同聲傳譯演示 這識別率要逆天了啊
再過幾年翻譯就要失業了