Главная > Математика > Алгебраическая проблема собственныx значений
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

Обратная подстановка

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

Ограничимся довольно кратким анализом, так как эта задача подробно исследована Уилкинсоном (1963b, стр. 99—107). Рассмотрим решение системы уравнений

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

где (гл. 3, § 9)

Если разделить числитель и знаменатель на то получим

где

Умножая уравнение (59.4) на и перегруппировывая, находим

показывая, что вычисленное точно удовлетворяет уравнению с коэффициентами Относительное возмущение во всех коэффициентах порядка кроме который может иметь относительное возмущение порядка Поэтому вычисленный вектор х удовлетворяет системе

где есть функция от но в любом случае она равномерно ограничена сверху, как показано в (59.8) для

60. Это одна из самых хороших оценок ошибок, полученных в матричном анализе. Насколько она хороша, станет ясно, когда рассмотрим вектор-невязку. Имеем

откуда

Если элементы ограничены единицей, то

для 1-, 2- или -нормы. Если то второй член незначителен. Рассмотрим теперь вектор х, полученный округлением точного решения до разрядов в арифметике с плавающей запятой. Можем написать

Очевидно, что

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

откуда

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

<< Предыдущий параграф Следующий параграф >>
Оглавление