Processing math: 100%
跳到主要內容

Quick Formula To Find Polynomial Form Given Finite Integers


日常生活中，常常會有機智問答，如給定一個數列 1,2,3,4,5,X ，請問下一項X是什麼，我們自然會回答 6 ，下一項是 7 ，事實上我們發現公式可以寫成 a_k = k  \quad  k=1,2,3,...
我們可以定義正式一個問題如下:
--------------------------------------------------------------------------
(Q)給定 n 個整數，如何找到 f 使得 (C) : a_k = f(k) , k = 1,2,3,...n
--------------------------------------------------------------------------
而根據知識，我們可以找到無窮多個多項式 f 可以滿足(C)，而恰好存在唯一一個 n-1 次多項式(polynomial) 可以滿足(C)，這問題的連續版本在數值分析(Numerical Analysis)領域稱為 interpolation ，也就是給定 S \subset \mathbb{R}^2，找到一個公式f 使得 \forall (x,y) \in S \quad f (x) = y [註: 這跟統計上迴歸分析不同的是，interpolation 要完全 fit !!，但是如果存在(x,y_1),(x,y_2) \in S,y_1 \neq y_2，因為函數無法一對多，則無法使用 interpolation !!   ]

而問題(Q) 在筆者讀高中的時候發現的一個公式，會找到一個最低項的多項式(如果只有紙跟筆的話)，分享給讀者~

先定義差分數列 b_k = a_{k+1}- a_{k} ，\{b_k\}^{n-1}_{k=1} 會比 a_k 少一項，記做 \{\Delta a_k\}^{n-1}_{k=1} ，每做一次差分會少一項。

我們持續做會得到很多差分數列，取它們的第一項，記做 \vec{a} :=< a_1 , \Delta a_1 , ..... \Delta^{n-1} a_1 > 再來定義 \vec{b}:= <C^{k-1}_0, C^{k-1}_1 , ....C^{k-1}_{n-1} >

所以 f(k) := \vec{a}\cdot \vec{b} = \sum^{n-1}_{i=0}\left[\Delta^{i}a_1 \cdot  C^{k-1}_{i} \right]  \qquad \text{(Plus & Minus  2007)}  

[註: 事實上我們只要做到差分數列是常數數列就可以停止了 !! ]

[舉例來說]
如下圖:  給定六個數字  \{ a_k \}= \{1,2,4,8,15,26\}  

\{\Delta^{1}a_k\} = \{1,2,4,7,11\}
\{\Delta^{2}a_k\} = \{1,2,3,4\}
\{\Delta^{3}a_k\} = \{1,1,1\}
\vec{a}=<a_1,\Delta a_1,\Delta^2 a_1, \Delta^3 a_1> = <1,1,1,1>

f(k) = C^{k-1}_{0}+C^{k-1}_{1}+C^{k-1}_{2}+C^{k-1}_{3}

展開得到

 f(k) = 1 + (k-1) + \frac{(k-1)(k-2)}{2} + \frac{(k-1)(k-2)(k-3)}{6} 

[檢查]
很明顯 f(1) , f(2) , f(3) 都滿足要求
計算 f(4) =  1 + 3 + \frac{3\cdot 2}{2}  + \frac{3\cdot 2 \cdot 1}{6} = 8
         f(5) =  1 + 4 + \frac{4\cdot 3}{2}  + \frac{4\cdot 3 \cdot 2}{6} = 15
         f(6) =  1 + 5 + \frac{5\cdot 4}{2}  + \frac{5\cdot 4 \cdot 3}{6} = 26
我們得到了 f ，這是最低項多項式可以滿足 (C)


[小結]
這公式當初是數感發現的，是個非常漂亮的公式，而原理應該可以用泰勒展開式的證明!!

[額外補充]
另外，還可以查詢 OEIS 大辭典，收集了數學家發現的整數數列，可以告訴你下一項是什麼 !! 還有這數列實際上會應用的地方


[以上純為學術經驗交流知識分享，如有錯誤或建議可留言~~] 
by Plus & Minus 2017.08



留言

張貼留言

這個網誌中的熱門文章

Nash Equilibrium & Best Responce Function (BRF) In Continuous Strategies

