Лекция 11. Нелинейные функциональные уравнения. Метод Ньютона – Контаровича

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

Средства управления криптографическими ключами

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

Различают следующие виды функций управления ключами:

- генерация,

- хранение,

- и распределение ключей.

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

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

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

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

Такой подход приводит к концепции иерархии ключей.

В иерархию ключей входит:

- главный ключ (т.е. мастер-ключ),

- ключ шифрования ключей

- и ключ шифрования данных.

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

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

Между пользователями сети ключи распределяют двумя способами:

- с помощью прямого обмена сеансовыми ключами;

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

Метод Ньютона – Контаровича является одним из немногих методов нахождения решения нелинейного функционального уравнения. Приведены алгоритмы итерационного процесса Ньютона – Контаровича и доказаны две теоремы о существований и единственности решения уравнения. Рассмотрены еще два принципа существования неподвижной точки: теорема Брауэра и принцип Шаудера.

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

Рассмотрим нелинейное функциональное уравнение вида

. (1)

Предположим, что в имеется решение уравнения (1) т.е. . Пусть в оператор непрерывно дифференцируем по Фреше. Полагаем, что в оператор непрерывно обратим. Алгоритм итерационного процесса следующий: 1) выбирается начальная точка ; 2) вычислим производной Фреше оператора в точке . В результате, находим оператор ; 3) следующее приближение . В общем случае

. (2)

Сходимость итерационного процесса Ньютона – Канторовича. Рассмотрим решение операторного уравнения (1) путем построения последовательности по формуле (2).

Теорема 1. Пусть оператор дифференцируем по Фреше в шаре , оператор удовлетворяет условию Липшица

. (3)

Пусть оператор , непрерывно обратим, причем

. (4)

Пусть , величина и выполнено неравенство . Тогда уравнение (1) имеет решение , при , скорость сходимости последовательность к определяется по формуле

. (5)

Доказательство. Пусть последовательность определяется по формуле (2). Покажем, что . Докажем методом математической индукции. Поскольку , то . Тогда . Следовательно, . Так как , то . Тогда и согласно формуле (4) из леммы (10), имеем

.

Итак, включение верно для значений .

Полагаем, что включение верно для значений , причем

. (6)

Докажем, что

. (7)

Из (4), (6) имеем

Отсюда следует первое неравенство из (7). Так как , то . Тогда

.

Следовательно, верно второе неравенство из (7). Доказано, что .

Покажем, что последовательность фундаментальна. Как следует из формулы (7), верна оценка

(8)

Тогда при для любого конечного . Следовательно, последовательность – фундаментальна, а в силу того, что – банахово пространство, последовательность сходится. Пусть при . Так как , то .

Покажем, что – решение уравнения . Поскольку , то при имеем . Отсюда имеем .

Из оценки (8) при фиксированном и при , получим

теорема доказана.

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

Модифицированный метод Ньютона – Канторовича. Метод построения последовательности по формуле (2) требует вычисления обратного оператора на каждой итерации. Рассмотрим следующую модификацию метода Ньютона – Канторовича

(9)

Отличие (9) от (2) состоит в том, что обратный оператор определяется только в начальной точке .

Теорема 2. Пусть выполнены следующие условия:

1) оператор дифференцируем по Фреше в шаре и

;

2) существует обратный оператор , причем ;

3) .

Тогда уравнение имеет единственное решение , при . Справедлива следующая оценка скорости сходимости

.

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

Отсюда, используя лемму 5 из лекции 10 (см. формулу (4)), имеем

где . Так как, , то . Следовательно, . Поскольку , то . Тогда , оператор отображает в себя.

Докажем, что оператор является сжимающим в . Как следует из теоремы 6 лекции 10 (см. следствие 3), норма

следовательно, , оператор является сжимающим.

Таким образом, оператор удовлетворяет условиям теоремы 6 лекции 5 и верны утверждения 1) – 3). Из утверждения 1) следует, что оператор имеет единственную неподвижную точку т.е . Так как , то . Следовательно, является решением уравнения . Поскольку , то при . Далее, величина , то верна оценка

Теорема доказана.

Теорема Брауэра. Отметим, что: 1) пусть – некоторое множество в банаховом пространстве , состоящее из конечного числа элементов т.е. , множество называется выпуклой оболочкой множества и обозначается ; 2) выпуклым телом в банаховом пространстве называется выпуклое замкнутое множество, имеющее хоть одну внутреннюю точку.

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

Пример 1. Пусть – непрерывная функция, отображающая в себя т.е . Покажем, что имеет неподвижную точку в т.е . В самом деле, функция , обладает свойствами , . Заметим, что: 1) если или , то или ; 2) если , то . Согласно теореме о промежуточных значениях непрерывной функции найдется точка такая, что . Тогда , где – выпуклое ограниченное тело в .

Принцип неподвижной точки Шаудера. Обобщением теоремы Брауэра является принцип неподвижной точки Шаудера. Теорема Брауэра не пригодна для решения многих задач функционального анализа из-за конечномерности множества .

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

Отметим, что: 1) если – непрерывный оператор, – конечномерные банаховы пространства, то вполне непрерывный оператор; 2) если – банаховы пространства, – ограниченный непрерывный оператор, – линейный вполне непрерывный оператор, то – вполне непрерывный оператор; 3) оператор . Пусть оператор непрерывен в ограниченном множестве , множество компактно, где – образ множества . Из компактности , согласно критерию Хаусдорфа, следует, что существует для любого конечная – сеть множества , где – замыкания множества .

Определим оператор следующим образом

.

где , если ; , если . Оператор называется – проектором Шаудера. Можно показать, что оператор , непрерывен.

Покажем, что . Так как

,

то

,

в силу того, что , . Отсюда следует, что оператор аппроксимирует оператор на с точностью .

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

Теорема 4. (принцип Шаудера). Пусть – замкнутое ограниченное выпуклое множество банахова пространства , оператор отображает в себя и является вполне непрерывным на . Тогда оператор имеет неподвижную точку на .

Доказательство. Предположим противное т.е. оператор не имеет неподвижную точку на . Тогда существует число такое, что . Так как оператор вполне непрерывен, то множество – компактно.

Отметим, что если не выполнено неравенство , то оператор имеет неподвижную точку на . В самом деле, существует последовательность такая, что при , где . Так как множество – компактно, то из можно выделить последовательность . Тогда , в силу того, что при . Следовательно, , что противоречит предположению оператор не имеет неподвижную точку на .

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

Обозначим через . Множество , является выпуклым телом, , в силу того, что .

Пусть – –проектор Шаудера. Рассмотрим сужение оператора на множество т.е. , . Для оператора , применим теорема Брауэра. Согласно теореме Брауэра, оператор имеет неподвижную точку т.е. . Тогда . Так как оператор является аппроксимацией оператора , то . Итак, имеем . Это противоречит неравенству , , где . Следовательно, предположение о том, что не имеет неподвижную точку на не верно. Теорема доказана.

Дата добавления: 2014-01-07