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

§ 29. Компактная схема

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

Снова рассмотрим матрицу удовлетворяющую условиям теоремы 27.1. Так как разложение (27.1) существует, то, приравнивая между собой элементы матрицы А и произведения получаем

Будем считать, что для всех Тогда из (29.1) следует:

Если матрица А почти треугольная, то одна из матриц в действительности будет двухдиагональной. В этом случае формулы (29.2) упрощаются. Например, для правой почти треугольной матрицы

В частности, для трехдиагональнол матрицы имеем

Полученные формулы можно использовать для численного определения треугольных сомножителей матрицы Соответствующий алгорифм называется компактной схемой метода Гаусса. Теперь в общем случае

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

Пусть находятся элементы первой строки матрицы С и первого столбца матрицы В. Положим и вычисляем

Реально вычисленные элементы можно рассматривать как точна вычисленные, исходя из возмущенных элементов Если то Если же то это означает, что поэтому получаем, что

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

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

поэтому

Если же Ту то это означает, что выражение,

стоящее в (29.3) слева, не превосходит со по модулю. Но тогда Следовательно, всегда

Аналогично мы получаем, что при вычислении элементов дополнительное возмущение вносится лишь в элемент . При этом

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

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

Наиболее эффективно компактная схема используется для получения треугольного разложения положительно определенных матриц. Согласно следствию теоремы 27.1 в этом случае имеет место разложение

В полном соответствии с (29.2) теперь получаем

В частности, если матрица А вещественная, то

Эти формулы используются для получения разложения (29.6) подобно тому, как формулы (29.2) — для разложения (27.1). Соответствующий алгорифм называется методом квадратного корня. Если применяются операции накопления, то для реально вычисленной матрицы С имеем

Элементы эквивалентного возмущения удовлетворяют соотношениям, аналогичным (29.5). Именно,

Мы не будем останавливаться подробно на их выводе, ибо они получаются почти так же, как и соотношения (29.5).

Заметим лишь, что теперь можно исключительно эффективно оценить

Итак,

УПРАЖНЕНИЯ

(см. скан)

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