有能算出反三角函數的準確值的演算法嗎?

遇到一位靠譜的民科,檢查他的想法後發現他確實得到了一個可以算出反三角函數的準確值的方法(前提是結果必須位於Qπ中,這個演算法才能在有限步內結束)。

現在想問問這是否已經重複了前人的結果?

各位不要惡意修改問題和添加標籤,題主是數學系學生,還是有一點判斷力的。這不是釣魚,省略兩遍。

具體步驟如下(原始想法來自百度貼吧「何懷能吧」,下面是整理過的步驟):


有個想法...如果 cos iggl(frac{p}{q}piiggl) 能被根式表達.

那麼其必定為某個多項式的根...

對表達式執行根約化.

例如: frac{1}{8} left(sqrt{5}+sqrt{6 left(5-sqrt{5}
ight)}+1
ight)=x

消去所有根式, 發現其滿足方程:

16 x^4-8 x^3-16 x^2+8 x+1=0

也就是說:

16 cos ^4left(frac{pi p}{q}
ight)-8 cos ^3left(frac{pi p}{q}
ight)-16 cos ^2left(frac{pi p}{q}
ight)+8 cos left(frac{pi p}{q}
ight)+1=0

那麼根據歐拉公式:

e^{-frac{i pi p}{q}}+e^{frac{i pi p}{q}}-e^{-frac{3 i pi p}{q}}-e^{frac{3 i pi p}{q}}+e^{-frac{4 i pi p}{q}}+e^{frac{4 i pi p}{q}}-1=0

於是比較係數可知:

frac{p}{q}=frac{2}{15}lor frac{4}{15}lor frac{8}{15}lor frac{14}{15}

當然這麼搞其中後面三個都是增根...

那麼得進行數值計算消根了...


Update: 按這個思路寫了個demo

