2. Course Goals and Themes

Last revision: January 13 1998

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.

Mathematica, a Programming Language

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.

Course Goals

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++, Java, 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.

Course Themes

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.

In this section we will consider some themes briefly, while introducing a few built-in, numerical functions of Mathematica.

Exploring Tradeoffs

Source Code, Interpreted vs. Compiled Languages

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.

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.

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.

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.

Dynamic Programming (NSolve)

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:

NSolve[x^2==4,x]

NSolve[x^2==-4,x]

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.  Compare the results of evaluating the following expressions.

NSolve[Exp[x] == x+2, x]

NSolve[Exp[x] == Abs[x+2], x]

NSolve[Exp[x] == x + 2 Cos[x], x]

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.

Simple vs. Complex Algorithms (FindRoot)

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:

FindRoot[x^2==4,{x,1}]

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 one of the equations which "NSolve[]" could not crack.

FindRoot[Exp[x]==x+2Cos[x],{x,1}]

FindRoot[Exp[x]==x+2Cos[x],{x,-1}]

How did we know to guess 1 and -1?  One way is to plot the two functions "Exp[x]" and "x+2Cos[x]" and see if we can determine where they might cross.

Plot[{Exp[x], x + 2 Cos[x]}, {x,-5,5}];

Sometimes Mathematica warns you it might be missing a solution, and sometimes it doesn't.  Recall our earlier attempt at solving
	 Exp[x] == x+2 
and at solving
	 Exp[x] == Abs[x+2].

NSolve[Exp[x] == x+2, x]

NSolve[Exp[x] == Abs[x+2], x]

Check out the graphs...

Plot[{Exp[x],x+2},{x,-5,5}];

Plot[{Exp[x], Abs[x+2]}, {x,-4,2}, 
	PlotRange->{0,4}
];

Mathematica warned us it might miss solutions to Exp[x] == x+2, but actually found all of them.  It didn't warn us concerning Exp[x] == Abs[x+2], but missed all three solutions.  Darn!

Some calculus courses teach a process of approximating a root to a function (a solution to f(x) = 0) called Newton's method.  Newton's method was developed hundreds of years ago and represents a good, if not foolproof, way to approach this problem.  It is an iterative method of successively improving estimates.  The idea is to start with an initial estimate for your answer and to replace your estimate with a "better" estimate.  Then replace the better estimate with an even better estimate.  Continue until you are satisfied with the accuracy of the latest estimate (perhaps because it doesn't differ by much from the previous estimate) .  The step which improves an estimated root to a "better" estimate is as follows:

Let the estimate be "x", and denote the value of the function at this estimate by "f(x)".  Find the derivative "d(x)" of the function at the estimate "x" 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 "better" estimate.

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+2Cos[x])==0".

Clear[f];
f[x_] := Exp[x]-(x + 2 Cos[x])

f[0.]

f[1.]

In this case, we already guess that a root lies between 0 and 1, and we explore further by examining "f[1.0]", "f[1.1]", "f[1.2]", "f[1.3]", and so on.

Is the method simpler?  Perhaps, but it is not as good as Newton's method.  Consider the problem of approximating solutions to (x–.5)^2=.15.  Let's try Newton's method, as implemented by Mathematica's FindRoot command, using an initial estimate of 0.

FindRoot[(x-.5)^2==.15,{x,0}]

There are actually two solutions between 0 and 1, as shown by the following graph.

Plot[{(x-.5)^2, .15}, {x,0,1}];

Now try the "simpler" method.

Clear[f]
f[x_] := (x-.5)^2 - .15;

f[0]

f[1]

Notice that, although two solutions to (x-.5)^2 = .15 occur between x=0 and x=1, the "simpler" method fails to recognize that there is any solution in this interval.  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.