#! /usr/bin/env python
#
def svd_solve ( m, n, a, b ):
#*****************************************************************************80
#
## SVD_SOLVE solves a linear system in the least squares sense.
#
# Discussion:
#
# The vector X returned by this routine should always minimize the
# Euclidean norm of the residual ||A*x-b||.
#
# If the matrix A does not have full column rank, then there are multiple
# vectors that attain the minimum residual. In that case, the vector
# X returned by this routine is the unique such minimizer that has the
# the minimum possible Euclidean norm, that is, ||A*x-b|| and ||x||
# are both minimized.
#
# Licensing:
#
# This code is distributed under the GNU LGPL license.
#
# Modified:
#
# 31 August 2016
#
# Author:
#
# John Burkardt
#
# Reference:
#
# David Kahaner, Cleve Moler, Steven Nash,
# Numerical Methods and Software,
# Prentice Hall, 1989,
# ISBN: 0-13-627258-4,
# LC: TA345.K34.
#
# Parameters:
#
# Input, integer M, the number of rows of A.
#
# Input, integer N, the number of columns of A.
#
# Input, real A(M,N), the matrix.
#
# Input, real B(M), the right hand side.
#
# Output, real X(N), the least squares solution.
#
import numpy as np
from dsvdc import dsvdc
from sys import exit
#
# Get the SVD.
#
a_copy = a
lda = m
ldu = m
ldv = n
job = 11
a_copy, sdiag, e, u, v, info = dsvdc ( a_copy, lda, m, n, ldu, ldv, job )
if ( info != 0 ):
print ( '' )
print ( 'SVD_SOLVE - Fatal error!' )
print ( ' The SVD could not be calculated.' )
print ( ' LINPACK routine DSVDC returned a nonzero' )
print ( ' value of the error flag, INFO = %d' % ( info ) )
exit ( 'SVD_SOLVE - Fatal error!' )
ub = np.dot ( u.transpose ( ), b )
sub = np.zeros ( n )
#
# For singular problems, there may be tiny but nonzero singular values
# that should be ignored. This is a reasonable attempt to avoid such
# problems, although in general, the user might wish to control the tolerance.
#
smax = max ( sdiag )
eps = 2.220446049250313E-016
if ( smax <= eps ):
smax = 1.0
stol = eps * smax
for i in range ( 0, n ):
if ( i <= m ):
if ( stol <= sdiag[i] ):
sub[i] = ub[i] / sdiag[i]
x = np.dot ( v, sub )
return x
def svd_solve_test ( ):
#*****************************************************************************80
#
## SVD_SOLVE_TEST tests SVD_SOLVE.
#
# Licensing:
#
# This code is distributed under the GNU LGPL license.
#
# Modified:
#
# 31 August 2016
#
# Author:
#
# John Burkardt
#
import numpy as np
import platform
from r8vec_norm import r8vec_norm
from test_ls import p00_a
from test_ls import p00_b
from test_ls import p00_m
from test_ls import p00_n
from test_ls import p00_prob_num
from test_ls import p00_x
print ( '' )
print ( 'SVD_SOLVE_TEST' )
print ( ' Python version: %s' % ( platform.python_version ( ) ) )
print ( ' SVD_SOLVE is a function with a simple interface which' )
print ( ' solves a linear system A*x = b in the least squares sense' )
print ( ' using the singular value decomposition (SVD).' )
print ( ' Compare a tabulated solution X1 to the QR_SOLVE result X2.' )
prob_num = p00_prob_num ( )
print ( '' )
print ( ' Number of problems = %d' % ( prob_num ) )
print ( '' )
print ( ' Index M N ||B|| ||X1 - X2||' ),
print ( ' ||X1|| ||X2|| ||R1|| ||R2||' )
print ( '' )
for prob in range ( 1, prob_num + 1 ):
#
# Get problem size.
#
m = p00_m ( prob )
n = p00_n ( prob )
#
# Retrieve problem data.
#
a = p00_a ( prob, m, n )
b = p00_b ( prob, m )
x1 = p00_x ( prob, n )
b_norm = r8vec_norm ( m, b )
x1_norm = r8vec_norm ( n, x1 )
r1 = np.dot ( a, x1 ) - b
r1_norm = r8vec_norm ( m, r1 )
#
# Use SVD_SOLVE on the problem.
# Since we want to compute residuals ourselves, we need
# to keep the originals of A and B, so we make copies
# to send to SVD_SOLVE.
#
a_qr = a.copy ( )
b_qr = b.copy ( )
x2 = svd_solve ( m, n, a_qr, b_qr )
x2_norm = r8vec_norm ( n, x2 )
r2 = np.dot ( a, x2 ) - b
r2_norm = r8vec_norm ( m, r2 )
#
# Compare tabulated and computed solutions.
#
x_diff_norm = r8vec_norm ( n, x1 - x2 )
#
# Report results for this problem.
#
print ( ' %5d %4d %4d' % ( prob, m, n ) ),
print ( ' %12.4g %12.4g' % ( b_norm, x_diff_norm ) ),
print ( ' %12.4g %12.4g' % ( x1_norm, x2_norm ) ),
print ( ' %12.4g %12.4g' % ( r1_norm, r2_norm ) )
#
# Terminate.
#
print ( '' )
print ( 'SVD_SOLVE_TEST' )
print ( ' Normal end of execution.' )
return
if ( __name__ == '__main__' ):
from timestamp import timestamp
timestamp ( )
svd_solve_test ( )
timestamp ( )