95616

ОСНОВНЫЕ ЧИСЛЕННЫЕ МЕТОДЫ, ПРИМЕНЯЕМЫЕ В ЭЛЕКТРОТЕХНИЧЕСКИХ ЗАДАЧАХ

Лекция

Математика и математический анализ

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

Русский

2015-09-25

729.85 KB

3 чел.

22

Лекции

«ОСНОВНЫЕ ЧИСЛЕННЫЕ МЕТОДЫ,

ПРИМЕНЯЕМЫЕ В ЭЛЕКТРОТЕХНИЧЕСКИХ ЗАДАЧАХ»

(Часть II: Решение СНАУ)

Новочеркасск 2012


СОДЕРЖАНИЕ

СОДЕРЖАНИЕ 3

2. ПОНЯТИЕ УРАВНЕНИЯ 4

2.1. ЧИСЛЕННОЕ РЕШЕНИЕ НЕЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ И ТРАНЦЕНДЕНТНЫХ УРАВНЕНИЙ 4

2.1.1. Метод перебора 4

2.1.2. Метод дихотомии (половинного деления) 5

2.1.3. Метод отделения корней 6

2.1.4. Метод хорд 8

2.1.5. Метод касательных 9

(метод Ньютона, метод линеаризованной итерации) 9

2.1.6. Метод секущих 12

(комбинированный метод секущих – хорд, метод хорд - касательных) 12

2.1.7. Метод простых итераций 13

2.2. ЧИСЛЕННЫЕ МЕТОДЫ РЕШЕНИЯ СИСТЕМ НЕЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ (СНАУ) 15

2.2.1. Метод последовательных приближений (простых итераций) для СНАУ 16

2.2.2. Метод Ньютона для СНАУ 17

2.2.2.1. Вариант 1 18

2.2.2.2. Вариант 2 18

2.2.2.3. Меры предосторожности  в методе Ньютона 20

2.2.2.4. Локальное решение нелинейного уравнения 20

2.2.3. Метод Ньютона по параметру 21

2.2.4. Метод Бройдена 21

2.2.5. Метод Матвеева 22

ЛИТЕРАТУРА 23

ЗАДАНИЯ и ПРИМЕРЫ ВЫПОЛНЕНИЯ 24


2. ПОНЯТИЕ УРАВНЕНИЯ

Уравнением с одним неизвестным называется равенство двух функций от одной и той же переменной величины, верное лишь при некоторых определённых значениях этой переменной.

Уравнение называется алгебраическим, если каждая из входящих в него функции и является алгебраической (рациональной или иррациональной). Одна из этих функций может быть постоянной величиной.

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

,

где коэффициенты предполагаются действительными.

 Иррациональными называются уравнения, которое содержит неизвестное под знаком радикала.

 Линейным называется уравнение вида .

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

Уравнение называется трансцендентным, если хотя бы одна из функций не является алгебраической.

Примеры:

 Решением нелинейных (в частности, трансцендентных) уравнений вида заключается в отыскании одного или всех корней на отрезке изменения . Обычно стараются локализовать каждый корень в своём отрезке . Тогда нахождение всех корней сводится к локализации каждого корня с последующим сужением отрезков локализации корня одним из описанных далее методов.

2.1. ЧИСЛЕННОЕ РЕШЕНИЕ НЕЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ И ТРАНЦЕНДЕНТНЫХ УРАВНЕНИЙ

2.1.1. Метод перебора

При решении нелинейного уравнения методом перебора задаются начальное значение аргумента и шаг , который при этом определяет и точность нахождения корней нелинейного уравнения. Пока выполняется условие ,  аргумент увеличивается на шаг . Если произведение становится отрицательным, то на интервале существует решение уравнения. Алгоритм метода изображен на блок-схеме ниже.

НАЧАЛО

a, h

x=a

F(x),  F (x+h)

F(x)F (x+h)>0

x=x+h

КОНЕЦ

x

Рис. 1.

2.1.2. Метод дихотомии (половинного деления)

Пусть задана непрерывная функция и требуется найти все или некоторые корни уравнения.

.

Для этого метода существенно, чтобы функция была непрерывна и ограничена в заданном интервале внутри которого ищется корень. Предполагается также, что и   имеют разные знаки.

Пусть найдены такие точки , что , т. е. на отрезке  лежит не менее одного корня уравнения. Найдем середину отрезка и вычислим . Из двух половин отрезка выберем ту, для которой, ибо один из корней лежит на этой половине. Затем новый отрезок опять делим пополам и выберем ту половину, на концах которой функция имеет разные знаки, и т. д. (рис. 2).

Если требуется найти корень с точностью ,то продолжаем деление пополам до тех пор, пока длина отрезка не станет меньше. Тогда середина последнего отрезка даст значение корня с требуемой точностью.

a

b

x1

x2

y

x

Рис. 2.

Метод дихотомии (деления пополам) на отрезке реализуется следующим алгоритмом (для ) :

  1.  Вычислить  и .
  2.  Если и имеют разные знаки (), то
  3.  Находим .
  4.  Вычисляем .
  5.  Если и имеют разные знаки (), то установить  и перейти к п. 3.
  6.  Если и имеют разные знаки (), то установить и перейти к п. 3.
  7.  Проверяем условие ,  если оно выполняется, идем к п.1, если оно не выполняется, заканчиваем вычисления и считаем что с заданной точностью .
  8.  Проверяем также условие, по которому количество итераций превышает или не превышает заданную величину.

Число итераций при использовании этого метода:   значительно, и поэтому  его сходимость медленная, однако при любой ширине отрезка сходимость гарантирована. Кроме того, простота реализации метода уменьшает число вспомогательных операций и частично компенсирует увеличение общего времени счета из-за медленной сходимости.

2.1.3. Метод отделения корней

Один из недостатков метода дихотомии – сходимость неизвестному  корню (имеется почти у всех итерационных методов). Его можно устранить отделением уже найденного корня.

