function f (x) is ill-conditioned.
Assignment 1
1.
(a) (b)
(c) (d)
(e)
Note:
In (b)
Submit a hard-copy of your code and output, together with any explanations and comments. In addition, submit the code electronically through the teaching labs (cdf) system.
2. [15 points] Consider the expression 1 − √1−x2, for some non-zero x with |x| small (close to 0), and a computer system with four-decimal-digits precision floating-point arithmetic. What sign should the value of the expression have?
In the above computer system, what is the value of the expression for x = 10−2 and what for x = 10−3?
If any of the two values computed seems clearly wrong, propose an alternative (but mathematically equivalent) expres- sion that would give more accurate value.
Note: The values do not need to be exact, but reasonably accurate within the limitations of the computer system.
3. Some history background: In about 250 BC, the Greek mathematician Archimedes gave an estimate of the number π, by bounding the circumference of a circle of diameter 1 (hence circumference π) below and above by the perimeters of appropriate inscribed and circumscribed polygons, respectively. For example, an inscribed square has perimeter 2√2, and thus 2√2 < π . Using a 96-sided inscribed and circumscribed polygon, he was able to show 223 / 71 < π < 22 / 7.
Today we know that, if pn is the perimeter of an inscribed polygon with 2n sides, starting with p2 = 2√2, and proceed- ing with
pn+1 =2 2(1− 1−(p /2n)2), n≥2 (1) n√√n
we have pn → π , as n → ∞. You do not need to prove this. You take is as granted.
Your work is to investigate how well or badly this formula converges to π computationally, and, if it does not converge
[10 points] Find the condition number of f (x) = 1 − cos(x), and study for what values (approximate ranges) of x the
x
[10 points] Consider the (numerical) stability of the computation of the expression 1 − cos(x) (as it is given) for some
1 − cos(x) x
x close to 0. Explain what problems the computation of the expression x may give rise to. Propose a mathe-
matically equivalent expression that is likely to be more stable for x close to 0, and explain.
[5 points] Is the expression you proposed in (b) stable for some x close to π ? Explain. If not, propose yet another mathematically equivalent expression that is likely to be more stable for x close to π (as well as for x close to 0), and explain.
[5 points] Write a matlab script that, for i = −5,−6,...,−12, and δ = 10i, computes f(x) as is given in (a) and as you proposed in (b). Comment on the results.
The script should look like the following:
for i = -5:-1:-12
d = 10ˆi;
fprintf(’%12.4e %12.4e %12.4e\n’, d, (1-cos(d))/d, ... );
end
Do not alter the output format.
[5 points] Write a matlab script that, for i = −5,−6,...,−12, and δ = π +10i, computes f(x) as is given in (a) and as you proposed in (c). Comment on the results.
The script should look like the following:
for i = -5:-1:-12
d = pi+10ˆi;
fprintf(’%12.10f %12.10f %12.10f\n’, d, (1-cos(d))/d, ... );
end
Do not alter the output format.
and (c), you are interested in the stability of an expression that computes f (x) and not in the conditioning of f (x).
Assignment 1
-2-
satisfactorily, propose an alternative formula that converges to π satisfactorily. More specifically,
(a) [10 points] Assuming that pn of (1) converges to π mathematically, explain what numerical stability problems may arise in (1) that would eventually make pn a poor approximation to π.
(b) [10 points] Propose an alternative formula that converges to π satisfactorily within the limitations of our computer sys- tem (assuming the system uses double-precision IEEE floating-point arithmetic).
Hint: Consider the expression 1 − √1−x2, for some small non-zero |x|.
(c) [10 points] Write a matlab script that, for n = 2, 3, . . . , 31, computes both approximations to π and the respective errors (taking as "exact" the predefined value of π in matlab) and outputs the results in the form of a table. Comment on the results.
Your script should look like the following:
n = 31;
i = 2; p(i) = 2*sqrt(2); q(i) = 2*sqrt(2);
fprintf(’%3d %20.16f %12.4e %20.16f %12.4e\n’, i, p(i), pi-p(i), ...
q(i), pi-q(i));
for i = 2:n
p(i+1) = 2ˆi * sqrt(2*(1-sqrt(1-(p(i)/2ˆi)ˆ2)));
q(i+1) = % fill-in the alternative expression
fprintf(’%3d %20.16f %12.4e %20.16f %12.4e\n’, i+1, p(i+1), pi-p(i+1), ...
q(i+1), pi-q(i+1));
end
Do not alter the output format.
Submit a hard-copy of your code and output, together with any explanations and comments. In addition, submit the code electronically through the teaching labs (cdf) system.
4. Show that
(a) [4 points] If A∈IRn×n is positive definite, then all its diagonal entries are positive.
(b) [12 points] If A∈IRn×n is symmetric positive definite, then
|a | < aii + ajj and |a | < a a ij 2 ij iijj
√
(c) [4 points] If A∈IRn×n is symmetric positive definite, then its absolutely largest element lies on the (main) diagonal.
for all i ≠ j.
Assignment 1