Introduction, Basics, Matlab

1.A Numerical Scheme

Consider the following example.

Example 1.1. Solve the quadratic equation

We can find the solution by performing some simple algebraic manipulations leading to the
familiar quadratic formula:

Does this formula bring us any closer to finding the numerical solutions of this problem? If we are
lucky, and b2−4c happens to be the square of some easily identifiable number, we can compute the
solutions using a couple of additions and divisions . Likewise, almost any calculator nowadays has a
built-in square root operation , and we can use it to find a numerical solution even for general b and
c. Suppose however that we are able only to perform the four fundamental arithmetic operations
of addition, subtraction, multiplication, and division. In this case, the formula (2) is not much use,
unless we can somehow come up with a good numerical approximation to the square root , obtained
using only +, −, ×, and /. Fortunately such schemes exist, as we discuss next.

1.1 Approximating the Square Root

So how do we calculate an approximate square root? Before we can answer, we must consider two
of the fundamental limitations of numerical computation:

• Limited precision. Since there is only a limited amount of space to store any number in
a computer
, we cannot always store it exactly. Rather, we can only get a solution that is
accurate up to the limit of our machine precision (for example, 16 digits of accuracy ).

• Limited time. Each arithmetic operation (e.g. addition, multiplication) takes time to perform.
Often we face a resource budget; the approximate solution must be available within a limited
time.

Just to evaluate the quadratic function f(x) = ax2 + bx + c at a point x takes time. Doing
it in the obvious way takes three multiplications (x * x, a * x2, b * x) and two additions. (Q:
Can you see a faster way?)

We now present a method for funding the square root of a given ( positive ) number c by generating
a sequence of guesses , each of which is usually more accurate than its predecessor.
is the initial guess, which we supply; is the next guess obtained form our method; is the
one after that, and so on.

Our procedure uses the following simple formula to obtain each new guess from the previous
guess :

If we start with an initial value = 2.2 and carry out this computation for three steps , we
obtain the following values of , and . (We also tabulate the squares of these values, for
interest.)

Using this procedure, only 3 × 4 = 12 simple arithmetic operations are required to arrive at a
numerical solution that is accurate to the limit of Matlab’s precision. Taking to be essentially
exact, and comparing it with the earlier values , and , we see that has 2 correct digits
has 4 correct digits, and has 8 correct digits. The number of correct digits doubles with each
guess - a rapid rate of convergence.

Soon we will study the basis for the excellent performance of this scheme, which is a particular
case of Newton’s method, and apply it to more complicated problems. In fact, before going further,
we derive a generalization of this scheme for finding the roots of the quadratic (1) directly, rather
than computing the square root approximation and plugging it into the formula (2). Given one
approximation to a root of (1), we obtain the next guess by applying the following formula:

which, by simple elimination , is equivalent to the following:

2 Loss of Significance

Another issue in numerical computation is loss of significance. Consider two real numbers stored
with 10 digits of precision beyond the decimal point :

If we subtract a from b , we will get the answer 0.0000000036. This result has only two significant
digits; it may differ from the underlying true value of this difference by more than 1%. We have
lost most of the precision of the two original numbers.

One might try to solve this problem by increasing the precision of the original numbers, but
this only improves the situation up to a point. Regardless of how high the precision is, if it remains
finite, numbers that are close enough together will be indistinguishable. An example of the effect
of loss of significance occurs in calculating derivatives.

Example 2.1 (Calculating Derivatives). Given the function f(t) = sint, what is f '(2)?

We all know from calculus that the derivative of sin t is cos t, so one could calculate cos(2) in
this case. However, just as with calculating definite integrals, it is not always possible, or efficient
to evaluate the derivative of a function by hand.

Tangent line to sin(2) Secant line through sin(2), sin(2+h)

Figure 1: Tangent and Secant Lines on f(t) = sint

Instead, recall that the value of the derivative of a function f at a point is the slope of the
line
tangent to f at . Recall, also, that we can approximate this slope by calculating the slope of
a secant line that intersects f at and at a point very close to , say +h, as shown in Figure 2.
We learned in calculus, that as h → 0, the slope of the secant line approaches the slope of the
tangent line, that is,

Just as with the definite integral, we could approximate the derivative at by performing this
calculation for a small (but nonzero) value of h, and setting our approximate derivative to be

This procedure is known as finite differencing. However, notice that if h is very small, f(+h) and
f() are the same in finite precision. That is, the numerator of (6) will be zero in finite precision,
and this calculation will erroneously report that all derivatives are zero.

Preventing loss of significance in our calculations will be an important part of this course.

 

Prev Next