Если есть простой корень уравнения и - непрерывна, то вспомогательная функция    непрерывна, причем все нули функции и совпадают, за исключением , ибо . Если– кратный корень уравнения , то он будет нулем кратности на единицу меньше; остальные нули обеих функций по-прежнему будут одинаковы.

Вот почему найденный корень можно отделить, т. е. перейти к другой функции .  Тогда нахождение остальных нулей функции сведется к нахождению нулей функции . Когда мы найдем какой-нибудь корень   функции , то этот корень тоже можно отделить, вводя новую вспомогательную функцию  . Так можно последовательно найти все корни .

Строго говоря, находится лишь приближенное значение корня .  А функция имеет нуль в точке и полюс в близкой к ней точке (рис. 3).  Только на некотором расстоянии от этого корня она близка к . Чтобы это не сказывалось при нахождении следующих корней, надо вычислить каждый корень с высокой точностью, особенно если он кратный или вблизи него расположен другой корень уравнения.

Рис 3.

 Отделение корней. Корень ξ уравнения считается отделённым на отрезке [a,b] , если на этом отрезке уравнение не имеет других корней.

 Отделить корни – значит, разбить всю область допустимых значений на отрезки, в каждом из которых содержится один корень.

Произведем отделение корней аналитическим способом.

Аналитический метод отделения корней.

  1.  Найти – первую производную.
  2.  Составить таблицу знаков функции ,полагая равным.

      а) критическим значениям (корням) производной  или ближайшим к ним;

      б) граничными значениями (исходя из области допустимых значений неизвестного).

  1.  Определить интервалы, на концах  которых функция принимает значения противоположных знаков. Внутри этих интервалов содержится по одному и только по одному корню.

2.1.4. Метод хорд 

При этом методе каждое значение находится как точка пересечения оси абсцисс с хордой, проведенной через точки и , причем одна из этих точек фиксируется та, для которой знаки и   одинаковы. Если неподвижен конец хорды , то

,

а если неподвижен конец хорды, то

  .

Если , то в первом случае считаем , во втором и повторяем вычисления. При использовании метода хорд предполагается, что корень находится на отрезке.

y

x

X411

X311

X211

a

b

X111

y

 Рис 4. Решение уравнения методом хорд

Алгоритм.

  1.  Провести прямую, соединяющую точки и . Вычисляем значение функции в точках и .
  2.  Эта прямая пересекает ось в точке :
  3.  Если   и   имеют разные знаки , то положить и перейти  к п. 5.
  4.  Если   и  имеют разные знаки , то положить и перейти  к п. 5.
  5.  Если условие остановки не удовлетворяется, то перейти к п. 1.
  6.  Условия остановки могут быть такими:

-     ( задаётся),

-  интервал ( задаётся),

-  количество итераций превысило заданную величину.

2.1.5. Метод касательных 

(метод Ньютона, метод линеаризованной итерации) 

Метод линеаризованной итерации, именуемый также метом Ньютона, состоит в том, что исходное уравнение заменяется последовательностью линеаризованных уравнений

каждое из которых следующее (улучшенное) приближение получается с учётом предыдущего результата

.                                

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

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

Для сходимости процесса линеаризованных итераций достаточно, чтобы:

  1.  на отрезке , содержащем единственный корень уравнения, функция имела непрерывные производные и ;
  2.  эти производные не обращались в нуль на отрезке ;
  3.  при выбранном начальном приближении выполнялось условие .

Сходимость данного метода оценивается порядком , где - погрешность приближенного значения .

a

X0=b

F

x

F(x)

Рис. 5. Решение уравнения методом Ньютона (касательных).

В некоторых случаях метод линеаризованных итераций применяется в модифицированном виде. Первая модификация заключается в том, что на каждом шаге вычислений вместо берётся постоянная величина . В этом случае формула принимает вид

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

В общем случае модифицированный итерационный процесс сходится медленнее и для него ещё большее значение имеет близость начального приближения к истинному значению корня.

Вторая модификация состоит в замене исходного уравнения уравнением

в котором подбирается так, чтобы равенство было тождественным. Корень ищется как предел последовательных приближений

;

Данная итерационная формула не обеспечивает сходимости в случае, если исходное уравнение имеет двукратный корень или два очень близких корня. В этом случае более точные значения корней могут быть найдены из уравнения

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

Основные достоинства метода – простота вычислительной схемы, хорошая сходимость и возможность вычисления корня с высокой точностью. Его рекомендуется применять в тех случаях, когда известно хорошее начальное приближение и требуется найти корень с высокой точностью. Особенно удобен этот метод при решении трансцендентных уравнений и нахождении комплексного корня. Перед использованием итерационной формулы необходимо поверить выполнение условий сходимости исследовать поведение первой производной и второй производной в окрестности корня. Если при этом окажется, что производная изменяется медленно, то вместо данной формулы целесообразно использовать формулу , которая существенно сокращает объём вычислений. При определении двух близких корней вычисления рекомендуется строить по формуле Если искомый корень комплексный, то в качестве начального приближения должно быть взято комплексное число.

