Page 110 - Applied Numerical Methods Using MATLAB

ITERATIVE METHODS TO SOLVE EQUATIONS 99
a 0 −1/2 1 0
x k = = =− = x as k →∞
1 − r 1 − (−1/2) 3
and what is better, the limit is the very true solution to the given equation.
We are happy with this, but might feel uneasy, because we are afraid that this
convergence to the true solution is just a coincidence. Will it always converge,
no matter how we modify the equation so that only x remains on the LHS?
To answer this question, let us try another iterative scheme.

x =−2x − 1 → x k+1 =−2x k − 1
x 1 =−1 − 2x 0
2
x 2 =−1 − 2x 1 =−1 − 2(−1 − 2x 0 ) =−1 + 2 + 2 x 0
2 3
x 3 =−1 − 2x 2 =−1 + 2 − 2 − 2 x 0
. ..... ...... ...... ...... ...... ...... ......

This iteration will diverge regardless of the initial value x 0 . But, we are never
disappointed, since we know that no one can be always lucky.
To understand the essential difference between these two cases, we should
know the fixed-point theorem (Section 4.1). Apart from this, let’s go into a system
of equations.

3 2 x 1 1
= , Ax = b
1 2 x 2 −1
Dividing the first equation by 3 and transposing all term(s) other than x 1 to the
RHS and dividing the second equation by 2 and transposing all term(s) other
than x 2 to the RHS, we have

x 1,k+1 0 −2/3 x 1,k 1/3
= +
x 2,k+1 −1/2 0 x 2,k −1/2
x k+1 = A x k + b (2.5.1)

Assuming that this scheme works well, we set the initial value to zero (x 0 = 0)
and proceed as

−1
1 2/3 1/3
2
x k → [I + A + A + ···]b = [I − A] b =
−1

1/2 1 −1/2

1 1 −2/3 1/3 1 2/3 1 o
= = = = x
1 − 1/3 −1/2 1 −1/2 2/3 −2/3 −1
(2.5.2)
T
o
which will converge to the true solution x = [1 − 1] . This suggests another
method of solving a system of equations, which is called Jacobi iteration. It can
be generalized for an N × N matrix–vector equation as follows: