有理函數Ｌ２近似法的近似複雜度

Abstract

在本論文中，我們研究的是對於一個給定的函數及測度，做Ｌ２近似時所需的計算複 雜度。 首先，我們分析高斯積分公式的建立所需之工作量，因為這是在任何做Ｌ２近似之題 目時都必須用到的。 其次，在近似過程中對於一個修正過的測度，我們應用三種演算法：一般性的克里斯 多夫演算法，最小解演算法和修正過的契比雪夫演算法來建立在求近似解過程中所必 須知道的正交多項式。 我們也分析了求正交多項式的線性組合時，所用的三種方法的複雜度，并提出了使用 它們的時機。 最後，我們結合前述各項分析的結果，而求出在計算趨近函數及趨近之誤差時，所需 的總工作量。 我們為了要求知有理函數之L ２近似，勢必要先求出修正過的正交多項式，而Gauts- chiy在７９到８２年間所提出的三篇論文中包含了三種演算法，我們用此三種演算法 來分析求正多項式之複雜度，此外，在三種方法求修正過的正交多項式時發現第一種 方法最省計算複雜度。 我們得到的結論是用高斯積分與用修正過的契比雪夫演算法所需要的複雜度最高。