Learning To Learn Math Successive Approximation

Learning to Learn ---Math--Successive Approximation Srinivasan Nenmeli-K

Introduction You might have read my previous document--Learning to learn---a document addressed to math teachers.Here is another article mainly to instruct

you one of the common approaches in math---Successive

Approximation. Many techniques and methods in math---including advanced numerical techniques ---are only modifications of this simple,widely used technique.

Step 1: We use in Successive Approximation [short form or abbreviation in this article ---SA method]a rough,approximate first solution... Step2: Then we apply this in the given problem and find the deviation due to approximate answer....If the deviation is small,take the solution as such.. Step3:If not, if the deviation is large, move closer to the real solution by increasing or decreasing the value used in the first solution... Step4: Repeat this process--approach the solution in a few iterative steps.!

Example 1 You will learn this method by the simple example of finding the square root of a number. May be, you know this method already..[in middle school you might have learnt!].but let us review this and get the method straight!;

Finding the square root: Let us find the square root of 38. Since we know 5 x 5= 25 and 10 x 10 = 100, the square root of 36 must lie between 5 and 10. Step 1: Try sqrt(38)= 7 then 7 x7 = 49 Step 2 : deviations from the solution:

49 is greater

than 36 So the square root should be < 7. Can it be 6? :

6x6 = 36

36 is less than 38: 36 < 38

So the square root of 38 must lie between 6 and 7. Deviation:

6 x 6 = 36

Deviation = 38 - 36= 2

7 x7 = 49

Deviation = 49 - 28 = 11

So the deviation is less for sqrt(38) = 6..... Therefore let us increase 6 by a little--say 6.2 Step3: take sqrt(38) = 6.2 Now: 6.2 x 6.2= 38.44 Deviation D = 38.44 - 38=0.44 Step4 The sqrt(38) should be slightly less than 6.2 Okay! Reduce from 6.2 to 6.1 Step5 : 6.1 x 6.1 = 37.21 deviation D = 38-37.1= 0.9 You can see that the deviation was less with 6.2....So the solution must be closer to 6.2 and not close to 6.1 Step 5 Take the solution as : 6.175 6.175 x 6.175 = 38.13 Deviation:

38.13- 38 = 0.13

We can stop with this ; Sqrt(38) = 6.175 The exact root your calculator gives is 6.164 The error in our approach is :

6.175 - 6.164 = 0.011

%error = [0.011/6.164] x 100 = 0.178 = 0.18%

Remarkable result indeed. Therefore sqrt(38)= 6.175 Practice Problem: Find the square root of 23 using this method. -------------------------------------------------------------------------

Example 2 Any non-linear algebraic equation can be solved by successive approximation in different ways: Here is a simple method called

method,widely

Bisection

used in computer programs because this

method always works.. [This method may be slow one---that does not matter because computers can do the calculations or number crunching very fast.] This method is similar to what we did for finding the square root in the previous example. Problem:

To solve

f(x) =

Let us write

Now let us find two values of x ,say x1 and x2 ,such that f(x1) is greater than zero and f(x2)is less than zero; f(x1)>0

and f(x2) <0

Since we assume that the function is continuous,this means that the root must lie between x1 and x2.Take the solution as x' = [x1+x2]/2

Step 1..Let

f(x') = f[(x1+x2)/2]

x1=0 f(x1) = 3

x2= 1 for this example: f(x2) = 1-5+3 = -1

Note that f(x1) and f(x2) are of opposite sign.Therefore

the root x' must lie within the interval (0,1); Take x'= 0.5

Step 2:

What is f(x')?

Note that f(1)= -1 and f(.5) = 0.625

These two are of opposite signs.So the root must lie between x1=1 and x2=0.5 Take x'= 1.5/2= 0.75 What is f(x') = f(.75)?

Step 3: Note that f(0.75)<0 and f(0.5)>0

The root must lie

between 0.75 and 0.5. Take the root x'= (.75+0.5)/2 = 0.625 What is f(x')= f(.625)?

We can take the root as 0.625. Step 4 f(.625)>0

f(.75)<0

So, the root must lie between 0.625 and 0.75 Take the root as: x'=(.625+0.75)/2 = 0.687 We see that in each step we are dividing the interval of roots by half..hence the name 'bisection'... With each step or iteration, we are getting closer to the root.! To check f(.687) = Note that we are indeed close to the root since f(x) is only -0.11, almost close to zero. Take the root as x= 0.687 This method is one of the most widely used numerical methods or "algorithm" used by computer scientists for solving non-linear algebraic equations.. The steps appear tedious with hand calculations as we did

now.!---but computers can do such things fast and give you the result in a fraction of a second.

Practice problem: Solve x^3 - 2x- 5= 0 The root is close to 2 ; Take the initial roots as x1= 2 and x2= 2.5 The root is 2.09455 { Isaac Newton solve this equation

by his method using

Calculus sometime in 1669!] --------------------------------------------------------------------------------

