ASSIGNMENT
I am seeking for assistance from an expert to modify the Broyden’s Class Method with the aim of making it more efficient to solve system of nonlinear equations better than the already existing ones.
I guide to doing this is to find a good method to estimate the inverse Jacobian which is a problem for me. Expert can use any kind of procedure to improve the Broyden method and that will be fine with me.
Please find below a brief literature on Broyden’s method
7.4 Broyden’s Method
A careful study of Newton Raphson method as reported earlier, revealed that a major disadvantage of the method has is the computation of the Jacobian matrix and its inverse at each iterative step, hence the only way to avoid this problem will be to employ the use of Quasi-Newton methods.
Quasi-Newton methods are methods which approximate the Jacobian matrix or its inverse with another matrix (i.e. . A very popular Quasi-Newton method is the Broyden’s method which was proposed by Charles Broyden in 1965 (Broyden, 1965). The iterative procedure involved in Broyden’s method is similar to that used in Newton Raphson method. The only difference is that an approximated matrix is used instead of .
According to Charles Broyden, (1965), there are two methods that can be used to find the approximate solution for nonlinear systems of equations as reported in Al-Towaiq, et al., (2017). The first method gives an approximate matrix for using the following assumption;
must satisfy the secant equation
where . However, Broyden’s method involves the computation of and not , this brings our attention to the next theorem.
THEOREM: (Sherman-Morrison Formula) If is a nonsingular matrix and are vectors, then is nonsingular provided that and
The theorem above is a matrix inverse formula (Deng, 2011). It allows to be computed directly using , rather than computing and then its inverse at each iteration. Hence using the theorem and setting , , as well as using as defined above we have that
Hence we get
From the assumption above, Broyden’s method is defined as
where is computed using equation (14).
Below is the Broyden’s method algorithm:
STEP 1: Let be the initial vector given.
STEP 2: Calculate
STEP 3: In this step we compute . Because we do not have enough information to compute directly, Broyden’s method permits us to let , which implies that .
STEP 4: Calculate
STEP 5: Calculate
STEP 6: Take and and calculate . Next take the first two iterations of and calculate .
STEP 7: Calculate
STEP 8: Compute
STEP 9: Take that we found in step 8, and calculate
STEP 10: Repeat the process until it converges at , i.e. when . This will indicate that we have reached the solution of the system.
Broyden’s method as well as all of the Quasi-Newton methods converge superlinearlly, this means that
where is the solution to , and are successive approximations to . This can be proved in a similar manner that proved the convergence of Newton’s method.
An advantage of Broyden’s method is the reduction in computations. More specifically, the way the inverse of the approximation matrix, reduces the number of computations needed for this method in comparison to Newton Raphson method. However, the following can be said about its disadvantages:
- It does not converge quadratically.
- It does not correct itself for round off errors.
3.1 Broyden’s Class Methods with Central Finite Difference (BC)
According to Al –Towaiq et al, (2017), the “Broyden’s method” is described to be an effective method for nonlinear system of equations, which is also called the “Quasi Newton method” (Goodwin and Kuprov, 2016). In this method there is the description of the “nonlinear system of equation” which is the iterative method, the
“Nonlinear system of equation” is, for
To find the “exact solution” we compute the equation for, .
Here, is the “Jocobian matrix” of F(x), So,
To be able to formulate the “Broyden’s method”, it is very important to have an “approximation matrix” which will be defined as. To perform this approximation there is the need to use the “secant equation”,
Here, ,
This is the first condition in the “Broyden’s method” which does not depend on the direction. Again, q = q, for all q belongs to the set of real numbers (Iwamura et al. 2018). This is the second condition for the given problem, hence combining both of them we have,
Where,
Which represents Broyden’s Class 1 (BC1) method.
In the above method, there is the need for “approximation of the Jacobian matrix”, Broyden (1965), using the forward finite difference to approximate the jacobian matrix, that is
According to Al –Towaiq, (2017), using the “central finite difference”, gives;
This approach leads to a solution for the Modified “Broyden’s classes” for the “Central finite differences”. So “Taylor’s expansion” is needed to prove convergence of the theorem or to find out the “order of the convergence” (Mumtazet al. 2015).
According to the “taylor’s expansion”,
From both of the above equations, , this equation is replaced by 2h
This changes the two conditions of Broyden’s method to become:
- Central secant equation 2h.
- No change condition q = q
Now to find out the value of , we start with the following assumptions, and, = 2h, then
And
So from the above two conditions, we have the equation,
=
this represents the Broyden’s Class 2 (BC2) method.
Here, we use the “Sherman-Morrison” formula to make the above equation to depend on the “inverse of the”,
This verifies the various data according to the given information for further implementation of the problem (Saab and Saab, 2015), that is
=
To this end, this research would consider using the “Central Finite Differences” to modify Broyden’s Classes with the aim of reducing the computational error associated with the classes of Broyden’s methods.
The post modify the Broyden’s Class Method appeared first on My Assignment Online.
