Polynomial(Under Construction!)

Polynomial

由未知數(變數)與已知數(常數)的加法、減法、乘法所組成的式子,就叫做「多項式」。以變數次方為主角,多項式可以拆成許多「項」。

多項式的資料結構,要嘛開個array,每一格存一種次方的係數;要嘛開個list,把係數為零的項統統去掉然後串成一串。

Polynomial運算

多項式的運算,主要有加、減、乘、除、模、微、積、分解、代入。中學到大學接觸了六年,應當難不倒各位讀者,就不贅述了。

UVa 392 126 10719 10586 10951 463 930 10428 498 10268 10105

乘法

O(NlogN)。

分解(Kronecker's Algorithm)

Polynomial Factorization

N項多項式恰有N-1個根,可能有重根,可能是虛數。

「因式分解」。

「質式Irreducible Polynomial」

「生成器Primitive Polynomial」

原理是「Lagrange Interpolation」。

      N-1         x  - rj
p(x) = ∑  di  ∏  ---------
      i=0    j≠i  ri - rj

兩個多項式整除,所有對應點也會整除。

【待補文字】

Matrix Polynomial

Cayley-Hamilton Theorem:特徵值,就是根!

「最小多項式Minimal Polynomial」。

「共伴矩陣Companion Matrix」。

basis is Krylov matrix.
change to companion matrix.
http://homepages.laas.fr/henrion/aime@cz11/kukelova.pdf
多項式的根 ---> companion matrix 的特徵值
遞迴多項式 ---> companion matrix 的次方
遞迴多項式的公式解 ---> eigendecomposition

「冪零矩陣Nilpotent Matrix」。Aᵏ = 0。

Polynomial Function

Polynomial Function

「多項式函數」。離散與連續的橋樑。離散的係數值,變成連續的函數值。數學家正在探索其奧秘。

Horner's Rule

f(x) = 3x³ + 2x + 1 = ((((3 ⋅ x) + 0) ⋅ x) + 2) ⋅ x) + 1
f(5) = 3x³ + 2x + 1 = ((((3 ⋅ 5) + 0) ⋅ 5) + 2) ⋅ 5) + 1

這是一個演算法。一元多項式函數,代入數值。一乘一加,不斷更迭,求得函數值。完全不需要次方運算。

Taylor Series

              f'(a)          f"(a)             
f(x) = f(a) + ――――― (x-a)¹ + ――――― (x-a)² + ...
                1!             2!              

這是一道數學公式。將平滑函數變成多項式函數。

換句話說,以無限項的多項式函數,趨近平滑函數。

y  = f(x)
                                     h¹         h²      
y₊ = f(x₊) = f(x + h) = f(x) + f'(x) ―― + f"(x) ―― + ...
                                     1!         2!      

這是另一種形式。當x略微增減,得知y如何增減。

當h介於±1之間,則次方越大、數值越小。後面的項,數值越來越小,越來越細膩,越來越不重要。只取前幾項,即是取近似值!多取幾項,即是逼近真實值!數值精確度,以項數多寡來決定。

UVa 12413

e

「歐拉數Euler Number」。實際數值差不多是2.72。

計算eˣ的演算法:Taylor Series與Horner's Rule。

π

「圓周率」。圓周長除以直徑,實際數值差不多是3.14。

http://en.wikipedia.org/wiki/Category:Pi_algorithms

延伸閱讀:π is wrong!

http://www.math.utah.edu/~palais/pi.html

有兩派人馬,一派支持角度,一派支持面積。

角度派認為π是180°,是圓周角360°的一半,要乘以二才能補成360°,極不方便。這派人馬認為應該替360°特別訂立一個代號。

面積派認為π剛好就是單位圓面積,明明很方便,不需要改。

延伸閱讀:math.h

https://zhuanlan.zhihu.com/p/20085048

Polynomial(Under Construction!)

http://www.cs.jhu.edu/~misha/Spring15/
Legendre polynomial:  laplace solution of sphere coordinate
http://mathworld.wolfram.com/LaplacesEquationSphericalCoordinates.html

Hankel transform of Zernike polynomials are essentially Bessel Functions

Chebyshev polynomial: sine wave wrapped around a cylinder

[surface]

https://plot.ly/javascript/3d-surface-plots/
http://bl.ocks.org/supereggbert/aff58196188816576af0

[green function]

https://www.wolframalpha.com/input/?i=e%5E(i%7Cx-y%7C)+%2F+%7Cx-y%7C

e^(iκ|x-y|) / |x-y|

ΔG(x, y) + κ^2 G(x, y) = 0