As described in the previous chapter, a nonlinear equation is an equation that has one or more nonlinear terms in its expression, or an equation that is not in the form of Equation (5.1). In its general form, a nonlinear equation involving n variables, x₁, x₂, x₃,...,x_n, can be expressed as

Equation 6.1. 

Some examples of nonlinear equations are given below:

3 — 3x2 + x3 = −2,	nonlinear because of the presence of nonlinear terms x2 and x 3.
x + sin y = −1,	nonlinear because of the presence of nonlinear term sin y.
xy = −1	nonlinear because the sum of indices in the variable term is 2.
	nonlinear because variable x is in the denominator.

Finding the root(s) of a nonlinear equation is one of the most fundamental problems involving nonlinear equations. The problem is stated as follows:

Given a function f(x) where f(x)= 0 exists, find the value of x.

Alternatively, the problem is also called finding the zeros of a function. Graphically, this problem can be described as finding one or more points along the x -axis where the curve f (x) crosses, provided the value(s) exist. Very often, f (x) does not cross the x -axis. In this case, f (x) is said to have no real root.

Several theorems have been documented to help in finding the zeros of a function.

Theorem 6.1. Intermediate-Value Theorem. Given a function f (x) continuous in [a, b] and a number C, where f(a) ≤ C ≤ f(b), then a number p ɛ (a,b) exists such that f(c) = C.

Theorem 6.2. Mean-Value Theorem. A function f(x) that is continuous in [a, b] is said to have at least one root in this interval if f(a) f(b) < 0.

The intermediate-value theorem and the mean-value theorem guarantee at least one root exists in the interval [a, b] for f(x) if f(a)f(b) < 0. However, it does not assume the uniqueness of the solution. f(a)f(b) < 0 suggests one of the terms in f(a) or f(b) is positive and the other is negative. This suggestion implies the positive term lies above the x -axis, whereas the negative term is located below the axis. Therefore, the curve must cross the x -axis at least once along the path from (0, f(a)) to (0, f(b)). This is illustrated in Figure 6.1.

In this chapter, we will concentrate on the case of finding a unique root for f(x) given the solution exists. We will discuss five methods based on iterations, namely, the bisection, false position, Newton-Raphson, secant, and fixed-point methods. In each method, we will emphasize on the construction of C++ code in solving the problem and on the development of its Windows interface. All these methods are summarized in Table 6.1 for their brief description.

Figure 6.1. Mean-value theorem illustration of curves with one root (left) and three roots (right).

An iterative technique for finding the zeros of an equation can be classified as either the closed or the open interval approach. A closed interval means the final solution is confined to within the given initial interval, whereas an open interval does not limit the solution to be within this range.

In the closed interval approach, an interval x ɛ [a₀,b ₀] that contains at least one root is identified using the mean-value theorem. The two initial values, a₀ and b₀, serve as the left and right points in the interval. The size of this initial interval is reduced gradually through successive iterations to[a₁, b₁], [a₂, b₂], and so on until the solution converges to an acceptable value x* based on a stopping condition. This final value is then the final solution to the problem. The beauty of the closed interval approach is convergence to x* is guaranteed through the mean-value theorem. Some well-known methods in the closed interval approach are the bisection and false position methods.

In the open interval approach, an initial value x₀ is selected as the starting value for x in the iteration. This value is a guess value that should not be far from the solution. A good guess for this value is either a₀ or b₀ in the interval x ɛ [a₀, b₀] using the mean-value theorem. The interval for the convergence is said to be open in this approach as the generated values are not bound to be within a specified range. Successive iterations are then performed on the initial value, which eventually leads to convergence to its solution after a stopping condition has been reached. The Newton-Raphson, secant and fixed-point iteration methods are some of the most common methods in the open interval approach.

The bisection method is based on a closed interval that produces a solution by reducing the interval size successively into a tolerable value through a series of iterations. The iterations start at interval x ε [a₀, b₀] whose end points x = a₀ and x = b₀ are any values that comply with the mean-value theorem requirement, or f (a₀) f (b₀) < 0.

Figure 6.2. Bisection method.

Figure 6.2 illustrates the bisection method showing the shrinking intervals after four successive iterations. At each iteration i, the size of the interval x ɛ [a_i, b_i] from the end points a_i and b_i is reduced into half by updating one of the two end points with the value of the interval midpoint, given by

Equation 6.2. 

The update is performed by looking at the sign of f (a_i)f (c_i) to quickly determine the rough location of the root. A value of f (a_i) f (c_i) < 0 suggests the root lies in x ɛ [a_i, c_i], definitely not in [c_i, b_i]. Therefore, the end point b_{i +1} is updated with the value of c_i, whereas a_{i +1} takes on a_i, or b_{i +1} = c_i and a_{i +1} = a_i, respectively. In a similar note, f (a_i)f (c_i) > 0 suggests the root lies in x ε [c_i, b,_i] not in x ɛ [a_i, c_i]. In this case, a_{i +1} = c_i and b_{i +1} = b_i. In a unique case where f (a_i)f (c_i) = 0, the solution has been reached with x* = c_i as the root of f(x).

