Iterative Solutions to Systems of Equations

Chris Harrow and H. W. Straley

Abstract

The purpose of this activity is to provide an alternate method of solving systems of equations using the process of numerical iteration. This is not necessarily intended to always be an easier method of solving systems and, in fact, it sometimes complicates the problems. The iterative process does involve some very beautiful mathematics and it occasionally offers a method of solution to systems that are otherwise analytically impossible to solve. The first activity presents the algorithm for the solution of any system of two linear equations and is suitable for Algebra I or Algebra II students. The second activity generalizes the algorithm to systems of equations in which one of the equations is linear and the other is any continuous and invertible function. The second part requires that students be familiar with inverses of various standard functions and is probably most appropriate for Algebra II or Trigonometry. Transformational geometry is used to justify the algorithms.

Part 1: Introduction to Linear Systems

We will illustrate this technique with the following system:

(1)

Notice that one of the functions in the system is the identity function. The reason for this requirement stems from the process involved in iteration. Allow students to pick any initial value of x that they want to try. This value of x is called a seed and is denoted by . For this example, we will let = 5. We now iterate our function using the non-identity equation in our system. Substitute into y = .5x+1 to obtain = .5(5)+1 = 3.5. Similarly, = .5()+1 = .5(3.5)+1 = 2.75. Continuing this process, we develop the sequence:

= 5, = 3.5, = 2.75, 2.375, 2.1875, 2.09375, . . .

our iterative process is 2. From the first equation in our system, we know that the x- and y-values of the solution are identical and therefore our system has the solution (2,2).

The most amazing thing about this process is that it does not matter what initial value was chosen for the seed. Any chosen value for will eventually converge to 2 and therefore lead to the solution point (2,2).

Does this process always work? Try each of the following systems with several different seed values.

The iteration of (2) should have developed a sequence converging to -8/5. Unless you made some lucky guesses (see problem 3 at the end of the article), the sequences for (3) and (4) went to , depending on your choices for .

The obvious question at this point is: Why do some systems converge while others do not? The answer to this lies in understanding the nature of fixed points in an iterative operation. Simply put, when iterating a system consisting of the identity function and one other function, the intersection of two graphs is called a fixed point and is attracting if the absolute value of the slope of the non-identity function at the point of intersection is less than one and is repelling if the slope at the fixed point is greater than one. In terms of our sequences, this means that if the absolute slope of the non-identity line is less than one, then we can solve our system by iteration and if the slope of the non-identity line is greater than one, then in general, we cannot solve the system using our present technique. This idea should become obvious to your students if they are given several different linear systems and are asked to determine when convergence is possible and when it is not.

At first glance, this seems to be quite a limited technique. Not only must one of the lines be the identity function, but the other must also have a slope between -1 and 1. Using the processes developed in transformational geometry, this process can be extended to all systems of two-dimensional linear equations.

Generalization of Linear Systems

Remember that convergence requires two important conditions:

1) one of the functions must be the identity function, and

2) the other function must have an absolute slope less than 1

Let us use (3) from above to illustrate the technique. Note that in this case, the first requirement has been met, but the second has not. This can be corrected by transforming the second linear equation into the identity function and then applying the same transformations to our first equation. By subtracting one from each equation and then dividing both by two, we obtain the sequence of systems below. This is transformationally equivalent to applying a

(3)

vertical translation of -1 and a vertical "shrink" of magnitude 2 to both of the lines in our system. Both of our requirements for convergence have now been met. If we were to try any value for now, we would notice that the system would converge to the fixed point that was previously repelling. For example, if = 5, then we obtain the sequence:

5, 2, .5, -.25, -.625, . . . , -1

Since the x- and y-values of the original system were identical, the solution would be (-1,-1).

Likewise, (4) could be transformed to (5) and upon iteration the solution would be found to be (.75,.75).

(5) (6)

Why does this work? In general, we have system (6). If a = c, then our system is either inconsistent (if b d) or dependent (if b = d), neither of which are very interesting cases. Without loss of generality, we can therefore assume that a c. We want to transform the line with the greatest absolute slope into the identity function. This process will simultaneously satisfy both of the conditions needed for convergence. For our system, we will assume that . Now, subtract b from both equations and then divide both by a. Under the rules of transformational geometry, this has the effect of applying a vertical translation of magnitude -b and then a vertical "stretch" of magnitude 1/a. It is crucial to note that while this process certainly alters the y-value of the point of intersection of the two lines, it does not affect the x-coordinate in any way. Algebraically, our system has been transformed as follows:

