Карта → событие
Число обусловленности: когда виновата задача, а не метод
Паника 1943 года
Машины появились — и почти сразу выяснилось, что вместе с ними появилась проблема, которой не было, пока считали руками.
Человек, ведущий вычисление, видит промежуточные числа и замечает бессмыслицу. Машина не видит ничего: она складывает то, что дали, с той точностью, какая заложена. Каждое действие округляется, округления накапливаются, и на выходе может оказаться правдоподобный на вид мусор.
Насколько это опасно, попытался оценить статистик Гарольд Хотеллинг (1943). Разбирая обычное исключение неизвестных при решении системы линейных уравнений, он получил, что ошибка в худшем случае растёт как $4^{n}$ с порядком системы. Вывод выходил убийственный: система порядка пятьдесят требовала бы порядка тридцати запасных знаков, то есть была бы недоступна никакой мыслимой машине.
Если бы оценка была верна, всё вычислительное дело кончилось бы, не начавшись.
Число, которое принадлежит задаче, а не методу
Джон фон НейманДжон фон НейманАксиоматизировал квантовую механику, основал теорию игр, придумал архитектуру компьютера и метод Монте-Карло — и всё это, по мнению современников, не напрягаясь. и Герман Голдстайн — оба из принстонского Института перспективных исследований, оба причастны к ЭНИАКу — разобрали вопрос заново и в 1947 году напечатали работу «Numerical inverting of matrices of high order».
Показали они две вещи. Во-первых, оценка Хотеллинга безнадёжно пессимистична: она описывает мыслимый худший случай, который на практике не встречается. Во-вторых — и это главное — они отделили друг от друга два обстоятельства, которые до тех пор смешивали.
Часть трудности принадлежит задаче, а не способу её решения.
Есть системы уравнений, у которых крошечное изменение входных данных меняет ответ до неузнаваемости. Никакой алгоритм здесь не поможет: сама постановка такова, что ответ неустойчив. Меру этого свойства фон Нейман и Голдстайн выразили отношением наибольшего и наименьшего сингулярных чисел матрицы, а имя — число обусловленности — закрепил ТьюрингАлан ТьюрингОпределил, что значит «вычислить», за десять лет до появления компьютеров, взломал «Энигму» и был осуждён за то, кем он был. годом позже, в работе 1948 года о тех же ошибках округления, написанной независимо.
Отсюда следует различение, на котором стоит вся дисциплина:
- задача плохо обусловлена — виновата задача; ответ нельзя получить точнее, чем позволяют входные данные, каким угодно методом;
- алгоритм неустойчив — виноват метод; хорошую задачу испортили дурным способом счёта.
Смешивать их — всё равно что путать хрупкость вазы с неловкостью грузчика.
Что здесь произошло
Впервые в этой линии предметом математики стала ошибка.
До сих пор история была про то, как считать дешевле: заменить умножение сложением, сжать таблицу, поручить операцию металлу, изъять понимание из процедуры. Всё это касалось цены. Точность подразумевалась: сколько знаков выписал, столько и верны.
Машина сделала это допущение ложным. Знаков она выписывает сколько угодно, а верны из них не все, и сколько именно — отдельный математический вопрос, у которого есть теоремы. С 1947 года «посчитать» означает не только получить число, но и уметь сказать, чему в нём можно верить.
В этой линии фон Нейман стоит трижды подряд, и все три раза по одной причине: он же начертил эту машину (1945), он же вместе с Уламом придумал считать на ней вероятность игрой (1946) — и он же первым спросил, чему в её ответе можно верить.
Следующая точка: Вашингтон — где научились искать оптимум, обходя вершины многогранника.