文章

顯示包含「計算數學入門系列」標籤的文章

目錄

20200718 想法源起 20200719 我們在做什麼(一) 20200722 我們在做什麼(二) 20200725 竟然成為數學家(一) 20200729 竟然成為數學家(二) 20200801 竟然成為數學家(三) 20200805 不同職級(一) 20200808 不同職級(二) 20200812 趕客系列(一)為什麼讀大學? 20200815 趕客系列(二)不同大學學位跟工作的關係 20200819 趕客系列(三)大學的目的 20200822 趕客系列(四)大學為什麼要有主修 20200826 趕客系列(五)要挑選一個什麼樣的主修 20200829 沒有無緣無故的恨(一) 20200831 科普系列 - 數學與電影動畫製作(一) 20200902 沒有無緣無故的恨(二) 20200905 沒有無緣無故的恨(三) 20200907 科普系列 - 數學與電影動畫製作(二) 20200909 終身職位的評核 20200912 學術界吸引人的地方 20200914 科普系列 - 數學與電影動畫製作 (三) 20200916 學術界辛苦的地方(一) 20200919 學術界辛苦的地方(二) 20200921 科普系列 - 數學與電影動畫製作 (四) 20200923 大學的讀書成績有多重要 20200926 本科生研究機會 20200928 科普系列 - 數學與圖像修復(一) 20200930 用創新的方法去教育科學 20201003 參加研討會的重要 20201005 科普系列 - 數學與圖像修復(二) 20201007 教授與教學 20201010 研究是什麼(一) 20201012 科普系列 - 數學與圖像修復(三) 20201014 研究是什麼(二) 20201017 研究是什麼(三) 20201019 科普系列 - 數學與圖像修復(四) 20201021 如何閱讀研究論文 20201024 研究生應該修什麼課 20201026 科普系列 - 數學與圖像修復(五) 20201029 本科生的多主修多副修 20201102 科普系列 - 數學與數獨(一) 20201105 幾位教授(一) 20201109 科普系列 - 數學與數獨(二) 20201112 幾位教授(二) 20201116 科普系列 - 數學與數獨(三) 20201119 幾位教授(三) 20...

計算數學入門系列 - 一些關於複數不等式的解

圖片
這個學期教授一門新的課程,其中有一個課題是討論一些微分方程數值解的絕對穩定性。 裏面牽涉到一些關於複數 (Complex Number)的不等式。 在這篇文章裏面介紹一些解決這些不等式的數值方法。 最簡單的例子,我們考慮 \( \left|1+z\right|\le1 \)。如果變數 z 是一個實數 (Real Number),這條不等式的答案相對比較簡單,在一般中學的課程裏面都應該已經提及過。經過一些運算,我們就可以得到 \( -2\le z\le0 \)。 如果 \( z \) 是複數, 我們就需要對複數有多一點的認識。首先我們需要去理解一下絕對值在複數的定義。其中一個方法我們可以將絕對值理解成一個複數的量或者是長度, 譬如說,\(\left|-i\right|=1\)。所以根據上面這個定義,我們就可以得到 \( \left|1+z\right|=\left|z-\left(-1\right)\right| \)就是在找一個複數 \(z \)和 -1 之間的距離。上面那條不等式,就是說要去找所有跟 -1 之間的距離就少於或等於1 的複數。 在複數平面上面,我們就可以找到一個中心在-1而且半徑為1的圓盤(Disk)。另外一個方法,我們可以把一個複數首先寫成 \( z=a+ib\) 。這樣子,不等式就變成 \( \left|1+a+ib\right|=\sqrt{\left(1+a\right)^2+b^2}\le1\),然後我們就可以找到一個中心在-1的圓盤的數學表示方式 \( \left(1+a\right)^2+b^2\le1\)。 而當 \(b=0\),我們就可以得到之前所提到的實數解 \( -2\le z\le0 \)。 上面的這個例子其實是一個一般情況的其中一個特別解。我們假設 \[ f_n\left(z\right)=1+z+\frac{z^2}{2}+\cdots+\frac{z^n}{n!} \] 為一個n項的泰勒級數(Taylor’s Expansion)。然後我們就需要找出所有滿足\( \left|f_n\left(z\right)\right|\le1\)的複數。剛剛討論的情況,就只是當\(n\)等於1時的情況。如果 z 是一個實數,我們需要解決的相關不等式,就只是一個找根 (Root Finding)的問題。 如果n等於2,我們就可以用一元...

計算數學入門系列 - 距離函數(三)

