The following program calculates the roots of two nonlinear functions using Newton's algorithm. The functions are:
F(x, y) = 0 and G(x, y) = 0
The basic algorithm for refining the guesses for the roots is:
x' = x - (F gy - G fy) / (fx gy - fy gx)
y' = y - (G fx - F gx) /(fx gy - fy gx)
where F and G are the functions F(x, y) and G(x, y) respectively. The symbols fx, fy, gx, and gy are the derivatives of the functions F(x, y) and G(x, y) with respect to x and y (that is fx = dF(x,y)/dx, fy = dF(x,y)/dy, and so on). The program approximate the function derivatives using the following approximations:
fx = (F(x + hx, y) - F(x,y)) / hx
fy = (F(x, y + hy) - F(x,y)) / hy
gx = (G(x + hx, y) - G(x,y)) / hx
gy = (G(x, y + hy) - G(x,y)) / hy
where hx = 0.01 * (1 + |x|) and hy = 0.01 * (1 + |y|).
The program prompts you to enter:
1. Guess for the roots.
2. Tolerances for the root.
3. The maximum number of iterations.
The program displays the following results:
1. The values of the two roots.
2. The number of iterations.
If the number of iterations exceeds the maximum limit, the program displays the text SOLUTION FAILED before displaying the above results.
Here is a sample session to find the roots of:
F(x,y) = x^2 + y^2 -1 and G(x,y) = x^2 - y^2 - 0.5
The initial guesses for the roots x and y are 0 and 0, respectively. The tolerances for the roots x and y are 1E-7 and 1E-7, respectively. The maximum number of iterations is 55.
|
PROMPT/DISPLAY |
ENTER/PRESS |
| > | [RUN] |
| GUESS X? | 0[END LINE] |
| TOLER X? | 1E-7[END LINE] |
| GUESS Y? | 0[END LINE] |
| TOLER Y? | 1E-7[END LINE] |
| MAX ITERS? | 55[END LINE] |
| WAIT... | |
| (Audio beep) | |
| ROOT X= 0.50000 | [CONT] |
| ROOT Y= 0.8660254 | [CONT] |
| ITERS= 13 |
The roots found are x = 0.5 and y = 0.8660254.
Here is the BASIC listing:
10 DEF FNF(X,Y) = X^2 + Y^2 - 1
20 DEF FNG(X,Y) = X^2 - Y^2 + 0.5
30 INPUT "GUESS X? ";X
40 INPUT "TOLER X? ";T1
50 INPUT "GUESS Y? ";Y
60 INPUT "TOLER Y? ";T2
70 INPUT "MAX ITERS? ";M
80 I = 0 @ DISP "WAIT..."
90 'TOP': I = I + 1
100 IF I > M THEN GOTO 'SKIP'
110 H1 = 0.01 * (1 + ABS(X))
120 H2 = 0.01 * (1 + ABS(Y))
130 F = FNF(X, Y)
140 G = FNG(X, Y)
150 F1 = (FNF(X+H1,Y) - F) / H1
160 F2 = (FNF(X, Y + H2) - F) / H2
170 G1 = (FNG(X+H1,Y) - G) / H1
180 G2 = (FNG(X, Y + H2) - G) / H2
190 J = F1 * G2 - F2 * G1
200 D1 = (F * G2 - G * F2) / J
210 D2 = (G * F1 - F * G1) / J
220 X = X - D1
230 Y = Y - D2
240 IF ABS(D1) > T1 OR ABS(D2) > T2 THEN GOTO 'TOP'
250 'SKIP': BEEP
260 If I > M THEN DISP "SOLUTION FAILED" @
PAUSE
270 DISP "ROOT X=";X @ PAUSE
280 DISP "ROOT Y=";Y @ PAUSE
290 DISP "ITERS=";I
300 END
The program uses the variables shown in the following table:
|
Variable Name |
Contents |
| X | Guess for root X |
| Y | Guess for root Y |
| T1 | Tolerance for root X |
| T1 | Tolerance for root Y |
| M | Maximum number of iterations |
| I | Iteration counter |
| H1 | Increment hx |
| H2 | Increment hy |
| F | F(X, Y) |
| G | G(X,Y) |
| F1 | Derivative of F(X, Y) with respect to X |
| F2 | Derivative of F(X, Y) with respect to Y |
| G1 | Derivative of G(X, Y) with respect to X |
| G1 | Derivative of G(X, Y) with respect to X |
| J | Jacobean matrix |
| D1 | Root X refinement |
| D2 | Root Y refinement |
You can customize the above listing by changing the definition of function FNF and FNG in lines 10 and 20.
Copyright (c) Namir Shammas. All rights reserved.