Numerical Methods and Optimization

Elements of Numerical Linear Algebra 75

of this system. The k

th

iteration of the Jacobi method is

x

(k+1)

i

=

d

i

+

n



j=1

j=i

a

ij

x

(k)

j

(1 − a

ii

)

for i =1, 2,...,n,

where 0 ≤ a

ij

< 1, d

i

≥ 0 for all i, j =1, 2,...,n. Therefore, if x

(k)

≥ 0

then x

(k+1)

i

≥ 0fori =1, 2,...,n, so x

(k+1)

≥ 0. Thus, choosing x

(0)

≥ 0,

the method will generate a sequence of nonnegative vectors converging to the

unique solution, which is also nonnegative.

3.3 Overdetermined Systems and Least Squares Solution

Consider a system Ax = b, where A is an m × n matrix with entries

a

ij

,i=1,...m,j =1,...,n, x =[x

1

,...,x

n

]

T

is the vector of unknowns, and

b =[b

1

,...,b

m

]

T

is the vector of right-hand sides.