Тихонов: регуляризация некорректных задач

Приговор Адамара

В 1902 году Адамар назвал задачу корректно поставленной, если выполнены три условия: решение существует, оно единственно и оно непрерывно зависит от данных. Третье — самое важное: данные всегда получены с погрешностью, и если малая погрешность даёт большое изменение ответа, вычислять бессмысленно.

Вывод, который Адамар сделал и который приняли на полвека: некорректные задачи не имеют физического смысла и заниматься ими не следует.

Беда в том, что почти все обратные задачи некорректны. Прямая задача: известен объект — вычислить, что покажет прибор. Обратная: известны показания прибора — восстановить объект. Именно обратные задачи составляют содержание геофизики, томографии, спектроскопии, обработки изображений, диагностики — всего, где мы судим о недоступном по доступному.

Почему обратные задачи неустойчивы — на пальцах

Пусть прибор устроен как усреднение:

$$\int_{0}^{1}K(x,s)\,u(s)\,ds=f(x).$$

Одна и та же задача: наивное обращение даёт рябь, регуляризация — гладкий ответMathLocus · построено для этого сайта

Добавим к искомой функции быструю рябь: $u\mapsto u+\varepsilon\sin(\omega s)$. Тогда правая часть изменится на

$$\varepsilon\int_{0}^{1}K(x,s)\sin(\omega s)\,ds\;\xrightarrow[\omega\to\infty]{}\;0$$

(лемма Римана — Лебега: быстрые осцилляции гасятся при интегрировании). Изменение ответа фиксировано и равно $\varepsilon$; изменение данных стремится к нулю. Значит, обратный оператор неограничен, и никакая точность измерений не спасает.

На языке сингулярных чисел то же самое: $Au=f$ решается формулой

$$u=\sum_{n}\frac{\langle f,v_{n}\rangle}{\sigma_{n}}\,u_{n},$$

а сингулярные числа $\sigma_{n}$ у сглаживающего оператора стремятся к нулю. Шум, попавший в далёкие коэффициенты, делится на почти нуль и разносит ответ в клочья.

Ход Тихонова: сменить постановку задачи

Раз задача «решить уравнение» неразрешима устойчиво, надо решать другую задачу. Тихонов предлагает минимизировать сглаживающий функционал

$$M^{\alpha}[u]=\|Au-f\|^{2}+\alpha\,\Omega[u],\qquad \Omega[u]=\|u\|^{2}\ \text{ или }\ \int\big(u^{2}+u'^{2}\big)\,dx.$$

Первое слагаемое требует согласия с данными, второе штрафует «дикость» решения, $\alpha>0$ — параметр регуляризации. Условие минимума даёт уравнение, которое уже разрешимо устойчиво:

$$\boxed{\;(A^{*}A+\alpha I)\,u_{\alpha}=A^{*}f.\;}$$

Через сингулярные числа видно, что именно произошло: вместо деления на $\sigma_{n}$ появляются фильтрующие множители

$$\frac{\sigma_{n}^{2}}{\sigma_{n}^{2}+\alpha},$$

которые близки к единице для крупных $\sigma_{n}$ и гасят вклад мелких. Шум больше не усиливается.

Почему это законно — теорема 1943 года

Идея опирается на факт, доказанный Тихоновым двадцатью годами раньше: непрерывное взаимно однозначное отображение компакта имеет непрерывное обратное. Иными словами, на компактном множестве неустойчивости не бывает.

Отсюда стратегия: сузить класс допустимых решений до компактного — и корректность вернётся. Стабилизирующий функционал $\Omega$ ровно это и делает: его множества уровня компактны в нужной топологии. Регуляризация — не вычислительный трюк, а способ добавить в задачу недостающую информацию, ту самую априорную гладкость, которую человек и так подразумевает, глядя на результат.

Две заметки в «Докладах Академии наук» 1963 года — «О решении некорректно поставленных задач и методе регуляризации» и «О регуляризации некорректно поставленных задач» — и создали дисциплину.

Как выбирать $\alpha$

Вопрос практический и нетривиальный: при $\alpha\to0$ возвращается неустойчивость, при большом $\alpha$ ответ превращается в гладкое ничто. Классический рецепт — принцип невязки (Морозов, 1966): если известен уровень шума $\delta$, брать $\alpha$ так, чтобы

$$\|Au_{\alpha}-f\|=\delta.$$

Согласовываться с данными точнее, чем они измерены, — значит подгонять решение под шум.

Где это сегодня

Формула $(A^{*}A+\alpha I)^{-1}A^{*}f$ известна каждому, кто занимался обработкой данных, — просто под другими именами.

Область	Как называется
статистика	гребневая (ridge) регрессия: $\hat\beta=(X^{\top}X+\alpha I)^{-1}X^{\top}y$
машинное обучение	$L_{2}$-регуляризация, weight decay
вычислительная математика	регуляризация плохо обусловленных систем
томография, геофизика	восстановление по проекциям

Гребневую регрессию переоткрыли Хоэрль и Кеннард в 1970 году, через семь лет после Тихонова, — и в англоязычной литературе она давно называется Tikhonov regularization. Метод наименьших квадратов Лежандра и Гаусса получил, таким образом, недостающую половину: что делать, когда матрица плана почти вырождена. Тот же сюжет с другой стороны — число обусловленности: там объясняется, когда виновата задача, а не метод; здесь — что с этим делать.

Человек

Андрей Николаевич Тихонов (1906–1993) начинал как топологом: в двадцать четыре года он доказал, что произведение любого числа компактов компактно, — результат первого ряда, вошедший в учебники как теорема Тихонова (см. московскую школу). Затем перешёл к уравнениям математической физики (теорема единственности для уравнения теплопроводности, 1935), затем к прикладным задачам.

Прикладной опыт здесь не деталь биографии, а источник теории. В 1950-е Тихонов разрабатывал магнитотеллурическое зондирование — способ судить о строении земных недр по естественным колебаниям электромагнитного поля. Это обратная задача в чистом виде, и метод регуляризации вырос из необходимости её решать: сначала были поиски полезных ископаемых, потом теорема.

В 1970 году Тихонов стал первым деканом созданного при его участии факультета вычислительной математики и кибернетики МГУ.

Следующая точка: Стокгольм, 1972 — за отрицательный ответ на задачу из львовского кафе вручают живого гуся.