The objective is to show that back substitution is backward stable. Consider the system
where is an upper triangular
matrix and
are
column vectors. For a
matrix system, this would look like:
Now let us consider the perturbation matrix
and a computed solution for
A system is backward stable if, on a computer with standard machine arithmetic, the computed solution satisfies the following:
where
which is more concisely expressed as
Let us begin by considering the third row, which purely mathematically solves as follows:
Let us introduce a machine perturbation at as follows, which results in a computed solution
The problem with this formulation is that the perturbation introduced does not match our definition for backward stability, which results in a formulation such as this:
We must thus transform the perturbation in to one in
. A Taylor series for the perturbation in
allows us to move the perturbation from the numerator to the denominator in this way:
where
This means that we can rewrite our equations for as
or
Thus
Now that we have solved for , we can proceed up a row and solve for
. We start by solving for
as follows:
Note that we have three operations in this step:
- Multiplication in the numerator
- Subtraction in the numerator
- Division between the numerator and the denominator
This introduces three points of machine error, accounted for thus:
where, as always,
Using the Taylor series transformation for two out of the three error expressions,
Again,
We can combine the two error expressions in the denominator by considering the fact that is beyond our considerations, as has been consistently shown. We thus say that
and substituting
where
Equating, as before,
and
Finally we get to the top row. The value for $\hat{x}_{1}$ is given
by
We have the same possibility for machine error as before, except that we have some additional calculations, each with the possibility of inducing error. Let us rewrite the above as follows:
which more clearly shows the order of machine operations. The error points can be inserted thus:
Performing the Taylor series operation and combining and
, we have
Multiplying
Factoring out in the numerator and applying two more Taylor series transformations, we can say
Combining error terms and eliminating the squared epsilons yields
Noting as before that
We are now able to construct the perturbation matrix thus:
Now we must use this to satisfy the criterion for the backward stability of back substitution:
Let us write a matrix in accordance with this criterion and factoring
out the machine epsilon:
We can factor the machine epsilon out because we have consistently demonstrated that all of the epsilons are smaller than the machine epsilon, thus the matrix on the right hand side is greater than the one on the left. The greatest single coefficient of the machine epsilon is 3, which equals to the matrix size . So this criterion is achieved for any and all of the quotients, and thus the backward stability of back substitution is achieved.
Concerning the extension of this pattern to larger matrices, the number of errors–and thus the value of the coefficients in the normalized matrix we wrote at the end–depends upon the number of calculations and thus points of error. These can be discussed as follows:
- Division: each calculation has one division. The error resulting from this division appears in the main diagonal because the denominator is always the coefficient in the diagonal, thus one error for each diagonal position is a result of the division.
- Multiplication: each non-diagonal term is associated with a multiplication because we are solving for the
associated with the diagonal. So one additional error is added to each non-diagonal element in the upper portion of the matrix for multiplication.
- Subtraction: there are as many subtractions as there are multiplications, but they end up in the error matrix differently. The situation with subtraction is further complicated by that fact that, in multiplying through the subtractive errors in order to get the error expressions into the denominator, the sum of the subtractive error coefficients ends up to be greater than the total number of error expressions entered into the equations. First, because of the multiplying through to get the Taylor series conversions to the denominator, the number of subtractive errors in the main diagonal (and thus associated with the denominator) is
, where
is the row number. For the rest of the matrix, the number of subtractions is
, where
is the column number.
The sum of any of these errors that apply to a given position in the matrix is the total number of errors in that position, and thus the value of that position in the error matrix.
The critical position is . In that position there is one error for division and
errors for division. The sum of these is always
, and thus the criterion for stability is maintained as the matrix size increased.