6CAD-CAE-23 Упорядочение (1014142), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

a) 2X₁+2X₂+4X₃=5

b) 6X₁-X₂+X₃=7

c) 4X₁-10X₂-12X₃= -4

Решаем её. Цель элементарных преобразований – привести матрицу к ступенчатому виду (так называемый, прямой ход в методе Гаусса).

a) 2X₁+2X₂+4X₃=5

b) -7X₂-11X₃= -8 (вычитание первой строки, умноженной на 3 из второй строки)

c) -14X₂-20X₃= -14 (вычитание первой строки, умноженной на 2 из третьей строки)

a) 2X₁+2X₂+4X₃=5

b) -7X₂-11X₃= -8

c) 2X₃=2 (вычитание второй строки, умноженной на 2

из третьей строки)

В обычной записи:

(23)X₁+(23)X₂+(43)X₃=53 (22)X₁+(22)X₂+(42)X₃=52

*

*

6X₁ -1X₂ +1X₃=7 4X₁-10X₂-12X₃= -4

-7X₂ -11X₃= -8 -14X₂-20X₃= -14

-72X₂-112X₃= -82

*

-14X₂-20X₃=-14

0+2X₃= 2

в итоге:

была стала

Как было в верхнем правом треугольнике 6 ненулевых элементов, так и осталось.

Пример 2.

2X₁+2X₂+4X₃=5

6X₁-X₂+0X₃=7

4X₁-10X₂-12X₃= -4

(23)X₁+(23)X₂+(43)X₃=53

*

6X₁+X₂+0X₃=7

-7X₂-12X₃= -8

(22)X₁+(22)X₂+(42)X₃=52

4X₁-10X₂-12X₃= -4

*

-14X₂-20X₃= -14

-72X₂-122X₃= -16

*

-14X₂-20X₃=-14

+4X₃= 2

В итоге:

была стала

Здесь картина иная: было 5 ненулевых элементов в верхнем треугольнике, а стало 6. Т.е. матрица претерпела заполнение.

Теперь обратимся к методу Холесского - симметричному варианту Гауссова исключения для симметричных положительно определенных матриц.

Предположим, что система уравнений, которую нужно решить есть

Ax=b, где А - NN симметричная положительно определенная матрица коэффициентов,

b - вектор длины N, называемый правой частью, а

х - вектор длины N, компоненты которого нужно вычислить.

Применения к А метода Холесского приводит к треугольному разложению

А=L L^T, где L - нижняя треугольная матрица с положительными диагональными элементами.

Верхний индекс Т указывает на операцию транспонирования.

Таким образом имеем: L L^T х=b

Замена y= L^Tх показывает, что х можно получить, решая треугольные системы:

Ly=b

L^T х=b

Поскольку L - треугольная матрица, то строка K может содержать ненулевые элементы только в первых K столбцах.

В частности, первая строка L содержит только один ненулевой элемент, так, что первая компонента y может быть легко вычислена. Вторая строка L содержит только два ненулевых элемента, следовательно, она связывает только две первые компоненты y; но так как первая компонента y известна, то теперь может быть вычислена и вторая. Таким образом, решаем систему уравнений относительно y.

Далее, поскольку матрица L^Т также треугольная, аналогичный процесс используется для отыскания х из второго уравнения, только теперь требуется обратный порядок операций, так как - L^Т верхняя, а не нижняя треугольная матрица.

Рассмотрим сначала случай 22 матрицы

А= L=

Потребуем, чтобы А=L L^T

L^T= : L L^T=

a₁₁=l₁₁²; a₁₂=l₁₁l₂₁; a₂₁=l₂₁l₁₁; a₂₂=l₂₁²+ l₂₂²

В силу положительной определенности матрицы А, элемент a₁₁>0 и извлечение квадратного корня l₁₁= возможно.

Второй элемент определяется из уравнения для a₂₁ (который равен a₁₂, т.к. А - симметричная матрица).

Наконец, l₂₂ определяется из равенства :

l₂₂ =

Алгоритм разложения Холесского для симметричной матрицы:

Цикл по столбцам А

For K=1 to n do

Вычисление очередного вектора-строки, кроме диагонального элемента.

For i=1 to K-1 do

a_Ki=( a_Ki - )/a_ii

Конец цикла по i.

Вычисление диагонального элемента

Конец цикла по К.

Теперь множитель L расположен в нижнем треугольнике матрицы А.

Этот алгоритм может быть сделан более устойчивым заменой оператора, содержащего квадратный корень, следующим оператором:

IF t >0 then a_KK= else a_KK =0

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

11.2. Проблема упорядочения

Вернёмся к примеру 2 решения системы уравнения методом Гаусса.

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

Для иллюстрации подобной проблемы в методе Холесского в качестве примера рассмотрим задачу:

Множитель L Холесского для матрицы коэффициентов системы выглядит так:

L=

Решая систему Ly=b, получаем: y=

Затем, решая систему L^TX=y, находим: X=

Этот пример иллюстрирует наиболее важный факт, относящийся к применению метода Холесского для разреженной матрицы А: матрица обычно претерпевает заполнение.

Это значит, что L имеет ненулевые элементы в позициях, где в нижней треугольной части А стояли нули.

Предположим теперь, что мы перенумеровали переменные в соответствии с правилом

Xi  , i =1,2,...,5

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

Должно быть ясно, что эта перенумерация переменных и переупорядочение уравнений равносильны симметричной перестановке строк и столбцов А, причем та же перестановка применяется к b.

Эту новую систему обозначим через

Применяя к ней , как и прежде, метод Холесского, мы разложим А в произведение , где (с точностью до 3-х значащих цифр)

Решая Ly=b и L^Tx=y, получим решение x , которое есть всего лишь переупорядоченная форма вектора х.

Важнейший момент здесь состоит в том, что переупорядочение уравнений и переменных привело к треугольному множителю , который разрежен в точности в той мере, что и нижний треугольник А.

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

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

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

1. Необходимо отводить память для хранения возникших
ненулевых элементов. При этом степень заполнения может ока­заться весьма значительной. Наиболее крайний пример, часто
цитируемый в литературе - это матрица с заполненными первой строкой,
первым столбцом и диагональю и остальными элементами, рав­ными нулю: если выполнить исключение в первом столбце, то
все остальные позиции матрицы подвергнутся заполнению. Если
матрица А симметрична и положительно определена, то размеры
заполнения и позиции новых ненулевых элементов могут быть
определены до того, как фактически начнется исключение. Таким
образом, становится возможным заранее выделить необходимый
дополнительный объем памяти. Однако если матрица А незнако-
определена, то это не удается сделать, и проблема распределения
памяти существенно усложняется.

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

3. Границы ошибок увеличиваются вместе с ростом заполне­ния. Многие исследователи отмечают ключевую роль того факта, что каждый элемент матрицы А лишь несколько раз претерпевает изменение в процессе исключения, и поэтому чрезмерного накопления вычислительных ошибок не происходит. С другой стороны, сдерживание роста ошибок должно рассматриваться как одна из целей, преследуемых при разработке алгоритмов, уменьшающих заполнение; этой точке зрения уделяется недостаточно внимания в литературе по разре­женным матрицам. Чрезмерное заполнение может повлечь за собой слишком сильное накопление вычислительных ошибок, что вынудит применить итерационный метод вместо прямого при решении системы линейных алгебраических уравнений большого размера.

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

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

Характеристики

Список файлов лекций