The update on the end points of the intervals has the effect of narrowing down the search area to the stage where the difference between the end points is very small. An error given by e = |c_i − c_i − ₁| for i > 0 is computed at each iteration. This error value is compared with a presetsmall value ε to determine whether the iterations are continued or stopped. The iterations are continued if e > ε, which suggests convergence to the solution is not reached yet. Convergence is said to have been reached if e ≤ ε, and the whole operation is stopped immediately. The final value of c_i obtained from the last iteration then becomes the desired solution.

Algorithm 6.1 summarizes the computational steps in the bisection method. It is important to set the maximum number of iterations max to be a reasonable number such as 20. Depending on the value ε, convergence to the solution is normally reached before this number.

Bisection Method.

Given f(x) = 0, ε and the initial end points [a₀, b₀], where f (a₀)f(b₀) < 0;

Given max =maximum number of iterations;

For i = 0 to max

Compute

If f (a_i)f (c_i) < 0

Update b_{i +1} = c_i and a_{i +1} = a_i;

If f (a_i)f (c_i) > 0

Update a_{i +1} = c_i and b_{i +1} = b_i;

If |c_i − c_i −₁| < ε

Solution= c_i;

Stop the iterations:

End for

Figure 6.3 shows a schematic flowchart of the bisection method. The iterations are performed as long as the computed error at each iteration, e = |c_i − c_i −₁|, is less than ε. There are also other ways to determine the error, including e = |b_i − a_i|, or e = |f (c_i)|.

Example 6.1. Find the root of f(x) = x³ − x² − 2 using the bisection method, given the initial values of a₀ = 1 and b₀ = 2 with iterations until |c_i − c_i −1| < ε, where ε = 0.005.

Solution. A quick check confirms f(a₀)f(b₀) = f (1)f (2) < 0. Therefore, at least one root lies inside x ɛ [1, 2]. At i = 0, a₀ = 1 and b₀ = 2, and this produces c₀ =

At i = 1, a₁ = 1.5 and b₁ = 2. This gives

Table 6.2 shows the results after eight iterations, which eventually leads to convergence when the error is smaller than ε. The final solution is x* = c₇ = 1.699219, which is obtained at i = 7 when |c₇ − c₆| = 0.003906 < ε.

Figure 6.3. Schematic flowchart of the bisection method.

The false position method is based on a linear interpolation of the two end points of the interval for approximating the root. The method starts with the end points a₀ and b₀ in the interval [a₀,b ₀], where f (a₀) f (b₀) < 0. The gradient of the secant line from (a₀, f (a₀)) to (c₀, 0) is given by

Equation 6.3. 

whereas the gradient from the straight line from (c_0,0) to (b₀,f (b₀)) is

Equation 6.4. 

Since the two lines above are colinear, or m₁ = m₂,

Equation 6.5. 

Simplify the above equation, we get

Equation 6.6. 

and this equation generalizes to

Equation 6.3. 

Figure 6.4 illustrates the false position method. a₀ and b₀ are two guess values that make up the initial interval [a₀, b₀] that is derived from the condition in the mean-value theorem. A secant line is drawn from (a₀, f (a₀)) to (b₀, f(b₀)). Clearly, this line intersects the x -axis at (c₀,0). After finding c₀ using Equation (6.3), the interval [a₀, b₀] is divided into [a₀, c₀] and[c₀, b₀]. If f (a₀)f(c₀) < 0, the root is in [a₀, c₀]. An update is performed with b₁ = c₀ and a₁ = a₀. If f (a₀) f (c₀) > 0, then the update involves a₁ = c₀ and b₁ = b₀ since the root lies in [c₀, b₀]. The iterations continue with i = 1, and so on, until the stopping criterion is met. The same rule for the stopping criterion as in the bisection method applies, and the iterations stop once the error is smaller than ε. In the case of f (a_i)f (c_i) = 0, c_i becomes the solution and the iteration is stopped immediately.

Figure 6.4. False position method.

Algorithm 6.2 summarizes the computational steps in the false position method. Obviously, the steps are similar to those in Algorithm 6.1 with the difference in the update formula for c_i only.

False Position Method.

Given f(x) = 0, ε and the initial end points [a₀, b₀] where f (a₀)f (b₀) <0;

Given max =maximum number of iterations;

For i = 0 to max

Compute

If f (a_i)f (c_i) < 0

Update b_i+₁ = c_i and a_{i +1} = a_i;

Endif

If f (a_i) f (c_i) < 0

Update a_{i +1} = c_i and b_{i +1} = b_i;

Endif

If |c_i − c_i−1| < ε

Solution= c_i;

Stop the iterations;

Endif

Endfor

Example 6.2. Find the root of f(x) = x³ — x² — 2 using the false position method, given the initial values of a₀ = 1 and b₀ = 2, and the error |c_i — c_i −₁| < ε, where ε = 0.005.

Solution. At i = 0, a₀ = 1 and b₀ = 2. We obtain f (a₀) = f (1) = −2 and f (b₀) = f (2) = 2. This gives

At i = 1, a₁ = 1.5 and b₁ = 2. This gives f (a₁) = f (1.5) = −0.875 and f(b₁) = f (2) = 2. We get

The iterations continue until i = 4, where |c₄ — c₃| = 0.001465 < ε. This produces the final solution with x * = c₄ = 1.695246. The full results are shown in Table 6.3.

