# A Simpler GMRES Method for Oscillatory Integrals with Irregular

Authors: Qinghua Wu; Meiying Xiang
Journal: Advances in Mathematical Physics
 (2015)

---

## Abstract

A simpler GMRES method for computing oscillatory integral is presented. Theoretical analysis shows that this method is mathematically
equivalent to the GMRES method proposed by Olver (2009). Moreover, the simpler GMRES does not require upper Hessenberg matrix factorization, which leads to much simpler program and requires less work. Numerical experiments are conducted to illustrate the performance of the new method and show that in some cases the simpler GMRES method could achieve higher accuracy than GMRES.


---

## Body

## 1. Introduction

In this paper we consider iterative methods for computing high oscillatory integral(1)∫abfxeiwgxdx,where f(x) and g(x) are smooth functions and g′(x)≠0 for x∈(a,b) and nonoscillatory with respect to increasing w. For large values of w, the integrand is highly oscillatory and special integration methods must be used for the evaluation of (1). In the last few years many efficient methods have been devised for approximating this kind of oscillatory integrals, such as asymptotic method [1], Filon-type method [2], Levin’s collocation method [3], modified Clenshaw-Curtis method, Clenshaw-Curtis-Filon-type method [4], generalized quadrature rule [5], and numerical steepest descent method [6]. These methods would improve with accuracy; the larger the frequency of oscillations w, the more the accuracy of the approximations. However, the asymptotic method will not converge for fixed w, which results in the accuracy of approximating an integral being limited. The idea of Filon-type method is to approximate f(x) by polynomial and is only applicable for certain oscillators for which the moments ∫ab‍xkeiωg(x)dx are easily computable, which is not necessarily the case. In many situations the accuracy of the Filon-type method is significantly higher than that of the asymptotic method, even though it is of the same order. To work around this weakness, Xiang [7] derived efficient Filon-type method, an approach without computing the moments. Afterwards, Xiang and Wu used this method to approximate the solutions of Volterra integral equations of the second kind with oscillatory trigonometric kernels in [8]. Also, Olver presented a moment-free method; for details see [9, 10]. Although moment-free Filon-type methods avoid computation of the moments, they are not numerically stable. Due to the requirement for solving an ill-conditioned collocation system, Levin collocation method cannot be used to achieve high asymptotic orders. Numerical steepest descent method achieves a higher asymptotic order than any other method. Sadly, it requires the integrand being analytic and deforming the path of integration into the complex plane, which in practice add complexity to the method.Recently, Olver introduced GMRES and shifted GMRES methods for oscillatory integrals in [11, 12], where convergence condition and some properties of the method were derived. By building an orthogonal basis of Kn(D,f) with respect to the given product ·,·, GMRES methods for differentiation operator turn the original problem(2)Dv=fforf∈C∞Ωto a least-squares problem as follows:(3)Rn=minvn∈KnD,f⁡Dvn-f,where D denotes the differentiation operator and Ω is a set of complex planes.In this paper, we deal with a different approach. We look for an orthogonal basisPn=(p1,…,pn) of DKn(D,f), where problem (3) is reduced to an upper triangular least-squares problem. By theoretical analysis, we show that this method is mathematically equivalent to the GMRES method and has some other properties as those possessed by GMRES but requires less work.The paper is organized as follows. In Section2, the simpler GMRES (S-GMRES) algorithm for differentiation operator is described. In Section 3, an equivalence between S-GMRES and GMRES for differentiation operator is established. In Section 4, numerical experiments are conducted to illustrate the performance of the proposed method.


## 2. Simpler GMRES for Differentiation Operator

Given a differentiation operatorD:C∞(Ω)→C∞(Ω) and the following differential equation:(4)Dv=F,forF∈C∞Ω,where Ω is a set of complex planes, we can find an antiderivative v of a smooth function F∈C∞(Ω) by the idea of GMRES method for finite dimension derived in [13].Specially, for an integral(5)∫abFxdx,once the approximation function v which satisfies (4) is obtained, integral (5) can be approximated by(6)∫abFxdx=vb-va.For convenience, assume that the initial guess of approximationv0=0 and (f/f,p1,…,pn-1) is a basis of Kn(D,f); then an orthogonal basis Pn=(p1,…,pn) of DKn(D,f) is obtained by Arnoldi process for differentiation operator as follows.Algorithm 1 (Arnoldi process for differentiation operator).
(1)
GivenF∈C∞(a,b) and a definition of inner (or semi-inner) product ·,·.
(2)
Compute theρ0=DF, if ρ0=0, then Hn=0 and Pn=0 return; otherwise,
(3)
p
1
=
D
F
/
ρ
0, h1,1=ρ0
(4)
Forj=1,…,n-1
(4.1)
ComputeW=Dpj.
(4.2)
Fori=1,…,j
h
i
,
j
+
1
=
W
,
p
i.
W
=
W
-
h
i
,
j
+
1
p
i.
End For
(4.3)
ComputeW and set hj+1,j+1=W.
(5)
IfW≠0, then pj+1=W/hj+1,j+1; otherwise set pk+1=0; End For
(6)
returnPn=(p1,…,pj+1) and Hn=(hi,j)n×n.Due to the orthogonality propertyRn⊥DKn(D,f), Rn can be computed recursively as(7)Rn=Rn-1-pnsn,where sn=Rn-1,pn.Defineαn=(s1,…,sn)T. Since [f/f,Pn-1] form a basis of Kn(D,f), we can represent vn in the form(8)vn=ff,Pn-1tn,where tn is the “coordinates” of vn with respect to the basis [f/f,Pn-1]. Due to Rn=f-D[f/f,Pn-1]tn, D[f/f,Pn-1]=PnHn, and Rn⊥DKn(D,f), it follows that(9)Untn=αn.Hence, once the residual norm (seminorm) with respect to the given inner (or semiproduct) is small enough, we can solve this upper triangular system (9) and then compute the approximate solution vn=(f/f,Pn-1)αn.


