# Fourth- and Fifth-Order Methods for Solving Nonlinear Systems of Equations: An Application to the Global Positioning System

Authors: Manuel F. Abad; Alicia Cordero; Juan R. Torregrosa
Journal: Abstract and Applied Analysis
 (2013)

---

## Abstract

Two iterative methods of order four and five, respectively, are presented for solving nonlinear systems of equations. Numerical comparisons are made with other existing second- and fourth-order schemes to solve the nonlinear system of equations of theGlobal Positioning System and some academic nonlinear systems.


---

## Body

## 1. Introduction

The search for solutions of nonlinear systems of equations is an old and difficult problem with wide applications in sciences and engineering. The best known method, for being very simple and effective, is Newton’s method. Its generalization to a system of equations was proposed by Ostrowski [1] and to Banach spaces by Kantorovič [2]. In the literature, several modifications have been made on classical methods in order to accelerate the convergence or to reduce the number of operations and evaluations of functions in each step of the iterative process. The extension of the variants of Newton’s method described by Weerakoon and Fernando in [3], by Özban in [4] and Gerlach in [5], to the functions of several variables has been developed in [6–9]. In [6, 7], families of variants of Newton’s method of third-order have been designed by using open and closed formulas of quadrature, including the families of the methods defined by Frontini and Sormani in [8]. Using the generic formula of the interpolatory quadrature, in [9] a family of methods is obtained with order of convergence 2d+1, under certain conditions, where d is the order up to which the partial derivatives of each coordinate function evaluated in the solution are canceled. Indeed, Darvishi and Barati improved in [10] the method from Frontini and Sormani, getting a fourth-order scheme. In addition to multistep methods based on interpolatory quadrature, other schemes have been developed by using different techniques, as extension to several variables of one-dimensional schemes (see [11]), Adomian decomposition (see [12, 13], e.g.), the one proposed by Darvishi and Barati in [14, 15] with super cubic convergence, and the methods proposed by Cordero et al. in [16] with orders of convergence four and five. Another procedure to develop iterative methods for nonlinear systems is the replacement of the second derivative by some approximation. In [17], Traub presented a family of multipoint methods based on approximating the second derivative that appears in the iterative formula of Chebyshev’s scheme, and more recently, Babajee et al. in [18] designed two Chebyshev-like methods free from second derivatives. Recently, Sharma et al. [19] designed a fourth-order scheme by using weight-function technique. Another well-known acceleration technique is the composition of two iterative methods of orders p1 and p2, respectively, obtaining a method of order p1p2 (see [17]). New evaluations of the Jacobian matrix and the nonlinear function are usually needed in order to increase the order of convergence.Now, we are going to introduce the problem and some necessary concepts in order to develop the modified methods and to analyze their convergence. Let us consider the problem of finding a real zero of a functionF:D⊆ℝn→ℝn, that is, a solution x¯∈D of the nonlinear system F(x)=0 of n equations with n unknowns. The best known iterative method is the classical Newton method given by
(1)x(k+1)=x(k)-F′(x(k))-1F(x(k)),k=0,1,…,
where F′(x(k)) is the Jacobian matrix of the function F evaluated in the kth iteration x(k). Traub, in [17], introduced a variant of Newton’s method of convergence order three. We are going to describe it because our methods combine Traub with Newton's method. Traub's scheme consists of the composition of Newton's method with itself, but with a frozen Jacobian matrix, its iterative expression is
(2)x(k+1)=x(k)-F′(x(k))-1(F(x(k))+F(y(k))),k=0,1,…,
where y(k) is the kth iteration of Newton’s method.On the other hand, recently Sharma et al. in [19] have developed a fourth-order method for solving nonlinear systems of equations. The algorithm is composed of two weighted Newton steps, and it is given by
(3)y(k)=x(k)-23F′(x(k))-1F(x(k)),x(k+1)=x(k)-12[-I+94F′(y(k))-1F′(x(k))+34F′(x(k))-1F′(y(k))]×F′(x(k))-1F(x(k)),k=0,1,….In the following, we remember some known notions and results that we need in order to analyze the convergence of the new methods. LetF:D⊆ℝn→ℝn be sufficiently Frechet differentiable in D. By using the notation introduced in [20], the qth derivative of F at u∈ℝn, q≥1 is the q-linear function F(q)(u):ℝn×ℝn×⋯×ℝn→ℝn such that F(q)(u)(v1,v2,…,vq)∈ℝn. It is easy to observe that(1)
F(q)(u)(v1,v2,…,vq-1,·)∈ℒ(ℝn),(2)
F(q)(u)(vσ(1),vσ(2),…,vσ(q))=F(q)(u)(v1,v2,…,vq) for all permutation σ of {1,2,…,q},where ℒ(ℝn) is the set of lineal operators of ℝn in ℝn.From the above properties, we can use the following notation:(1)
F(q)(u)(v1,v2,…,vq)=F(q)(u)v1·⋯·vq,(2)
F(q)(u)vq-1F(p)vp=F(q)(u)F(p)(u)vq+p-1.On the other hand, forx¯+h∈ℝn lying in a neighborhood of a solution x¯ of F(x)=0, we can apply Taylor's expansion, and assuming that the Jacobian matrix F′(x¯) is nonsingular, we have
(4)F(x¯+h)=F′(x¯)[h+∑q=2p-1‍Cqhq]+O(hp),
where Cq=(1/q!)[F′(x¯)]-1F(q)(x¯), q≥2. We observe that Cqhq∈ℝn since F(q)(x¯)∈ℒ(ℝ×⋯×ℝ,ℝ) and [F′(x¯)]-1∈ℒ(ℝn).In addition, we can expressF′ as
(5)F′(x¯+h)=F′(x¯)[I+∑q=2p-1‍qCqhq-1]+O(hp)=F′(x¯)D(h)+O(hp),
where I is the identity matrix. Therefore, qCqhq-1∈ℒ(ℝn). From the previous equation, we obtain
(6)[F′(x¯+h)]-1=D(h)-1[F′(x¯)]-1+O(hp).Then, if the inverse ofD(h) is
(7)D(h)-1=I+X2h+X3h2+X4h3+⋯,provided that Xi, i=2,3,…  verify
(8)D(h)D(h)-1=D(h)-1D(h)=I.Solving the system involved in (8), we have that
(9)X2=-2C2,X3=4C22-3C3,X4=-8C23+6C2C3+6C3C2-4C4,⋮We denotee(k)=x(k)-x¯ as  the error in the kth iteration. The equation(10)e(k+1)=Le(k)p+O(e(k)p+1),
where L is a p-linear function L∈ℒ(ℝ×⋯×ℝ,ℝ), is called the error equation, and p is the order of convergence. Observe that e(k)p is (e(k),e(k),…,e(k)).In [7], the concept of computational order of convergence was introduced as follows.Definition 1.
Letx¯ be a zero of a function F, and suppose that x(k-1), x(k), and x(k+1) are three consecutive iterations close to x¯. Then, the  computational order of convergence p can be approximated using the formula
(11)p≈ACOC=ln(∥x(k+1)-x(k)∥/∥x(k)-x(k-1)∥)ln(∥x(k)-x(k-1)∥/∥x(k-1)-x(k-2)∥).In addition, in order to compare different methods, we use theefficiency index, I=p1/d, where p is the order of convergence and d is the total number of new functional evaluations (per iteration) required by the method. This is the most used index, but not the only one. In [17], Traub uses a computational index defined as CI=p1/op, where op is the number of products/quotients per iteration. We recall that the number of products and quotients that we need for solving m linear systems with the same matrix of coefficients, by using LU factorization, is
(12)13n3+mn2-13n,
where n is the size of each system. We will use these indices in order to compare the different iterative methods. Kung and Traub in [21] conjectured that the order of convergence of any multipoint method without memory for solving nonlinear equations cannot exceed the bound 2d-1 (called the optimal order). Ostrowski's method [1], Jarrett's scheme [22], and King's procedure [23] are some of the optimal one-dimensional fourth-order methods. We have adapted the definition of optimal order of convergence to the case of iterative methods to solve nonlinear systems. The extension to several variables of the conjecture of Kung and Traub could be done in the following way [24].Conjecture 2.
Given a multipoint iterative method to solve nonlinear systems of equations which requiresd=k1+k2 functional evaluations per step such that k1 of them correspond to the functional evaluations of the Jacobian matrix and k2 to evaluations of the nonlinear function. We conjecture that the optimal order for this method is 2k1+k2-1 if k1≤k2.In this paper, we propose two new and competitive iterative methods of orders four and five, respectively, that improve other known methods.The rest of this paper is organized as follows: in Section2, we make an introduction to the Global Positioning System (GPS), focusing on the way that the receiver calculates the user position using the ephemeris data of the artificial satellites. In Section 3, we present our new iterative methods and analyze its convergence order, and by using the idea of a technique presented in [25], it is also proved that, in general, if we combine two methods of orders p and q, respectively, with p≥q, in the same way that we do it in our method of order five, the order of convergence of the resultant method is p+q. In Section 4, we show an application of this analysis in order to solve the nonlinear system of the GPS and several academic nonlinear systems of equations. A comparison is established among the new methods and Newton and Sharma’s methods in terms of convergence order, approximated computational convergence order (ACOC), and computational and efficiency indices, CI and I, respectively.