The Newton-Raphson method is an open interval method that requires one initial value. This iterative method is based on a tangent line at the approximated point that provides an update at the point where this line intersects the x -axis. An initial point is any guess value that is not far from the solution. A good guess value will be x₀ = a or x₀ = b from the mean-value theorem condition, f (a₀)f (b₀) < 0. This theorem is not required in the Newton-Raphson method, but it provides a good starting point for the iterations, which contributes in faster convergence to the solution.

Figure 6.5 shows a situation for finding a root of the function f(x) with x = x₀ as the initial value. A tangent line is drawn from the point (x₀, f(x₀)), which intersects the x -axis at (x₁, 0). The value x = x₁ is the new value at iteration i = 0. At i = 1, another tangent line is drawn from (x₁, f(x₁)), which intersects the x -axis at (x₂, 0)to produce an improved value of x = x₂. The same step is repeated for i = 2, 3,... until the error given by e = |x_i+1 — x_i| is smaller than a preset value ε. The final value of x is obtained at the last iteration where e < ε becomes the solution to the problem.

The formula for the Newton-Raphson method is derived by looking at the tangent line to the point (x₀, f (x₀)). The gradient of this tangent line is f (x₀), which can also be expressed as

Equation 6.8. 

Figure 6.5. Newton—Raphson method.

The above equation is simplified further to produce

Equation 6.9. 

This equation is generalized to produce the Newton—Raphson update formula, as follows:

Equation 6.4. 

The computational steps in the Newton-Raphson method are summarized in Algorithm 6.3. The algorithm requires both f(x) and f'(x).

The Newton-Raphson Method.

Given f(x) = 0, ε and the initial point x₀;

Given max=maximum number of iterations;

Find f'(x);

For i = 0 to max

Compute

If |x_i +₁ — x_i| < ε

Solution= x_i+₁;

Stop the iterations;

Endif

Endfor

Example 6.3. Use the Newton-Raphson method to find the root of f(x)= x³ − x² − 2, given the initial value of x₀ = 1 with iterations until |x_i − x_i−₁| < ε, where ε = 0.005.

Solution. With f(x) = x³ − x² — 2 we have f'(x) = 3x² — 2x. At i = 0, x₀ = 1 and we have x₁ = x₀ —

The iterations stop at i = 5, where |x₆ — x₅| = 0.000 < ε, and this produces the final solution, x* = x₆ = 1.695621. Table 6.4 shows the full results from the iterations.

One big difficulty with the Newton-Raphson method is in finding the derivative of f(x) at the iterated points. This requirement adds to the overhead on the computer, and it may also add to the computational cost in solving the problem. An alternative approach is provided in the form of the secant method, which eliminates the derivative by replacing it with a secant line.

We refer to Figure 6.6 to illustrate the method. The secant method starts with two initial guess points x₀ and x₁, where f (x₀) ≠ f(x ₁). These two points can be any points that are reliably close to the solution, and they do not have to be on the opposite sides of the x -axis. A good choice for the two initial points will be x₀ = a and x₁ = b, which are the end points in the interval [a, b] that abides the mean-value theorem requirement, f (a)f (b) < 0.

The first iteration with i = 0 produces an approximation at x = x₂, which is the x-intercept of the chord that passes through the points (x₀,f (x₀)) and (x₁, f (x₁)). Similarly, the next approximated value x = x₃ is obtained from the x-intercept of the chord that passes through the points (x₁,f (x₁)) and (x₂,f (x₂)). The same step is repeated until convergence to the solution is reached through the stopping condition e = |x_i +₂ — x_{i +1}| < ε.

Figure 6.6. Secant method.

The iterative formula is derived by referring to Figure 6.6. The gradient of the line from (x₀,f (x₀)) to (x₂, 0) is given by

Equation 6.11. 

which equals the gradient of the line from (x₁,f (x₁)) to (x₂, 0), given by

Equation 6.12. 

The above equation is further simplified, as follows:

Equation 6.13. 

This produces

Equation 6.14. 

Replacing x₀ with x_i, x ₁ with x_{i +1} and x₂ with x_{i +2} in the above equation, we obtain the iterative formula for the secant method:

Equation 6.5. 

The computational steps in the secant method are summarized in Algorithm 6.4.

Secant Method.

Given f (x) = 0, ε and two initial points, x₀ and x₁;

Given max=maximum number of iterations;

For i = 0 to max

Compute

If |x_{i +2} — x_{i +1}| < ε

Solution=x_{i +2};

Stop the iterations;

Endif

Endfor

Example 6.4. Find the root of f(x) = x³ — x² — 2 using the secant method with the initial values of x₀ = 1 and x₁ = 2. Perform the iterations until |x_{i +2} — x_{i +1} | < ε, where ε = 0.005.

Solution. At i = 0, x₀ = 1 and x₁ = 2. We get

Figure 6.7. Reassigning the problem from f(x) = 0 to y = g(x).

Through simplification, the equation f(x) = 0 maybe rewritten as x = g(x). This relationship can be obtained by making x the subject of the new equation from f(x) = 0. This representation can be viewed as reassigning the problem into finding the intersection point between the straight line y = x and the curve y = g(x) provided the solution exists. Figure 6.7 shows this connection where g(x) is totally a different curve from f(x).