На практике не всегда удается определить  заранее кратность корня или существование двух близких корней. Поэтому оправдывает себя комбинированный способ, при котором вычисления ведутся по нескольким формулам.  Алгоритм, реализующий такой способ нахождения корней, может быть следующим:

  1.  Вычисления по формуле при фиксированном значении (начиная с );
  2.  Проверка выполнения условия . Если условие выполнено, то задача считается решенной и управление передается оператору п.7. При невыполнении указанного условия и выполнение  передается следующему оператору п. 3;
  3.  Проверка того, достигло ли число итераций установленного предела . Если , то управление передается оператору п. 1, при выполняется следующий оператор  п. 4;
  4.  Вычисление следующих приближений по формуле и проверка достигнутой точности вычислений. Если корень вычислен с нужной точностью, то задача считается решенной и управление может быть передано оператору п. 7. Но в окрестности  этого корня имеется ещё кратный корень (или два близких корня), который может быть найден с помощью оператора п. 5. Если же нужная точность ещё не достигнута, то это, возможно, свидетельствует о том, что искомый корень является кратным или близко расположенным с другим корнем. Данное предположение проверяется с помощью оператора п. 5;
  5.  Вычисление следующих приближений по формуле и проверка достигнутой точности вычислений. Если нужная степень точности достигнута, то выполняется следующий оператор п. 6. При получении нужной точности задача считается решенной (при этом получаются два близких корня) и управление передается оператору п. 7;
  6.  Получение следующих приближений по формуле (метод хорд) ( или иному методу. Если и после этого нужная степень точности не достигается, то в окрестности искомого корня имеется более двух близких корней и для их получения следует воспользоваться другим методом;
  7.  Конец вычислений.

Метод Ньютона имеет квадратичную скорость сходимости.

Пример.

program Newt;

{Дана функция f(x)= tg(ax)-bx-c; a, b, c;

Решить методом Ньютона уравнение f(x)=0,c точостью до Epsi=0.0001, x0=0.01}

{Если X0 есть начальное приближение значения корня уравнения f(x)=0, то в

качестве более точного приближения берется X1= X0-f(X0)/f'(X0). Заменой X0

на X1 может быть получно следующее приближение и т. д. Процесс последовате-

льных приближений всегда сходится, если только корень Xn не кратный (т.е.

f'(Xn) <> 0) и первое придлижение взято достаточно близко}

Uses CRT;

Var

R : Integer;

x1, x0, a, b, c, Epsi, Fu, F, E : Real;

Begin

{Головная программа}

TextBackGround(Black);{Меняет цвет фона на черный, модуль Crt}

ClrScr;{Очищает экран, модуль Crt}

TextColor(LightRed);{Меняет цвет символов на светло-красный, модуль Crt}

WriteLn ('   Работает программа Newt');

TextColor(Yellow);{Меняет цвет символов на желтый, модуль Crt}

WriteLn   ('  Введите численные значения: a, b, c, Epsi, x0:');

 ReadLn(a,b,c,Epsi,x0);

 R:= 0;  {Флажок. Если R=0, то Cos(a*x0) <> 0.0

                 Если R=1, то Cos(a*x0) = 0.0}

x1:= x0;{Начальное приближение}

 Repeat

If (Cos(a*x0) <> 0.0) then

   begin

        F:= Sin(a*x0)/Cos(a*x0) - b*x0 - c; {Значение функции}

        Fu:= a/(Cos(a*x0)*Cos(a*x0)) - b;   {Значение производной}

        x1:= x0 - F/Fu; {Новое, уточненное приближение корня}

        WriteLn(x0,x1);

        E:= Abs(x1-x0); {Погрешность вычисления корня}

        x0:=x1;

   end

                       else

   begin

        WriteLn(' ОШИБКА! Cos(a*x0) = 0.0 ');

        x0:= x1;

        E:= Abs(x1-x0);

        R:= 1;

   end;

Until (E < Epsi);

If (R  =  0) then

   begin

        TextColor(LightRed);{Меняет цвет символов на светло-красный, модуль Crt}

        WriteLn ('   **************** РЕЗУЛЬТАТ ****************');

        TextColor(LightGreen);{Меняет цвет символов на светло-зеленый, модуль Crt}

        WriteLn(x1);

   end;

TextColor(LightGray);{Меняет цвет символов на светло-серый, модуль Crt}

WriteLn ('   ДЛЯ ПРОДОЛЖЕНИЯ НАЖМИТЕ ЛЮБУЮ КЛАВИШУ!!!');

Repeat Until KeyPressed; {Ожидает нажатия любой клавиши, модуль Crt}

                         {Используется для задержки информации на экране}

ClrScr;{Очищает экран, модуль Crt}

{Ответ:x1}

End.{Newt}

2.1.6. Метод секущих

(комбинированный метод секущих – хорд, метод хорд - касательных)

В методе секущих линейная аппроксимация функции строится с использованием двух предыдущих итераций и . Метод основан на уточнении приближённого значения корня с помощью линейной интерполяции. При этом на каждом шаге за приближённое значение корня принимается корень интерполяционного многочлена первой степени, построенного по значениям функции в точках и .

Вычисления строятся по итерационной формуле

.

Это и есть формула метода секущих.

Геометрический смысл такого изменения алгоритма Ньютона в том, что от аппроксимации функции касательной мы переходим к секущей (рис. 6).

F

x

X0

X1

X2

X3

X4

Рис. 6. Метод секущих.

Заметим, что формула метода секущих соответствует формуле метода Ньютона, в которой используется аппроксимация

.

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

Для того, чтобы начать итерационный процесс, необходимо задать два начальных приближения x 0 и x 1. Затем каждое новое приближение к корню получаем по формуле . Заканчиваем процесс уточнения корня при выполнении условия x k+1 - x k 

где – заданная абсолютная погрешность определения корня.

Метод секущих уступает методу Ньютона в скорости сходимости, однако не требует вычисления производной левой части уравнения.

По алгоритму метод секущих близок к методу хорд, однако в отличии от последнего, начальные приближения в методе секущих могут располагаться как с разных сторон от корня, так и с одной стороны; кроме того, при уточнения корня не проверяются знаки функции .

Метод секущих сходится сверхлинейно со скоростью .

Метод секущих может не сходится, во многом по тем же самым причинам, что и метод Ньютона. Например, при метод просто неопределён.  Однако, многие проблема можно обойти, если включить в алгоритм предупредительные меры.

2.1.7. Метод простых итераций

Существует  простой метод, позволяющий решить уравнение . Рассматриваемое уравнение представляют в виде и находят более точное значение корня по первому приближению с помощью формулы .

Повторяя этот процесс («итерируя») несколько раз, можно получить значения корня с любой степенью точности, если на интервале между корнем уравнения и первым приближением . Если это условие выполняется, то считается, что решение сходится к искомому корню.  

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

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

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

  1.  Остановка, как только .
  2.  Остановка, как только число итераций достигнет N.

Величины задаются.

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

  1.  Вычисление ()-го приближения по формуле при фиксированном значении (начиная с );
  2.  Вычисление ()-го приближения по той же формуле;
  3.  Проверка достигнутой точности вычислений . Если искомый корень вычислен с нужной степенью точности, то задача считается решенной и управление передаётся оператору п. 5, при недостаточной точности вычислений выполняется оператор п. 4;
  4.  Вычисление ()-го приближения по формуле Эйткена

;

  1.  Окончание вычислений искомого корня.

Пример 1.

PROGRAM Me_Pro_It;

{Решение нелинейных и транцендентных уравнений методом

простых итераций}

{Рассматриваемое уравнение представляется в виде x=f(x). Задают

начальное приближение X0 и уточняют с помощью формулы X1=f(X0).

Повторяют процесс до тех пор, пока не будет достигнута заданная

точность Epsi}

Uses CRT;

Type

   Func = Function(a,b,c,X:Real):Real;

Const

    a=5.67;

    b=4.794;

    c=4.5;

    Epsi=0.001;

Var

    I        : Integer;

    X0, X, Y : Real;

{$F+}

Function F(a,b,c,X:Real):Real;

{Преобразованная к виду x=f(x) заданная функция}

Begin

F:= a/c*SIN(b*X);

End; {F}

{$F-}

Procedure Iter(a,b,c,Epsi,X0:Real;var X, Y : Real; var I : Integer; F:Func);

Var E:Real;

Begin

X:= X0; {Начальное приближение}

I:=0;   {Параметр, позволяющий определить число итераций}

Repeat

     I:=I+1;

     Y:= F(a,b,c,X);

     WriteLn ('   Кол. итер.', I:7, '   X= ',X:5:3,'   Y= ',Y:5:3);

     E:=ABS(Y-X);

     X:=Y;

Until (E < Epsi);

End; {Iter}

BEGIN

{Головная программа}

TextBackGround(Black);{Меняет цвет фона на черный, модуль Crt}

ClrScr;{Очищает экран, модуль Crt}

HighVideo; {Устанавливает высокую яркость символов, модуль Crt}

TextColor(LightRed);{Меняет цвет символов на светло-красный, модуль Crt}

WriteLn ('   Работает программа Me_Pro_It');

TextColor(Yellow);{Меняет цвет символов на желтый, модуль Crt}

Write   ('   Введите начальное приближение корня   ');

ReadLn (X0);

Iter(a,b,c,Epsi,X0,X, Y,I,F);

TextColor(LightRed);{Меняет цвет символов на светло-красный, модуль Crt}

WriteLn ('   **************** РЕЗУЛЬТАТ ****************');

TextColor(LightGreen);{Меняет цвет символов на светло-зеленый, модуль Crt}

WriteLn ('   Кол. итер.', I:7, '   X= ',X:5:3,'   Y= ',Y:5:3);

NormVideo;{Устанавливает первоначальную яркость символов, модуль Crt}

TextColor(LightGray);{Меняет цвет символов на светло-серый, модуль Crt}

WriteLn ('   ДЛЯ ПРОДОЛЖЕНИЯ НАЖМИТЕ ЛЮБУЮ КЛАВИШУ!!!');

Repeat Until KeyPressed; {Ожидает нажатия любой клавиши, модуль Crt}

ClrScr;{Очищает экран, модуль Crt}

END.

2.2. ЧИСЛЕННЫЕ МЕТОДЫ РЕШЕНИЯ СИСТЕМ НЕЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ (СНАУ)

В подавляющем большинстве случаев математические модели реальных объектов содержат нелинейные функции, их отсутствие в математической модели говорит, как правило, о наличии упрощений.

Решение СНАУ является сложной задачей, необходимо глубокое знание, как физических свойств исследуемого объекта, так и особенностей СНАУ, используемых для его описания.

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

СНАУ будем представлять как равную нулю вектор-функцию размерности , элементами которого являются функции , ,  где - вектор искомого решения размерности . Например,

Вариант нелинейного метода наименьших квадратов не рассматривается.

При решении СНАУ, как правило, возникает проблема существования и единственности решения, выбора подходящего решения из множества решений, удовлетворяющих тождеству , если решение существует.

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

Говорят, что последовательность сходится к , если  

при .

Если существует константа и целое , такие, что для всех

,

то говорят, что последовательность  линейно сходится к  .

Если данное неравенство выполняется для некоторой последовательности , сходящейся к нулю, то говорят, что сходится сверхлинейно к .

Если сходится к  и существуют постоянные , такие, что для всех

,

то говорят, что сходится к  с порядком, по меньшей мере равным . При говорят о квадратичной скорости сходимости.

Итерационный метод, сходящийся с определенной скоростью к истинному решению при условии, что он стартует в достаточной близости от этого решения, называется локально сходящимся.

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

2.2.1. Метод последовательных приближений (простых итераций) для СНАУ

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

Алгоритм решения заключается в последовательном вычислении  


и начиная с некоторого начального приближения ,  пока:

  1.  будет выполнено условие , где - заданная точность расчета, т.е. получено некоторое решение;
  2.  зарегистрирован факт расхождения итерационного процесса;
  3.  превышено заданное предельное число итераций.

Для сходимости итерационного процесса достаточно, чтобы вблизи истинных значений корней выполнялись неравенства

.

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

Необходим глубокий анализ вида системы в каждом отдельном случае с точки зрения сходимости метода, возможности получения желаемого решения с требуемой точностью. Как правило, метод последовательных приближений является, в лучшем случае, линейно сходящимся.

В качестве вариантов метода последовательных приближений можно указать рассмотренные  методы простой и ускоренной (метод Зейделя) итерации, модифицированные с учетом нелинейности решаемой задачи.

 

2.2.2. Метод Ньютона для СНАУ 

Название метод Ньютона применяется к целому семейству методов, для которых собственно метод Ньютона служит базовым прототипом.

Рассмотрим простой пример.

Поскольку , где -начальное приближение, то

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

Расчетная формула для метода Ньютона может быть получена, если представить в окрестности текущего приближения в виде ряда Тейлора

,

и ограничиться линейными членами, тогда в матричной форме получим

,

где

Рис. 1. Итерация метода Ньютона для .

2.2.2.1. Вариант 1

Применительно к СНАУ получим следующий алгоритм:

1. Выбрать начальный вектор , положить

2. Вычислить вектор . Если все , где -  заданная точность расчета, то получено решение, расчет окончен. Если и , то итерационный процесс расходится, расчет завершить аварийно.

 3. Построить матрицу Якоби

 

и вычислить значения всех производных в точке .

4. Решить систему уравнений, определив вектор поправок 

 5. Вычислить новое приближение

и положить .

 6. Если , где -заданное предельное число итераций, то аварийно завершить расчет, иначе перейти к  п.2  алгоритма.

7. Конец алгоритма.

Метод Ньютона при начальном приближении близком к некоторому решению часто обладает устойчивой квадратичной сходимостью. При плохой начальной точке имеет место расходящийся итерационный процесс. Метод Ньютона расходится, если матрица Якоби плохо обусловлена в окрестности решения. Часто перед использованием метода Ньютона выполняют несколько итераций, например, методом последовательных приближений для того, чтобы иметь «хорошее» начальное приближение.

В качестве косвенного критерия расхождения итерационного процесса можно использовать изменение знака Якобиана  -  определителя матрицы Якоби. Однако это условие, являясь достаточным, не является необходимым. Якобиан может быть вычислен, как побочный продукт решения методом Гаусса системы из п.3 алгоритма.

2.2.2.2. Вариант 2

Алгоритм:

  1.  Задаём абсолютную или относительную погрешность , число уравнений , максимальное число итераций и вектор начальных приближений (с компонентами ).
  2.  Используя разложение в ряд Тейлора, формулируем матрицу Якоби , необходимую для расчёта приращений при малом изменении переменных. Матрица Якоби в развёрнутом виде записывается следующим образом:

Поскольку аналитическое дифференцирование в общем случае нежелательно, заменяем частные производные в матрице Якоби их приближенными конечно-разностными значениями

где - малое приращение , например .

  1.  Составляем и решаем систему линейных уравнений для малых приращений :   

Решение этой системы даёт , т. е. .

  1.  Вычисляем уточнённые значения

или в общем виде

  1.  Для всех проверяем одно из условий: по абсолютной и относительной погрешностям.

Если оно выполняется, идём к п. 2, т. е. выполняем новую итерацию. Иначе считаем вектор найденным решением.

 ПРИМЕР.

Испытаем метод Ньютона на примере

с . Матрица Якоби имеет вид

,

и уравнение Ньютона имеет вид

Использование гауссова исключения даёт , и поэтому новым приближением к решению будет . Решением же системы нелинейных уравнений является .

2.2.2.3. Меры предосторожности  в методе Ньютона

Меры предосторожности для метода Ньютона основаны на двух идеях. Во-первых, мы хотим иметь гарантию, что на каждой итерации происходит приближение к решению. Во-вторых, мы хотим предотвратить использование больших шагов, которые могут привести к катастрофе.

Мы хотим добиться выполнения условия

.

Напомним, что вторая (евклидова ) норма .

С целью предотвращения больших шагов наложим ограничение на шаг :

,

где - некоторый ограничитель, выбираемый алгоритмом. Ограничитель выбирает нашу степень доверия к модели . Если модель хорошая, то аппроксимация будет эффективной при больших значениях и можно выбирать большой ограничитель . Если модель плохая, то аппроксимация будет приемлемой лишь при малых значениях и нужно использовать малое значение . Множество называется доверительной областью.

Если ограничитель мал, то трудно надеяться, что решение уравнения Ньютона будет удовлетворять нашему ограничению. Необходим некоторый компромисс. Другими словами необходима задача оптимизации:

Минимизировать по норму при условии .

Опишем простейшую версию всего алгоритма в целом. На -й итерации выполняются следующие действия:

  1.  Если , то останов.
  2.  Вычислить шаг , решая приведённую выше задачу оптимизации с ограничением (Минимизировать по норму при условии ).
  3.  Если , то шаг принимается. Положить . Перейти к шагу 1.
  4.  Если шаг отвергается, то уменьшить ограничитель . Положить . Перейти к шагу 1.

Невозможно гарантировать, что  алгоритмы доверительной области будут сходиться к решению СНАУ. Для задач размерности больше единицы методы с гарантированной глобальной сходимостью всё ещё остаются предметом исследования. Эти проблема тесно связана с задачей глобальной оптимизации.

2.2.2.4. Локальное решение нелинейного уравнения

В качестве иллюстрации решения рассмотрим одномерную задачу

.

Решение нелинейного уравнения есть точка . Однако точка является его локальным решением. Чтобы убедиться в этом, заметим, что

.

В точке производные имеют вид

поэтому - локальный минимизатор . Но поскольку , точка не является решением нелинейного уравнения.

Чтобы  избежать нахождения только локальных решений, можно использовать более сложные стратегии. К ним относятся методы гомотопии.

2.2.3. Метод Ньютона по параметру

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

,

где   - (итерационный коэффициент) параметр, выбираемый на каждой итерации.

При метод совпадает с обычным методом Ньютона.

Параметр выбирают с целью ускорения сходимости и предупреждения расхождения метода. Факт расхождения может быть установлен, если невязка любого уравнения системы не уменьшилась по сравнению с предыдущей итерацией .

 2.2.4. Метод Бройдена

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

Вычислим значение и, выполнив предварительно шаг метода Ньютона, вычислим .  Если , то поиск на отрезке  [0,1]  начинается  с , в противном случае с . Зададимся некоторым и вычислим значения функции в точках в первом случае  и  в точках во втором случае, где Поиск прекращается при выполнении условия  

.

В окрестности -й точки производится квадратичная аппроксимация функции и определяется из условия ее минимума (равенства нулю производной) значение , равное

,

где - точки, в которых известно значение аппроксимируемой функции .

2.2.5. Метод Матвеева

Он предусматривает выбор оптимального параметра следующим образом:

Значение определяется, например, по следующей формуле:

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

Для метода Матвеева необходимо, чтобы функции были дважды дифференцируемыми по .

Метод Матвеева требует большего по сравнению с методом Ньютона объема вычислений и памяти, однако, обладает устойчивой сходимостью при не очень хороших исходных приближениях. Доказано, что данный метод сколь угодно приближается к решению, даже, если Якобиан стремится к нулю, т.е. матрица Якоби очень плохо обусловлена в окрестности решения.


ЛИТЕРАТУРА

  1.  Бахвалов Н. С. Численные методы/ Жидков Н. П. , Кобельков Г. М.; МГУ им М. В. Ломоносова. - М.: БИНОМ. Лаборатория знаний, 2006. - 636 с. - ISBN 5-94774-396-5: 372-20, н-1, ч/з-2, общ.8-1, уч-20(1- к ЭВМ); (24:25)
  2.  Киреев В. И. Численные методы в примерах и задачах/ Пантелеев А. В.; М.: Высш. шк., 2008. - 480 с. - ISBN 978-5-06-004763-9: 661-10.(уч-20); (20:25).
  3.  Мудров А. Е. Численные методы для ПЭВМ на языках Бейсик, Фортран и Паскаль/ Томск: МП"РАСКО", 1991. - 272 с. - ISBN 5-256-00602-9: 11р.20к. н-1; (1:25).
  4.  Калиткин Н. Н. Численные методы/ Под ред. А. А. Самарского. - М.: Наука, 1978. - 512 с. - 1 р. 30 к. КУКП-3, н-4, уч-99, ч/з-3. (110:25).


ЗАДАНИЯ и ПРИМЕРЫ ВЫПОЛНЕНИЯ

НАХОЖДЕНИЕ КОРНЯ НЕЛИНЕЙНОГО УРАВНЕНИЯ

1. Постановка задачи

Пусть задана функция , непрерывная вместе со своими несколькими производными. Требуется найти все или некоторые вещественные корни уравнения

. (1)

Данная задача распадается на несколько подзадач. Во-первых, необходимо определить количество корней, исследовать их характер и расположение. Во-вторых, найти приближенные значения корней. В-третьих, выбрать из них интересующие нас корни и вычислить их с требуемой точностью . Первая и вторая задачи решаются, как правило, аналитическими или графическими методами. В случае, когда ищутся только вещественные корни уравнения (1), полезно составить таблицу значений функции . Если в двух соседних узлах таблицы функция имеет разные знаки, то между этими узлами лежит нечетное число корней уравнения (по меньшей мере, один). Если эти узлы близки, то, скорее всего, корень между ними только один.

Найденные приближенные значения корней можно уточнить с помощью различных итерационных методов. Рассмотрим три метода: 1) метод дихотомиии (или деление отрезка пополам); 2) метод простой итерации и 3) метод Ньютона.


