#! /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 ( )