## 2. Basics on Global Positioning System

This section introduces the basic concept of how a GPS receiver determines its position. From the satellite constellation, the equations required for solving the user position conform a nonlinear system of equations. In addition, some practical considerations (i.e., the inaccuracy of the user clock) will be included in these equations. These equations are usually solved through a linearization and a fixed point iteration method. The obtained solution is in a Cartesian coordinate system, and after that the result will be converted into a spherical coordinate system. However, the Earth is not a perfect sphere; therefore, once the user position is estimated, the shape of the Earth must be taken into consideration. The user position is then translated into the Earth-based coordinate system. In this paper, we are going to focus our attention in solving the nonlinear system of equations of the GPS giving the results in a Cartesian coordinate system. We can find further information about GPS in [26].


### 2.1. Basic GPS Concepts

The position of a point in space can be found by using the distances measured from this point to some known position in space. We are going to use an example to illustrate this point.Figure1 shows a two-dimensional case. In order to determine the user position U, three satellites S1, S2, and S3 and three distances are required. The trace of a point with constant distance to a fixed point is a circle in the two-dimensional case. Two satellites and two distances give two possible solutions because two circles intersect at two points. A third circle is needed to uniquely determine the user position. For similar reasons in a three-dimensional case, four satellites and four distances are needed. The equal-distance trace to a fixed point is a sphere in a three-dimensional case. Two spheres intersect to make a circle. This circle intersects another sphere, and this intersection produces two points. In order to determine which point is the user position, one more satellite should be needed. In GPS, the position of the satellite is known from the ephemeris data transmitted by the satellite. By measuring the distance from the receiver to the satellite, the position of the receiver can be determined. In the above discussion, the distance measured from the user to the satellite is assumed to be very accurate, and there is no bias error. However, the distance measured between the receiver and the satellite has a constant unknown bias, because the user clock usually is different from the GPS clock. In order to solve this bias error, one more satellite is required. Therefore, in order to find the user position, five satellites are needed. If one uses four satellites and the measured distance with bias error to measure a user position, two possible solutions can be obtained. Theoretically, one cannot determine the user position. However, one of the solutions is close to the Earth's surface, and the other one is in the space. In fact, as we will see in Section 4, in this memory, we have used four satellites, and sometimes we have found the solution in the space. Since the user position is usually close to the surface of the earth, it can be uniquely determined. Therefore, the general statement is that four satellites can be used to determine a user position, even though the distance measured has a bias error. The method of solving the user position discussed in the next subsections is through iteration. The initial position is often selected at the center of the Earth. In the following discussion, four satellites are considered as the minimum number required for finding the user position.Figure 1
Two-dimensional user position.


### 2.2. Basic Equations for Finding User Position

In this section, the basic equations for determining the user position will be presented. Assume that the distance measured is accurate, and under this condition, three satellites should be sufficient. Let us suppose that there are three known points at locationsr1 or (x1,y1,z1), r2 or (x2,y2,z2), and r3 or (x3,y3,z3) and an unknown point at ru or (xu,yu,zu). If the distances between the three known points to the unknown point can be measured as ρ1, ρ2, and ρ3, these distances can be written as
(13)ρ1=(x1-xu)2+(y1-yu)2+(z1-zu)2,ρ2=(x2-xu)2+(y2-yu)2+(z2-zu)2,ρ3=(x3-xu)2+(y3-yu)2+(z3-zu)2.Because there are three unknowns and three equations, the values ofxu, yu, and zu can be determined from these equations. Theoretically, there should be two sets of solutions as they are second-order equations. These equations can be solved by linearizing them and making an iterative approach. The solution of these equations will be discussed later in Section 2.4. In GPS operation, the positions of the satellites are given. This information can be obtained from the data transmitted from the satellites. The distances from the user (the unknown position) to the satellites must be measured simultaneously at a certain time instance. Each satellite transmits a signal with a time reference associated with it. By measuring the time of the signal traveling from the satellite to the user, the distance between the user and the satellite can be found. The distance measurement is discussed in the next section.


### 2.3. Measurement of Pseudorange

Every satellite sends a signal at a certain timetsi. The receiver will receive the signal at a later time tu. The distance between the user and the satellite i can be determined as
(14)ρiT=c(tu-tsi),
where c is the speed of light, ρiT is often referred to as the true value of pseudorange from user to satellite i, tsi is referred to as the true time of transmission from satellite i, and tu is the true time of reception. From a practical point of view, it is difficult, if not impossible, to obtain the correct time from the satellite or the user. The actual satellite clock time tsi′ and actual user clock time tu′ are related to the true time as
(15)tsi′=tsi+Δbi,tu′=tu+but,
where Δbi is the satellite clock error and but is the user clock bias error. Besides the clock error, there are other factors affecting the pseudorange measurement. The measured pseudorange ρi can be written as
(16)ρi=ρiT+ΔDi-c(Δbi-but)+c(ΔTi+ΔIi+vi+Δvi),
where ΔDi is the satellite position error effect on the range, ΔTi is the tropospheric delay error, ΔIi is the ionospheric delay error, vi is the receiver measurement noise error, and Δvi is the relativistic time correction. Some of these errors can be corrected; for example, the tropospheric delay can be modeled, and the ionospheric error can be corrected in a two-frequency receiver. The errors will cause inaccuracy of the user position. However, the user clock error cannot be corrected through receiver information. Thus, it will remain as an unknown. So, the system of (13) must be modified as
(17)ρ1=(x1-xu)2+(y1-yu)2+(z1-zu)2+bu,ρ2=(x2-xu)2+(y2-yu)2+(z2-zu)2+bu,ρ3=(x3-xu)2+(y3-yu)2+(z3-zu)2+bu,ρ4=(x4-xu)2+(y4-yu)2+(z4-zu)2+bu,
where bu is the user clock bias error expressed in distance, which is related to the quantity but by bu=cbut. In the system of (17), four equations are needed to solve four unknowns xu, yu, zu, and bu. Thus, in a GPS receiver, a minimum of four satellites is required to solve the user position.


