| Solving nonlinear equations problem is one of the most basic problems in modem mathematics. Traditional numerical algorithms-Newton method has to compute Jacobian matrix at each iteration, and O(n3) arithmetic operations are needed. Although traditional quasi-Newton methods reduce the amount of the arithmetic operations comparing with Newton method, it lose some advantages of Newton method. First, it doesn't have self-correction, so the round-off error may take some adverse effects. Second, it can't keep sparse property of the matrix. So it will be restricted in sparse nonlinear systems of equations. But column correction methods can restore the advantage of Newton method. While it has few arithmetic operations.In this paper, we propose a new method combining column partition with LU column correction, which is called LU column partition (LUCP) algorithm. It both needs few arithmetic operations like LU factorizations, and has a better rconvergence order like column correction methods. At the same time, it reduces the amount of the LU factorizations at each iteration. Then it needs less CPU time. It is a more efficient method.Given a consistent partition of the columns of the Jacobian, which divides the set (1,2,…,n) into p subsets c1,c2,…,cp,the calculation process of LUCP algorithm is as follows:(1) Choose x0∈Rn. Set k=0,1=0.(2) Evaluate F0=F(x0), and B0=J(x0), or a finite difference approximation to J0.(3) Factor P0B0=L0U0 by a Doolittle scheme with partial pivoting.(4) Solve Lkzk=-P0Fk and Uksk=zk. Chooseω, and choose xk+1 by xk+1=xk+ωsk, or by a global strategy.(5) Check for convergence.(6) If l＜p, set l=l+1, otherwise, l=1. (7) Choose hk+1, evaluate Fk+1= F(xk+1) and dk+1=∑j∈cl hk+1 ej,F(xk+1+dk+1) and set bijk+1= eiT(F(xk+1+dk+1)-F(xk+1))/hk+1, if j∈cl, (i,j)∈M, ei is the ith column of identity matrix, otherwise, bijk+1=bijk.(8) Update the jth column of Uk=(uij(k)) and Lk=(lij(k)), i.e., if j∈cl, (i, j)∈M, then setotherwise set(9) Replace l by l+1, k by k+1, and go to (4).Lemma 1. Assume thatΩ0={x‖F(x)‖≤‖F(x0)‖} is bounded for all x0∈Rn, F:Rn→Rn is continuously differentiable inΩ0, The LU decomposition of F′(x) exists inΩ0, P0F′(x)=L(x)U(x). Then assume there existsβ＞0, vij＞0, i,j=1,2,…,n such that‖F(x)-1‖≤βand |eiT(F′(x)-F′(y))ej|≤vij‖x-y‖2, i,j =1,2,…,n for all x,y∈Ω0. Then if xk(?)Ω0, hk=O(‖F(xk)‖), Lk and Uk defined by the algorithm satisfies: where cj and dj are constants independent of k, T is the amount of dependent cots of Lk and Uk.Corollary 1. According to Lemma 1, set Bk=LkUk,ifωk has a bottomline, then there exists c and (?) such that Bk satisfies:Theorem 1. According to Corollary 1, there exists 0＜α＜1, if such that‖U0-U(x0)‖+‖L0-L(x0)‖≤(1-α)/2β(?)(2T-1), then for allωk which satisfiesα≤ωkÏ≤(1-α)/2(2T-1), 0＜ωk≤1, whereÏ=2cβ2η, then c is defined by Corollary 1,ηis a constant which satisfies‖F(x0)‖≤η, then xk defined by the algorithm which converges to x* the solution of F(x)=0, and satisfieswhereθ=1-2α2/(1+α)Ï.Theorem 2. Let F : Rn→Rn be continuously differentiable in an oprn convex set D0, there exists x*∈D0 such that F(x*)=0, and F′(x*)is nonsingular. Assume that existsΓ=(vij) such that for all x, x′∈D0,Then given P0, there existsε,δ＞0, such that if‖x0-x*‖＜ε, P0F′(x0) has a LU decomposition, and if‖F′(x0)-F′(x*)‖≤δ, then the algorithm with hk≤O‖F(xk)‖,ωk=1 generates {xk} which conveges locally and q-superlinearly x*.Theorem 3. According to Theorem 2, the r-convergence order of LUCP is not less than. After the paper proved the convergence in probability of LUCP in theory, We select several typical examples to carry on the numerical experiment. We analyse and compare LUCP with CMSCC and WYLU. Our numerical results show that the LUCP algorithm is competitive with the other algorithms. |
PDF Full Text Request