MATH 2308 Saint Marys University Intro to Numerical Analysis Program Questions

Description

For
computer problems, make sure to submit a copy of the source code you have written
and as well as a copy of the output produced by your program. All computer programs
should be written in Fortran 95.

2 attachmentsSlide 1 of 2attachment_1attachment_1attachment_2attachment_2

Unformatted Attachment Preview

CSCI/MATH2308.1 2020
Assignments should be submitted to the appropriately titled Brightspace Dropbox. For
computer problems, make sure to submit a copy of the source code you have written
and as well as a copy of the output produced by your program. All computer programs
should be written in Fortran 95.
1 Consider the two mathematically equivalent expressions
𝑓 (𝑥 ) = 𝑥(√𝑥 + 1 − √𝑥),
and
𝑔(𝑥 ) =
𝑥
(√𝑥+1+√𝑥)
a) Prove that the two expressions are mathematically equivalent.
b) Which of the two expressions can be evaluated more accurately in floating point
arithmetic? Why?
c) Using 4-digit precision, at 𝑥 = 500, 𝑓(500) = 10, and 𝑔(500) = 11.17. Which of
these two evaluations is correct? Explain the discrepancy by performing the
computation and analyzing the interim steps. Use an arbitrary precision calculator
such as https://apfloat.appspot.com/.
2 Assume that you are solving the quadratic equation 𝑎𝑥 2 + 𝑏𝑥 + 𝑐 = 0, with 𝑎 = 1.22,
𝑏 = 3.34, and 𝑐 = 2.28, using the standard quadratic formula, and using 3-digit
arithmetic with rounding. Use an arbitrary precision calculator such as
https://apfloat.appspot.com/.
a. What is the computed value for 𝑏 2 − 4𝑎𝑐 ?
2
b. What is the exact value for 𝑏 − 4𝑎𝑐?
c. What is the relative error for the computed value for 𝑏 2 − 4𝑎𝑐 ?
3 When 𝑎 and 𝑏 are the same sign, which of the following two formulas is preferable
for computing the midpoint 𝑚 of an interval [𝑎, 𝑏], in floating point arithmetic with
rounding? Why? [Hint: It is possible to devise example(s) in which the midpoint lies
outside the interval [𝑎, 𝑏], for only one the formulas above.]
𝑚=
𝑎+𝑏
2
𝑜𝑟
𝑚=𝑎+
𝑏−𝑎
2
Programming Questions
1)
Write a program to compute the mathematical constant 𝑒, the base of natural logarithms
from the definition
1.0 𝑛
𝑒 = lim (1.0 +
) .
𝑛→∞
𝑛
1.0 𝑛
Specifically, compute (1.0 + 𝑛 ) for 𝑛 = 10𝑘 , 𝑘 = 1, 2, … ,20. Determine the error in your
successive approximations by comparing them with the exact value, 𝑒. Does the error
always decrease as 𝑛 increases? Explain your results.
2)
a) Consider the function
𝑓 (𝑥 ) =
Use L’ Hospital’s rule to show that
(𝑒 𝑥 − 1)
.
𝑥
(𝑒 𝑥 − 1)
= 1.
𝑥→0
𝑥
lim 𝑓 (𝑥 ) = lim
𝑥→0
b) Check this result empirically by writing a program to compute 𝑓(𝑥) for
𝑥 = 10.0−𝑘 , 𝑘 = 1, … … … . . , 15 . Do your results agree with theoretical
expectations? Explain why.
3)
Write a program to compute the absolute and relative errors in Stirling’s approximation
𝑛! ≈ √2𝜋𝑛 (𝑛⁄𝑒)𝑛 .
for 𝑛 = 1, 2, … … … ,10. Does the absolute error grow or shrink as 𝑛 increases? Does the
relative error grow or shrink as 𝑛 increases?
CSCI/MATH 2308 Assignment Help
Overview: All of the questions in this assignment exemplify the complications encountered
when numerical computations are carried out in floating point arithmetic.
It is important to realize that often times, computations done with finite precision arithmetic,
produce results which will eventually diverge from theoretical expectations, much like in the
case of the finite difference approximation discussed in class. These assignment questions are
no exception, so you should expect to see some anomalies in the computed solution that will
require some analysis.
When attempting to answer any of these questions, you must put on your numerical analysis
thinking cap and assess the problem in the context of numerical issues such as, machine
precision, underflow, overflow, truncation error, round-off error and catastrophic
cancelation. This is because at least one of these culprits is inevitably responsible for anomalies
in the computed solution.
What to look out for:
Catastrophic cancellation: Beware of expressions or numbers with different or alternate signs
(plus & minus) which are added together. These must be analyzed carefully as a potential
source of the cancellation of significant digits.
Machine precision: This is the smallest positive number in a floating point system whose sum
with 1 is larger than 1, that is,
1 + 𝜖𝑀𝐴𝐶𝐻 > 1
The addition of any number 𝜖 < 𝜖𝑀𝐴𝐶𝐻 to 1 will have no impact on the sum. In other words, 1+𝜖 = 1 Note that numbers less than 𝜖𝑀𝐴𝐶𝐻 can be represented in the given floating point system. Underflow: All numbers less than the smallest number in a floating point system are referred to as underflow. These numbers cannot be represented by the system and are replaced by zero. Overflow: All numbers greater than the largest number in a floating point system are referred to as underflow. These numbers cannot be represented by the system and are replaced by not a number (NAN). Round-off error: This occurs because floating point systems have finite precision and cannot therefore represent all real numbers accurately. Rounding error is an inevitable consequence when computations are performed using floating pint arithmetic. Truncation error: This is concerned with the approximation of an exact mathematical procedure with a numerical technique. E.g. approximation the derivative of a function with a finite difference approximation formula. Question 1: Hint: One of these two formulas is susceptible to a numerical complication that arise when numbers with different signs are added together. Please use 4-digit precision with truncation (no rounding) at each step in the computation process. Question 2: Please use 3-digit precision when required with rounding at each step in the computation process. Note that the computed value is rounded to 3-digit precision and the exact value to infinite precision, which is as many digits as it takes to represent the result of the computation. Question 3: Hint: One of these two formulas is susceptible to one of the numerical complications mentioned above. For example, using two digit precision with rounding at each step, choose,[ 𝑎, 𝑏] = [9.7, 9.9], then 𝑚= 𝑚=𝑎+ 𝑎 + 𝑏 9.7 + 9.9 19.6 20 = = = = 10 2 2 2 2 𝑏−𝑎 9.9 − 9.7 0.2 = 9.7 + = 9.7 + = 9.7 + 0.1 = 9.8 2 2 2 In the first formula, the sum of 𝑎 and 𝑏 is 3 digits, which has to be rounded to two digits as required, hence this results in the midpoint being outside the interval [9.7, 9.9]! Note that in this example the midpoint is larger than the range of numbers in the given system. You will have to identify what numerical complication is at play here. Please make sure to devise your own example. Programming Questions 1) Write a program to compute the mathematical constant 𝑒, the base of natural logarithms from the definition 𝑒 = lim (1.0 + 𝑛→∞ 1.0 𝑛 ) . 𝑛 Theoretical Result: As n approaches infinity, Euler’s number e, on the left is exactly equal to the formula on the right. Numerical Reality: We can never reach infinity or the end of the real number line because it has infinitely many numbers, so n can only be numerically represented as a very large integer. Therefore, the theoretical equality must be replaced by an approximation of the form, 𝑒 ≈ (1.0 + 1.0 𝑛 ) , 𝑟𝑒𝑎𝑙(𝑛) for some large integer, n. 1.0 𝑛 Numerical Experiment: For 𝑛 = 10𝑘 , 𝑘 = 1, 2, … … 20, approximate e with (1.0 + 𝑟𝑒𝑎𝑙(𝑛)) . That is: when 𝑘 = 1, 𝑛 = 101 = 10 Compute 1) (1.0 + 10 1.0 ) ≈𝑒 𝑟𝑒𝑎𝑙(10) 2) Absolute error = |𝑒 − (1.0 + ⋮ ⋮ 10 1.0 ) | 𝑟𝑒𝑎𝑙(10) When, 𝑘 = 20, 𝑛 = 1020 Compute 1) 20 10 1.0 (1.0 + ) 𝑟𝑒𝑎𝑙(1020 ) 1.0 1020 2) Absolute error = |𝑒 − (1.0 + 𝑟𝑒𝑎𝑙(1020 )) ≈𝑒 | Program notes: 1) Note that the value of n changes with each different value of k, so a loop must be used to execute this part of the program. 2) Three variables must be declared in this program. Integer type must be declared for variables, 𝑛, 𝑘, and real type for the approximation, (1.0 + 1.0 𝑛 𝑛 ) . Use the Fortran intrinsic type, 𝑒𝑥𝑝(1.0) for the exact value of 𝑒. 3) In order to obtain the program you need for this question, make a copy of the finite difference program, and edit it to obtain the program you need rather that writing a new program from scratch. 4) Please observe that the variable n is of integer type, so the key phrase (𝑟𝑒𝑎𝑙(𝑛)) is used to protect the computation from mixed mode arithmetic complications. 5) Should you wish to do so, a variable of type real can be declared and used to store the result of the absolute error computation is step 2 above. Hint: As n increases, expect the absolute error to initially decrease down to a minimum, then eventually increase. Revisit the finite difference approximation experiment because the analysis of the error trend is similar to this question. You will have to explain in your analysis, what possible sources of error contribute to the trend in the absolute error. Can you also explain why the value of the approximation equals one after a while? 2) a) Consider the function 𝑓(𝑥) = Use L’ Hospital’s rule to show that (𝑒 𝑥 − 1) . 𝑥 lim 𝑓 (𝑥) = 1. 𝑥→0 b) Check this result empirically by writing a program to compute 𝑓(𝑥) for 𝑥 = 10−𝑘 , 𝑘 = 1, … … … . . , 15 . Do your results agree with theoretical expectations? Explain why. Theoretical Result: As 𝑥 approaches zero, 𝑓(𝑥) is equals one. (Calculus of limits) Numerical Reality: Because division by zero isn’t allowed, the value of 𝑥 can never be zero, therefore, 𝑥 can only be numerically represented as very small numbers close to zero. Therefore, we expect 𝑓(𝑥) to approach one, as 𝑥 becomes increasingly smaller. That is: (𝑒 𝑥 − 1) ≈1 𝑥 Numerical Experiment: For 𝑥 = 10.0−𝑘 , 𝑘 = 1, 2, … … 15, approximate 1.0 with That is: when 𝑘 = 1, 𝑥 = 10.0−1 = 0.1 Compute 1) (𝑒 0.1 − 1) ≈1 0.1 2) Absolute error = |1.0 − (𝑒 0.1 − 1) | 0.1 (𝑒 𝑥 −1) 𝑥 . When 𝑘 = 15, 𝑥 = 10.0−15 Compute 1) −15 (𝑒10.0 − 1) ≈1 10.0−15 2) −15 Absolute error = |1.0 − (𝑒10.0 − 1) | 10.0−15 Program notes: 6) Note that the value of x changes with each different value of k, so it should be obvious by now that a loop must be used to execute the statements in this part of the program. 7) At least three variables must be declared in this program. Integer type must be declared for variable, 𝑘, and real type for the variables, 𝑥 and 𝑓(𝑥). The exact value is 1.0. 8) In order to obtain the program you need for this question, make a copy of the finite difference program, and edit it to obtain the program you need rather that writing a new program from scratch. Hint: Here again as x decreases, expect the absolute error to initially decrease down to a minimum, then eventually increase. However, in addition to the two common sources of computational error, a third numerical complication is also at play here. Note that the expression at the top is a difference of two numbers. You are to identify all the possible sources of error which contribute to the trend in the absolute error 3) Write a program to compute the absolute and relative errors in Stirling’s approximation 𝑛! ≈ √2𝜋𝑛 (𝑛⁄𝑒)𝑛 . For 𝑛 = 1, 2, … … … ,10. Does the absolute error grow or shrink as 𝑛 increases? Does the relative error grow or shrink as 𝑛 increases? Comments: The explanation of this program is relatively straightforward, the expression on the right is used to approximate n factorial. Numerical Experiment: For 𝑛 = 1, 2, . . . . . . . . . ,10. approximate n! with √2𝜋𝑛 (𝑛⁄𝑒)𝑛 . That is: when 𝑛 = 1, Compute: 1) 1! 1 2) √2𝜋 (1⁄𝑒) . 1 3) 𝐴𝑏𝑠𝑜𝑙𝑢𝑡𝑒 𝑒𝑟𝑟𝑜𝑟 = |1! − √2𝜋 (1⁄𝑒) |. 1 4) 𝑅𝑒𝑙𝑎𝑡𝑖𝑣𝑒 𝑒𝑟𝑟𝑜𝑟 = ⋮ ⋮ ⋮ |1!−√2𝜋 (1⁄𝑒 ) | 1! When 𝑛 = 10, Compute: 5) 10! 10 6) √2𝜋 ∗ 10 (10⁄𝑒) . 10 7) 𝐴𝑏𝑠𝑜𝑙𝑢𝑡𝑒 𝑒𝑟𝑟𝑜𝑟 = |10! − √2𝜋 ∗ 10 (10⁄𝑒) |. 8) 𝑅𝑒𝑙𝑎𝑡𝑖𝑣𝑒 𝑒𝑟𝑟𝑜𝑟 = |10!−√2𝜋∗10 (10⁄𝑒 ) 10 | 10! Program notes: 1) Note that both the values of 𝑛! and approximation √2𝜋𝑛 (𝑛⁄𝑒)𝑛 change as 𝑛 loops through the different values, so a loop must be used to execute the statements in this part of the program. 2) This program involves a little more finessing, so I will analyze some parts of the code here. Step 1: Computing n factorial (n!) and √2𝜋𝑛 (𝑛⁄𝑒)𝑛 . 𝟏! = 𝟏 𝟐! = 𝟏 × 𝟐 = 𝟏! × 𝟐 𝟑! = (𝟏 × 𝟐) × 𝟑 = 𝟐! × 𝟑 𝟒! = (𝟏 × 𝟐 × 𝟑) × 𝟒 = 𝟑! × 𝟒 𝟓! = (𝟏 × 𝟐 × 𝟑 × 𝟒) × 𝟓 = 𝟒! × 𝟓 ⋮ 𝒏! = (𝟏 × 𝟐 × 𝟑 × 𝟒 × 𝟓 × … × (𝒏 − 𝟏)) × 𝒏 = (𝒏 − 𝟏)! × 𝒏 Note that the current factorial, 𝑛! can be written in terms of the previous (𝑛 − 1)! Factorial multiplied by n. 1) Declare two integer type variables, 𝑛 and 𝑛_𝑓𝑎𝑐, representing 𝑛 and 𝑛!, respectively. 2) Declare three real type variables for the approximation formula, √2𝜋𝑛 (𝑛⁄𝑒)𝑛 , the absolute error and pi. I will use 𝑎𝑝𝑝𝑟𝑜𝑥, 𝑎𝑏𝑠_𝑒𝑟𝑟, and 𝑝𝑖 respectively. 3) The intrinsic function 𝑒𝑥𝑝(−𝑟𝑒𝑎𝑙(𝑛)) replaces 𝑒 −𝑛 . Note that (𝑟𝑒𝑎𝑙(𝑛)) is used to protect computation from mixed mode arithmetic complications. 4) The variable pi is defined in Fortran as either: 𝜋 = 4 ∗ 𝑡𝑎𝑛−1 (1.0) or 𝜋 = 𝑐𝑜𝑠 −1 (−1.0) 5) Use the Fortran intrinsic type, 𝑒𝑥𝑝(1.0) for the exact value of 𝑒. 6) The intrinsic Fortran function 𝑠𝑞𝑟𝑡(𝑥) replaces √𝑥 in the code 7) Initialize, 𝑝𝑖 = 𝑎𝑐𝑜𝑠(−1.0), 𝑛_𝑓𝑎𝑐 = 1 then 8) Construct loop index, n, see code fragment below 𝑝𝑖 = 𝑎𝑐𝑜𝑠(−1.0) (𝑎𝑐𝑜𝑠(𝑥)) is the intrinsic Fortran function 𝑐𝑜𝑠 −1 (𝑥)). 𝑛_𝑓𝑎𝑐 = 1 Do 𝑛 = 1, 10 𝑛_𝑓𝑎𝑐 = 𝑛_𝑓𝑎𝑐 × 𝑛 𝑎𝑝𝑝𝑟𝑜𝑥. = √2𝜋𝑛 (𝑛𝑛 𝑒 −𝑛 ), 𝑎𝑏𝑠_𝑒𝑟𝑟 = |𝑛_𝑓𝑎𝑐 − 𝑎𝑝𝑝𝑟𝑜𝑥| print: 𝑛, 𝑛_𝑓𝑎𝑐, 𝑎𝑏𝑠_𝑒𝑟𝑟 End Do Important: Exponentiation in Fortran is implemented by the double asterisk, **. For e.g. 2𝑘 ≡ 2∗∗ 𝑘 Hint: The questions to this problem are very straightforward. Purchase answer to see full attachment Tags: numerical analysis quadratic equation mathematically equivalent expressions floating point arithmetic arbitrary precision User generated content is uploaded by users for the purposes of learning and should be used following Studypool's honor code & terms of service.