### 2.4. Solution of User Position from Pseudoranges

One common way to solve the system of (17) is to linearize them. The system can be written in a simplified form as
(18)ρi=(xi-xu)2+(yi-yu)2+(zi-zu)2+bu,
(with i=1,2,3,4, and xu, yu, zu and bu) are the unknowns. The pseudorange ρi and the positions of the satellites xi, yi, zi are known. By differentiating (18),
(19)δρi=(xi-xu)δxu+(yi-yu)δyu+(zi-zu)δzu(xi-xu)2+(yi-yu)2+(zi-zu)2+δbu=(xi-xu)δxu+(yi-yu)δyu+(zi-zu)δzuρi-bu+δbu.In (19), δxu, δyu, δzu, and δbu can be considered as the only unknowns. The quantities xu, yu, zu, and bu are treated as known values because one can assume some initial values for these quantities. From these initial values, a new set of δxu, δyu, δzu, and δbu can be calculated. These values are used to modify the original xu, yu, zu, and bu to find another new set of solutions. This new set of xu, yu, zu, and bu can be considered again as known quantities. This process continues until the absolute values of δxu, δyu, δzu, and δbu are very small and within a certain predetermined limit. The final values of xu, yu, zu, and bu are the desired solution. This method is often referred to as an iteration method of fixed point. With δxu, δyu, δzu, and δbu as unknowns, the above equation becomes a set of linear equations. This procedure is often referred to as linearization. The expression (19) can be written in matrix form as
(20)[δρ1δρ2δρ3δρ4]=[α11α12α131α21α22α231α31α32α331α41α42α431][δxuδyuδzuδbu],
where
(21)αi1=xi-xuρi-bu,αi2=yi-yuρi-bu,αi3=zi-zuρi-bu.The solution of (20) is
(22)[δxuδyuδzuδbu]=[α11α12α131α21α22α231α31α32α331α41α42α431]-1[δρ1δρ2δρ3δρ4].This process obviously does not provide the needed solutions directly. However, the desired solutions can be obtained from it. In order to find the desired position solution, this procedure must be used repetitively in an iterative way. A quantity is often used to determine whether the desired result is reached, and this quantity can be defined as(23)δυ=δxu2+δyu2+δzu2+δbu2.Whenδυ is lower than a certain predetermined threshold, the iteration will stop. Sometimes, the clock bias bu is not included in (23). In this paper, we use as stopping criterion the quantity ||x(k+1)-x(k)||+||F(x(k+1))|| because it is stronger than (23). As we can verify in [27] the above iterative method used to calculate via software, the receiver position in the GPS is Newton's method, a well-known method of second-order of convergence. In this work, we improve the GPS software by means of two methods of order four and five, respectively, that converge to the solution with less number of iterations and better I or CI than Newton scheme.


## 2.1. Basic GPS Concepts

The position of a point in space can be found by using the distances measured from this point to some known position in space. We are going to use an example to illustrate this point.Figure1 shows a two-dimensional case. In order to determine the user position U, three satellites S1, S2, and S3 and three distances are required. The trace of a point with constant distance to a fixed point is a circle in the two-dimensional case. Two satellites and two distances give two possible solutions because two circles intersect at two points. A third circle is needed to uniquely determine the user position. For similar reasons in a three-dimensional case, four satellites and four distances are needed. The equal-distance trace to a fixed point is a sphere in a three-dimensional case. Two spheres intersect to make a circle. This circle intersects another sphere, and this intersection produces two points. In order to determine which point is the user position, one more satellite should be needed. In GPS, the position of the satellite is known from the ephemeris data transmitted by the satellite. By measuring the distance from the receiver to the satellite, the position of the receiver can be determined. In the above discussion, the distance measured from the user to the satellite is assumed to be very accurate, and there is no bias error. However, the distance measured between the receiver and the satellite has a constant unknown bias, because the user clock usually is different from the GPS clock. In order to solve this bias error, one more satellite is required. Therefore, in order to find the user position, five satellites are needed. If one uses four satellites and the measured distance with bias error to measure a user position, two possible solutions can be obtained. Theoretically, one cannot determine the user position. However, one of the solutions is close to the Earth's surface, and the other one is in the space. In fact, as we will see in Section 4, in this memory, we have used four satellites, and sometimes we have found the solution in the space. Since the user position is usually close to the surface of the earth, it can be uniquely determined. Therefore, the general statement is that four satellites can be used to determine a user position, even though the distance measured has a bias error. The method of solving the user position discussed in the next subsections is through iteration. The initial position is often selected at the center of the Earth. In the following discussion, four satellites are considered as the minimum number required for finding the user position.Figure 1
Two-dimensional user position.


## 2.2. Basic Equations for Finding User Position

In this section, the basic equations for determining the user position will be presented. Assume that the distance measured is accurate, and under this condition, three satellites should be sufficient. Let us suppose that there are three known points at locationsr1 or (x1,y1,z1), r2 or (x2,y2,z2), and r3 or (x3,y3,z3) and an unknown point at ru or (xu,yu,zu). If the distances between the three known points to the unknown point can be measured as ρ1, ρ2, and ρ3, these distances can be written as
(13)ρ1=(x1-xu)2+(y1-yu)2+(z1-zu)2,ρ2=(x2-xu)2+(y2-yu)2+(z2-zu)2,ρ3=(x3-xu)2+(y3-yu)2+(z3-zu)2.Because there are three unknowns and three equations, the values ofxu, yu, and zu can be determined from these equations. Theoretically, there should be two sets of solutions as they are second-order equations. These equations can be solved by linearizing them and making an iterative approach. The solution of these equations will be discussed later in Section 2.4. In GPS operation, the positions of the satellites are given. This information can be obtained from the data transmitted from the satellites. The distances from the user (the unknown position) to the satellites must be measured simultaneously at a certain time instance. Each satellite transmits a signal with a time reference associated with it. By measuring the time of the signal traveling from the satellite to the user, the distance between the user and the satellite can be found. The distance measurement is discussed in the next section.


## 2.3. Measurement of Pseudorange

