Уилкинсон: точный ответ на слегка другой вопрос

Человек, оставшийся при машине

Джеймс Хардли Уилкинсон (1919–1986) пришёл в Национальную физическую лабораторию в Теддингтоне в 1946 году — работать с ТьюрингомАлан Тьюринганглийский математик и криптоаналитик · 1912–1954Определил, что значит «вычислить», за десять лет до появления компьютеров, взломал «Энигму» и был осуждён за то, кем он был. над проектом вычислительной машины ACE. Тьюринг ушёл через два года; Уилкинсон остался и довёл дело до работающего Pilot ACE (1950).

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

Неправильный вопрос

Фон Нейман и Голдстайн показали, что часть трудности принадлежит задаче. Оставался вопрос об алгоритме: насколько вычисленный ответ $\hat x$ отличается от истинного $x$?

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

Уилкинсон вопрос перевернул.

Не «насколько наш ответ неверен для нашей задачи», а: для какой задачи наш ответ был бы совершенно верен?

Формально: вычисленное $\hat x$ не решает систему $Ax=b$, но оно точно решает какую-то соседнюю систему $(A+E)\,\hat x=b+f$. Спрашивать надо про размер возмущения $E$ и $f$ — то есть про то, насколько сильно пришлось бы пошевелить исходные данные, чтобы наш ответ стал безупречным.

Это и есть обратный анализ ошибок.

Почему это оказалось решением

Переворот выглядит игрой слов, а даёт три вещи сразу.

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

Появляется критерий совершенства. Данные в реальной задаче известны неточно — с погрешностью измерения, с ошибкой округления при вводе. Если возмущение $E$, внесённое алгоритмом, меньше этой неопределённости, спрашивать больше не о чем: алгоритм вернул точный ответ на задачу, неотличимую от вашей. Лучшего требовать бессмысленно. Такой алгоритм называют обратно устойчивым.

Разделяются ответственности. Соединив обратный анализ с числом обусловленности, получаем формулу, ставшую каноном численной математики:

$$\text{ошибка ответа}\;\lesssim\;\underbrace{\text{обусловленность}}_{\text{свойство задачи}}\;\times\;\underbrace{\text{обратная ошибка}}_{\text{свойство алгоритма}}.$$

Теперь на вопрос «почему ответ плох?» есть проверяемый ответ: либо задача такова, либо метод.

Многочлен, который его напугал

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

Он взял для проверки программы безобиднейший многочлен с очевидными корнями:

$$p(x)=(x-1)(x-2)\cdots(x-20).$$

Раскрыл скобки, получил коэффициенты, подал их машине — и получил чушь. Оказалось, что если изменить один-единственный коэффициент, при $x^{19}$, на $2^{-23}$ — величину порядка ошибки округления, — то корни расползаются катастрофически: часть их сходит с вещественной прямой и становится комплексными, а некоторые уезжают от своих мест на расстояние в несколько единиц.

Программа была ни при чём. Задача «найти корни по коэффициентам» для этого многочлена чудовищно плохо обусловлена сама по себе — и никто до Уилкинсона этого не подозревал, потому что вручную такое никто не считал.

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

Следующая точка: Мюррей-Хилл — где нашёлся алгоритм, ждавший своей нужды сто шестьдесят лет.