книги / Численные методы решения некорректных задач

ББК 22.193 Т46

УДК 519.6

Т и х о н о в А.Н., Г о н ч а р с к и й А.В., С т е п а н о в В.В., Я г о д а А.Г. Численные методы решения некорректных задач. — М.: Наука. Гл. ред. физ.-мат. лит., 1990. - 232 с. ISBN 5-02-014135-6.

При обработке данных физического эксперимента часто возникает необ­ ходимость решения на ЭВМ неустойчивых по отношению к погрешностям экспе­ римента так называемых некорректно поставленных задач. В книге дается изложение теории и численных методов решения некорректных задач при различной априорной информации об искомом решении. Приводятся тексты на языке фортран большого комплекса программ решения интегральных уравнений 1-го рода.

Для студентов и аспирантов физико-математических и других естест­ веннонаучных специальностей, а также для инженеров и научных работни­ ков, интересующихся вопросами обработки и интерпретации данных экс­ перимента.

Ил. 104. Библиогр. 220 назв.

Р е ц е н з е н т академик М.М. Лаврентьев

1602120000 - 095 37-90 053(02)90

ОГЛАВЛЕНИЕ

§3. Применение метода проекций сопряженных градиентов с проециро­ ванием на множество векторов с неотрицательными компонента­

3

ВВЕДЕНИЕ

С точки зрения современной математики все задачи принято условно делить на корректно и некорректно поставленные.

Рассмотрим операторное уравнение

где Z, U—метрические пространства. Согласно Адамару [213] задача (В.1) называется корректной, или корректно поставленной, если выполнены два условия:

а) уравнение (В.1) разрешимо для любого и Е U единственным об­ разом;

б) решение уравнения (В.1) устойчиво относительно возмущения пра­ вой части уравнения, т.е. оператор А ~1 определен на всем U и является непрерывным.

Типичным примером некорректно поставленной задачи является линейное операторное уравнение (В.1) в случае, когда оператор Л вполне непрерывен. В этом случае, как известно, нарушаются оба условия коррект­ ности задачи по Адамару. Если Z - бесконечномерное пространство, то, во-первых, оператор Л ”1 определен не на всем U (AZ Ф U) и, во-вторых,

Л"1 (определенный на AZ С U) не является непрерывным.

Кнекорректно поставленным задачам относятся многие задачи теории оптимального управления, линейной'алгебры, задача суммирования рядов Фурье с неточно заданными коэффициентами, задача минимизации функ­ ционалов и многие другие.

Теория и методы решения некорректных задач получили интенсивное развитие после выхода в свет основополагающих работ [164—166]. Важ­ нейшим открытием было введенное в [166] понятие приближенного реше­ ния некорректных задач. В основе новой постановки лежит понятие регуляризирующего алгоритма (РА) как способа приближенного решения некор­ ректной задачи.

Рассмотрим следующую абстрактную задачу. Даны метрические про­ странства X и Y и отображение G: X Y, заданное на подмножестве D G С X. Необходимо по элементу х Е D Q найти его образ G(x) Е Y. Если вернуться к задаче (В.1), то в новых терминах G = А '1, X = U, Y = Z и за­ дача состоит в вычислении оператора Л ”1. Роль DQ в э т о м случае играет

D G = AZ С и .

Отображение G может играть роль оператора, переводящего множество данных какой-либо экстремальной задачи в элемент, на котором достигает­ ся экстремум, и т.п.

5

Если отображение G определено на всех X и непрерывно, то рассматри­

не существовать, так как xs не обязательно принадлежит DG, а если и принадлежит, то р у (G(х$), у ) , вообще говоря, не стремится к нулю при 8 -*0.

Таким образом, рассматриваемую проблему можно трактовать как задачу о приближенном вычислении значения абстрактной функции <7(х) при неточно заданном аргументе х. Понятие неточно заданного аргумента нуждается в определении. Под приближенными данными х будем пони­ мать пару (х$, 6) такую, что р^(х$, х) < 5 , причем элемент х& не обяза­ тельно принадлежит DG.

Фундаментальным понятием теории решения некорректных задач является понятие регуляризирующего алгоритма как способа приближен­ ного решения некорректной задачи. Введем в рассмотрение оператор R ,

