तीव्रतम अवतरण की विधि

For the optimization algorithm, see Gradient descent.

गणित में, तीव्रतम अवतरण की विधि या काठी-बिंदु विधि इंटीग्रल का अनुमान लगाने के लिए लाप्लास की विधि का विस्तार है, जहां स्थिर बिंदु (सैडल बिंदु) के समीप से निकलने के लिए कठोर विमान में समोच्च इंटीग्रल को तीव्रतम अवतरण या स्थिर चरण की दिशा में विकृत किया जाता है। सैडल-पॉइंट सन्निकटन का उपयोग कठोर विमान में इंटीग्रल्स के साथ किया जाता है, जबकि लाप्लास की विधि का उपयोग वास्तविक इंटीग्रल्स के साथ किया जाता है।

अनुमान लगाया जाने वाला इंटीग्रल प्रायः रूप का होता है

$\int _{C}f(z)e^{\lambda g(z)}\,dz,$

जहां C समोच्च है, और λ बड़ा है। तीव्रतम अवतरण की विधि का संस्करण एकीकरण C के समोच्च को नवीन पथ एकीकरण C' में विकृत कर देता है जिससे निम्नलिखित स्थितियाँ बनी रहें:

1. C′ व्युत्पन्न g′(z) के या अधिक शून्य से होकर निकलता है,
2. g(z) का काल्पनिक भाग C′ पर स्थिर है।

तीव्रतम अवतरण की विधि सर्वप्रथम किसके द्वारा प्रकाशित की गई थी? डेबी (1909), जिन्होंने बेसेल फलन का अनुमान लगाने के लिए इसका उपयोग किया और बताया कि यह हाइपरज्यामितीय फलन के विषय में रीमैन (1863) अप्रकाशित नोट में हुआ था। तीव्रतम अवतरण के समोच्च में न्यूनतम गुण होता है, देखें फेडोर्युक (2001) देखें। सीगल (1932) रीमैन के कुछ अन्य अप्रकाशित नोट्स का वर्णन किया, जहां उन्होंने रीमैन-सीगल सूत्र प्राप्त करने के लिए इस विधि का उपयोग किया था।

मूल विचार

तीव्रतम अवतरण की विधि प्रपत्र के कठोर इंटीग्रल का अनुमान लगाने की विधि है

$$I(\lambda )=\int _{C}f(z)e^{\lambda g(z)}\,\mathrm {d} z$$

बड़े के लिए $\lambda \rightarrow \infty$, जहाँ $f(z)$ और $g(z)$, $z$ के विश्लेषणात्मक कार्य हैं। क्योंकि इंटीग्रैंड विश्लेषणात्मक है, रूपरेखा $C$ नये स्वरूप $C'$में इंटीग्रल को परिवर्तित किए बिना विकृत किया जा सकता है। विशेष रूप से, कोई नई रूपरेखा की शोध करता है जिस पर काल्पनिक भाग हो $g(z)={\text{Re}}[g(z)]+i\,{\text{Im}}[g(z)]$ स्थिर है। तब

