Loading [MathJax]/jax/output/SVG/jax.js
Research article Special Issues

On maximum residual block Kaczmarz method for solving large consistent linear systems

  • Received: 25 September 2024 Revised: 21 November 2024 Accepted: 25 November 2024 Published: 28 November 2024
  • MSC : 65F10, 65F20

  • In this paper, we propose two block variants of the Kaczmarz method for solving large-scale consistent linear equations Ax=b. The first method, named the maximum residual block Kaczmarz (denoted as MRBK) method, first partitions the coefficient matrix, and then captures the largest block in the residual vector during each block iteration to ensure that it is eliminated first. Simultaneously, in order to avoid the pseudo-inverse calculation of the MRBK method during block iteration and improve the convergence speed, we further propose the maximum residual average block Kaczmarz method. This method completes the iterative process by projecting the current solution vector onto each row of the constrained subset of the matrix A and averaging it with different extrapolation steps. We analyze and prove the deterministic convergence of both methods. Numerical experiments validate our theory and show that our proposed methods are superior to some other block Kaczmarz methods.

    Citation: Wen-Ning Sun, Mei Qin. On maximum residual block Kaczmarz method for solving large consistent linear systems[J]. AIMS Mathematics, 2024, 9(12): 33843-33860. doi: 10.3934/math.20241614

    Related Papers:

    [1] Xiulin Hu, Lei Wang . Positive solutions to integral boundary value problems for singular delay fractional differential equations. AIMS Mathematics, 2023, 8(11): 25550-25563. doi: 10.3934/math.20231304
    [2] Changlong Yu, Jufang Wang, Huode Han, Jing Li . Positive solutions of IBVPs for q-difference equations with p-Laplacian on infinite interval. AIMS Mathematics, 2021, 6(8): 8404-8414. doi: 10.3934/math.2021487
    [3] Yitao Yang, Dehong Ji . Properties of positive solutions for a fractional boundary value problem involving fractional derivative with respect to another function. AIMS Mathematics, 2020, 5(6): 7359-7371. doi: 10.3934/math.2020471
    [4] Jiaqi Xu, Chunyan Xue . Uniqueness and existence of positive periodic solutions of functional differential equations. AIMS Mathematics, 2023, 8(1): 676-690. doi: 10.3934/math.2023032
    [5] Limin Guo, Jiafa Xu, Donal O'Regan . Positive radial solutions for a boundary value problem associated to a system of elliptic equations with semipositone nonlinearities. AIMS Mathematics, 2023, 8(1): 1072-1089. doi: 10.3934/math.2023053
    [6] Zhiqian He, Liangying Miao . Uniqueness and multiplicity of positive solutions for one-dimensional prescribed mean curvature equation in Minkowski space. AIMS Mathematics, 2020, 5(4): 3840-3850. doi: 10.3934/math.2020249
    [7] Mouataz Billah Mesmouli, Taher S. Hassan . On the positive solutions for IBVP of conformable differential equations. AIMS Mathematics, 2023, 8(10): 24740-24750. doi: 10.3934/math.20231261
    [8] Godwin Amechi Okeke, Akanimo Victor Udo, Rubayyi T. Alqahtani, Melike Kaplan, W. Eltayeb Ahmed . A novel iterative scheme for solving delay differential equations and third order boundary value problems via Green's functions. AIMS Mathematics, 2024, 9(3): 6468-6498. doi: 10.3934/math.2024315
    [9] Limin Guo, Lishan Liu, Ying Wang . Maximal and minimal iterative positive solutions for p-Laplacian Hadamard fractional differential equations with the derivative term contained in the nonlinear term. AIMS Mathematics, 2021, 6(11): 12583-12598. doi: 10.3934/math.2021725
    [10] Xiaoxin Zuo, Weibing Wang . Existence of solutions for fractional differential equation with periodic boundary condition. AIMS Mathematics, 2022, 7(4): 6619-6633. doi: 10.3934/math.2022369
  • In this paper, we propose two block variants of the Kaczmarz method for solving large-scale consistent linear equations Ax=b. The first method, named the maximum residual block Kaczmarz (denoted as MRBK) method, first partitions the coefficient matrix, and then captures the largest block in the residual vector during each block iteration to ensure that it is eliminated first. Simultaneously, in order to avoid the pseudo-inverse calculation of the MRBK method during block iteration and improve the convergence speed, we further propose the maximum residual average block Kaczmarz method. This method completes the iterative process by projecting the current solution vector onto each row of the constrained subset of the matrix A and averaging it with different extrapolation steps. We analyze and prove the deterministic convergence of both methods. Numerical experiments validate our theory and show that our proposed methods are superior to some other block Kaczmarz methods.



    In this manuscript we discuss the existence of multiple non-negative solutions of the boundary value problem (BVP)

    {(p(t)u(t))+f(t,u(t))=0, t0,αu(0)βu(0)=H[u], u(+)=0, (1.1)

    where p,f are continuous functions on their domains with p>0, α>0, β0 and R>0 exists such that f(t,v)0 for (t,v)[0,R]×[0,). Further, H is a suitable functional on the space C[0,R]. No sign condition is assumed on f for t>R.

    The functional formulation of the boundary conditions (BCs) in (1.1) covers, as special cases, the interesting setting of (not necessarily linear) multi-point and integral BCs. A wide literature has been devoted on this topic; for the case of the bounded intervals we refer the reader to the recent paper [11] and references therein. Nonlocal BCs have also received attention in the case of unbounded intervals, one example is the paper [22] where the case β=0 and H[u]=u(ξ) (ξ(0,R]) has been investigated by means of a fixed point theorem of Leggett–Williams type. The case β=0 and H[u]=m2i=1ηiu(ξi) (ξi(0,R]) has been studied, for instance, in [16] for a differential equation with a different linear part in (1.1), by means of the well-known Krasnosel'skiĭ-Guo theorem on cone-compressions and cone-expansions. The approach in [16,22] is to rewrite the BVP into an integral equation of Hammerstein type on the half-line, and this approach is possible due to the linearity of the BCs considered. Our methodology to solve the BVP (1.1) is different, and fits within the line of the papers [7,8,10,20,21]. It consists in considering two auxiliary BVPs separately, the first one on the compact interval [0,R], where the functional BC acts and f is nonnegative, and the second one on the half-line [R,), where f is allowed to change its sign. Unlike the above cited articles, in which the problem of gluing the solutions is solved with some continuity arguments and an analysis in the phase space, here both the auxiliary problems have the same slope condition in the junction point (namely the condition u(R)=0), which simplifies the arguments. This kind of decomposition is some sort of an analogue of one employed by Boucherif and Precup [2] utilized for equations with nonlocal initial conditions, where the associated nonlinear integral operator is decomposed into two parts, one of Fredholm-type (that takes into account the functional conditions) and another one of Volterra-type.

    We make the following assumptions on the terms that occur in (1.1).

    p:[0,+)(0,+) is continuous, with

    P=+R1p(t)dt<+. (1.2)

    f:[0,+)×[0,+)R is continuous, with f(t,v)0 for (t,v)[0,R]×[0,+), f(t,0)=0 for t0.

    ● There exist two continuous functions b1,b2:[R,+)R, with b20, and two nondecreasing C1-functions F1,F2:[0,+)[0,+), with Fj(0)=0, Fj(v)>0 for v>0, j=1,2, such that

    b1(t)F1(v)f(t,v)b2(t)F2(v),for all (t,v)[R,+)×[0,+). (1.3)

    ● For j=1,2

    lim supv0+Fj(v)v<+. (1.4)

    ● Let b1,b+1 be the negative and the positive part of b1, i.e. b1(t)=max{0,b1(t)}, b+1(t)=max{0,b1(t)}. Then

    B1=+Rb1(t)dt<+, (1.5)
    +R1p(t)tRb+1(s)dsdt=+. (1.6)

    Notice that (1.2), (1.6) imply

    Rb+1(t)dt=+,

    and, in particular, the function b1 cannot be negative in a neighbourhood of infinity.

    If (1.6) is not satisfied, then (1.1) may have no solution, since it may happen that no positive solution of the equation in (1.1), satisfying the functional boundary conditions, tends to zero as t tends to infinity. This happens, for instance, if f(t,u)0 for all (t,u)[R,+)×R (i.e., b+1=b2=0) and u(R)0, in which case all positive solutions are nondecreasing. However, as we will show in Section 3 (see also Theorem 4.1), when the condition (1.6) is not satisfied, then our approach leads to sufficient conditions for the existence of a bounded non-negative solution of the differential equation in (1.1), namely a solution of the problem

    {(p(t)u(t))+f(t,u(t))=0, t0,αu(0)βu(0)=H[u], u0 and bounded on [0,+). (1.7)

    The problem of the existence and multiplicity of the solutions for the equation in (1.1), which are non-negative in the interval [0,R] and satisfy the functional BCs and the additional assumptions at u(R)=0, is considered in Section 2 and is solved by means of the classical fixed point index for compact maps. A BVP on [R,+) is examined in Section 3, where we deal with the existence of positive global solutions which have zero initial slope and are bounded or tend to zero at infinity. This second problem is solved by using a fixed point theorem for operators defined in a Frechét space, by a Schauder's linearization device, see [5,Theorem 1.3], and does not require the explicit form of the fixed point operator, but only some a-priori bounds. These estimates are obtained using some properties of principal and nonprincipal solutions of auxiliary second-order linear equations, see [15,Chapter 11] and [9]. Finally, the existence and multiplicity of solutions for the BVP (1.1) and (1.7) is obtained in Section 4, thanks to the fact that the problem in [R,+) has at least a solution for every initial value u(R) sufficiently small. A couple of examples completes the paper, illustrating our two main results.

    In this Section we investigate the existence of multiple positive solutions of the BVP

    {(p(t)u(t))+f(t,u(t))=0, t[0,R],αu(0)βu(0)=H[u], u(R)=0. (2.1)

    First of all we recall some results regarding the linear BVP

    {(p(t)u(t))=0,t[0,R],αu(0)βu(0)=0, u(R)=0. (2.2)

    It is known, see for example [19], that the Green's function k for the BVP (2.2) is given by

    k(t,s):=1α{βp(0)+αs01p(μ)dμ,st,βp(0)+αt01p(μ)dμ, st.

    and satisfies the inequality (see [19,Lemma 2.1])

    c(t)Φ(s)k(t,s)Φ(s), (t,s)[0,R]2,

    where

    Φ(s):=βαp(0)+s01p(μ)dμ, and c(t):=βp(0)+αt01p(μ)dμβp(0)+αR01p(μ)dμ. (2.3)

    Note that the constant function 1α solves the BVP

    {(p(t)u(t))=0,t[0,R],αu(0)βu(0)=1, u(R)=0.

    We associate to the BVP (2.1) the perturbed Hammerstein integral equation

    u(t)=Fu(t)+H[u]α:=Tu(t), (2.4)

    where

    Fu(t):=R0k(t,s)f(s,u(s))ds.

    We seek fixed points of the operator T in a suitable cone of the space of continuous functions C[0,R], endowed with the usual norm w:=max{|w(t)|,t[0,R]}.

    We recall that a cone K in a Banach space X is a closed convex set such that λxK for xK and λ0 and K(K)={0}. In the following Proposition we recall the main properties of the classical fixed point index for compact maps, for more details see [1,12]. In what follows the closure and the boundary of subsets of a cone K are understood to be relative to K.

    Proposition 2.1. Let X be a real Banach space and let KX be a cone. Let D be an open bounded set of X with 0DK and ¯DKK, where DK=DK. Assume that T:¯DKK is a compact operator such that xTx for xDK. Then the fixed point index iK(T,DK) has the following properties:

    (i) If there exists eK{0} such that xTx+λe for all xDK and all λ>0, then iK(T,DK)=0.

    (iii) If Txλx for all xDK and all λ>1, then iK(T,DK)=1.

    (iv) Let D1 be open bounded in X such that ¯D1KDK. If iK(T,DK)=1 and iK(T,D1K)=0, then T has a fixed point in DK¯D1K. The same holds if iK(T,DK)=0 and iK(T,D1K)=1.

    The assumptions above allow us to work in the cone

    K:={uC[0,R]:u0,mint[a,b]u(t)cu}, (2.5)

    a type of cone firstly used by Krasnosel'skiĭ, see [17], and D. Guo, see e.g. [12]. In (2.5) [a,b] is a suitable subinterval of [0,R] and c:=mint[a,b]c(t), with c(t) given by (2.3). We have freedom of choice of [a,b], with the restriction a>0 when β=0. Note also that the constant function equal to r0 (that we denote, with abuse of notation r) belongs to K, so K{0}.

    Regarding the functional H we assume that

    H:K[0,+) is continuous and maps bounded sets in bounded sets.

    With these ingredients it is routine to show that T leaves K invariant and is compact. We make use of the following open bounded set (relative to K)

    Kρ:={uK:u<ρ}.

    We now employ some local upper and lower estimates for the functional H, in the spirit of [13,14]. We begin with a condition which implies that the index is 1.

    Lemma 2.2. Assume that

    (I1ρ) there exists ρ>0, such that the following algebraic inequality holds:

    1m¯fρ+1α¯Hρ<ρ, (2.6)

    where

    ¯fρ:=max(t,u)[0,R]×[0,ρ]f(t,u), ¯Hρ:=supuKρH[u]  and 1m:=supt[0,R]R0k(t,s)ds.

    Then iK(T,Kρ) is 1.

    Proof. Note that if uKρ then we have 0u(t)ρ for every t[0,R]. We prove that μuTu for every μ1 and uKρ. In fact, if this does not happen, there exist μ1 and uKρ such that, for every t[0,R], we have

    μu(t)=Tu(t)=Fu(t)+1αH[u].

    Then we obtain, for t[0,R],

    μu(t)R0k(t,s)¯fρds+1α¯Hρ1m¯fρ+1α¯Hρ. (2.7)

    Taking the supremum for t[0,R] in (2.7) and using the inequality (2.6) we obtain μρ<ρ, a contradiction that proves the result.

    Now we give a condition which implies that the index is 0 on the set Kρ.

    Lemma 2.3. Assume that

    (I0ρ) there exists ρ>0 such that the following algebraic inequality holds:

    1Mf_ρ+1αH_ρ[u]>ρ, (2.8)

    where

    f_ρ:=min(t,u)[a,b]×[cρ,ρ]f(t,u), H_ρ:=infuKρH[u]  and 1M:=inft[a,b]bak(t,s)ds.

    Then iK(T,Kρ) is 0.

    Proof. Note that the constant function 1 belongs to K. We prove that uTu+λ1 for every uKρ and for every λ0. If this is false, there exist uKρ and λ0 such that u=Tu+λ1. Then we have, for t[a,b],

    ρu(t)=Fu(t)+1αH[u]+λ1Fu(t)+1αH[u]bak(t,s)f(s,u(s))ds+1αH[u]bak(t,s)f_ρds+1αH_ρ[u]1Mf_ρ+1αH_ρ[u]. (2.9)

    Using the inequality (2.8) in (2.9) we obtain ρ>ρ, a contradiction that proves the result.

    In view of the Lemmas above, we may state our result regarding the existence of one or more nontrivial solutions. Here, for brevity, we provide sufficient conditions for the existence of one, two or three solutions. It is possible to obtain more solutions, by adding more conditions of the same type, see for example [18].

    Theorem 2.4. The BVP (2.1) has at least one non-negative solution u1, with ρ1<u1(R)<ρ2 if either of the following conditions holds.

    (S1) There exist ρ1,ρ2(0,+) with ρ1<ρ2 such that (I0ρ1) and (I1ρ2) hold.

    (S2) There exist ρ1,ρ2(0,+) with ρ1<ρ2 such that (I1ρ1) and (I0ρ2) hold.

    The BVP (2.1) has at least two non-negative solutions u1 and u2, with ρ1<u1(R)<ρ2<u2(R)<ρ3, if either of the following conditions holds.

    (S3) There exist ρ1,ρ2,ρ3(0,+) with ρ1<ρ2<ρ3 such that (I0ρ1),(I1ρ2)and(I0ρ3) hold.

    (S4) There exist ρ1,ρ2,ρ3(0,+) with ρ1<ρ2<ρ3 such that (I1ρ1),(I0ρ2)and(I1ρ3) hold.

    The BVP (2.1) has at least three non-negative solutions u1, u2 and u3, with ρ1<u1(R)<ρ2<u2(R)<ρ3<u3(R)<ρ4 if either of the following conditions holds.

    (S5) There exist ρ1,ρ2,ρ3,ρ4(0,+) with ρ1<ρ2<ρ3<ρ4 such that (I0ρ1),(I1ρ2),(I0ρ3) and (I1ρ4) hold.

    (S6) There exist ρ1,ρ2,ρ3,ρ4(0,+) with ρ1<ρ2<ρ3<ρ4 such that (I1ρ1),(I0ρ2),(I1ρ3) and (I0ρ4) hold.

    Proof. Assume condition (S1) holds, then, by Lemma 2.3, we have iK(T,Kρ1)=0 and, by Lemma 2.2, iK(T,Kρ2)=1. By Proposition 2.1 we obtain a solution u1 for the integral equation (2.4) in Kρ2¯Kρ1. Furthermore note that

    tk(t,s):=1α{0, s<t,1p(t), s>t,

    and therefore u10 in [0,R], which, in turn, implies u1(R)=u1.

    Assume now that condition (S3) holds, then we obtain in addition that iK(T,Kρ3)=0. By Proposition 2.1 we obtain the existence of a second solution u2 of the integral equation (2.4) in Kρ3¯Kρ2. A similar argument as above holds for the monotonicity of u2.

    The remaining cases are dealt with in a similar way.

    In this section we state sufficient conditions for the existence of solutions of the following BVP

    (p(t)u(t))+f(t,u(t))=0, tR, (3.1)
    u(R)=0,u(R)=u0,u(t)>0,limtu(t)=0, (3.2)

    where u0>0 is a given constant. The BVP (3.1), (3.2) involves both initial and asymptotic conditions, and a global condition (i.e., the positivity on the whole half-line). The continuability at infinity of solutions of (3.1) is not a simple problem, see for example [4]. For instance, the Emden–Fowler equation

    (p(t)u(t))+g(t)|u(t)|βsgn(u(t))=0, (3.3)

    if β>1 and g is allowed to take negative values, has solutions which tend to infinity in finite time, see [3,4]. Moreover, again in the superlinear case β>1, if g is non-negative with isolated zeros, then (3.3) may have solutions which change sign infinitely many times in the left neighborhood of some ˉt>R, and so these solutions are not continuable to infinity, see [6]. Further, even if global solutions exist (that is, solutions which are defined in the whole half-line [R,+)), their positivity is not guaranteed in general. Indeed, (3.1) may exhibit the coexistence of nonoscillatory and oscillatory solutions; further, nonoscillatory solutions may have an arbitrary large number of zeros.

    The problem (3.1), (3.2) has been consider in [9] for nonlinear equations with p-laplacian operator and nonlinear term f(t,u(t))=b(t)F(u(t)). We address the reader to such a paper for a complete discussion on the issues related to the BVP (3.1), (3.2) and for a review of the existing literature on related problems. The approach used in [9] to solve the BVP was based on a combination of the Schauder's (half)-linearization device, a fixed point result in the Fréchet space of continuous functions on [R,+), and comparison results for principal and nonprincipal solutions of suitable auxiliary half-linear equations, which allow to find good upper and lower bounds for the solutions of the (half)-linearized problem. The same approach, with minor modifications, allow us to treat also the present case with a general nonlinearity f(t,u(t)), under the assumptions (1.3), (1.4). In the following Proposition we recall the fixed-point result [9,Theorem 1], based on [5,Theorem 1.3], in the form suitable for the present problem.

    Proposition 3.1. Let J=[t0,). Consider the BVP

    {(p(t)u)+f(t,u)=0,tJ,uS, (3.4)

    where f is a continuous function on J×R and S is a subset of C1(J,R). Let g be a continuous function on J×R2 such that

    g(t,c,c)=f(t,c)for all(t,c)J×R,

    and assume that there exist a closed convex subset Ω of C1(J,R) and a bounded closed subset S1 of SΩ which make the problem

    {(p(t)y)+g(t,y,q)=0,tJ,yS1 (3.5)

    uniquely solvable for all qΩ. Then the BVP (3.4) has at least one solution in Ω.

    In view of this result, no topological properties of the fixed-point operator are needed to be checked, since they are a direct consequence of a-priori bounds for the solutions of the "linearized" problem (3.5).

    We state here the existence results in the form which will be used in the next section, addressing to [9,Theorem 2] for the general result, in case of a factored nonlinearity. For reader's convenience we provide a short proof, focusing only on those points which require some adjustments due to the more general nonlinearity. We point out that the present results are obtained by using the Euler equation

    t2y+nty+(n12)2y=0,n>1, (3.6)

    as a Sturm majorant of the linearized auxiliary equation (see also [9,Corollary 3]), but any other linear equation having a positive decreasing solution can be used as a majorant equation, obtaining different conditions. The first result states sufficient conditions for the existence of a global positive solution of (3.1), bounded on [R,+).

    Theorem 3.2. Assume that (1.2)–(1.5) hold, and let

    Mj(d)=supv(0,d]Fj(v)v,j=1,2

    where d>0 is a fixed constant. If

    B1log2M1(d)P, (3.7)

    and

    p(t)tn,b2(t)(n1)24M2(d)tn2,for alltR, (3.8)

    for some n>1, then for every u0(0,d/2] the equation (3.1) has a solution u, satisfying u(R)=u0,u(R)=0,0<u(t)2u0 for tR.

    Proof. The result follows from [9,Theorem 2 and Corollary 3], with some technical adjustments due to the actual general form of the nonlinearity. Indeed, it is sufficient to observe that, for every continuous function q:[R,)(0,d] fixed, the equations

    (p(t)w(t))M1(d)b1(t)w(t)=0 (3.9)

    is a Sturm minorant of the linearized equation

    (p(t)u(t))+f(t,q(t))q(t)u(t)=0, (3.10)

    and (3.6) is a Sturm majorant, due to (3.8) (see for instance [15]). Since (3.6) is nonoscillatory, and has the solution y(t)=t(n1)/2, which is positive decreasing on [R,+), from [9,Lemma 3] the solution of (3.10) satisfying the initial conditions u(R)=u0, u(R)=0 exists and is positive on [R,+), since it satisfies u(t)w0(t) for all tR, where w0 is the principal solution of (3.9). Further, double integration of (3.10) on [R,t], t>R, gives

    U(t)u0+M1(d)B1tRU(s)p(s)ds, where U(t)=maxs[R,t]u(s),

    and the Gronwall lemma, together with (3.7), gives the upper bound u(t)U(t)2u0. Thus, put

    S={qC1[t0,):q(R)=u0, q(R)=0, q(t)>0 for tR},Ω={qC1[1,):q(R)=u0,q(R)=0,w0(t)q(t)2u0}.

    We have SΩ=Ω and the set S1=¯T(Ω), where T is the operator which maps every qΩ into the unique solution of (3.10) satisfying the initial conditions u(R)=u0, u(R)=0, satisfies S1SΩ=Ω and is bounded in C1[R,+) (for the detailed proof see [9,Theorem 2]). Then Proposition 3.1 can be applied, and the existence of a solution of (3.1) in the set SΩ is proved.

    Remark 3.3. Clearly, the result in Theorem 3.2 holds also if we allow a different upper bound for the solution. More precisely, if we look for a solution satisfying 0<u(t)ku0 with k>1, then it is sufficient to put logk instead of log2 in (3.7), and we get the existence of global positive solutions of the Cauchy problem associated with (3.1), for every u0 such that 0<ku0d.

    Remark 3.4. Since M2(d) is nondecreasing, condition (3.7) can be seen as an upper bound for the values of u0 for which (3.1) has a global bounded solution. For instance, if F1(v)=vβ, β>1, then M1(d)=dβ1 and (3.7) can be read as

    2u0(log2PB1)1β1ifB10,

    while, if F1(v)=v, then M1(d)=1 for all d>0, and (3.1), (3.2) has solution for all u0>0, provided (3.8) is satisfied.

    If in the statement of Theorem 3.2 we assume in addition the condition (1.6), we get the existence of a solution of the BVP (3.1), (3.2).

    Theorem 3.5. Assume that (1.2)–(1.6) hold, and that d>0 exists such that (3.7) and (3.8) are satisfied for some n>1. Then, for every u0(0,d/2], the BVP (3.1), (3.2) has at least a solution u, satisfying

    0<u(t)2u0fort[R,), u(t)<0for larget.

    Proof. The proof is analogous to the second part of the proof of [9,Theorem 2], with obvious modifications due to the more general form of the nonlinear term here considered. In particular notice that (3.1) with conditions (1.3) gives the inequality

    (p(t)u(t))F1(u(t))+b1(t)0

    for every positive solution u of (3.1) and all tR. Thus the arguments in the proof of [9,Theorem 2] apply also to the present case.

    We conclude this Section pointing out that the case b1(t)0 for tR is included in the previous results, and in this case Theorems 3.2, 3.5 have a more simple statement. Indeed, B1=0, and therefore (1.5) and (3.7) are trivially satisfied. Further, every solution of (3.1) is nonincreasing on the whole half-line.

    Combining Theorems 2.4 and 3.2 or 2.4 and 3.5, we obtain an existence result for one or more solutions of the BVP (3.1) and (3.2), respectively. We limit ourself to state results for the existence of one or two solutions, for sake of simplicity. Clearly, as pointed out in Section 2, adding more conditions, with similar arguments it is possible to obtain sufficient conditions for the existence of three solutions (see Theorem 2.4) or more solutions.

    Theorem 4.1. Suppose that (1.2)–(1.5) are satisfied, and that there exist ρ1,ρ2(0,+), with ρ1<ρ2, such that either (S1) or (S2) holds. If n>1 exists, such that (3.7), (3.8) are satisfied with d=2ρ2, then the BVP (1.7) has at least one solution u1, with u1(t)2ρ2 for all t0.

    If, in addition, there exists ρ3(0,+), with ρ2<ρ3, such that either (S3) or (S4) holds, and (3.7), (3.8) are satisfied with d=2ρ3, then the BVP (1.7) has an additional solution u2, with u2(t)2ρ3.

    Notice that, from Theorem 2.4, the solutions u1,u2 satisfy ρ1<u1(R)<ρ2<u2(R)<ρ3 and therefore they are distinct solutions. Further, since solutions on [0,R] are increasing, then u1(t)<ρ2,u2(t)<ρ3, for all t[0,R].

    In case also assumption (1.6) is satisfied, from the above Theorem we obtain sufficient conditions for the existence of solutions of the BVP (1.1).

    Theorem 4.2. Suppose that (1.2)–(1.6) are satisfied, and that there exist ρ1,ρ2(0,+), with ρ1<ρ2, such that either (S1) or (S2) holds. If n>1 exists, such that (3.7), (3.8) are satisfied with d=2ρ2, then the BVP (1.1) has at least one solution u1, with u1(t)2ρ2 for all t0.

    If, in addition, there exists ρ3(0,+), with ρ2<ρ3, such that either (S3) or (S4) holds, and (3.7), (3.8) are satisfied with d=2ρ3, then the BVP (1.1) has an additional solution u2, with u2(t)2ρ3.

    Remark 4.3. If we have that f(t,v)0 for (t,v)[0,+)×[0,+), then every solution of (3.1) satisfying u(R)=0 is nonincreasing for tR. Thus our method provides one (or more) solutions having a global maximum at t=R, as solutions on [0,R] are nondecreasing. Clearly, if f changes sign in some t1>R, f0 for t[R,t1], then t=R is only a point of local maximum (not necessarily global) for the solutions.

    We conclude this section with the following examples that illustrate our results.

    Example 4.4. Let us consider the BVP

    {(p(t)u(t))+b(t)u2(t)=0, t0,u(0)=H[u], u(+)=0, (4.1)

    where

    p(t)={1,0t1,tn,t>1,b(t)={1,0t1,sin+(π2t)μt2sin(π2t),t>1,

    for some n>1 and μ>0, and

    H[u]=1210u(t)dt.

    The definition of H leads to the natural choice [0,R]=[0,1]. By direct computation one has m=2. The choice of [a,b]=[1/2,1] leads to c=1/2 and M=4. Furthermore note that f_ρ=14ρ2, ¯fρ=ρ2 and

    12ρH[u]1211/2u(t)dt14ρ,foreveryuKρ.

    Observe that the inequalities

    14f_ρ1+H_ρ1[u]14(14ρ12+ρ1)>ρ1,12¯fρ2+¯Hρ212(ρ22+ρ2)<ρ2,14f_ρ3+H_ρ3[u]14(14ρ32+ρ3)>ρ3.

    are satisfied for ρ1=1/20, ρ2=3/4 and ρ3=15. Thus (S3) holds for ρ1=1/20, ρ2=3/4 and ρ3=15. Note that (1.2)–(1.5) are satisfied, with P=1/(n1), F1(v)=F2(v)=v2, b1(t)=b(t),b2(t)=1, and B1<μ holds. Straightforward calculations show that also (1.6) is satisfied. Since M1(d)=M2(d)=d, applying Theorem 4.2 we get the following result:

    If (n1)26 then (4.1) has at least a positive solution u1, with 0u1(t)3/2, for every μ2(n1)log2/3.

    If (n1)2120 then (4.1) has at least two distinct positive solutions u1,u2, with 0u1(t)3/2, 0u2(t)30, for every μ(n1)log2/30.

    Example 4.5. Let us consider the BVP

    {(p(t)u(t))+b(t)u2(t)=0, t0,u(0)=H[u], u(1)=0,u(t)0andboundedon[0,+), (4.2)

    where this time we take

    p(t)={1,0t1,t5,t>1,b(t)={1,0t1,2t,1<t3,e(t3),t>3,

    and we keep H[u]=1210u(t)dt, as in Example 4.3. With the natural choice [0,R]=[0,1], following the same computations as in Example 4.3, we get that (S1) holds for ρ1=1/20, ρ2=3/4. Furthermore (1.2)–(1.5) are satisfied, with P=1/4, F1(v)=F2(v)=v2, b1(t)=b(t),b2(t)=1, and B1=3/2, while (1.6) does not hold. Since M1(d)=M2(d)=d, and (3.7), (3.8) are satisfied for all dmin{83ln2,4}=83ln2>32=2ρ2, applying Theorem 4.1 we get that (4.2) has at least a solution u1, with 0u1(t)3/2 for all t0.

    Note that u1 does not tend to zero as t+. Indeed, as u1(1)=0 and b(t)>0 in [1,2), then u1 is decreasing on [1,2]. Thus, for all t[1,2] it holds

    t5u1(t)=t1(2s)u21(s)dsu21(1)21(2s)ds=u21(1)/2.

    Integration of the above inequality on [1,t],t2 gives

    u1(t)u1(1)u21(1)2t11s5dsu1(1)(1u1(1)8).

    Thus we have u1(2)u21(1)/64 and u1(2)u1(1)(1u1(1)/8)>0 if u1(1)<8. Now, for t2, it holds (t5u1(t))=b(t)u21(t)0, thus t5u1(t)32u1(2)u21(1)/2, and integrating this inequality on [2,t],t2 we obtain

    u1(t)u1(2)u21(1)2t21s5dsu1(1)(1u1(1)8u1(1)221s5ds)=u1(1)(117128u1(1)).

    Thus, since 1/20<u1(1)<3/4, from the above inequality we have

    u1(t)120(151512),t2,

    and therefore u1 has no zero limit as t+.

    The authors wish to thank the Referee for the careful reading of the paper and the constructive comments. G. Infante and S. Matucci were partially supported by G.N.A.M.P.A. - INdAM (Italy).

    The authors declare no conflict of interest in this paper.



    [1] L.-P. Sun, Y.-M. Wei, J.-Y. Zhou, On an iterative method for solving the least squares problem of rank-deficient systems, Int. J. Comput. Math., 92 (2014), 532–541. https://doi.org/10.1080/00207160.2014.900173 doi: 10.1080/00207160.2014.900173
    [2] Z.-Z. Bai, C.-H. Jin, Column-decomposed relaxation methods for the overdetermined systems of linear equations, Int. J. Appl. Math., 13 (2003), 71–82.
    [3] S. Kaczmarz, Angenäherte Auflösung von systemen linearer gleichungen, Bull. Int. Acad. Polon. Sci. Lett., 35 (1937), 355–357.
    [4] M. A. Brooks, A survey of algebraic algorithms in computerized tomography, Oshawa: University of Ontario Institute of Technology, 2010.
    [5] G. N. Hounsfield, Computerized transverse axial scanning (tomography): Part 1. Description of system, Brit. J. Radiol., 46 (1973), 1016–1022. https://doi.org/10.1259/0007-1285-46-552-1016 doi: 10.1259/0007-1285-46-552-1016
    [6] G. T. Herman, Fundamentals of computerized tomography: Image reconstruction from projections, 2 Eds., London: Springer, 2009. https://doi.org/10.1007/978-1-84628-723-7
    [7] F. Natterer, The mathematics of computerized tomography, Philadelphia: SIAM Publications, 2001. https://doi.org/10.1137/1.9780898719284
    [8] G. T. Herman, R. Davidi, Image reconstruction from a small number of projections, Inverse Probl., 24 (2008), 045011. https://doi.org/10.1088/0266-5611/24/4/045011 doi: 10.1088/0266-5611/24/4/045011
    [9] R. Gordon, R. Bender, G. T. Herman, Algebraic reconstruction techniques (ART) for three-dimensional electron microscopy and X-ray photography, J. Theor. Biol., 29 (1970), 471–481. https://doi.org/10.1016/0022-5193(70)90109-8 doi: 10.1016/0022-5193(70)90109-8
    [10] G. T. Herman, L. B. Meyer, Algebraic reconstruction techniques can be made computationally efficient (positron emission tomography application), IEEE. Trans. Med. Imaging, 12 (1993), 600–609. https://doi.org/10.1109/42.241889 doi: 10.1109/42.241889
    [11] C. Byrne, A unified treatment of some iterative algorithms in signal processing and image reconstruction, Inverse Probl., 20 (2004), 103. https://doi.org/10.1088/0266-5611/20/1/006 doi: 10.1088/0266-5611/20/1/006
    [12] D. A. Lorenz, S. Wenger, F. Schöpfer, M. Magnor, A sparse Kaczmarz solver and a linearized Bregman method for online compressed sensing, In: 2014 IEEE International conference on image processing, 2014, 1347–1351. https://doi.org/10.1109/ICIP.2014.7025269
    [13] F. Pasqualetti, R. Carli, F. Bullo, Distributed estimation via iterative projections with application to power network monitoring, Automatica, 48 (2012), 747–758. https://doi.org/10.1016/j.automatica.2012.02.025 doi: 10.1016/j.automatica.2012.02.025
    [14] J. M. Elble, N. V. Sahinidis, P. Vouzis, GPU computing with Kaczmarz's and other iterative algorithms for linear systems, Parallel Comput., 36 (2010), 215–231. https://doi.org/10.1016/j.parco.2009.12.003 doi: 10.1016/j.parco.2009.12.003
    [15] A. Galántai, Projectors and projection methods, New York: Springer, 2004. https://doi.org/10.1007/978-1-4419-9180-5
    [16] P. A. Knight, Error analysis of stationary iteration and associated problems, Manchester: University of Manchester, 1993.
    [17] Z.-Z. Bai, X.-G. Liu, On the Meany inequality with applications to convergence analysis of several row-action iteration methods, Numer. Math., 124 (2013), 215–236. https://doi.org/10.1007/s00211-012-0512-6 doi: 10.1007/s00211-012-0512-6
    [18] A. Ma, D. Needell, A. Ramdas, Convergence properties of the randomized extended Gauss-Seidel and Kaczmarz methods, SIAM J. Matrix Anal. Appl., 36 (2015), 1590–1604. https://doi.org/10.1137/15M1014425 doi: 10.1137/15M1014425
    [19] L. Dai, T. B. Schön, On the exponential convergence of the Kaczmarz algorithm, IEEE Signal Process. Lett., 22 (2015), 1571–1574. https://doi.org/10.1109/LSP.2015.2412253 doi: 10.1109/LSP.2015.2412253
    [20] T. Strohmer, R. Vershynin, A randomized Kaczmarz algorithm with exponential convergence, J. Fourier Anal. Appl., 15 (2009), 262–278. https://doi.org/10.1007/s00041-008-9030-4 doi: 10.1007/s00041-008-9030-4
    [21] Z.-Z. Bai, W.-T. Wu, On greedy randomized Kaczmarz method for solving large sparse linear systems, SIAM J. Sci. Comput., 40 (2018), A592–A606. https://doi.org/10.1137/17M1137747 doi: 10.1137/17M1137747
    [22] R. Ansorge, Connections between the Cimmino-method and the Kaczmarz-method for the solution of singular and regular systems of equations, Computing, 33 (1984), 367–375. https://doi.org/10.1007/bf02242280 doi: 10.1007/bf02242280
    [23] C. Popa, Convergence rates for Kaczmarz-type algorithms, Numer. Algor., 79 (2018), 1–17. https://doi.org/10.1007/s11075-017-0425-7 doi: 10.1007/s11075-017-0425-7
    [24] Z.-Z. Bai, W.-T. Wu, On relaxed greedy randomized Kaczmarz methods for solving large sparse linear systems, Appl. Math. Lett., 83 (2018), 21–26. https://doi.org/10.1016/j.aml.2018.03.008 doi: 10.1016/j.aml.2018.03.008
    [25] J.-J. Zhang, A new greedy Kaczmarz algorithm for the solution of very large linear systems, Appl. Math. Lett., 91 (2019), 207–212. https://doi.org/10.1016/j.aml.2018.12.022 doi: 10.1016/j.aml.2018.12.022
    [26] Z.-Z. Bai, W.-T. Wu, On convergence rate of the randomized Kaczmarz method, Linear Algebra Appl., 553 (2018), 252–269. https://doi.org/10.1016/j.laa.2018.05.009 doi: 10.1016/j.laa.2018.05.009
    [27] Y. Jiang, G. Wu, L. Jiang, A semi-randomized Kaczmarz method with simple random sampling for large-scale linear systems, Adv. Comput. Math., 49 (2023), 20. https://doi.org/10.1007/s10444-023-10018-2 doi: 10.1007/s10444-023-10018-2
    [28] Y. Zeng, D. Han, Y. Su, J. Xie, Randomized Kaczmarz method with adaptive stepsizes for inconsistent linear systems, Numer. Algor., 94 (2023), 1403–1420. https://doi.org/10.1007/s11075-023-01540-x doi: 10.1007/s11075-023-01540-x
    [29] Z.-Z. Bai, W.-T. Wu, Randomized Kaczmarz iteration methods: Algorithmic extensions and convergence theory, Japan J. Indust. Appl. Math., 40 (2023), 1421–1443. https://doi.org/10.1007/s13160-023-00586-7 doi: 10.1007/s13160-023-00586-7
    [30] Z.-Z. Bai, L. Wang, On convergence rates of Kaczmarz-type methods with di erent selection rules of working rows, Appl. Numer. Math., 186 (2023), 289–319. https://doi.org/10.1016/j.apnum.2023.01.013 doi: 10.1016/j.apnum.2023.01.013
    [31] X.-Z. Wang, M.-L. Che, Y.-M. Wei, Randomized Kaczmarz methods for tensor complementarity problems, Comput. Optim. Appl., 82 (2022), 595–615. https://doi.org/10.1007/s10589-022-00382-y doi: 10.1007/s10589-022-00382-y
    [32] D. Needell, J. A. Tropp, Paved with good intentions: Analysis of a randomized block Kaczmarz method, Linear Algebra Appl., 441 (2014), 199–221. https://doi.org/10.1016/j.laa.2012.12.022 doi: 10.1016/j.laa.2012.12.022
    [33] D. Needell, R. Zhao, A. Zouzias, Randomized block Kaczmarz method with projection for solving least squares, Linear Algebra Appl., 484 (2015), 322–343. https://doi.org/10.1016/j.laa.2015.06.027 doi: 10.1016/j.laa.2015.06.027
    [34] Y. Liu, C.-Q. Gu, On greedy randomized block Kaczmarz method for consistent linear systems, Linear Algebra Appl., 616 (2021), 178–200. https://doi.org/10.1016/j.laa.2021.01.024 doi: 10.1016/j.laa.2021.01.024
    [35] I. Necoara, Faster randomized block Kaczmarz algorithms, SIAM J. Matrix Anal. Appl., 40 (2019), 1425–1452. https://doi.org/10.1137/19M1251643 doi: 10.1137/19M1251643
    [36] C.-Q. Miao, W.-T. Wu, On greedy randomized average block Kaczmarz method for solving large linear systems, J. Comput. Appl. Math., 413 (2022), 114372. https://doi.org/10.1016/j.cam.2022.114372 doi: 10.1016/j.cam.2022.114372
    [37] W. Li, F. Yin, Y.-M. Liao, G.-X. Huang, A greedy average block Kaczmarz method for the large scaled consistent system of linear equations, AIMS Mathematics, 7 (2022), 6792–6806. https://doi.org/10.3934/math.2022378 doi: 10.3934/math.2022378
    [38] A.-Q. Xiao, J.-F. Yin, N. Zheng, On fast greedy block Kaczmarz methods for solving large consistent linear systems, Comput. Appl. Math., 42 (2023), 119. https://doi.org/10.1007/s40314-023-02232-x doi: 10.1007/s40314-023-02232-x
    [39] J. Briskman, D. Needell, Block Kaczmarz method with inequalities, J. Math. Imaging Vis., 52 (2015), 385–396. https://doi.org/10.1007/s10851-014-0539-7 doi: 10.1007/s10851-014-0539-7
    [40] Y. Zhang, H. Li, Block sampling Kaczmarz-Motzkin methods for consistent linear systems, Calcolo, 58 (2021), 39. https://doi.org/10.1007/s10092-021-00429-2 doi: 10.1007/s10092-021-00429-2
    [41] Y. Zhang, H. Li, Randomized block subsampling Kaczmarz-Motzkin method, Linear Algebra Appl., 667 (2023), 133–150. https://doi.org/10.1016/j.laa.2023.03.003 doi: 10.1016/j.laa.2023.03.003
    [42] R.-R. Li, H. Liu, On randomized partial block Kaczmarz method for solving huge linear algebraic systems, Comput. Appl. Math., 41 (2022), 278. https://doi.org/10.1007/s40314-022-01978-0 doi: 10.1007/s40314-022-01978-0
    [43] J.-Q. Chen, Z.-D. Huang, On a fast deterministic block Kaczmarz method for solving large-scale linear systems, Numer. Algor., 89 (2022), 1007–1029. https://doi.org/10.1007/s11075-021-01143-4 doi: 10.1007/s11075-021-01143-4
    [44] Å. Björck, Numerical methods for least squares problems, Philadelphia: SIAM Publications, 1996. https://doi.org/10.1137/1.9781611971484
    [45] S. P. Kolodziej, M. Aznaveh, M. Bullock, J. David, T. A. Davis, M. Henderson, et al., The SuiteSparse matrix collection website interface, J. Open Source Softw., 4 (2019), 1244. https://doi.org/10.21105/joss.01244 doi: 10.21105/joss.01244
  • Reader Comments
  • © 2024 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索

Metrics

Article views(521) PDF downloads(61) Cited by(0)

Figures and Tables

Figures(2)  /  Tables(3)

Other Articles By Authors

/

DownLoad:  Full-Size Img  PowerPoint
Return
Return

Catalog