2. Методы решения задачи

2.1 Метод деления отpезка пополам

Наиболее простым методом, позволяющим найти корень нелинейного уравнения (1), является метод половинного деления.

Пусть на отрезке [a, b] задана непрерывная функция Если значения функции на концах отрезка имеют разные знаки, т.е. то это означает, что внутри данного отрезка находится нечетное число корней. Пусть для определенности корень один. Суть метода состоит в сокращении на каждой итерации вдвое длины отрезка. Находим середину отрезка [a,b] (см. рис. 1) Вычисляем значение функции и выбираем тот отрезок, на котором функция меняет свой знак. Новый отрезок вновь делим пополам. И этот процесс продолжаем до тех пор, пока длина отрезка не сравняется с наперед заданной погрешностью вычисления корня . Построение нескольких последовательных приближений по формуле (3) приведено на рисунке 1.

Итак, алгоритм метода дихотомии:

1. Задать отрезок [a,b] и погрешность .

2. Если f(a) и f(b) имеют одинаковые знаки, выдать сообщение о невозможности отыскания корня и остановиться.


Рис.1. Метод деления отрезка пополам для решения уравнения вида f(х)=0.

3. В противном случае вычислить c=(a+b)/2

4. Если f(a) и f(c) имеют разные знаки, положить b=c, в противном случае a=c.

