1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
|
package bisection;
/*
* Benjamin Culkin
* 1/16/2018
* CS 479
* Bisection
*
* Use the bisection method to find bracketed roots of arbitrary real-valued functions.
*/
import bjc.utils.math.Dual;
import bjc.utils.math.DualExpr;
/**
* Bisect a curve to find bracketed roots of arbitrary real-valued functions.
* @author bjculkin
*
*/
public class Bisection {
/**
* Maximum number of iterations to attempt.
*/
public static final int MAXITR = 500;
/**
* Main method.
* @param args Unused CLI args.
*/
public static void main(String[] args) {
/* The variable to manipulate in the expressions. */
Dual varX = new Dual();
DualExpr varXExpr = new DualExpr(varX);
/* The functions to find the roots of. */
DualExpr dualA = new DualExpr(DualExpr.ExprType.SUBTRACTION,
new DualExpr(DualExpr.ExprType.COS, varXExpr), varXExpr);
DualExpr dualB;
{
/* Construct the second function. */
DualExpr tempA = new DualExpr(varXExpr, 5);
DualExpr tempB = new DualExpr(DualExpr.ExprType.MULTIPLICATION, new DualExpr(new Dual(3)),
new DualExpr(varXExpr, 4));
DualExpr tempC = new DualExpr(DualExpr.ExprType.MULTIPLICATION, new DualExpr(new Dual(4)),
new DualExpr(varXExpr, 3));
dualB = new DualExpr(DualExpr.ExprType.ADDITION,
new DualExpr(DualExpr.ExprType.SUBTRACTION, tempA, tempB),
new DualExpr(DualExpr.ExprType.SUBTRACTION, tempC, new DualExpr(new Dual(1))));
}
DualExpr dualC = new DualExpr(DualExpr.ExprType.SUBTRACTION,
new DualExpr(DualExpr.ExprType.MULTIPLICATION, varXExpr, varXExpr),
new DualExpr(new Dual(3)));
/* The approximated roots, using Newton's method. */
double newtonA = newton(dualA, varX, 0, 1, 0.0001);
double newtonB = newton(dualB, varX, 0, 1, 0.0001);
double newtonC = newton(dualC, varX, 1, 2, 0.0000001);
/* Print out the answers + their function. */
System.out.printf("Newton's Method:\n");
System.out.printf("\tx = cos(x) => %.4f\n", newtonA);
System.out.printf("\tx^5 - 3x^4 + 4x^2 - 1 => %.4f\n", newtonB);
System.out.printf("\tx^2 - 3 => %.7f\n", newtonC);
/* The approximated roots, using the secant method. */
double secantA = secant(dualA, varX, 0, 1, 0.0001);
double secantB = secant(dualB, varX, 0, 1, 0.0001);
double secantC = secant(dualC, varX, 1, 2, 0.0000001);
/* Print out the answers + their function. */
System.out.printf("Secant Method:\n");
System.out.printf("\tx = cos(x) => %.4f\n", secantA);
System.out.printf("\tx^5 - 3x^4 + 4x^2 - 1 => %.4f\n", secantB);
System.out.printf("\tx^2 - 3 => %.7f\n", secantC);
}
/**
* Use Newton's method to find the root of an equation.
*
* @param func
* The function to find a root for.
*
* @param var
* The variable in the function.
*
* @param lo
* The lower bound for the root
*
* @param hi
* The higher bound for the root
*
* @param tol
* The tolerance for the answer
*
* @return The estimated value for the equation.
*/
public static double newton(DualExpr func, Dual var, double lo, double hi, double tol) {
/* Initial guess for root. */
double newmid = (lo + hi) / 2;
for (int i = 0; i < MAXITR; i++) {
/* Previous root guess. */
double prevmid = newmid;
/* Set the variable properly. */
var.real = newmid;
var.dual = 1;
/* Evaluate the function and its derivative. */
Dual res = func.evaluate();
/* Use Newton's method to refine our solution. */
newmid = prevmid - (res.real / res.dual);
/* Hand back the solution if it's good enough. */
if (Math.abs(newmid - prevmid) < tol) {
return newmid;
}
}
System.out.println("Newton's method iteration limit reached.");
/* Give back the solution. */
return newmid;
}
/**
* Bisect an arbitrary expression using the secant method.
* @param func The expression to bisect.
* @param var The variable to manipulate.
* @param lo The lower bounding value.
* @param hi The higher bounding value.
* @param tol The tolerance to find the answer to.
* @return The bisected root for the expression, within the specified tolerance.
*/
public static double secant(DualExpr func, Dual var, double lo, double hi, double tol) {
/* Initial guesses for root. */
double guess1 = (lo + hi) / 3; // 1/3 into the range
double guess2 = ((lo + hi) / 3) * 2; // 2/3 into the range
for (int i = 0; i < MAXITR; i++) {
var.real = guess1;
var.dual = 1;
/* Evaluate the first guess. */
Dual res1 = func.evaluate();
var.real = guess2;
var.dual = 1;
/* Evaluate the first guess. */
Dual res2 = func.evaluate();
{
double top1 = guess1 * res2.real;
double top2 = guess2 * res1.real;
double top = top1 - top2;
double bot = res2.real - res1.real;
/* Use the secant method to refine our guesses. */
guess1 = guess2;
guess2 = top / bot;
}
/* Hand back the solution if it's good enough. */
if (Math.abs(guess1 - guess2) < tol) {
return guess2;
}
}
System.out.println("Secant method iteration limit reached.");
/* Give back the solution. */
return guess2;
}
}
|
