(************** 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[ 79829, 2127]*) (*NotebookOutlinePosition[ 80599, 2153]*) (* CellTagsIndexPosition[ 80555, 2149]*) (*WindowFrame->Normal*) Notebook[{ Cell[TextData[{ "Lab 5: ", StyleBox["C", FontSize->72], StyleBox["o", FontSize->36], StyleBox["n", FontSize->24], StyleBox["v", FontSize->18], StyleBox["e", FontSize->16], StyleBox["r", FontSize->14], StyleBox["g", FontSize->12], StyleBox["e", FontSize->11], StyleBox["n", FontSize->9], StyleBox["c", FontSize->7], StyleBox["e", FontSize->8], " : Getting Back to Our Roots!" }], "Title", Background->RGBColor[0, 0, 1]], Cell["Math 342\tSpring 2003", "Subtitle"], Cell[CellGroupData[{ Cell["\<\ Initialization Cells \ \>", "Subsubsection"], Cell[BoxData[{ RowBox[{\( (*\(:\)\(Title : \ Bisection\ Algorithm\)\ *) \), "\n", \( (*\(:\)\(Author : \ Mark\ Parker\)\ *) \), "\n", \( (*\(:\)\(Mathematica\ \(Version : \ 4.0\)\)\ *) \), "\n", \( (*\(:\)\(Version : \ 2.0\)\ *) \), "\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\"]\).\>";\), "\n"}], "\[IndentingNewLine]", \(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"], StyleBox[\( (*\ ELSE\ *) \), "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], Cell[BoxData[{ RowBox[{\( (*\(:\)\(Title : \ Secant\ Algorithm\)\ *) \), "\n", \( (*\(:\)\(Author : \ Mark\ Parker\)\ *) \), "\n", \( (*\(:\)\(Mathematica\ \(Version : \ 4.0\)\)\ *) \), "\n", \( (*\(:\)\(Version : \ 2.0\)\ *) \), "\n", \( (*\(\(:\)\(History : \n\tV1 .0\ by\ M . \ Parker\)\), \ September\ 2000. \[IndentingNewLine]\ \ V2 .0\ by\ M . \ Parker, \ February\ 2003\[IndentingNewLine]\ \ \ \ \ \ \ cleaned\ up\ code*) \), "\n", "\n", \( (*\ Last\ \(Revision : \ \ February\ 2003\)\ *) \), "\n", "\n", \(Off[General::"\"];\)}], "\n", RowBox[{\(Off[General::"\"];\), "\n"}], "\n", \(Clear[Secant, f0, end1, end2, tol, its, \ digits];\), "\[IndentingNewLine]", RowBox[{\(Secant::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\"]\), with starting points \!\(\* StyleBox[\"end1\",\nFontSlant->\"Italic\"]\) and \!\(\* StyleBox[\"end2\",\nFontSlant->\"Italic\"]\). All other parameters are \ optional. The root is found within a 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 16).\>";\), "\n"}], "\[IndentingNewLine]", \(Secant::ende\ = \ "\";\), "\[IndentingNewLine]", \(Secant::tol\ = \ \ "\";\), "\[IndentingNewLine]", RowBox[{\(Secant::its\ = \ "\";\), "\[IndentingNewLine]"}], "\[IndentingNewLine]", RowBox[{\(Options[Secant] = {tol\ \[Rule] \ 0.00001, \ its\ \[Rule] \ 100, \ digits\ \[Rule] \ 16};\), "\n"}], "\n", RowBox[{ RowBox[{ RowBox[{\(Secant[f0_, end1_, end2_, opts___Rule]\), ":=", RowBox[{"Module", "[", RowBox[{\({x1, x2, x3, \ FLAG, fx1, fx2, fx3, f, ztol, cnt, \ maxits, \ digs, \ toln}\), ",", "\[IndentingNewLine]", RowBox[{\(toln\ = \ \(tol\ /. \ {opts}\)\ /. \ Options[Secant]\), ";", "\[IndentingNewLine]", \(maxits\ = \ \(its\ /. \ {opts}\)\ \ /. \ Options[Secant]\), ";", "\[IndentingNewLine]", \(digs\ = \ \(digits\ /. \ {opts}\)\ \ /. \ Options[Secant]\), ";", "\[IndentingNewLine]", \({f0, \ end1, \ end2, \ 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]", "\[IndentingNewLine]", \(If[ x1\ \[Equal] \ x2, \ \(Return[Message[Secant::ende]];\)]\), ";", "\[IndentingNewLine]", \(If[ toln\ \[LessEqual] \ 0, \ \(Return[Message[Secant::tol]];\)]\), ";", "\[IndentingNewLine]", \(If[ maxits\ \[LessEqual] \ 0, \ \(Return[Message[Secant::its]];\)]\), ";", "\[IndentingNewLine]", \(cnt\ = \ 1\), ";", "\[IndentingNewLine]", \(If[ Abs[fx1] < Abs[fx2], \[IndentingNewLine]\t temp = fx1; \[IndentingNewLine]\t fx1 = fx2; \[IndentingNewLine]\t fx2 = temp; \[IndentingNewLine]\t temp = x1; \[IndentingNewLine]\t x1 = x2; \[IndentingNewLine]\tx2 = temp;]\), ";", "\[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\ = \ x2 - fx2*\(x1 - x2\)\/\(fx1 - fx2\)\), ";", "\[IndentingNewLine]", "\t", \(fx3 = f[x3]\), ";", "\[IndentingNewLine]", "\t", \(Print["\"\_cnt, \ "\< = \>", \ N[x3, digs], \ "\<, f(x\>"\_cnt, \ "\<) = \>", \ N[fx3, digs]]\), ";", "\[IndentingNewLine]", "\t", "\[IndentingNewLine]", "\t", RowBox[{"If", "[", RowBox[{\(Abs[fx3]\ < \ toln\), " ", ",", "\[IndentingNewLine]", " ", \(Print["\<\n Vertical \ convergence! - function value is smaller than tolerance of \>", toln]; \[IndentingNewLine]\t\tPrint["\", \ f[x]]; \[IndentingNewLine]\t\tPrint["\"]; \[IndentingNewLine]\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ Print["\< x = \>", \ N[x3, digs]]; \[IndentingNewLine]\t\t\ Print["\", \ N[fx3, digs]]; \[IndentingNewLine]\t\tPrint["\", \ cnt]; \[IndentingNewLine]\t\tFLAG\ = \ 0\), ",", "\[IndentingNewLine]", StyleBox["\t\t", "Input"], StyleBox[\( (*\ ELSE\ *) \), "Input"], "\[IndentingNewLine]", "\t\t", \(\(cnt\ = \ cnt\ + \ 1;\)\[IndentingNewLine] \t\t\(x1 = x2;\)\[IndentingNewLine] \t\t\(fx1 = fx2;\)\[IndentingNewLine] \t\t\(x2\ = \ x3;\)\[IndentingNewLine] \t\t\(fx2 = fx3;\)\)}], "]"}], ";"}]}], "]"}], ";", "\[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]];]\), "Input"], StyleBox[";", "Input"]}]}], StyleBox["\n", "Input"], StyleBox["\[IndentingNewLine]", "Input"], StyleBox[" ", "Input"], StyleBox["]", "Input"]}]}], StyleBox[";", "Input"]}], "\[IndentingNewLine]"}], "\[IndentingNewLine]", \(On[ General::"\"];\)}], "Input", InitializationCell->True], Cell[BoxData[{ RowBox[{\( (*\(:\)\(Title : \ False\ Position\ Algorithm\)\ *) \), "\n", \( (*\(:\)\(Author : \ Mark\ Parker\)\ *) \), "\n", \( (*\(:\)\(Mathematica\ \(Version : \ 4.0\)\)\ *) \), "\n", \( (*\(:\)\(Version : \ 2.0\)\ *) \), "\n", \( (*\(\(:\)\(History : \n\tV1 .0\ by\ M . \ Parker\)\), \ September\ 2000. \[IndentingNewLine]\ \ V2 .0\ by\ M . \ Parker, \ February\ 2003\[IndentingNewLine]\ \ \ \ \ \ \ cleaned\ up\ code*) \), "\n", "\n", \( (*\ Last\ \(Revision : \ \ February\ 2003\)\ *) \), "\n", "\n", \(Off[General::"\"];\)}], "\n", RowBox[{\(Off[General::"\"];\), "\n"}], "\n", \(Clear[FalsePosition, f0, end1, end2, tol, its, \ digits];\), "\[IndentingNewLine]", RowBox[{\(FalsePosition::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 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 16).\>";\), "\n"}], "\[IndentingNewLine]", \(FalsePosition::ends\ = \ "\";\), "\[IndentingNewLine]", \ \(FalsePosition::ende\ = \ "\";\), "\ \[IndentingNewLine]", \(FalsePosition::tol\ = \ "\";\), "\[IndentingNewLine]", RowBox[{\(FalsePosition::its\ = \ "\";\), "\[IndentingNewLine]"}], "\[IndentingNewLine]", RowBox[{\(Options[FalsePosition] = {tol\ \[Rule] \ 0.00001, \ its\ \[Rule] \ 100, \ digits\ \[Rule] \ 16};\), "\n"}], "\n", RowBox[{ RowBox[{ RowBox[{\(FalsePosition[f0_, end1_, end2_, opts___Rule]\), ":=", RowBox[{"Module", "[", RowBox[{\({x1, x2, x3, \ FLAG, fx1, fx2, fx3, f, ztol, cnt, \ maxits, \ digs, \ toln}\), ",", "\[IndentingNewLine]", RowBox[{\(toln\ = \ \(tol\ /. \ {opts}\)\ /. \ Options[FalsePosition]\), ";", "\[IndentingNewLine]", \(maxits\ = \ \(its\ /. \ {opts}\)\ \ /. \ Options[FalsePosition]\), ";", "\[IndentingNewLine]", \(digs\ = \ \(digits\ /. \ {opts}\)\ \ /. \ Options[FalsePosition]\), ";", "\[IndentingNewLine]", \({f0, \ end1, \ end2, \ 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]", "\[IndentingNewLine]", \(If[ x1\ \[Equal] \ x2, \ \(Return[Message[FalsePosition::ende]];\)]\), ";", "\[IndentingNewLine]", \(If[ fx1\ fx2\ > \ 0, \ \(Return[Message[FalsePosition::ends]];\)]\), ";", "\[IndentingNewLine]", \(If[ toln\ \[LessEqual] \ 0, \ \(Return[Message[FalsePosition::tol]];\)]\), ";", "\[IndentingNewLine]", \(If[ maxits\ \[LessEqual] \ 0, \ \(Return[Message[FalsePosition::its]];\)]\), ";", "\[IndentingNewLine]", \(cnt\ = \ 1\), ";", "\[IndentingNewLine]", \(dx\ = \ Abs[x1 - x2]\), ";", "\[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\ = \ x2 - fx2*\(x1 - x2\)\/\(fx1 - fx2\)\), ";", "\[IndentingNewLine]", "\t", \(fx3\ = \ f[x3]\), ";", "\[IndentingNewLine]", "\t", \(Print["\"\_cnt, \ "\< = \>", \ N[x3, digs], \ "\<, f(x\>"\_cnt, \ "\<) = \>", \ N[fx3, digs]]\), ";", "\[IndentingNewLine]", "\t", "\[IndentingNewLine]", "\t", RowBox[{"If", "[", RowBox[{\(Abs[fx3]\ < \ toln\), ",", "\[IndentingNewLine]", " ", \(Print["\<\n Vertical \ convergence! - function value is smaller than tolerance of \>", toln]; \[IndentingNewLine]\t\tPrint["\", \ f[x]]; \[IndentingNewLine]\t\tPrint["\"]; \[IndentingNewLine]\t\tPrint["\< x = \ \>", \ N[x3, digs]]; \[IndentingNewLine]\t\tPrint["\", \ N[fx3, digs]]; \[IndentingNewLine]\t\tPrint["\", \ cnt]; \[IndentingNewLine]\t\tFLAG\ = \ 0\), ",", "\[IndentingNewLine]", "\[IndentingNewLine]", StyleBox["\t\t", "Input"], StyleBox[\( (*\ ELSE\ *) \), "Input"], "\[IndentingNewLine]", "\t\t", \(\(cnt\ = \ cnt\ + \ 1;\)\[IndentingNewLine] \t\t\(If[ 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]", 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]];]\), "Input"], StyleBox[";", "Input"]}]}], StyleBox["\[IndentingNewLine]", "Input"], StyleBox["\[IndentingNewLine]", "Input"], StyleBox[" ", "Input"], StyleBox["]", "Input"]}]}], StyleBox[";", "Input"]}], "\[IndentingNewLine]"}], "\[IndentingNewLine]", \(On[ General::"\"];\)}], "Input", InitializationCell->True], Cell[BoxData[{ RowBox[{\( (*\(:\)\(Title : \ Newton' s\ Method\)\ *) \), "\n", \( (*\(:\)\(Author : \ Mark\ Parker\)\ *) \), "\n", \( (*\(:\)\(Mathematica\ \(Version : \ 4.0\)\)\ *) \), "\n", \( (*\(:\)\(Version : \ 2.0\)\ *) \), "\n", \( (*\(\(:\)\(History : \n\tV1 .0\ by\ M . \ Parker\)\), \ September\ 2000. \n\ \ \ \ V2 .0\ by\ M . \ Parker, \ February\ 2003\[IndentingNewLine]\ \ \ \ \ \ \ cleaned\ up\ code*) \), "\n", "\n", \( (*\ Last\ \(Revision : \ \ February\ 2003\)\ *) \), "\n", "\n", \(Off[General::"\"];\)}], "\n", RowBox[{\(Off[General::"\"];\), "\n"}], "\n", \(Clear[OurNewton, f0, start, tol, its, \ digits];\), "\[IndentingNewLine]", RowBox[{\(OurNewton::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\"]\), with starting point \!\(\* StyleBox[\"start\",\nFontSlant->\"Italic\"]\). All other parameters are \ optional. The root is found within a 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 16).\>";\), "\[IndentingNewLine]"}], "\n", \(OurNewton::end0\ = \ "\";\), "\[IndentingNewLine]", \(OurNewton::tol\ = \ \ "\";\), "\[IndentingNewLine]", RowBox[{\(OurNewton::its\ = \ "\";\), "\[IndentingNewLine]"}], "\[IndentingNewLine]", RowBox[{\(Options[OurNewton] = {tol\ \[Rule] \ 0.00001, \ its\ \[Rule] \ 100, \ digits\ \[Rule] \ 16};\), "\n"}], "\n", RowBox[{ RowBox[{ RowBox[{\(OurNewton[f0_, start_, opts___Rule]\), ":=", RowBox[{"Module", "[", RowBox[{\({x1, x2, \ FLAG, fx1, fx2, f, fprime, \ cnt, \ maxits, \ digs, \ toln}\), ",", "\[IndentingNewLine]", RowBox[{\(toln\ = \ \(tol\ /. \ {opts}\)\ /. \ Options[OurNewton]\), ";", "\[IndentingNewLine]", \(maxits\ = \ \(its\ /. \ {opts}\)\ \ /. \ Options[OurNewton]\), ";", "\[IndentingNewLine]", \(digs\ = \ \(digits\ /. \ {opts}\)\ \ /. \ Options[OurNewton]\), ";", "\[IndentingNewLine]", \({f0, start, \ tol, \ its, \ digits}\), ";", "\[IndentingNewLine]", \(Set @@ {f[x_], f0}\), ";", "\[IndentingNewLine]", \(x1\ = \ N[start, \ digs]\), ";", "\[IndentingNewLine]", \(fx1\ = \ f[x1]\), ";", "\[IndentingNewLine]", \(fprime = \(f'\)[x1]\), ";", "\[IndentingNewLine]", "\[IndentingNewLine]", "\[IndentingNewLine]", \(If[ fprime \[Equal] 0, \ \(Return[Message[OurNewton::end0]];\)]\), ";", "\[IndentingNewLine]", \(If[ toln\ \[LessEqual] \ 0, \ \(Return[Message[OurNewton::tol]];\)]\), ";", "\[IndentingNewLine]", \(If[ maxits\ \[LessEqual] \ 0, \ \(Return[Message[OurNewton::its]];\)]\), ";", "\[IndentingNewLine]", \(cnt\ = \ 1\), ";", "\[IndentingNewLine]", \(FLAG\ = \ 1\), ";", "\[IndentingNewLine]", \(Print["\< start = \>", \ N[start, \ digs]]\), ";", "\[IndentingNewLine]", \(Print["\< tol = \>", \ toln, \ "\<, its = \>", \ maxits, \ "\<, digits = \>", \ digs]\), ";", "\[IndentingNewLine]", "\[IndentingNewLine]", RowBox[{"While", "[", RowBox[{\(cnt\ \[LessEqual] \ maxits\ && \ FLAG\ \[Equal] \ 1\), ",", "\[IndentingNewLine]", "\t", RowBox[{\(x2 = \ x1 - fx1\/fprime\), ";", "\[IndentingNewLine]", "\t", \(fx2 = f[x2]\), ";", "\[IndentingNewLine]", "\t", \(Print["\"\_cnt, \ "\< = \>", \ N[x2, digs], \ "\<, f(x\>"\_cnt, \ "\<) = \>", \ N[fx2, digs]]\), ";", "\[IndentingNewLine]", "\t", "\[IndentingNewLine]", "\t", RowBox[{"If", "[", RowBox[{\(Abs[fx2]\ < \ toln\), " ", ",", "\[IndentingNewLine]", " ", \(Print["\<\n Vertical \ convergence! - function value is smaller than tolerance of \>", toln]; \[IndentingNewLine]\t\tPrint["\", \ f[x]]; \[IndentingNewLine]\t\tPrint["\"]; \[IndentingNewLine]\t\tPrint["\< x = \ \>", \ N[x2, digs]]; \[IndentingNewLine]\t\tPrint["\", \ N[fx2, digs]]; \[IndentingNewLine]\t\tPrint["\", \ cnt]; \[IndentingNewLine]\t\tFLAG\ = \ 0\), ",", "\[IndentingNewLine]", StyleBox["\t\t", "Input"], StyleBox[\( (*\ ELSE\ *) \), "Input"], "\[IndentingNewLine]", "\t\t", \(\(cnt\ = \ cnt\ + \ 1;\)\[IndentingNewLine] \t\t\(x1 = x2;\)\[IndentingNewLine] \t\t\(fx1 = fx2;\)\[IndentingNewLine] \t\t\(fprime = \(f'\)[x1];\)\[IndentingNewLine] \t\t\(If[ fprime \[Equal] 0, \ \(Return[ Message[OurNewton::end0]];\)];\)\)}], "]"}], ";"}]}], "]"}], ";", "\[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[x2, digs]]; \[IndentingNewLine]\t Print["\", N[fx2, 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 commands ", StyleBox["Bisection", FontWeight->"Bold"], ", ", StyleBox["Secant", FontWeight->"Bold"], ", ", StyleBox["FalsePosition", FontWeight->"Bold"], ", and ", StyleBox["OurNewton", FontWeight->"Bold"], ". These commands allow us use the respective algorithms to find roots of \ a continuous function. The commands generate the sequence of test points \ iterated to the root." }], "Text"], Cell[CellGroupData[{ Cell[TextData[StyleBox["Instructions!", FontColor->RGBColor[1, 0, 0]]], "Section"], Cell[TextData[{ "Work either individually or in groups of 2, going through the entire \ notebook. If you have questions, ask. There isn't any real homework to hand \ in from this Lab, but you should make sure that you ", StyleBox["understand", FontWeight->"Bold"], " what is going on - so you may need to spend time thinking about it \ outside of class. Bring unresolved questions to class on Tuesday, where \ we'll wrap up any last questions and talk about the test next Thursday." }], "Subsubtitle"] }, Closed]], Cell[CellGroupData[{ Cell["The Basics...", "Section"], Cell[CellGroupData[{ Cell["Bisection", "Subsubsection"], Cell[TextData[{ "Evaluate the following for a brief description of the syntax for ", StyleBox["Bisection", FontWeight->"Bold"], ":" }], "Text"], Cell[BoxData[ \(\(?Bisection\)\)], "Input"], Cell[TextData[{ "At a minimum, ", StyleBox["Bisection", FontWeight->"Bold"], " needs the function and endpoints of the interval to search for a root. \ Here is an example:" }], "Text"], Cell[BoxData[ \(Bisection[Sin[x] - 2*Exp[x], \ \(-2\), \ \(-5\), intervl]\)], "Input"], Cell[TextData[{ "Note that the order of the endpoints of the interval doesn't matter; ", StyleBox["Bisection", FontWeight->"Bold"], " will find the same solution in the same number of iterations if we \ reverse them:" }], "Text"], Cell[BoxData[{ \(Clear[intervl]\), "\[IndentingNewLine]", \(Bisection[Sin[x] - 2*Exp[x], \ \(-5\), \ \(-2\), intervl]\)}], "Input"], Cell[TextData[{ "Evaluate the following cell to see the default values for ", StyleBox["Bisection", FontWeight->"Bold"], "'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[intervl]\), "\[IndentingNewLine]", \(Bisection[Sin[x]\ - \ 2 Exp[x], \(-2\), \ \(-5\), \ intervl, tol \[Rule] 10\^\(-7\), \ its\ \[Rule] \ 50, \ digits\ \[Rule] \ 15]\)}], "Input", AnimationDisplayTime->0.2197] }, Closed]], Cell[CellGroupData[{ Cell["Secant", "Subsubsection"], Cell[TextData[{ "Evaluate the following for a brief description of the syntax for ", StyleBox["Secant", FontWeight->"Bold"], ":" }], "Text"], Cell[BoxData[ \(\(?Secant\)\)], "Input"], Cell[TextData[{ "At a minimum, ", StyleBox["Secant", FontWeight->"Bold"], " needs the function and the first two test points to search for a root. \ Here is an example:" }], "Text"], Cell[BoxData[ \(Secant[Sin[x] - 2*Exp[x], \ \(-2\), \ \(-5\)]\)], "Input"], Cell[TextData[{ "Note that the order of the endpoints doesn't matter; ", StyleBox["Secant", FontWeight->"Bold"], " will order them with ", Cell[BoxData[ \(TraditionalForm\`x\_0\)]], "having the largest function value and ", Cell[BoxData[ \(TraditionalForm\`x\_1\)]], "having the smallest - and so finds the same solution in the same number of \ iterations if we reverse them:" }], "Text"], Cell[BoxData[ \(Secant[Sin[x] - 2*Exp[x], \ \(-5\), \ \(-2\)]\)], "Input"], Cell[TextData[{ "Evaluate the following cell to see the default values for ", StyleBox["Secant", FontWeight->"Bold"], "'s optional arguments " }], "Text"], Cell[BoxData[ \(\(\(\ \)\(Options[Secant]\)\)\)], "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 20 digits of \ precision are printed:" }], "Text"], Cell[BoxData[ \(Secant[Sin[x]\ - \ 2 Exp[x], \(-2\), \ \(-5\), \ tol \[Rule] 10\^\(-7\), \ its\ \[Rule] \ 50, \ digits\ \[Rule] \ 20]\)], "Input", AnimationDisplayTime->0.2197] }, Closed]], Cell[CellGroupData[{ Cell["Regula Falsi (False Position)", "Subsubsection"], Cell[TextData[{ "Evaluate the following for a brief description of the syntax for ", StyleBox["FalsePosition", FontWeight->"Bold"], ":" }], "Text"], Cell[BoxData[ \(\(?FalsePosition\)\)], "Input"], Cell[TextData[{ "At a minimum, ", StyleBox["FalsePosition", FontWeight->"Bold"], " needs the function and endpoints of the interval to search for a root. \ Here is an example:" }], "Text"], Cell[BoxData[ \(FalsePosition[Sin[x] - 2*Exp[x], \ \(-2\), \ \(-5\)]\)], "Input"], Cell[TextData[{ "Note that the order of the endpoints of the interval doesn't matter; ", StyleBox["FalsePosition", FontWeight->"Bold"], " will find the same solution in the same number of iterations if we \ reverse them:" }], "Text"], Cell[BoxData[ \(FalsePosition[Sin[x] - 2*Exp[x], \ \(-5\), \ \(-2\)]\)], "Input"], Cell[TextData[{ "Evaluate the following cell to see the default values for ", StyleBox["FalsePosition", FontWeight->"Bold"], "'s optional arguments " }], "Text"], Cell[BoxData[ \(\(\(\ \)\(Options[FalsePosition]\)\)\)], "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 20 digits of \ precision are printed:" }], "Text"], Cell[BoxData[ \(FalsePosition[Sin[x]\ - \ 2 Exp[x], \(-2\), \ \(-5\), \ tol \[Rule] 10\^\(-7\), \ its\ \[Rule] \ 50, \ digits\ \[Rule] \ 20]\)], "Input", AnimationDisplayTime->0.2197] }, Closed]], Cell[CellGroupData[{ Cell["Newton", "Subsubsection"], Cell[TextData[{ "Evaluate the following for a brief description of the syntax for ", StyleBox["OurNewton", FontWeight->"Bold"], ":" }], "Text"], Cell["\<\ Note: Newton is a protected word in Mathematica, so I made up a New and \ Original name...\ \>", "Commentary", FontColor->RGBColor[0, 0, 1]], Cell[BoxData[ \(\(?OurNewton\)\)], "Input"], Cell[TextData[{ "At a minimum, ", StyleBox["OurNewton", FontWeight->"Bold"], " needs the function and the first test point to search for a root. Here \ is an example:" }], "Text"], Cell[BoxData[ \(OurNewton[Sin[x] - 2*Exp[x], \ \(-2\)]\)], "Input"], Cell[TextData[{ "Evaluate the following cell to see the default values for ", StyleBox["OurNewton", FontWeight->"Bold"], "'s optional arguments " }], "Text"], Cell[BoxData[ \(\(\(\ \)\(Options[OurNewton]\)\)\)], "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 20 digits of \ precision are printed:" }], "Text"], Cell[BoxData[ \(OurNewton[Sin[x]\ - \ 2 Exp[x], \(-2\), \ tol \[Rule] 10\^\(-7\), \ its\ \[Rule] \ 50, \ digits\ \[Rule] \ 20]\)], "Input", AnimationDisplayTime->0.2197] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell["Some Experiments ", "Section"], Cell["\<\ In this section, we'll look at what happens with the different algorithms \ when we test them on different kinds of functions...\ \>", "Text"], Cell[CellGroupData[{ Cell["A Simple Function...", "Subsubsection"], Cell[TextData[{ "Let's define a function to play with: ", Cell[BoxData[ \(\((x - 1)\)\^2 - 1\)]], " on the interval [1,3]. We'll see how each algorithm does at finding the \ root ", StyleBox["x", FontSlant->"Italic"], "=2. No tricks up our sleeve today, this is a pretty simple and \ well-behaved function:" }], "Text"], Cell[BoxData[{ \(\(Clear[f, g, h, x];\)\), "\[IndentingNewLine]", \(\(f[x_] = \((x - 1)\)\^2 - 1;\)\), "\[IndentingNewLine]", \(\(Plot[f[x], {x, 1, 3}, PlotStyle \[Rule] RGBColor[1, 0, 0], PlotLabel \[Rule] f[x]];\)\)}], "Input"], Cell["So how do the algorithms perform?", "Text"], Cell["\<\ Life would be way too easy if we let Bisection have 1 and 3 as its starting \ points, since the midpoint is exactly the root we are looking for, so we'll \ skew things a bit.\ \>", "Text", FontColor->RGBColor[0, 0, 1]], Cell[BoxData[{ \(Clear[intervl]\), "\[IndentingNewLine]", \(Bisection[f[x], 0.9, 2.9, intervl]\)}], "Input"], Cell["Not too bad... how are the others?", "Text"], Cell["Secant[f[x],.9,2.9]", "Input", AspectRatioFixed->True], Cell[BoxData[ \(FalsePosition[f[x], .9, 2.9]\)], "Input"], Cell[TextData[{ "What happens if we let Newton start with ", StyleBox["x", FontSlant->"Italic"], "=1? What happens to the derivative there?" }], "Commentary", FontColor->RGBColor[0, 0, 1]], Cell[BoxData[ \(OurNewton[f[x], 1]\)], "Input"], Cell[BoxData[ \(OurNewton[f[x], 3]\)], "Input"], Cell[TextData[{ StyleBox["Question:\tHow well does each algorithm work? How many \ iterations? What is the actual error?", FontWeight->"Bold"], " " }], "Text", Background->RGBColor[0, 1, 1]] }, Closed]], Cell[CellGroupData[{ Cell["A slightly harder function?", "Subsubsection"], Cell[TextData[{ "So... what happens if we simply change the little exponent from a 2 to a \ 4: ", Cell[BoxData[ \(\((x - 1)\)\^4 - 1\)]], ". Note that as we increase the power (and keep it even), the effect is to \ flatten the graph around its base, and to thus increase the slope around the \ the root:" }], "Text"], Cell[BoxData[{ \(\(g[x_] = \((x - 1)\)\^4 - 1;\)\), "\[IndentingNewLine]", \(\(Plot[{f[x], g[x]}, {x, 1, 3}, PlotStyle \[Rule] {RGBColor[1, 0, 0], RGBColor[0, 1, 0]}, PlotLabel \[Rule] {f[x], g[x]}];\)\)}], "Input"], Cell[TextData[{ StyleBox["Question:\tThink about what we covered in class Tuesday - \ specifically, ", FontWeight->"Bold"], StyleBox["how", FontWeight->"Bold", FontSlant->"Italic"], StyleBox[" the algorithms work. Do you think that this change in the \ function will tend to improve an algorithm's ability to locate the root? ", FontWeight->"Bold"] }], "Text", Background->RGBColor[0, 1, 1]], Cell["Well... let's experiment!", "Text"], Cell[BoxData[{ \(Clear[intervl]\), "\[IndentingNewLine]", \(Bisection[g[x], 0.9, 2.1, intervl]\)}], "Input"], Cell["Secant[g[x],.9,2.9]", "Input", AspectRatioFixed->True], Cell[TextData[StyleBox["Question:\tAck! What happened here? Look closely at \ the values Secant calculated...Is there a pattern? What is going on?!?", FontWeight->"Bold"]], "Text", Background->RGBColor[0, 1, 1]], Cell[BoxData[ \(FalsePosition[g[x], .9, 2.9]\)], "Input"], Cell[BoxData[ \(OurNewton[g[x], 3]\)], "Input"], Cell["pretty good, eh?", "Text", FontColor->RGBColor[0, 0, 1]], Cell[TextData[StyleBox["Question:\tSo, which algorithms still find the \ correct root? For those that do, how many more iterations does it take? Can \ you hypothesize about the attributes of f(x) and g(x) that cause this \ behavior? ", FontWeight->"Bold"]], "Text", Background->RGBColor[0, 1, 1]], Cell["Test out your theory as we increase the exponent to an 8:", "Text"], Cell[BoxData[{ \(h[x_] = \ \ yeah, \ \(type\ something\ in\ here ... \)\ the\ labs\ \ aren' t\ THAT\ easy ... \), "\[IndentingNewLine]", \(\(Plot[{f[x], g[x], h[x]}, {x, 1, 3}, PlotStyle \[Rule] {RGBColor[1, 0, 0], RGBColor[0, 1, 0], RGBColor[0, 0, 1]}];\)\)}], "Input"], Cell["Go ahead and test the algorithms:", "Text"], Cell[BoxData[ \(\(\(Yup ... \)\(\ \)\(you'\) \(ve\)\(\ \)\(gotta\)\(\ \)\(do\)\(\ \ \)\(some\)\(\ \)\(more\)\(\ \)\(work\)\(\ \)\(here\)\(\ \)\(too!\)\(\ \ \)\)\)], "Input"], Cell[TextData[StyleBox["Question:\tWhich ones work? How many iterations do \ they take? Have you learned anything from this experiment?", FontWeight->"Bold"]], "Text", Background->RGBColor[0, 1, 1]] }, Closed]], Cell[CellGroupData[{ Cell["A flat function...", "Subsubsection"], Cell[TextData[{ "What happens if the function is really flat around the root, instead of \ very steep? Try using the function ", Cell[BoxData[ \(x\^2\)]], " on the interval [-2,5]:" }], "Text"], Cell[BoxData[{ \(\(Clear[f, fprime, x];\)\), "\[IndentingNewLine]", \(\(f[x_] = x\^2;\)\), "\[IndentingNewLine]", \(\(Plot[f[x], {x, \(-2\), 5}, PlotStyle \[Rule] RGBColor[1, 0, 0], PlotLabel \[Rule] f[x]];\)\)}], "Input"], Cell[TextData[{ "Since Bisection and False Position won't work directly on the function ", StyleBox["(why?)", FontWeight->"Bold"], ", they can try to find the root of the ", StyleBox["derivative", FontSlant->"Italic"], " of the function:" }], "Text"], Cell[BoxData[{ \(\(fprime[x_] = \(f'\)[x];\)\), "\[IndentingNewLine]", \(\(Plot[fprime[x], {x, \(-2\), 5}, PlotStyle \[Rule] RGBColor[1, 0, 0], PlotLabel \[Rule] fprime[x]];\)\)}], "Input"], Cell[TextData[{ StyleBox[" Question:\t", FontWeight->"Bold"], StyleBox["Do you think this function will give those two algorithms an \ unfair advantage? Why or why not?", FontWeight->"Bold"] }], "Text", Background->RGBColor[0, 1, 1]], Cell[BoxData[{ \(Clear[intervl]\), "\[IndentingNewLine]", \(Bisection[fprime[x], \(-2\), 5, intervl]\)}], "Input"], Cell["Secant[f[x],-2,5]", "Input", AspectRatioFixed->True], Cell[BoxData[ \(FalsePosition[fprime[x], \(-2\), 5]\)], "Input"], Cell[TextData[StyleBox["Question:\tWhy did this only take one iteration to \ converge? - look at the graph of fprime and think about how the Secant \ algorithm works.", FontWeight->"Bold"]], "Text", Background->RGBColor[0, 1, 1]], Cell[BoxData[ \(OurNewton[f[x], \(-2\)]\)], "Input"], Cell[TextData[StyleBox["Question:\tHow did they do?", FontWeight->"Bold"]], "Text", Background->RGBColor[0, 1, 1]] }, Closed]], Cell[CellGroupData[{ Cell["A flatter function...", "Subsubsection"], Cell[TextData[{ "So... what happens if we simply change the little exponent from a 2 to a \ 4: ", Cell[BoxData[ \(x\^4\)]], ". Note that as we increase the power (and keep it even), the effect is to \ flatten the graph around the root:" }], "Text"], Cell[BoxData[{ \(\(g[x_] = x\^4;\)\), "\[IndentingNewLine]", \(\(Plot[{f[x], g[x]}, {x, \(-2\), 5}, PlotStyle \[Rule] {RGBColor[1, 0, 0], RGBColor[0, 1, 0]}, PlotLabel \[Rule] {f[x], g[x]}];\)\)}], "Input"], Cell[TextData[{ "Of course, we still need the derivative function for ", StyleBox["Bisection", FontWeight->"Bold"], " and ", StyleBox["False Position", FontWeight->"Bold"], ":" }], "Text"], Cell[BoxData[{ \(\(gprime[x_] = \(g'\)[x];\)\), "\[IndentingNewLine]", \(\(Plot[{fprime[x], gprime[x]}, {x, \(-2\), 5}, PlotStyle \[Rule] {RGBColor[1, 0, 0], RGBColor[0, 1, 0]}, PlotLabel \[Rule] {fprime[x], gprime[x]}];\)\)}], "Input"], Cell["How will they perform?", "Text"], Cell[BoxData[{ \(Clear[intervl]\), "\[IndentingNewLine]", \(Bisection[gprime[x], \(-2\), 5, intervl]\)}], "Input"], Cell["Secant[g[x],-2,5]", "Input", AspectRatioFixed->True], Cell["\<\ Question:\tHey... Will FalsePosition still converge in 1 iteration? Why or \ why not?\ \>", "Text", FontWeight->"Bold", Background->RGBColor[0, 1, 1]], Cell[BoxData[ \(FalsePosition[gprime[x], \(-2\), 5]\)], "Input"], Cell[BoxData[ \(OurNewton[g[x], \(-2\)]\)], "Input"], Cell[TextData[StyleBox["Question:\tWhat happened? Which algorithms \ converged, which didn't, why?", FontWeight->"Bold"]], "Text", Background->RGBColor[0, 1, 1]], Cell[TextData[{ StyleBox["Question:\tRepeat this experiment for the function ", FontWeight->"Bold", FontColor->GrayLevel[0]], Cell[BoxData[ \(TraditionalForm\`x\^8\)], FontWeight->"Bold", FontColor->GrayLevel[0]], StyleBox[". What do you think will happen?", FontWeight->"Bold", FontColor->GrayLevel[0]] }], "Text", FontColor->RGBColor[1, 0, 0], Background->RGBColor[0, 1, 1]], Cell[BoxData[ \(\ \)], "Input"], Cell[TextData[StyleBox["Question:\tWhat did you observe? What have you \ learned about \"flat\" functions?", FontWeight->"Bold"]], "Text", Background->RGBColor[0, 1, 1]] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell["Fixed-Point Iteration", "Section"], Cell[TextData[{ "We can implement the Fixed-Point iteration method (Section 6.1) directly \ in ", StyleBox["Mathematica ", FontSlant->"Italic"], "via the ", StyleBox["FixedPointList", FontWeight->"Bold"], " command (or the ", StyleBox["FixedPoint", FontWeight->"Bold"], " command if we just want the value of the root without all intermediate \ iterates)" }], "Text"], Cell[BoxData[ \(\(?FixedPointList\)\)], "Input"], Cell[TextData[{ "A hidden feature that we don't get from the ", StyleBox["Mathematica ", FontSlant->"Italic"], "help is that we can specify a maximum number of iterations. Let's look at \ how to do that for the", " example function from Section 1.6: ", Cell[BoxData[ \(TraditionalForm\`f(x) = x\^2 - 2 x - 3\)]], ", we'll first use the iterative form: ", Cell[BoxData[ \(TraditionalForm\`x\_\(n + 1\) = \@\(2 x\_n + 3\)\)]], " with ", Cell[BoxData[ \(TraditionalForm\`x\_0 = 4\)]], ":" }], "Text"], Cell[BoxData[{ \(\(Clear[g, x];\)\), "\[IndentingNewLine]", \(\(g[x_] = \@\(2 x + 3\);\)\), "\[IndentingNewLine]", \(FixedPointList[g, 4. ]\)}], "Input"], Cell[TextData[{ "Notice that we don't use g[x] in the call to FixedPointList! You ", StyleBox["must ", FontWeight->"Bold"], "use g rather than g[x]." }], "Text", FontColor->RGBColor[0, 0, 1]], Cell["\<\ Here's what happens if we put a restriction on the number of iterations:\ \>", "Text"], Cell[BoxData[ \(FixedPointList[g, 4. , 8]\)], "Input"], Cell["\<\ Another (undocumented) form of the command allows us to specify the equality \ test that we perform:\ \>", "Text"], Cell[BoxData[ \(FixedPointList[g, 4. , 25, SameTest \[Rule] \((Abs[#1 - #2] < 10\^\(-4\)\ &)\)]\)], "Input"], Cell[TextData[{ "In the SameTest option, #1 and #2 are placeholders that refer to the two \ most recent iterates. We compare them to see if they differ by at most ", Cell[BoxData[ \(TraditionalForm\`10\^\(-4\)\)]], " and terminate if they do. The & at the end of the SameTest option tells \ ", StyleBox["Mathematica", FontSlant->"Italic"], " to load values into the 2 placeholders and perform the test (something \ called a ", StyleBox["pure function", FontSlant->"Italic"], " in ", StyleBox["Mathematica)", FontSlant->"Italic"], "." }], "Text", FontColor->RGBColor[0, 0, 1]], Cell[TextData[{ "What happens with the non-converging form ", Cell[BoxData[ \(TraditionalForm\`x\_\(n + 1\) = \((x\^2 - 3)\)\/2\)]] }], "Text"], Cell[BoxData[{ \(\(Clear[g, x];\)\), "\[IndentingNewLine]", \(\(g[x_] = \((x\^2 - 3)\)\/2;\)\), "\[IndentingNewLine]", \(FixedPointList[g, 4. ]\)}], "Input"], Cell["\<\ So, it will usually be safer to use this command with a restriction on \ iterations:\ \>", "Text"], Cell[BoxData[ \(FixedPointList[g, 4. , 8]\)], "Input"], Cell[TextData[{ "We can also create Cobweb Plots using this cool function I found at the \ Wolfram web site... Execute this cell ", StyleBox["once", FontWeight->"Bold"], " to define the command:" }], "Text"], Cell[BoxData[{ \(Clear[x, a, n, expr]\), "\[IndentingNewLine]", \(CobwebPlot[expr_, x_, a_, n_] := Block[{f, nl, pts, min, max}, f = Function[x, expr]; \[IndentingNewLine]nl = NestList[f, a, n]; \[IndentingNewLine]pts = Transpose[\({Drop[#, \(-1\)], Rest[#]} &\)@ Flatten[Transpose[\({#, #} &\)@nl]]]; \[IndentingNewLine]min = Min[nl]; \[IndentingNewLine]max = Max[nl]; \[IndentingNewLine]Plot[ f[x], {x, min, max}, Epilog \[Rule] {{Hue[0], Line[pts]}, {Hue[ .7], Line[{{min, min}, {max, max}}]}}, PlotRange \[Rule] {min, max}, Frame \[Rule] True]]\)}], "Input"], Cell[TextData[{ "... now use it: the syntax is ", StyleBox[" CobwebPlot[function, variable, starting point, iterations]", FontWeight->"Bold"] }], "Text"], Cell[BoxData[ \(\(CobwebPlot[\@\(2 x + 3\), x, 4, 25];\)\)], "Input"], Cell[TextData[{ "The output is ", "black curve = function, ", StyleBox["blue curve ", FontColor->RGBColor[0, 0, 1]], "is y=x, and ", StyleBox["red lines ", FontColor->RGBColor[1, 0, 0]], "are the iterations" }], "Text"], Cell[TextData[StyleBox["Cool.", FontWeight->"Bold"]], "Text", TextAlignment->Center, TextJustification->0], Cell[TextData[{ "Back to more mundane thoughts...\nThe more general form of the ", StyleBox["FixedPointList", FontWeight->"Bold"], " command is the ", StyleBox["NestWhileList", FontWeight->"Bold"], " command, and since several options that I've used are undocumented, it \ probably means that we should use NestWhileList (but I'm not too worried \ about it, maybe we'll need to change with the next ", StyleBox["Mathematica", FontSlant->"Italic"], " release)." }], "Text"], Cell[BoxData[ \(\(?NestWhileList\)\)], "Input"] }, Closed]], Cell[CellGroupData[{ Cell["Convergence... an Introduction...", "Section"], Cell[TextData[{ "In the last part of this endless lab, we'll look at ways to compare the \ performance of these algorithms. There are many ways to do this, but we will \ analyze them based upon the sequence of points they generate in approximating \ the root of a function. We will also give some consideration to the amount \ of ", StyleBox["work", FontSlant->"Italic"], " that is performed by each algorithm to generate the next point. This \ will help us determine:\n\twhich is better? \n\tAn algorithm that is within \ ", Cell[BoxData[ \(TraditionalForm\`10\^\(-7\)\)]], " of 0 after 7 iterations, but takes many computations to determine those 7 \ iterates, or\n\tAn algorithm that is within ", Cell[BoxData[ \(TraditionalForm\`10\^\(-7\)\)]], "of 0 after 100 iterations, but takes very few computations to determine \ those 14 iterates. \n" }], "Text", TextAlignment->Left, TextJustification->0], Cell[TextData[{ "On today's journey, we will also look one last time at how we measure the \ error of our calculation, and take a quick glance at the fixed-point \ iteration algorithm - which should remind you somewhat of the ", StyleBox["discrete dynamical systems", FontWeight->"Bold"], " that you saw way back in MA 131/232", "." }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell["One Last Look at Error", "Section"], Cell[TextData[{ "Suppose that we have the function ", Cell[BoxData[ \(TraditionalForm\`f(x) = \((x - 1)\)\^10\)]], ". We know that the real root, call it ", StyleBox["r", FontSlant->"Italic"], ", occurs at ", StyleBox["x", FontSlant->"Italic"], " = 1. Using some algorithm, suppose the estimate of the root at step ", StyleBox["n", FontSlant->"Italic"], " is ", Cell[BoxData[ \(TraditionalForm\`x\_n = 1 + 1\/n\)]], ". How many iterations must be performed in order for ", Cell[BoxData[ \(TraditionalForm\`\(\(|\)\(f( x\_n)\)\(|\)\(\(<\)\(10\^\(-4\)\)\)\)\)]], "? " }], "Text"], Cell["\<\ In other words, how many iterations does it take before our standard \ convergence criteria are met?\ \>", "Text", FontColor->RGBColor[0, 0, 1]], Cell[BoxData[ \(\ \)], "Input"], Cell[TextData[{ "How many iterations must be performed for ", Cell[BoxData[ \(TraditionalForm\`\(\(|\)\(r - x\_n\)\(|\)\(\(<\)\(10\^\(-4\)\)\)\)\)]], " ?" }], "Text"], Cell[TextData[{ "In other words, how many iterations does it take before we are within ", Cell[BoxData[ \(TraditionalForm\`10\^\(-4\)\)]], "of the actual ", StyleBox["x", FontSlant->"Italic"], "-value of the root?" }], "Text", FontColor->RGBColor[0, 0, 1]], Cell[BoxData[ \(\ \)], "Input"], Cell[TextData[StyleBox["Question:\tInteresting isn't it... of course, if we \ already knew the root, we wouldn't be using some algorithm to search for it \ anyway! What does this illustrate for you?", FontWeight->"Bold"]], "Text", Background->RGBColor[0, 1, 1]], Cell["For grins, here is what is happening:", "Text"], Cell[BoxData[{ \(\(Clear[f, x, plt1, plt2, pts];\)\), "\[IndentingNewLine]", \(\(f[x_] = \((x - 1)\)\^10;\)\), "\[IndentingNewLine]", \(\(plt1 = Plot[f[x], {x, 0.5, \ 1.5}];\)\), "\[IndentingNewLine]", \(\(pts = Table[{x, Chop[f[x], 10\^\(-4\)]}, {x, 0.50, 1.5, 0.001}];\)\), "\[IndentingNewLine]", \(\(plt2 = ListPlot[pts, PlotJoined \[Rule] True, PlotStyle \[Rule] RGBColor[1, 0, 0]];\)\), "\[IndentingNewLine]", \(\(Show[plt1, plt2];\)\)}], "Input"] }, Closed]], Cell[CellGroupData[{ Cell["Convergence: A Practical Look", "Section"], Cell[TextData[{ "One way to examine the relative performance of an algorithm is to look at \ the improvement in the root approximation at each step. Think of the points \ generated during the search for a root as a ", StyleBox["sequence", FontWeight->"Bold"], ". We want to look at the behavior of that sequence ", StyleBox["as we get close to the root", FontWeight->"Bold"], ". Thus, we can talk about the convergence rate of an algorithm ", StyleBox["even if it won't converge for all functions and/or starting \ conditions!", FontWeight->"Bold"], " \nA solution method that produces a sequence, ", Cell[BoxData[ \(TraditionalForm\`{x\_n}\)]], ", of approximations that converges to a root ", StyleBox["r ", FontSlant->"Italic"], "is said to converge ", StyleBox["linearly", FontWeight->"Bold"], " if, ", StyleBox["for large values of n, ", FontSlant->"Italic"], "a constant 0 < ", StyleBox["K < ", FontSlant->"Italic"], "1 exists with ", Cell[BoxData[ \(TraditionalForm\`\(\(|\)\(x\_\(n + 1\) - r\)\(|\)\(\(\[LessEqual]\)\(K\)\)\(|\)\(x\_n - r\)\(|\)\)\)]], " . Another way to look at this is to say that , ", StyleBox["for large values of n", FontSlant->"Italic"], ", we have ", Cell[BoxData[ \(TraditionalForm\`\(\(|\)\(x\_\(n + 1\)\)\(|\)\(\(\[LessEqual]\)\(K\)\)\(|\)\(x\_n\)\(|\)\)\)]], " . In other words, the sequence values are getting closer together at \ every step (maybe not initially, but after some number of iterations, they \ will).\nCheck this out using Fixed-Point Iteration on the function ", Cell[BoxData[ \(TraditionalForm\`f(x) = \(e\^x\) \(sin(x)\) - x\^2\)]], " to find a root near ", StyleBox["x", FontSlant->"Italic"], " = 2.6 using the starting point ", Cell[BoxData[ \(TraditionalForm\`x\_0 = 3\)]], ". Try using several different stopping values (more than 10)." }], "Text"], Cell[BoxData[{\(Clear[f, g, x];\), "\[IndentingNewLine]", \(f[x_] = \[ExponentialE]\^x\ Sin[x] - x\^2;\), "\[IndentingNewLine]", \(g[ x_] = \@\(\(\[ExponentialE]\^x\) Sin[x]\);\), "\[IndentingNewLine]", RowBox[{"FixedPointList", "[", RowBox[{ StyleBox["??", FontColor->RGBColor[1, 0, 0]], RowBox[{ StyleBox["??", FontColor->RGBColor[1, 0, 0]], StyleBox["]", FontColor->GrayLevel[0]]}]}]}]}], "Input"], Cell[TextData[StyleBox["Question:\tBased upon the ratios of successive \ iterates, do you think the Fixed Point algorithm converges linearly?", FontWeight->"Bold"]], "Text", Background->RGBColor[0, 1, 1]], Cell[TextData[{ "A solution method that produces a sequence, ", Cell[BoxData[ \(TraditionalForm\`{x\_n}\)]], ", of approximations that converges to a root ", StyleBox["r ", FontSlant->"Italic"], "is said to converge ", StyleBox["quadratically", FontWeight->"Bold"], " if, ", StyleBox["for large values of n, ", FontSlant->"Italic"], "a constant 0 < ", StyleBox["K < ", FontSlant->"Italic"], "1 exists with ", Cell[BoxData[ \(TraditionalForm\`\(\(|\)\(x\_\(n + 1\) - r\)\(|\)\(\(\[LessEqual]\)\(\(K(\(|\)\(x\_n - r\)\(|\))\)\^2\)\)\)\)]], " . Another way to look at this is to say that , ", StyleBox["for large values of n", FontSlant->"Italic"], ", we have ", Cell[BoxData[ \(TraditionalForm\`\(\(|\)\(x\_\(n + 1\)\)\(|\)\(\(\[LessEqual]\)\(\(K(\(|\)\(x\_n\)\(|\))\)\^2\)\)\)\ \)]], " . " }], "Text"], Cell[TextData[{ StyleBox["Question:\tThe first definition is really useful here. What does \ the value ", FontWeight->"Bold"], Cell[BoxData[ \(TraditionalForm\`\(\(|\)\(x\_\(n + 1\) - r\)\(|\)\)\)], FontWeight->"Bold"], StyleBox[" represent?", FontWeight->"Bold"] }], "Text", Background->RGBColor[0, 1, 1]], Cell[TextData[{ "Hint: remember that ", StyleBox["r", FontSlant->"Italic"], " is the actual root, and ", Cell[BoxData[ \(TraditionalForm\`x\_\(n + 1\)\)]], "is the ", Cell[BoxData[ \(TraditionalForm\`\((n + 1)\)\^st\)]], " approximation to it." }], "Text", FontColor->RGBColor[0, 0, 1]], Cell[TextData[{ "So, a solution method that converges quadratically has, after a sufficient \ number of iterations, the current error term on the order of the square of \ the previous error term. Thus, in effect, we gain about ", StyleBox["2 decimal places of accuracy after each iteration", FontWeight->"Bold"], ".\nTo illustrate, check out the same function as above with Newton's \ method, still using ", StyleBox["x", FontSlant->"Italic"], " = 3 as the starting point:" }], "Text"], Cell[BoxData[ \(OurNewton[f[x], 3.0]\)], "Input"], Cell[TextData[StyleBox["Question:\tBy comparing the errors of successive \ iterates, what do you think the order of convergence is for Newton's method?", FontWeight->"Bold"]], "Text", Background->RGBColor[0, 1, 1]], Cell[TextData[{ "An important point to make here is that we ", StyleBox["cannot", FontWeight->"Bold"], " reach a definitive conclusion about the convergence order of an algorithm \ by looking ", StyleBox["only", FontWeight->"Bold"], " at its behavior on a few functions. We ", StyleBox["must", FontWeight->"Bold"], " be able to generalize with theory." }], "Text"], Cell[TextData[{ "To see why, consider what happens if we use Newton's method on: ", Cell[BoxData[ \(TraditionalForm\`f(x) = \(e\^\(-x\)\)(x\^2 - 2 x + 1)\)]], " with a starting point of ", StyleBox["x", FontSlant->"Italic"], " = 1.1:" }], "Text"], Cell[BoxData[{ \(\(Clear[f, x];\)\), "\[IndentingNewLine]", \(\(f[x_] = Exp[\(-x\)] \((x^2 - 2 x + 1)\);\)\), "\[IndentingNewLine]", \(OurNewton[f[x], 1.1]\)}], "Input"], Cell[TextData[{ StyleBox["Question:\tBased upon this experiment, and the knowledge that the \ real root is at ", FontWeight->"Bold"], StyleBox["x", FontWeight->"Bold", FontSlant->"Italic"], StyleBox[" = 1.0, what is your estimate of the convergence order of \ Newton's method?", FontWeight->"Bold"] }], "Text", Background->RGBColor[0, 1, 1]], Cell[TextData[{ "We'll explore later what happened in this case, for now it will have to \ suffice to say that \"most of the time, when Newton's method does converge, \ it will do so quadratically\"... which is why it is viewed as a very powerful \ method for root finding.\nWhat does it mean to say that a method converges \ linearly versus converging quadratically? Suppose we have two sequences of \ values from two different algorithms. One converges linearly to 0, the other \ quadratically to 0. Both started at 1 and the constant value ", StyleBox["K", FontSlant->"Italic"], " = 0.5 in both cases:\n", StyleBox["LINEAR:\t", FontWeight->"Bold"], Cell[BoxData[ \(TraditionalForm\`\(\(|\)\(x\_1\)\(|\)\(\(\[LessEqual]\)\(K\)\)\(|\)\(\ x\_0\)\(|\)\)\)]], " which means ", Cell[BoxData[ \(TraditionalForm\`\(\(|\)\(x\_1\)\(|\)\(\(\[LessEqual]\)\(0.5\)\)\(|\)\ \(x\_0\)\(|\)\)\)]], " and then ", Cell[BoxData[ \(TraditionalForm\`\(\(|\)\(x\_2\)\(|\)\(\(\[LessEqual]\)\(0.5\^2\)\)\(|\ \)\(x\_0\)\(|\)\)\)]], " and so on until ", Cell[BoxData[ \(TraditionalForm\`\(\(|\)\(x\_n\)\(|\)\(\(\[LessEqual]\)\(0.5\^n\)\)\(|\ \)\(x\_0\)\(|\)\)\)]], "\n", StyleBox["QUADRATIC:\t", FontWeight->"Bold"], Cell[BoxData[ \(TraditionalForm\`\(\(|\)\(x\_1\)\(|\)\(\(\[LessEqual]\)\(\(K(\(|\)\(x\ \_0\)\(|\))\)\^2\)\)\)\)]], " which means ", Cell[BoxData[ \(TraditionalForm\`\(\(|\)\(x\_1\)\(|\)\(\(\[LessEqual]\)\(0.5 \((\(|\)\ \(x\_0\)\(|\))\)\^2\)\)\)\)]], " and then ", Cell[BoxData[ \(TraditionalForm\`\(\(|\)\(x\_2\)\(|\)\(\(\[LessEqual]\)\(0.5 \((0.5 | \ x\_0 | )\)\^2\)\)\)\)]], " or ", Cell[BoxData[ \(TraditionalForm\`\(\(|\)\(x\_2\)\(|\)\(\(\[LessEqual]\)\(0.5\^3\)\)\(|\ \)\(x\_0\)\( | \^4\)\)\)]], "and so on until ", Cell[BoxData[ \(TraditionalForm\`\(\(|\)\(x\_n\)\(|\)\(\(\[LessEqual]\)\(\(0.5\^\(2\^\ n - 1\)\) \((\(|\)\(x\_0\)\(|\))\)\^\(2\^n\)\)\)\)\)]], "\nSo what does that mean practically? After ", StyleBox["n", FontSlant->"Italic"], " iterations, we have (try a few values for ", StyleBox["n", FontSlant->"Italic"], "):" }], "Text"], Cell[BoxData[{ \(\(n = 10;\)\), "\[IndentingNewLine]", \(Print["\", N[0.5\^n], \ "\< after \>", \ n, \ "\< iterations\>"]\), "\[IndentingNewLine]", \(Print["\", \ N[0.5\^\(2\^n - 1\)], "\< after \>", \ n, \ "\< iterations\>"]\), "\[IndentingNewLine]", \(\(Clear[n];\)\)}], "Input"], Cell[TextData[StyleBox[" Question:\tSo... now how important is this idea of \ rate of convergence?", FontWeight->"Bold"]], "Text", Background->RGBColor[0, 1, 1]], Cell[TextData[StyleBox["Question:\tWhat are the caveats that go along with \ using rate of convergence as a criteria for the effectiveness of an \ algorithm? What are we measuring at each step - Actual error? or How close \ are consecutive terms of the iterated sequence?", FontWeight->"Bold"]], "Text", Background->RGBColor[0, 1, 1]] }, Closed]], Cell[CellGroupData[{ Cell["Convergence: Some Theory", "Section"], Cell[TextData[{ "For the ", StyleBox["Serious Minded Student\[Copyright] ", FontWeight->"Bold"], ". We'll play with the Fixed-Point algorithm first. The iteration form \ is: ", Cell[BoxData[ \(TraditionalForm\`x\_\(n + 1\) = g(x\_n)\)]], ", and assume that the root of ", StyleBox["f(x)", FontSlant->"Italic"], " that we are looking for is at ", StyleBox["x", FontSlant->"Italic"], " = ", StyleBox["r", FontSlant->"Italic"], " . If we rewrite the iteration form in such a way that we look at the ", StyleBox["actual", FontSlant->"Italic"], " error (by subtracting ", StyleBox["r", FontSlant->"Italic"], " from both sides), we have: ", Cell[BoxData[ \(TraditionalForm\`x\_\(n + 1\) - r = g(x\_n) - r\)]], ". But if ", StyleBox["r", FontSlant->"Italic"], " is the root of ", StyleBox["f(x)", FontSlant->"Italic"], ", then ", StyleBox["r", FontSlant->"Italic"], " must also be a fixed-point of ", StyleBox["g(x)", FontSlant->"Italic"], ", which means that ", StyleBox["g(r)", FontSlant->"Italic"], " = ", StyleBox["r", FontSlant->"Italic"], ". Let's make that substitution: ", Cell[BoxData[ \(TraditionalForm\`x\_\(n + 1\) - r = g(x\_n) - g(r)\)]], ". Hmmmm. now if we use our imaginations, we might see that the \ right-hand-side of this equation looks somewhat like a difference equation. \ Let's multiply and divide by ", Cell[BoxData[ \(TraditionalForm\`x\_n - r\)]], " : ", Cell[BoxData[ \(TraditionalForm\`x\_\(n + 1\) - r = \(\(g(x\_n) - g(r)\)\/\(x\_n - r\)\) \((x\_n - r)\)\)]], ". \nNow the quantity ", Cell[BoxData[ \(TraditionalForm\`\(g(x\_n) - g(r)\)\/\(x\_n - r\)\)]], " is the slope of the secant line between ", Cell[BoxData[ \(TraditionalForm\`x\_n\)]], " and ", StyleBox["r ;", FontSlant->"Italic"], " according to the ", StyleBox["Mean Value Theorem", FontWeight->"Bold"], ", we know that there is some point, call it ", StyleBox["c", FontSlant->"Italic"], ", between ", Cell[BoxData[ \(TraditionalForm\`x\_n\)]], " and ", StyleBox["r ", FontSlant->"Italic"], "with ", Cell[BoxData[ \(TraditionalForm\`g' \((c)\) = \(g(x\_n) - g(r)\)\/\(x\_n - r\)\)]], ". So we have: ", Cell[BoxData[ \(TraditionalForm\`x\_\(n + 1\) - r = g' \((c)\) \((x\_n - r)\)\)]], ". As we stated above, we are writing the left-hand-side as an error. \ Thus, if we let ", Cell[BoxData[ \(TraditionalForm\`e\_\(n + 1\) = x\_\(n + 1\) - r\)]], " be the error at the ", Cell[BoxData[ \(TraditionalForm\`\((n + 1)\)\^st\)]], " iteration, then we can rewrite our expression as: ", Cell[BoxData[ \(TraditionalForm\`e\_\(n + 1\) = g' \((c)\) \((e\_n)\)\)]], ". \nHmmmmm.... we think.... this looks close to the definition of ", StyleBox["linearly convergent", FontWeight->"Bold"], "... take the absolute value of both sides: ", Cell[BoxData[ \(TraditionalForm\`\(\(|\)\(e\_\(n + 1\)\)\(|\)\) = g' \((c)\) | e\_n | \)]], ". Looks even closer now, doesn't it?\nIf we let ", StyleBox["g'(c) ", FontSlant->"Italic"], "= ", StyleBox["K", FontSlant->"Italic"], ", then we have ", Cell[BoxData[ \(TraditionalForm\`\(\(|\)\(e\_\(n + 1\)\)\(|\)\) = K | e\_n | \)]], "; which is the definition of linearly convergent. So, as long as ", StyleBox["g'(c) ", FontSlant->"Italic"], "< 1 for all ", StyleBox["c", FontSlant->"Italic"], " in a small interval around the root, then the Fixed-Point algorithm will \ converge linearly." }], "Text"], Cell[TextData[{ "We can use a similar argument for False-Position and Secant Method, but \ I'm kind of tired of typing... \nWe have already seen that Bisection makes \ improvement of a factor of 2 on the ", StyleBox["bound", FontWeight->"Bold"], " of the error (i.e. the interval width) at each iteration. We can easily \ say that Bisection also converges linearly. " }], "Text"], Cell[TextData[{ "What about Newton's method?\nWe can rewrite Newton's method in an \ iterative form: ", Cell[BoxData[ \(TraditionalForm\`x\_\(n + 1\) = x\_n - \(f(x\_n)\)\/\(f' \((x\_n)\)\)\)]], ". Now, recall the form of the Fixed-Point method, and let ", Cell[BoxData[ \(TraditionalForm\`g(x\_n) = x\_n - \(f(x\_n)\)\/\(f' \((x\_n)\)\)\)]], ", so that we have: ", Cell[BoxData[ \(TraditionalForm\`x\_\(n + 1\) = g(x\_n)\)]], ". \nFollow what we have done above, and we see that as long as ", StyleBox["g'(c)", FontSlant->"Italic"], " < 1, we will converge. If we differentiate to find ", StyleBox["g'(c)", FontSlant->"Italic"], ", we have: ", Cell[BoxData[ \(TraditionalForm\`g' \((c)\) = \(\(f(c)\) f'' \((c)\)\)\/\((f' \ \((c)\))\)\^2\)]], ". So we also run into problems converging if ", StyleBox["f'(c)", FontSlant->"Italic"], " = 0 (as it does when we have multiple roots, and this is the reason \ Newton's method was slower to converge on one of the problems in the previous \ section).\nWe can continue upon this path and will see that Newton's method \ (as long as we don't have ", StyleBox["f'(x)", FontSlant->"Italic"], " = 0) converges ", StyleBox["quadratically", FontWeight->"Bold"], "." }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell["What! A Test on Thursday! ", "Section"], Cell[TextData[{ "That's right... we have a test next Thursday. We'll meet in the lab (so \ that you have all the wonderful computer tools we've worked on so far \ available).\nWhat to study? Hmmmm... Make sure that you can do things that \ we have:\n\t1. looked at in class (examples, etc)\n\t2. worked out on \ homework\n\t3. worked on in the lab\nLook over the reading assignments that \ I've had on the web - we haven't covered ", StyleBox["everything", FontWeight->"Bold"], " that is in the reading, but we've hit the main points.", "\n", StyleBox["Format:\n\t", FontWeight->"Bold"], "the test will be open book, open note, open computer and calculator, and \ open ", StyleBox["Mathematica", FontSlant->"Italic"], " notebook.\n\tI'll have you do some pretty basic type things to make sure \ we all understand the material, and then one or two harder questions that \ will push you a little. I'll put these questions at the end of the test, \ since they are a little more open-ended and might take up a lot of time. I \ put questions like these on tests to let you show how you have ", StyleBox["synthesized ", FontSlant->"Italic"], "material. No one has ever died while taking (nor shortly after having \ taken) one of my tests, so I'm reasonably sure that you'll survive ", StyleBox["just fine", FontWeight->"Bold"], ".", " \n\t", StyleBox["Bottom Line: I would look over notes and labs and try to get a \ picture of what we have done so far. That will be the best preparation for \ the exam. If you follow what we are doing and are getting something useful \ out of the labs, then you should be in pretty good shape for the exam.", FontWeight->"Bold"] }], "Text"] }, Closed]] }, FrontEndVersion->"4.1 for Microsoft Windows", ScreenRectangle->{{0, 1024}, {0, 632}}, AutoGeneratedPackage->None, WindowToolbars->{"RulerBar", "EditBar"}, CellGrouping->Manual, WindowSize->{1016, 600}, WindowMargins->{{0, Automatic}, {Automatic, 0}}, 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, 492, 26, 114, "Title"], Cell[2200, 78, 41, 0, 41, "Subtitle"], Cell[CellGroupData[{ Cell[2266, 82, 54, 3, 71, "Subsubsection"], Cell[2323, 87, 10559, 190, 2232, "Input", InitializationCell->True], Cell[12885, 279, 8058, 148, 1858, "Input", InitializationCell->True], Cell[20946, 429, 8377, 153, 1838, "Input", InitializationCell->True], Cell[29326, 584, 7615, 141, 1680, "Input", InitializationCell->True] }, Closed]], Cell[36956, 728, 498, 16, 47, "Text"], Cell[CellGroupData[{ Cell[37479, 748, 84, 1, 54, "Section"], Cell[37566, 751, 514, 9, 94, "Subsubtitle"] }, Closed]], Cell[CellGroupData[{ Cell[38117, 765, 32, 0, 34, "Section"], Cell[CellGroupData[{ Cell[38174, 769, 34, 0, 44, "Subsubsection"], Cell[38211, 771, 153, 5, 29, "Text"], Cell[38367, 778, 47, 1, 40, "Input"], Cell[38417, 781, 195, 6, 29, "Text"], Cell[38615, 789, 90, 1, 40, "Input"], Cell[38708, 792, 239, 6, 29, "Text"], Cell[38950, 800, 140, 2, 60, "Input"], Cell[39093, 804, 167, 5, 29, "Text"], Cell[39263, 811, 65, 1, 40, "Input"], Cell[39331, 814, 399, 10, 48, "Text"], Cell[39733, 826, 262, 5, 61, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[40032, 836, 31, 0, 28, "Subsubsection"], Cell[40066, 838, 150, 5, 29, "Text"], Cell[40219, 845, 44, 1, 40, "Input"], Cell[40266, 848, 192, 6, 29, "Text"], Cell[40461, 856, 78, 1, 40, "Input"], Cell[40542, 859, 418, 12, 48, "Text"], Cell[40963, 873, 78, 1, 40, "Input"], Cell[41044, 876, 164, 5, 29, "Text"], Cell[41211, 883, 62, 1, 40, "Input"], Cell[41276, 886, 399, 10, 48, "Text"], Cell[41678, 898, 200, 4, 41, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[41915, 907, 54, 0, 28, "Subsubsection"], Cell[41972, 909, 157, 5, 29, "Text"], Cell[42132, 916, 51, 1, 40, "Input"], Cell[42186, 919, 199, 6, 29, "Text"], Cell[42388, 927, 85, 1, 40, "Input"], Cell[42476, 930, 243, 6, 29, "Text"], Cell[42722, 938, 85, 1, 40, "Input"], Cell[42810, 941, 171, 5, 29, "Text"], Cell[42984, 948, 69, 1, 40, "Input"], Cell[43056, 951, 399, 10, 48, "Text"], Cell[43458, 963, 207, 4, 41, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[43702, 972, 31, 0, 28, "Subsubsection"], Cell[43736, 974, 153, 5, 29, "Text"], Cell[43892, 981, 152, 4, 23, "Commentary"], Cell[44047, 987, 47, 1, 40, "Input"], Cell[44097, 990, 190, 6, 29, "Text"], Cell[44290, 998, 71, 1, 40, "Input"], Cell[44364, 1001, 167, 5, 29, "Text"], Cell[44534, 1008, 65, 1, 40, "Input"], Cell[44602, 1011, 399, 10, 48, "Text"], Cell[45004, 1023, 186, 3, 41, "Input"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[45239, 1032, 36, 0, 34, "Section"], Cell[45278, 1034, 152, 3, 29, "Text"], Cell[CellGroupData[{ Cell[45455, 1041, 45, 0, 44, "Subsubsection"], Cell[45503, 1043, 341, 10, 48, "Text"], Cell[45847, 1055, 252, 4, 80, "Input"], Cell[46102, 1061, 49, 0, 29, "Text"], Cell[46154, 1063, 230, 5, 29, "Text"], Cell[46387, 1070, 117, 2, 60, "Input"], Cell[46507, 1074, 50, 0, 29, "Text"], Cell[46560, 1076, 62, 1, 40, "Input"], Cell[46625, 1079, 62, 1, 40, "Input"], Cell[46690, 1082, 201, 6, 23, "Commentary"], Cell[46894, 1090, 51, 1, 40, "Input"], Cell[46948, 1093, 51, 1, 40, "Input"], Cell[47002, 1096, 202, 6, 45, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[47241, 1107, 52, 0, 28, "Subsubsection"], Cell[47296, 1109, 330, 8, 48, "Text"], Cell[47629, 1119, 242, 4, 60, "Input"], Cell[47874, 1125, 415, 11, 64, "Text"], Cell[48292, 1138, 41, 0, 29, "Text"], Cell[48336, 1140, 117, 2, 60, "Input"], Cell[48456, 1144, 62, 1, 40, "Input"], Cell[48521, 1147, 217, 3, 45, "Text"], Cell[48741, 1152, 62, 1, 40, "Input"], Cell[48806, 1155, 51, 1, 40, "Input"], Cell[48860, 1158, 64, 1, 29, "Text"], Cell[48927, 1161, 302, 5, 64, "Text"], Cell[49232, 1168, 73, 0, 29, "Text"], Cell[49308, 1170, 301, 5, 60, "Input"], Cell[49612, 1177, 49, 0, 29, "Text"], Cell[49664, 1179, 177, 3, 40, "Input"], Cell[49844, 1184, 203, 3, 45, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[50084, 1192, 43, 0, 28, "Subsubsection"], Cell[50130, 1194, 206, 6, 29, "Text"], Cell[50339, 1202, 245, 4, 80, "Input"], Cell[50587, 1208, 268, 8, 29, "Text"], Cell[50858, 1218, 207, 3, 60, "Input"], Cell[51068, 1223, 248, 7, 45, "Text"], Cell[51319, 1232, 123, 2, 60, "Input"], Cell[51445, 1236, 60, 1, 40, "Input"], Cell[51508, 1239, 68, 1, 40, "Input"], Cell[51579, 1242, 233, 4, 45, "Text"], Cell[51815, 1248, 56, 1, 40, "Input"], Cell[51874, 1251, 118, 2, 45, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[52029, 1258, 46, 0, 28, "Subsubsection"], Cell[52078, 1260, 262, 7, 48, "Text"], Cell[52343, 1269, 233, 4, 60, "Input"], Cell[52579, 1275, 206, 8, 29, "Text"], Cell[52788, 1285, 263, 4, 60, "Input"], Cell[53054, 1291, 38, 0, 29, "Text"], Cell[53095, 1293, 123, 2, 60, "Input"], Cell[53221, 1297, 60, 1, 40, "Input"], Cell[53284, 1300, 165, 5, 45, "Text"], Cell[53452, 1307, 68, 1, 40, "Input"], Cell[53523, 1310, 56, 1, 40, "Input"], Cell[53582, 1313, 166, 3, 45, "Text"], Cell[53751, 1318, 417, 13, 45, "Text"], Cell[54171, 1333, 35, 1, 40, "Input"], Cell[54209, 1336, 174, 3, 45, "Text"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[54432, 1345, 40, 0, 34, "Section"], Cell[54475, 1347, 393, 13, 48, "Text"], Cell[54871, 1362, 52, 1, 40, "Input"], Cell[54926, 1365, 543, 16, 48, "Text"], Cell[55472, 1383, 168, 3, 82, "Input"], Cell[55643, 1388, 204, 6, 29, "Text"], Cell[55850, 1396, 96, 2, 29, "Text"], Cell[55949, 1400, 58, 1, 40, "Input"], Cell[56010, 1403, 124, 3, 29, "Text"], Cell[56137, 1408, 120, 2, 41, "Input"], Cell[56260, 1412, 615, 18, 48, "Text"], Cell[56878, 1432, 153, 4, 39, "Text"], Cell[57034, 1438, 171, 3, 97, "Input"], Cell[57208, 1443, 108, 3, 29, "Text"], Cell[57319, 1448, 58, 1, 40, "Input"], Cell[57380, 1451, 218, 6, 29, "Text"], Cell[57601, 1459, 683, 12, 180, "Input"], Cell[58287, 1473, 162, 4, 29, "Text"], Cell[58452, 1479, 74, 1, 43, "Input"], Cell[58529, 1482, 239, 9, 29, "Text"], Cell[58771, 1493, 112, 3, 29, "Text"], Cell[58886, 1498, 498, 13, 79, "Text"], Cell[59387, 1513, 51, 1, 40, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[59475, 1519, 52, 0, 34, "Section"], Cell[59530, 1521, 941, 21, 191, "Text"], Cell[60474, 1544, 356, 8, 48, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[60867, 1557, 41, 0, 34, "Section"], Cell[60911, 1559, 647, 21, 51, "Text"], Cell[61561, 1582, 156, 4, 29, "Text"], Cell[61720, 1588, 35, 1, 40, "Input"], Cell[61758, 1591, 189, 6, 29, "Text"], Cell[61950, 1599, 278, 9, 29, "Text"], Cell[62231, 1610, 35, 1, 40, "Input"], Cell[62269, 1613, 266, 4, 45, "Text"], Cell[62538, 1619, 53, 0, 29, "Text"], Cell[62594, 1621, 523, 10, 141, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[63154, 1636, 48, 0, 34, "Section"], Cell[63205, 1638, 1963, 51, 186, "Text"], Cell[65171, 1691, 517, 13, 102, "Input"], Cell[65691, 1706, 209, 3, 45, "Text"], Cell[65903, 1711, 921, 30, 48, "Text"], Cell[66827, 1743, 333, 10, 45, "Text"], Cell[67163, 1755, 319, 12, 29, "Text"], Cell[67485, 1769, 504, 11, 79, "Text"], Cell[67992, 1782, 53, 1, 40, "Input"], Cell[68048, 1785, 221, 4, 45, "Text"], Cell[68272, 1791, 391, 12, 48, "Text"], Cell[68666, 1805, 268, 8, 29, "Text"], Cell[68937, 1815, 193, 4, 80, "Input"], Cell[69133, 1821, 365, 11, 45, "Text"], Cell[69501, 1834, 2172, 57, 191, "Text"], Cell[71676, 1893, 343, 6, 102, "Input"], Cell[72022, 1901, 165, 3, 45, "Text"], Cell[72190, 1906, 340, 5, 64, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[72567, 1916, 43, 0, 34, "Section"], Cell[72613, 1918, 3671, 117, 275, "Text"], Cell[76287, 2037, 392, 8, 79, "Text"], Cell[76682, 2047, 1311, 35, 190, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[78030, 2087, 46, 0, 34, "Section"], Cell[78079, 2089, 1734, 35, 365, "Text"] }, Closed]] } ] *) (******************************************************************* End of Mathematica Notebook file. *******************************************************************)