5. Если длина нового отрезка , то вычислить значение корня c=(a+b)/2 и остановиться, в противном случае перейти к шагу 3.

Так как за N шагов длина отрезка [a, b] сокращается в 2N раз, то заданная погрешность отыскания корня  будет достигнута за итераций.

Как видно, скорость сходимости мала, но к достоинствам метода относятся простота и безусловная сходимость итерационного процесса. Если отрезок [a, b] содержит больше одного корня (но нечетное число), то всегда будет найден какой-нибудь один.

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

2.2 Метод простой итерации

При использовании этого метода исходное нелинейное уравнение (1) необходимо переписать в виде

 (2)

Обозначим корень этого уравнения C*. Пусть известно начальное приближение корня . Подставляя это значение в правую часть уравнения (2), получаем новое приближение

и т.д. Для (n+1)- шага получим следующее приближение

 (3)

Таким образом, по формуле (3) получаем последовательность С0, С1,…,Сn+1, которая стремиться к корню С* при n. Итерационный процесс прекращается, если результаты двух последовательных итераций близки, т. е. выполняется условие

 (4)


Исследуем условие и скорость сходимости числовой последовательности {C
n} при n. Напомним определение скорости сходимости. Последовательность {Cn}, сходящаяся к пределу С*, имеет скорость сходимости порядка , если при n выполняется условие

 (5)

