!======================================================================= ! ch08_sor.f90 ! ! Solve a system of linear equations A*x = b by successive ! over-relaxation (SOR). ! ! Origin: ! Based on GS_sor.f90 by Alexander Godunov, November 2009. ! The sequential SOR update is retained. Comments, input checks, ! convergence reporting, and the residual test have been revised ! for the Chapter 8 companion website. ! ! Example: ! A = [ 8 2 4; 2 6 1; 1 1 8 ], b = [ 2, 6, 4 ]. ! Exact solution: x = [ -0.2, 1, 0.4 ]. ! ! The program reports the iteration count and the final maximum ! residual |A*x-b|. Change omega and the initial guess to see how ! they affect convergence. SOR does not converge for every matrix ! or every choice of omega. !======================================================================= program ch08_sor implicit none integer, parameter :: n = 3, max_iter = 100 double precision :: a(n,n), b(n), x(n), omega, eps, residual integer :: i, j, iterations, info ! Each implied-DO fills one row of A. data (a(1,j),j=1,n) / 8.0d0, 2.0d0, 4.0d0 / data (a(2,j),j=1,n) / 2.0d0, 6.0d0, 1.0d0 / data (a(3,j),j=1,n) / 1.0d0, 1.0d0, 8.0d0 / data (b(i),i=1,n) / 2.0d0, 6.0d0, 4.0d0 / ! Initial estimate, relaxation parameter, and residual tolerance. x = 0.0d0 omega = 1.2d0 eps = 1.0d-8 write (*,'(a)') 'Successive over-relaxation (SOR)' write (*,'(/,a)') 'Matrix A and right-hand side b:' do i = 1,n write (*,'(3f12.5,3x,f12.5)') (a(i,j),j=1,n), b(i) end do write (*,'(/,a,3f12.6)') 'Initial guess x:',x write (*,'(a,f8.4)') 'Relaxation parameter omega = ',omega write (*,'(a,es12.4)') 'Residual tolerance = ',eps call sor(a,b,x,n,omega,eps,max_iter,iterations,residual,info) if (info == 1) then write (*,'(/,a)') 'Invalid input: check omega, tolerance, and diagonal entries.' stop 1 end if write (*,'(/,a,i0)') 'Iterations = ',iterations write (*,'(a)') 'Solution x:' do i = 1,n write (*,'(a,i0,a,f12.6)') 'x(',i,') = ',x(i) end do write (*,'(a,es12.4)') 'Maximum residual |A*x-b| = ',residual if (info == 2) then write (*,'(a)') 'Iteration limit reached before the tolerance was met.' stop 1 end if contains subroutine sor(a,b,x,n,omega,eps,max_iter,iterations,residual,info) !======================================================================= ! Solve A*x = b by sequential successive over-relaxation sweeps. ! ! Input: ! a(n,n) - coefficient matrix, left unchanged ! b(n) - right-hand side, left unchanged ! x(n) - initial guess, overwritten by the final estimate ! n - number of equations (n >= 1) ! omega - relaxation parameter, 0 < omega < 2 ! eps - requested maximum absolute residual (positive) ! max_iter - maximum number of complete sweeps (positive) ! ! Output: ! iterations - number of complete sweeps performed ! residual - max_i |sum_j a(i,j)*x(j) - b(i)| ! info - 0 if residual <= eps; 1 for invalid input; ! 2 if max_iter was reached without convergence ! ! Method: ! For row i, compute the mismatch delta = b(i) - sum_j a(i,j)*x(j). ! Entries x(j) with j < i have already been updated in this sweep; ! entries with j > i still have their values from the last sweep. ! The update x(i) = x(i) + omega*delta/a(i,i) is the original ! GS_sor.f90 SOR step. At omega = 1 it is Gauss-Seidel. ! ! A full residual is computed after the sweep. The original routine ! tested mismatches while the individual rows were being updated; ! that quantity was not the residual of a single completed iterate. ! A small absolute residual alone may be misleading when the scale ! of A or b changes or when A is poorly conditioned. !======================================================================= implicit none integer, intent(in) :: n, max_iter double precision, intent(in) :: a(n,n), b(n), omega, eps double precision, intent(inout) :: x(n) integer, intent(out) :: iterations, info double precision, intent(out) :: residual double precision :: delta, off_diagonal integer :: i, j, k iterations = 0 residual = huge(1.0d0) info = 1 ! A zero diagonal makes the update undefined. Diagonal dominance is ! useful to check, but is not imposed as a requirement for SOR. if (n < 1 .or. max_iter < 1 .or. eps <= 0.0d0) return if (omega <= 0.0d0 .or. omega >= 2.0d0) return do i = 1,n if (a(i,i) == 0.0d0) return end do do i = 1,n off_diagonal = 0.0d0 do j = 1,n if (j /= i) off_diagonal = off_diagonal + abs(a(i,j)) end do if (abs(a(i,i)) <= off_diagonal) then write (*,'(a)') 'Warning: A is not strictly diagonally dominant.' exit end if end do ! First check the supplied guess, which may already be a solution. call maximum_residual(a,b,x,n,residual) if (residual <= eps) then info = 0 return end if ! Sweep through the rows. Updating x(i) immediately is essential: ! later rows use the newly computed values from the same sweep. do k = 1,max_iter do i = 1,n delta = b(i) do j = 1,n delta = delta - a(i,j)*x(j) end do x(i) = x(i) + omega*delta/a(i,i) end do iterations = k call maximum_residual(a,b,x,n,residual) if (residual <= eps) then info = 0 return end if end do info = 2 end subroutine sor subroutine maximum_residual(a,b,x,n,residual) !----------------------------------------------------------------------- ! Evaluate the residual of the completed iterate using the original ! system. Explicit loops keep the code independent of matrix libraries. !----------------------------------------------------------------------- implicit none integer, intent(in) :: n double precision, intent(in) :: a(n,n), b(n), x(n) double precision, intent(out) :: residual double precision :: row_sum integer :: i, j residual = 0.0d0 do i = 1,n row_sum = -b(i) do j = 1,n row_sum = row_sum + a(i,j)*x(j) end do residual = max(residual,abs(row_sum)) end do end subroutine maximum_residual end program ch08_sor