CosFind[num_] := Block[{fun, eqn, sol, find},
Echo[fun = First[tri // RootReduce][x] == 0];
Echo[(eqn = fun /. x -&> Cos[Pi t] // TrigToExp) /. t -&> p/q];
sol = t /. Normal[Solve[{eqn, 1 &> t &> 0}, t], ConditionalExpression];
find = sol[[FirstPosition[Chop@N[num - Cos[Pi sol]], 0]]];
First@FullSimplify@find
]


Update2:

我覺得應該有更好的演算法...比如直接找域擴張.

畢竟根約化在很複雜的情況下是很慢的...

可能要用到一些分圓域之類的高級技巧...


更新一下,首先做一點明確,這裡只需要初始值是 cos(qpi) ( qinmathbb Q ),並不需要這個數只用根式或者二次根式表達( @Andre ).

簡單評價一下這個過程。

  1. 從計算的角度,如果一開始任給一個實數x,我們可以通過這個方法估計 arccos x . 進行n步迭代之後,記這n次操作的複合為F. 任取[0,1)之間的一個數,比如說0,那麼由於 |F(x)-0|<1 ,就有 |x-F^{-1}(0)|<frac{1}{2^n} (因為每次乘二),那麼 |arccos(x)-arccos(F^{-1}(0))|<varepsilon_n ,其中 varepsilon_n 是由一致連續得到的跟n有關的數. 所以看起來這個方法似乎能估計哎~能數值計算arccos哎~指數收斂哎~但仔細想想這跟二分法沒有本質差別。思路上來說相當於是逆向的二分法,但是不論從收斂速度、計算複雜程度還是最後計算的方式,都與二分法沒什麼差別。所以也許思路比較清奇,但橫向比較比不過二分法。
  2. 從證明的角度,相當於給出了結論「 eta=cos(qpi)(qinmathbb Q) 當且僅當某個關於 eta 的迭代在有限步出現循環」。也就是給出了這種數字的一個判准咯。但是,我感覺這跟「 eta=cos(qpi)(qinmathbb Q) 等價於把有理數排一列一個一個試一試在有限步發現等於 eta 」沒有本質上的差別。至少相同點是都沒什麼用。

————————————————————————————————

xy. 這個演算法其實跟反三角函數沒啥關係。其實問題就是,如果我知道q是個(0,1)裡面的有理數,那麼能不能知道q是多少。(話說這個說法超級奇怪。。)

手機打字,為了說明起來簡單,我換一個跟題圖裡面不太一樣的演算法,但原理是一樣的。

其實很簡單,每次把q乘2(2換成別的也一樣),如果某一次大於等於1了,那麼就減一個1拉回來。注意記下每一步的操作。那麼這樣操作下可以得到一列數。但由於已經知道了q是有理數,這種操作並不會改變分母,所以可能的變化只有有限多種,所以一定會出現循環。具體來說,有兩種情況:

1 這個數列碰到了0。那麼「若干步後是0」這是個方程,就可以解出來q了。這種情況發生當且僅當q=a/2^b. 這種情況題圖裡面也並沒有說明。

2 出現了非0的循環。那麼「某兩步的數相等」就是個非平凡的方程,就可以解出來了。

如果我們把q套上一個比較好看的函數f,也就是假定f(2x)和f(x-1)都可以很好看地用f(x)表示出來,比如說反三角函數,那麼就是題圖裡面的步驟了。

我懂得少,不知道這是不是重複造輪子。我看實際應用上別的答案評論區裡面有分析了,我只說一個理論上的事情,一個關於cos(qpi)的最簡單的問題:是否存在有理數q使得cos(qpi)是不同於0,1,-1,1/2,-1/2的有理數?(這相當於是問,這個演算法是否有助於判斷什麼樣的數可以寫成cos(qpi).)在這個問題面前這個方法還是蠻無力的。


用一個演算法估計一個有理數好像是一道經典的演算法面試題……


首先原文例2.3的計算有誤,不過到 arccos eta =frac{11pi}{30} 為止都是正確的。

這個方法「似乎」是有用的,原理我雖然完全不懂,但是照著流程算總沒什麼問題,祭出我心愛的Mathematica

f[[Lambda]1_] := Block[{[Lambda] = [Lambda]1, res = {[Eta][0]}, n, sol, ans},
[Eta][0] := Piecewise[{{Abs[[Lambda]], Abs[[Lambda]] &<= 1/Sqrt[2]}, {Sqrt[1 - [Lambda]^2], Abs[[Lambda]] &> 1/Sqrt[2]}}];
[Eta][n_] := FullSimplify[Piecewise[{{2*[Eta][n - 1]*Sqrt[1 - [Eta][n - 1]^2], [Eta][n - 1] &<= Cos[(3*Pi)/8]}, {1 - 2*[Eta][n - 1]^2, [Eta][n - 1] &> Cos[(3*Pi)/8]}}]];
A[0] = x;
A[n_] := Piecewise[{{2*A[n - 1] - 1, [Eta][n - 1] &<= Cos[(3*Pi)/8]}, {2 - 2*A[n - 1], [Eta][n - 1] &> Cos[(3*Pi)/8]}}];
test[y_, res_] := FullSimplify[(y == #1 ) /@ res];
NestWhileList[#1 + 1 , 1, (AppendTo[res, [Eta][#1]]; !Or @@ test[[Eta][#1], Most[res]]) ];
n = Position[test[Last[res], Most[res]], True][[1,1]];
sol = Solve[A[n - 1] == A[Length[res] - 1], x][[1]];
ans = If[Abs[[Lambda]] &> Sqrt[2]/2, Pi/2 - x*(Pi/2), x*(Pi/2)] /. sol;
ans = If[[Lambda] &> 0, ans, Pi - ans]]
{f[Cos[(3/2)*Degree]], f[Cos[3*Degree]], f[Cos[5*Degree]], f[Cos[10*Degree]],
f[Cos[20*Degree]], f[Cos[21*Degree]], f[Cos[102*Degree]], f[Cos[153*Degree]]}

雖然圖中給出的幾個例子都能夠正常計算,但是這些其實是我有所選擇的,在初步的測試下,對於 frac{3^m 5^n}{2^p}k (m,n,p,kinmathbb{N}) 形式的角度可以計算出結果,但在我嘗試f@Cos[1°]的時候卡住了,不知道是迭代層數太深還是這個方法本身不支持,還請其他大神繼續分析。


一般不都是用泰勒級數算出來的么……


這題我不會,網上找的,這些函數都有冪級數展開式,精度要求高就多計算幾位


歡迎一起討論,也可以推出多一點的細節


有可行的演算法。

考慮Q=m/n(最簡分數形式),但先估算出某一特解(周期函數嘛)一個小區間(a,b)。

根據已知條件有理解存在,可以得出一個結論:該區間內,滿足最簡分數形式下分母小於等於n的有理數是有限的,那麼直接枚舉就可以解了。不負責證明,這個是直覺。

方程形式未必是餘弦函數,只要連續、不亂抖動都可以。(說的不嚴謹,反正不需要可微這麼強的條件)

比如這個函數,有理解位於(-1,1)內,第一輪考慮n=2,代入-1/2,1/2,沒撞到,再考慮n=3,代入(-2/3,-1/3,1/3,2/3),直到n足夠大,碰到正確解的最簡分母。

當然,計算機演算法必須考慮的問題是,浮點數的精度。。。。


推薦閱讀:

演算法能受到版權保護嗎?
隨機森林中訓練每一棵樹輸入的m個特徵都是隨機選取的嗎?
如果本科已經能拿到BAT演算法offer,是否還有必要讀研?
有什麼網站介紹數據挖掘演算法的實現過程的?
如何設計權重演算法?

TAG:演算法 | 數學 | 三角函數 |