Высокая точность вычисленного решения треугольной системы уравнений

61. В последнем параграфе мы дали оценку невязок вычисленных решений. Как ни замечательна эта оценка, она недооценивает точности самого решения, когда очень плохо обусловлена. Мы показали, что вычисленное х удовлетворяет (59.7), и дали оценку (59.8) для Все, что мы можем получить из нее, так это

и, следовательно,

при условии До сих пор, когда мы имели оценку такого вида, мы заменяли на и обычно это не приводило к большим переоценкам. Однако для нашего частного случая это не так. Действительно, пренебрегая членом получаем

Здесь диагональные элементы равны следовательно, матрица в квадратных скобках правой части (61.3) есть нижняя треугольная матрица с единичными диагональными элементами. Предположим, что элементы удовлетворяют соотношениям

для некоторого К. Тогда (61.3) дает

где есть нижняя треугольная матрица, каждый элемент которой равен единице. Следовательно,

Аналогично, если мы решаем систему уравнений

с верхней треугольной матрицей, то вычисленное решение удовлетворит соотношению

где, с точностью до членов порядка есть такая диагональная матрица, что

Снова, если

Для многих очень плохо обусловленных треугольных матриц К порядка единицы. Например, такой матрицей является из § 45. Для этой верхней треугольной матрицы мы можем взять поэтому

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

62. Для того чтобы подчеркнуть, что довольно неожиданная высокая точность имеет место не только у матриц со свойством (61.4), рассмотрим матрицы, имеющие почти противоположное свойство. Предположим, что нижняя треугольная матрица и имеет положительные диагональные элементы и отрицательные недиагональные. Покажем, что если есть правая часть с неотрицательными элементами, то вычисленное решение имеет малую относительную ошибку, хотя может быть очень плохо обусловленной.

Обозначим точное решение через у, а вычисленное через х и определим соотношением

Покажем, что

лричем эту форму оценки ошибки удобно сохранить на некоторое время. Доказательство по индукции. Предположим, что оно верно до Теперь дается формулой (59.2), где из гл. 3 § 8 можем заменить оценки на более точные:

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

Легко построить матрицы этого вида, имеющие сколь угодно большие числа обусловленности. Заметим, что для того, чтобы обратить мы берем правых частей от до каждая из которых состоит целиком из неотрицательных элементов. Следовательно, все элементы вычисленной обратной матрицы имеют малые относительные ошибки. Читатель может почувствовать, что аргументы, которые мы только что привели, весьма тенденциозны. Признавая, что это верно, все же имеет смысл подчеркнуть, что вычисленные решения треугольных систем, вообще говоря, намного точнее, чем это можно установить из оценки, полученной для вектора невязок, и эта высокая точность часто важн на практике.

Мы исследовали лишь случай, когда используется накопление с плавающей запятой. Для других видов вычислений полученные оценки несколько слабее, но в общих чертах сохраняют те же самые свойства. Подробный анализ был дан Уилкинсоном (1961b и 1963b, сгр. 99-107).