$$I(\lambda )=e^{i\lambda {\text{Im}}\{g(z)\}}\int _{C'}f(z)e^{\lambda {\text{Re}}\{g(z)\}}\,\mathrm {d} z,$$

और शेष इंटीग्रल का अनुमान लाप्लास की विधि जैसी अन्य विधियों से लगाया जा सकता है।

व्युत्पत्ति

विश्लेषणात्मक $g(z)$ होने के कारण इस विधि को तीव्रतम अवतरण की विधि कहा जाता है, स्थिर चरण समोच्च तीव्रतम अवरोही समोच्चों के समतुल्य हैं।

यदि $g(z)=X(z)+iY(z)$ का विश्लेषणात्मक कार्य$z=x+iy$ है, यह कॉची-रीमैन समीकरण को संतुष्ट करता है

$${\frac {\partial X}{\partial x}}={\frac {\partial Y}{\partial y}}\qquad {\text{and}}\qquad {\frac {\partial X}{\partial y}}=-{\frac {\partial Y}{\partial x}}.$$

तब

$${\frac {\partial X}{\partial x}}{\frac {\partial Y}{\partial x}}+{\frac {\partial X}{\partial y}}{\frac {\partial Y}{\partial y}}=\nabla X\cdot \nabla Y=0,$$

इसलिए स्थिर चरण की आकृतियाँ भी तीव्रतम अवतरण की आकृतियाँ हैं।

साधारण अनुमान

मान लीजिए  f, S : Cⁿ → C और C ⊂ Cⁿ. यदि

$M=\sup _{x\in C}\Re (S(x))<\infty ,$

जहाँ $\Re (\cdot )$ वास्तविक भाग को दर्शाता है, और धनात्मक वास्तविक संख्या λ₀ सम्मिलित है ऐसा है कि

$\int _{C}\left|f(x)e^{\lambda _{0}S(x)}\right|dx<\infty ,$

तो निम्नलिखित अनुमान मान्य है:

$\left|\int _{C}f(x)e^{\lambda S(x)}dx\right|\leqslant {\text{const}}\cdot e^{\lambda M},\qquad \forall \lambda \in \mathbb {R} ,\quad \lambda \geqslant \lambda _{0}.$

सरल अनुमान का प्रमाण:

${\begin{aligned}\left|\int _{C}f(x)e^{\lambda S(x)}dx\right|&\leqslant \int _{C}|f(x)|\left|e^{\lambda S(x)}\right|dx\\&\equiv \int _{C}|f(x)|e^{\lambda M}\left|e^{\lambda _{0}(S(x)-M)}e^{(\lambda -\lambda _{0})(S(x)-M)}\right|dx\\&\leqslant \int _{C}|f(x)|e^{\lambda M}\left|e^{\lambda _{0}(S(x)-M)}\right|dx&&\left|e^{(\lambda -\lambda _{0})(S(x)-M)}\right|\leqslant 1\\&=\underbrace {e^{-\lambda _{0}M}\int _{C}\left|f(x)e^{\lambda _{0}S(x)}\right|dx} _{\text{const}}\cdot e^{\lambda M}.\end{aligned}}$

एकल गैर-क्षतिग्रस्त काठी बिंदु का विषय

मूल धारणाएँ और संकेतन

मान लीजिए x कठोर n-आयामी सदिश है, और

$S''_{xx}(x)\equiv \left({\frac {\partial ^{2}S(x)}{\partial x_{i}\partial x_{j}}}\right),\qquad 1\leqslant i,\,j\leqslant n,$

किसी फलन S(x) के लिए हेस्सियन आव्यूह को निरूपित करें, यदि

${\boldsymbol {\varphi }}(x)=(\varphi _{1}(x),\varphi _{2}(x),\ldots ,\varphi _{k}(x))$

सदिश फलन है, तो इसके जैकोबियन आव्यूह और निर्धारक को इस प्रकार परिभाषित किया गया है,

${\boldsymbol {\varphi }}_{x}'(x)\equiv \left({\frac {\partial \varphi _{i}(x)}{\partial x_{j}}}\right),\qquad 1\leqslant i\leqslant k,\quad 1\leqslant j\leqslant n.$

गैर पतित काठी बिंदु, z⁰ ∈ Cⁿ, होलोमोर्फिक फलन S(z) का महत्वपूर्ण बिंदु है (अर्थात, ∇S(z⁰) = 0) जहां फलन के हेसियन आव्यूह में गैर-लुप्त होने वाला निर्धारक है (अर्थात, $\det S''_{zz}(z^{0})\neq 0$).

गैर-अपक्षयी सैडल बिंदु के विषय में इंटीग्रल के एसिम्प्टोटिक्स के निर्माण के लिए निम्नलिखित मुख्य उपकरण है:

कॉम्प्लेक्स मोर्स लेम्मा

वास्तविक-मूल्यवान फलन के लिए मोर्स सिद्धांत मोर्स लेम्मा निम्नानुसार सामान्यीकृत होता है होलोमोर्फिक फलन के लिए: गैर-पतित काठी बिंदु के निकट z⁰ होलोमोर्फिक फलन S(z) का, जिसके संदर्भ में निर्देशांक सम्मिलित हैं S(z) − S(z⁰) सम्पूर्ण द्विघात है. इसे त्रुटिहीन बनाने के लिए आइए Sडोमेन के साथ होलोमोर्फिक फलन बनें W ⊂ Cⁿ, और जाने z⁰ में W का गैर पतित काठी बिंदु हो S, वह है, ∇S(z⁰) = 0 और $\det S''_{zz}(z^{0})\neq 0$. फिर पड़ोस सम्मिलित हैं U ⊂ W का z⁰ और V ⊂ Cⁿ का w = 0, और वन-टू-वन फलन होलोमोर्फिक फलन φ : V → U साथ φ(0) = z⁰ ऐसा है कि

$\forall w\in V:\qquad S({\boldsymbol {\varphi }}(w))=S(z^{0})+{\frac {1}{2}}\sum _{j=1}^{n}\mu _{j}w_{j}^{2},\quad \det {\boldsymbol {\varphi }}_{w}'(0)=1,$

यहां ही μ_j आव्यूह $S_{zz}''(z^{0})$ के आइगेनवैल्यूज़ एवं आइगेनसदिश्स हैं।

Proof of complex Morse lemma

The following proof is a straightforward generalization of the proof of the real Morse Lemma, which can be found in. We begin by demonstrating

Auxiliary statement. Let  f  : Cⁿ → C be holomorphic in a neighborhood of the origin and  f (0) = 0. Then in some neighborhood, there exist functions g_i : Cⁿ → C such that

$$f(z)=\sum _{i=1}^{n}z_{i}g_{i}(z),$$

where each g_i is holomorphic and

$$g_{i}(0)=\left.{\tfrac {\partial f(z)}{\partial z_{i}}}\right|_{z=0}.$$

From the identity

$f(z)=\int _{0}^{1}{\frac {d}{dt}}f\left(tz_{1},\cdots ,tz_{n}\right)dt=\sum _{i=1}^{n}z_{i}\int _{0}^{1}\left.{\frac {\partial f(z)}{\partial z_{i}}}\right|_{z=(tz_{1},\ldots ,tz_{n})}dt,$

we conclude that

$g_{i}(z)=\int _{0}^{1}\left.{\frac {\partial f(z)}{\partial z_{i}}}\right|_{z=(tz_{1},\ldots ,tz_{n})}dt$

and

$g_{i}(0)=\left.{\frac {\partial f(z)}{\partial z_{i}}}\right|_{z=0}.$

Without loss of generality, we translate the origin to z⁰, such that z⁰ = 0 and S(0) = 0. Using the Auxiliary Statement, we have

$S(z)=\sum _{i=1}^{n}z_{i}g_{i}(z).$

Since the origin is a saddle point,

$\left.{\frac {\partial S(z)}{\partial z_{i}}}\right|_{z=0}=g_{i}(0)=0,$

we can also apply the Auxiliary Statement to the functions g_i(z) and obtain

$S(z)=\sum _{i,j=1}^{n}z_{i}z_{j}h_{ij}(z).$

(1)

Recall that an arbitrary matrix A can be represented as a sum of symmetric A^(s) and anti-symmetric A^(a) matrices,

$A_{ij}=A_{ij}^{(s)}+A_{ij}^{(a)},\qquad A_{ij}^{(s)}={\tfrac {1}{2}}\left(A_{ij}+A_{ji}\right),\qquad A_{ij}^{(a)}={\tfrac {1}{2}}\left(A_{ij}-A_{ji}\right).$

The contraction of any symmetric matrix B with an arbitrary matrix A is

$\sum _{i,j}B_{ij}A_{ij}=\sum _{i,j}B_{ij}A_{ij}^{(s)},$

(2)

i.e., the anti-symmetric component of A does not contribute because

$\sum _{i,j}B_{ij}C_{ij}=\sum _{i,j}B_{ji}C_{ji}=-\sum _{i,j}B_{ij}C_{ij}=0.$

Thus, h_ij(z) in equation (1) can be assumed to be symmetric with respect to the interchange of the indices i and j. Note that

$\left.{\frac {\partial ^{2}S(z)}{\partial z_{i}\partial z_{j}}}\right|_{z=0}=2h_{ij}(0);$

hence, det(h_ij(0)) ≠ 0 because the origin is a non-degenerate saddle point.

Let us show by induction that there are local coordinates u = (u₁, ... u_n), z = ψ(u), 0 = ψ(0), such that

$S({\boldsymbol {\psi }}(u))=\sum _{i=1}^{n}u_{i}^{2}.$

(3)

First, assume that there exist local coordinates y = (y₁, ... y_n), z = φ(y), 0 = φ(0), such that

$S({\boldsymbol {\phi }}(y))=y_{1}^{2}+\cdots +y_{r-1}^{2}+\sum _{i,j=r}^{n}y_{i}y_{j}H_{ij}(y),$

(4)

where H_ij is symmetric due to equation (2). By a linear change of the variables (y_r, ... y_n), we can assure that H_rr(0) ≠ 0. From the chain rule, we have

${\frac {\partial ^{2}S({\boldsymbol {\phi }}(y))}{\partial y_{i}\partial y_{j}}}=\sum _{l,k=1}^{n}\left.{\frac {\partial ^{2}S(z)}{\partial z_{k}\partial z_{l}}}\right|_{z={\boldsymbol {\phi }}(y)}{\frac {\partial \phi _{k}}{\partial y_{i}}}{\frac {\partial \phi _{l}}{\partial y_{j}}}+\sum _{k=1}^{n}\left.{\frac {\partial S(z)}{\partial z_{k}}}\right|_{z={\boldsymbol {\phi }}(y)}{\frac {\partial ^{2}\phi _{k}}{\partial y_{i}\partial y_{j}}}$

Therefore:

$S''_{yy}({\boldsymbol {\phi }}(0))={\boldsymbol {\phi }}'_{y}(0)^{T}S''_{zz}(0){\boldsymbol {\phi }}'_{y}(0),\qquad \det {\boldsymbol {\phi }}'_{y}(0)\neq 0;$

whence,

$0\neq \det S''_{yy}({\boldsymbol {\phi }}(0))=2^{r-1}\det \left(2H_{ij}(0)\right).$

The matrix (H_ij(0)) can be recast in the Jordan normal form: (H_ij(0)) = LJL⁻¹, were L gives the desired non-singular linear transformation and the diagonal of J contains non-zero eigenvalues of (H_ij(0)). If H_ij(0) ≠ 0 then, due to continuity of H_ij(y), it must be also non-vanishing in some neighborhood of the origin. Having introduced ${\tilde {H}}_{ij}(y)=H_{ij}(y)/H_{rr}(y)$, we write

$x_{r}={\sqrt {H_{rr}(y)}}\left(y_{r}+\sum _{j=r+1}^{n}y_{j}{\tilde {H}}_{rj}(y)\right),\qquad x_{j}=y_{j},\quad \forall j\neq r.$