(************** Content-type: application/mathematica ************** Mathematica-Compatible Notebook This notebook can be used with any Mathematica-compatible application, such as Mathematica, MathReader or Publicon. The data for the notebook starts with the line containing stars above. To get the notebook into a Mathematica-compatible application, do one of the following: * Save the data starting with the line of stars above into a file with a name ending in .nb, then open the file inside the application; * Copy the data starting with the line of stars above to the clipboard, then use the Paste menu command inside the application. Data for notebooks contains only printable 7-bit ASCII and can be sent directly in email or through ftp in text mode. Newlines can be CR, LF or CRLF (Unix, Macintosh or MS-DOS style). NOTE: If you modify the data for this notebook not in a Mathematica- compatible application, you must delete the line below containing the word CacheID, otherwise Mathematica-compatible applications may try to use invalid cache data. For more information on notebooks and Mathematica-compatible applications, contact Wolfram Research: web: http://www.wolfram.com email: info@wolfram.com phone: +1-217-398-0700 (U.S.) Notebook reader applications are available free of charge from Wolfram Research. *******************************************************************) (*CacheID: 232*) (*NotebookFileLineBreakTest NotebookFileLineBreakTest*) (*NotebookOptionsPosition[ 28704, 851]*) (*NotebookOutlinePosition[ 29536, 879]*) (* CellTagsIndexPosition[ 29492, 875]*) (*WindowFrame->Normal*) Notebook[{ Cell["Lab 4: Meet me in the middle... BISECTION!", "Title", Background->RGBColor[0, 0, 1]], Cell["Math 342\tSpring 2003", "Subtitle"], Cell[CellGroupData[{ Cell["\<\ Initialization Cells: Bisection Algorithm \ \>", "Subsubsection"], Cell[BoxData[{ RowBox[{\( (*\(:\)\(Title : \ Bisection\ Algorithm\)\ *) \), "\n", "\n", \( (*\(:\)\(Author : \ Mark\ Parker\)\ *) \), "\n", "\n", \( (*\(:\)\(Mathematica\ \(Version : \ 4.0\)\)\ *) \), "\n", "\n", \( (*\(:\)\(Version : \ 2.0\)\ *) \), "\n", "\n", \( (*\(\(:\)\(History : \n\tV1 .0\ by\ M . \ Parker\)\), \ August\ 2000. \ \[IndentingNewLine]\ \ V2 .0\ by\ M . \ Parker, \ February\ 2003\[IndentingNewLine]\ \ \ \ \ \ \ cleaned\ up\ code, \ added\ intervl\ list\ output*) \), "\n", "\n", \( (*\ Last\ \(Revision : \ \ February\ 2003\)\ *) \), "\n", "\n", \(Off[General::"\"];\)}], "\n", RowBox[{\(Off[General::"\"];\), "\n"}], "\n", \(Clear[Bisection, f0, end1, end2, tol, its, \ digits, \ stopping, \ intervl];\), "\[IndentingNewLine]", RowBox[{\(Bisection::usage = "\\!\(\* StyleBox[\"value\",\nFontSlant->\"Italic\"]\), its->\!\(\* StyleBox[\"value\",\nFontSlant->\"Italic\"]\), digits->\!\(\* StyleBox[\"value\",\nFontSlant->\"Italic\"]\)] numerically solves for a zero \ of a function, \!\(\* StyleBox[\"f0\",\nFontSlant->\"Italic\"]\), occuring in the interval between \ \!\(\* StyleBox[\"end1\",\nFontSlant->\"Italic\"]\) and \!\(\* StyleBox[\"end2\",\nFontSlant->\"Italic\"]\). All other parameters are \ optional. The root is found within a horizontal tolerance of \!\(\* StyleBox[\"tol\",\nFontSlant->\"Italic\"]\) (default 0.00001), using a \ maximum number of iterations of \!\(\* StyleBox[\"its\",\nFontSlant->\"Italic\"]\) (default 100) and the result is \ printed using a precision of \!\(\* StyleBox[\"digits\",\nFontSlant->\"Italic\"]\)\!\(\* StyleBox[\" \",\nFontSlant->\"Plain\"]\)(default 10). A list containing the \ sequence of endpoints is returned in the variable \!\(\* StyleBox[\"intervl\",\nFontSlant->\"Italic\"]\).\>";\), "\[IndentingNewLine]"}], "\n", \(Bisection::ends\ = \ "\";\), "\[IndentingNewLine]", \(Bisection::ende\ \ = \ "\";\), "\[IndentingNewLine]", \ \(Bisection::tol\ = \ "\";\), "\ \[IndentingNewLine]", RowBox[{\(Bisection::its\ = \ "\";\), "\[IndentingNewLine]"}], "\[IndentingNewLine]", RowBox[{\(Options[Bisection] = {tol\ \[Rule] \ 0.00001, \ its\ \[Rule] \ 100, \ digits\ \[Rule] \ 10};\), "\n"}], "\n", RowBox[{ RowBox[{ RowBox[{\(Bisection[f0_, end1_, end2_, intervl_, opts___Rule]\), ":=", RowBox[{"Module", "[", RowBox[{\({x1, x2, x3, \ FLAG, fx1, fx2, fx3, f, ztol, cnt, \ maxits, \ digs, \ toln}\), ",", "\[IndentingNewLine]", RowBox[{\(toln\ = \ \(tol\ /. \ {opts}\)\ /. \ Options[Bisection]\), ";", "\[IndentingNewLine]", \(maxits\ = \ \(its\ /. \ {opts}\)\ \ /. \ Options[Bisection]\), ";", "\[IndentingNewLine]", \(digs\ = \ \(digits\ /. \ {opts}\)\ \ /. \ Options[Bisection]\), ";", "\[IndentingNewLine]", \({f0, \ end1, \ end2, \ intervl, tol, \ its, \ digits}\), ";", "\[IndentingNewLine]", \(Set @@ {f[x_], f0}\), ";", "\[IndentingNewLine]", \(x1\ = \ N[end1, \ digs]\), ";", "\[IndentingNewLine]", \(x2\ = \ N[end2, \ digs]\), ";", "\[IndentingNewLine]", \(fx1\ = \ f[x1]\), ";", "\[IndentingNewLine]", \(fx2\ = \ f[x2]\), ";", "\[IndentingNewLine]", \(ztol\ = \ 1\/10\^20\), ";", "\[IndentingNewLine]", "\[IndentingNewLine]", \(If[ x1\ \[Equal] \ x2, \ \(Return[Message[Bisection::ende]];\)]\), ";", "\[IndentingNewLine]", \(If[ fx1\ fx2\ > \ 0, \ \(Return[Message[Bisection::ends]];\)]\), ";", "\[IndentingNewLine]", \(If[ toln\ \[LessEqual] \ 0, \ \(Return[Message[Bisection::tol]];\)]\), ";", "\[IndentingNewLine]", \(If[ maxits\ \[LessEqual] \ 0, \ \(Return[Message[Bisection::its]];\)]\), ";", "\[IndentingNewLine]", \(intervl = {{x1, x2}}\), ";", "\[IndentingNewLine]", \(cnt\ = \ 1\), ";", "\[IndentingNewLine]", \(dx\ = \ Abs[x1 - x2]/2\), ";", "\[IndentingNewLine]", \(FLAG\ = \ 1\), ";", "\[IndentingNewLine]", \(Print["\< end1 = \>", \ N[end1, \ digs]]\), ";", "\[IndentingNewLine]", \(Print["\< end2 = \>", \ N[end2, \ digs]]\), ";", "\[IndentingNewLine]", \(Print["\< tol = \>", \ toln, \ "\<, its = \>", \ maxits, \ "\<, digits = \>", \ digs]\), ";", "\[IndentingNewLine]", "\[IndentingNewLine]", RowBox[{"While", "[", RowBox[{\(cnt\ \[LessEqual] \ maxits\ && \ FLAG\ \[Equal] \ 1\), ",", "\[IndentingNewLine]", "\t", RowBox[{\(x3\ = \ \(x1 + x2\)\/2\), ";", "\[IndentingNewLine]", "\t", \(fx3\ = \ f[x3]\), ";", "\[IndentingNewLine]", "\t", \(Print["\"\_cnt, \ "\< = \>", \ N[x3, digs], \ "\<, f(x\>"\_cnt, \ "\<) = \>", \ N[fx3, digs], \ "\<, |\[CapitalDelta]x| = \>", \ N[dx, digs]]\), ";", "\[IndentingNewLine]", "\t", "\[IndentingNewLine]", "\t", RowBox[{"If", "[", RowBox[{\(Abs[fx3]\ < \ ztol\), ",", "\[IndentingNewLine]", " ", \(Print["\<\n Vertical \ convergence! - function value is smaller than zero tolerance of \>", ztol]; \[IndentingNewLine]\t\tPrint["\", \ f[x]]; \[IndentingNewLine]\t\tPrint["\"]; \[IndentingNewLine]\t\tPrint["\< x = \ \>", \ N[x3, digs]]; \[IndentingNewLine]\t\tPrint["\", \ N[fx3, digs]]; \[IndentingNewLine]\t\tPrint["\<|\ \[CapitalDelta]x| = \>", \ N[dx, digs]]; \[IndentingNewLine]\t\tPrint["\", \ cnt]; \[IndentingNewLine]\t\tFLAG\ = \ 0\), ",", "\[IndentingNewLine]", StyleBox["\t\t", "Input"], RowBox[{ StyleBox["(*", "Input"], StyleBox[" ", "Input"], StyleBox["ELSE", "Input"], StyleBox[" ", "Input"], StyleBox["*)", "Input"]}], "\[IndentingNewLine]", " ", RowBox[{ RowBox[{"If", "[", RowBox[{\(dx\ < \ 2*toln\), ",", "\[IndentingNewLine]", " ", \(Print["\<\n \ Horizontal convergence! - interval width is smaller than twice tolerance of \ \>", toln]; \[IndentingNewLine]\t\t\ \ Print["\", \ f[x]]; \[IndentingNewLine]\t\t\ \ \ Print["\"]; \[IndentingNewLine]\t\t\ \ \ Print["\< x = \>", \ N[x3, digs]]; \[IndentingNewLine]\t\t\ \ \ Print["\", \ N[fx3, digs]]; \[IndentingNewLine]\t\t\ \ \ Print["\<|\[CapitalDelta]x| = \>", \ N[dx, digs]]; \[IndentingNewLine]\t\t\ \ \ Print["\", \ cnt]; \[IndentingNewLine]\t\tFLAG\ = \ 0\), ",", "\[IndentingNewLine]", StyleBox["\t\t", "Input"], StyleBox[\( (*\ ELSE\ *) \), "Input"], "\[IndentingNewLine]", "\t\t", \(cnt\ = \ cnt\ + \ 1; \[IndentingNewLine]\t\tIf[ fx3\ fx1\ < \ 0, \[IndentingNewLine]\t\t\tx2\ = \ x3; \[IndentingNewLine]\t\t\tfx2\ = \ fx3, \[IndentingNewLine]\t\t\t (*\ ELSE\ *) \[IndentingNewLine]\t\t\tx1\ = \ \ x3; \[IndentingNewLine]\t\t\tfx1\ = \ fx3]; \[IndentingNewLine]\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ AppendTo[intervl, {x1, x2}]; \[IndentingNewLine]\t\tdx\ = \ Abs[x1 - x2]/2;\)}], "]"}], ";"}]}], "]"}], ";"}]}], "]"}], ";", "\[IndentingNewLine]", " ", "\[IndentingNewLine]", "\[IndentingNewLine]", StyleBox[\(If[ FLAG\ == 1, \n\t\tPrint["\<\n We haven't yet converged, but \ we've exceeded the iteration limit of \>", \ maxits]; \n\t\tPrint["\", f[x]]; \n\t\tPrint["\", \ maxits]; \[IndentingNewLine]\t Print["\", N[x3, digs]]; \[IndentingNewLine]\t Print["\", N[fx3, digs]]; \[IndentingNewLine]\t Print["\<|\[CapitalDelta]x| = \>", N[dx, digs]];]\), "Input"], StyleBox[";", "Input"]}]}], StyleBox["\n", "Input"], StyleBox["\[IndentingNewLine]", "Input"], StyleBox[" ", "Input"], StyleBox["]", "Input"]}]}], StyleBox[";", "Input"]}], "\[IndentingNewLine]"}], "\[IndentingNewLine]", \(On[ General::"\"];\)}], "Input", InitializationCell->True] }, Closed]], Cell[TextData[{ "The initialization cells in this notebook define the command ", StyleBox["Bisection", FontWeight->"Bold"], ". This command allows us to use the Bisection Algorithm to find a root of \ a continuous function in a closed interval. The command generates the \ sequence of test points iterated to the root." }], "Text"], Cell[CellGroupData[{ Cell["Bisection", "Section"], Cell["\<\ Evaluate the following for a brief description of the syntax for Bisection:\ \>", "Text"], Cell[BoxData[ \(\(?Bisection\)\)], "Input"], Cell["\<\ At a minimum, Bisection needs the function, the endpoints of the interval, \ and a list name (to store the succession of intervals) in order to search for \ a root. Here is an example:\ \>", "Text"], Cell[BoxData[ \(Bisection[Sin[x] - 2*Exp[x], \ \(-2\), \ \(-5\), intervllist]\)], "Input"], Cell[TextData[{ "\nOn the output above, ", StyleBox["x", FontSlant->"Italic"], " represents the midpoint (or ", StyleBox["center", FontSlant->"Italic"], ") of the interval we are bisecting, ", StyleBox["f(x)", FontSlant->"Italic"], " is the function value, and |\[CapitalDelta]x| is the absolute error (the \ width of the interval divided by two). The algorithm terminates if one of \ the following occurs: \n\t1. ", StyleBox["f(x)", FontSlant->"Italic"], " is less than ", StyleBox["zero tolerance", FontSlant->"Italic"], " (defined as ", Cell[BoxData[ \(TraditionalForm\`10\^\(-20\)\)]], ")\n\t2. the maximum number of iterations has been exceeded\n\t3. the ", StyleBox["absolute error", FontWeight->"Bold"], " is less than the default (or user specified) tolerance." }], "Text"], Cell["\<\ Here is the list of intervals that were used to bracket the root:\ \>", "Text"], Cell[BoxData[ \(intervllist\)], "Input"], Cell[TextData[{ "One funky characteristic of this version of", StyleBox[" Bisection", FontWeight->"Bold"], " is that you ", StyleBox["must ", FontWeight->"Bold"], "clear the interval list between successive runs. Check out what happens \ if you don't:", " " }], "Text", FontColor->RGBColor[0, 0, 1]], Cell[BoxData[ \(Bisection[Sin[x] - 2*Exp[x], \ \(-2\), \ \(-5\), intervllist]\)], "Input"], Cell[TextData[{ "... you get all sorts of funky errors, in ", StyleBox["red", FontColor->RGBColor[1, 0, 0]], ", above.", " " }], "Text", FontColor->RGBColor[0, 0, 1]], Cell["\<\ You don't have to worry about which endpoint evaluates with a positive \ function value and which evaluates with a negative function value: for this \ implementation, the order of the endpoints doesn't matter; Bisection will \ find the same solution in the same number of iterations if we reverse them:\ \>", "Text"], Cell[BoxData[{ \(Clear[intervllist]\), "\[IndentingNewLine]", \(Bisection[Sin[x] - 2*Exp[x], \ \(-5\), \ \(-2\), intervllist]\)}], "Input"], Cell["\<\ Evaluate the following cell to see the default values for Bisection's \ optional arguments \ \>", "Text"], Cell[BoxData[ \(\(\(\ \)\(Options[Bisection]\)\)\)], "Input"], Cell[TextData[{ "If you want to change one of the default values, use the standard ", StyleBox["Mathematica", FontSlant->"Italic"], " notation for changing named options. Here is an example where the \ tolerance is set to ", Cell[BoxData[ \(TraditionalForm\`10\^\(-7\)\)]], ", the maximum number of iterations is set to 50, and 15 digits of \ precision are printed:" }], "Text"], Cell[BoxData[{ \(Clear[intervllist]\), "\[IndentingNewLine]", \(Bisection[Sin[x]\ - \ 2 Exp[x], \(-2\), \ \(-5\), intervllist, \ tol \[Rule] 10\^\(-7\), \ its\ \[Rule] \ 50, \ digits\ \[Rule] \ 15]\)}], "Input", AnimationDisplayTime->0.2197] }, Closed]], Cell[CellGroupData[{ Cell["Some Examples ", "Section"], Cell["\<\ In this section, we'll look more closely at the Bisection Algorithm and how \ it works\ \>", "Text"], Cell[CellGroupData[{ Cell["How does Bisection work?", "Subsubsection"], Cell[TextData[{ "Let's define a function to play with: ", Cell[BoxData[ \(x\^3 + 4 x\^2 - 10\)]], " on the interval [1,2]. For now, just accept that it has a single root in \ the interval, which is easily seen from the graph." }], "Text"], Cell[BoxData[{ \(\(Clear[f, x, plt, plt0, \ plt1, \ plt2, \ plt3, \ plt4, \ plt5, \ plt6];\)\), "\[IndentingNewLine]", \(\(f[x_] = x\^3 + 4 x\^2 - 10;\)\), "\[IndentingNewLine]", \(\(plt = Plot[f[x], {x, 1, 2}, PlotStyle \[Rule] RGBColor[1, 0, 0], PlotLabel \[Rule] f[x]];\)\)}], "Input"], Cell["So... how does it work? ", "Text"], Cell[BoxData[{ \(Clear[intervllist]\), "\[IndentingNewLine]", \(Bisection[f[x], 1, 2, intervllist]\)}], "Input"], Cell[BoxData[ \(intervllist\)], "Input"], Cell["\<\ Now, we'll take this list data and convert it into something useful to look \ at:\ \>", "Text"], Cell[TextData[{ "The first ", StyleBox["For", FontWeight->"Bold"], " loop creates ordered pairs to graph - here is the plan: graph the first \ bracketing interval at y=1, the second interval on y=2, the third interval on \ y=3, etc.\nThe second ", StyleBox["For ", FontWeight->"Bold"], "loop takes the ordered pairs and creates the graphs. You can animate the \ graphs by double clicking on one of them. The interval bracketing the root \ is in green, and the function is in red." }], "Text", FontColor->RGBColor[0, 0, 1]], Cell[BoxData[{ \(For[i = 1, i \[LessEqual] Length[intervllist], \(i++\), \[IndentingNewLine]\ \ \ \ PlotVals[ i] = {{intervllist[\([i, 1]\)], i}, {intervllist[\([i, 2]\)], i}}]\), "\[IndentingNewLine]", \(\(For[i = 1, i \[LessEqual] Length[intervllist] - 2, \(i++\), \[IndentingNewLine]\ \ \ plot[ i] = ListPlot[PlotVals[i], PlotStyle \[Rule] RGBColor[0, 1, 0], PlotJoined \[Rule] True, DisplayFunction \[Rule] Identity]; \[IndentingNewLine]Show[plt, plot[i]]];\)\)}], "Input"], Cell[TextData[{ "Note: the option", " ", StyleBox["DisplayFunction\[Rule]Identity", FontWeight->"Bold"], " causes output from a graphics command to ", StyleBox["not", FontVariations->{"Underline"->True}], " be displayed. This can be useful when we want to show a bunch of \ plots..." }], "Text", FontColor->RGBColor[0, 0, 1]] }, Closed]], Cell[CellGroupData[{ Cell[TextData[{ "How does ", StyleBox["Mathematica", FontSlant->"Italic"], " work?" }], "Subsubsection"], Cell[TextData[{ "So... how does ", StyleBox["Mathematica", FontSlant->"Italic"], " do in comparison? We can use the ", StyleBox["FindRoot ", FontWeight->"Bold"], "command to ", StyleBox["numerically approximate ", FontWeight->"Bold"], "the root:" }], "Text"], Cell[BoxData[ \(\(?FindRoot\)\)], "Input"], Cell["FindRoot[f[x]==0, {x,1.5}]", "Input", AspectRatioFixed->True], Cell["pretty good, eh?", "Commentary", FontColor->RGBColor[0, 0, 1]], Cell[TextData[{ "or we can use the ", StyleBox["NSolve ", FontWeight->"Bold"], "command to ", StyleBox["numerically approximate ", FontWeight->"Bold"], "the root - note that this only works for ", StyleBox["polynomial expressions", FontWeight->"Bold"], ":", " " }], "Text"], Cell[BoxData[ \(\(?NSolve\)\)], "Input"], Cell[BoxData[ \(NSolve[f[x] \[Equal] 0]\)], "Input"], Cell[TextData[{ "or we can use the ", StyleBox["Solve ", FontWeight->"Bold"], "command to solve ", StyleBox["algebraically:", FontWeight->"Bold"] }], "Text"], Cell[BoxData[ \(\(\(\ \)\(Solve[f[x] \[Equal] 0]\)\)\)], "Input"], Cell["ack... might look better if we converted after we solved!", "Text"], Cell[BoxData[ \(N[Solve[f[x] \[Equal] 0]]\)], "Input"], Cell[TextData[{ "Note: ", StyleBox["N[Solve[whatever]] ", FontWeight->"Bold"], "is ", StyleBox["not", FontVariations->{"Underline"->True}], " the same as using ", StyleBox["NSolve", FontWeight->"Bold"], "[whatever]!" }], "Text", FontColor->RGBColor[0, 0, 1]] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell["What's Wrong With It?", "Section"], Cell["Let's look at some problems we can have with Bisection:", "Text"], Cell[CellGroupData[{ Cell["What Interval Should I Use?", "Subsubsection"], Cell[TextData[{ "What happens if we have a more realistic problem like: ", StyleBox["Find a root of the function f(x) = ", FontSlant->"Italic"], Cell[BoxData[ \(\(-0.7290000000000001`\) + 5.346`\ x - 16.794`\ x\^2 + 29.296000000000003`\ x\^3 - 30.649000000000004`\ x\^4 + 19.23`\ x\^5 - 6.7`\ x\^6 + x\^7\)]], " accurate to ", Cell[BoxData[ \(TraditionalForm\`10\^\(-4\)\)]], ". Hmmm. what interval should I use? We can always ", StyleBox["plot", FontWeight->"Bold"], ":" }], "Text"], Cell[BoxData[{ \(\(Clear[f, x, \ i];\)\), "\[IndentingNewLine]", \(\(f[x_] = \(-0.7290000000000001`\) + 5.346`\ x - 16.794`\ x\^2 + 29.296000000000003`\ x\^3 - 30.649000000000004`\ x\^4 + 19.23`\ x\^5 - 6.7`\ x\^6 + x\^7;\)\), "\[IndentingNewLine]", \(\(Plot[f[x], {x, \(-5\), 5}];\)\)}], "Input"], Cell["\<\ From the graph it appears that there is a root somewhere in the interval [-2, \ 2]. Give this as the interval for the Bisection algorithm: \ \>", "Text"], Cell[BoxData[{ \(\ Clear[intervllist]\), "\[IndentingNewLine]", \(Bisection[\ ]\)}], "Input"], Cell["\<\ Yup... you need to actually type something up there, not just hit the enter \ key...\ \>", "Text", FontColor->RGBColor[1, 0, 0]], Cell[TextData[{ "... Well, graphing ", StyleBox["usually", FontWeight->"Bold"], " works to find an interval, but what happens if we have two (or more) \ roots that are very close together? I intentially selected a nasty function \ to motivate using another technique: Letting ", StyleBox["Mathematica", FontSlant->"Italic"], " evaluate many points over an interval to see if the sign of the function \ changes:" }], "Text"], Cell[BoxData[ \(\(\(Do[\ Print["\", i, \ "\< function is \>", f[i]], \ {i, 0, 2, 0.05}]\)\(\ \)\)\)], "Input"], Cell[TextData[{ "The ", StyleBox["Do", FontWeight->"Bold"], " command has the following format:" }], "Text", FontColor->RGBColor[0, 0, 1]], Cell[BoxData[ \(\(?Do\)\)], "Input"], Cell[TextData[{ "So we told ", StyleBox["Mathematica", FontSlant->"Italic"], " ", "to print out values of ", StyleBox["f(x)", FontSlant->"Italic"], " ranging from ", StyleBox["x", FontSlant->"Italic"], "=0 to ", StyleBox["x", FontSlant->"Italic"], "=2 with an increment of 0.05.", " " }], "Text", FontColor->RGBColor[0, 0, 1]], Cell[TextData[{ "Use the output of the ", StyleBox["Do ", FontWeight->"Bold"], "statement and the Bisection algorithm to search for two roots in [0,2]. " }], "Text"], Cell[BoxData[ \(\ \)], "Input"], Cell[TextData[{ "What are the ", StyleBox["exact", FontWeight->"Bold"], " roots?" }], "Text"], Cell[TextData[{ StyleBox["(Type your answer below)", FontSlant->"Italic"], "\n" }], "Commentary", Background->RGBColor[0, 1, 1]] }, Closed]], Cell[CellGroupData[{ Cell["What about those intermediate solutions?", "Subsubsection"], Cell[TextData[{ "The Bisection algorithm uses very little information about the function - \ we do not care which endpoint is actually closest to the root, we always use \ the midpoint as our next evaluation point. \nLook at what happens for the \ simple function ", Cell[BoxData[ \(TraditionalForm\`f(x) = x\^3\)]], " on the interval [-1, 0.9]. Go ahead and use the Bisection algorithm to \ find the root at 0:" }], "Text"], Cell[BoxData[ \(\(\(Clear[f, x, i];\)\(\[IndentingNewLine]\)\)\)], "Input"], Cell["\<\ Look at the sequence of test points generated by the algorithm. Rather than \ looking at the estimated error bound which is printed, compare the function \ value of the test points with the true root of 0. What sort of strange \ behavior do you see? \ \>", "Text"], Cell[TextData[{ StyleBox["(Type your answer below)", FontSlant->"Italic"], "\n" }], "Commentary", Background->RGBColor[0, 1, 1]] }, Closed]], Cell[CellGroupData[{ Cell["What happens to functions that never go negative?", "Subsubsection"], Cell[TextData[{ "How can we use the Bisection algorithm to find the the root of a function \ like ", Cell[BoxData[ \(TraditionalForm\`f(x) = x\^8\)]], "?" }], "Text"], Cell[BoxData[{ \(\(Clear[f, x];\)\), "\[IndentingNewLine]", \(\(f[x_] = x\^8;\)\), "\[IndentingNewLine]", \(\(Plot[f[x], {x, \(-2\), 2}];\)\)}], "Input"], Cell[TextData[{ "The function never goes negative, thus no interval [a,b] exists where ", StyleBox["f(a)", FontSlant->"Italic"], "\[CenterDot]", StyleBox["f(b)", FontSlant->"Italic"], "<0. How could you modify the ", StyleBox["function", FontSlant->"Italic"], " (", StyleBox["not the algorithm!", FontWeight->"Bold"], ") to make use of the Bisection algorithm in finding the root that exists \ at ", StyleBox["x", FontSlant->"Italic"], "=0?" }], "Text"], Cell["\<\ (Type your answer here) \ \>", "Commentary", Background->RGBColor[0, 1, 1]], Cell[BoxData[ \(\[IndentingNewLine]\)], "Input"], Cell[TextData[StyleBox["Good Job!", FontColor->RGBColor[1, 0, 0]]], "Text"] }, Closed]], Cell[CellGroupData[{ Cell["Last Word...", "Subsubsection"], Cell["\<\ What are the advantages and disadvantages of the Bisection Algorithm?\ \>", "Text"], Cell["\<\ (Type your answer here) \ \>", "Commentary", Background->RGBColor[0, 1, 1]], Cell[TextData[{ "I hope you included:\t\"It ", StyleBox["always", FontVariations->{"Underline"->True}], " converges to a solution and it is easy to determine a bound for the \ number of iterations needed to ensure a given accuracy.\" as a strength. \ Next time, we'll look at some algorithms that perform \"better\" from a rate \ of convergence standpoint." }], "Commentary", FontColor->RGBColor[0, 0, 1]] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell["Some Homework (due Friday, Feb 14, by 5:00 pm)", "Section"], Cell[TextData[{ "You can work these problems ", StyleBox["together", FontSlant->"Italic"], " if you wish, but write up ", StyleBox["individual", FontWeight->"Bold"], " hand ins.. thanks" }], "Text"], Cell[TextData[{ "1. How many iterations are necessary to find a root accurate to within ", Cell[BoxData[ \(TraditionalForm\`10\^\(-4\)\)]], " if the interval we are working with is: \n\t[-10, 10] \t[-1,1]\t\t[-.1, \ .1]\t\t [-3,3]?\n2. Use the Bisection algorithm to find roots accurate to \ within ", Cell[BoxData[ \(TraditionalForm\`\(\(10\^\(-4\)\)\(\ \)\)\)]], "for ", Cell[BoxData[ \(TraditionalForm\`f(x) = x\^3 - 7 x\^2 + 14 x - 6\)]], " on the intervals:\n\t[0, 1]\t[1,3. 2]\t[3.2, 4]\n2. Use the Bisection \ algorithm to find, accurate to within ", Cell[BoxData[ \(TraditionalForm\`10\^\(-4\)\)]], ", the ", StyleBox["first", FontWeight->"Bold"], " positive intersection of the functions:\n\t\t ", Cell[BoxData[ \(TraditionalForm\`f(x) = x\)]], " and ", StyleBox["g(x)", FontSlant->"Italic"], " = tan(", StyleBox["x", FontSlant->"Italic"], ")\n3. Use the Bisection algorithm to find an approximation of ", Cell[BoxData[ \(TraditionalForm\`\@15\)]], "correct to within ", Cell[BoxData[ \(TraditionalForm\`10\^\(-4\)\)]], "." }], "Text"], Cell[BoxData[ \(\ \)], "Input"] }, Closed]] }, FrontEndVersion->"4.1 for Microsoft Windows", ScreenRectangle->{{0, 1024}, {0, 632}}, AutoGeneratedPackage->None, WindowToolbars->{"RulerBar", "EditBar"}, CellGrouping->Manual, WindowSize->{1015, 600}, WindowMargins->{{Automatic, 0}, {Automatic, 0}}, PrintingCopies->1, PrintingPageRange->{Automatic, Automatic}, StyleDefinitions -> "DemoText.nb" ] (******************************************************************* Cached data follows. If you edit this Notebook file directly, not using Mathematica, you must remove the line containing CacheID at the top of the file. The cache data will then be recreated when you save this file from within Mathematica. *******************************************************************) (*CellTagsOutline CellTagsIndex->{} *) (*CellTagsIndex CellTagsIndex->{} *) (*NotebookFileOutline Notebook[{ Cell[1705, 50, 95, 1, 70, "Title"], Cell[1803, 53, 41, 0, 41, "Subtitle"], Cell[CellGroupData[{ Cell[1869, 57, 76, 3, 71, "Subsubsection"], Cell[1948, 62, 10946, 199, 2312, "Input", InitializationCell->True] }, Closed]], Cell[12909, 264, 343, 7, 47, "Text"], Cell[CellGroupData[{ Cell[13277, 275, 28, 0, 54, "Section"], Cell[13308, 277, 99, 2, 29, "Text"], Cell[13410, 281, 47, 1, 40, "Input"], Cell[13460, 284, 209, 4, 29, "Text"], Cell[13672, 290, 101, 2, 40, "Input"], Cell[13776, 294, 846, 25, 172, "Text"], Cell[14625, 321, 89, 2, 29, "Text"], Cell[14717, 325, 44, 1, 40, "Input"], Cell[14764, 328, 322, 11, 29, "Text"], Cell[15089, 341, 101, 2, 40, "Input"], Cell[15193, 345, 180, 7, 29, "Text"], Cell[15376, 354, 327, 5, 48, "Text"], Cell[15706, 361, 155, 3, 60, "Input"], Cell[15864, 366, 115, 3, 29, "Text"], Cell[15982, 371, 65, 1, 40, "Input"], Cell[16050, 374, 399, 10, 48, "Text"], Cell[16452, 386, 270, 5, 61, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[16759, 396, 33, 0, 34, "Section"], Cell[16795, 398, 110, 3, 29, "Text"], Cell[CellGroupData[{ Cell[16930, 405, 49, 0, 44, "Subsubsection"], Cell[16982, 407, 252, 6, 29, "Text"], Cell[17237, 415, 332, 6, 80, "Input"], Cell[17572, 423, 40, 0, 29, "Text"], Cell[17615, 425, 121, 2, 60, "Input"], Cell[17739, 429, 44, 1, 40, "Input"], Cell[17786, 432, 105, 3, 29, "Text"], Cell[17894, 437, 545, 13, 79, "Text"], Cell[18442, 452, 594, 12, 120, "Input"], Cell[19039, 466, 348, 11, 29, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[19424, 482, 114, 5, 28, "Subsubsection"], Cell[19541, 489, 285, 11, 29, "Text"], Cell[19829, 502, 46, 1, 40, "Input"], Cell[19878, 505, 69, 1, 40, "Input"], Cell[19950, 508, 70, 1, 23, "Commentary"], Cell[20023, 511, 301, 12, 29, "Text"], Cell[20327, 525, 44, 1, 40, "Input"], Cell[20374, 528, 56, 1, 40, "Input"], Cell[20433, 531, 173, 7, 29, "Text"], Cell[20609, 540, 69, 1, 40, "Input"], Cell[20681, 543, 73, 0, 29, "Text"], Cell[20757, 545, 58, 1, 40, "Input"], Cell[20818, 548, 287, 12, 29, "Text"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[21154, 566, 40, 0, 34, "Section"], Cell[21197, 568, 71, 0, 29, "Text"], Cell[CellGroupData[{ Cell[21293, 572, 52, 0, 44, "Subsubsection"], Cell[21348, 574, 539, 15, 48, "Text"], Cell[21890, 591, 333, 5, 80, "Input"], Cell[22226, 598, 164, 3, 29, "Text"], Cell[22393, 603, 102, 2, 60, "Input"], Cell[22498, 607, 140, 4, 29, "Text"], Cell[22641, 613, 443, 11, 48, "Text"], Cell[23087, 626, 139, 3, 40, "Input"], Cell[23229, 631, 150, 6, 29, "Text"], Cell[23382, 639, 40, 1, 40, "Input"], Cell[23425, 642, 366, 17, 29, "Text"], Cell[23794, 661, 176, 5, 29, "Text"], Cell[23973, 668, 35, 1, 40, "Input"], Cell[24011, 671, 103, 5, 29, "Text"], Cell[24117, 678, 138, 5, 50, "Commentary"] }, Closed]], Cell[CellGroupData[{ Cell[24292, 688, 65, 0, 28, "Subsubsection"], Cell[24360, 690, 437, 9, 79, "Text"], Cell[24800, 701, 79, 1, 60, "Input"], Cell[24882, 704, 276, 5, 48, "Text"], Cell[25161, 711, 138, 5, 50, "Commentary"] }, Closed]], Cell[CellGroupData[{ Cell[25336, 721, 74, 0, 28, "Subsubsection"], Cell[25413, 723, 178, 6, 29, "Text"], Cell[25594, 731, 167, 3, 80, "Input"], Cell[25764, 736, 496, 18, 48, "Text"], Cell[26263, 756, 87, 4, 50, "Commentary"], Cell[26353, 762, 52, 1, 60, "Input"], Cell[26408, 765, 77, 1, 29, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[26522, 771, 37, 0, 28, "Subsubsection"], Cell[26562, 773, 93, 2, 29, "Text"], Cell[26658, 777, 87, 4, 50, "Commentary"], Cell[26748, 783, 418, 9, 36, "Commentary"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[27215, 798, 65, 0, 34, "Section"], Cell[27283, 800, 216, 8, 29, "Text"], Cell[27502, 810, 1148, 35, 215, "Text"], Cell[28653, 847, 35, 1, 40, "Input"] }, Closed]] } ] *) (******************************************************************* End of Mathematica Notebook file. *******************************************************************)