摘要:本篇博客將介紹該公式及其應用,首先我們來看一下該公式的內容及其證明。應用循環三對角線性方程組的求解本篇博客將詳細講述公式在循環三對角線性方程組的求解中的應用。
Sherman-Morrison公式
??Sherman-Morrison公式以 Jack Sherman 和 Winifred J. Morrison命名,在線性代數中,是求解逆矩陣的一種方法。本篇博客將介紹該公式及其應用,首先我們來看一下該公式的內容及其證明。
??(Sherman-Morrison公式)假設$Ainmathbb{R}^{n imes n}$為可逆矩陣,$u,vinmathbb{R}^{n}$為列向量,則$A+uv^{T}$可逆當且僅當$1+v^{T}A^{-1}u
eq 0$, 且當$A+uv^{T}$可逆時,該逆矩陣由以下公式給出:
$$(A+uv^{T})^{-1}=A^{-1}-{A^{-1}uv^{T}A^{-1} over 1+v^{T}A^{-1}u}.$$
證明:
$(Leftarrow)$當$1+v^{T}A^{-1}u
eq 0$時,令$X=A+uv^{T}, Y=A^{-1}-{A^{-1}uv^{T}A^{-1} over 1+v^{T}A^{-1}u}$,則只需證明$XY=YX=I$即可,其中$I$為n階單位矩陣。
$$ {displaystyle {egin{aligned} XY&=(A+uv^{T})left(A^{-1}-{A^{-1}uv^{T}A^{-1} over 1+v^{T}A^{-1}u} ight) &=AA^{-1}+uv^{T}A^{-1}-{AA^{-1}uv^{T}A^{-1}+uv^{T}A^{-1}uv^{T}A^{-1} over 1+v^{T}A^{-1}u} &=I+uv^{T}A^{-1}-{uv^{T}A^{-1}+uv^{T}A^{-1}uv^{T}A^{-1} over 1+v^{T}A^{-1}u} &=I+uv^{T}A^{-1}-{u(1+v^{T}A^{-1}u)v^{T}A^{-1} over 1+v^{T}A^{-1}u} &=I+uv^{T}A^{-1}-uv^{T}A^{-1} &=Iend{aligned}}} $$
同理,有$YX=I$.因此,當$1+v^{T}A^{-1}u
eq 0$時,$(A+uv^{T})^{-1}=A^{-1}-{A^{-1}uv^{T}A^{-1} over 1+v^{T}A^{-1}u}.$
$(Rightarrow)$當$u=0$時,顯然有$1+v^{T}A^{-1}u=1
eq 0.$當$u
eq0$時,用反正法證明該命題成立。假設$A+uv^{T}$可逆,但$1+v^{T}A^{-1}u = 0$,則有
$$(A+uv^{T})A^{-1}u=u+u(v^{T}A^{-1}u)=(1+v^{T}A^{-1}u)u=0.$$
因為$A+uv^{T}$可逆,故$A^{-1}$u=0,又因為$A^{-1}$可逆,故$u=0$,此與假設$u
eq 0$矛盾。因此,當$A+uv^{T}$可逆時,有$1+v^{T}A^{-1}u
eq 0.$
??在Sherman-Morrison公式中,令$A=I$,則有:$I+uv^{T}$可逆當且僅當$1+v^{T}u
eq 0$, 且當$I+uv^{T}$可逆時,該逆矩陣由以下公式給出:
$$(I+uv^{T})^{-1}=I-{uv^{T} over 1+v^{T}u}.$$
??再令$v=u$,則$1+u^{T}u > 0$, 因此,$I+uu^{T}$可逆,且
$$(I+uu^{T})^{-1}=I-{uu^{T} over 1+u^{T}u}.$$
??Sherman-Morrison公式在BFGS算法中的應用,可用來求解BFGS算法中近似Hessian矩陣的逆。本篇博客并不打算給出Sherman-Morrison公式在BFGS算法中的應用,將會再寫篇博客介紹BFGS算法,到時再給出該公式的應用,并會在之后補上該博客的鏈接(因為筆者還沒寫)。
應用3:循環三對角線性方程組的求解??本篇博客將詳細講述Sherman-Morrison公式在循環三對角線性方程組的求解中的應用。
??首先給給出理論知識介紹部分。
??對于$Ainmathbb{R}^{n imes n}$為可逆矩陣,$u,vinmathbb{R}^{n}$為列向量,$1+v^{T}A^{-1}u
eq 0$,需要求解方程$(A+uv^{T})x=b.$對此,我們可以先求解以下兩個方程:
$$Ay=b,qquad Az=u$$.
然后令$x=y-frac{v^{T}y}{1+v^{T}z}z$,該解即為原方程的解,驗證如下:
$$ {displaystyle {egin{aligned} (A+uv^{T})x&=(A+uv^{T})(y-frac{v^{T}y}{1+v^{T}z}z) &=Ay+uv^{T}y-frac{v^{T}y}{1+v^{T}z}Az-frac{v^{T}y}{1+v^{T}z}uv^{T}z &=b+uv^{T}y-frac{v^{T}yu+v^{T}yuv^{T}z}{1+v^{T}z} &=b+uv^{T}y-frac{(1+v^{T}z)v^{T}yu}{1+v^{T}z} &=b+uv^{T}y-uv^{T}y &=bend{aligned}}} $$
??這樣將原方程$ (A+uv^{T})x=b$分成兩個方程,可以在一定程度上簡化原方程。接下來,我們將介紹循環三對角線性方程組的求解。
??所謂循環三對角線性方程組,指的是系數矩陣為如下形式:
$$ A=egin{bmatrix} b_1&c_1&0&cdots&0&a_1 a_2&b_2&c_2&0&vdots&0 0&ddots&ddots&ddots&0&vdots vdots&vdots&a_{n-2}&b_{n-2}&c_{n-2}&0 0&cdots&cdots&a_{n-1}&b_{n-1}&c_{n-1} c_n&0&cdots&0&a_n&b_nend{bmatrix} $$
循環三對角線性方程組可寫成$Ax=d$,其中$d=(d_{1},d_2,...,d_{n})^{T}.$
??對于此方程的求解,我們令$u=(gamma, 0,0,...,c_{n})^{T}, v=(1,0,0,...,frac{a_1}{gamma})^{T}$, 且$A=A^{"}+uv^{T}$,其中$A^{"}$如下:
$$ A^{"}=egin{bmatrix} b_1-gamma&c_1&0&cdots&0&0 a_2&b_2&c_2&0&vdots&0 0&ddots&ddots&ddots&0&vdots vdots&vdots&a_{n-2}&b_{n-2}&c_{n-2}&0 0&cdots&cdots&a_{n-1}&b_{n-1}&c_{n-1} 0&0&cdots&0&a_n&b_n-frac{a_1c_n}{gamma}end{bmatrix} $$
$A^{"}$為三對角矩陣。根據以上的理論知識,我們只需要求解以下兩個方程
$$A^{"}y=d,qquad A^{"}z=u,$$
然后,就能根據$y,z$求出$x$.而以上兩個方程為三對角線性方程組,可以用追趕法(或Thomas法)求解,具體算法可以參考博客:三對角線性方程組(tridiagonal systems of equations)的求解 。
??綜上,我們利用Sherman-Morrison公式的思想,可以將循環三對角線
性方程組轉化為三對角線性方程組求解。我們將會在下面給出該算法的Python語言實現。
??我們要解的循環三對角線性方程組如下:
$$ {egin{bmatrix} 4&1&{0}&{0}&{2} {1}&{4}&{1}&{0}&{0} {0}&{1}&{4}&{1}&{0} {0}&{0}&{1}&{4}&{1} {3}&{0}&{0}&{1}&{4} end{bmatrix}} {egin{bmatrix}{x_{1}}{x_{2}}{x_{3}}{x_{4}} {x_{5}}end{bmatrix}}={egin{bmatrix}{76 668}end{bmatrix}} $$
??用Python實現解該方程的Python完整代碼如下:
# use Sherman-Morrison Formula and Thomas Method to solve cyclic tridiagonal linear equation import numpy as np # Thomas Method for soling tridiagonal linear equation Ax=d # parameter: a,b,c,d are list-like of same length # b: main diagonal of matrix A # a: main diagonal below of matrix A # c: main diagonal upper of matrix A # d: Ax=d # return: x(type=list), the solution of Ax=d def TDMA(a,b,c,d): try: n = len(d) # order of tridiagonal square matrix # use a,b,c to create matrix A, which is not necessary in the algorithm A = np.array([[0]*n]*n, dtype="float64") for i in range(n): A[i,i] = b[i] if i > 0: A[i, i-1] = a[i] if i < n-1: A[i, i+1] = c[i] # new list of modified coefficients c_1 = [0]*n d_1 = [0]*n for i in range(n): if not i: c_1[i] = c[i]/b[i] d_1[i] = d[i] / b[i] else: c_1[i] = c[i]/(b[i]-c_1[i-1]*a[i]) d_1[i] = (d[i]-d_1[i-1]*a[i])/(b[i]-c_1[i-1] * a[i]) # x: solution of Ax=d x = [0]*n for i in range(n-1, -1, -1): if i == n-1: x[i] = d_1[i] else: x[i] = d_1[i]-c_1[i]*x[i+1] x = [round(_, 4) for _ in x] return x except Exception as e: return e # Sherman-Morrison Fomula for soling cyclic tridiagonal linear equation Ax=d # parameter: a,b,c,d are list-like of same length # b: main diagonal of matrix A # a: main diagonal below of matrix A # c: main diagonal upper of matrix A # d: Ax=d # return: x(type=list), the solution of Ax=d def Cyclic_Tridiagnoal_Linear_Equation(a,b,c,d): try: # use a,b,c to create cyclic tridiagonal matrix A n = len(d) A = np.array([[0] * n] * n, dtype="float64") for i in range(n): A[i, i] = b[i] if i > 0: A[i, i - 1] = a[i] if i < n - 1: A[i, i + 1] = c[i] A[0, n - 1] = a[0] A[n - 1, 0] = c[n - 1] gamma = 1 # gamma can be set freely u = [gamma] + [0] * (n - 2) + [c[n - 1]] v = [1] + [0] * (n - 2) + [a[0] / gamma] # modify the coefficient to form A" b[0] -= gamma b[n - 1] -= a[0] * c[n - 1] / gamma a[0] = 0 c[n - 1] = 0 # solve A"y=d, A"z=u by using Thomas Method y = np.array(TDMA(a, b, c, d)) z = np.array(TDMA(a, b, c, u)) # use y and z to calculate x # x = y-(v·y)/(1+v·z) *z # x is the solution of Ax=d x = y - (np.dot(np.array(v), y)) / (1 + np.dot(np.array(v), z)) * z x = [round(_, 3) for _ in x] return x except Exception as e: return e def main(): """ equation: A = [[4,1,0,0,2], [1,4,1,0,0], [0,1,4,1,0], [0,0,1,4,1], [3,0,0,1,4]] d = [7,6,6,6,8] solution x should be [1,1,1,1,1] """ a = [2, 1, 1, 1, 1] b = [4, 4, 4, 4, 4] c = [1, 1, 1, 1, 3] d = [7, 6, 6, 6, 8] x = Cyclic_Tridiagnoal_Linear_Equation(a,b,c,d) print("The solution is %s"%x) main()
輸出結果如下:
The solution is [1.0, 1.0, 1.0, 1.0, 1.0]參考文獻
https://en.wikipedia.org/wiki...
http://wwwmayr.in.tum.de/konf...
https://scicomp.stackexchange...
https://blog.csdn.net/jclian9...
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/41692.html
摘要:為什么呢本文將對這一問題進行解疑并介紹多種多種激活函數。激活函數就是用來引入這個非線性因素的,下面介紹幾種常見的激活函數及其優缺點正負號表示。如果想了解更多可上網搜激活函數選擇在同一個模型中,激活函數不會混搭使用,選定一個就用一個。 【DL-CV】反向傳播,(隨機)梯度下降【DL-CV】神經網絡的補充 在介紹線性分類器的時候,提到了激活函數,還提到線性分類器的輸出要經過激活函數才能作為...
摘要:為什么呢本文將對這一問題進行解疑并介紹多種多種激活函數。激活函數就是用來引入這個非線性因素的,下面介紹幾種常見的激活函數及其優缺點正負號表示。如果想了解更多可上網搜激活函數選擇在同一個模型中,激活函數不會混搭使用,選定一個就用一個。 【DL-CV】反向傳播,(隨機)梯度下降【DL-CV】神經網絡的補充 在介紹線性分類器的時候,提到了激活函數,還提到線性分類器的輸出要經過激活函數才能作為...
摘要:寫本文的目的,希望結合眾家之長,試圖解決數學對機器學習入門的困擾。這里假設你上過大學的數學課,你就具備了機器學習的數學入門門檻了,之后的數學啃一啃是可以下來的。 寫這篇文章很久想了很久,到底該怎么寫? 關于數學與機器學習的關系,觀點很多。 寫本文的目的,希望結合眾家之長,試圖解決數學對機器學習入門的困擾。 現在數學困擾大家主要有這幾個方面: 1、 機器學習需要的數學知識是不是很難,網上...
閱讀 2655·2021-11-24 10:44
閱讀 1896·2021-11-22 13:53
閱讀 1908·2021-09-30 09:47
閱讀 3704·2021-09-22 16:00
閱讀 2433·2021-09-08 09:36
閱讀 2312·2019-08-30 15:53
閱讀 2791·2019-08-30 15:48
閱讀 977·2019-08-30 15:44