The fixed-point iteration method requires an initial point x = x ₀, which is a guess value relatively close to the root of f(x). Choosing x ₀ = a or x ₀ = b from the interval x ɛ [a, b], where f(a)f(b) < 0 is an ideal choice for this value as it is close to the solution. The reassignment from f(x) = 0 to x = g(x) gives rise to an iterative relationship given by

Equation 6.6. 

for i = 0, 1,2,....Convergence to the solution is guaranteed if the following condition is met:

Equation 6.7. 

Equation (6.7) suggests — 1 ≤ g' (x)≤1, and that the choice for the new equation x = g(x) from f(x) = 0 must strictly obey this condition. There is no guarantee for convergence to the solution if this condition is not fulfilled. Figure 6.8 illustrates a case with convergence to the solution according to x₀ → x₁ → x₂ →x₃ when the above condition is fulfilled.

The fixed-point iteration method is outlined in Algorithm 6.5. The algorithm is illustrated in Example 6.5.

Figure 6.8. Convergence in the fixed-point iteration method.

Example 6.5. Find the root of f (x) = x³ — x² — 2 using the fixed-point iteration method, given the initial value of x₀ = 1 with iterations until |x_{i +1} — x_i| < ε, where ε = 0.005.

Solution. Setting f (x) = 0 suggests several representations in the form of x = g(x), including

Starting the iterations at i = 0 with the initial value of x₁ = (x₀² + 2)^1/3 =(1² +2)^1/3 = 1.442250, with g'(x₀) = 0.320500. The error is |x₁ — x ₀| = |1.442250 − 1.000| = 0.442250 > ε.

At i =1, x₂ = (x₁² + 2)^1/3 = (1.442250² + 2)^1/3 = 1.597925 and g' (x₁)= 0.376562. The error is |x₂ — x ₁| = |1.597925 − 1.442250| = 0.155675 > ε.

Therefore, the process continues with the next iteration. The iterations stop at i = 5, where |x₆ — x₅| = 0.003568 < ε. The final solution is x* = x₆ = 1.693311. Table 6.6 shows the complete results from this method.

MFC provides a rich environment for developing a user-friendly interface for numeric-intensive calculations. In this chapter, we illustrate and discuss a Windows interface for finding the zeros of a function using four methods, namely, the bisection, false position, Newton-Raphson, and secant methods. The other method discussed in the last section, the fixed-point iteration method, is left as an exercise for the reader.

The Windows project for the nonlinear equations is codenamed Code6. Figure 6.9 shows a screen snapshot from the project that consists of an output from the bisection method. The input in this problem consists of the function f (x) = 3 sin 2x — 5cos(4x — 1) in0 ≤ x ≤ 1, and the results are displayed in the list view table and plotted as a graph. The solution to f(x) = 0 in this problem is displayed as x = 0.508761.

The displayed output is made up of four regions. The first region consists of the menu items that are located in the top left corner of the window. The second region consists of the input boxes that are located to the right of the menu items. The results from the calculations that are displayed in a list view table located below the menu items. The last region is located at the bottom, and it displays the solution curve.

The menu region consists of shaded rectangles for the bisection, secant, Newton-Raphson and secant methods. An item in the menu becomes activated from the left button click of the mouse. A click at one of these items prompts the creation of the input region. Edit boxes for input according to the selected method appear inside the input region. A push button called Compute is also displayed in the input region. A click at the push button causes the input to be read and processed. A complete input for the selected method will produce the desired results in the list view table and its corresponding graph in the curve region.

Figure 6.9. Output from the bisection method for f (x) = 3sin 2x — 5cos(4x — 1) in Code6.

Figure 6.10 shows the development stages of Code6. A Boolean flag called fStatus monitors the progress of the execution whose initial value of 0 indicates the execution is not yet complete. Another variable called fMenu (not shown in the diagram) stores a value for the selected method: with fMenu=1 for bisection, fMenu=2 for false position, fMenu=3 for Newton—Raphson, and fMenu=4 for secant. A value for fMenu is assigned inside the function OnLButtonDown(). The stage at fStatus=1 indicates the input for the selected method has been completed, and executed. The results are displayed both in the list view table and visualized as a curve with this status.

Code6 consists of two source files, Code6.cpp and Code6.h, and the object file, MyParser.obj. A single class called CCode6 is used in this application. This class is derived from MFC's CFrameWnd, which displays a single window.

Figure 6.10. Schematic drawing showing the main computational steps in Code6.

The main variables in this project are represented as four structures: PT, INPUT, MENU, and CURVE. PT defines the points based on the real coordinates, as described in Table 6.7. An array called pt defines the points in the real coordinates in PT.

typedef struct
{
      double x,y,yd1,a,b,c,error;
} PT;
PT *pt,max,min,left,right;

The number of input items varies with the methods. For example, the bisection method requires four inputs, whereas the secant method requires five. A macro called maxInput is declared to store the maximum number of input, whereas nInputItems is the actual number of inputs for the selected method. Input is made using the edit boxes, which are located in the input region. A structure called INPUT defines the edit boxes and their components, and this is described in Table 6.8.

typedef struct
{
      CString label,item;
      CPoint hm;
      CEdit ed;
      CRect rc,display;
} INPUT;
INPUT input[maxInput+1];

The menu items are organized into a structure called MENU. A macro called nMenuItems stores the number of menu items whose value is four in this project. The elements of this structure are the menu titles, their rectangular objects, and their home coordinates. The elements are described in Table 6.9.

