We often have to price the American Option with Linear Complementarity Formulation when using finite difference method. One of methods for solving linear complementarity problem is Projected Successive Over Relaxation (PSOR), which is iterative and tries to solve the following formulation:                  
               x'(Ax - b) = 0                                        
                       x >= 0                                        
                  Ax - b >= 0                                        
using the projected SOR algorithm. Here is a sample Matlab code showing the basic algorithem of PSOR,
function [x] = psor(A,b,x0)
omega = 1.5;
tol = 1e-9;
jmax = 1e+3;

n = length(b); x = x0; j = 1;
for i = 1:n
x(i) = max(0,x(i)+omega*(b(i)-A(i,:)*x)/A(i,i));
end

while (norm(x-x0) > tol) && (j < jmax)
j = j + 1; x0 = x;
for i = 1:n
x(i) = max(0,x(i)+omega*(b(i)-A(i,:)*x)/A(i,i));
end
end
return

A problem with this sample code is slow computation speed, Should you are happy with C++, the following C++ code which can be called directly in Matlab.  



wiki(Linear complementarity problem)
Unclear about this post? Asking questions and receiving answers.