1611688890-f641c9ec8276824e4686da772eb56520 (826652), страница 80
Текст из файла (страница 80)
На практикебывает вполне достаточно нахождения оценки для множества решений, т. е. приближенного описания, удовлетворяющего содержательному смыслу рассматриваемой задачи.Приведём полезный технический результат, который часто используется в связи с исследованием и оцениванием множества решений интервальных систем линейных алгебраических уравнений.4.6. Интервальные линейные системы уравнений491Теорема 4.6.1 (характеризация Бека) Если A ∈ IRm×n , b ∈ IRm ,тоΞ(A, b) = x ∈ Rn | Ax ∩ b 6= ∅= x ∈ Rn | 0 ∈ Ax − b .Доказательство. Если x̃ ∈ Ξ(A, b), то Ãx̃ = b̃ для некоторых Ã ∈ A,b̃ ∈ b. Следовательно, по крайней мере b̃ ∈ Ax̃ ∩ b, так что действительно Ax̃ ∩ b 6= ∅.Наоборот, если Ax̃ ∩ b 6= ∅, то это пересечение Ax̃ ∩ b содержитвектор b̃ ∈ Rm , для которого должно иметь место равенство b̃ = Ãx̃ снекоторой Ã ∈ A.
Итак, x̃ ∈ Ξ(A, b).Второе равенство следует из того, что Ax̃ ∩ b 6= ∅ тогда и толькотогда, когда 0 ∈ Ax̃ − b.Теорема 4.6.2 (характеризация Оеттли-Прагера) Для объединённогомножества решений ИСЛАУ имеет местоx ∈ Ξ(A, b) ⇔ (mid A) x − mid b ≤ rad A · |x| + rad b, (4.18)где неравенство между векторами понимается покомпонентным образом.Доказательство. Для любых интервальных векторов-брусов p и qвключение p ⊆ q равносильно покомпонентному неравенству| mid q − mid p | ≤ rad q − rad p.Следовательно, условие характеризации Бека, т. е.
0 ∈ Ax̃ − b, можетбыть переписано в следующем виде:| mid (Ax̃ − b) | ≤ rad (Ax̃ − b).С учётом правил преобразования середины и радиуса получаемmid (Ax̃ − b) = (mid A) x̃ − mid b,rad (Ax̃ − b) = (rad A) · |x̃| + rad b,откуда вытекает требуемое.4924.74. Решение нелинейных уравнений и их системИнтервальные методы решенияуравнений и систем уравненийИнтервальные методы позволяют придать конструктивный характер некоторым известным результатам математического анализа, которые раньше рассматривались как «чистые» теоремы существования.Самым первым из них являетсяТеорема 4.7.1 (теорема Брауэра о неподвижной точке) Пусть D —выпуклое компактное множество в Rn .
Если непрерывное отображение g : Rn → Rn переводит D в себя, g(D) ⊆ D, то оно имеет на Dнеподвижную точку x∗ , т. е. такую что x∗ = g( x∗ ).Если вместо произвольных выпуклых компактов ограничиться интервальными векторами-брусами в Rn , а для оценивания области значений применять его внешнюю оценку в виде интервального расширения, то условия теоремы Брауэра могут быть конструктивно проверенына компьютере.С учётом сказанного выше во введении к главе (стр. 455) о равносильности рекуррентного вида систем уравнений (4.4) каноническойформе (4.1)–(4.2) чрезвычайно полезными для вычислительной математики оказываются результаты анализа, утверждающие существование неподвижных точек отображений.
Теорема Брауэра является именно таким результатом.4.7аОсновы интервальной техникиЗадача решения уравнений и систем уравнений является одной изклассических задач вычислительной математики, для решения которой развито немало эффективных подходов — метод простой итерации,метод Ньютона, их модификации и т.п.
Преимущества и недостаткиэтих классических методов мы обсудили выше в §§4.4–4.5 (см. также[5, 27, 31, 42]). Для дальнейшего нам важны два факта:• Для уравнений, в которых фигурируют функции, не обладающие «хорошими» глобальными свойствами, все традиционные методы имеют локальный характер, т. е.
обеспечивают отысканиерешения, находящегося в некоторой (иногда достаточно малой)окрестности начального приближения. Задача нахождения всех4934.7. Интервальные методы решения уравненийрешений уравнения или системы уравнений, как правило, рассматривается лишь в специальных руководствах и методы её решения оказываются очень сложными.• Гарантированные оценки погрешности найденного приближенияк решению в традиционных методах дать весьма непросто.Указание приближённого значения величины и его максимальнойпогрешности равносильно тому, что мы знаем левую и правую границывозможных значений этой величины, и поэтому можно переформулировать нашу задачу в следующем усиленном виде —Для каждого решения системы уравненийF (x) = 0на данном множестве D ⊆ Rn найтигарантированные двусторонние границы,(4.19)— который будем называть задачей доказательного глобального решения системы уравнений.
Эпитет «доказательный» означает здесь, чтополучаемый нами ответ к задаче — границы решений и т.п. — имеетстатус математически строго доказанного утверждения о расположении решений при условии, что ЭВМ работает корректно (см. §1.9).Задача (4.19) оказывается чрезвычайно сложной, а в классическомчисленном анализе почти полностью отсутствуют развитые методы дляеё решения. Из часто используемых подходов, имеющих ограниченныйуспех, следует упомянуть аналитическое исследование, мультистарт,методы продолжения [27].Итак, пусть к решению предъявлена система уравнений (4.2)F (x) = 0на брусе X ⊂ Rn . Существование решения этой системы на X можнопереписать в виде равносильного условияran (F, X) ∋ 0,и потому техника интервального оценивания множеств значений функций оказывается весьма полезной при решении рассматриваемой задачи.
В частности, если нуль содержится во внутренней интервальной оценке множества значений ran (F, X) отображения F , то на брусе4944. Решение нелинейных уравнений и их системX гарантированно находится решение системы (4.2). С другой стороны, если в нашем распоряжении имеется интервальное расширение Fфункции F на X, то F (X) ⊇ ran (F, X). Поэтому если 0 6∈ F (X), тона X нет решений рассматриваемой системы уравнений.Далее, перепишем исходную систему (4.2) в равносильной рекуррентной формеx = T (x)(4.20)с некоторым отображением T : Rn → Rn .
Оно может быть взято, кпримеру, в видеT (x) = x − F (x)либоT (x) = x − ΛF (x),с неособенной n × n-матрицей Λ, либо как-нибудь ещё. Пусть такжеT : IRn → IRn — интервальное расширение отображения T . Ясно, чторешения системы (4.20) могут лежать лишь в пересечении X ∩ T (X).Поэтому еслиX ∩ T (X) = ∅,то в X нет решений системы уравнений (4.20). Коль скоро искомое решение содержится и в T (X), то для дальнейшего уточнения бруса, вкотором может присутствовать решение, мы можем организовать итерации с пересечениемX (0) ← X,(4.21)X (k+1) ← T (X (k) ) ∩ X (k) ,k = 0, 1, 2, . . . .(4.22)Следует особо отметить, что в получающихся при этом брусах наличие решения, вообще говоря, не гарантируется.
Они являются лишь«подозрительными» на существование решения.Но вот если для бруса X выполненоT (X) ⊆ X,то по теореме Брауэра о неподвижной точке (стр. 492) в X гарантированно находится решение системы (4.20). Для уточнения этого брусамы снова можем воспользоваться итерациями (4.21)–(4.22). Таким образом, наихудшим, с точки зрения уточнения информации о решениисистемы, является случайT (X) % X.(4.23)4954.7.
Интервальные методы решения уравненийПриведённую выше последовательность действий по обнаружениюрешения системы уравнений и уточнению его границ мы будем называть далее кратко тестом существования (решения). Условимся также считать, что его результатом является брус пересечения (X ∩T (X))либо предел последовательности (4.21)–(4.22). Если этот брус непуст,то он либо наверняка содержит решение системы уравнений, либо является подозрительным на наличие в нём решения. Если же результаттеста существования пуст, то в исходном брусе решений системы уравнений нет.В действительности, каждый из изложенных выше приёмов уточнения решения допускает далеко идущие модификации и улучшения.Например, это относится к итерациям вида (4.21)–(4.22), которые могут быть последовательно применены не к целым брусам X (k) , а к отдельным их компонентам в комбинации с различными способами приведения исходной системы к рекуррентному виду (4.20).
На этом путимы приходим к чрезвычайно эффективным алгоритмам, которые получили наименование методов распространения ограничений (см., кпримеру, [30]).Как простейший тест существования, так и его более продвинутыеварианты без особых проблем реализуются на ЭВМ и работают темлучше, чем более качественно вычисляются интервальные расширения функций F в (4.2) и T в (4.20) и чем меньше ширина бруса X.Последнее связано с тем, что погрешность оценивания области значений функции посредством любого интервального расширения убываетс уменьшением размеров бруса, на котором производится это оценивание. (см. §1.6).4.7бОдномерный интервальный метод НьютонаВ этом параграфе мы рассмотрим простейший случай одного уравнения с одним неизвестным.Предположим, что f : R ⊇ X → R — функция, имеющая нуль x⋆ нарассматриваемом интервале X и дифференцируемая на нём.
Тогда длялюбой точки x̃ ∈ X из этого же интервала в силу теоремы Лагранжао среднем значенииf (x̃) − f (x⋆ ) = (x̃ − x⋆ ) · f ′ (ξ),(4.24)где ξ — некоторая точка между x̃ и x⋆ . Но так как f (x⋆ ) = 0, то при4964. Решение нелинейных уравнений и их системf ′ (ξ) 6= 0 отсюда следуетx⋆ = x̃ −f (x̃).f ′ (ξ)Если f ′ (X) является какой-либо интервальной оценкой производнойот функции f (x) на X, то f ′ (ξ) ∈ f ′ (X) и, интервализуя выписанноеравенство, получим включениеx⋆ ∈ x̃ −f (x̃)f ′ (X)(4.25)в случае 0 6∈ f ′ (X).
Иными словами, для корня x⋆ уравнения f (x) = 0получается новый интервал локализации в виде правой части включения (4.25). Интервальное выражение, фигурирующее в правой части(4.25), играет важную роль в интервальном анализе и потому выделяется в самостоятельное понятие.Определение 4.7.1 Пусть заданы функция f : R → R и интервальная оценивающая функция f ′ для её производной. ОтображениеN : IR × R → IR,действующее по правилуN(X, x̃) := x̃ −f (x̃),f ′ (X)называется (одномерным) интервальным оператором Ньютона для f .Итак, пусть 0 6∈ f ′ (X), так что N(X, x̃) является вполне определённым конечным интервалом.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
