Friday, February 24, 2017

Finding by Computer Integer Solutions of Nonlinear Systems of Equations

Jsun Yui Wong

The computer program listed below seeks to find integer solutions (if any) of the following nonlinear system:

         - 3 * X(2) - 5 * X(4) - 6 * X(3) - 7 * X(6) - X(1) ^ 2=-106,

         13 * X(1) + X(2) * X(3) * X(4) + X(5) * X(6)=127,

         - 2 * X(1) * X(2) * X(3) - X(4) - X(5) - X(6)=-70,

         1 * X(1) + 1 * X(2) + 2 * X(3) - 7 * X(4) - 1 * X(5) + 1 * X(6)=-29,

         1 * X(1) + 1 * X(2) + 1 * X(3) + 2 * X(4) - 9 * X(5) - 3 * X(6)=21,

        1 * X(1) + 1 * X(2) + 1 * X(3) + 1 * X(4) + 2 * X(5) - 7 * X(6)=-13.

The first three of these equations are based on page 177 of Conley [4].  The last three come from

Greenspan and Casulli [5, page 41].

One notes line 94, which is 94 A(KK) = -30 + FIX(RND * 61).


0 DEFDBL A-Z

3 DEFINT J, K, X

4 DIM X(342), A(342), L(333), K(333)

12 FOR JJJJ = -32000 TO 32000

    14 RANDOMIZE JJJJ

    16 M = -1D+317

    77 IF JJJJ > -32000 THEN GOTO 88 ELSE GOTO 91


    88 IF RND < .05 THEN GOTO 91 ELSE GOTO 128


    91 FOR KK = 1 TO 6

        94 A(KK) = -30 + FIX(RND * 61)



    95 NEXT KK


    128 FOR I = 1 TO 200000

        129 FOR K = 1 TO 6


            131 X(K) = A(K)
        132 NEXT K
        155 FOR IPP = 1 TO FIX(1 + RND * 3)

            181 B = 1 + FIX(RND * 6)


            182 REM IF RND < -.1 THEN 183 ELSE GOTO 189

            183 r = (1 - RND * 2) * A(B)
            186 X(B) = A(B) + (RND ^ 3) * r

            188 GOTO 191
            189 IF RND < .5 THEN X(B) = A(B) - FIX(1 + RND * 1.99) ELSE X(B) = A(B) + FIX(1 + RND * 1.99)


        191 NEXT IPP


        996 N83 = 106 - 3 * X(2) - 5 * X(4) - 6 * X(3) - 7 * X(6) - X(1) ^ 2


        998 N82 = -127 + 13 * X(1) + X(2) * X(3) * X(4) + X(5) * X(6)


        1000 N81 = 70 - 2 * X(1) * X(2) * X(3) - X(4) - X(5) - X(6)
        1004 N84 = 29 + 1 * X(1) + 1 * X(2) + 2 * X(3) - 7 * X(4) - 1 * X(5) + 1 * X(6)
        1005 N85 = -21 + 1 * X(1) + 1 * X(2) + 1 * X(3) + 2 * X(4) - 9 * X(5) - 3 * X(6)

        1006 N86 = 13 + 1 * X(1) + 1 * X(2) + 1 * X(3) + 1 * X(4) + 2 * X(5) - 7 * X(6)


        1335 P = -ABS(N81) - ABS(N82) - ABS(N83) - ABS(N84) - ABS(N85) - ABS(N86)

        1499 IF P <= M THEN 1670
        1657 FOR KEW = 1 TO 6


            1658 A(KEW) = X(KEW)
        1659 NEXT KEW
        1661 M = P
        1664 NN81 = N81: NN82 = N82

        1665 NN83 = N83: NN84 = N84

        1666 NN85 = N85: NN86 = N86

    1670 NEXT I
    1888 IF M < 0 THEN 1999


    1917 PRINT A(1), A(2), A(3), A(4), A(5), A(6), M, JJJJ, NN81, NN82, NN83, NN84, NN85, NN86

1999 NEXT JJJJ

This computer program was run with qb64v1000-win [11]. Copied by hand from the screen, the computer program’s complete output through
JJJJ=-24354 is shown below:
 
