1611688890-f641c9ec8276824e4686da772eb56520 (826652), страница 75
Текст из файла (страница 75)
п.Пример 4.2.1 Задача решения систем линейных уравнений Ax = b снеособенной квадратной матрицей A является вычислительно-корректной. Если топология на пространстве Rn её решений задаётся обычнымевклидовым расстоянием и подобным же традиционным образом задаётся расстояние между векторами правой части и матрицами, то существуют хорошо известные неравенства (см. §3.5а), оценивающие сверхуграницы изменения решений x через изменения элементов матрицы A,правой части b и число обусловленности матрицы A.Пример 4.2.2 Вычисление ранга матрицы — вычислительно некорректная задача. Дело в том, что в основе понятия ранга лежит линейная зависимость строк или столбцов матрицы, т.
е. свойство, котороенарушается при сколь угодно малых возмущениях матрицы.Разрывная зависимость решения от входных данных задачи можетвозникать вследствие присутствия в алгоритме вычисления функцииусловных операторов вида IF . . . THEN . . . ELSE, приводящих к ветвле-4594.2. Вычислительно-корректные задачинию. Такова хорошо известная функция знака числа −1, если x < 0,sgn x =0, если x = 0,1, если x > 0.Аналогична функция модуля числа |x|, с которой в обычных и внешнепростых выражениях могут быть замаскированы разрывы и ветвления.Например, таково частное sin x / |x|, которое ведёт себя в окрестностинуля примерно как sgn x.Для систем нелинейных уравнений, могущих иметь неединственное решение, топологию на множестве ответов A нужно задавать ужекаким-либо расстоянием между множествами, например, с помощьютак называемой хаусдорфовой метрики [8]. Напомним её определение.Если задано метрическое пространство с метрикой ̺, то расстоянием точки a до множества X называется величина ̺ (a, X), определяемая как inf x∈X ̺ (a, x).
Хаусдорфовым расстоянием между компактными множествами X и Y называют величинуno̺ (X, Y ) = max max ̺ (x, Y ), max ̺ (y, X) .x∈Xy∈YПри этом ̺ (X, Y ) = +∞, если X = ∅ или Y = ∅. Введённая таким образом величина действительно обладает всеми свойствами расстоянияи может быть использована для задания топологии на пространствахрешений тех задач, ответы к которым неединствены, т. е.
являются целыми множествами.4.2бЗадача решения уравнений не являетсявычислительно-корректнойУже простейшие примеры показывают, что задача решения уравнений и систем уравнений не является вычислительно-корректной. Например, квадратное уравнениеx2 + px + q = 0(4.5)p2 = 4q(4.6)дляимеет лишь одно решение x = −p/2. Но при любых сколь угодно малых возмущениях коэффициента p и свободного члена q, нарушающих4604. Решение нелинейных уравнений и их системравенство (4.6), уравнение (4.5) теряет это единственное решение илиже приобретает ещё одно (см. Рис. 4.1).xxxРис. 4.1.
Неустойчивая зависимость решений уравнения (4.5)–(4.6)от сколь угодно малых шевелений его коэффициентов.Аналогичным образом ведёт себя решение двумерной системы уравнений, эквивалентной (4.5),(x + y = r,xy = sпри s = r2 /4. При этом раздвоение решения не является большимгрехом, коль скоро мы можем рассматривать хаусдорфово расстояниемежду целостными множествами решений. Но вот исчезновение единственного решения, при котором расстояние между множествами решений скачком меняется до +∞ — это чрезвычайное событие, однозначноуказывающее на разрывность разрешающего отображения.Как видим, математическую постановку задачи нахождения решений уравнений нужно «исправить», заменив какой-нибудь вычислительно-корректной постановкой задачи. Приступая к поиску ответа на4.2.
Вычислительно-корректные задачи461этот математический вопрос, отметим, прежде всего, что с точки зрения практических приложений задачи, которые мы обычно формулируем в виде решения уравнений или систем уравнений, традиционновыписывая соотношениеF (x) = 0(4.2)и ему подобные, имеют весьма различную природу. Это и будет отправной точкой нашей ревизии постановки задачи решения уравненийи систем уравнений.4.2вε-решения уравненийВ ряде практических задач пользователю требуется не точное равенство некоторого выражения нулю, а лишь его «исчезающая малость» в сравнении с каким-то a priori установленным порогом. С аналогичной точки зрения часто имеет смысл рассматривать соотношениявида (4.3) или (4.4), выражающие равенство двух каких-то выражений.Таковы, например, в большинстве физических, химических и других естественнонаучных расчётов уравнения материального баланса,вытекающие из закона сохранения массы и закона сохранения заряда.
Точное равенство левой и правой частей уравнения здесь неявнымобразом и не требуется, так как погрешность этого равенства всегдаограничена снизу естественными пределами делимости материи. В самом деле, масса молекулы, масса и размеры атома, заряд элементарной частицы и т. п. величины, с точностью до которых имеет смыслрассматривать конкретные уравнения баланса — все они имеют вполнеконечные (хотя и весьма малые) значения.Например, не имеет смысла требовать, чтобы закон сохранения заряда выполнялся с погрешностью, меньшей чем величина элементарного электрического заряда (т. е. заряда электрона, равного 1.6·10−19 Кл).Также бессмысленно требовать, чтобы погрешность изготовления илиподгонки деталей оптических систем была существенно меньшей длины световой волны (от 4 · 10−7 м до 7.6 · 10−7 м в зависимости от цвета).А что касается температуры, то при обычных земных условиях определение её с точностью, превосходящей 0.001 градуса, вообще проблематично в силу принципиальных соображений.
Наконец, ограниченнаяточность, с которой известны абсолютно все физические константы1,1 В лучшем случае относительная погрешность известных на сегодняшний деньзначений физических констант равна 10−10 , см. [58].4624. Решение нелинейных уравнений и их системтакже воздвигает границы для требований равенства в физических соотношениях.Совершенно аналогична ситуация с экономическими балансами, какв стоимостном выражении, так и в натуральном: требовать, чтобы онивыполнялись с погрешностью, меньшей, чем одна копейка (наименьшая денежная величина) или чем единица неделимого товара (телевизор, автомобиль и т. п.) просто бессмысленно.Во всех вышеприведённых примерах под решением уравнения понимается значение переменной, которое доставляет левой и правой частям уравнения пренебрежимо отличающиеся значения.
В применениик уравнениям вида (4.2) соответствующая формулировка выглядит следующим образом:Для заданных отображения F : Rn → Rn и ε > 0 найтизначения неизвестной переменной x, такие что F (x) ≈ 0с абсолютной погрешностью ε , т. е. kF (x)k < ε .Решением этой задачи является целое множество точек, которые мыбудем называть ε-решениями или почти решениями, если порог этойпренебрежимой малости не оговорён явно или несуществен.Нетрудно понять, что условием kF (x)k < ε задаётся открытое множество, если отображение F непрерывно. Любая точка из этого множества устойчива к малым возмущениям исходных данных, а задача«о нахождении почти решений» является вычислительно-корректной.Как уже отмечалось выше, в некоторых задачах система уравненийболее естественно записывается не как (4.2), а в виде (4.3)G(x) = H(x),и требуется обеспечить с относительной погрешностью ε равенство еёлевой и правой частей:4.2.
Вычислительно-корректные задачи463Для заданных отображений G, H : Rn → Rn и ε > 0найти значения неизвестной переменной x, такие чтоG(x) ≈ H(x) с относительной погрешностью ε , т. е.kG(x) − H(x)k<ε.max{kG(x)k, kH(x)k}Решения этой задачи мы также будем называть ε-решениями системыуравнений вида (4.3).Математические понятия, определения которых привлекают малыйдопуск ε, не являются чем-то экзотическим. Таковы, к примеру, εэнтропия множеств в метрических пространствах, ε-субдифференциалфункции, ε-оптимальные решения задач оптимизации и т. п.
Одним изчастных случаев ε-решений являются точки ε-спектра матрицы, предложенные для обобщения традиционного понятия собственного значения матрицы [11, 47, 59]. Говорят, что точка z на комплексной плоскости принадлежит ε-спектру матрицы A, если существует комплексныйвектор v единичной длины, такой что k(A − zI)vk ≤ ε, где k · k —какая-то векторная норма.
Иными словами, при условии kvk = 1 здесьрассматривается приближённое «с точностью до ε» равенство Av = zv.4.2гНедостаточность ε-решенийНо есть и принципиально другой тип задач, которые образно могутбыть названы задачами «об определении перехода через нуль» и не сводятся к нахождению ε-решений.
Таковы задачи, в которых требуетсягарантированно отследить переход функции к значениям противоположного знака (или, более общо, переход через некоторое критическоезначение). При этом, в частности, в любой окрестности решения должны присутствовать как положительные значения функции, так и еёотрицательные значения, тогда как в задачах нахождения «почти решений» это условие может и не выполняться.Рассмотрим следующую ситуацию, для анализа которой достаточно знание элементарной физики. Пусть кирпич лежит на опоре (см.Рис. 4.2), и мы потихоньку сдвигаем его к краю. Когда он упадёт? Для4644.
Решение нелинейных уравнений и их системРис. 4.2. Когда кирпич упадёт с подставки?ответа на этот вопрос приравнивают момент силы тяжести, действующей на свисающую часть кирпича, и момент силы тяжести, действующей на ту часть, которая лежит на опоре.Но в случае точного их равенства кирпич ещё не упадёт! Эта ситуация называется неустойчивым равновесием, но в отсутствие каких-либовоздействий на кирпич он не будет падать, а зависнет на грани опоры.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
