1611688890-f641c9ec8276824e4686da772eb56520 (826652), страница 81
Текст из файла (страница 81)
Так как любой нуль функции f (x) на Xлежит также в N(X, x̃), то разумно взять в качестве следующего болееточного интервала локализации решения пересечениеX ∩ N(X, x̃),которое окажется, по крайней мере, не хуже X. Эта ситуация иллюстрируется на Рис. 4.9, где обозначено X ′ = N(X, x̃). Далее, положивX (0) = X, естественно организовать итерационное уточнениеk = 0, 1, 2, . . . ,(4.26)X (k+1) ← X (k) ∩ N X (k) , x̃(k) ,4974.7. Интервальные методы решения уравненийxx′x̃x′xy = f (x)Рис. 4.9. Иллюстрация работы одномерногоинтервального метода Ньютона.с какими-то x̃(k) ∈ X (k) , которое называется интервальным методомНьютона. В благоприятном случае он порождает последовательностьинтервалов X (k) уменьшающейся ширины, которые содержат искомоерешение уравнения.
Критерием остановки итераций при этом можетбыть достижение требуемой точности локализации решения, т. е. ширины X (k) .Ещё одним вариантом развития итераций (4.26) является возникновение на каком-то шаге пустого пересечения X (k) ∩ N(X (k) , x̃). Посленего необходимо прекращать выполнение алгоритма, коль скоро арифметические операции с пустым множеством не определены. При этомпо самому построению интервального оператора Ньютона мы должнызаключить, что на X (k) , а значит и на исходном интервале X, решенийуравнения f (x) нет.Наконец, наименее благоприятным с точки зрения уточнения информации о решении является «застаивание» итераций интервальногометода Ньютона, когда на каком-то шаге получаем X (k) ⊆ N(X (k) , x̃),так чтоX (k+1) = X (k) ∩ N(X (k) , x̃) = X (k) .Ясно, что тогда и все последующие итерации метода будут равны X (k) ,и решение никак не уточнится.
Ниже в §4.8 мы обсудим, как преодолевать это затруднение.В случае, когда производная функции f , фигурирующей в левой4984. Решение нелинейных уравнений и их системчасти уравнения, на интервале X не зануляется и её оценка f ′ (X) несодержит нуля, интервальный метод Ньютона обладает рядом замечательных качеств. Если 0 6∈ f ′ (X) для некоторого X, то на следующемшаге метода будет исключена по крайней мере половина X. При этомасимптотический порядок сходимости метода к нулю функции f наинтервале X является квадратичным, т. е.
таким же, как у обычногонеинтервального метода Ньютона.Предложение 4.7.1 Пусть функция f непрерывно дифференцируемаи на интервале X имеет место f ′ (X) 6∋ 0. Если для некоторой точкиx̃ справедливо включение N(X, x̃) ⊆ X, то интервал X содержитрешение уравнения f (x) = 0.Доказательство. Помимо x̃ рассмотрим ещё точку y ∈ X. Согласнотеореме Лагранжа о среднем найдётся такая точка ξ ∈ {x̃, y} ⊂ X,чтоf (x̃) − f (y) = f ′ (ξ) (x̃ − y).(4.27)Чтобы подчеркнуть зависимость этой точки от x̃ и y, мы обозначимеёкак ξ(x̃, y).
Коль скоро f ′ (ξ) ∈ f ′ (X), то ясно, что f ′ ξ(x̃, y) 6= 0 прилюбых x̃ и y. По этой причине мы можем определить функциюg(y) = y −f (y).f ′ ξ(x̃, y)(4.28)По условиям Предложения функция g(y) непрерывна. Кроме того,из равенства (4.27) следуетx̃ −f (y)f (x̃) = y−,f ′ ξ(x̃, y)f ′ ξ(x̃, y)так что верно альтернативное представление функции g:g(y) = x̃ −f (x̃).f ′ ξ(x̃, y)Как следствие, после интервализации этого выражения по y ∈ X, получаемg(y) = x̃ −f (x̃)f (x̃) ∈ x̃ − ′= N(X, x̃) ⊆ X.f (X)f ′ ξ(x̃, y)4994.7. Интервальные методы решения уравненийТак как это включение справедливо для любого y ∈ X, то получается,что непрерывное отображение g переводит интервал X в себя.
Следовательно, в силу теоремы Брауэра о неподвижной точке, существуеттакое y ⋆ ∈ X, что g(y ⋆ ) = y ⋆ . Из (4.28) тогда вытекает, что f (y ⋆ ) = 0,т. е. y ⋆ является решением уравнения f (x) = 0.y = f (x)xx′xx̃x′x′′x′′Рис. 4.10. Иллюстрация работы одномерногоинтервального метода Ньютона. Случайнульсодержащего интервала производной.Рассмотрим теперь случай 0 ∈ f ′ (X).
Он встречается, когда на интервале X имеется кратный корень x⋆ , в котором f ′ (x⋆ ) = 0, либокогда интервал X настолько широк, что содержит более одного корня.В этом случае мы также можем придать смысл интервальному оператору Ньютона, воспользовавшись для выполнения деления f (x̃)/f ′ (X)специальной интервальной арифметикой — так называемой интервальной арифметикой Кахана, допускающей деление на нульсодержащиеинтервалы.
В действительности, эта модификация даже усилит интервальный метод Ньютона, так как мы получим возможность отделять различные решения друг от друга: в результате выполнения шагаинтервального метода Ньютона при 0 ∈ int f ′ (X) часто получаются два непересекающися интервала. Эта ситуация иллюстрируется наРис. 4.10.В арифметике Кахана дополнительно определено деление интервалов a и b c 0 ∈ b, которое и приводит к бесконечным интервалам.Для удобства мы выпишем соответствующие результаты в развёрнутой5004. Решение нелинейных уравнений и их системформе:a/b ==[ a,[ b,a]b]a · [ 1/b, 1/b ],если 0 6∈ b,] − ∞, + ∞ [ ,если 0 ∈ a и 0 ∈ b,[ a/b, + ∞ [ ,если a < 0 и b < b = 0,] − ∞, a/b] ∪ [ a/b, + ∞ [ , если a < 0 и b < 0 < b,] − ∞, a/b ],] − ∞, a/b ],] − ∞, a/b ] ∪ [a/b, + ∞ [ ,[ a/b, + ∞ [ ,∅,если a < 0 и 0 = b < b,если 0 < a и b < b = 0,если 0 < a и b < 0 < b,если 0 < a и 0 = b < b,если 0 6∈ a и 0 = b.(4.29)В заключение — необходимый комментарий о реализации интервального метода Ньютона на ЭВМ.
Значение f (x̃), несмотря на точечность аргумента x̃, для достижения доказательности вычисленийследует находить с помощью машинной интервальной арифметики свнешним направленным округлением. Иначе возможны потеря решений и другие нежелательные феномены.4.7вМногомерный интервальныйметод НьютонаПереходя к решению систем нелинейных уравнений, следует отметить, что многомерные версии интервального метода Ньютона гораздоболее многочисленны, чем одномерные, и отличаются очень большимразнообразием. В многомерном случае мы можем варьировать не только выбор точки x̃, вокруг которой осуществляется разложение, формуинтервального расширения производных или наклонов функции, какэто было в одномерном случае, но также и способ внешнего оцениваниямножества решений интервальной линейной системы, к которой приводится оценивание бруса решения.
В оставшейся части этого параграфа5014.7. Интервальные методы решения уравнениймы рассмотрим простейшую форму многомерного интервального метода Ньютона, а его более специальным версиям, которые связываются сименами Кравчика и Хансена-Сенгупты, будут посвящены отдельныепараграфы.Определение 4.7.2 [46] Для отображения F : Rn ⊇ D0 → Rmматрица A ∈ IRm×n называется интервальной матрицей наклоновна D ⊆ D0 , если для любых x, y ∈ D равенствоF (y) − F (x) = A(y − x)имеет место с некоторой вещественной m × n-матрицей A ∈ A.Предположим, что на брусе x к решению предъявлена система нелинейных уравненийF (x) = 0.(4.30)Если S — интервальная матрица наклонов отображения F на x, то длялюбых точек x, x̃ ∈ x справедливо представлениеF (x) ∈ F (x̃) + S(x − x̃).В частности, если x — решение системы уравнений (4.30), т.
е. F (x) = 0,то0 ∈ F (x̃) + S(x − x̃).(4.31)Вспомним характеризацию Бека для объединённого множества решений ИСЛАУ (Теорема 4.6.1): получается, что точка x удовлетворяетвключению (4.31) тогда и только тогда, когда она принадлежит объединённому множеству решений интервальной линейной системыS(x − x̃) = −F (x̃).(4.32)Далее, если Encl — процедура внешнего оценивания множества решений ИСЛАУ, то справедливо включениеx − x̃ ∈ Encl (S, −F (x̃)),так чтоx ∈ x̃ + Encl (S, −F (x̃)).5024. Решение нелинейных уравнений и их системОпределение 4.7.3 Пусть для внешнего оценивания множеств решений ИСЛАУ зафиксирована процедура Encl, а для отображения F :Rn ⊇ D → Rn известна интервальная матрица наклонов S ∈ IRn×n .ОтображениеN : ID × Rn → IRn ,задаваемое правиломN(x, x̃) = x̃ + Encl (S, −F (x̃)),называется интервальным оператором Ньютона на ID относительноточки x̃.Как лучше выбирать центр разложения x̃? Имеет смысл делатьэто так, чтобы величина kF (x̃)k была, по-возможности, меньшей.
Чемменьше будет норма вектор-функции F (x̃), тем меньшим будет норма векторов, образующих множество решений интервальной линейнойсистемыS(x − x̃) = −F (x̃),которое мы должны пересекать с исходным брусом. Может быть, мыполучим при этом более узкую внешнюю оценку множества решенийисходной нелинейной системы и более точно определим статус исследуемого бруса.
Численные эксперименты как будто подтверждают этотвывод.Процедуру для уточнения центра разложения можно организоватькак метод типа Ньютона, коль скоро нам известна интервальная матрица наклонов.Наиболее неблагоприятной ситуацией при работе интервального метода Ньютона является, конечно, появление включенияN(x, x̃) ⊇ x.Тогда все последующие шаги зацикливаются на брусе x и не дают никакой дополнительной информации об искомых решениях системы. Какпоступать в этом случае? Ответ на этот вопрос рассматривается в следующем §4.8.4.7гМетод КравчикаПусть на брусе x ∈ IRn задана система n нелинейных уравнений cn неизвестнымиF (x) = 0,5034.7. Интервальные методы решения уравненийдля которой требуется уточнить двусторонние границы решений.
Возьмём какую-нибудь точку x̃ ∈ x и организуем относительно неё разложение функции F :F (x) ∈ F (x̃) + S(x − x̃),где S ∈ Rn×n — интервальная матрица наклонов отображения F набрусе x. Если x — это точка решения системы, то0 ∈ F (x̃) + S(x − x̃).(4.31)Но далее, в отличие от интервального метода Ньютона, мы не будемпереходить к рассмотрению интервальной линейной системы (4.32), адомножим обе части этого включения слева на точечную n×n-матрицу,которую нам будет удобно обозначить как (−Λ):0 ∈ −ΛF (x̃) − ΛS(x − x̃).Добавление к обеим частям получившегося соотношения по (x − x̃)приводит кx − x̃ ∈ −ΛF (x̃) − ΛS(x − x̃) + (x − x̃),что равносильноx ∈ x̃ − ΛF (x̃) + (I − ΛS)(x − x̃),так как для неинтервального общего множителя (x − x̃) можно воспользоваться дистрибутивным соотношением (1.17).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