Example 3 Heron's method to find the square root: Heron of Alexandria in Greece, found a simple method using successive approximation: To find the square root of a number N,start with approximate one ,say x1. The next better value is simply: x2= 1/2(x1+ N/x1) Now you plow back or iterate ,using x2 on the right side: x3= 1/2(x2 + N/x2) Repeat this:

x4= 1/2( x3 + N/x3)

{ The word 'iterare' means in latin 'to plow back"]

Let us try this for sqrt(2):

N =2

Start with x1= 1 x2= 1/2( 1 + 2/1) = 1.5 x3= 1/2(1.5 + 2/1.5)= 1.416 x4 = 1/2 (1.416 + 2/1.416)= 1.4143 x5=

1/2( 1.4143 + 2/1.4143) = 1.414213565

Your calculator would give: Are you surprised at the remarkable closeness of our value in five iterations with that of the calculator?

Well---the calculator mostly uses the same algorithm or method as this

method!

Practice problem

Find the square root of 38 using the Heron's

method. --------------------------------------------------------------------------------------------------

Iterative Formula Look at the example of Heron's formula for finding the square root: We start with an approximate value of the root ,say x1. Then use the formula:

x2= 1/2(x1 + N/x1)

Note that this is an iterative formula;we plug in x1 in the expression or function in the right side;we get a better value for the root ,called x2. Again you plug in x2 in the right side ane get x3,a still better value and so on.. The iterative fromula can be written in a general form: xi+1 = f(xi) = 1/2 (xi + N/ Xi)

How to develop an iterative formula to solve an equation? For many

problems, it is very easy to develop an iterative

formula. Take the example of Bisection method given ealier: Solve: We can develop an interative formula as follows: Rewrite the equation:

Now we have an iterative formula of the form: x = g(x)

Let us start with x1= 0.5 and find successive approx values for the root x: x2= (1/5) (0.125 + 3) = 0.625 Let us repeat again:

x3= (1/5)(0.244414+3)=0.6488

Once more iterate:

x4= 0.654629

We are getting close to the root. This method is also called Picard's iteration.

Practice Problem: Develop an iterative formula and solve the equation:

[The root is: 2.09455] Note: For deeper understanding ,learn about "fixed points' of such solution. --------------------------------------------------------------------------------------Example 4 Leonardo of Pisa or Fibonacci solved this cubical equation:

Let us solve this by an effective method: The root is more than 1...so we can find an approximate solution by developing an iterative formula:

Start with x= 1.5

x = -(1/10)(

With x= 1.2125, we get:

)=1.2125

x=1.5277 x= 1.339255

After a few more iterations, we get: 1.368 808 ------------------------------------------------------------------------------------------------------

Graphical Approach-- Cobweb Model There is another approach for successive approximation---a graphical method. Let us start with the iterative formula: To solve Rewrite:

f(x) = 0, x = g(x)

Let us draw two graphs on the same sheet: y = x [this is a straightline passing thru the origin] y = g(x)

The solution is the point of intersection of the two graph.This point is called the "fixed point", x*. Now you do not know the fixed point ....then start with x = x1, find g(x1) on the graph of y = g(x). For the same y,find x, the new x ,say x2. for x2 ,find g(x2) and so on...you will converge at the fixed point x*.... Example 5 let us take the same example of finding the square root of 2, using a graphical method.

Let us rewrite this in the following way:

x = 2/x

y = x and

y = 2/x

If you plot the two curves, you will find the point of intersection at x = 1.414 To enable you to draw the curves, I give this short table: y1= x ; y2= 2/x

x

y1

y2

0.2

0.2

10

0.5

0.5

4

1

1

2

1.5

1.5

1.333

2

2

2.5

2.5

0.8

3

3

0.666

4

4

0.5

1

-----------------------------------------------------------------------------------------------------------------------------------------------

Secant method--another successive approximation

To solve the equation f(x)=0, we find two approximate solutions x1 and x2 such that f(x1) <0 and f(x2)>0 ---Let us call f(x1) = y1 and f(x2) = y2. y1 is negative and y2 is postive. The root x* lies in between x1 and x2 and f(x*) = 0

In the Secant method, we draw a straight line joining

y1 and y2.

This line will cut the x axis at some point x' very close to the root x*;we take x' as the next approximate root. To find x', let us write the equation of this straight line: y = mx + c m= the slope = (y2-y1)/(x2-x1) Taking y= y1 at x= x1, we get

y1= (y2-y1)/(x2-x1) (x1) +

C c= y1 - [(y2-y1)/(x2 - x1)]x1 To find the next root x', we find the x intercept when y=0 Then

y=mx' + c =0 x' = -c/m x' = -[y1 - mx1]/m = (mx1 -y1)/m x' = x1 -y1/m x' = x1 - f(x1).[(x2-x1)/(f(x2)-f(x1)]

Let us use this method for the same problem given earlier:

To Solve: Let us take x1=0 x2=1

f(x1)= y1 = 3 f(x2) = y2 = 1-5+3= -1

Note that y1 and y2 are of opposite signs;so the root lies between 0 and 1. let us form the straight line between x1=0 and x2= 1 y= mx+c Slope = m = (y2-y1)/(x2-x1) = (-1-3)/(1)= -4 y1=3 = c

c=3 y= -4x + 3 Now the x intercept : y=0

x=3/4= 0.75

The next root is 0.75 We are getting close to the root. Next iteration f(0.75) = Let us take x1=0

f(x1)=y1=3

x2 =0.75

f(x2)= y2= -0.3281

Let us take the straight line joining y1 and y2. Using the formula we got earlier: x'= x1 - y1/m m= (-0.3281-3)/(0.75-0)= -3.3281/0.75= -4.43 x'= 0 - 3/-4.43=0.6772 We can take x' = 0.6772 as the next approximate root. We stop here,but as an exercise you can do one more interation by this method. You will find that the secant method is quite 'efficient' in that in just two iteration , we have the root x'= 0.6772 while the exact root x*= 0.687 The error = 0.687-0.6772/0.687 = 0.015/0.687 = 0.021 Error is 2.1% only. Note: The secant method is also attributed to Isaac Newton. --------------------------------------------------------------------------------------------

Finding the value of Integrals--Numerical Integration

Suppose you want to find the value of a definite integral, bewteen the limits x=a and x= b;

Oftentimes, it is not possible to find an expression F(x) the integral value and then plug in the limits: (b).We then use

I = F(a) - F

"numerical integration" methods.

I introduce here a few simple ways --actually three methods--of doing this. 1. Rectangular method Here, we want to find the area under the curve y = f(x) Replace f(x) by a straight line of value f(x) at x=a or simply f(a). Then construct the rectangle with width = (b-a) and height =f(a) We approximate the value of the integral to the area of this rectangle: I = width x height = (b-a) f(a) This value will be very poor approximation if the function is curved. OKay, I can approach the curve closer by taking smaller and smaller rectangles. {note: I could have used for the area: I = width x height= (b-a) f(b) This is called right-end method...both are equally good.]

Example 1:

Find

This integral is just ln2 because: I =ln2 -ln1=ln2= 0.69314... Let us use our method and get some value close to this. First approximation: Second approximation:

I = (2-1).(1/x) at x =1

I = 1*1=2

We split the integral into two integrals

and then use the rectangular method:

I = (1.5-1)(1/1) + (2-1.5)(1/1.5)= 0.5 ( 1 + 0.666)= 1.666/2= 0.833 We are getting closer to to 0.69 ,but still the value is a very poor approximation. Third approximation:

Let us split the integral into 4 each with

a width of 0.25.

Using the rectangular method, width = 0.25 for each integral: I = 0.25 [1/1 + 1/1.25 + 1/1.5 +1/1.75]= 0.25 (1 + 0.8 + 0.666 +

0.57] = 0.25 ( 2.466+0.57) =

3.036/4=0.76

We are getting close to the value I = 0.69 We can go further with 8 strips or imntegrals with width 0.125.....Try this for yourself!

2. Trapezoidal rule Instead of approximating the area to a

rectangle, let us use a

trapezoid with f(a) and f(b) as two sides. The area of this trapezoid is then taken: I = width (f(a)+f(b))/2 Let us try the same problem with this method:

First approximation:

This is a good result.Let us split the integral into two and then apply trapezoidal rule: Second approximation:

we have come close to I = 0.69 in just two approximations. Trapezoidal rule is more powerful than the rectangular method,so that we hardly use rectangular method.

3. Midpoint rule This method is also powerful and compares with trapezoidal rule. Let us take the function at the middle value--- for x = (a+b)/2 Construct a rectangle with width = (b-a) but height = f((a+b)/2) , that is the midpoint between a and b.

Let us take the same example:midpoint x= 1.5 First approximation: We are rather close to I = 0.69 Second approximation:

The midpoint method is more efficient;in two approximations we got very closer to I=0.69; Error = [0.005/0.69]100= 0.72%

I always suggest midpoint method to researchers doing numerical integration! Let us see the third approximation :

Applying the midpoint method: I =0.25(1/1.125+1/1.375+1/1.625+1/1.875)=0.691219=0.6912 This answer is pretty close to the actual value of 0.69314 The error is 0.002/0.693 x100=

0.2%

----------------------------------------------------------------------------------------Practice Problems: 1 Using the trapezoidal rule and midpoint rule,find the approximate value of the integral:

The answer is 2 Find ln5 using the integral: use the midpoint method.

--------------------------------------------------------------------------------------[Note: In advanced courses in Numerical Integration, you will learn the method of Simpson rule,wherein the curve f(x) is approximated to a parabola, instead of a rectangle or trapezoid and then integrated: f(x)= a + bx +cxx.] --------------------------------------------the end-----------------------------------------