pdf
keyboard_arrow_up
School
The Chinese University of Hong Kong *
*We aren’t endorsed by this school
Course
3230
Subject
Mathematics
Date
Nov 24, 2024
Type
Pages
2
Uploaded by MinisterGorilla8297
MATH3230 Numerical Analysis
Tutorial 2
1
Recall:
1.1
Iterative methods and rate of convergence
1.
Linear convergence of a sequence:
Assume that a sequence
{
x
k
}
converges to
x
∗
, it is said to converge linearly
to
x
∗
if
lim
k
→∞
|
x
k
+1
−
x
∗
|
|
x
k
−
x
∗
|
=
ρ,
where
0
< ρ <
1
is a constant.
2.
Sublinear convergence of a sequence:
If
ρ
= 1
, we say that
{
x
k
}
coverge to
x
∗
sublinearly.
3.
Superlinear convergence of a sequence:
If
ρ
= 0
, we say that
{
x
k
}
coverge to
x
∗
superlinearly.
4.
Convergence order:
If there are two positive constants
C
and
p >
1
such that
lim
k
→∞
|
x
k
+1
−
x
∗
|
|
x
k
−
x
∗
|
p
=
C,
then the sequence
{
x
k
}
is said to converge to
x
∗
with order
p
.
When
p
= 2
,
{
x
k
}
is said to converge to
x
∗
quadratically or the sequence is of quadratic convergence.
1.2
Absolute and relative error:
The absolute error between the true value
x
∗
and the approximate value
x
k
is the error given by
|
x
k
−
x
∗
|
.
The relative error between the true value
x
∗
and the approximate value
x
k
is the error given by
ρ
=
|
x
k
−
x
∗
|
|
x
∗
|
.
1.3
Bisection method:
1. The bisection algorithm is based on the intermediate value theorem:
Theorem 1
(Intermediate value theorem)
.
Let
f
(
x
)
be continuous on
[
a, b
]
, then for any real number
g
that lies
between
f
(
a
)
and
f
(
b
)
there exists
ζ
∈
[
a, b
]
such that
f
(
ζ
) =
g
.
We then have the following
Theorem 2.
If
f
(
a
)
f
(
b
)
<
0
, then there exists at least one solution
x
∗
∈
(
a, b
)
such that
f
(
x
∗
) = 0
.
2.
Convergence of Bisection Algorithm:
Theorem 3.
Let
f
(
x
)
be a continuous function on
[
a, b
]
such that
f
(
a
)
f
(
b
)
<
0
, then the bisection algorithm always
converges to a solution
x
∗
of the equation
f
(
x
) = 0
, and the following error estimate holds for the
k
−
th approximate
value
x
k
:
|
x
k
−
x
∗
| ≤
1
2
(
b
k
−
a
k
) = 2
−
(
k
+1)
(
b
−
a
)
.
3.
Improved Bisection Method
Convergence of the improved bisection method
Theorem 4.
Suppose
f
is a convex function on the interval
[
a, b
]
such that
f
(
a
)
<
0
and
f
(
b
)
>
0
.
Then the
sequence
{
c
k
}
, generated by the improved bisection algorithm with the initial interval
[
a
0
, b
0
] = [
a, b
]
, satisfies either
f
(
c
k
) = 0
for some
k
≥
0
, or
c
k
→
x
∗
∈
[
a, b
]
, where
f
(
x
∗
) = 0
.
1
2
Exercises:
Please do the star problem (*) in tutorial class first and finish the rest after class.
1.
(a) * State the definition of the following concepts:
i. Linear convergence of a sequence;
ii. Sublinear convergence of a sequence;
iii. Superlinear convergence of a sequence;
iv. Convergence of a sequence with order
p
;
(b) Check whether the following sequences converge. In the case of convergence, find the rate of convergence or
the convergence order.
i. *
x
n
=
1
n
2
,
n
= 0
,
1
,
2
,
· · ·
.
ii.
x
n
= 5 +
(
2
3
)
n
, n
= 0
,
1
,
2
,
· · ·
.
iii. *
x
n
=
∑
n
k
=1
1
k
,
n
= 1
,
2
,
· · ·
.
iv. *
x
0
>
0
,
x
n
+1
= (2
−
n
+ 3
−
n
)
x
n
,
n
= 0
,
1
,
2
,
· · ·
.
v.
x
n
= 1 + 2
1
−
n
+
1
(
n
+2)
n
,
n
= 0
,
1
,
2
,
· · ·
.
2.
(a) * Show that a sequence that converges with order
α >
1
must converge superlinearly.
(b) Show that the sequence
x
n
=
1
n
n
converges superlinearly to
0
but does not converge to
0
with order
α
for any
α >
1
.
3.
(a) * Let
p
∗
= 2
.
3026
and
p
= 2
.
30
. Compute the absolute error and relative error in the approximation of
p
∗
by
p
.
(b) * Suppose
p
must approximate
p
∗
with relative error at most
10
−
3
. Find the largest interval in which
p
must
lie for
p
∗
= 20
.
(c) Explain the advantage of the relative error over the absolute error and give an example to justify your reasons.
4.
Consider the following nonlinear equation:
f
(
x
) = 0
x
∈
[
a, b
]
,
(1)
(a) * Please state the assumptions on
f
such that the bisection algorithm works, and explain why we need these
assumptions.
(b) * Let
a
0
=
a
,
b
0
=
b
, and
[
a
n
, b
n
]
be the successive intervals generated by the bisection algorithm. Denoting
x
n
as the midpoint of
[
a
n
, b
n
]
, i.e.,
x
n
=
1
2
(
a
n
+
b
n
)
,
i. Show
|
x
n
+1
−
x
n
|
= 1
/
4(
b
n
−
a
n
)
.
ii. Using the result from the last subquestion, show
|
x
n
+1
−
x
n
|
= 2
−
n
−
2
|
b
0
−
a
0
|
.
5.
Let
f
(
x
)
be a continuous function on
R
with
f
(
a
0
)
<
0
and
f
(
b
0
)
>
0
where
a
0
= 0
and
b
0
= 1
.
(a) * Let
f
(
x
) =
−
x
2
+ 6
x
−
2
, compute the first three values
x
0
,
x
1
,
x
2
generated from the bisection method.
(b) Without computing
x
n
, what is the minimum number of iterations required by the bisection method to ap-
proximate the solution with an absolute error of less than
10
−
5
?
6.
(a) * Let
f
(
x
) := 2
x
2
+
x
−
1
, denote
{
c
k
}
as the sequence generated from the improved bisection method with
a
0
= 0
,
b
0
= 1
. Write down
c
0
and
c
1
.
(b) Let
f
(
x
)
be a convex function in
[
a, b
]
, and
x
1
,
x
2
,
x
3
∈
[
a, b
]
where
x
1
< x
2
< x
3
, show that
f
(
x
2
)
−
f
(
x
1
)
x
2
−
x
1
≤
f
(
x
3
)
−
f
(
x
2
)
x
3
−
x
2
.
(c) Let
f
(
x
)
be a second order polynomial which is also convex.
Denote
{
a
k
}
,
{
b
k
}
, and
{
c
k
}
as sequences
generated from the improved bisection method with
[
a
0
, b
0
]
such that
f
(
a
0
)
f
(
b
0
)
<
0
.
Write
x
∗
∈
[
a
0
, b
0
]
satisfies
f
(
x
∗
) = 0
, show that
c
k
−
x
∗
=
f
′′
(
x
∗
)
2
f
′
(
ζ
)
(
b
0
−
x
∗
)(
c
k
−
1
−
x
∗
)
,
for some
ζ
∈
[
a
k
, b
k
]
, and points out when the improved bisection method converges faster.
2
Your preview ends here
Eager to read complete document? Join bartleby learn and gain access to the full version
- Access to all documents
- Unlimited textbook solutions
- 24/7 expert homework help