Page 31 - Compact Numerical Methods For Computers

Formal problems in linear algebra 21
equations. Fröberg (1965, p 256) considers the differential equation
2
y" + y/(1+x ) = 7x (2.8)
with the boundary conditions

(2.9)
y = { 0 for x = 0 (2.10)
2
for x = 1.
To solve this problem numerically, Fröberg replaces the continuum in x on the
interval [0, 1] with a set of (n + 1) points, that is, the step size on the grid is
h = 1/n. The second derivative is therefore replaced by the second difference at
point j
2
(y – 2y j + y )/h . (2.11)
j+l
j-1
The differential equation (2.8) is therefore approximated by a set of linear
equations of which the jth is
(2.12)
or

(2.13)

Because y = 0 and y = 2, this set of simultaneous linear equations is of order
n
0
(n - 1). However, each row involves at most three of the values y . Thus, if the
j
order of the set of equations is large, the matrix of coefficients is sparse.
2.3. THE LINEAR LEAST-SQUARES PROBLEM

As described above, n linear equations give relationships which permit n parame-
ters to be determined if the equations give rise to linearly independent coefficient
vectors. If there are more than n conditions, say m, then all of them may not
necessarily be satisfied at once by any set of parameters x. By asking a somewhat
different question, however, it is possible to determine solutions x which in some
way approximately satisfy the conditions. That is, we wish to write

Ax b (2.14)
where the sense of the sign is yet to be defined.
By defining the residual vector

r = b – Ax (2.15)
we can express the lack of approximation for a given x by the norm of r
|| r ||. (2.16)
This must fulfil the following conditions:

|| r || > 0 (2.17)
for r 0, and || 0 || = 0,
|| cr || = || c || · || r || (2.18)