Every satellite sends a signal at a certain timetsi. The receiver will receive the signal at a later time tu. The distance between the user and the satellite i can be determined as
(14)ρiT=c(tu-tsi),
where c is the speed of light, ρiT is often referred to as the true value of pseudorange from user to satellite i, tsi is referred to as the true time of transmission from satellite i, and tu is the true time of reception. From a practical point of view, it is difficult, if not impossible, to obtain the correct time from the satellite or the user. The actual satellite clock time tsi′ and actual user clock time tu′ are related to the true time as
(15)tsi′=tsi+Δbi,tu′=tu+but,
where Δbi is the satellite clock error and but is the user clock bias error. Besides the clock error, there are other factors affecting the pseudorange measurement. The measured pseudorange ρi can be written as
(16)ρi=ρiT+ΔDi-c(Δbi-but)+c(ΔTi+ΔIi+vi+Δvi),
where ΔDi is the satellite position error effect on the range, ΔTi is the tropospheric delay error, ΔIi is the ionospheric delay error, vi is the receiver measurement noise error, and Δvi is the relativistic time correction. Some of these errors can be corrected; for example, the tropospheric delay can be modeled, and the ionospheric error can be corrected in a two-frequency receiver. The errors will cause inaccuracy of the user position. However, the user clock error cannot be corrected through receiver information. Thus, it will remain as an unknown. So, the system of (13) must be modified as
(17)ρ1=(x1-xu)2+(y1-yu)2+(z1-zu)2+bu,ρ2=(x2-xu)2+(y2-yu)2+(z2-zu)2+bu,ρ3=(x3-xu)2+(y3-yu)2+(z3-zu)2+bu,ρ4=(x4-xu)2+(y4-yu)2+(z4-zu)2+bu,
where bu is the user clock bias error expressed in distance, which is related to the quantity but by bu=cbut. In the system of (17), four equations are needed to solve four unknowns xu, yu, zu, and bu. Thus, in a GPS receiver, a minimum of four satellites is required to solve the user position.


## 2.4. Solution of User Position from Pseudoranges

One common way to solve the system of (17) is to linearize them. The system can be written in a simplified form as
(18)ρi=(xi-xu)2+(yi-yu)2+(zi-zu)2+bu,
(with i=1,2,3,4, and xu, yu, zu and bu) are the unknowns. The pseudorange ρi and the positions of the satellites xi, yi, zi are known. By differentiating (18),
(19)δρi=(xi-xu)δxu+(yi-yu)δyu+(zi-zu)δzu(xi-xu)2+(yi-yu)2+(zi-zu)2+δbu=(xi-xu)δxu+(yi-yu)δyu+(zi-zu)δzuρi-bu+δbu.In (19), δxu, δyu, δzu, and δbu can be considered as the only unknowns. The quantities xu, yu, zu, and bu are treated as known values because one can assume some initial values for these quantities. From these initial values, a new set of δxu, δyu, δzu, and δbu can be calculated. These values are used to modify the original xu, yu, zu, and bu to find another new set of solutions. This new set of xu, yu, zu, and bu can be considered again as known quantities. This process continues until the absolute values of δxu, δyu, δzu, and δbu are very small and within a certain predetermined limit. The final values of xu, yu, zu, and bu are the desired solution. This method is often referred to as an iteration method of fixed point. With δxu, δyu, δzu, and δbu as unknowns, the above equation becomes a set of linear equations. This procedure is often referred to as linearization. The expression (19) can be written in matrix form as
(20)[δρ1δρ2δρ3δρ4]=[α11α12α131α21α22α231α31α32α331α41α42α431][δxuδyuδzuδbu],
where
(21)αi1=xi-xuρi-bu,αi2=yi-yuρi-bu,αi3=zi-zuρi-bu.The solution of (20) is
(22)[δxuδyuδzuδbu]=[α11α12α131α21α22α231α31α32α331α41α42α431]-1[δρ1δρ2δρ3δρ4].This process obviously does not provide the needed solutions directly. However, the desired solutions can be obtained from it. In order to find the desired position solution, this procedure must be used repetitively in an iterative way. A quantity is often used to determine whether the desired result is reached, and this quantity can be defined as(23)δυ=δxu2+δyu2+δzu2+δbu2.Whenδυ is lower than a certain predetermined threshold, the iteration will stop. Sometimes, the clock bias bu is not included in (23). In this paper, we use as stopping criterion the quantity ||x(k+1)-x(k)||+||F(x(k+1))|| because it is stronger than (23). As we can verify in [27] the above iterative method used to calculate via software, the receiver position in the GPS is Newton's method, a well-known method of second-order of convergence. In this work, we improve the GPS software by means of two methods of order four and five, respectively, that converge to the solution with less number of iterations and better I or CI than Newton scheme.


## 3. Description of the Methods and Convergence Analysis

### 3.1. A Fourth-Order Method

