% Gausselimination mit "Verhaeltnispivotsuche"
%
% Dies ist eine Pivotierungsstrategie, die das Problem der Zeilen-
% oder Vollpivotsuche bei der Vandermondematrix vermeidet.  Allerdings
% hat diese Strategie den gleichen Rechenaufwand wie die
% Vollpivotsuche, ist aber generisch weniger gut (allerdings besser
% als die einfache (aber schnellere) Zeilenpivotsuche).

function x = gauss_verhaeltnispivot(A,b)
  
M = [A b];
n = length(b);
min_ratio = ones(n,1);

% Vorwaertselimination:
for j=1:n-1
  % Bestimme die Pivotzeile
  for k=j:n
    min_ratio(k) = abs(M(k,j)) / sum(abs(M(k,j+1:n+1)));
  end
  [pivot,p] = max(min_ratio(j:n));
  p = p+j-1; % Index der Pivotzeile
  % Vertausche j-te Zeile mit der Pivotzeile
  x      = M(j,:);
  M(j,:) = M(p,:);
  M(p,:) = x;
  % Jetzt weiter wie bisher...
  for k=j+1:n
    M(k,:) = M(k,:) - (M(k,j)/M(j,j)) * M(j,:);
  end
end

% Rueckwaerts einsetzen:
x = [zeros(n,1); -1];
for j=0:n-1
  x(n-j) = -M(n-j,:)*x / M(n-j,n-j);
end
x(n+1) = [];