Допустим, что имеет непрерывную производную, тогда погрешность на (n+1)-м итерационном шаге n+1=Cn+1-C*=g(Cn)-g(C*) можно представить в виде ряда

n+1 Cn+1 – C* = g(C*) (Cn-C*) + g(C*) n+

Таким образом, получаем, что при выполнении условия

g(C*)    (6)

последовательность (3) будет сходиться к корню с линейной скоростью . Условие (6) является условием сходимости метода простой итерации. Очевидно, что успех метода зависит от того, насколько удачно выбрана функция .

Например, для извлечения квадратного корня, т. е. решения уравнения вида x =a2, можно положить

x=g1(x)=a/x  ()

или


x=g2(x)=(x+a/x)/2.  ()

Нетрудно показать, что

g1(C)=1,

g2(C)<1.

Таким образом, первый процесс (7а) вообще не сходится, а второй (7б) сходится при любом начальном приближении С0 >0.

Рис. 2. Графическая интерпретация метода простых итераций для решения уравнения вида x=g(х).

Построение нескольких последовательных приближений по формуле (3)

С0, С1, …, Сn = C*

 приведено на рисунке 2.

2.3 Метод Ньютона

В литературе этот метод часто называют методом касательных, а также методом линеаризации. Выбираем начальное приближение С0. Допустим, что отклонение С0 от истинного значения корня С* мало, тогда, разлагая f(C*) в ряд Тейлора в точке С0 , получим