= =

The first equation is the identity and since , then the second has a slope with absolute value less than one. Because of the transformations involved, this process only yields the x-values of the solution points. To solve the system choose any value for and iterate. The resulting limit of the sequence will be the x-value of the solution point. To find the y-value, substitute your x-coordinate into either of the original two equations.

Consider (7). Since the top equation has the greatest absolute slope, it must be

transformed into the identity function. Subtract two from both equations and then divide both by -3. This is equivalent to sliding both lines down two units and vertically compressing them by a factor of -3. The result is (8). Since the choice for does not matter, we can use .425 as our seed. The resulting sequence is approximately:

.425, 3.05, 1.3, 2.47, . . . , 2

The x-value of the solution is 2 and the y-coordinate is found by substitution into the original system: y = 2(2) - 8 = -4. Therefore, the solution to the system is (2,-4). This can be verified by any of the traditional techniques.

Part 2: Introduction to Other Systems

In this section, your students should probably utilize graph paper to make reasonably careful sketches of each system with particular attention to the slopes.

(9) (10) .

determine that this iterative function has a limit of -2. Since we had to transform the original system, we can recall from section one that our limit is then the x-coordinate of the solution point. Evaluating either of the original functions at this x-value, we find that y = (-2)² = 4 and therefore our system has solution (-2,4). Verify this using any traditional methods.

Try each of the following systems. Remember to graph the systems after any necessary transformations and try to notice any graphical relationships within the systems. It might also be helpful to try different values for .

System (11) converged to about -0.567143 while (12) did not converge for any seed. Why?

The slopes at the points of intersection for (9) - (12) varied. With partially non-linear systems, the slopes are not necessarily easy to find unless one uses calculus. However, using careful sketches of each transformed system, students can approximate the tangent lines to the curves at the points of intersection. They should then be able to approximate the slope of their tangent lines. Note that the absolute values of the slopes of the (9) and (11) were less than one and that the iterative processes converged rather quickly. The slope of (10) had a slope of one and converged slowly. (12) had a slope greater than one and all seeds diverged. These results are consistent with the restrictions on convergence from Part I.

Generalizations of Other Systems

Let us now change (12) by replacing the nonlinear component with its inverse to obtain:

.

Geometrically (and transformationally) this has the effect of reflecting the original function over the line y = x. Try any seed on the new system and notice that while it diverged quickly before, it now converges very quickly to 1.90416. As before, this is the x-value of the solution and since the identity was part of the original system, we get the y-coordinate with no work and the solution of the system is approximately (1.9,1.9).

This section discussed systems of two equations of the form:

.

The requirements for convergence with systems of this type are the same as they were in Part I. The first requirement is easy to satisfy by subtracting b from both equations and then dividing both by a to obtain:

.

We can no longer depend on f(x) being linear and this makes the process particularly interesting. If the absolute value of the slope of the non-linear portion of our system is less than one, then iterations will converge; otherwise, they will diverge. By using the inverse technique of the previous paragraph, we have effectively reflected our system over the line y=x. Recall that by our initial transformations we changed the y-value while the x-value was unchanged. Before finding the inverse, notice that we had moved the point of intersection of the system to a location on the line y=x. Upon reflection, transformational geometry guarantees that points on the reflecting line are their own images. This means that when we found the inverse of the non-linear function, again the x-value of the point of intersection remained unaltered. Finding the inverse is only necessary if the absolute value of the original slope of the tangent line was greater than one. Transformations also guarantee that if a line is reflected over the line y=x, then the slope of the image line is the reciprocal of the original slope. This means that if the slope of the tangent line was originally greater than one, than the slope of the inverse function at the point of intersection would be less than one and our second requirement will be met. From another perspective, this is exactly the same process we used in Part I (See problem #1).

Conclusion

When given a system containing at least one linear equation, this process can be simplified to the following steps:

1) Transform the linear equation to the identity function, y = x, and apply the identical transformation to the other function in the system.

