1611688890-f641c9ec8276824e4686da772eb56520 (826652), страница 82
Текст из файла (страница 82)
Наконец, если решение x системы уравнений предполагается принадлежащим брусу x,мы можем взять интервальное расширение по x ∈ x правой части полученного включения, придя к соотношениюx ∈ x̃ − ΛF (x̃) + (I − ΛS)(x − x̃),Определение 4.7.4 Пусть определены некоторые правила, сопоставляющие всякому брусу x ∈ IRn точку x̃ ∈ x и вещественную n × nматрицу Λ и пусть также S ∈ IRn×n — интервальная матрицанаклонов отображения F : Rn ⊇ D → Rn на D.
ОтображениеK : ID × R → IRn ,задаваемое выражениемK(x, x̃) := x̃ − ΛF (x̃) + (I − ΛS)(x − x̃),называется оператором Кравчика на ID относительно точки x̃.5044. Решение нелинейных уравнений и их системТеорема 4.7.2 Пусть F : Rn ⊇ D → Rn — непрерывное по Липшицуотображение, S — его интервальная матрица наклонов и x̃ ∈ x ⊆ ID.Тогда(i) каждое решение системы F (x) = 0 на брусе x лежит также вK(x, x̃);(ii) если x ∩ K(x, x̃) = ∅, то в x нет решений системы F (x) = 0;(iii) если K(x, x̃) ⊆ x, то в x находится хотя бы одно решение системы F (x) = 0;(iv) если x̃ ∈ int x и ∅ 6= K(x, x̃) ⊆ int x, то матрица S сильнонеособенна и в K(x, x̃) содержится в точности одно решениесистемы F (x) = 0.Оператор Кравчика — это не что иное, как центрированная формаинтервального расширения отображения Φ(x) = x − ΛF (x), возникающего в правой части системы уравнений после её приведения к рекуррентному видуx = Φ(x).4.8Глобальное решение уравненийи систем уравненийЕсли ширина бруса X велика, то на нём описанные в предшествующем параграфе методики уточнения решения могут оказаться малоуспешными в том смысле, что мы получим включение (4.23), из которого нельзя вывести никакого определённого заключения ни о существовании решения на брусе X, ни о его отсутствии.
Кроме того, самэтот брус, как область потенциально содержащая решение, нискольконе будет уточнён (уменьшен).Тогда практикуют принудительное дробление X на более мелкиеподбрусы. Наиболее популярна при этом бисекция — разбиение бруса X на две (равные или неравные) части вдоль какой-нибудь грани,например, на половинкиX ′ = X 1 , . . . , [ X ι , mid X ι ], . . . , X n ,X ′′ = X 1 , . . . , [ mid X ι , X ι ], . . .
, X n5054.8. Глобальное решение уравнений и системXX ′′X ′′X′X′Рис. 4.11. Принудительное дробление бруса.для некоторого номера ι ∈ {1, 2, . . . , n}. При этом подбрусы X ′ и X ′′ называются потомками бруса X. Далее эти потомки можно разбить ещёраз, и ещё . . . — столько, сколько необходимо для достижения желаемой малости их размеров, при которой мы сможем успешно выполнятьна этих брусах рассмотренные выше тесты существования решений.Если мы не хотим упустить при этом ни одного решения системы, тодолжны хранить все возникающие в процессе такого дробления подбрусы, относительно которых тестом существования не доказано строго,что они не содержат решений. Организуем поэтому рабочий список Lиз всех потомков начального бруса X, подозрительных на содержание решений.
Хотя мы называем эту структуру данных «списком», всмысле программной реализации это может быть не обязательно список, а любое хранилище брусов, организованное, к примеру, как стек(магазин) или куча и т. п. (см. [4]) В целом же алгоритм глобальногодоказательного решения системы уравнений организуем в виде повторяющейся последовательности следующих действий:• извлечение некоторого бруса из списка L,• дробление этого бруса на потомки,• проверка существования решений в каждом5064.
Решение нелинейных уравнений и их системиз подбрусов-потомков, по результатам которой мы− либо выдаём этот подбрус в качестве ответак решаемой задаче,− либо заносим его в рабочий список Lдля последующей обработки,− либо исключаем из дальнейшего рассмотрения,как не содержащий решений рассматриваемой системы.Кроме того, чтобы обеспечить ограниченность времени работы алгоритма, на практике имеет смысл задаться некоторым порогом мелкости (малости размеров) брусов δ, при достижении которого дальшедробить брус уже не имеет смысла. В Табл. 4.2 приведён псевдокодполучающегося алгоритма, который называется методом ветвленийи отсечений: ветвления соответствуют разбиениям исходного бруса наподбрусы (фактически, разбиениям исходной задачи на подзадачи), аотсечения — это отбрасывание бесперспективных подбрусов исходнойобласти поиска.2Отметим, что неизбежные ограничения на вычислительные ресурсы ЭВМ могут воспрепятствовать решению этим алгоритмом задачи(4.19) «до конца», поскольку могут возникнуть ситуации, когда1) размеры обрабатываемого бруса уже меньше δ, нонам ещё не удаётся ни доказать существование в нёмрешений, ни показать их отсутствие;2) размеры обрабатываемого бруса всё ещё больше δ, новычислительные ресурсы уже не позволяют производитьего обработку дальше: исчерпались выделенное время,память и т.
п.В реальных вычислениях остановка алгоритма Табл. 4.2 может происходить поэтому не только при достижении пустого рабочего списка L(когда исчерпана вся область поиска решений), но и, к примеру, придостижении определённого числа шагов или времени счёта и т. п. Тогдавсе брусы, оставшиеся в рабочем списке L, оказываются не до конца2 Стандартный английский термин для обозначения подобного типа алгоритмов— «branch-and-prune».
С ними тесно связаны методы ветвей и границ, широкоприменяемые в вычислительной оптимизации.4.8. Глобальное решение уравнений и системТаблица 4.2. Интервальный метод ветвлений и отсеченийдля глобального доказательного решения уравненийВходСистема уравнений F (x) = 0. Брус X ∈ IRn .Интервальное расширение F : IX → IRn функции F .Заданная точность δ > 0 локализации решений системы.ВыходСписок НавернякаРешения из брусов размера менее δ, которыегарантированно содержат решения системы уравнений в X.Список ВозможноРешения из брусов размера менее δ, которыемогут содержать решения системы уравнений в X.Список Недообработанные из брусов размера более δ, которыемогут содержать решения системы уравнений в X.Алгоритминициализируем рабочий список L исходным брусом X ;DO WHILE ( L 6= ∅ ) и ( не исчерпаны ресурсы ЭВМ )извлекаем из рабочего списка L брус Y ;применяем к Y тест существования решения,его результат обозначаем также через Y ;IF ( в Y доказано отсутствие решений ) THENудаляем брус Y из рассмотренияELSEIF ( (размер бруса Y ) < δ ) THENзаносим Y в соответствующий из списковНавернякаРешения или ВозможноРешенияELSEрассекаем Y на потомки Y ′ и Y ′′и заносим их в рабочий список LEND IFEND IFEND DOвсе брусы из L перемещаем в список Недообработанные;5075084.
Решение нелинейных уравнений и их системобработанными, и мы условимся так и называть их — «недообработанные». Итак, в общем случае результатом работы нашего алгоритмадолжны быть три списка брусов:список НавернякаРешения, состоящий из брусов ширинойменьше δ, которые гарантированно содержат решения,список ВозможноРешения, состоящий из брусов ширинойменьше δ, подозрительных на содержание решения, исписок Недообработанные, состоящий брусов, которыеалгоритму не удалось обработать «до конца» и которыеимеют ширину не меньше δ.При этом все решения рассматриваемой системы уравнений, не принадлежащие брусам из списка НавернякаРешения, содержатся в брусахиз списков ВозможноРешения и Недообработанные.Практика эксплуатации интервальных методов для доказательного глобального решения уравнений и систем уравнений выявила рядпроблем и трудностей. Во многих случаях (особенно при наличии такназываемых кратных корней) задачу не удаётся решить до конца ипредъявить все гарантированные решения уравнения.
Список брусовответов с неопределённым статусом (ВозможноРешения в псевдокодеТабл. 4.2) часто никак не собираются исчезать ни при увеличении точности вычислений, ни при выделении дополнительного времени счета ит.п. Нередко он разрастается до огромных размеров, хотя большинствообразующих его брусов возможных решений являются «фантомами»немногих реальных решений. Но эти феномены могут быть успешнообъяснены на основе теории, изложенной в §4.3.Решения уравнений и систем уравнений — это особые точки соответствующих векторных полей, которые, как мы могли видеть, отличаются большим разнообразием.
Насколько используемые нами при доказательном решении систем уравнений инструменты приспособленыдля выявления особых точек различных типов? Нетрудно понять, чтоинтервальный метод Ньютона, методы Кравчика и Хансена-Сенгупты,тесты существования Мура и Куи, основывающиеся на теоремах ЛерэШаудера и Брауэра и наиболее часто используемые при практическихдоказательных вычислениях решений уравнений, охватывают толькослучаи индекса ±1 особой точки F .
Если же решение системы является критической точкой соответствующего отображения с индексом, неЛитература к главе 4509равным ±1, то доказать его существование с помощью вышеупомянутых результатов принципиально не получится. Это объясняет, почемумногие существующие практические интервальные алгоритмы для доказательного глобального решения систем уравнений не могут достичь«полного успеха» в общем случае.Помимо вышеназванной причины необходимо отметить, что список ВозможноРешения может соответствовать неустойчивым решениямсистемы уравнений, имеющим нулевой индекс. Эти решения разрушаются при сколь угодно малых возмущениях уравнений и потому немогут быть идентифицированы никаким приближенным вычислительным алгоритмом с конечной точностью представления данных.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