## 3. Convergence Rate

It is well known that equivalence between the simpler GMRES [14] and the GMRES has been established for finite dimension. Analogously, we can formulate the same conclusion in the case of infinite dimension space. The following theorem indicates that S-GMRES is equivalent to GMRES for differentiation operator.Theorem 2.
Suppose thatPn=(p1,p2,…,pn) are obtained by S-GMRES procedure; then we have(10)Kn=span⁡f,f′,…,fn-1=span⁡f,p1,…,pn-1which shows that S-GMRES and GMRES are equivalent.Proof.
We prove the result by induction. Forn=1, q1=f/f; then K1=span{f}, and thus the statement clearly holds.
Now, we assume that the theorem is true forn and try to prove that it also holds for n+1. By using the assumption, we have(11)Kn=span⁡f,f′,…,fn-1=span⁡f,p1,…,pn-1.Then, by Arnoldi process, we have(12)Dpn-1=pnhn,n+∑k=1n-1pkhk,n,and we obtain(13)span⁡f,…,fn-1,fn=span⁡f,p1,…,pn.The statement holds for n+1. Therefore, it completes the proof.Theorem2 indicates that the asymptotic order of S-GMRES method is the same as GMRES method. Let Qn[F] denote the approximation of (1); it was observed in [11] that differential GMRES has an asymptotic order(14)IF-QnF=Own-1,asw⟶∞,with the condition that the kernel of oscillations is a standard Fourier oscillator; that is, g(x)=x. For more general oscillations g(x), Olver showed that the same asymptotic rate can be obtained for shifted GMRES which is a method equivalent to GMRES; for details see [12]. We can expect that the same conclusion can be derived for S-GMRES.Besides asymptotic order, S-GMRES shares some other properties which shifted GMRES possesses such as reuse of the Arnoldi process required by S-GMRES to computeQn[F] for additional values of w and the method is guaranteed to converge for a large class of analytic functions; for details see [12].


## 4. Numerical Examples

In this section, we give some numerical examples to illustrate the efficiency of the proposed methods. When use S-GMRES or GMRES methods, we encounter inner (or semi-inner product)·,·. We use the same semi-inner product ·,· as in [11], which is defined by(15)f,g=∫abfxg¯xdx.For an integral ∫ab‍f(x)eiwg(x)dx, we denote F(x)=f(x)eiwg(x); then the derivative of F(x) can be obtained as follows:(16)F′=f′+iwg′feiwg≔r1eiwg,F2=r1′+iwg′r1eiwg≔r2eiwg,….Thus we can write f1,f2∈Kn[D,F] as q1eiwg and q2eiwg, where q1,q2 are nonoscillatory which indicates that the inner product of these two functions is a nonoscillatory integral and can be easily and efficiently computed by classical quadrature such as Clenshaw-Curtis and Gauss-Kronrod rules.In all the following examples, we plot the absolute error|I[f]-QnN[f]| and use the following discrete semi-inner product defined by(17)p,qN=∑k=1Nwkpxkq¯xk,where (x1,…,xN) and (w1,…,wN) are Clenshaw-Curtis quadrature nodes and weights, respectively. Unless otherwise specified, the exact value of integral is computed by Matlab2012a internal functionintegral.Example 1.
We consider∫01‍((x+1)/(x2+10))eiw(x2+x)dx and set N=10.It is easy to see from Figure1 that both S-GMRES and GMRES methods are converged. There are some differences in the iterates produced by two methods, although both methods are equivalent. We can also see from Figure 1 that these differences are insignificant and two methods share the fact that the higher the frequency the more the accuracy of the approximations.Figure 1
Example1. The absolute error versus the number of iterations for w=100 (a), w=100 (b), and w=1000 (c).
(a)
(b)
(c)Example 2.
In our second experiment, we consider∫01‍cos⁡(x)eiw(x2+x)dx and set N=10.Figure2 shows that S-GMRES method is more accurate than GMRES, although both methods are equivalent. This indicates that S-GMRES methods could achieve higher accuracy than GMRES with less work in some case.Figure 2
Example2. The absolute error versus the number of iterations for w=10 (a), w=100 (b), and w=1000 (c).
(a)
(b)
(c)Example 3.
In our third experiment, we consider∫01‍x3eiwxdx and set N=10.Generally, forβ>-1 (p is a natural number), we have(18)∫0yxβeiωxpdx=1p-iωβ+1/pΓβ+1p-Γβ+1p,-iωyp,which can be computed explicitly by the incomplete Gamma function Γ(z,α) (Abramowitz and Stegun [15, pp 260], Iserles and Nørsett [1, 2]). We will calculate the exact value of integral by (18).Figure3 also shows that S-GMRES method is more accurate than GMRES with less work.Figure 3
Example3. The absolute error versus the number of iterations for w=10 (a), w=100 (b), and w=1000 (c).
(a)
(b)
(c)


## 5. Conclusion

In this paper we have proposed a minimum residual method mathematically equivalent to the GMRES method for computing oscillatory integrals with irregular oscillations. The proposed S-GMRES method shares some properties as those possessed by GMRES, such as guaranteed to converge for a large class of analytic functions. But S-GMRES method does not need the factorization of an upper Hessenberg matrix. Numerical experiments show that in some cases S-GMRES methods could achieve higher accuracy than GMRES; also S-GMRES method possesses the fact that the higher the frequency the more the accuracy of the approximations.



---

*Source: 103074-2015-07-02.xml*