TCAX 字幕特效制作工具官方论坛 | ASS | TCAS | Python | Aegisub | Lua

 找回密码
 新人加入
查看: 4559|回复: 5

【saiyaku】脫線⑨的完美算法教室 [复制链接]

Administrator

Shanzhai Pro.

Rank: 7Rank: 7Rank: 7

发表于 2012-10-27 19:07:11 |显示全部楼层
開個坑 寫點讀書筆記 預計每週末更新一點

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

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

查看全部评分

Administrator

Shanzhai Pro.

Rank: 7Rank: 7Rank: 7

发表于 2012-10-27 19:29:54 |显示全部楼层
最近打算看下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)

Administrator

Shanzhai Pro.

Rank: 7Rank: 7Rank: 7

发表于 2012-10-27 20:32:17 |显示全部楼层
積分

主要提下曲綫長度的積分

雖然有公式
2.jpg


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

簡單解釋一下
2.jpg


如上圖 曲綫可以近似為連續的直線線段組成
這近似的直線線段長度 根據三角形勾股定理
可算出等於√((Δ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
2

查看全部评分

Administrator

Shanzhai Pro.

Rank: 7Rank: 7Rank: 7

发表于 2012-11-4 21:41:43 |显示全部楼层
數值解析
數值解析真挺難 我也好多沒弄明白
主要就講下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
嗯 大概是這樣 話說中文一樣嗎 有點搞不清楚

Administrator

Shanzhai Pro.

Rank: 7Rank: 7Rank: 7

发表于 2012-11-15 00:21:17 |显示全部楼层
嗯 上周論壇開了個會沒更新
不再拖進度了 抽個時間補上

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.     h = float(b - a) / n
  4.     S = f(a)

  5.     for i in range(1, n, 2):
  6.         x = a + h * i
  7.         S += 4 * f(x)

  8.     for i in range(2, n-1, 2):
  9.         x = a + h * i
  10.         S += 2 * f(x)

  11.     S += f(b)
  12.     F = h * S / 3

  13.     return F
复制代码

Administrator

Shanzhai Pro.

Rank: 7Rank: 7Rank: 7

发表于 2012-11-16 12:21:28 |显示全部楼层
http://www.donews.com/it/201211/1692777.html

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

查看全部评分

您需要登录后才可以回帖 登录 | 新人加入

GitHub|TCAX 主页

GMT+8, 2024-3-28 21:25

Powered by Discuz! X2

© 2001-2011 Comsenz Inc.

回顶部
RealH