(*^
::[ Information =
"This is a Mathematica Notebook file. It contains ASCII text, and can be
transferred by email, ftp, or other text-file transfer utility. It should
be read or edited using a copy of Mathematica or MathReader. If you
received this as email, use your mail application or copy/paste to save
everything from the line containing (*^ down to the line containing ^*)
into a plain text file. On some systems you may have to give the file a
name ending with ".ma" to allow Mathematica to recognize it as a Notebook.
The line below identifies what version of Mathematica created this file,
but it can be opened using any other version as well.";
FrontEndVersion = "Macintosh Mathematica Notebook Front End Version 2.2";
MacintoshStandardFontEncoding;
fontset = title, inactive, noPageBreakBelow, nohscroll, preserveAspect,
groupLikeTitle, center, M7, bold, e8, 24, "Times";
fontset = subtitle, inactive, noPageBreakBelow, nohscroll, preserveAspect,
groupLikeTitle, center, M7, bold, e6, 18, "Times";
fontset = subsubtitle, inactive, noPageBreakBelow, nohscroll,
preserveAspect, groupLikeTitle, center, M7, italic, e6, 14, "Times";
fontset = section, inactive, noPageBreakBelow, nohscroll, preserveAspect,
groupLikeSection, grayBox, M22, bold, a20, 18, "Times";
fontset = subsection, inactive, noPageBreakBelow, nohscroll,
preserveAspect, groupLikeSection, blackBox, M19, bold, a15, 14, "Times";
fontset = subsubsection, inactive, noPageBreakBelow, nohscroll,
preserveAspect, groupLikeSection, whiteBox, M18, bold, a12, 12, "Times";
fontset = text, inactive, nohscroll, noKeepOnOnePage, preserveAspect, M7,
12, "Times";
fontset = smalltext, inactive, nohscroll, noKeepOnOnePage, preserveAspect,
M7, 10, "Times";
fontset = input, noPageBreakInGroup, preserveAspect, groupLikeInput, M42,
N23, bold, B65535, L-5, 12, "Courier";
fontset = output, output, inactive, noPageBreakInGroup, preserveAspect,
groupLikeOutput, M42, N23, L-5, 12, "Courier";
fontset = message, inactive, noPageBreakInGroup, preserveAspect,
groupLikeOutput, M42, N23, R65535, L-5, 12, "Courier";
fontset = print, inactive, noPageBreakInGroup, preserveAspect,
groupLikeOutput, M42, N23, L-5, 12, "Courier";
fontset = info, inactive, noPageBreakInGroup, preserveAspect,
groupLikeOutput, M42, N23, B65535, L-5, 12, "Courier";
fontset = postscript, PostScript, formatAsPostScript, output, inactive,
noPageBreakInGroup, preserveAspect, groupLikeGraphics, M7, l34, w282, h287,
12, "Courier";
fontset = name, inactive, nohscroll, noKeepOnOnePage, preserveAspect, M7,
italic, 10, "Geneva";
fontset = header, inactive, noKeepOnOnePage, preserveAspect, M7, 12, "Times";
fontset = leftheader, inactive, L2, 12, "Times";
fontset = footer, inactive, noKeepOnOnePage, preserveAspect, center, M7,
12, "Times";
fontset = leftfooter, inactive, L2, 12, "Times";
fontset = help, inactive, nohscroll, noKeepOnOnePage, preserveAspect, M7,
10, "Times";
fontset = clipboard, inactive, nohscroll, noKeepOnOnePage, preserveAspect,
M7, 12, "Times";
fontset = completions, inactive, nohscroll, noKeepOnOnePage,
preserveAspect, M7, 12, "Times";
fontset = special1, inactive, nohscroll, noKeepOnOnePage, preserveAspect,
M7, 12, "Times";
fontset = special2, inactive, nohscroll, noKeepOnOnePage, preserveAspect,
M7, 12, "Times";
fontset = special3, inactive, nohscroll, noKeepOnOnePage, preserveAspect,
M7, 12, "Times";
fontset = special4, inactive, nohscroll, noKeepOnOnePage, preserveAspect,
M7, 12, "Times";
fontset = special5, inactive, nohscroll, noKeepOnOnePage, preserveAspect,
M7, 12, "Times";
currentKernel;
]
:[font = smalltext; inactive; preserveAspect]
Copyright (C) 1997 Rich Neidinger, John Swallow, and Todd Will. Free for
distribution to college and university instructors for personal,
non-commercial use. If these notebooks are used in a course, the authors
request $20 per student.
:[font = title; inactive; preserveAspect]
2. Course Goals and Themes
:[font = smalltext; inactive; preserveAspect]
Last revision: August 27 1996
:[font = text; inactive; preserveAspect]
In this section we introduce the primary goals and themes of the course and
explore some of them in the context of solving equations numerically.
:[font = section; inactive; Cclosed; preserveAspect; startGroup]
Mathematica, a Programming Language
:[font = text; inactive; preserveAspect]
By now you are becoming familiar with the Mathematica environment and the
evaluation of one-line expressions in input cells. Mathematica may seem at
this point irrelevant to programming, seemingly a simple---albeit
powerful---calculator. Do not despair! At this early stage we will
continue to examine some basic programming terms while applying them to
some easily posed mathematical problems. In the next section we will begin
defining functions, and soon after that we will learn how to construct
modules, or procedures, with which we can instruct Mathematica to perform a
series of steps, test conditions, and so on. At that stage, we will be
learning how to program.
:[font = subsection; inactive; Cclosed; preserveAspect; startGroup]
Course Goals
:[font = text; inactive; preserveAspect; endGroup]
The organizing principle of this course is that the best introduction to
programming is an introduction in the broadest sense, covering different
programming principles, which apply to most computer languages, as well as
different programming paradigms, each of which might apply to certain
languages but not others. (A paradigm, for the purposes of this course,
will be any method of organizing computer instructions which privileges
certain types of action or certain types of data representation over
others. We will first take up paradigms explicitly in section 5.) We have
chosen Mathematica for the language of the course because within
Mathematica---and comparatively few other languages---we can program using
many different principles and many different paradigms. We believe that
when students satisfactorily complete this course, they will not only have
come to terms with programming as a broad discipline but will also able to
pick up the particulars of another language (C or Pascal being conscious
instances) quickly and productively. Thus, moving from this course to a
"second-semester" programming course focussing on C or Pascal (or on their
object-oriented cousins, C++ and Delphi) should be relatively smooth, and
you will take from this course many ideas and perspectives you would not
have gained had you studied only C or Pascal from the beginning.
;[s]
7:0,0;158,1;168,0;243,1;252,0;321,1;329,0;1375,-1;
2:4,13,9,Times,0,12,0,0,0;3,13,9,Times,2,12,0,0,0;
:[font = subsection; inactive; Cclosed; preserveAspect; startGroup]
Course Themes
:[font = text; inactive; preserveAspect]
We also, however, believe that an introductory programming course should
seek to introduce students to some fundamental programming issues in which
the programmer must balance sometimes competing goals. These issues we
call themes of our course, and we attempt to consider each of these themes
at several points in the course. One theme is the tradeoff between using
an interpreted language, such as Mathematica is in its basic form, and a
compiled language, such as most implementations of C and Pascal. Another
is the tradeoff between data security within a program and speed of
execution; this issue is raised in choosing between call-by-value functions
and call-by-reference functions, as well as in whether or not to use an
object-oriented programming paradigm. Still another is the tradeoff
between having a program save results it has already computed, in case it
may need them later, and having a program maintain as small a demand on
computer resources as possible, as for instance when one considers whether
to use dynamic programming. One final issue is the balance between the
simplest solution to a problem from the programmer's perspective and the
fastest solution to a problem from a user's perspective, leading students
to consider a course in data structures and algorithms.
:[font = text; inactive; preserveAspect; endGroup; endGroup]
In this section we will consider some themes briefly, while introducing a
few built-in, numerical functions of Mathematica.
:[font = section; inactive; Cclosed; preserveAspect; startGroup]
Exploring Tradeoffs
:[font = subsection; inactive; Cclosed; preserveAspect; startGroup]
Source Code, Interpreted vs. Compiled Languages
:[font = text; inactive; preserveAspect]
Let's begin by introducing some terms. We already introduced some terms in
section 1; you should know what data types are (and some examples of them
in Mathematica), why operator precedence matters in the evaluation of
expressions, and what a boolean value is.
;[s]
7:0,0;107,1;118,0;170,1;190,0;243,1;251,0;262,-1;
2:4,13,9,Times,0,12,0,0,0;3,13,9,Times,2,12,0,0,0;
:[font = text; inactive; preserveAspect]
The instructions we write to computers, in some computer language, are
generically called source code. All of the Mathematica instructions, or
commands, or expressions, which we evaluated in input cells in the section
before were examples of source code. A microprocessor, such as the one
inside the computer your are working on, however, does not understand these
statements of source code; it understands only machine code. Hence
computer programmers face a conversion problem, that of taking the source
code they have written and converting it to instructions the microprocessor
can understand. Depending on the particular language and its
implementation, this conversion happens typically in one of two possible
ways. Either a program converts the source code to machine code when we
ask the computer to execute our source code or beforehand. In the first
case, we say that the source code is interpreted; in the second we say that
the source code is compiled.
;[s]
13:0,0;90,1;104,0;414,1;426,0;785,1;836,0;839,1;850,0;903,1;914,0;961,1;969,
0;973,-1;
2:7,13,9,Times,0,12,0,0,0;6,13,9,Times,2,12,0,0,0;
:[font = text; inactive; preserveAspect]
Deciding which system of conversion is better depends, to a large extent,
on how a programmer balances ease of programming with fast execution.
Because the conversion process happens every time the source code is
executed, and because the conversion process takes a fair amount of time,
interpreted languages tend to be much slower then compiled languages.
Practically all of the programs you find on your computer were written in a
computer language and then compiled, because the expectation is that you
will run these programs hundreds, if not millions, of times and would like
to see them execute as fast as possible. However, suppose that we do not
intend to run our programs hundreds of times, but wish instead to be spared
the tiresome process of writing code, compiling it, running it, realizing
that there is an error, rewriting the code, recompiling, and so on.
Suppose instead that we wish to be able to correct the code immediately and
then execute the program again. In this case we would opt for an
interpreted language, such as Mathematica. Notice that you may execute any
cell of code at any time; it is only then that Mathematica converts the
code to machine code and executes it.
:[font = text; inactive; preserveAspect; endGroup]
The decision, even before any code is written, of whether or not to use a
language which encourages or demands compilation versus one which
encourages or demands interpretation is essentially the first of many ways
in which a programmer comes up against one of the many tradeoffs in
computer programming, balancing one goal against another.
:[font = subsection; inactive; Cclosed; preserveAspect; startGroup]
Dynamic Programming (NSolve)
:[font = text; inactive; preserveAspect]
Mathematica has a built-in command, "NSolve[ ]", which takes an equation
involving a variable and attempts to find numeric approximations to the
values of the variable for which the equation holds true. For example:
:[font = input; preserveAspect]
NSolve[x^2==4,x]
:[font = text; inactive; preserveAspect]
The first argument to the function "NSolve[ ]" is the equation involving
the variable, where double equals signs("==") are substituted where a
standard equals sign would reside. The second argument is the name of the
variable. We notice that the values Mathematica has found, which do in
fact make the equation true, are each placed inside a list, and each of
these lists is placed into one large list. The values themselves are
expressed in what Mathematica calls rules, where the variable appears on
the left-hand side of an arrow ("->"), and the value appears on the right.
We can use "NSolve[ ]" to find solutions to many, many equations, though
sometimes Mathematica fails, as in the following equation.
;[s]
3:0,0;469,1;474,0;714,-1;
2:2,13,9,Times,0,12,0,0,0;1,13,9,Times,2,12,0,0,0;
:[font = input; preserveAspect]
NSolve[Exp[x]==x+2, x]
:[font = text; inactive; preserveAspect; endGroup]
Let us pause to consider the best way Mathematica might implement a
function such as "NSolve[ ]". One method Mathematica might consider is
that of dynamic programming, which means the process of retaining the
solutions it has found every time it performs an "NSolve[ ]" command. If
it were to do so, then it could check the next time when asked it to
execute an "NSolve[ ]" command, and, if we had already executed the same
one before, it could simply look up the old answer, a process which would
take much less time than actually trying to solve the equation. At what
cost, though? Here we have a tradeoff between storage space (memory or
hard disk) and speed: if we are willing to give up space, we can have many
answers to questions at our fingertips, while if we are not, we force
Mathematica to derive answers to equations over and over again. In this
case, as you might probably imagine, dynamic programming is a poor choice
for a programming method, since the number of possible equations is so
enormous that no computer would have space enough to hold all possible
solutions. For another problem, however, dynamic programming might be a
great choice. This example illustrates another tradeoff common in computer
programming, that of space versus time.
;[s]
3:0,0;148,1;167,0;1269,-1;
2:2,13,9,Times,0,12,0,0,0;1,13,9,Times,2,12,0,0,0;
:[font = subsection; inactive; Cclosed; preserveAspect; startGroup]
Simple vs. Complex Algorithms (FindRoot)
:[font = text; inactive; preserveAspect]
If "NSolve[ ]" does not work, another Mathematica function which is
appropriate is "FindRoot[ ]". "FindRoot[ ]" uses a mathematical process
called Newton's method, which begins with an estimate for a root of the
equation---a value of the variable for which the equation is true---and
attempts gradually to refine this estimate into a very good approximation.
For example:
:[font = input; preserveAspect]
FindRoot[x^2==4,{x,1}]
:[font = text; inactive; preserveAspect]
To be sure, another root exists (namely x=-2), but the 1 was refined into
the 2 which is, correctly, a root of the equation. Let us try "FindRoot[
]" on the equation which "NSolve[ ]" could not crack.
:[font = input; preserveAspect]
FindRoot[Exp[x]==x+2,{x,2}]
:[font = text; inactive; preserveAspect]
How did we know to guess "2"? One way is to plot the two functions
"Exp[x]" and "x+2" and see if we can determine where they might cross.
:[font = input; preserveAspect]
Plot[{Exp[x],x+2},{x,-5,5}]
:[font = text; inactive; preserveAspect]
Now Newton's method was developed hundreds of years ago and represents a
good, if not foolproof, way to approximate the solution of an equation.
The method is as follows:
:[font = text; inactive; preserveAspect]
Let the initial guess be "x", and let the value of the function at this
guess be denoted "f(x)". Find the derivative "d(x)" of the function at the
initial guess using some calculus, either approximately or exactly,
depending on the method chosen. Evaluate "x-f(x)/d(x)", and use this value
as the new guess. Continue until the guesses seem to approach one
particular number.
:[font = text; inactive; preserveAspect]
To an untrained observer, however, Newton's method may seem needlessly
complicated, using the theory of calculus. One might imagine someone
making the claim that a simpler algorithm, or method, might be used to find
a point where two functions intersect, using the following argument:
manipulate the equation so that the right-hand side is a zero. Now proceed
through the integers, one at a time, beginning with 1, substituting them
inside the left-hand side of the equation. When we reach two consecutive
integers for which the signs of the numbers we find on the left-hand sides
are opposite, we surmise that a root occurs between the two integers and
then check numbers equally spaced between the two integers, say at
intervals of one-tenth. Let's do this for the functions above. We'll
define a function "f[ ]" which gives us the value of the left-hand side of
the equation "Exp[x]-(x+2)==0".
:[font = input; preserveAspect]
Clear[f]
f[x_] := Exp[x]-(x+2)
:[font = input; preserveAspect]
f[1]
:[font = input; preserveAspect]
f[2]
:[font = text; inactive; preserveAspect]
In this case, we already guess that a root lies between 1 and 2, and we
explore further by examining "f[1.0]", "f[1.1]", and so on.
:[font = text; inactive; preserveAspect]
Is the method simpler? Perhaps, but it is not as good a method as Newton's
method, as the following example suggests.
:[font = input; preserveAspect]
FindRoot[(x-.5)^2==.15,{x,0}]
:[font = input; preserveAspect]
Clear[f]
f[x_] := (x-.5)^2 - .15;
:[font = input; preserveAspect]
f[0]
:[font = input; preserveAspect]
f[1]
:[font = text; inactive; preserveAspect; endGroup; endGroup]
Notice that although a root exists between x=0 and x=1, the "simpler"
method fails to find it. This illustrates a third tradeoff in computer
programming. Sometimes the more intuitive method fails, sometimes because
it never works, and sometimes because it only works some of the time.
While all programmers would like simple methods to work, they must balance
this desire against the other concerns of correctness, execution time,
memory or hard drive space, and so on. In this course you will be
presented at times with problems which require somewhat complicated
solutions, and you must strive to understand why your solution should work
in every possible case. It also helps, of course, to try your solution out
on lots of examples.
^*)