Алгоритм Сергеева. Остановимся на решении системы линейных алгебраических уравнений с целыми коэффициентами

Ax=2b,

и четными коэффициентами правой части (масштабированием к этому случаю сводятся приводимые системы). На каждом шаге итерации уменьшается невязка

xi=xi-1+δxi, ei=ei-1+Aδxi,

где δxi=-sign(diag(A)ei-1), x0=0, e0=-2b, знаковая функция sign(0)=1.

Алгоритм гарантированно сходится за m шагов к точному решению, где m - отвечает максимальному элементу вектора x. Решение Ax=b отличается вдвое, что в машинной арифметике соответствует поразрядному сдвигу битов числа вправо.

Пример 1. Нечетная правая часть удваивается на старте


A=[4 1; 1 -2], b=[8 -7], 

D={A}, diag(D), 
x=zero(b), e={-2*b}, n=norm(e), 
gx={x}, ge=n, k=0,

while n>0, dx={D.*e}, 
for i=0:size(x), if dx[i]<0, 
dx[i]=1, else, dx[i]=-1, end, end,
x={x+dx}, e={{e+A*dx}}, n=norm(e), 
gx={[gx x]}, ge={[ge n]},  
k++, if k>50, n=0, end,
end,

tr(gx), gx={[gx ge]},
t=line(ge), plot(t gx), x={x/2}, x=?

На рисунке представлен график падения невязки и характер перехода значений итерируемого вектора к удвоенным значениям решения [1 4] за 8 шагов.

Пример 2. Пример четвертого порядка более показателен


A=[-13 2 -1 3; -6 19 4 5; -1 -5 -37 7; -5 -9 8 23], 
b=[-61 -217 233 520], 

D={A}, diag(D), 
x=zero(b), e={-2*b}, n=norm(e), 
gx={x}, ge=n, k=0,

while n>0, dx={D.*e}, 
for i=0:size(x), if dx[i]<0, 
dx[i]=1, else, dx[i]=-1, end, end,
x={x+dx}, e={{e+A*dx}}, n=norm(e), 
gx={[gx x]}, ge={[ge n]},  
k++, if k>50, n=0, end,
end,

tr(gx), % gx={[gx ge]},
t=line(ge), plot(t gx), x={x/2}, x=?

На график выводятся только итерации искомого вектора решения, ведущие за 38 шагов к удвоенным значениям [7 -14 -1 19].

Пример 3. Изменим первый коэффициент матрицы A, исключив тем самым возможность получения целочисленного решения.


A=[-12 2 -1 3; -6 19 4 5; -1 -5 -37 7; -5 -9 8 23], 
b=[-61 -217 233 520], 

D={A}, diag(D), 
x=zero(b), e={-2*b}, n=norm(e), 
gx={x}, ge=n, k=0,

while n>0, dx={D.*e}, 
for i=0:size(x), if dx[i]<0, 
dx[i]=1, else, dx[i]=-1, end, end,
x={x+dx}, e={{e+A*dx}}, n=norm(e), 
gx={[gx x]}, ge={[ge n]},  
k++, if k>100, n=0, end,
end,

tr(gx), % gx={[gx ge]},
t=line(ge), plot(t gx), x={x/2}, x=?

Итерационный процесс не завершается нулевой невязкой, что не мешает ему финально флуктуировать в окрестности некоторого приближенного решения.

Идеология разрядных методов вычислений строится на предположении их эффективной аппаратной реализации на микропроцессорах. Монотонное гарантированное снижение нормы невязки позволяет не вводить ограничения на результаты целочисленных операций.

1. Сергеев М.Б. Гибридный разрядный метод решения систем уравнений в целочисленной арифметике. Журнал Информационно-управляющие системы. N 2-3, c. 16-18. 2003 г.



Rambler's Top100