nag_linsys_real_posdef_solve_1rhs (f04as) calculates the accurate solution of a set of real symmetric positive definite linear equations with a single right-hand side,

A x = b

, using a Cholesky factorization and iterative refinement.

Syntax

[a, c, ifail] = f04as(a, b, 'n', n)

[a, c, ifail] = nag_linsys_real_posdef_solve_1rhs(a, b, 'n', n)

Description

Given a set of real linear equations

A x = b

, where

A

is a symmetric positive definite matrix, nag_linsys_real_posdef_solve_1rhs (f04as) first computes a Cholesky factorization of

A

A = L L^{T}

where

L

is lower triangular. An approximation to

x

is found by forward and backward substitution. The residual vector

r = b - A x

is then calculated using additional precision and a correction

d

x

is found by solving

L L^{T} d = r

x

is then replaced by

x + d

, and this iterative refinement of the solution is repeated until machine accuracy is obtained.

References

Wilkinson J H and Reinsch C (1971) Handbook for Automatic Computation II, Linear Algebra Springer–Verlag

Parameters

Compulsory Input Parameters

1: $a (lda :)$ – double array: The first dimension of the array a must be at least $\max (1, n)$ .
The second dimension of the array a must be at least $\max (1, n)$ .

The upper triangle of the $n$ by $n$ positive definite symmetric matrix $A$ . The elements of the array below the diagonal need not be set.
2: $b (\max (1, n))$ – double array: The dimension of the array b must be at least $\max (1, n)$

The right-hand side vector $b$ .

Optional Input Parameters

1: $n$ – int64int32nag_int scalar: Default: the first dimension of the array a and the second dimension of the arrays a, b.
$n$ , the order of the matrix $A$ .

Constraint: $n \geq 0$ .

Output Parameters

1: $a (lda :)$ – double array: The first dimension of the array a will be $\max (1, n)$ .
The second dimension of the array a will be $\max (1, n)$ .

The elements of the array below the diagonal are overwritten; the upper triangle of $a$ is unchanged.
2: $c (\max (1, n))$ – double array: The solution vector $x$ .
3: $ifail$ – int64int32nag_int scalar: $ifail = 0$ unless the function detects an error (see Error Indicators and Warnings).

Error Indicators and Warnings

Errors or warnings detected by the function:

$ifail = 1$: The matrix $A$ is not positive definite, possibly due to rounding errors.

$ifail = 2$: Iterative refinement fails to improve the solution, i.e., the matrix $A$ is too ill-conditioned.

$ifail = 3$

On entry,	$n < 0$ ,
or	$lda < \max (1, n)$ .

$ifail = - 99$: An unexpected error has been triggered by this routine. Please contact NAG.

$ifail = - 399$: Your licence key may have expired or may not have been installed correctly.

$ifail = - 999$: Dynamic memory allocation failed.

Accuracy

The computed solutions should be correct to full machine accuracy. For a detailed error analysis see page 39 of Wilkinson and Reinsch (1971).

Further Comments

The time taken by nag_linsys_real_posdef_solve_1rhs (f04as) is approximately proportional to

n^{3}

The function must not be called with the same name for arguments b and c.

Example

This example solves the set of linear equations

A x = b

where

A = (\begin{array}{r} 5 & 7 & 6 & 5 \\ 7 & 10 & 8 & 7 \\ 6 & 8 & 10 & 9 \\ 5 & 7 & 9 & 10 \end{array}) and b = (\begin{array}{l} 23 \\ 32 \\ 33 \\ 31 \end{array}) .

Open in the MATLAB editor: f04as_example

function f04as_example


fprintf('f04as example results\n\n');

% Accurate solution to Ax = b, for positive definite A
a = [5,  7,  6,  5;
     7, 10,  8,  7;
     6,  8, 10,  9;
     5,  7,  9, 10];
b = [23;
     32;
     33;
     31];

[afac, x, ifail] = f04as(a, b);

disp('Solution');
disp(x);

f04as example results

Solution
     1
     1
     1
     1

PDF version (NAG web site, 64-bit version, 64-bit version)

Chapter Contents

Chapter Introduction

NAG Toolbox