圖片
  一般來說,找出曲線的距離函數的表示方式並不簡單。舉個例來說我們如果想表示一個橢圓形, 最簡單的隱性表示方式就是找 \(f\left(x,y\right)=\frac{x^2}{a^2}+\frac{y^2}{b^2}-1\)。 但是計算一下,就可以知道他並不是一個距離函數。 甚至乎,\(f\left(x,y\right)=\sqrt{\frac{x^2}{a^2}+\frac{y^2}{b^2}}-1\)畫起來有點像,可是仍然不是我們想找的距離函數。 Figure 6. "ellipse1.jpg". An implicit representation of an ellipse. a = 0.25; b = 0.7; f=sqrt(x.^2/a^2+y.^2/b^2)-1; contour(x,y,g,30); axis equal; axis([-1.1 1.1 -1.1 1.1]) hold on contour(x,y,g,[0 0],'k--') colormap('jet') print -djpeg ellipse1.jpg 在Figure 6 可以看到,我們要找的橢圓形附近,y方向的等高線相對比x方向距離比較遠。要找出橢圓形的距離函數,我們就必須 要從每一個meshpoint找出在橢圓上距離最短的距離。 Figure 7. "ellipse2.jpg". The signed distance function representation of an ellipse. [m,n]=size(x); f = @(theta,x0,a,b) (x0(1)-a*cos(theta)).^2+(x0(2)-b*sin(theta)).^2; x0=zeros(1,2); for i=1:m for j=1:n    x0(1)=x(i,j);    x0(2)=y(i,j);    theta0 = atan2(x0(2),x0(1));    theta_s = fminsearch(@(theta) f(theta,x0,a,b),theta0);    sdist(i,j) = sign(sdist(i,j))*sqrt(f(theta...

計算數學入門系列 - 距離函數(二)

圖片
  而這個圓形的其中一個隱性表示方式,可以首先構造函數\(f(x,y)=x^2+y^2-1\),然後找出這個函數等於零的地方。可以得到f(x,y)=0,就是說 \(x^2+y^2-1=0\),所以 \(x^2+y^2=1\),然後就找到了在圓形上面所有點所需要符合的數學方程式。 Figure4."circle4.jpg". An implicit representation of a unit circle. x=[-1.1:0.01:1.1]; [x,y]=meshgrid(x,x); f=x.^2+y.^2-1; contour(x,y,f,50); axis equal; axis([-1.1 1.1 -1.1 1.1]) colormap('jet') hold on contour(x,y,f,[0 0],'k') print -djpeg circle4.jpg 雖然說是一個隱性的表示方式,但是MATLAB裏面指令contour 還是可以把函數f 等如0 的地方找出來。我們是需要在第四個輸入指出所需要繪畫的水平線就可以了。 在這幅「等高線」contour的圖上面,我們可以看到這些代表着函數值的不同線相距並不相等。比較接近圓心的, 函數比較平,代表着他的斜率相對比較少。越往外圍走, 線與線之間的距離越密,代表着他的斜率相對比較大,函數的值越升越快。 前面提到,上面這個函數f只是其中一個隱性的表示方式。 如果我們希望函數的斜率 在不同的地方不會有太大的改變,我們可以在設計這個函數的時候希望他的斜率可以被控制,比如說我們希望「斜率的值等於1」。這裏要再仔細定義「斜率」。在一般微積分裏面,我們知道斜率就是一個函數的導數。可是我們現在看見的函數並不只有一個變量,所以這裏所講的斜率,其實是函數f梯度 (Gradient) 的長度,數學上來說就是 \( |\ \nabla f| \)。 用圓形作為例子,我們可以選取 \(g\left(x,y\right)=\sqrt{x^2+y^2}-1\)。同學們如果有修讀過多元微積分,可以計算一下這個函數g梯度的長度。 Figure 5. “circle5.jpg”. An implicit representation of a unit circle using the s...

計算數學入門系列 - 距離函數(一)

圖片
在跟學生討論研究問題時,發現他們需要找出一條在平面上閉合曲線(Closed Curve)的隱性表示方式(Implicit Representation),去構做一條例子證明研究的方法有效。不像顯式表示(Explicit Representation),我們不想將曲線用兩個函數x(t)和y(t)寫成(x(t),y(t))表示出來。所謂隱性表示方式,我們希望直接構造一個函數f(x,y)而令到函數等於某一個先前固定值的地方就是我們所需要找的閉合曲線。舉一個很簡單的例子,如果我們需要找出一個半徑為一的圓形,他的顯式表示可以用極坐標(Polar Coordinates)寫成(x(theta),y(theta))=(cos(theta),sin(theta))。在MATLAB上面可以用下面的方法標示出來。 Figure1.“Circle1.jpg”. Explicit representation of a unit circle (default). Figure2."Circle2.jpg". Explicit representation of a unit circle (with the aspect ratio fixed). Figure3.“Circle3.jpg”.  Explicit representation of a unit circle (with the aspect ratio and the axis fixed). theta=[0:2*pi/100:2*pi]; x=cos(theta); y=sin(theta); plot(x,y) print -djpeg circle1.jpg axis equal print -djpeg circle2.jpg axis([-1.1 1.1 -1.1 1.1]) print -djpeg circle3.jpg 留意一點,MATLAB在繪圖時圖表的比例並不是一比一,所以如果我們要繪畫一些比喻像圓形的圖案時,用MATLAB自己的繪圖比例,圖形看起來並不像一個圓形,反而像是橢圓形(就像上面Figure1的情況)。所以如果我們繪圖是希望看見一個更像是圓形的形狀,我們就必須要使用axis equal去把圖像的比例弄對才可以。Figure2看起來才是一個圓形。這幅圖唯...

計算數學入門系列 - 疊代方法(四)

圖片
對於疊代本身,其實亦有着一些很有趣的數學問題。其中一個是關於混沌(Chaos)的理論。有一些數學系統,本身的定義就會根據疊代的法則進行演變。可以假設x(n)代表着第n次疊代後的數值,而每一次進行疊代,我們只需要根據函數f來定義。數學上來說,我們定義x(n+1)=f(x(n)),然後希望看一下根據這個疊代所做出來的數列是否有一些特別的特性。其中一個我們可能想找的是不動點(Fixed Point),就是說想找一個數值x不受疊代過程所改變。跟上面找出函數f的根不同,我們希望找到的是另外一個函數g(x)=x-f(x)的根。 如果函數f(x)只是一個線性函數,討論本身相對簡單,也比較沒有趣味。而一個最簡單的非線性函數是定義\(f(x)=\mu x(1-x)\),而函數內參數\(\mu\)一定要為一個正數。這個疊代過程也叫做單峰映射(Logistic Map)[ 3 ]。比如說,我們選擇參數\(\mu\)等於1,我們用x0=1/2開始進行疊代,x1=1/2*1/2=1/4,然後x2=1/4*3/4=3/16,再得到x3=3/16*13/16=39/256,等等。我們可以看到做出來數列的數值越來越接近零。仔細的看一下這個問題,我們會發現,如果函數f存在着一個不動點,這個不動點的數值將會符合x=x(1-x)這條方程式。而這條方程式的唯一解就是x=0。 複雜一點的例子,我們可以將參數作出一點改變,比如說我們選擇參數\(\mu\)等於1.5,我們用x0=0.5開始進行疊代,我們會得到x1=1.5*0.5*0.5=0.375,然後x2=1.5*0.375*0.625=0.3515625,再得到x3=0.34194946891,等等。我們會發現疊代所做出來的數列似乎並不是趨向零。如果函數f存在着一個不動點,這個不動點的數值將會符合x=1.5x(1-x)這條方程式。而這條方程式存在着兩個解,其中一個是x=0,而令一個是上面數列似乎會趨向的x=1/3。 同學如果挑選一個細於3的參數,然後使用不同的初始條件進行疊代可以發現所產生的數列將會趨向\( (\mu-1)/\mu \)這個數值。同學可以使用普通的計算機進行一些簡單的運算看看情況如何。可是,如果參數大於3,情況就有點特殊。我們可以發現,絕大部份初始條件都會產生一些不收斂的數列(除非你挑選初始條件x=0)。如果\(3<\mu<1+...

計算數學入門系列 - 疊代方法(三)

圖片
對於找出函數f的根的問題,其中一個比較常用的方法就是牛頓法(Newton’s Method )[ 2 ],x(n+1)=x(n)-f(x(n))/f’(x(n))。如果初始數值相對比較接近確切解時,我們可以證明牛頓法收斂單根(Simple Root)的速度為2。雖然速度非常快,但是使用這個方法是我們有兩點需要注意。第一個使用牛頓法的困難,是我們需要使用一個在確切解附近的初始數值。一般來說,我們會根據實質應用,對答案有一個想法。可能是先對實質情況的一個非常初步的簡化,用這個簡化了問題的答案作為牛頓法的初始值。可是這個初始值是否夠接近這個確切解,我們就一般都不太確定了。一般的做法,就是對牛頓法有信心,「相信牛頓」就可以了(!)。更重要的問題,是方法需要用到函數的導數(Derivative)。比起二分法,這裏對函數的要求比較多,我們不單單只希望函數是連續函數,我們更希望函數有一定的正則性(Regularity)。在一般情況,我們可以清楚知道函數的導數是否存在,在功課內更加毋庸置疑。同學如果可以直接把函數寫出來,很容易的就可以知道函數是否一個可微函數(Differentiable Function)。將日常生活的應用,我們有些時候甚至乎不一定知道函數是否一個連續函數,要研究他是否一個可微函數就更加困難。就算我們知道他是一個可微函數,計算起來還是可能很複雜以致有些時候我們可能不太想把他的導數計算出來。所以,有些時候我們就只會使用導數的近似值,這就得到了割線法(Secant Method)。 假設我們現在想解決的問題,並不是一個普通函數f(x)=0的問題,而是一個線性代數問題。就是說f(x)=Ax-b,這裏的x和b就不是一個純量(Scalar)而是一個向量(Vector),而A就是一個矩陣。這個問題就沒有辦法使用二分法去計算因為答案x是在一個高維空間。如果我們使用上面的牛頓法,函數的導數就會變成他的雅可比矩陣(Jacobian),就是矩陣A本身。而牛頓法,就可以寫成 \[ x(n+1)=x(n)-J^{-1}*f(x(n))=x(n)-A^{-1}(Ax(n)-b)=A^{-1}b。\] 這代表什麼呢,這代表牛頓法找出來的就是線性代數方程的確實解。而中間的過程,我們就必須要計算矩陣A的逆矩陣(Inverse Matrix)。在上面文章提到,如果矩陣A非常大,這個方法就不切實際了...

計算數學入門系列 - 疊代方法(二)

圖片
聽起來相當簡單,剩下來的問題,就是如何設計中間的運算過程。最重要的條件,就是當n越大,我們希望xn越接近確切解y。不同的設計,就會得到不同的方法。其中一個運用到上面IVT特性的方法,就是同學們可能一早認識的二分法(Bisection Method)。假設我們知道函數f的根在a和b之間而且(a<b),我們可以取x1=(a+b)/2就是兩點的中間值作為一個近似值然後我們再去判別函數f的根到底是在a到x1之間還是在x1到b之間。這個判斷方式,就可以再運用IVT。如果f(a)*f(x1)<0,我們就可以知道在a跟x1之間就會有一個函數f的根,所以我們就可以取x2=(a+x1)/2。反之如果f(x1)*f(b)<0,我們就可以取x2=(x1+b)/2。如此類推,我們就可以得到一數列的xn。由於每一次進行二分法的計算,線段的長度就會短了一半,當n越來越大我們就知道,我們就知道xn會收斂(Convergence)到一個數值。 有沒有什麼情況這個二分法會失效的呢?譬如說,當x大於或者等於零,函數f輸出數值就是等於1;當x少於零,函數輸出數值就是等於-1。這個函數f並沒有根,可是上面的二分法還是會得出一個收斂到0的數列。心水清的同學,可能就會馬上指出這個函數f並不是一個連續函數,所以上面二分法的分析並不適用在這個函數例子裏面。完全正確。所以雖然二分法的使用非常簡單,同學們在使用之前還是需要對函數f進行一定的認識,確保他起碼是一個連續函數。另外的一個例子我們可以考慮函數f(x)=cos(2N*x)。你可以假設N為一個很大的正整數。這個例子有點奇怪,儘管程式的不同執行方式,都可以得到一個收斂的數列,但是他們可能將會得到函數f不同的解。程式內先考慮二分後左手邊線段的情況,還是先考慮右手邊線段的情況,都會得到不同的答案。剛開始的線段,也會令到我們得到不同的解。這個例子顯示,我們把這個二分法在運用到日常生活時,不但需要知道函數f的一些特性,我們還希望剛開始的線段不要太長,令到計算線段太大,希望在線段內只有唯一一個解。 二分法的好處,是我們要求函數f的特性相對比較簡單,我們只希望他是一個連續函數。可是,在實質運用上,二分法所產生的數列收斂起來有點太慢。如果要運算f需要很多計算量,這個方法就不太實際。這裏就引入疊代方法的第二個重點。除了上面關於修練性的要求,我們還希望這個產生的數...

計算數學入門系列 - 疊代方法(一)

圖片
上面提到一些疊代方法(Iterative Methods)去解決線性代數問題。回想一下,大部份計算數學的方法都是建基於疊代的概念。所以,在這篇文章會簡單介紹一下疊代方法以及他在不同地方的應用。 首先解釋一下為什麼我們需要用疊代的方法。對於一般同學來說,解決數學的問題,應該都可以找到一個確切的答案(Exact Solution)。要解線性代數問題2x-1=0,作為學生,我們都必須會得到x=1/2。一個比較普及的問題,要解決f(x)=0,我們都會想辦法運用不同的數學技巧,把未知數x用一些數學的表示方式寫出來。可以的話,我們會把未知數x放到一邊,把數值弄到方程式的右手邊。這樣我們就把函數f的根(Root)找出來。也可能,把函數f寫成多個項(Terms)的乘積(Product),函數f的根就會使所有項的根的集合。舉個例來說,如果函數f(x)=x2-1,我們會把f(x)寫成(x+1)(x-1),這樣函數f的根就是1或者-1。這些方法,同學們都用了好幾年的時間,在中學生涯不斷學習不同的數學技巧,把不同函數的情況都學過一遍。但事實上,還是有很多函數,我們是沒有方法可以把他的確切解找出來。 其中一個例子,我們可以想像函數f(x)=x-cos(x)。我們當然認識g(x)=x和三角函數h(x)=cos(x),可是要找出g(x)=h(x),情況就不是那麼簡單。純數學家第一個想解決的問題,就是想知道這個函數是否有實(Real)的根,這是個存在性(Existence)的問題。要解決這個問題我們可以使用介值定理(Intermediate Value Theorem, IVT)。簡單來說,這個定理指出,對於一個連續函數(Continuous Function)f,我們必定可以在線段(a,b)中間找得到一點x=c,令到f(c)的數值在f(a)和f(b)之間。在上面的例子來說,我們知道f(0)=-1<0而且f(1)=1-cos(1)>0,所以我們就知道在0到1之間一定存在着一個y令到f(y)=0。而且個y就是我們想找到的函數f的根。純數學家下一個將會問的問題,是想知道這個y是否函數f唯一的根。這是個唯一性(Uniqueness)的問題。對於形容數學家來說,我們更想知道的,是這個根到底是什麼。如何可以把這個答案找出來。 上面說過,我們沒有方法把確切解找出來。所以我們就需要有一些近似值的方法...

計算數學入門系列 - 線性代數問題(二)

圖片
上面這個例子,我們考慮一個2X2 的矩陣,矩陣內每一個元素都是1。由於這個矩陣的兩橫行相等,在計算時,程式就會跟我們說這方程組並不何解。 對於MATLAB 來說,最神妙(不是之一)的內置程式,就是這個「\」,用法是 >> x=A\b; 這個計算裏面,並不會計算A的逆。這個表達式要求程式找出x 令到A乘以x等於右手邊的向量b。MATLAB 會根據A的特性用不同的方法把一個答案找出來[ 1 ]。 自己以往做過一些問題,需要解決的方程組非常巨大也異常複雜,運用其他譬如說C++ 的軟件,根本沒有辦法把方程組的答案找出來。還是需要用到MATLAB 這個神奇的內置程式。網上有人指出,這個backslash 內置函數可能有高達25萬行的程式[ 2 ]。因為裏面考慮到那麼多不同的情況,而每一個情況用到的計算方法也比較專業,所以甚至乎你跟我說程式裏面其實有一百萬行,自己一點也不會驚訝。由於這個「秘密武器」,自己也漸漸少用了FORTRAN/C/C++ 的這些編寫程式語言,而越來越多使用MATLAB。 雖然這個內置函數非常強大,但是在研究裏面反而會帶來一點困擾。由於我們很多時候都希望自己做出來的研究成果可以比其他人複製(就是所謂的reproduceable),如果其他研究員並不是使用統一編程語言,有機會沒有辦法再次做出我們在論文裏面提到的結果。所以有些時候,我們反而不希望太過倚賴這個函數。 要避免這個倚賴,有些時候我們就需要仔細考慮矩陣A 的一些特性,去使用其他的計算方法解決這個線性代數問題。在本科生的課程,數值分析的這門課裏面,我們就會介紹幾款經典的迭代方法(Iterative Methods) 去把問題的近似值找出來。在實質應用上,我們一般都不會使用這些經典的方法,可是他們也可作為入門,讓我們了解如何設計一些好像(Preconditioned) Conjugate Gradient 或者Multigrid 等等的新的迭代方法。仔細的也不會在這裏討論有興趣的同學可以看看上面的參考書。MATLAB 裏面也有不同的程式,包括了minres, gmres, fft, pcg 等等的方法。雖然很多時候效果沒有「\」那麼好,可是在使用上我們可以有多一點的控制。

計算數學入門系列 - 線性代數問題(一)

圖片
上文提到如何在程式內建構一個矩陣,在這篇文章我們討論一下如何解決一些矩陣的數值問題。最簡單的數值問題,是去找尋N 元一次方程組的答案,數學上來說我們希望找出Ax=b 的根。方程式裏面A 代表一個矩陣,b 代表着方程組的一個已知向量。對於純數學家來說(在本科生課程裏面的線性代數),我們只會問這個方程組有答案嗎?有答案的話,他是唯一的嗎?要真的找出這個方程組的答案,課程裏面,我們也只會用高斯消去法(Gaussian Elimination)一步一步的把答案找出來。對於一些不是很大的問題(就是說N 並不會太大),這個高斯消去法當然不會有太大的問題。方法 一般都可以把確切解(Exact Solution)找出。 可是這裏有兩個問題。第一個,確切解有多exact 其實是可以被質疑的。主要原因是因為前面文章有提過,在電腦裏面我們根本沒有辦法把所有數字確切的標示出來。在那麼多的加減乘除後,我們真的有辦法知道計算出來的數字到底有多準確?當然我們可以說,如果答案準確至小數點後十多個位,誤差一般都不會很大。在一般應用上來說,這個問題應該不會有太大影響。可是這個解釋,對應用數學家來說並沒有太大的吸引力。我們需要的是一個更嚴謹的證明去說明每一步驟微小的不準確,是如何影響着答案的準確度。在數學上來說,這是一個關於算法(Algorithm)本身的穩定性(Stability)的問題。一般在本科生的課程裏面並不會提到。同學們如果有興趣可以參考一些數值線性代數的參考書(譬如說Golub 和Van Loan 的Matrix Computations)。這裏就不再仔細討論。可是比較大的問題,是這個算法的計算量實在太大。簡單來說,要找出一個N 元一次方程組的答案,高斯消去法就差不多需要N的3次方那麼多的計算量。對於應用數學上的問題,這個方法就變得不切實際。 在程式內,很多同學都會第一時間使用MATLAB 的內置函數inv 把矩陣A 的逆 (Inverse)找出來 >> x=inv(A)*b; 這裏沒有錯, x的解(如果我們可以把A的逆找得到)就真的等於這個表達式。 可是,要找出這個矩陣的inverse,可能就真的需要用一些像高斯消去法的方法。所以當矩陣很大時,這個方法就不可行。而且,儘管A本身可能是非常稀疏,他的inverse 一般來說都會是一個全矩陣。這個表達式就先需要把這個全矩陣儲存起來,...

計算數學入門系列 - 矩陣的儲存(二)

圖片
上面這個例子,我們就設定了一個中等大小的矩陣,在一些問題裏面已經非常有用。可是有一點要特別小心,如果這個變量n 是更大,就比如說30000 ,上面這個方法就已經對電腦的儲存空間造成很大的負擔。主要的問題是,定義一個30000×30000 的矩陣,電腦就必須儲存9 千萬個數字。在MATLAB 內,就需要差不多1.8GB 的內存空格。 要解決這個問題,我們可以看見這9 千萬個數字裏面大部份都是0,而且這些數字在運算過程內我們可能根本沒有機會用到。所以雖然說1.8GB 的儲存空間,可是大部份根本沒有機會用到而浪費掉了。當我們要處理這些非常大的稀疏矩陣,我們可以使用MATLAB 另一個矩陣儲存方式,我們只需要把矩陣內不是0的地方標示出來就可以了。 以上面一個10×10的三對角矩陣為例,我們知道這個矩陣一共有10+9+9=28 個不是0的元素,所以我們可以先設定 >> D=zeros(28,3); D 是一個28×3的矩陣,每一橫行代表着一個不是等於0元素。我們會用前兩個數字 去代表位置,最後一個代表他的數值。 >> D(1:10,1)=1:10; >> D(1:10,2)=1:10; >> D(1:10,3)=-2; 這樣,我們就把矩陣的對角線上的元素定義好。再把 >> D(11:19,1)=1:9; >> D(11:19,2)=2:10; >> D(11:19,3)=1; >> D(20:28,1)=2:10; >> D(20:28,2)=1:9; >> D(20:28,3)=1; 矩陣內所有不是零的元素都已經定義後,我們再用 >> D=spconvert(D); 這個稀疏矩陣就完成了。這個方法的問題,是如果矩陣的大小有所改變,我們就必須要把不是零元素的數目重新設定,然後很小心的把位置計算清楚。但是,如果我們所需要定義的矩陣並沒有一些特別的特徵,我們很可能還是要用這個方法把元素一個一個的設定出來。 比較方便改變的方法,可以使用MATLAB內置函數speyes 或spdiags >> n=30000; >> tmp = ones(n,1); >> E = spdiags([tmp -2*tmp tmp], -...

計算數學入門系列 - 矩陣的儲存(一)

圖片
矩陣(Matrix)在應用數學裏面有着不可或缺的重要性。我們曾經用過矩陣的方式把計算區域標示出來(可以參考〈科普系列 - 數學、社會隔離與生命遊戲〉一文)。在數據科學裏面,我們曾經討論過如何把高維數據內的低維資訊找出來(可以參考〈科普系列 - 數學與數獨〉一文)。在〈科普系列 - 數學與圖像修復〉裏面,我們也曾經把圖像修復的問題,模擬成為找出鄰近地區色彩平均值的問題。在這篇文章裏面,我們希望討論一些關於矩陣的問題。 最基本要解決的問題,是如何在程式內把這個矩陣標示出來。如果矩陣相對非常細小,我們可以把矩陣內的所有元素一個一個標示出來,我們可以直接用MATLAB 的設定 >> A = [1 2; 3 4]; 這個矩陣A是一個2×2的矩陣,第一行是1和2的兩個數值,另外一行就只有3和4兩個數值。這個方法最為簡單,基本上也不會花太多時間就把矩陣定義出來。可是有些時候我們的矩陣非常大,這個把數值一個一個輸入的方法就非常浪費時間,也很容易出錯。可是如果需要解決的問題,矩陣並沒有任何的特性,而且也是一個全矩陣 (Full Matrix,就是說在矩陣內絕大部份的元素都不是0),我們也沒有其他辦法。 幸運的是,大部份這些非常巨大的矩陣,很多時候都會有一些特別的特徵,而且也更可能是一個稀疏矩陣(Sparse Matrix,就是說矩陣裏大部份的元素都是0)。所以我們在設定這些矩陣時會有一些很方便的方法。 如果我們想設定一個10×10的三對角矩陣(Tridiagonal Matrix),對角線上的所有數值都是-2,上對角線和下對角線的所有數值都是1,而剩下來的所有數值都是0,我們可以用MATLAB 內置函數diag >> B = -2*diag(ones(10,1)) + diag(ones(9,1),1) + diag(ones(9,1),-1); MATLAB 的內置函數diag 可以把一個向量放到矩陣的對角線上面。ones(10,1) 設定了一個10×1的向量,diag(ones(10,1)) 就做出了一個矩陣,而矩陣的對角線所有元素都是1。內置函數diag 還有一個功能,如果函數有兩個input,他就會把第一個輸入的向量放到第二個輸入的相對應對角線上。舉例來說,diag(ones(9,1),1) 就會把一個9×1的向量放到一個矩陣的上對角線。如果這個矩陣,...

計算數學入門系列 - 編寫程式模擬社會隔離(三)

圖片
所以這裏的問題,在於中心一點是否等於0。如果中心一點是0就沒有問題,不等於0的話答案就錯了。再仔細看一下,就是說,如果第一行count2 中心點是1,第二行就需要「-1」;如果第一行count2 中心點是0,第二行就不需要「-1」,就是說只需要「-0」。所以,要解決這個bug,我們可以把第二行改成 count2=[X~=0]; count2=sum(count2(:))-count2(2,2); 這樣子就可以了。 當然,就算我們不改正這一個bug,其實對整個程式不會有太大影響。因為如果中心一格等於0,我們根本不需要考慮居住在這一格的人是否滿意自己居住的環境然後考慮會否搬離這一格。所以無論答案是對還是錯,其實不會對整個程式有太大影響。甚至乎,同學在編寫這個程式時並沒有發現這個bug也沒關係,最後的模擬應該看不出來。  但是,這個例子就可以看出為什麼我們在編寫程式時有時會發現,程式越改越複雜,越來越難debug。因為很多時一小部份的錯誤並不會在整體上顯示出來。只有當我們將不同部份拼湊起來,作出改動,有些時候才會發現計算出來的答案和想像中好像有點落差,答案好像總是有點不對頭。有些同學在這個地方已經放棄,一直跟我們說找不到bug,跟我們說每一部份計出來的答案都和想像中的一樣。這可能是在編寫大型程式時最有挑戰的地方,同學們必須要回頭再去嘗試找出這些邏輯錯誤(Logical Error)。 這個模擬社會隔離的程式內,最重要的部份基本上已經完成,剩下來的是把需要搬來的人隨機放到一些空格來。針對着「隨機」, MATLAB 有兩個來自函數rand 和randn。可是他們都是用來產生一些隨機數,並不是可以直接使用在我們現在的應用上。那我們應該如何使用隨機函數rand 編寫我們的程式呢?我們可以簡化一點討論,假設我們現在有10個空格,用矩陣Y來表示。然後我們有5個人,要隨機放進這10個空格內。 聽起來好像有點複雜,但是其實我們只需要在矩陣Y內隨機放入1至5,代表着5個人的標記,餘下來的5格都放0,代表還是空置着。更簡單的方法,我們可以先將1至10隨機放入矩陣Y裏面,然後將6到10這些數字更改為0。這就完成了。所以剩下來最重要的問題,就是如何用隨機函數rand「隨機將1至10隨機放入矩陣Y裏面」。 這裏沒有一個最好的方法,同學可以運用自己的想像力,設計不同的方法達到這個效果。自己覺...

計算數學入門系列 - 編寫程式模擬社會隔離(二)

圖片
上面的三種方法,沒有那一個是絕對的好,或者是那一個絕對不要學習。根據同學們自己的能力可以隨便使用任何一種方法。第一種方法無疑是最直接,程式的脈落看起來也最清楚。可是程式可能會非常冗長,在copy-and-paste 的時候可能也要精神一點,不要忘記將其中一些內容更改。第三種方法,編寫要用最多腦力,也需要對MATLAB有更好的掌握。但是熟能生巧,當你習慣了MATLAB這套語言,這個兩行程式是最乾淨,而且程式執行起來也會更快捷。我自己對入門同學的建議,是先寫一個沒有錯誤bug-free 的程式,這比起是否有效率,是否乾淨更其重要。當同學對軟件更加純熟,才慢慢的想方法把for-loop 移除,想像一下如何可以用MATLAB的一些內置函數將程式簡化和加速。 在模擬社會隔離的這個數學模型裏面,還有另外一個相關的計算問題。由於我們需要看一下在我旁邊八個格裏面一共有多少人跟我同一標籤,再看一下這佔據所有鄰居的多少個百分比,所以除了上面的計算外,還需要看一下旁邊有多少空格有人居住。做法其實同上面的那個問題基本上一樣,唯一要注意的,是矩陣X所儲存的是0,1和2,代表着冇人居住,標籤A和標籤B。所以如果我們要計算有多少鄰居的話,我們如果只將上面的程式更改成為 count2=[X~=0]; count2=sum(count2(:))-1; 這樣就「差不多」可以了。第一項裏面我們只需要將conditional statement 改變為X~=0,就是說他不等於0的地方,就用1代表,有了標籤A或B,那一個對應的地方就放入0。 然後第二句,就只需要計一下count2 這個變量裏面有多少個1,我們就知道這個3×3矩陣裏面有多少個鄰居。 前面為什麼說是「差不多」呢?因為這個程式計算出來的答案有機會是錯誤的。當同學如果把不同的矩陣放入這個程式內跑,會發覺大部份情況都沒有太大的問題,程式也不會有任何錯誤訊息顯示。可是,有些簡單情況,程式出現的答案會是錯誤的。這一種程式的bug 是相當難被發現。他不是一些語法錯誤(Syntax Error),MATLAB是可以執行這兩項程式,他也不會告訴你計算出來的答案和你想象中顯示的不相符。 這兩項程式的問題,是在於第二行「-1」這個行為。上面我們需要在第二行「-1」,是由於我們知道在中心那一格重複計算了一次。可是在這個計算裏面,中心一格並不一定等於0,所以程式第二行...

計算數學入門系列 - 編寫程式模擬社會隔離(一)

圖片
以往其中一篇科普系列裏面提到一個簡單的數學模型,去解釋社會隔離現象的產生。 (有興趣的讀者,可以先參閱《數學、社會隔離與生命遊戲》)假設在一個社區內只有兩個不同的群體,我們用標籤A跟標籤B表示這兩個不同的背景群體。所代表的,可能是貧與富,也可能是華人與白人,也可能是喜歡自由黨或喜歡民主黨的。數學上,這個社區內所有的標籤,我們都可以用一個矩陣外表是,我們將它寫X(i,j)。這一個矩陣X裏面這個成員X(i,j),我們可以用1表示這個平房內的家庭有着標籤A,用2表示這個房間內家庭都有着標籤B。而如果這個房子還沒有成交,沒有人居住,我們就可以用0表示。這個我們以前提到的數學模型,用上下左右以及左上,右上,左下,和右下一共八間房子去定義「鄰居」。假設現在看(i,j)這個地方,他的鄰居將會是這八個,(i-1,j-1), (i-1,j), (i-1,j+1), (i,j-1), (i,j+1), (i+1,j-1), (i+1,j), (i+1,j+1)。要去定義「喜好」最簡單的方法,就是看這八個鄰居有百分之多少是跟我自己的標籤一樣。如果這個百分比太少,住在原本(i,j) 的人,就會搬離這個房子到其他地方居住。 如果我們要編寫一個MATLAB程式,如何可以簡單地說出在我旁邊有多少鄰居是跟我同一個標籤的呢?用一個簡單一點的例子,我們只考慮3×3的範圍,而我自己就住在(2,2) 這個地方。所以編寫程式的目的,就要看看在這個X矩陣裏面有多少個元素是跟X(2,2) 一樣。最簡單(亦是最簡陋)的編寫方法是, count1=0; if (X(1,1)==X(2,2))    count1=count1+1; end if (X(1,2)==X(2,2))    count1=count1+1; end … if (X(3,3)==X(2,2))    count1=count1+1; end 中間包含了八個condition。這個編寫的方式沒有錯誤,可是編寫起來非常麻煩,中間需要有很多copy-and-paste 和改動(所以編寫時,忘記了改寫某一些行的時候就很大機會有bug),而且看起來程式會非常長。另外一個好一點的辦法,是編寫兩個for-loop,程式將會大大縮短。 count1=0; for i=1:3 for j=1:3 ...

計算數學入門系列 - 計算區域的離散化(三)

圖片
情況在高維空間會變得有點複雜。在一維空間內, 我們上面考慮的都只是一段線段,沒有其他的可能性。在高維空間情況就有機會有點特殊。 在二維空間最簡單的情況是計算區域只是一個正方形或長方形。假設形狀是\([0,a]\times[0,b]\),我們可以很簡單的把計算區域離散化 M=…; N=…; dx=a/M; dy=b/N; x=[0:dx:a]; y=[0:dy:b]; [x,y]=meshgrid(x,y); 可是如果計算區域並不是一個長方形,而是一個圓形,我們就不可能用一些\([0,dx]\times[0,dy]\) 的小長方形把這個形狀覆蓋。那到底我們應該如何把這個區域離散化 就有點複雜了。如果計算區域的形狀太過複雜 (比如說很多在工程上的應用),一般都會使用小三角形把整個計算區域覆蓋,我們把這個過程叫做三角剖分(Triangulation)。這些在有限元法(Finite Element Method) 的計算都是必須的。 如何把這些小三角形安放在整個計算區域內有時都不是那麼容易。有一些有限元法 的準確度會根據三角形的形狀而有所影響,我們可能希望三角形盡量是等邊三角形,也可能只希望這些小三角形的鈍角不會太細小。編寫這些程式有時候也不是太簡單。 這個三角剖分的過程,在三維空間還是可以做出來。可是高維度的計算,就非常複雜了。當然,就算計算區域是一些高維度的長方形,一般的偏微分方程計算還是非常困難,最主要的原因是這些取樣點的總數將會非常之多。如果每一方向我們有 N個點,在d維 空間,需要計算點的總數將會是\(N^d\)。 以d=3為例, 一般電腦都不可以計算到N=200 的情況。如果在四維空間,用相同的儲存空間, N就最多只可以是大約53。 對於大部份我們有興趣的情況,用53點根本不可能做出一個正確和精密的計算。在學術上,這個叫做維數災難 (Curse of Dimensionality),一般我們做偏微分方程計算時都會盡量避免高於三維的計算。  另外也有一些計算問題,在高位空間的計算區域並不是像上面那麼的直接。以一些動態界面問題為例子,我們希望計算氣泡在水裏面的運動情況。這個動態介面本身就是我們的計算區域。 最簡單的情況,是如何將取樣點平均分布在球體上,本身也已經是一個研究問題,叫做湯姆森問題(Thomson Problem) 。 有一些情況還是沒有找出來。 ...

計算數學入門系列 - 計算區域的離散化(二)

圖片
假設我們有興趣的區域是在0到1之間,我們可以把這個區域分成某些數量的線段。最簡單的方式, 就是把這線段分成N 段相同長度的線段。 所以一共就會有N +1點。用MATLAB 的表示方式,我們可以用 N=…; dx=1/N; x=[0:dx:1]; 當然,還是有一些同學喜歡用looping 的方法,喜歡把第三行寫成 for i=1:N+1       x(i)=(i-1)*dx; end 需要留意的是,這裏一共有N +1點,所以最後一個index並不是N,要不是最後運算時就差了x=1 那一點。 這裏有一點奇怪的是,我們定義了線段的段數,而不是取樣點數。所以如果同學喜歡定義N點,那就記得要把dx 定義成1/(N-1)。 對於不同問題的邊界條件,我們可能會將這個簡單的分段作出一點變化。上面所說的,對於一些Dirichlet Boundary Condition 非常方便。這種邊界條件,固定了在邊界上面函數的數值。在一些應用來說可能是邊界的溫度已經固定了,然後我們希望找出在區域內其他地方的溫度。所以在進行導數的近似值的時候,x(1) 和x(N+1) 就可以直接運用邊界條件去固定他們的數值。另外一點要注意的是,當我們在解決這個在計算區域內的問題,裏面我們希望求的是N -1個取樣點的函數值。 如果同學希望要找出來的是N個未知數(而不是N -1個取樣點上的函數),那就可以把dx定義成1/(N+1) 。 有一些問題,我們希望做一個周期性計算區域(Periodic Domain),就是說我們假設答案有一個周期性的特性所以無論x 的數值是什麼,x 和x+1 這兩點其實函數值是會一樣。如果這樣子,我們定義計算區域是就不需要考慮x=1 這一點,因為這一點的數值其實會跟x(1) 一樣,我們就不需要再多花心神在這一點上。 N=…; dx=1/N; x=[0:dx:1-dx]; 如果寫這樣子, N這個數值就不是代表着線段的總數,而是代表着取樣點的數目。 然後有另外一些數學問題,我們希望取樣點是在線段的中心,而不是在線段的兩端。這樣,我們可以用 N=…; dx=1/N; x=[dx/2:dx:1-dx/2]; 這個取樣點的方法不太常用,對一般入門的同學可能沒有太大用途。可是當我們在解決一些守恆定律方程式(Conservation Laws), 用到一些有限容積法(Fini...

計算數學入門系列 - 計算區域的離散化(一)

圖片
很多的計算問題,我們都需要將計算的區域 (Domain)標示出來。我們要定義一個數學上的函數 (Function),就必須要提供兩個東西。第一個就是如何運算數字的方式。比如說f(x)=sin(x) 的這一個三角函數。 你給我一個數字x,計算機就可以把它變成另外一個數字。中間這個過程就是運算數字的方式。對於我們來說,這個運算模式可以算是一個黑盒,電腦當然不可能根據定義繪畫一個半徑為一的圓形,再將你放入的數字x作為角度,然後看一下在圓形裏形成的三角形高度是多少。不過沒關係,就算中間的過程是一個黑盒,在運用上,我們還是可以把它定義為一個函數。第二個需要定義的,是到底什麼東西可以放入函數裏面。我們把可以放入這個函數的數字收集起來, 這個就是我們所說的「區域」。 上面所舉例的函數,我們可以放進任何的數字,所以他的區域是可以由負無限去到正無限大的。另外一些例子,譬如說我們需要解決一些拋物線型偏微分方程 (Parabolic Partial Differential Equation),就好像是要知道在一個空間裏面溫度的分布如何隨着時間而改變。所以放入去函數 (在這個例子裏面,這個函數就是溫度)的數字,就是在空間裏面一點的座標。 當然我們可以問在這無限三維空間裏面的溫度,但是這些關於無限空間的問題在計算數學裏面一般是不會考慮的。其中一個原因,是當數字越來越大,可以正確表示的數字分布將會越來越稀疏。那我們可以得到的數值解就越來越不準確。第二,就算可以計算出來,我們也沒有辦法把它畫出來,要清楚表示你計算出來的答案將不會是一件容易的事情。通常我們只會把計算集中在一個有限的區域以內,然後假設在這個區域以外,答案可能不太重要又或者是沒有趣味。如果真的是需要計算在一個無限空間上面的答案, 我們可以把問題進行傅立葉 (Fourier Transform)變換, 然後在頻率空間上面只考慮有限的頻率來進行計算。 這些我就不再繼續討論。 就算我們考慮有限的區域,一般計算我們也不會要求將區域內所有地方的答案都找出來。純數學裏面一般都會考慮那一段數線 內所有的數值,就是所說的for all 或者for any。可是在應用或者計算數學裏面我們一般都會把這些計算區域先做一個離散化 (Discretization), 就是說我們會先做一個取樣過程,只計算在某些地方的答案。而如果有需要,我們就會再用插補 (In...

計算數學入門系列 - 數值表示方式(三)

圖片
  另外一個比較特別的,是可以看到在電腦裏面可以表示的數字並不是平均分布。上面我們可以看到在0.0 旁邊的數字,要比在1.0旁邊的密 (距離1.0 最近的數字所差距只有大約\(10^{-7}\))。 而這個在1.0附近的數字密度就大大影響着所有在電腦裏面計算的準確度。 想像一下,如果我們要計算x+y = x (1+y/x),如果y/x 是少於 \(\epsilon\),電腦將無法把1+y/x 準確計算出來。所以x+y就等於x。 由於上面這兩個關於數值分布的特性,在我們編寫程式時有些時候也要特別留意。其中一個例子是同學在編寫偏微分方程的數值解的時候,有時會出現下面的情況。 (下面用到的,是一些MATLAB 的程式,在其他編程語言裏面問題也差不多。) finalT=…; N=…; % number of time iterations dt=finalT/N; time=0; while (time~=finalT)       time=time+dt;       … end 上面這個結構,很多時候我們在解決跟時間有關的偏微分方程時都會用到。我們希望找到在finalT 時候的數值解。由於一些穩定性的要求,我們必須把從開始的時間到最後時間分隔成N分,然後也要把中間的所有數值解也找出來,而時間與時間之間的相隔用dt 來表示。 這個程式的問題是在於time 這個variable 會不斷改變,而這個不斷改變的time,我們會期待在N次運算以後剛好等於finalT,然後中間的while-loop 就會完成。這個疊代 (Iteration)過程完結以後,我們得到的數值解就是我們希望找到的答案。可是由於數字很可能無法被正確表示,有可能time 和finalT 是沒有辦法相等的。然後,這個程式就loop 死了。 那有什麼辦法解決呢?方法有很多,既然已經知道需要做N次疊代,為什麼不用它作為疊代 的index 呢? finalT=…; N=…; % number of time iterations dt=finalT/N; time=0; for i=1:N       time=time+dt;       … end   另外還有些情況,穩定性...

計算數學入門系列 - 數值表示方式(二)

圖片
通常我們介紹這些實數的標示方式,開始時都會用single precision 作為切入,如果同學有用C/C++, 在設定variable 的時候就會用到float 這一個class ,如果還有人在寫FORTRAN,用的就是real 這一個class。Single precision 只會用4 bytes (32 bits,意思就是說會用32個0或者1) 去代表一個實數。 表示的方式,會是 \( (-1)^s 2^{e-127} 1.f\)。s代表Sign,是32 bits 裏面的第一個bit,用來代表這個數字是正數還是負數,0 代表正數,1代表負數。 然後的1 byte = 8 bits 是e (代表exponent),會先化為一個整數, 再減去127。 剩餘的23 bits,叫作mantissa,每一個bit 的數值會用二進制小數點的數位值慢慢遞減。 例如,這23bits 裏面的第一個bit, 數位值就是½,第二bit 的數位值就是¼,如此類推。 如果e=0,無論s 或者f 是什麼,數值所代表的都是實數0.0。而如果\(e=11111111_{(2)}=255_{(10)}\),情況就有點不同。如果f=0,數值所代表的就是正無限大或是 負無限大 (根據s 是等於0還是等於1)。而如果f 是其他東西,就是同學最不知所措的NaN (Not A Number)。 通常這些情況,就很可能是同學在編寫程式時有Bug。中間一定有一些在編程時的問題。 舉個例子,\( 1.0 = (-1)^0 2^{127-127} 1.0\) 在single precision 裏面的表示方式是, \[0 01111111 000000000000000000000000000。\] 那麼,最接近0的正實數是那一個數字呢? 由於e不可以是0,我們要找的這個數字 的數值表示方式是 \( (-1)^0 2^{1-127} 1.0 = 2-126_{(10)}\),大約等於\(1.2\times10^{-38}\)。另外一個有趣的問題,是問,最接近1 而又比1大的實數是那一個數目字。 這個數字的數值表示方式是 \[0 01111111 000000000000000000000000001。\] 把它換回十進制,我們得到 \( (1+2^{-23})_{(10)}\) 。 因為這一個數值\(2^{-...