(>х(хЬ* * ) < 6

О п р е д е л е н и е . Функция G называется регуляризируемой m D G, если существует отображение R(x, 8) = R&(х), действующее из прямого произведения пространств X и {5}, такое, что

Нш Д(Дб,5 ,х ) = 0

бо

для любых х £ Dg . Сам оператор R (х, 8) (R&(х)) назьшается регуляризирующим оператором (регуляризирующим семейством операторов).

Абстрактная постановка задачи, предложенная в следующем разделе, включает различные некорректные задачи (решение операторных уравне­ ний, задачи минимизации функционалов и т.п.). Понятие регуляризируе-

z _

В теории регуляризации существенно, что приближение к (7(х) строит­ ся с использованием пары (хб, 5).

Ясно, что при построении приближенного решения нельзя использовать тройку (х$ ,5, х ), так как точное значение х неизвестно. Возникает вопрос о возможности построения приближенного решения только по значению

6

*5 (погрешность 5 неизвестна, но известно, что Рх(*ь> *) -*0 при б -*0). Следующее утверждение показывает, что это возможно только для задач, по существу являющихся корректными.

Отображение G регуляризируемо на DQ семейством R § = /?(*, б) = = /?(•) тогда и только тогда, когда G(x) продолжается на все X , причем это продолжение непрерывно на DQ в X (см. [16]).

Последнее означает, что для некорректной задачи (В.1) (например, пусть в (В.1) оператор А взаимно однозначен из Z в f/и вполне непреры­ вен) отображение G = А не может быть продолжено на все пространст­ во U с множества DQ = AZ С U так, чтобы оно было непрерывно на DQ , поскольку оператор А~* не является непрерывным. Это значит, что в указанной задаче регуляризация при помощи оператора R ( - ), не завися­ щего от б, невозможна.

Таким образом, пара (*g, б) является, вообще говоря, той минималь­ ной информацией, которая необходима для построения приближенного решения некорректных задач. Соответственно для задачи (В.1) минималь­ ной информацией является пара (хб, б ).

Зададимся следующим вопросом: насколько широк круг задач, кото­ рые допускают построение регуляризирующего семейства отображений, т.е. постараемся описать круг задач, регуляризируемых по Тихонову. Очевидно, что множество таких задач не пусто, так как для любой кор­ ректной задачи в качестве регуляризирующего семейства можно взять R6 = G. На этом факте по сути дела основана вся классическая вычисли­ тельная математика. Регуляризируемыми являются не только корректные, но и значительная часть некорректных задач. Так, например, если в урав­ нении (В.1) оператор А линеен, непрерывен и инъективен, a Z и U - гиль­ бертовы пространства, то такая задача регуляризируема.

Этот результат является основным результатом главы I. Более того, в первой главе будут предложены конструктивные методы построения регуляризирующих алгоритмов для задачи (В.1) в случае, когда с погреш­ ностью задана не только правая часть уравнения, но и сам оператор. Пусть заданы элементы ид и линейный оператор Ah такие, что || Wg - и\\и < 5 , \\Ah - А || < А. Таким образом, входной информацией является набор (wg, A ht б, А). По этим данным требуется построить элемент zn £ Z,

%z _

г? = {б, А } такой, что z при т ? 0. Для решения этой задачи широко используется следующая конструкция. Рассмотрим функционал

Пусть z% — экстремаль функционала Ма [z] , т.е. элемент, минимизи­ рующий Ma [z] на Z. Если параметр регуляризации а = а(т?) согласован

определенным образом т? = (б, А}, то элемент и будет в определен­

ном смысле решением задачи (В.1).

В главе I подробно обсуждаются способы согласования параметра регуляризации а с погрешностью задания входной информации гb Заметим сразу, что если пытаться строить приближенные решения так, чтобы а не являлось функцией от погрешности г?, то последнее эквивалентно по­ пытке построить регуляризатор R ( • , г?) = R ( ‘ ), что, как мы уже знаем, возможно лишь для корректных задач.

7

В главе I подробно обсуждаются априорные схемы выбора параметра регуляризации, впервые предложенные в работе [165].

Особый интерес для практики представляет схема выбора параметра регуляризации по обобщенной невязке [58, 185]. В монографии подроб­ но изложены методы решения несовместных уравнений.

Значительное место в главе I отведено проблемам конечно-разностной аппроксимации и численным методам решения полученных после ап­ проксимации систем линейных уравнений. Особое внимание уделено современным методам решения интегральных уравнений типа свертки. Регуляризирующие алгоритмы решения уравнений от разности аргумен­ тов нашли широкое применение в задачах обработки изображений, компью­ терной томографии и т.п. [183,184].

Построение регуляризирующих алгоритмов основано на использова­ нии дополнительной априорной информации об искомом решении. Особен­ но просто эта задача решается, если есть информация о принадлежности искомого решения компактному классу [185]. Как показано в главе II, этой информации вполне достаточно, чтобы построить регуляризирующий алгоритм.

Более того, в этом случае оказывается возможным построить не толь-

z _

ко приближенное решение (В.1) Zg такое, что Zg -►z при Ъ -*0, но и полу­

wg: II Mg - и \\ц < 6

—погрешность решения некорректной задачи (В.1) в точке z при помощи алгоритма Rg. Оказывается, что если задача (В.1) регуляризируема не­ прерывными отображениями Rs и существует равномерная на множестве D оценка погрешности

sup A(Rs , 6 ,z ) < e(S) ->• О, zG D

то сужение оператора A ~l на множество AD C U непрерывно на AD С U [16]. Последнее утверждение не дает возможности построить погреш­ ность решения некорректной задачи на всем пространстве Z.

Однако если D компакт, то обратный оператор А ~х, определенный на AD С U, непрерывен, что и позволяет находить вместе с приближенным решением его погрешность.

Следующий важный вопрос, который обсуждается в главе II — это вопрос о том, как в конкретной задаче, используя априорную информацию об искомом решении задачи, выделять компактное множество коррект­ ности М.

В целом ряде обратных задач математической физики имеется качест­ венная информация об искомом решении обратной задачи, такая, как моно­ тонность искомых функций, их выпуклость и т.п. [71]. Как показано в главе II, этой информации достаточно, чтобы на ее основании построить РА решения некорректной задачи (1.1) [74].

8

Г л а в а I

МЕТОДЫ РЕГУЛЯРИЗАЦИИ

В настоящей главе рассмотрим методы решения некорректно постав ленных задач при условии, что априорной информации, вообще говоря, не­ достаточно для выделения компактного множества корректности. Основ­ ные идеи этой главы были высказаны в работах [165,166]. Мы будем рас­ сматривать случай, когда оператор также задается приближенно, а мно­ жество ограничений задачи - выпуклое замкнутое множество в гильберто­ вом пространстве. Случай точно заданного оператора и случай отсутствия ограничений (т.е. множество ограничений совпадает со всем пространст­ вом) являются частными случаями рассмотренной постановки задачи.

10