2) To try to ensure convergence, pick a value for the seed somewhat close to where you think the point of intersection might be. Iterate!

3) If your sequence approaches a limit, then you have found the x-value of the solution point. If the sequence diverges, then you are guaranteed that slope at the intersection was greater than one. If this happens, replace the function with its inverse and iterate again. You are guaranteed to get the x-coordinate now.

4) Plug your x-value from above into either of the original functions and you will get the y-coordinate. Fini!

Problems

The method of numerical iteration is not necessarily intended to always be an easier method of solving systems and the method of finding inverses could in fact complicate the process. The iterative process does, though, involve some very beautiful mathematics and offers a method of solution to many systems that are otherwise analytically impossible to solve.

1) Why does the overall method for a system containing only one linear equation also work for the systems of two linear equations? That is, why is it only necessary to change one line to the identity and then see what happens? (Hint: Think about step three.)

2) Prove that if y = f(x) is a linear function with a slope between -1 and 1, then the iteration of f(x) with any seed will converge on some number x_s such that f(x_s) = x_s.

3) Use these systems to answer the following questions:

A) The given method will never work if the slopes in the original system are opposite (a = -c). Try the iterative process that was given with any choice you want for in each system. What does happen? How quickly is this pattern achieved?

B) Solve each of the above systems by any traditional means available and record the solution point.

C) How do the x-coordinates of the solutions from part B correspond to the patterns you achieved in part A?

D) How can you now revise the iterative process to handle two line systems where the slopes are opposite (a = -c)? (This will only work with two line systems.)

4) What happens to the system if is chosen to be -1 or to the system if is chosen to be 3/4. Why? How do the given choices of relate to the graphs of each of the given systems? Try other types of systems to test your hypothesis.

5) Systems involving at least one non-linear equation often have multiple solutions.

A) Given: Look at the graph of the system to determine how many solutions exist. First transform the system to get the identity function and try some careful values for . Notice that only one solution is generally possible. Replace the cubic function with its inverse to obtain the other solutions. Notice that certain choices of tend to lead to specific solutions for the system. The set of all that result in a specific solution is called the basin of attraction for that given solution. Can you determine the basins of attraction for each solution to this system? Calculus students should be able to determine the exact values for the endpoints of the basins. (Recall the requirements for convergence in a system!)

B) Try another example: Unless something like problem 3 happens, all choices for will initially diverge and you will have to find the inverse of a quadratic. Be careful. The inverse of is . Try both the positive and the negative portions in your attempt to find a solution. Look at the graph of the original system and try to determine why both the negative and the positive square roots are needed to solve the system.

C) Use your answers to parts A and B to determine a method for solving systems that have multiple solutions.

6) The big question: How can you handle systems where neither equation is linear?

Try (11)

This particular system cannot be solved analytically and the usual approach is to graph the solutions on a calculator and "zoom in" on the points of intersection. The two solutions near the origin are relatively easy to locate in this manner, but the third solution "way out" in the first quadrant requires a significant readjustment of the viewing window. The window would also have to be readjusted after each zoom. Iteration allows you to avoid that problem.

Given a system of the form

where neither f nor g is linear, the system could be transformed into either (12) or (13). Transform (11) into each of the

given forms if and . At this point, your system is much like the transformed systems we have used before. Use the two different transformed systems and the iteration method to find the solutions to the systems. Determine the basis of attraction for each solution.

If you are familiar with the process of "cobwebbing" to graphically represent iteration, this paper could take on another beautiful dimension. In this light, another solution technique for problem 5 can be determined by "cobwebbing" between both and . Your students might enjoy this view of iteration. In this case, you are really transforming the system in this problem into the following two forms.

Have fun!

Resources

For an excellent discussion of transformational geometry and its features and properties, we suggest that you read the appropriate sections of UCSMP's Geometry and Advanced Algebra (Scott, Foresman publishers).

The TI-82 graphics calculator has a great cobwebbing feature. As an introduction to the concepts of "cobwebs," we recommend that you read the appropriate section of the TI-82 guidebook.

Woodrow Wilson Leadership Program in Mathematics lpt@www.woodrow.org
The Woodrow Wilson National Fellowship Foundation webmaster@woodrow.org
CN 5281, Princeton NJ 08543-5281 Tel:(609)452-7007 Fax:(609)452-0066