{'fraction_non_alphanumeric': 0.05609962519646959, 'fraction_numerical': 0.018498367791077257, 'mean_word_length': 3.9411589008363204, 'pattern_counts': {'":': 0, '<': 7, '<?xml version=': 0, '>': 23, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 7, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A convergence rates result for an iteratively regularized Gauss-Newton-Halley method in Banach space

The use of second order information on the forward operator often comes at a very moderate additional computational price in the context of parameter identification probems for differential equation models. On the other hand the use of general (non-Hilbert) Banach spaces has recently found much interest due to its usefulness in many applications. This motivates us to extend the second order method previously considered by the author in a Hilbert space setting, (see also Hettlich and Rundell 2000) to a Banach space setting and analyze its convergence. We here show rates results for a particular source condition and different exponents in the formulation of Tikhonov regularization in each step. This includes a complementary result on the (first order) iteratively regularized Gauss-Newton method (IRGNM) in case of a one-homogeneous data misfit term, which corresponds to exact penalization. The results clearly show the possible advantages of using second order information, which get most pronounced in this exact penalization case. Numerical simulations for a coefficient identification problem in an elliptic PDE illustrate the theoretical findings.


Introduction
Identification of parameters in ordinary or partial differential equations by Newton methods usually requires repeated solution of the model equation (the PDE or ODE) and its linearization, since these methods rely on a first order Taylor expansion of the parameter-to-state map. It has already been observed in [9,12] that also higher derivative evaluation for this forward operator typically lead to the same linear differential equation as the one arising for the first order derivative, and only the right hand sides differ. Let us illustrate this by means of two examples. from measurements y = Cu of the state u, where C is some linear operator (e.g., a trace operator in case of boundary measurements). Problems of this kind arise, e.g., in stationary inverse groundwater filtration, as well as in the characterization or nondestructive inspection of (non)linearly elastic or magnetic materials.
Here Ω ⊆ R d , and the functions f : R d+1 → R, g : R 2 → R, h ∈ H 1/2 (∂Ω) are given. Note that linear growth of f, g and monotonicity (uniform one in case of f ) with respect to their second argument allow to show well-posedness of (1) by means of the Lax-Milgram Lemma. Then, using the parameter-to-state map G : (a, c) → u, the forward operator and its derivatives at some point (a, c) in parameter space can be written as F (a, c) = CG(a, c), F (a, c) = CG (a, c), F (a, c) = CG (a, c), where the derivatives of G at (a, c) in certain directions can be recovered as solutions of the same linearized elliptic PDE with different right hand sides: For parameter increments (α, γ), (α,γ) we have that v 1 = G (a, c)(α, γ), v 2 = G (a, c)((α, γ), (α,γ)) solve where and u = G(a, c),ṽ 1 = G (a, c)(α,γ), i.e., the same linear elliptic boundary value problem (2), only with different right hand sides.
Example 2 For modelling time dependent problems, consider the state space model where the dot denotes the time derivative, which includes systems of ODEs but also (thinking of u(t) as an element of a function space over some spatial domain Ω) time dependent PDEs. Given f , u 0 , we seek to identify the paramter c -possibly element of a finite or infinite dimensional Banach space -from measurements y = Cu of the state u, where C is some linear operator. Again, using the parameter-to-state-map G : c → u, the forward operator and its derivatives at some point c in parameter space can be written as with different right hand sides We point out that in these two examples (and many more), evaluating F (c k ) at some iterate c k leads to the same linear problem as evaluating F (c k ), just with some different right hand side. In case of elliptic or parabolic PDEs this means that the stiffness matrix remains unchanged and therefore, once we have done the computations for F (c k ), the additional effort for evaluating F (c k ) can be kept quite moderate, usually much lower than the effort for doing an additional Newton step that requires F (c k+1 ), thus setting up a new stiffness matrix, at some different coefficient c k+1 . This cheap evaluation of the second derivative at the same iterate is just what Halley's method (see [3,7,14] for the well-posed setting) does, which for ill-posed problems in Hilbert spaces can be formulated as follows (the coefficient iterates are now denoted by x δ k instead of c k ): x δ 0 = x 0 for k = 1, 2, . . .
with two a priori fixed sequences (α k ) k∈N , (β k ) k∈N satisfying cf. [12]. In here, F : X → Y is the forward operator in the operator equation formulation of the coefficient identification problem and the superscript δ indicates the presence of noise in the given data y δ , whose deterministic level we assume to be known, i.e., Here we use a fixed reference point x 0 , i.e., the first order version of this method (skipping the step with S k ) would be the iteratively regularized Gauss-Newton method (IRGNM), see, e.g., [1,10,13]. If we would replace x 0 by the current iterate x δ k in each step, we would arrive at the Levenberg-Marquardt type version of Halley's method considered by Hettlich and Rundell in [9]. While [9,12] concentrate on the case of X, Y being Hilbert spaces, it is often desirable to also work in Banach spaces that to not possess Hilbert space structure, such as L 1 or the space of Radon measures for obtaining sparse solutions or modelling impulsive noise, or L ∞ for guaranteeing essential bounds (e.g., nonnegativity) of coefficients or modelling uniform noise, cf., e.g., [5,6,11]. Method (5) can indeed be extended to the more general setting of X, Y being Banach spaces in a straightforward manner: with p, r ∈ [1, ∞). Below we will prove a convergence result under the source condition for some v ∈ X Here J p = ∂ 1 p · p denotes the duality mapping. Our analysis will make use of the shifted Bregman distance which, if X is p-convex, satisfies the coercivity estimate for some constant c > 0 depending on p (see, e.g., [2, Lemma 2.7]). The stopping index k * will be the first one such that α if r > 1. In case r = 1 we can choose β k and α k constant (i.e., the Tikhonov regularization parameter is independent of δ, as typical for this case, see, e.g., [4]) and where σ = p+2 p 2 , which is larger than one for p < 2. We first of all consider the case r > 1. Theorem 1. Let X, Y be Banach spaces with additionally X being p-convex so that (11) holds, where the exponents satisfy Assume that a source condition (10) with v sufficiently small holds. Let F be twice Fréchet differentiable with F bounded and Lipschitz continuous in B ρ (x † ) and let x 0 be suffiently close to x † . Assume that with s > 0, α 0 sufficiently small and (6), and let k * be chosen according to (12) with τ sufficiently large. Then the iterates defined by (9) converge at the rate The case r = 1 corresponding to exact penalization of the data misfit (see, e.g., [4]) is treated separately. Since the existing results on the IRGNM from [10,13] do not seem to be applicable, § we also prove the corresponding result for the IRGNM.
Theorem 2. Let X, Y be Banach spaces with additionally X being p-convex so that (11) holds, where the exponents satisfy 1 ≤ p < 2 and r = 1 .
Assume that a source condition (10) with v sufficiently small holds. Let F be twice Fréchet differentiable with F bounded and Lipschitz continuous in B ρ (x † ) and let x 0 be suffiently close to x † . Assume that for some constants α, β > 0, and let k * be chosen according to (13) with σ = p+2 p 2 > 1. Then the iterates defined by (9) converge at the rate If δ = 0 we have convergence of order σ = p+2 p 2 (i.e., cubic for p = 1). For the iteratively regularized Gauss-Newton method (IRGNM) defined by setting x k+1 = x k+ , under the same assumptions (except the ones on F and on β k , which are not needed) with k * chosen according to (13) with σ = 2 p > 1, the iterates converge at the rate (16). If δ = 0, we have convergence of order σ = 2 p for the IRGNM iterates (i.e., quadratic for p = 1). § note that [13] requires r > 1, whereas in [10], the multiplicative source condition (12) does not contain the case (10) if r = 1 and the additive one (35) with Theorem 4.2 does not give the desired rate in this case Remark 1. The difference between first and second order IRGNM becomes even clearer here than in the Hilbert space case with quadratic penalties from [12], especially in the case r = 1 of Theorem 2: In the exact data case, the order of convergence is always better for Halley than for IRGNM, since which becomes most obvious in the case p = 1, where we get cubic convergence for Halley's method and quadratic one for the IRGNM. This faster convergence is also reflected in the number of iterates according to (13) in case of noisy data, since the logarithm in (13) is taken with respect to a larger basis for Halley than for IRGNM.

Proof of Theorems 1, 2
By minimality in the definition (9) of the iterates we have On the other hand, we use the fact that by definition of the Bregman distance and the source condition (10) in both cases we have Note that (up to a linearization error) we have so we will correspondingly dominate the term κ v T (x − x † ) from (18) by a small multiple of T (x − x † ) r , which is obvious in case r = 1 with the smallness assumption and for r ∈ (1, ∞) follows from Young's inequality in the form with r * = r r − 1 , C( , r) = r − 1 1/(r−1) r r * setting = 2 −r /r, a = T (x − x † ) , b = κ v . Putting these estimates together and using the simple inequalities (a − b) r + b r ≥ 2 −(r−1) a r , (a + b) r ≤ 2 r−1 (a r + b r ) we obtain two estimates of the form where 0 < c 0 < 2 −(r−1) and the term v r * κ r * vanishes (also formally, by κ v < 1) in case r = 1, hence for some constants c 1 , C 1 > 0 depending only on q. The approximations in (19) can be quantified by the Taylor remainder estimates Hence we end up with and with some constants c, C > 0 depending only on q, C 2 , L 2 . Thus, using the coercivity estimate (11) and considering first of all the case r > 1, we expected to obtain the rates and hence consider the quantities for which, dividing by β r * k and α r * k+1 , respectively, from (21), (22), (11) and the stopping rule (cf. (12)) we obtain, for k ≤ k * − 1 Since the sequences α k , β k tend to zero, the desired boundedness of the right hand side imposes some restrictions to the exponents. Namely, in view of term VI in (26) we need and from terms I, II, IV, using the fact that by (27) 1 p−1 ≥ 2 p we infer condition for some m, M > 0 independent of k. For instance, β k = sα k with some s > 0 is an admissible choice satisfying (28), and settingτ = s and where we have imposed the bound We wish to carry out an induction proof of the claim (for all k ∈ N 0 in case δ = 0) with appropriately chosen constantsγ,Γ > 0. For this purpose, it suffices to do the induction step, since the induction beginning can be easily established by imposing the closeness condition x δ 0 − x † ≤γα 1 p(r−1) 0 and using the convention Γ 0 = 0. The induction step can be carried out by means of the following Lemma Lemma 1. Let φ, Φ be defined as in (29), (30) with Then there existγ,Γ such that for d, e, f, h, j > 0 sufficiently small the implication ∀γ, Γ > 0 : Γ p ≤ φ(γ, Γ) and γ p ≤ Φ(γ, γ, Γ) ⇒ Γ ≤Γ and γ ≤γ holds.
Proof. see the Appendix.
Note that indeed d can be made small by imposing v small and choosing τ large; e, f, h, j can be made small by choosing β k = sα k with s small, i.e., (14). Also note that the choice of all bounds in this lemma is independent of δ and of k.
Thus we have established (32). This immediately implies the claimed rate in the exact data case. The stopping rule (12) then implies the rate x δ k * − x † = O(δ 1 p ) in case of noisy data.
Finally, we consider the special case r = 1 where (21), (22) with the coercivity estimate (11) becomes and In case p > 1, the elementary estimate (20) with p instead of r and = 1, a = and similarly where we have used α k ≥ α, β k ≥ β. If p = 1, we have and Inserting (35) into (36) and (37) into (38) we conclude that withĈ sufficiently large and provided µ k remains below some sufficiently small boundμ > 0 (which will be guaranteed inductively by Lemma 2 under smallness conditions on µ 0 = x 0 − x † and on δ) such that in case p = 1, sc − Cμ > 0, c − C μ 2 +μ + C sc−Cμ δ +μ 2 > 0. The requirement σ > 1 resulting from the need of proving boundedness of µ k+1 according to (39) with possibly largeĈ translates to the condition p < 2. Now we make use of an elementary consequence of the recursion (39).
So by setting k = k * − 1 according to (13) we get i.e., the stated convergence rate with noisy data. If δ = 0 then (39) directly provides us with convergence of µ k to zero with convergence order σ.
In the same manner the respective convergence result for the IRGNM in case r = 1 can be seen: Namely, since the IRGNM corresponds to setting x k+1 = x k+ , by (35), (37) we have The requirementσ > 1 again translates to p < 2, which entails that in factσ = 2 p and Lemma 2 yields the claimed result.

Numerical experiments
We now show results of numerical tests with a Matlab implementation of method (9) for the test example of identifying c in c] , so that Υ ∈ W 2,∞ (R) and for the potential Υ(c) nonnegativity and p-integrability is guaranteed if c ∈ L p (Ω): For the forward operator F = C • G with G : L p (Ω) → W 2,p (Ω) and C : W 2,p (Ω) → Z some linear observation operator mapping in to some Banach space Twice differentiability and Lipschitz continuity of F can be shown analogously to Example 3.1 in [8], see also Example 2 in [12]. Numerical tests are here done for f ≡ 4000, g ≡ 10, and as starting value we use c 0 ≡ 1. A comparison with the IRGNM for this example has been carried out in the Hilbert space setting of [12]. Here we consider non-Gaussian noise and compare performance of the Hilbert space version of Halley's method with the formulation in appropriate Banach spaces. It is well-known that L 1 data misfit terms are better suited than the L 2 norm in case of impulsive noise. This can be seen also here in our tests with Y = L 1.1 , r = 1.1 as compared to Y = L 2 , r = 2 ( Figure 1). Here the noise was generated by randomly (uniformly distributed) picking measurement points and perturbing their values by an amount of ten per cent of the maximal measurement value. Note that the ideal choice Y = L 1 is admissible by our theory but would make the subproblems in each Halley step nonsmooth, which would require more sophisticated numerical techniques, (see, e.g., [5]) than what we have implemented for our tests. Using L 1+ with > 0 may be viewed as a smooth approximation to the computationally hard case of L 1 or the space of Radon measures, cf. [15].

Conclusions and remarks
In this paper we have extended the IRGNM-Halley method from [12] to the general Banach space setting with possibly nonquadratic penalties and proven convergence rates under a particular source condition and with a priori regularization parameter choice for a variety of exponents in the data misfit and regularization terms.
More general convergence rates, including convergence without rates, have yet to be shown. Such results might be obtained using approximate or variational source conditions. As soon as (10) is violated, certainly stronger structural assumptions on F will be needed to still establish convergence. It is not yet clear, though, how such conditions should be formulated to enable convergence proofs and still be satisfied for relevant applications. In [9] a tangential cone type condition was successfully used for proving convergence without source conditions. However, for the Levenberg-Marquardt type approach taken there, a monotonicity argument can be used, which does not apply to the IRGNM-type version considered here. In the Hilbert space setting of [12], we have proven convergence without (or with weaker) source conditions under a range invariance condition on F , F , (which is in some sense dual to the tangential cone condition). However, it is not yet clear how to carry out proofs under such conditions in a Banach space setting, where the classical Hilbert space spectral calculus is not available. Even for the first order version, i.e., the original IRGNM, this has yet to be done in non-Hilbert spaces.