發刊日期 |
2019年12月
|
---|---|
標題 | 薛昭雄來函暨林開亮回覆(上) |
作者 | |
關鍵字 | |
檔案下載 | |
全文 |
梁教授: 頃閱數學傳播第 170 期 (2019 年 6 月) 文章"解常係數線性微分方程和遞推關係的新方法 --- 秦九韶和亥維賽的遺產", 作者為林開亮先生。 這是一篇非常好的科普文章, 值得推介給有興趣的讀者。 然而, 在第五節:解整數同餘方程的求一術中, 作者提到 "如解方程 $$250x\equiv1\pmod {2017},(1)$$ 你可能就無計可施了!"
本人覺得上面的敘述值得商榷, 因為 (1) 之解可用矩陣方法 (不必利用整數之帶餘除法), 請見文獻 下面是(1)式之解之說 \begin{align*} \begin{bmatrix} ~250&\,\,~1~\,\,\\ ~2017&\,\,0\,\, \end{bmatrix} &\xrightarrow[\mbox{ 加到第二列}]{\mbox{ 將第一列乘$(-8)$}} \begin{bmatrix} ~250~&1\\ 17&-8 \end{bmatrix} \xrightarrow[\mbox{ 加到第一列}]{\mbox{ 將第二列乘$(-15)$}} \begin{bmatrix} -5&121\\ ~17~&-8 \end{bmatrix}\\ &\xrightarrow[\mbox{加到第二列}]{\mbox{ 將第一列乘$(+3)$}} \begin{bmatrix} -5&121\\ 2&~355~ \end{bmatrix}\ \xrightarrow[\mbox{ 加到第一列}]{\mbox{ 將第二列乘$(+3)$}} \begin{bmatrix} 1&1186\\ ~2~&355 \end{bmatrix} \end{align*} 即得 $x\equiv 1186\pmod {2017}$。 參考文獻薛昭雄 美國內華達州立大學教授
答薛昭雄教授 --- 並附評論與反思 尊敬的薛教授:
謝謝您對拙文
此外, 對於
其實這篇文章還有許多可以改進的地方, 這裡我特別想指出的有五點。
第一 :
定理1 : [RSA解密算法] 設 $b, k,m$ 是給定的整數, $m$ 是正整數, $\phi(m)$ 是其歐拉函數。 $$\gcd(b,\ m)=1\qquad\text{且}\qquad\gcd(k,\ \phi(m)) =1.$$ 則下述步驟, 給出同餘式 $$ x^{k}\equiv b\pmod{m} $$ 的解。 用求一術解關於 $u$ 的同餘方程 $$ku\equiv 1\pmod{\phi(m)},$$ 得到 $u$, 然後令 $x=b^{u}\pmod{m}$。
第二 :
定理2 : [指數平移定理] 設 $$P(D)=a_n(x)D^n+a_{n-1}(x)D^{n-1}+\cdots+a_1(x)D+a_0(x),$$ 其中 $a_i(x)$ 是區間 $I$ 上的函數, $D$ 是對 $x$ 的求導運算元。 設 $\lambda(x)$ 是區間 $I$ 上的光滑函數, 則在 $I$ 上的 $n$ 次可導函數空間上, 成立以下運算元等式: $$\mathrm{e}^{-\lambda(x)}P(D)\mathrm{e}^{\lambda(x)}=P(D+\lambda'(x)),$$ 其中 $$P(D+\lambda'(x))=a_n(x)(D\!+\!\lambda'(x))^n\!+\!a_{n-1}(x)(D\!+\!\lambda'(x))^{n-1}\!+\!\cdots\!+\!a_1(x)(D\!+\!\lambda'(x))\!+\!a_0(x).$$ 特別地, 對 $\lambda(x)=\lambda x$ (此處 $\lambda$ 為常數), 我們有 $$\mathrm{e}^{-\lambda x}P(D)\mathrm{e}^{\lambda x}=P(D+\lambda).$$ 注意, 如同正文中一樣, 此處 $\mathrm{e}^{-\lambda( x) }$ 與 $\mathrm{e}^{-\lambda ( x)}$ 均表示由各自決定的左乘運算元, $P(D)$ 中的各個係數 $a_i(x)$ 也是如此理解。 更值得注意的是, $(D+\lambda'(x))^k$ 是運算元 $D+\lambda'(x)$ 的 $k$ 次冪, 因此 要作為運算元的複合來理解, 不能視為普通的(交換)二項式展開。 例如, 計算 $(D+x)^2$, 我們有 \begin{align*} (D+x)^2&=(D+x)(D+x)\\ &=D^2+Dx+xD+x^2\\ &=D^2+(xD+1)+xD+x^2\\ &=D^2+2xD+x^2+1, \end{align*} 其中我們用到了著名的對易關係 $$Dx-xD=1,$$ 它只不過是求導的 Leibniz 法則的直接應用 : 對任意的可導函數 $f$ 有 $$Dx(f)=D(x \cdot f)=D(x)\cdot f+x\cdot D(f)=f+xD(f)=(1+xD)f.$$ 定理2的證明: 根據上述解釋, 我們只要證明對 $P(D)=D^k$, $k=0,1,\ldots, n$ 的情況證明即可, 事實上不難發現, 只要證明 $P(D)=D$ 的情況, 此時任取一個可導函數 $f$, 計算 \begin{align*} (\mathrm{e}^{-\lambda(x)}D\mathrm{e}^{\lambda(x)})f&= (\mathrm{e}^{-\lambda(x)}D)(\mathrm{e}^{\lambda(x)} f)\\ &=(\mathrm{e}^{-\lambda(x)})D(\mathrm{e}^{\lambda(x)} f)\\ &=(\mathrm{e}^{-\lambda(x)})(\mathrm{e}^{\lambda(x)} \lambda'(x)f+\mathrm{e}^{\lambda(x)}Df)\\ &=\lambda'(x)f+Df\\ &=(D+\lambda'(x))f. \end{align*}
這個定理的一個直接應用是, 求解原文第 9 節中的廣義特徵方程 (見 此外, 該定理還可以倒過來應用, 即我們利用 $$\mathrm{e}^{\lambda(x)}P(D+\lambda'(x))\mathrm{e}^{-\lambda(x)}=P(D)$$ 來求解一個形如 $$P(D+\lambda'(x))y=f$$ 的方程。 容易看出在變數替換 $y=\mathrm{e}^{-\lambda(x)}z$ 下, 只需要求解方程 $$P(D)z=\mathrm{e}^{\lambda(x)}f.$$ 以下給出兩個例子: 例1: 求解 $(D+\lambda'(x))y=f$, 根據前面的說明, 令 $y= \mathrm{e}^{-\lambda(x)}z$, 只需要求解方程 $Dz=\mathrm{e}^{\lambda(x)}f$。 積分得 $z=\int \mathrm{e}^{\lambda x}f$, 從而 $$y=\mathrm{e}^{-\lambda(x)}z=\mathrm{e}^{-\lambda(x)}\int \mathrm{e}^{\lambda(x)}f,$$ 這就是我們在討論一階線性微分方程 $y'+py=q$ 時所得到的通解公式的等價表達。 例2: 前面我們已經算出 $(D+x)^2=D^2+2xD+x^2+1$, 於是可以討論方程 $$(D^2+2xD+x^2+1)y=f(x).$$ 在變數替換 $y=\mathrm{e}^{-\frac{1}{2}x^2}z$ 下, 只需要求解方程 $$D^2z=\mathrm{e}^{\frac{1}{2}x^2}f.$$ 連續積分兩次可得 $z$, 進而得出 $y=\mathrm{e}^{-\frac{1}{2}x^2}z$。
第三:
第四: 我們回顧一下上述求解思路, 會發現上述方法可用于求解形如 $$P(A)v=b$$ 的方程, 其中 $A$ 是某複綫性空間 $V$ 上的線性運算元, $b,v$ 分別是 $V$ 上的已知向量與未知向量, $P$ 是一個給定的複係數多項式。 求解的基本假定是: 設 $b$ 有零化多項式 $g(x)$。 於是 $b$ 落在空間 $\ker g(A)$, 設 $g(x)=(x-\lambda_1)^{m_1}\cdots(x-\lambda_s)^{m_s}$ 完全分解, 則根據正文 p.72 定理 3 (即 [5, 定理5.2.1]), $\ker g(A)$ 有直和分解: $$\ker g(A)=\ker (A-\lambda_1)^{m_1}\oplus\cdots\oplus \ker (A-\lambda_s)^{m_s}$$ 從而 $b=b_1+\cdots+b_s$, 其中 $b_i\in \ker (A-\lambda_i)^{m_i}$, $i=1,\ldots, s$。 根據線性性質, 為求解方程 $P(A)v=b$, 我們只需要對每個 $b_i$, 求解方程 $P(A)v=b_i$。 換言之, 我們可以不妨假定 $b$ 滿足 $(A-\lambda)^{m}b=0$, 即 $b$ 是 $A$ 的屬於特徵值 $\lambda$ 的廣義特徵向量。 於是, 我們考慮多項式同餘方程 $$P(x)U(x)\equiv 1\pmod{(x-\lambda)^m}.$$ 若 $P(\lambda)\neq0$, 則上述方程有解, 並且可由求一術得到 $U(x)$; 從而令 $v=U(A)b$ 即可。 若 $P(\lambda)=0$, 則 不妨設 $P(x)=(x-\lambda)^n Q(x)$, 其中 $Q(\lambda)\neq0$。 我們可以分兩步來求解, 先解方程 $$(A-\lambda)^n u=b,$$ 若它無解, 則原方程無解;若它有解 $u$, 再用求一術求解 $Q(A)v=u$。 注意向量 $u$ 滿足 $$(A-\lambda)^{m+n} u=(A-\lambda)^m((A-\lambda)^nu)=(A-\lambda)^mb=0,$$ 而 $Q(\lambda)\neq0$, 所以可以用求一術解出$Q(A)v=u$的解$v$, 並且它滿足 $(A-\lambda)^n(Q(A)v)=(A-\lambda)^nu=b$, 即 $P(A)v=b$。
綜上可見, 特解之所以能夠產生, 主要是因為, 在最簡單的情況,
$b$ 是 $A$ 的廣義特徵向量(而在更一般的情況, $b$ 是 $A$ 的不同的廣義特徵向量之和)。
例如, 當 $A=D$ 是微分運算元時,
非齊次項 $b$ 是 $D$ 的廣義特徵函數, 即擬多項式(參見前文對定理2的第一個應用)。
參見
第五:
正如求一術可以推廣到求解同餘方程組, 這裡的方法也可以推廣到求解常係數線性微分方程組與常係數線性遞推關係組。
我們只對於常微分方程組的情形, 說明大致思路。
這一點已經為 Bourbaki 寫進他們的實變函數著作, 參見 Bourbaki 設我們考慮的方程組形如 $$AX=b,$$ 其中 $A=(a_{ij})_{m\times n}$, 而每個元素 $a_{ij}=a_{ij}(D)$ 是關於 $t$ 的求導運算元 $D=\frac{\textrm{d}}{\textrm{d}t}$ 的多項式, $b=(f_1,\ldots,f_m)^T$, 各個$ f_i$ 是 $t$ 的已知向量值函數, $X=(x_1(t),\ldots,x_n(t))^T$ 是未知向量值函數。 求解思路如下, 設 $D$ 為未定元 $\lambda$, 將 $A$ 視為多項式環 $R=\mathbb{C}[\lambda]$ 上的矩陣, 根據主理想整環矩陣的一個基本結果 (https://en.wikipedia.org/wiki/Smith_normal_formSmith標準型), 我們知道, 存在可逆矩陣 $P\in GL(m,R), Q\in GL(n,R)$ 使得 $$PAQ=\Lambda=\textrm{diag}[d_1(\lambda),d_2(\lambda), \ldots,d_r(\lambda),0,\ldots,0],$$ 其中 $d_1(\lambda),d_2(\lambda),\ldots,d_r(\lambda)$ 為首一多項式, 且 $d_1(\lambda)\mid d_2(\lambda)\mid\cdots\mid d_r(\lambda)$。 在這個等式中將未定元 $\lambda$ 替換為 $D$, 得到 $$PAQ=\Lambda=\textrm{diag}[d_1(D),d_2(D),\ldots,d_r(D),0,\ldots,0],$$ (其中 $P,A,Q$ 我們用了同一個記號, 以避免符號複雜。)
注意到, 從 $AX=b$ 可以得到方程
$$PAX=Pb,$$
若我們令
$Y=Q^{-1}X$, 則它等價於
$$\Lambda Y=Pb.$$
注意到, 由於 $\Lambda$ 是對角矩陣, 所以上述方程可以變數分離為關於每個
$y_i$ 的方程, 如果這樣的方程我們可以逐一判定它是否可解
(注意到若 $Pb$ 是多項式或擬多項式, 則用 參考文獻---本文作者任教於中國西北農林科技大學--- |