202-1-3011 Introduction to Numerical Analysis
Assignment #1
Due: 12.9.2007
General guidelines for this and future assignments
- Be concise, clear, and organized.
- Don't provide only final answers. Show all your calculations and thought process.
- If you are the only one who can read your handwriting, print your answers. We will not check unreadable submissions.
- Certain problems may ask for Matlab programs. In these cases you would normally need to show a printout of your code along with numerical results. If requested (and only if requested),email your code as an attachment to the grader.
- Homework assignments are individual assignments. Do it by yourself!! Don't copy your answersfrom others. You will learn nothing by doing so and your assignment grade will not besomething to be proud of.
- Submit your answers by 17:00 on the due date to the Numerical Analysis Box in the ComputerScience department.
- Late submissions will not be accepted unless authorized in advanced by the lecturer.
1. Your very first numerical algorithm
In class we introduced an algorithm for finding the square root of a given number M by (a) increasinga guess xiby step h until (xi+ h)2-M > 0, then (b) decreasing the step size, and (c) repeatingeverything until a desired approximation εis achieved.
- Implement this algorithm as a Matlab program that takes a single input (the number M) andreturns an answer accurate up to ε= 10-10(or less). In your answer show your code, theiterations (ordinal number, current guess, and error relative to the "true" answer as obtainedwith Matlab's function sqrt()), and the final results.
Note: format the output with sprintf() using %<n>.<m>f to make sure Matlab displays enoughdigits after the decimal point. Output can be recorded and then printed with Matlab's diarycommand. If the output of a particular run contains too many iterations to print (say, wellover 100 iterations), edit the diary with a text editor and crop all but the very first and verylast iterations before you print the file for submission.
When your program is ready, test it on the following inputs:
- M = 9801
- M = 0.3141589
- M = 3141589
Does it work properly?
Discuss your results, make observations about potential problems, andexplain what's going on.
- In our program we required accuracy up to certain absolute error ε. However, since the realanswer is unknown, testing for the difference |xi – M|(where xiis the approximationat iteration i) was impossible and we had to resort to a criterion that we could compute.Unfortunately, this criterion does not guarantee the required accuracy.
- Explain when you expect the original stopping criterion to be particularly bad and givesuch an example using your program above.
- Improve the program by defining a new stopping criterion that is both computable andguarantees the required absolute error of ε= 10-10. Explain how your improvementachieves the task and test with the previous three inputs. Are all problem solved now?
- Now you are required to think as a numerical analyst and improve the basic idea and yourprogram such that the approximated solution in found in as few iterations as you can possiblyachieve. Note - you are not asked to invent a new algorithm. Rather, improve the algorithmyou already implemented above (for example, one possibility, but certainly not the only orthe best one, is to make better initial guesses).
Explain your improvements and submit yourimproved program as a .m file whose name is HW01_P01 <student-number>.m. Note that yourfunction should be called similarly.
2 Floating points and error analysis
F2 is a revolutionary computer with 2 digits floating point arithmetic, rounding, and arbitrary,unlimited exponent. Find three real numbers x; y; z such that their sum S = (x+y)+z in F2 givesrelative error of 100% or more. Explain your answer.
3 error analysis
Let the two numbers, a=101 and b=100, be both known with the relative error δ.
The relative error in calculation of a-b is 10-2. What can be the minimal value of δ?
4 Floating points and error analysis
The software in the Patriot missile that failed in Saudi Arabia in 1991 represented the time intervalof 0.1 second with a binary numberof 23 digits and chopping (note - this is not a normalized floating point representation). The system tracked potential targets by dividing the elapsed timeby the target speed. Time differences were computed as follows based on the system clock, whichreturned values ni in units of tenth of a second:
t1←x n1
t2←x n2
∆t←t1-t2
Given that information, answer all the sections below:
1. What are 0.1 andin binary?
2. What are the absolute and relative errors in?
3. What is the number of significant (binary) digits in?
4. Assume that n1 was read from the system clock 8 hours after initialization and n2 was readtwo seconds later. What are the absolute and relative errors in ∆t in this case?
5. Repeat section 4 for 100 hours after initialization instead of 8.
6. Assume that the missile software was updated with a newer and more accurate time calculationprocedure. Assume further that this new procedure was inserted in several, but not all parts ofthe program. Repeat section 4 under the ssumption that t2 is calculated based on 0.1 whilet1 is still calculated based on. Expressed absolute error as a decimal number (in seconds)and relative error in percentiles.
7. Repeat section 6 for 100 hours after initialization instead of 8
(this is the case which causedthe failure in the Patriot in 1991 that caused the death of 28 marines!!).