typedef struct
{
      CString item;
      CPoint hm;
      CRect rc;
} MENU;
MENU menu [nItems+1];

A structure called CURVE organizes the generated curve so that it is confined to a rectangular region called rc. The structure has its starting point and end point represented by hm and end respectively.

typedef struct
{
      CPoint hm,end;
      CRect rc;
} CURVE;
CURVE curve;

Table 6.10 describes other main variables and objects in Code6.h. The execution of the program is monitored through the value of fStatus, where fStatus=0 is the pre-evaluation stage and fStatus=1 indicates a method has been applied to the problem. Therefore, this variable is suitable to be declared as a Boolean. fMenu is an integer variable for denoting the selected method. Stop is a variable that stores the last iteration number before convergence for all methods, whereas the last value of x from this iteration is stored as Solution, which becomes the solution to the problem.

CCode6 has seven member functions that are described in Table 6.11. Bisection FPP() is a function shared by the bisection and false position methods. It is not necessary to create separate functions for these two methods as the only difference between them is the formula for c_i. The Newton—Raphson and secant methods are represented by Newton() and Secant(), respectively. Other functions in Code6 are more or less similar to functions of similar names as in the previous chapters. They are described briefly in Table 6.11.

There are three events in Code6, and each one of them is handled by its corresponding function. The code is given as

BEGIN_MESSAGE_MAP(CCode6,CFrameWnd)
      ON_WM_PAINT()
      ON_WM_LBUTTONDOWN()
      ON_BN_CLICKED(IDC_BUTTON,OnButton)
END_MESSAGE_MAP()

The process starts at the constructor. Basically, the constructor allocates memory for the class. It is also in the constructor that several variables are assigned with their initial values. The initial values include the location of the objects, the size of each object, and its title. It is also important to set the initial value for fStatus=0 to indicate no input has been read yet at this level of execution. At this initial stage, the menu has not been displayed, and its flag is set to fMenu=0. The code is given as

CCode6::CCode6()
{
      Create(NULL,"Code6: Nonlinear Equations",
            WS OVERLAPPEDWINDOW,CRect(0,0,800,635),NULL);
      Arial80.CreatePointFont(80,"Arial");
      pt=new PT [m+1];
      fMenu=0; fStatus=0; idc=301
      menu[1].item="NLE: Bisection";
      menu[2].item="NLE: False-Point Position";
      menu[3].item="NLE: Newton-Raphson";
      menu[4].item="NLE: Secant";
      for (int i=1;i<=nMenuItems;i++)
      {
           menu[i].hm= CPoint(20,30+(i-1)*30);
           menu[i].rc=CRect(menu[i].hm.x,menu[i].hm.y,
                 menu[i].hm.x+150,menu[i].hm.y+20);
      }
      curve.hm=CPoint(320,320); curve.end=CPoint(760,590);
      curve.rc=CRect(curve.hm.x-10,curve.hm.y-10,
            curve.end.x+10,curve.end.y+10);
      input[0].hm=CPoint(200,10);
      input[0].rc=CRect(input[0].hm.x,input[0].hm.y,
            input[0].hm.x+560,input[0].hm.y+260);
      input[0].display=CRect(30,180,170,250);
      for (i=1;i<=maxInput;i++)
            input[i].hm=CPoint(input[0].hm.x+10,input[0].
                     hm.y+30+(i-1)*25);
}

OnPaint() displays and updates the output regularly. The initial display in the main window consists of the menu items that are located in shaded rectangular boxes in the menu region. An update is made immediately whenever InvalidateRect() is invoked. The update is made possible through the test

if (fMenu!=0)

This conditional test separates the initial screen display from the time when a method has been selected. Another test written as

if (fStatus)

indicates the method has been successfully applied and produces its solution. The message updates the window by drawing the corresponding curve through DrawCurve() and displaying the solution. If the method fails, for example in the case of the absence of a root in the given interval, then the message No solution is displayed. The complete code for OnPaint() is shown below:

void CCode6::OnPaint()
{
      CPaintDC dc(this);
      CString str;
      dc.SelectObject(Arial80);
      dc.SetBkColor(RGB(150,150,150));
      dc.SetTextColor(RGB(255,255,255));
      for (int i=1;i<=nMenuItems;i++)
      {
            dc.FillSolidRect(&menu[i].rc,RGB(150,150,150));
            dc.TextOut(menu[i].hm.x+5,menu[i].hm.y+5,menu
                   [i].item);
    }
    dc.SetBkColor(RGB(255,255,255));
    dc.SetTextColor(RGB(100,100,100));
    dc.Rectangle(input[0].rc);
    dc.TextOut(input[0].hm.x+150,
          input[0].hm.y+5,menu[fMenu].item);
    if (fMenu!=0)
    {
          for (i=1;i<=nInputItems;i++)
                dc.TextOut(input[i].hm.x+10,
                input[i].hm.y,input[i].label);
          if (fStatus)
          {
                DrawCurve();
                str.Format("Solution: x=%lf",Solution);
                dc.TextOut(input[0].display.left,input
                       [0].display.top,str);
                fStatus=0;
          }
          else
                dc.TextOut(input[0].display.left,input
                       [0].display.top, "No solution");
    }
}