f(C*) = f(C0) + f (C0) (C*-C0) + (8)

Если f (C0)  0 , то в (8) можно ограничится линейными по C =C-C0 членами. Учитывая, что f(C*)=0, из (9) можно найти следующее приближение для корня

C1 = C0 f (C0) / f(C0)

или для (n+1)-го приближения

Cn+1= C n – f (C n) / f (C n)  (9)

Для окончания итерационного процесса можно использовать одно из двух условий

Cn+1 Cn  

или

f(Cn+1)  .

Исследование сходимости метода Ньютона проводится аналогично предыдущему случаю. Самостоятельно получить, что при выполнении условия

f (C)/2f(C)<1.

метод Ньютона имеет квадратичную скорость сходимости ().

Рис. 3. Графическая интерпретация метода Ньютона для решения уравнения вида f(х)=0.

Построение нескольких последовательных приближений по формуле (9)

С0, С1, …, Сn = C*

приведено на рисунке 3.

Задание

1. Для заданной функции f(x)

  1.  определите число вещественных корней уравнения f(x)=0, место их расположения и приближенные значения (постройте график или распечатайте таблицу значений).
  2.  Вычислите один из найденных корней (любой) с точностью =0,5*10-3.

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

Сравните полученные результаты.

Варианты заданий

1. x3 –3x2 +6x – 5 = 0     2. x 3 +sin x –12x-1=0

3. x3 –3x2 –14x – 8 = 0    4. 3x + cos x + 1 =0   

5. x2 +4sin x –1 = 0     6. 4x –ln x = 5

7. x6 –3x2 +x – 1 = 0      8. x3 – 0.1x2 +0.3x –0.6 = 0

9.    10. ( x -1)3 + 0.5ex = 0

11.   12. x5 –3x2 + 1 = 0

13. x3 –4x2 –10x –10 = 0   14.

15. 16.

17.   18.

19.   20.  

21. 22.

23.  24. x 4- 2.9x3 +0.1x2 + 5.8x - 4.2=0

25. x4+2.83x3- 4.5x2-64x-20=0 26.


МЕТОДЫ РЕШЕНИЯ СИСТЕМЫ НЕЛИНЕЙНЫХ УРАВНЕНИЙ

  1.  Постановка задачи

Пусть требуется решить систему n нелинейных уравнений:

 (1)

Прямых методов решения системы (1) не существует. Лишь в отдельных случаях эту систему можно решить непосредственно. Например, для случая двух уравнений иногда удаётся выразить одну неизвестную переменную через другую и таким образом свести задачу к решению одного нелинейного уравнения относительно одного неизвестного.

Систему уравнений (1) можно кратко записать в векторном виде:

.  (2)

Уравнение (2) может иметь один или несколько корней в области определения D. Требуется установить существование корней уравнения и найти приближённые значения этих корней. Для нахождения корней обычно применяют итерационные методы, в которых принципиальное значение имеет выбор начального приближения. Начальное приближение иногда известно из физических соображений. В случае двух неизвестных начальное приближение можно найти графически: построить на плоскости (x1, x2) кривые f1(x1, x2)=0 и f2(x1, x2)=0 и найти точки их пересечения. Для трех и более переменных (а также для комплексных корней) удовлетворительных способов подбора начального приближения нет.

Рассмотрим два основных итерационных метода решения системы уравнений (1), (2) - метод простой итерации и метод Ньютона.

2. Методы решения системы нелинейных уравнений

2.1.Метод простой итерации

Представим систему (1) в виде

 (3)

или в векторной форме:

 (4)

Алгоритм метода простой итерации состоит в следующем. Выберем некоторое нулевое приближение

 

Следующее приближение находим по формулам:

 


или более подробно:

 (5)

Итерационный процесс (5) продолжается до тех пор, пока изменения всех неизвестных в двух последовательных итерациях не станут малыми, т.е.

На практике часто вместо последнего условия используют неравенство:

 (6)

где - среднеквадратичная норма n-мерного вектора , т.е.

При использовании данного метода успех во многом определяется удачным выбором начального приближения : оно должно быть достаточно близким к истинному решению. В противном случае итерационный процесс может не сойтись. Если процесс сходится, то его скорость сходимости является линейной.

2.2. Метод Ньютона

В переводной литературе можно встретить название метод Ньютона-Рафсона. Этот метод обладает гораздо более быстрой сходимостью, чем метод простой итерации.

Пусть известно некоторое приближение к корню , так что

 

Тогда исходную систему (2) можно записать следующим образом:

Разлагая уравнение (7) в ряд Тейлора в окрестности точки и ограничиваясь линейными членами по отклонению , получим:

,

или в координатной форме:

 (8)

Систему (8) можно переписать в виде:


 (9)

Полученная система (9) является системой линейных алгебраических уравнений относительно приращений

.

