544
Appendix
C.
Solutions
to
odd-numbered
exercises
The
exact solution
is
Figure
C.9.
The
exact
and
approximate
solutions
from
Exercise
5.5.5.
7.
(a) It
will
take about
10
3
times
as
long,
or
1000 seconds (almost
17
minutes),
to
solve
a
1000
x
1000 system,
and
100
3
times
as
long,
or
10
6
seconds (about 11.5
days)
to
solve
a
10000
x
10000 system.
(b)
Gaussian elimination consists
of a
forward
phase,
in
which
the
diagonal entries
are
used
to
eliminate nonzero entries below
and in the
same column,
and a
backward
phase,
in
which
the
diagonal entries
are
used
to
eliminate nonzero
entries above
and in the
same column. During
the
forward
phase,
at a
typical
step, there
is
only
1
nonzero entry below
the
diagonal,
and
only
5
arithmetic
operations
are
required
to
eliminate
it (1
division
to
compute
the
multiplier,
and 2
multiplications
and 2
additions
to add a
multiple
of the
current
row
to the
next). Thus
the
forward
phase requires
O(5n)
operations.
A
typical
step
of the
backward phase requires
3
arithmetic operations
(a
multiplication
and an
addition
to
adjust
the
right-hand side
and a
division
to
solve
for the
unknown).
Thus
the
backward phase requires
O(3n)
operations.
The
grand
total
is
O(8n)
operations.
(c)
It
will
take about
10
times
as
long,
or 0.1
seconds,
to
solve
a
1000
x
1000
tridiagonal system,
and 100
times
as
long,
or 1
second,
to
solve
a
10000
x
10000
tridiagonal system.
The
exact
and
approximate solutions
are
graphed
in
Figure
C.9.
544 Appendix
C.
Solutions
to
odd-numbered exercises
The
exact solution is
1
2 1 1
u(x)
=
--x
+
-x
-
--In
(1
+ x)
4 2
4ln2
.
The
exact
and
approximate solutions are graphed in Figure C.g.
0.045r-----r-----r-----r-----r----~
0.04
0.035
0.03
0.025
0.02
0.015
0.01
0.2
0.4 0.6
exact
approximate
0.8
Figure
C.9.
The exact and approximate solutions from Exercise 5.5.5.
7.
(a)
It
will take
about
10
3
times as long,
or
1000 seconds (almost
17
minutes),
to
solve a 1000 x 1000 system,
and
100
3
times as long, or
10
6
seconds (about 11.5
days)
to
solve a 10000 x 10000 system.
(b) Gaussian elimination consists of a forward phase, in which
the
diagonal entries
are
used
to
eliminate nonzero entries below
and
in
the
same column,
and
a
backward phase, in which
the
diagonal entries are used
to
eliminate nonzero
entries above
and
in
the
same column. During
the
forward phase,
at
a typical
step,
there
is only 1 nonzero
entry
below
the
diagonal,
and
only 5 arithmetic
operations are required
to
eliminate
it
(1
division
to
compute
the
multiplier,
and
2 multiplications
and
2 additions
to
add
a multiple of
the
current row
to
the
next).
Thus
the
forward phase requires O(5n) operations. A typical
step of
the
backward phase requires 3 arithmetic operations (a multiplication
and
an
addition
to
adjust
the
right-hand side
and
a division
to
solve for
the
unknown). Thus
the
backward phase requires O(3n) operations.
The
grand
total
is O(Sn) operations.
(c)
It
will take
about
10
times as long, or 0.1 seconds,
to
solve a 1000 x 1000
tridiagonal system,
and
100 times as long, or 1 second,
to
solve a 10000 x 10000
tridiagonal system.