2      3      5      7      -1  
4      0      -31947      0      0
0      0      0      0

2      3      5      7      -1  
4      0      -31946      0      0
0      0      0      0

2      3      5      7      -1
4      0      -31945      0      0
0      0      0      0

2      3      5      7      -1
4      0      -31944      0      0
0      0      0      0

2      3      5      7      -1
4      0      -31943      0      0
0      0      0      0

2      3      5      7      -1
4      0      -31942      0      0
0      0      0      0

2      3      5      7      -1
4      0      -28653      0      0
0      0      0      0

2      3      5      7      -1
4      0      -28652      0      0
0      0      0      0

2      3      5      7      -1
4      0      -25332      0      0
0      0      0      0

2      3      5      7      -1
4      0      -25331      0      0
0      0      0      0

2      3      5      7      -1
4      0      -25330      0      0
0      0      0      0

2      3      5      7      -1
4      0      -25329      0      0
0      0      0      0
2      3      5      7      -1
4      0      -25328      0      0
0      0      0      0

2      3      5      7      -1
4      0      -25327      0      0
0      0      0      0
2      3      5      7      -1
4      0      -25326      0      0
0      0      0      0

2      3      5      7      -1
4      0      -25325      0      0
0      0      0      0

2      3      5      7      -1
4      0      -25324      0      0
0      0      0      0
2      3      5      7      -1
4      0      -25323      0      0
0      0      0      0

2      3      5      7      -1
4      0      -25322      0      0
0      0      0      0
2      3      5      7      -1
4      0      -25321      0      0
0      0      0      0

2      3      5      7      -1
4      0      -25320      0      0
0      0      0      0

2      3      5      7      -1
4      0      -25319      0      0
0      0      0      0

2      3      5      7      -1
4      0      -25318      0      0
0      0      0      0

2      3      5      7      -1
4      0      -25317      0      0
0      0      0      0

2      3      5      7      -1
4      0      -24355      0      0
0      0      0      0

2      3      5      7      -1
4      0      -24354      0      0
0      0      0      0

Above there is no rounding by hand; it is just straight copying by hand from the screen.

On a personal computer with a Pentium Dual-Core CPU E5200 @2.50GHz, 2.50 GHz, 960 MB of RAM and with qb64v1000-win [11], the wall-clock time through
JJJJ=-24354 was 32 minutes.

Incidentally, one can stop the computer run as soon as the first 0 for M appears on the screen.  For the present problem, that happens at JJJJ=-31947.

Acknowledgment

I would like to acknowledge the encouragement of Roberta Clark and Tom Clark.

References
[1] R. Burden, J. Faires, A. Burden, Numerical Analysis, Tenth Edition. Cengage Learning, 2016.
[2] R. Burden, J. Faires, Numerical Analysis, Sixth Edition. Brooks/Cole Publishing Company, 1996.
[3] R. Burden, J. Faires, Numerical Analysis, Third Edition. PWS Publishers, 1985.
[4] W. Conley, Computer Optimization Techniques, Revised Edition.  Petrocelli Books, Inc., NY/Princeton, 1984.
[5] D. Greenspan, V. Casulli, Numerical Analysis for Applied Mathematics, Science, and Engineering. Addison-Wesley Publishing Company, 1988
[6] L. W. Johnson, R. D. Riess, Numerical Analysis, Second Edition. Addison-Wesley Publishing Company, 1982
[7] Microsoft Corp. BASIC, second edition (May 1982), Version 1.10. Boca Raton, Florida: IBM Corp., Personal Computer, P. O. Box 1328-C, Boca Raton, Florida 33432, 1981.
[8] William H. Mills, A System of Quadratic Diophantine Equations, Pacific Journal of Mathematics, 3 (1953), pp. 209-220.
[9]  Thomas L. Saaty, Optimization in Integers and Related Extremal Problems.  McGraw-Hill, 1970.
[10] Terry E. Shoup, Applied Numerical Methods for the Microcomputer, Prentice-Hall, 1984.
[11] Wikipedia, QB64, https://en.wikipedia.org/wiki/QB64.

No comments:

Post a Comment