OnLButtonDown() repondsto ON_WM_LBUTTONDOWN, which corresponds to a click at one of the items in the menu. With the menu displayed, the user has the choice of four methods from which to choose. OnLButtonDown() handles this event and returns true through the test

if (menu[k].rc.PtInRect(pt))

The above conditional test makes sure that only a left-click at the menu items is valid. The click at one of the menu items causes the assignment of a number to fMenu, with fMenu=1 for bisection, fMenu=2 for false position, fMenu=3 for Newton— Raphson, and fMenu=4 for secant. With this selection, edit boxes and the Compute push button appear in the input region. The complete code for OnLButtonDown() is shown below:

void CCode6::OnLButtonDown(UINT nFlags,CPoint pt)
{
      int i,k;
      for (k=1;k<=nMenuItems;k++) // menu items
            if (menu[k].rc.PtInRect(pt))
            {
                  fMenu=k;
                  InvalidateRect(input[0].rc);
                  switch(k)
                  {
                        case 1:
                        case 2:
                              nInputItems=4;
                              input[1].label="y=f(x)";
                              input[2].label="a[0]";
                              input[3].label="b[0]";
                              input[4].label="epsilon";
                              break;
                        case 3:
                              nInputItems=5;
                              input[1].label="y=f(x)";
                              input[2].label="y=f'(x)";
                              input[3].label="x[0]";
                              input[4].label="x[m]";
                              input[5].label="epsilon";
                              break;
                        case 4:
                              nInputItems=5;
                              input[1].label="y=f(x)";
                              input[2].label="x[0]";
                              input[3].label="x[1]";
                              input[4].label="x[m]";

input[5].label="epsilon";
                              break;
                  }
                  for (int i=1;i<=maxInput-1;i++)
                        input[i].ed.DestroyWindow();
                  btn.DestroyWindow();
                  btn.Create("Compute",WS CHILD|WS VISIBLE|
                        BS DEFPUSHBUTTON,
                        CRect(CPoint(input[0].hm.x+10,
                        input[0].hm.y+5),
                        CSize(100,20)),this,IDC BUTTON);
                  for (i=1;i<=nInputItems;i++)
                        input[i].ed.Create(WS CHILD|
                              WS VISIBLE| WS BORDER,
                              CRect(input[i].hm.x+100,
                              input[i].hm.y,input[i].hm.x+520,
                              input[i].
                              hm.y+20),this,idc++);
      }
}

The user now completes the input by filling in the values in the edit boxes. Once this is done, a click at Compute confirms the entries, and the process proceeds into the next stage. This event is detected as ON_gBN_CLICKED, and its message handler is OnButton(). This function reads the input values, and then calls the corresponding function according to its fMenu value.

void CCode6::OnButton()
{
      CString str;
      if (fMenu!=0)
      {
            for (int i=1;i<=nInputItems;i++)
                 input[i].ed.GetWindowText(input[i].item);
            if (fMenu==1 | | fMenu==2)
                  BisectionFPP();
            if (fMenu==3)
                  Newton();
            if (fMenu==4)
                  Secant();
            if (fStatus)
            {
                  ShowTable();
                  InvalidateRect(curve.rc);

InvalidateRect(input[0].display);
            }
            else
                  InvalidateRect(input[0].display);
      }
}

In the above code segment, a conditional test is performed to determine whether the problem has been solved successfully using the selected method. This is done through

if (fStatus)

A successful method is one that converges to its solution. This is indicated through the assignment of fStatus=1. A message is also displayed in the main window if the method fails, which is indicated through fStatus=0.

The value of the status flag fStatus is updated inside one of the functions from BisectionFPP(), Newton(), and Secant(). An update of fStatus=1 indicates the input data have been successfully executed in the selected method. A value of 0 means the method fails mostly from wrong end points in locating the root. With fStatus=1, the process now proceeds to the next stage, which is a display of the results in the table through ShowTable(). The graph of y = f (x) is also drawn through an update in OnPaint() using InvalidateRect(). The final solution in the form of an approximated value of the root to y = f (x) is displayed through InvalidateRect(input[0].display).

The bisection and the false position methods are handled by BisectionFPP(). In terms of concepts, the two methods are similar as they are based on a fixed starting interval given by a ₀ ≤ x ≤ b ₀. The only difference between them is the way an update is made on c_i. The code segment for BisectionFPP() is given by

void CCode6::BisectionFPP()
{
      int i,psi[2];
      double fa,fb,fc,psv[2],epsilon;
      pt[0].a=atof(input[2].item);
      pt[0].b=atof(input[3].item);
      epsilon=atof(input[4].item);
      psi[1]=23; psv[1]=pt[0].a;
      fa=parse(input[1].item,1,psv,psi);
      psv[1]=pt[0].b;
      fb=parse(input[1].item,1,psv,psi);
      if (fa*fb<0)
      {
            for (i=0;i<=maxIter;i++)
        {

if (fMenu==1)
                         pt[i].c=(pt[i].a+pt[i].b)/2;
                   if (fMenu==2)
                         pt[i].c=(pt[i].a*fb-pt[i].b*fa)/(fb-fa);
                   psv[1]=pt[i].a;
                   fa=parse(input[1].item,1,psv,psi);
                   psv[1]=pt[i].b;
                   fb=parse(input[1].item,1,psv,psi);
                   psv[1]=pt[i].c; pt[i].x=pt[i].c;
                   fc=parse(input[1].item,1,psv,psi);pt[i].y=fc;
                   if (fa*fc>0)
                   {
                         pt[i+1].a=pt[i].c; pt[i+1].b=pt[i].b;
                   }
                   else
                   {
                         pt[i+1].b=pt[i].c; pt[i+1].a=pt[i].a;
                   }
                   if (i>0)
                   {
                         pt[i].error=fabs(pt[i].c-pt[i-1].c);
                         if (pt[i].error<epsilon)
                         {
                               Stop=i;
                               Solution=pt[Stop].c;
                               fStatus=1;
                               break;
                         }
                   }
           }
    }
}

