Joshua Brinsfield
Garrett Spears
Section 201
Bisection Method of Solving Polynomials
This Maplet allows the user to practice solving continuous functions (polynomials here) for specific roots. The program creates randomized new polynomials of degree 3 to 5 via integrating a product of roots subtracted from x, and graphs the function over an interval* between randomized x[1] and x[2] (chosen so that no local maxima or minima exist on the interval between them, as these can throw off the process). The user must (using the built-in calculator, if neccessary) calculate the x value (x[1] + x[2])/2 and the function's value at that x, fill them in, and choose whether to replace x[1] or x[2] with the new value in order to obtain a new interval containing the desired root. The program checks, of course, for errors in this process. When the user has performed this step several times, he/she may click "Done" and the program will evaluate his/her progress (total steps (replacements made), current f value, etc.) and display the current maximum error, telling the user whether he/she has achieved the desired level of precision or must continue the process.
*Actually, to give a fuller view of the function, the first graph the user sees upon asking for a new problem graphs the function over the interval larger by 20 on each side than this one. IE, the interval from x[1]-20 to x[2]+20.
Programming note: Midpoints and y values at midpoints must be within .001 of the correct value; this flexibility is to allow decimal answers in all cases (although the exact answer is recalculated by the computer when the replacement is made). Because of this, the required maximum error is always greater than .001. Required error is determined by plugging in a required number of steps to get the exact answer into the error formula; the program currently randomizes this value to between 5 and 11 steps, inclusive.
restart;with(Maplets[Tools]): with(Maplets[Elements]):
with(RandomTools):StartEngine();randomize():Digits:=5:lightorange:="#FFB300":newGenf:=proc()
global NGXLoc, NGIOne, NGITwo, NGXOne, NGXTwo, NGFunc, NGFOne, NGFTwo, NGPrec, RHS, StepOK;
local randa, min1, max1, NGDegree, NGElevation, NGFor,
someNum, someNum2, pad;
randa:=rand(-25..25);
min1:=randa(); #first local min/max
# (x1 and x2 are initialized with no local extrema between them)
randa:=rand(8..39);
max1:=min1 + randa(); #second local min/max
randa:=rand(min1+2..max1-2);
NGXLoc:=randa(); #location of actual solution
randa:=rand(min1..NGXLoc-1);
NGIOne:=randa(); #initial x1
randa:=rand(NGXLoc+1..max1);
NGITwo:=randa(); #initial x2
#NGIOne,NGITwo:=op(sort([NGIOne,NGITwo]));
Set(iOne=NGIOne);
Set(iTwo=NGITwo);
randa:=rand(3..5);
NGDegree:=randa(); #degree of the polynomial
randa:=rand(-10..10);
NGElevation:=randa(); #constant added to final function
NGFunc:=(x - min1) * (x - max1);
for NGFor from 3 to NGDegree - 1 do
randa:=rand(0..1);
someNum2:=randa();
if someNum2=0 then
randa:=rand(round(min1 - round((NGDegree - 2)/10*(max1 - min1)))..min1);
someNum:=randa();
else
randa:=rand(max1..round(max1 + round((NGDegree - 2)/10*(max1 - min1))));
someNum:=randa();
end if;
NGFunc:=NGFunc * (x - someNum);
end do;
NGFunc:=sort(int(NGFunc, x) + NGElevation);
Set(func=NGFunc);
RHS:=evalf(subs(x=NGXLoc, NGFunc));
Set(TFRHS=RHS);
randa:=rand(2..5); #Changed to require fewer iterations
NGPrec:=randa(); #Number of steps required for correct error value
NGPrec:=10^(-ceil(log10(2^(NGPrec) / (NGITwo - NGIOne))));
Set(prec=NGPrec);
NGXOne,NGXTwo:=NGIOne,NGITwo; #current x1 and x2
Set(xOne=NGXOne);
Set(xTwo=NGXTwo);
NGFOne:=evalf(subs(x=NGXOne, NGFunc));
NGFTwo:=evalf(subs(x=NGXTwo, NGFunc));
Set(fOne=NGFOne);
Set(fTwo=NGFTwo);
pad:=(NGXTwo-NGXOne)/20;
Set(pt1=plot([NGFunc,RHS], x=NGXOne-pad..NGXTwo+pad, color=[blue,green]));
Set(xMid="");
Set(fMid="");
Set(TFerror="");
Set(repXOne=false);
Set(repXTwo=false);
Set(reply="");
Set(CalcIn="");
Set(CalcOut="");
StepOK:=false;
end proc:CheckStep:=proc()
global NGXOne, NGXTwo, CurrXMid, NGFunc, CurrFMid, CurrError, StepOK;
local userXMid, userFMid, userError;
CurrXMid:=evalf((NGXOne+NGXTwo)/2);
CurrFMid:=evalf(subs(x=CurrXMid,NGFunc));
CurrError:=evalf((NGXTwo-NGXOne)/2);
if Get(xMid)="" or Get(fMid)="" or Get(TFerror)="" then
Set(reply=" Please fill in x_mid, f(x_mid) and E.");
StepOK:=false;
return;
end if;
userXMid:=Get(xMid::realcons);
userFMid:=Get(fMid::realcons);
userError:=Get(TFerror::realcons);
if evalf(abs(userXMid-CurrXMid))>.001*abs(CurrXMid) then
Set(reply=" x_mid is incorrect. Please fix it and check again.");
StepOK:=false;
return;
end if;
if evalf(abs(userFMid-CurrFMid))>.001*abs(CurrFMid) then
Set(reply=" f(x_mid) is incorrect. Please fix it and check again.");
StepOK:=false;
return;
end if;
if evalf(abs(userError-CurrError))>.001*abs(CurrError) then
Set(reply=" Your error is incorrect. Please fix it and check again.");
StepOK:=false;
return;
end if;
StepOK:=true;
Set(reply=" Correct. Now decide if the error is small enough or replace one endpoint and repeat the process.");
end proc:ShowStep:=proc()
global NGXOne, NGXTwo, CurrXMid, NGFunc, CurrFMid, CurrError;
CurrXMid:=evalf((NGXOne+NGXTwo)/2);
Set(xMid=CurrXMid);
CurrFMid:=evalf(subs(x=CurrXMid,NGFunc));
Set(fMid=CurrFMid);
CurrError:=evalf((NGXTwo-NGXOne)/2);
Set(TFerror=CurrError);
end proc:probDone:=proc()
global RHS, CurrXMid, CurrFMid, StepOK, CurrError, NGPrec;
CheckStep();
if not StepOK then
Set(reply=" x_mid or f(x_mid) or the error are incorrect. Please fix them and check again.");
return;
end if;
if RHS=CurrFMid then
Set(reply=sprintf(" Since f(x_mid) = %a, you have found the solution exactly (within the machine accuracy of 5 digits). The solution is x = %a.", RHS, CurrXMid));
return;
end if;
if CurrError<=NGPrec then
Set(reply=sprintf(" Correct! You win! The solution is x = %a +/- %a.",
CurrXMid, CurrError));
else
Set(reply=" You're on the right track, but your error isn't small enough. Keep going!");
end if;
end proc:repXVal:=proc()
global NGFunc, RHS, NGXOne, NGFOne, NGXTwo, NGFTwo, CurrXMid, CurrFMid, StepOK;
local pad;
CheckStep();
if not StepOK then
Set(reply=" x_mid or f(x_mid) or the error are incorrect. Please fix them and check again.");
return;
end if;
if not Get(repXOne) and not Get(repXTwo) then
Set(reply=" You need to specify which endpoint to replace.");
return;
end if;
if RHS=CurrFMid then
Set(reply=sprintf(" Since f(x_mid) = %a, you have found the solution exactly (within the machine accuracy of 5 digits) and do not need to replace either endpoint.", RHS));
Set(repXOne=false);
Set(repXTwo=false);
return;
elif (NGFOne<RHS and RHS<CurrFMid) or (NGFOne>RHS and RHS>CurrFMid) then #replace x2
if Get(repXTwo) then
Set(xTwo=CurrXMid);
Set(fTwo=CurrFMid);
NGXTwo:=CurrXMid;
NGFTwo:=CurrFMid;
Set(reply=" OK, now repeat the process.");
else
Set(reply=sprintf(" Don't replace that x! %a is between f(x1) and f(x_mid).", RHS));
return;
end if;
elif (CurrFMid<RHS and RHS<NGFTwo) or (CurrFMid>RHS and RHS>NGFTwo) then #replace x1
if Get(repXOne) then
Set(xOne=CurrXMid);
Set(fOne=CurrFMid);
NGXOne:=CurrXMid;
NGFOne:=CurrFMid;
Set(reply=" OK, now repeat the process.");
else
Set(reply=sprintf(" Don't replace that x! %a is between f(x_mid) and f(x2).", RHS));
return;
end if;
end if;
pad:=(NGXTwo-NGXOne)/20;
Set(pt1=plot([NGFunc,RHS], x=NGXOne-pad..NGXTwo+pad, color=[blue,green]));
Set(xMid="");
Set(fMid="");
Set(TFerror="");
Set(repXOne=false);
Set(repXTwo=false);
StepOK:=false;
end proc:calcula:=proc()
Set(CalcOut=evalf(Get(CalcIn::realcons)));
end proc:BiMeth:=Maplet(onstartup=RunWindow(MAIN),
Window[MAIN](title="Bisection Method of Solving Equations", defaultbutton=BCalc,
[ valign=none, halign=none, inset=0, spacing=0,
[ halign=none,
Button("Instructions", onclick=BiMethExplanation, background=lightorange),
Button("New Problem", Evaluate(function="newGenf"), background=magenta),
HorizontalGlue(),
Button("Quit", Shutdown(), background=pink)
],
[ halign=none, inset=0, spacing=0,
[ valign=none, halign=none, inset=0, spacing=0,
BoxColumn( border=true,
caption="Goal: Use the bisection method to solve the equation:",
[ halign=none,
"f(x) = ",
TextField[func](editable=false, width=30, background=white),
" = ",
TextField[TFRHS](editable=false, width=10, background=white),
HorizontalGlue()
],
[ halign=none,
"to within E <",
TextField[prec](editable=false, width=5, background=white),
"on the interval [",
TextField[iOne](editable=false, width=5, background=white),
",",
TextField[iTwo](editable=false, width=5, background=white),
"].",
HorizontalGlue()
]
),
[ halign=none, border=true,
caption="Current Endpoints and Function Values",
"x1 =",
TextField[xOne](editable=false, width=5, background=white),
" f(x1) =",
TextField[fOne](editable=false, width=10, background=white),
HorizontalGlue(),
"x2 =",
TextField[xTwo](editable=false, width=5, background=white),
" f(x2) =",
TextField[fTwo](editable=false, width=10, background=white)
],
BoxColumn( halign=none, border=true,
caption="Find the Midpoint, Midpoint Value and the Error",
[ halign=none, inset=0,
"x_mid =",
TextField[xMid](width=5, background=turquoise),
"f(x_mid) =",
TextField[fMid](width=10, background=turquoise),
HorizontalGlue(),
"E = |x2-x1|/2 =",
TextField[TFerror](width=10, background=turquoise)
],
[ halign=none,
HorizontalGlue(),
Button[BCkStep]("Check", Evaluate(function="CheckStep"), background=green),
HorizontalGlue(),
Button[BShStep]("Show", Evaluate(function="ShowStep"), background=lightorange),
HorizontalGlue()
]
)
],
[ border=true,
caption="Plot",
Plotter[pt1](plot(undefined, x=-1..1, y=-1..1), width=250, height=250)
]
],
[ halign=none, inset=0, spacing=0,
BoxRow( border=true,
caption="Are you done?",
HorizontalGlue(),
Button("Done", Evaluate(function="probDone"), background=green),
HorizontalGlue()
),
BoxRow( border=true,
caption="If not, which endpoint should you replace?",
HorizontalGlue(),
RadioButton[repXOne]("Replace x1", group=RBGroup, background=turquoise),
RadioButton[repXTwo]("Replace x2", group=RBGroup, background=turquoise),
Button("Replace", Evaluate(function="repXVal"), background=magenta),
HorizontalGlue()
)
],
[ "Reply:",
TextBox[reply](editable=false, width=40, height=2)
],
[ border=true, background=gold,
"Calculator:",
TextBox[CalcIn](editable=true, width=40, height=2),
Button[BCalc]("Calculate", Evaluate(function="calcula"), background=lightorange),
TextField[CalcOut](editable=false, width=10, background=white)
],
[ valign=none, halign=none, inset=0, spacing=0,
"Creators: Joshua Brinsfield and Garrett Spears",
HorizontalGlue(),
"\302\251 Copyright P. Yasskin 2007"
]
]
),
Window[EXPL](title="Bisection Method - Instructions",
[ TextBox(width=80, height=14,
" The Bisection Method is a method for finding roots of continuous functions
(solving f(x)=y for a given y) by dividing an interval repeatedly in half.\n
You will be given initial x1 and x2 values, endpoints on an interval where
y is between f(x1) and f(x2). You must repeatedly follow these steps:\n
(1) Find the midpoint, x_mid, between x1 and x2 and f(x_mid).\n
(2) Select whether to replace x1 or x2 with x_mid to create a new interval,
keeping y is between f(x1) and f(x2).\n
You should stop when the absolute error | x2 - x1 | / 2 is less than the
specified value. Then click ""Done"" and do not replace an endpoint."),
Button("Close", CloseWindow(EXPL), background=pink)
]
),
ButtonGroup[RBGroup](),
Action[BiMethExplanation](RunWindow(EXPL))
):QyQtJkkoTWFwbGV0c0c2JEkoX3N5c2xpYkc2IiUqcHJvdGVjdGVkRzYjSShEaXNwbGF5R0YoNiNJJ0JpTWV0aEdGKCIiIg==