In this section, we display a new method for solving nonlinear systems that we callM4, obtained by combining (Newton and Traub's method). Its iterative expression is
(24)z(k)=x(k)-F′(x(k))-1(F(x(k))+F(y(k))),x(k+1)=y(k)-[F′(z(k))]-1F(y(k)),
where y(k) is the kth iteration of Newton’s method. In the next result, we are going to prove that the convergence order of the method is four.Theorem 3.
LetF:D⊆ℝn→ℝn be sufficiently differentiable at each point of an open neighborhood D of  x¯∈ℝn that is a solution of the nonlinear system F(x)=0. Let one suppose that F′(x) is continuous and nonsingular in x¯. Then, the sequence {x(k)}k≥0 obtained by using the iterative expression (24) converges to x¯ with order four. The error equation is
(25)e(k+1)=-C23e(k)4+O(e(k)5),
where Ck=(1/k!)[F′(x¯)]-1F(k)(x¯),k=2,3,…, and e(k)=x(k)-x¯.Proof.
Taylor expansion ofF(x(k)) and F′(x(k)) around x¯ gives
(26)F(x(k))=F′(x¯)[e(k)+C2e(k)2+C3e(k)3+C4e(k)4]+O(e(k)5),F′(x(k))=F′(x¯)[I+2C2e(k)+3C3e(k)2+4C4e(k)3+5C5e(k)4]+O(e(k)5),
where Ck=(1/k!)[F′(x¯)]-1F(k)(x¯),k=2,3,…, and e(k)=x(k)-x¯. From (26), we obtain
(27)[F′(x(k))]-1=[I+X2e(k)+X3e(k)2+X4e(k)3]×[F′(x¯)]-1+O(e(k)4),
where X2=-2C2, X3=4C22-3C3, and X4=-8C23+6C2C3+6C3C2-4C4. Taylor's expansion of y(k) is
(28)y(k)-x¯=C2e(k)2+(2C3-2C22)e(k)3+(4C23-4C2C3-3C3C2+3C4)e(k)4+O(e(k)5).
On the other hand, we have that(29)F(y(k))=F′(x¯)[(y(k)-x¯)+C2(y(k)-x¯)2]+O(e(k)5),
and by operating, we get
(30)F(y(k))=F′(x¯)[C2e(k)2+(2C3-2C22)e(k)3+(5C23-4C2C3-3C3C2+3C4{C23})e(k)4]+O(e(k)5).
Analogously, we obtain the expression ofz(k)-x¯. Given that the kth iteration of Traub's scheme is
(31)z(k)=y(k)-[F′(x(k))]-1F(y(k)),
then
(32)z(k)-x¯=2C22e(k)3+(-9C23+4C2C3+3C3C2)e(k)4+O(e(k)5).
Besides, the expression ofF′(z(k)) is
(33)F′(z(k))=F′(x¯)[I+2C2(z(k)-x¯)]+O(e(k)5),
or, equivalently from (32),
(34)F′(z(k))=F′(x¯)[I+4C23e(k)3+(-18C24+8C22C3+6C2C3C2)e(k)4]+O(e(k)5).
So,(35)[F′(z(k))]-1=[I+W2e(k)+W3e(k)2+W4e(k)3+W5e(k)4]×[F′(x¯)]-1+O(e(k)5),
and provided that [F′(z(k))]-1F′(z(k))=I, solving the linear system of equations involved, we have W2=W3=0, W4=-4C23, and W5=18C24-8C22C3-6C2C3C2, so
(36)[F′(z(k))]-1=[I-4C23e(k)3+(18C24-8C22C3-6C2C3C2)e(k)4]×[F′(x¯)]-1+O(e(k)5).
Then,(37)[F′(z(k))]-1F(y(k))=C2e(k)2+2(C3-C22)e(k)3+(5C23-4C2C3-3C3C2+3C4)e(k)4+O(e(k)5).
Finally, by replacing (28) and (37) in the iterative expression (24), we obtain the error equation
(38)e(k+1)=x(k+1)-x¯=y(k)-x¯-[F′(z(k))]-1F(y(k))=-C23e(k)4+O(e(k)5),
and the proof of the theorem is completed.


### 3.2. A Fifth-Order Method

In this section, we show a new method for solving nonlinear systems that we callM5, which is obtained by combining again Newton and Traub's methods but in a different way. Its iterative expression is
(39)z(k)=x(k)-F′(x(k))-1(F(x(k))+F(y(k))),x(k+1)=z(k)-[F′(y(k))]-1F(z(k)),
where y(k) is the kth iteration of Newton's method. We prove in the next result that the convergence order of this method is five.Theorem 4.
LetF:D⊆ℝn→ℝn be sufficiently differentiable at each point of an open neighborhood D of  x¯∈ℝn that is a solution of the nonlinear system F(x)=0. Let one suppose that F′(x) is continuous and nonsingular in x¯. Then, the sequence {x(k)}k≥0 obtained by using the iterative expression (39) converges to x¯ with order five. The error equation is
(40)e(k+1)=4C24e(k)5+O(e(k)6),
where Ck=(1/k!)[F′(x¯)]-1F(k)(x¯),k=2,3,…, and e(k)=x(k)-x¯.Proof.
Following the procedure used in Theorem3, we have that
(41)F(y(k))=F′(x¯)[C2e(k)2+(2C3-2C22)e(k)3+(5C23-4C2C3-3C3C2+3C4)e(k)4+(-6C32-12C24+10C22C3+8C2C3C2+6C3C22-6C2C4-4C4C2+4C5)e(k)5]+O(e(k)6),(42)z(k)-x¯=2C22e(k)3+(-9C23+4C2C3+3C3C2)e(k)4+(30C24-18C22C3+6C32-12C3C22-14C2C3C2+6C2C4+4C4C2{C22})e(k)5+O(e(k)6).
On the other hand,(43)F(z(k))=F′(x¯)[(z(k)-x¯)]+O(e(k)4),(44)[F′(y(k))]-1=[I+X2(y(k)-x¯)+X3(y(k)-x¯)2]×[F′(x¯)]-1+O(e(k)5).
Finally, by replacing (42) and (44) in the iterative expression (39), we obtain the error equation
(45)e(k+1)=x(k+1)-x¯=z(k)-x¯-[F′(y(k))]-1F(z(k))=4C24e(k)5+O(e(k)6),
and the proof of the theorem is completed.


### 3.3.Pseudocomposition

In [25] a technique called pseudocomposition that uses a known method as a predictor and the Gaussian quadrature as a corrector was introduced. The order of convergence of the resulting scheme depends, among other factors, on the order of the last two steps of the predictor. Following this idea, we generalize the procedure used to design method M5.Then, we can establish the next result.Theorem 5.
LetF:D⊆ℝn→ℝn be sufficiently differentiable at each point of an open neighborhood D of  x¯∈ℝn that is a solution of the nonlinear system F(x)=0. Let one suppose that F′(x) is continuous and nonsingular in x¯. Let y(k) be the kth iteration of an iterative method of order q and z(k) the kth iteration of an iterative method of order p, with p≥q. The sequence {x(k)}k≥0 obtained by the iterative expression
(46)x(k+1)=z(k)-[F′(y(k))]-1F(z(k)),
converges to x¯ with the order of convergence p+q.Proof.
Taylor’s expansions ofy(k) and z(k) are
(47)y(k)=x¯+M1e(k)q+M2e(k)q+1+⋯+Mp+1e(k)q+p+O(e(k)p+q+1),z(k)=x¯+N1e(k)p+N2e(k)p+1+⋯+Nq+1e(k)p+q+O(e(k)p+q+1).
Taylor’s expansion ofF(z(k)) around x¯ gives
(48)F(z(k))=F′(x¯)[z(k)-x¯+C2(z(k)-x¯)2]+O(e(k)2(p+q)+1)=F′(x¯)[N1e(k)p+N2e(k)p+1+⋯+Nq+1e(k)p+q+C2(N1e(k)p+N2e(k)p+1+⋯+Nq+1e(k)p+q)2]+O(e(k)2(p+q)+1),
where Ck=(1/k!)[F′(x¯)]-1F(k)(x¯),k=2,3,…, and e(k)=x(k)-x¯. On the other hand, we have that
(49)[F′(y(k))]-1=[I+X2(y(k)-x¯)+X3(y(k)-x¯)2]×[F′(x¯)]-1+O(e(k)2q+1)=[I+X2(M1e(k)q+M2e(k)q+1+⋯+Mp+1e(k)q+p)+X3(R1e(k)2q+⋯)]×[F′(x¯)]-1+O(e(k)m),
where m=min{p+q+1,2q+1}=p+q+1. Finally, by replacing (47), (48), and (49) in the iterative expression (46), we obtain the error equation
(50)e(k+1)=x(k+1)-x¯=z(k)-x¯-[F′(y(k))]-1F(z(k))=2C2M1N1e(k)p+q+O(e(k)p+q+1).
Then, the convergence order of the method that results from this combination of a method of orderq with another of order p with p≥q is p+q.


## 3.1. A Fourth-Order Method

In this section, we display a new method for solving nonlinear systems that we callM4, obtained by combining (Newton and Traub's method). Its iterative expression is
(24)z(k)=x(k)-F′(x(k))-1(F(x(k))+F(y(k))),x(k+1)=y(k)-[F′(z(k))]-1F(y(k)),
where y(k) is the kth iteration of Newton’s method. In the next result, we are going to prove that the convergence order of the method is four.Theorem 3.
LetF:D⊆ℝn→ℝn be sufficiently differentiable at each point of an open neighborhood D of  x¯∈ℝn that is a solution of the nonlinear system F(x)=0. Let one suppose that F′(x) is continuous and nonsingular in x¯. Then, the sequence {x(k)}k≥0 obtained by using the iterative expression (24) converges to x¯ with order four. The error equation is
(25)e(k+1)=-C23e(k)4+O(e(k)5),
where Ck=(1/k!)[F′(x¯)]-1F(k)(x¯),k=2,3,…, and e(k)=x(k)-x¯.Proof.
Taylor expansion ofF(x(k)) and F′(x(k)) around x¯ gives
(26)F(x(k))=F′(x¯)[e(k)+C2e(k)2+C3e(k)3+C4e(k)4]+O(e(k)5),F′(x(k))=F′(x¯)[I+2C2e(k)+3C3e(k)2+4C4e(k)3+5C5e(k)4]+O(e(k)5),
where Ck=(1/k!)[F′(x¯)]-1F(k)(x¯),k=2,3,…, and e(k)=x(k)-x¯. From (26), we obtain
(27)[F′(x(k))]-1=[I+X2e(k)+X3e(k)2+X4e(k)3]×[F′(x¯)]-1+O(e(k)4),
where X2=-2C2, X3=4C22-3C3, and X4=-8C23+6C2C3+6C3C2-4C4. Taylor's expansion of y(k) is
(28)y(k)-x¯=C2e(k)2+(2C3-2C22)e(k)3+(4C23-4C2C3-3C3C2+3C4)e(k)4+O(e(k)5).
On the other hand, we have that(29)F(y(k))=F′(x¯)[(y(k)-x¯)+C2(y(k)-x¯)2]+O(e(k)5),
and by operating, we get
(30)F(y(k))=F′(x¯)[C2e(k)2+(2C3-2C22)e(k)3+(5C23-4C2C3-3C3C2+3C4{C23})e(k)4]+O(e(k)5).
Analogously, we obtain the expression ofz(k)-x¯. Given that the kth iteration of Traub's scheme is
(31)z(k)=y(k)-[F′(x(k))]-1F(y(k)),
then
(32)z(k)-x¯=2C22e(k)3+(-9C23+4C2C3+3C3C2)e(k)4+O(e(k)5).
Besides, the expression ofF′(z(k)) is
(33)F′(z(k))=F′(x¯)[I+2C2(z(k)-x¯)]+O(e(k)5),
or, equivalently from (32),
(34)F′(z(k))=F′(x¯)[I+4C23e(k)3+(-18C24+8C22C3+6C2C3C2)e(k)4]+O(e(k)5).
So,(35)[F′(z(k))]-1=[I+W2e(k)+W3e(k)2+W4e(k)3+W5e(k)4]×[F′(x¯)]-1+O(e(k)5),
and provided that [F′(z(k))]-1F′(z(k))=I, solving the linear system of equations involved, we have W2=W3=0, W4=-4C23, and W5=18C24-8C22C3-6C2C3C2, so
(36)[F′(z(k))]-1=[I-4C23e(k)3+(18C24-8C22C3-6C2C3C2)e(k)4]×[F′(x¯)]-1+O(e(k)5).
Then,(37)[F′(z(k))]-1F(y(k))=C2e(k)2+2(C3-C22)e(k)3+(5C23-4C2C3-3C3C2+3C4)e(k)4+O(e(k)5).
Finally, by replacing (28) and (37) in the iterative expression (24), we obtain the error equation
(38)e(k+1)=x(k+1)-x¯=y(k)-x¯-[F′(z(k))]-1F(y(k))=-C23e(k)4+O(e(k)5),
and the proof of the theorem is completed.


## 3.2. A Fifth-Order Method

In this section, we show a new method for solving nonlinear systems that we callM5, which is obtained by combining again Newton and Traub's methods but in a different way. Its iterative expression is
(39)z(k)=x(k)-F′(x(k))-1(F(x(k))+F(y(k))),x(k+1)=z(k)-[F′(y(k))]-1F(z(k)),
where y(k) is the kth iteration of Newton's method. We prove in the next result that the convergence order of this method is five.Theorem 4.
LetF:D⊆ℝn→ℝn be sufficiently differentiable at each point of an open neighborhood D of  x¯∈ℝn that is a solution of the nonlinear system F(x)=0. Let one suppose that F′(x) is continuous and nonsingular in x¯. Then, the sequence {x(k)}k≥0 obtained by using the iterative expression (39) converges to x¯ with order five. The error equation is
(40)e(k+1)=4C24e(k)5+O(e(k)6),
where Ck=(1/k!)[F′(x¯)]-1F(k)(x¯),k=2,3,…, and e(k)=x(k)-x¯.Proof.
Following the procedure used in Theorem3, we have that
(41)F(y(k))=F′(x¯)[C2e(k)2+(2C3-2C22)e(k)3+(5C23-4C2C3-3C3C2+3C4)e(k)4+(-6C32-12C24+10C22C3+8C2C3C2+6C3C22-6C2C4-4C4C2+4C5)e(k)5]+O(e(k)6),(42)z(k)-x¯=2C22e(k)3+(-9C23+4C2C3+3C3C2)e(k)4+(30C24-18C22C3+6C32-12C3C22-14C2C3C2+6C2C4+4C4C2{C22})e(k)5+O(e(k)6).
On the other hand,(43)F(z(k))=F′(x¯)[(z(k)-x¯)]+O(e(k)4),(44)[F′(y(k))]-1=[I+X2(y(k)-x¯)+X3(y(k)-x¯)2]×[F′(x¯)]-1+O(e(k)5).
Finally, by replacing (42) and (44) in the iterative expression (39), we obtain the error equation
(45)e(k+1)=x(k+1)-x¯=z(k)-x¯-[F′(y(k))]-1F(z(k))=4C24e(k)5+O(e(k)6),
and the proof of the theorem is completed.


## 3.3.Pseudocomposition

In [25] a technique called pseudocomposition that uses a known method as a predictor and the Gaussian quadrature as a corrector was introduced. The order of convergence of the resulting scheme depends, among other factors, on the order of the last two steps of the predictor. Following this idea, we generalize the procedure used to design method M5.Then, we can establish the next result.Theorem 5.
LetF:D⊆ℝn→ℝn be sufficiently differentiable at each point of an open neighborhood D of  x¯∈ℝn that is a solution of the nonlinear system F(x)=0. Let one suppose that F′(x) is continuous and nonsingular in x¯. Let y(k) be the kth iteration of an iterative method of order q and z(k) the kth iteration of an iterative method of order p, with p≥q. The sequence {x(k)}k≥0 obtained by the iterative expression
(46)x(k+1)=z(k)-[F′(y(k))]-1F(z(k)),
converges to x¯ with the order of convergence p+q.Proof.
Taylor’s expansions ofy(k) and z(k) are
(47)y(k)=x¯+M1e(k)q+M2e(k)q+1+⋯+Mp+1e(k)q+p+O(e(k)p+q+1),z(k)=x¯+N1e(k)p+N2e(k)p+1+⋯+Nq+1e(k)p+q+O(e(k)p+q+1).
Taylor’s expansion ofF(z(k)) around x¯ gives
(48)F(z(k))=F′(x¯)[z(k)-x¯+C2(z(k)-x¯)2]+O(e(k)2(p+q)+1)=F′(x¯)[N1e(k)p+N2e(k)p+1+⋯+Nq+1e(k)p+q+C2(N1e(k)p+N2e(k)p+1+⋯+Nq+1e(k)p+q)2]+O(e(k)2(p+q)+1),
where Ck=(1/k!)[F′(x¯)]-1F(k)(x¯),k=2,3,…, and e(k)=x(k)-x¯. On the other hand, we have that
(49)[F′(y(k))]-1=[I+X2(y(k)-x¯)+X3(y(k)-x¯)2]×[F′(x¯)]-1+O(e(k)2q+1)=[I+X2(M1e(k)q+M2e(k)q+1+⋯+Mp+1e(k)q+p)+X3(R1e(k)2q+⋯)]×[F′(x¯)]-1+O(e(k)m),
where m=min{p+q+1,2q+1}=p+q+1. Finally, by replacing (47), (48), and (49) in the iterative expression (46), we obtain the error equation
(50)e(k+1)=x(k+1)-x¯=z(k)-x¯-[F′(y(k))]-1F(z(k))=2C2M1N1e(k)p+q+O(e(k)p+q+1).
Then, the convergence order of the method that results from this combination of a method of orderq with another of order p with p≥q is p+q.


## 4. Numerical Results

Numerical computations have been carried out using variable precision arithmetic, with 2000 digits of mantissa, in MATLAB 7.1. The stopping criterion has been||x(k+1)-x(k)||+||F(x(k+1))||<10-250, and therefore, we check that the iterate sequence converges to an approximation of the solution of the nonlinear system. For every method, we count the number of iterations needed to reach the wished tolerance, and we calculate the approximated computational order of convergence ACOC, the efficiency index I, the computational index CI, and an error estimation made with the last values of ||x(k+1)-x(k)|| and ||F(x(k+1))||.


### 4.1. Numerical Results Obtained with Academic Nonlinear Systems

Now, we are going to compareM4, M5, and Newton (N) and Sharma’s (S) schemes with some nonlinear academic systems in order to prove the effectiveness and the computational order of convergence of the methods developed in this work. The test systems used are as follows:(a)
F(x1,x2)=(exp(x12)-exp(2x1),x1-x2),x¯=(2,2)T,(b)
F(x1,x2)=(x1+exp(x2)-cos(x2),3x1-x2-sin(x2)),x¯=(0,0)T,(c)
F(x)=(f1(x),f2(x),…,fn(x)), where x=(x1,x2,…,xn)T and fi:ℝn→ℝ,i=1,2,…,n such that
(51)fi(x)=xixi+1-1,i=1,2,…n-1,fn(x)=xnx1-1.
When n is odd, the exact zeros of F are x¯1=(1,1,…,1) and x¯2=(-1,-1,…,-1).In Table1, we can find a comparative among the different numerical methods for the nonlinear systems (a), (b), and (c). As we can see, the approximated computational orders of convergence are the expected ones, and methods M4 and M5 are clearly very competitive in terms of error estimation.Table 1
Comparative of the iterative methods with nonlinear systems (a) to (c).
Function
x
(
0
)
Method
Iter
ACOC
|
|
x
(
k
+
1
)
-
x
(
k
)
|
|
|
|
F
(
x
(
k
+
1
)
)
|
|
(a)
(
2,2
)
T
N
13
2
0.163
e
-
338
0
S
7
4
0.962
e
-
270
0
M
4
7
4
0.140
e
-
805
0
M
5
7
5
0.893
e
-
831
0
(b)
(
-
0.1
,
-
0.1
)
T
N
9
2
0.94
e
-
307
0.28
e
-
921
S
5
4
0.53
e
-
276
0.83
e
-
1106
M
4
5
4
0.98
e
-
300
0.32
e
-
1801
M
5
5
5
0.435
e
-
647
0.1
e
-
3941
(c)n=99
(
2,2
,
…
,
2
)
T
N
11
2
0.535
e
-
488
0.286
e
-
976
S
6
4
0.113
e
-
408
0.960
e
-
1636
M
4
6
4
0.380
e
-
704
0
M
5
6
5
0.122
e
-
1201
0The efficiency index,I, and the computational index, CI, of the different methods are as follows:
(52)IN=21/(n+n2),IS=41/(n+2n2),IM4=41/(2n+2n2),IM5=51/(3n+2n2),CIN=23/(n3+3n2-n),CIS=43/(2n3+15n2-2n),CIM4=43/(2n3+6n2-2n),CIM5=53/(2n3+6n2-2n).In Figures2 and 3, we show these efficiency indices for n=2,3,…,10. It can be concluded that our methods improve Sharma's scheme in terms of CI, although the classical efficiency of Sharma's procedure is better for n≤6. M4 and M5 are competitive, obtaining better error estimation than N and S, with the same number of iterations.Figure 2
Comparative among the efficiency indices of the methods.Figure 3
Comparative among the computational indices of the methods.


### 4.2. Numerical Results for the GPS Problem

In order to test the proposed schemes on the problem of a user position of a GPS device, we have requested to the Cartographic Institute of Valencia to provide us with data of known geocentric coordinates.Concretely, the Cartographic Institute of Valencia provided us with the following:(i)
an example of a fixed-point GPS in the geocentric coordinates:x=4984687,426, y=-41199,155, and z=3966605,952. It is a point located in Alcoy (Alicante, Spain),(ii)
observations from that fixed point (file *.09o) for a day,(iii)
positions of the satellites for that day:*.09n and *.sp3 files,(iv)
description of RINEX format (*.09o file):http://www.igs.org/components/formats.html(v)
description of the ephemeris file and satellite positions sp3:http://igscb.jpl.nasa.gov/igscb/data/format/sp3c.txt(vi)
link to other libraries for analysis calculations:http://www.ngs.noaa.gov/gps-toolbox/exist.htm.With these data, we obtain the positions of the visible satellites in the instant that corresponds to the provided data. With these coordinates, we calculate the approximated pseudoranges for every satellite, and then we are able to build the nonlinear system of equations of GPS (18) using four of the satellites, with which we check the iterative methods of Newton, Sharma, M4, and M5.In Table2, we can find a comparative among the iterative methods N, S, M4, and M5 for the nonlinear system of the GPS. We recall that the coordinates of the center of the Earth and bu=0, that is, x(0)=(0,0,0,0)T, are usually used as initial estimation. Despite this, we have also tested the methods with some other initial conditions. We denote that x*≈(4984687.426,-41199.155,3966605.952,and0.116e-8)T as the Earth’s solution and xs≈(-39720114.893,-16748760.539,-23938190.113,and-0.159)T as the exterior space solution.Table 2
Comparative of the iterative methods with the nonlinear system of equations of the GPS.
Method
x
(
0
)
Iter
ACOC
|
|
x
(
k
+
1
)
-
x
(
k
)
|
|
|
|
F
(
x
(
k
+
1
)
)
|
|
x
¯
N
(
0,0
,
0,0
)
T
12
2
0.6
e
-
374
0.830
e
-
739
x
*
S
7
4
0.173
e
-
767
0.2
e
-
1991
x
*
M
4
7
4
0.823
e
-
512
0.1
e
-
1991
x
*
M
5
7
5
0.222
e
-
814
0.3
e
-
1991
x
s
N
(
1
0
6
,
1
0
6
,
1
0
6
,
1
0
6
)
T
15
2
0.421
e
-
317
0.537
e
-
627
x
s
S
8
4
0.739
e
-
799
0.1
e
-
1991
x
*
M
4
7
4
0.191
e
-
735
0
x
*
M
5
8
5
0.104
e
-
563
0.1
e
-
1991
x
s
N
(
-
1
0
4
,
-
1
0
4
,
-
1
0
4
,
-
1
0
4
)
T
12
2
0.371
e
-
381
0.317
e
-
753
x
*
S
7
4
0.138
e
-
784
0.3
e
-
1991
x
*
M
4
7
4
0.704
e
-
520
0
x
*
M
5
7
4.9968
0.510
e
-
692
0.1
e
-
1991
x
sAs we can see, for this particular system of equations, Newton's method does not converge to the user position for all the initial estimations, so doesM5, but M4 is a good method in all senses, very competitive in respect of known methods.


## 4.1. Numerical Results Obtained with Academic Nonlinear Systems

Now, we are going to compareM4, M5, and Newton (N) and Sharma’s (S) schemes with some nonlinear academic systems in order to prove the effectiveness and the computational order of convergence of the methods developed in this work. The test systems used are as follows:(a)
F(x1,x2)=(exp(x12)-exp(2x1),x1-x2),x¯=(2,2)T,(b)
F(x1,x2)=(x1+exp(x2)-cos(x2),3x1-x2-sin(x2)),x¯=(0,0)T,(c)
F(x)=(f1(x),f2(x),…,fn(x)), where x=(x1,x2,…,xn)T and fi:ℝn→ℝ,i=1,2,…,n such that
(51)fi(x)=xixi+1-1,i=1,2,…n-1,fn(x)=xnx1-1.
When n is odd, the exact zeros of F are x¯1=(1,1,…,1) and x¯2=(-1,-1,…,-1).In Table1, we can find a comparative among the different numerical methods for the nonlinear systems (a), (b), and (c). As we can see, the approximated computational orders of convergence are the expected ones, and methods M4 and M5 are clearly very competitive in terms of error estimation.Table 1
Comparative of the iterative methods with nonlinear systems (a) to (c).
Function
x
(
0
)
Method
Iter
ACOC
|
|
x
(
k
+
1
)
-
x
(
k
)
|
|
|
|
F
(
x
(
k
+
1
)
)
|
|
(a)
(
2,2
)
T
N
13
2
0.163
e
-
338
0
S
7
4
0.962
e
-
270
0
M
4
7
4
0.140
e
-
805
0
M
5
7
5
0.893
e
-
831
0
(b)
(
-
0.1
,
-
0.1
)
T
N
9
2
0.94
e
-
307
0.28
e
-
921
S
5
4
0.53
e
-
276
0.83
e
-
1106
M
4
5
4
0.98
e
-
300
0.32
e
-
1801
M
5
5
5
0.435
e
-
647
0.1
e
-
3941
(c)n=99
(
2,2
,
…
,
2
)
T
N
11
2
0.535
e
-
488
0.286
e
-
976
S
6
4
0.113
e
-
408
0.960
e
-
1636
M
4
6
4
0.380
e
-
704
0
M
5
6
5
0.122
e
-
1201
0The efficiency index,I, and the computational index, CI, of the different methods are as follows:
(52)IN=21/(n+n2),IS=41/(n+2n2),IM4=41/(2n+2n2),IM5=51/(3n+2n2),CIN=23/(n3+3n2-n),CIS=43/(2n3+15n2-2n),CIM4=43/(2n3+6n2-2n),CIM5=53/(2n3+6n2-2n).In Figures2 and 3, we show these efficiency indices for n=2,3,…,10. It can be concluded that our methods improve Sharma's scheme in terms of CI, although the classical efficiency of Sharma's procedure is better for n≤6. M4 and M5 are competitive, obtaining better error estimation than N and S, with the same number of iterations.Figure 2
Comparative among the efficiency indices of the methods.Figure 3
Comparative among the computational indices of the methods.


## 4.2. Numerical Results for the GPS Problem

In order to test the proposed schemes on the problem of a user position of a GPS device, we have requested to the Cartographic Institute of Valencia to provide us with data of known geocentric coordinates.Concretely, the Cartographic Institute of Valencia provided us with the following:(i)
an example of a fixed-point GPS in the geocentric coordinates:x=4984687,426, y=-41199,155, and z=3966605,952. It is a point located in Alcoy (Alicante, Spain),(ii)
observations from that fixed point (file *.09o) for a day,(iii)
positions of the satellites for that day:*.09n and *.sp3 files,(iv)
description of RINEX format (*.09o file):http://www.igs.org/components/formats.html(v)
description of the ephemeris file and satellite positions sp3:http://igscb.jpl.nasa.gov/igscb/data/format/sp3c.txt(vi)
link to other libraries for analysis calculations:http://www.ngs.noaa.gov/gps-toolbox/exist.htm.With these data, we obtain the positions of the visible satellites in the instant that corresponds to the provided data. With these coordinates, we calculate the approximated pseudoranges for every satellite, and then we are able to build the nonlinear system of equations of GPS (18) using four of the satellites, with which we check the iterative methods of Newton, Sharma, M4, and M5.In Table2, we can find a comparative among the iterative methods N, S, M4, and M5 for the nonlinear system of the GPS. We recall that the coordinates of the center of the Earth and bu=0, that is, x(0)=(0,0,0,0)T, are usually used as initial estimation. Despite this, we have also tested the methods with some other initial conditions. We denote that x*≈(4984687.426,-41199.155,3966605.952,and0.116e-8)T as the Earth’s solution and xs≈(-39720114.893,-16748760.539,-23938190.113,and-0.159)T as the exterior space solution.Table 2
Comparative of the iterative methods with the nonlinear system of equations of the GPS.
Method
x
(
0
)
Iter
ACOC
|
|
x
(
k
+
1
)
-
x
(
k
)
|
|
|
|
F
(
x
(
k
+
1
)
)
|
|
x
¯
N
(
0,0
,
0,0
)
T
12
2
0.6
e
-
374
0.830
e
-
739
x
*
S
7
4
0.173
e
-
767
0.2
e
-
1991
x
*
M
4
7
4
0.823
e
-
512
0.1
e
-
1991
x
*
M
5
7
5
0.222
e
-
814
0.3
e
-
1991
x
s
N
(
1
0
6
,
1
0
6
,
1
0
6
,
1
0
6
)
T
15
2
0.421
e
-
317
0.537
e
-
627
x
s
S
8
4
0.739
e
-
799
0.1
e
-
1991
x
*
M
4
7
4
0.191
e
-
735
0
x
*
M
5
8
5
0.104
e
-
563
0.1
e
-
1991
x
s
N
(
-
1
0
4
,
-
1
0
4
,
-
1
0
4
,
-
1
0
4
)
T
12
2
0.371
e
-
381
0.317
e
-
753
x
*
S
7
4
0.138
e
-
784
0.3
e
-
1991
x
*
M
4
7
4
0.704
e
-
520
0
x
*
M
5
7
4.9968
0.510
e
-
692
0.1
e
-
1991
x
sAs we can see, for this particular system of equations, Newton's method does not converge to the user position for all the initial estimations, so doesM5, but M4 is a good method in all senses, very competitive in respect of known methods.


## 5. Conclusions

In this paper, we have gone in depth on an emerging line of investigation, the GPS receivers software improvement. Concretely, GPS receivers currently use Newton's method to solve the nonlinear system (18) and to calculate their exact position with the information obtained from signals received from the GPS constellation of satellites. We propose two different combinations of Newton method and Traub's methods, obtaining two methods of fourth- (M4) and fifth-order (M5). Using the idea presented in [25], called pseudocomposition, it is proved that combining in a particular way two methods of order p and q, respectively, with p≥q, the order of convergence of the resulting scheme is p+q. We have numerically compared the different methods, and we have concluded that M4 and M5 are very competitive in terms of the error estimation.



---

*Source: 586708-2013-05-13.xml*