Problem Set 6 Solutions
Problem 1:
(a)
We will show that f (x) = 2x computed via the algorithim f˜(x) = x ⊕ x is backwards stable
(and hence also stable). Our computations in this problems are all with real numbers, so we may
take the norm to be absolute value. We need to show there exists x̃ with
m
|x − x̃|
er as
= O(machine )
|x|
co
eH w
that statisfies f˜(x) = f (x̃). Our control over the problem comes from choosing x̃, so we start by
o.
computing f˜(x) and figuring out what x̃ must be. Note that error in f˜ comes from two places: the
rs e
rounding error from initially turning x into a floating point number and the error from the floating
ou urc
point operation per 13.7.
o
f˜(x) = (x(1 + 1 )) ⊕ (x(1 + 1 )) = 2(x)(1 + 1 )(1 + 2 )
aC s
With |1 |, |2 | < machine . Now we must choose x̃ so that f (x̃) = 2x̃ = 2x(1 + 1 )(1 + 2 ).
vi y re
Dividing by two, we can see that we must choose x̃ = x(1 + 1 )(1 + 2 ). Its left to verify this satifies
the condition of error in proportion to x:
ed d
ar stu
|x − x̃| |x − x(1 + 1 )(1 + 2 )|
= = |1 − (1 + 1 + 2 + 1 2 )| = |1 + 2 + 1 2 | = O(machine )
|x| |x|
This finishes the proof that f is backwards stable.
is
(b)
Th
Now our function is f (x) = x2 computed as f˜(x) = x ⊗ x. It is also backwards stable. The
procedure is the same as above. First find what x̃ must be by expanding f˜, then to show x̃ is of
the right order.
sh
√
f˜ = (x(1 + 1 )) ⊗ (x(1 + 1 )) = x2 (1 + 1 )2 (1 + 2 ) = (x(1 + 1 ) 1 + 2 )2
√
So x̃ = x(1+1 ) 1 + 2 . The square root in there might be alarming, but since it is a squareroot
of one plus epsilon and not of epsilon alone, it okay since a squareroot of a number larger than one
√
gets smaller so | 1 + 2 | ≤ 1 + |2 | (2 might be negative hense the absolute values).
1
This study source was downloaded by 100000827039679 from CourseHero.com on 08-10-2021 03:18:23 GMT -05:00
https://www.coursehero.com/file/12776988/math104hw6/
Problem 1:
(a)
We will show that f (x) = 2x computed via the algorithim f˜(x) = x ⊕ x is backwards stable
(and hence also stable). Our computations in this problems are all with real numbers, so we may
take the norm to be absolute value. We need to show there exists x̃ with
m
|x − x̃|
er as
= O(machine )
|x|
co
eH w
that statisfies f˜(x) = f (x̃). Our control over the problem comes from choosing x̃, so we start by
o.
computing f˜(x) and figuring out what x̃ must be. Note that error in f˜ comes from two places: the
rs e
rounding error from initially turning x into a floating point number and the error from the floating
ou urc
point operation per 13.7.
o
f˜(x) = (x(1 + 1 )) ⊕ (x(1 + 1 )) = 2(x)(1 + 1 )(1 + 2 )
aC s
With |1 |, |2 | < machine . Now we must choose x̃ so that f (x̃) = 2x̃ = 2x(1 + 1 )(1 + 2 ).
vi y re
Dividing by two, we can see that we must choose x̃ = x(1 + 1 )(1 + 2 ). Its left to verify this satifies
the condition of error in proportion to x:
ed d
ar stu
|x − x̃| |x − x(1 + 1 )(1 + 2 )|
= = |1 − (1 + 1 + 2 + 1 2 )| = |1 + 2 + 1 2 | = O(machine )
|x| |x|
This finishes the proof that f is backwards stable.
is
(b)
Th
Now our function is f (x) = x2 computed as f˜(x) = x ⊗ x. It is also backwards stable. The
procedure is the same as above. First find what x̃ must be by expanding f˜, then to show x̃ is of
the right order.
sh
√
f˜ = (x(1 + 1 )) ⊗ (x(1 + 1 )) = x2 (1 + 1 )2 (1 + 2 ) = (x(1 + 1 ) 1 + 2 )2
√
So x̃ = x(1+1 ) 1 + 2 . The square root in there might be alarming, but since it is a squareroot
of one plus epsilon and not of epsilon alone, it okay since a squareroot of a number larger than one
√
gets smaller so | 1 + 2 | ≤ 1 + |2 | (2 might be negative hense the absolute values).
1
This study source was downloaded by 100000827039679 from CourseHero.com on 08-10-2021 03:18:23 GMT -05:00
https://www.coursehero.com/file/12776988/math104hw6/