The bisection and false position methods will only produce the desired results if the starting interval complies with the mean-value theorem. In the above code segment, a conditional test is performed for this possibility, as follows:

if (fa*fb<0)

In the above test, fa and fb are f (a₀) and f (b₀), respectively. This test performs a check on the validity of the starting points in the interval through the mean-value theorem.

The iterations in the bisection and false position methods are governed by a comparison on the error, |c_i — c_{i −1}| < ε or pt[i].error<epsilon. A check is made at every iteration to determine whether the stopping criteria have been achieved, through

pt[i].error=fabs(pt[i].c-pt[i-1].c);
if (pt[i].error<epsilon)
{
       Stop=i;
       Solution=pt[Stop].c;
       fStatus=1;
       break;
}

Several assignments are made if the stopping mark for the iterations has been achieved. First, the last iteration number is stored as Stop. The last value of c_i is then the final solution, and this value is assigned to Solution. Finally, the status flag is assigned with a value of 1 to indicate the method is successful.

The Newton—Raphson method is handled by Newton(). This method is easier to implement than the bisection and false position methods as the method does not involve an update at the end points of the intervals. The code is shown as follows:

void CCode6::Newton()
{
      int i,psi[2];
      double epsilon,psv[2];
      pt[0].x=atof(input[3].item);
      pt[m].x=atof(input[4].item);
      epsilon=atof(input[5].item);
      psi[1]=23;
      for (i=0;i<=maxIter;i++)
      {
            psv[1]=pt[i].x;
            pt[i].y=parse(input[1].item,1,psv,psi);
            pt[i].yd1=parse(input[2].item,1,psv,psi);
            if (i<m)
            {
                     pt[i+1].x=pt[i].x-pt[i].y/pt[i].yd1;
                     pt[i].error=fabs(pt[i+1].x-pt[i].x);
            }
            if (pt[i].error<epsilon)
            {
                 Stop=i;
                 Solution=pt[Stop].x;
                 fStatus=1;
                 break;
            }
     }
}

A difficulty with the Newton-Raphson method is the requirement of the first derivative in its update formula. Since our application does not support symbolic computing for determining the derivative, it is necessary for the user to enter the input string. In the above code segment, f'(x) is denoted as pt[i].yd1, and its string value is read as input[2].item in theedit box. This string will be processed through parse() to produce the numerical value of f'(x) at the given point.

The error in the Newton-Raphson method is |x_i+1 — x_i|, and this is written as pt[i].error=fabs(pt[i+1].x-pt[i].x). The error is again compared with epsilon at each iteration to determine whether convergence has been achieved.

The secant method is handled by Secant(). The method works on the same concept as in the Newton-Raphson method with the derivative replaced by an approximation using a secant line. The code segment for Secant() is given by

void CCode6::Secant()
{
      int i,psi[2];
      double epsilon,psv[2];
      pt[0].x=atof(input[2].item);
      pt[1].x=atof(input[3].item);
      pt[m].x=atof(input[4].item);
      epsilon=atof(input[5].item);
      psi[1]=23; psv[1]=pt[0].x;
      pt[0].y=parse(input[1].item,1,psv,psi);
      for (i=0;i<=maxIter;i++)
      {
             if (i<m-2)
            {
                  psv[1]=pt[i+1].x;
                  pt[i+1].y=parse(input[1].item,1,psv,psi);
                  pt[i+2].x=(pt[i].x*pt[i+1].y
                        -pt[i+1].x*pt[i].y)/(pt[i+1].y-pt[i].y);
                  pt[i].error=fabs(pt[i+2].x-pt[i+1].x);
             }
             if (pt[i].error<epsilon)
             {
                   Stop=i;
                   Solution=pt[Stop].x;
                   fStatus=1;
                   break;
             }
      }
}

The two-ahead update in the value of x for the secant method is shown in the above code segment through

if (i<m-2)
{
     psv[1]=pt[i+1].x;
     pt[i+1].y=parse(input[1].item,1,psv,psi);
     pt[i+2].x=(pt[i].x*pt[i+1].y-pt[i+1].
         x*pt[i].y)/(pt[i+1].y-pt[i].y);
     pt[i].error=fabs(pt[i+2].x-pt[i+1].x);
}

The error in the secant formula is pt[i].error=fabs(pt[i+2].x-pt[i+1].x) or |x_{i +2} — x_{i +1}|. As in the other three methods, the error is compared with epsilon at each iteration to determine whether a stopping mark has been reached.

