Статистические методы криптоанализа. Методы решения систем нелинейных уравнений

Существует много различных методов решения нелинейных уравнений, некоторые из них представлены ниже:

1) Метод итераций. При решении нелинейного уравнения методом итераций воспользуемся записью уравнения в виде x=f(x). Задаются начальное значение аргумента x0 и точность е. Первое приближение решения x1 находим из выражения x1=f(x0), второе - x2=f(x1) и т.д. В общем случае i+1 приближение найдем по формуле xi+1 =f(xi). Указанную процедуру повторяем пока |f(xi)|>е. Условие сходимости метода итераций |f'(x)|<1.

2) Метод Ньютона. При решении нелинейного уравнения методом Ньтона задаются начальное значение аргумента x0 и точность е. Затем в точке(x0,F(x0)) проводим касательную к графику F(x) и определяем точку пересечения касательной с осью абсцисс x1. В точке (x1,F(x1)) снова строим касательную, находим следующее приближение искомого решения x2 и т.д. Указанную процедуру повторяем пока |F(xi)| > е. Для определения точки пересечения (i+1) касательной с осью абсцисс воспользуемся следующей формулой xi+1=xi-F(xi)\ F'(xi). Условие сходимости метода касательных F(x0)•F''(x)>0, и др.

3). Метод дихотомии. Методика решения сводится к постепенному делению начального интервала неопределённости пополам по формуле Ск=ак+вк/2.

Для того чтобы выбрать из двух получившихся отрезков необходимый, надо находить значение функции на концах получившихся отрезков и рассматривать тот на котором функция будет менять свой знак, то есть должно выполняться условие f (ак)* f (вк)<0.

Процесс деления отрезка проводится до тех пор, пока длина текущего интервала неопределённости не будет меньше заданной точности, то есть

вк - ак < E. Тогда в качестве приближенного решения уравнения будет точка, соответствующая середине интервала неопределённости.

4). Метод хорд. Идея метода состоит в том, что на отрезке [a,b] строится хорда стягивающая концы дуги графика функции y=f(x), а точка c, пересечения хорды с осью абсцисс, считается приближенным значением корня

c = a - (f(a)Ч (a-b)) / (f(a) - f(b)),

c = b - (f(b)Ч (a-b)) / (f(a) - f(b)).

Следующее приближение ищется на интервале [a,c] или [c,b] в зависимости от знаков значений функции в точках a,b,c

x* О [c,b], если f(с)Ч f(а) > 0;

x* О [a,c], если f(c)Ч f(b) < 0.

Если f'(x) не меняет знак на [a,b], то обозначая c=x1 и считая начальным приближением a или b получим итерационные формулы метода хорд с закрепленной правой или левой точкой.

x0=a, xi+1 = xi - f(xi)(b-xi) / (f(b)-f(xi), при f '(x)Ч f "(x) > 0;

x0=b, xi+1 = xi - f(xi)(xi-a) / (f(xi)-f(a), при f '(x)Ч f "(x) < 0.

Сходимость метода хорд линейная.