Значение функций F1, F2, …, Fn и их производные в (9) вычисляются при

.

Определителем системы (9) является якобиан J:

 (10)

Для существования единственного решения системы уравнений (9) он должен быть отличен от нуля. Решив систему (9), например, методом Гаусса, найдём новое приближение:

.

Проверяем условие (6). Если оно не удовлетворяется, находим и якобиан (10) с новым приближением и опять решаем (9), таким образом, находим 2-е приближение и т.д.

 

Итерации прекращаются, как только выполнится условие (6).

Задание

Используя метод Ньютона, найдите решения системы нелинейных уравнений с заданной точностью . Исследуйте сходимость итерационного процесса.

Варианты заданий

1    2

3   4

5   6

7    8 

9   10

11    12 

13   14.

15.  16.

17.  18.

19.    20.  

21.     


 

А также другие работы, которые могут Вас заинтересовать

33628. Обобщенная модель системы безопасности сетей передачи данных 46.5 KB
  Обобщенная модель системы безопасности сетей передачи данных Рассматриваемая модель предполагает что функционирование системы безопасности происходит в среде которую можно представить кортежем 1.1 где {Пс} множество неуправляемых параметров внешней среды оказывающих влияние на функционирование сети; {Пу} множество внутренних параметров сети и системы безопасности которыми можно управлять непосредственно в процессе обработки защищаемых данных; {Пв} множество внутренних параметров сети не поддающихся...
33629. Мандатная модель 31 KB
  Модели механизмов обеспечения целостности данных Модель Биба Рассматриваемая модель основана на принципах которые сохраняют целостность данных путем предотвращения поступления данных с низким уровнем целостности к объектам с высоким уровнем целостности. Уровень целостности согласно. субъектам запрещено чтение данных из объекта с более низким уровнем целостности; нет записи наверх т. субъектам запрещено запись данных в объект с более высоким уровнем целостности.
33630. Модель Харрисона-Руззо-Ульмана (матричная модель) 32 KB
  Модель ХаррисонаРуззоУльмана матричная модель Модель матрицы права доступа предполагает что состояние разрешения определено используя матрицу соотносящую субъекты объекты и разрешения принадлежащие каждой теме на каждом объекте. Состояние разрешения описано тройкой Q = S О А где S множество субъектов 0 множество объектов А матрица права доступа. Вход s о содержит режимы доступа для которых субъект S разрешается на объекте о. Множество режимов доступа зависит от типа рассматриваемых объектов и функциональных...
33631. Многоуровневые модели 31.5 KB
  К режимам доступа относятся: чтение запись конкатенирование выполнение.7 где b текущее множество доступа. Это множество составлено из троек формы субъект объект режим доступа. Тройка s о т в b указывает что субъект s имеет текущий доступ к объекту о в режиме т; М матрица прав доступа аналогичная матрице прав доступа в модели ХаррисонаРуззоУльмана; f функция уровня которая связывается с каждым субъектом и объектом в системе как уровень их защиты.
33632. Графические модели 44 KB
  Графические модели сети Петри которые позволяют построить модели дискретных систем. Определение: Сеть Петри это набор N =STFWM0 где S непустое множество элементов сети называемое позициями T непустое множество элементов сети называемое переходами отношение инцидентности а W и M0 две функции называемые соответственно кратностью дуг и начальной разметкой. Если п 1 то в графическом представлении сети число n выписывается рядом с короткой чертой пересекающей дугу. Часто такая дуга будет также заменяться пучком из п...
33633. Построение модели систем защиты на базе Е-сетей на основе выделенного набора правил фильтрации 78 KB
  2 Переходы: d3 = XEâ€r3 p1 p2 p3 t3 установление соединения проверка пароля и имени пользователя для доступа к внутренней сети подсети; d4 = XEâ€r4 p2 p4 р5 0 подсчет попыток ввода пароля и имени; d5 = Tp4 p6 0 вывод сообщения о неверном вводе пароля и имени; d6 = Tp1 p6 0 – передача пакета для повторной аутентификации и идентификации; d7 = Tp5 p7 t4 создание соответствующей записи в журнале учета и регистрации. 3 Решающие позиции: r3 проверка пароля и имени пользователя; r4 ...
33634. RSA (буквенная аббревиатура от фамилий Rivest, Shamir и Adleman) 92.5 KB
  Алгоритм RS состоит из следующих пунктов: Выбрать простые числа p и q заданного размера например 512 битов каждое. Вычислить n = p q Вычисляется значение функции Эйлера от числа n: m = p 1 q 1 Выбрать число d взаимно простое с m Два целых числа называются взаимно простыми если они не имеют никаких общих делителей кроме 1. Выбрать число e так чтобы e d = 1 mod m Числа e и d являются ключами. Шифруемые данные необходимо разбить на блоки числа от 0 до n 1.
33635. IDEA (англ. International Data Encryption Algorithm, международный алгоритм шифрования данных) 121 KB
  Interntionl Dt Encryption lgorithm международный алгоритм шифрования данных симметричный блочный алгоритм шифрования данных запатентованный швейцарской фирмой scom. Известен тем что применялся в пакете программ шифрования PGP. Если такое разбиение невозможно используются различные режимы шифрования. Каждый исходный незашифрованный 64битный блок делится на четыре подблока по 16 бит каждый так как все алгебраические операции использующиеся в процессе шифрования совершаются над 16битными числами.
33636. Advanced Encryption Standard (AES) - Алгоритм Rijndael 317.5 KB
  dvnced Encryption Stndrd ES Алгоритм Rijndel Инициатива в разработке ES принадлежит национальному институту стандартов США NIST. Основная цель состояла в создании федерального стандарта США который бы описывал алгоритм шифрования используемый для защиты информации как в государственном так и в частном секторе. В результате длительного процесса оценки был выбрал алгоритм Rijndel в качестве алгоритма в стандарте ES. Алгоритм Rijndel представляет собой симметричный алгоритм блочного шифрования с переменной длиной блока и переменной...