The results from the iterations in the selected method are tabulated in the list view table through ShowTable(). The items displayed are the iteration number i, x_i, f (x_i) and the corresponding error values. The code segment for ShowTable() is given by

void CCode6::ShowTable()
{
      CString str;
      CPoint hTable=CPoint(20,310);
      CRect rcTable=CRect(hTable.x,hTable.y,hTable.x+280,
      hTable.y+290);
      table.DestroyWindow();
      table.Create(WS VISIBLE | WS CHILD | WS DLGFRAME |
              LVS REPORT| LVS NOSORTHEADER,rcTable,this,idc++);
      table.InsertColumn(0,"i",LVCFMT CENTER,25);
      table.InsertColumn(1,"x",LVCFMT CENTER,70);
      table.InsertColumn(2,"f(x)",LVCFMT CENTER,70);
      table.InsertColumn(3,"error",LVCFMT CENTER,70);
      for (int i=0;i<=Stop;i++)
      {
            str.Format("%d",i); table.InsertItem(i,str,0);
            str.Format("%lf",pt[i].x);
            table.SetItemText(i,1,str);
            str.Format("%lf",pt[i].y);
            table.SetItemText(i,2,str);
            if (fMenu>2 | | ((fMenu<=2) &&i>0))
            {
                  str.Format("%lf",pt[i].error);
                  table.SetItemText(i,3,str);
            }
      }
}

DrawCurve() is basically the same function as discussed earlier in Chapter 4. There are some modifications to cater the needs in the methods discussed. The graph is not drawn if the selected method fails. The full code segment for DrawCurve() is given as follows:

void CCode6::DrawCurve()
{
      CClientDC dc(this);
      int i,psi[2];
      double h,m1,m2,c1,c2,psv[2];
      CString str;
      CPoint px;
      psi[1]=23;
      if (fMenu==1 | | fMenu==2)
      {
            left.x=pt[0].a;
            right.x=pt[0].b;
      }
      if (fMenu==3 | | fMenu==4)
      {
            left.x=Solution-2;
            right.x=Solution+2;
      }
      h=(right.x-left.x)/(double)m;
      pt[0].x=left.x; psv[1]=pt[0].x;
      pt[0].y=parse(input[1].item,1,psv,psi);
      max.y=pt[0].y; min.y=pt[0].y;
      for (i=1;i<=m;i++)
      {
           pt[i].x=pt[i-1].x+h;
           psv[1]=pt[i].x;
           pt[i].y=parse(input[1].item,1,psv,psi);
           if (max.y<pt[i].y)
                 max.y=pt[i].y;
           if (min.y>pt[i].y)
                 min.y=pt[i].y;
      }

      // Cartesian-Windows conversion coordinates
      m1=(double)(curve.end.x-curve.hm.x)/(right.x-left.x);
      c1=(double)curve.hm.x-left.x*m1;
      m2=(double)(curve.hm.y-curve.end.y)/(max.y-min.y);
      c2=(double)curve.end.y-min.y*m2;

// Draw & label the x,y axis
      CPen pGray(PS SOLID,1,RGB(100,100,100));
      dc.SelectObject(pGray);
      dc.SelectObject(Arial80);
      px=CPoint(m1*0+c1,m2*min.y+c2); dc.MoveTo(px);
      px=CPoint(m1*0+c1,m2*max.y+c2); dc.LineTo(px);

      px=CPoint(m1*left.x+c1,m2*0+c2); dc.MoveTo(px);
      str.Format("%.0lf",left.x); dc.TextOut(px.x,px.y,str);
      px=CPoint(m1*right.x+c1,m2*0+c2); dc.LineTo(px);
      str.Format("%.0lf",right.x); dc.TextOut(px.x-10,px.y,str);

      // draw the curve
      CPen pDark(PS SOLID,2,RGB(50,50,50));
      dc.SelectObject(pDark);
      for (i=0;i<=m;i++)
      {
            px=CPoint((int)(m1*pt[i].x+c1),
                      (int)(m2*pt[i].y+c2));
            if (i==0)
                  dc.MoveTo(px);
            else
                  dc.LineTo(px);
            if (pt[i].y==max.y)
            {
                  str.Format("%.6lf",max.y);
                  dc.TextOut(px.x,px.y-10,str);
            }
            if (pt[i].y==min.y)
            {
                  str.Format("%.6lf",min.y);
                  dc.TextOut(px.x,px.y,str);
            }
      }
}

The interval of x for the curve has been set differently the methods. In the case of the bisection and false position methods, DrawCurve() draws a graph based on the input values in the left and right intervals, or a ₀ ≤ x ≤ b ₀. This is given by

if (fMenu==1 | | fMenu==2)
{
      left.x=pt[0].a;
      right.x=pt[0].b;
}

We discussed five methods for finding the zeros of a function f(x), namely, the bisection, false position, Newton-Raphson, secant, and fixed-point iteration methods. Four methods are illustrated in their visual interfaces using Visual C++. Each method is represented as an item in the menu. The solution for each method is shown in a list view table and is depicted in its solution curve. This interface provides the fundamental requirement for visualization on the nonlinear equation problems.

The nonlinear problem arises in many science and engineering applications. In many cases, the problem appears as a small component from the overall problem. Solving the problem as a component definitely contributes to solving the overall problem. The Windows-friendly interface for handling the numerical computations using C++ helps much in contributing to the solution.