經濟學重要的賽局理論( Game Theory )領域，用數學描述人與人之間的理性互動，最重要的就是尋找奈許均衡( Nash equilibrium )， 本篇介紹其數學規劃與非線性方程組!!  假設有 p 名玩家(player i)，i=1,2,3,4,5,....p ， 正在玩一場遊戲(Game)~~，完全不合作，各自獨立作決策 每個人有決策向量 x_i \in \Omega_i \subseteq R^{n_i} (有n_i個決策變數)  定義長向量: \underbrace{x =  (x_1,x_2,x_3,....x_p)}_{\# \text{ of } \sum^{p}_{i=1}n_i \text{ variables }} \in  \prod^{p}_{i=1} \Omega_i = \Omega 對於每個 player i ，長向量可以寫成 x = (x_i , x_{-i}) ，x_{-i} 代表其他人(不是 player i) 能做的決策向量。 所有人各自作決策後，每個人都會個自的存在報酬效用函數 f_i (x)  \in \mathbb{R}  (報酬函數皆為公開已知資訊) 假設每位玩家是理性人(會極大化自己效用) 即 \forall i = 1,2,3,4....p \qquad  \underset{x_i \in \Omega_i}{\text{max }}f_i(x)   [註: 如果為合作可視為多目標規劃問題( multiobjective )，即 x_1,x_2,...x_p 可以由領導人一起決定] [註: 如果為合作而且把效用加總，即目標式變成 \sum_{i=1}^{p} f_i(x) ，可能對集體效益有更大的幫助，但是如何分配效益給 ( player i )會是個議題，可以查關鍵字 fair optimization ] 我們可以定義每個 player i 的 Best Response Function (BRF) or Best Reponce Set S_i(x_{-i}) \subset \Omega_i $$  S_i(x...
張貼留言
閱讀完整內容

Lattice & Multinomial Theorem

本文介紹格子點(Lattice) 幾何意義與多項式定理(Mutinomial Theorem) 的關係，並可協助我們理解計算一些機率問題。 [符號定義] 非負整數 / 非負實數:  \mathbb{Z}_{\geq 0} := \{0,1,2,3,4,......\}  \subseteq [0,\infty) =: \mathbb{R}_{\geq 0} 離散機率向量:  p_{I} := (p_{i})_{i \in I} \text{ s.t } \sum_{i\in I}p_i =1 ，|I|<\infty  發生事件 i \in I 的累積次數向量: k_{I} := (k_i)_{i \in I} \in \mathbb{Z}^{|I|}_{\geq 0} \mathbb{Z}^{|I|}_{\geq 0} 就是 |I| 維格子點 !! [格子點情境] 出發點定義為 k^{start}_{I}:= \overbrace{(0,0...,0)}^{|I|}，今發生一次 p_{I} 分布隨機互斥事件，等價於"點的移動"(state transition)，數學定義如下:   \text{Event } i  \text{ happens }  \Longleftrightarrow  \overbrace{(\color{red}{k_i},k_{-i})}^{k^{old}_{I}}  \underset{\text{with probability }p_{i}}{\longrightarrow}   \overbrace{(\color{red}{k_i+1},k_{-i})}^{ k^{new}_{I}}    PS1: 其中  k_{-i} := (k_{i'})_{i' \in I-\{i\}} PS2: 不管怎麼走都在第一象限，也就是只能往右，往上，往高.... 當發生 n 次獨立同分布 p_{I} (iid) 的事件後，所有可能點位置在以下的集合上 $$  S_{n}(\col...
張貼留言
閱讀完整內容

Linear Regression By Using Linear Programming

當拿到一筆資料準備玩統計，往往會想要做線性迴歸( Linear Regression )，找出一個模型( mathematical model )來解釋變數間的關係，一般都是使用平方距離，但是如果我們採用絕對值距離呢?? 而剛好在工業工程( Industrial Engineering )，作業研究( Operation Research ) 領域，發展成熟的線性規劃( Linear Programming ) 恰好可以來解決，是一個跨領域的應用 !! 已經存在有許多商業或open source 軟體，如: Gurobi ， Cplex ， Xpress ， Mosek ， SCIP  可以輕易求解大型的線性規劃問題。而不僅如此也可以利用整數規劃( Integer Programming )來做特徵選擇 ( Feature Selection )，甚至可以偵測離群值( Detect Outlier ) !! 本文只介紹最小絕對值和，關於 Feature Selection , Detect Outlier 可以參考 Mixed-Integer Linear Programming Robust Regression with Feature Selection , Oleksii Omelchenko , 2010 的論文。 [Data Fitting Problem] 給定n筆實數型訓練資料 (training data) \{(x^{k},y^{k})\}^{n}_{k=1} = \mathcal{D} , x^{k} =(x^{k}_1,x^{k}_2, ... , x^{k}_{p})\in \mathbb{R}^{p} , y^{k} \in \mathbb{R} ， 我們目標是想要找到一個函數 f_{\mathcal{D}} : \mathbb{R}^p \rightarrow \mathbb{R} 使得  \forall x \in \mathbb{R}^{p} , f_{\mathcal{D}}(x) \approx y ， 精確來說: $$ \text{Find } f_{\mathcal{D}} \text{ such that } f_{\mathcal{D}}(x)\...
張貼留言
閱讀完整內容