Амосов А.А., Дубинский В.А., Копченова Н.В. Вычислительные методы для инженеров (1994) (1095853), страница 32
Текст из файла (страница 32)
Отличие от вычислений примера 5,9 состоит в том, что на 2-м шаге множители дг1 и дгп а также второе и третье уравнения системы (5.40) меняются места— ми. В результате получим разложение вида (5.62), где 2 -9 5 0 3.5 -10 0 0 3.00029 1 0 0 0.5 1 0 0.6 2.9 10 5 1 После получения разложения вида (5.62) для решения системы Ах = 6 выполняют следующие действия. 1о. Правую часть перестановкой элементов приводят к виду м Ь = р 1р„г ... Р Р~6.
Ю 2о. Преобразуют вектор Ь по формулам прямого хода; необходимые и Ю для вычислений множители д," берут из матрицы Х. В результате получают вектор б~т '~. Зо. Обратной подстановкой решают систему Ух = 5~ т '~ . 157 Пример 5.15.
Решим систему (5.39), используя полученное в примере 5.14 Ю разложение матрицы А Здесь вектор Ь = ( — 4, 0.6001„-8.5)т преобразуется в вектор Ь = (-4, -8.5, 0.6001)т перестановкой второго и третьего элементов. А П р я и о й х о д. 1-й ш ь г. Ь'1' = Ьз — п21Ь1 = — 8.5 — 0.5( — 4) = — 6.5, м м Ьз — — Ьз — 1зз 1 Ь1 — 0.
600 1 — О. 6 ° (-4) = 3.000 1 . В результате 1-го шага имеем Ь(1) — ( 4 ~ 5 3 0001)т 2-й ш а г. Ьз~т~ Ьз~ы Дз2Ь2~1' = 30001 — 29 10 з (-65) ~ 300029 В результате прямого хода правая часть оказалась приведенной к виду Ь'т' = (-4, -6.5, 3.00029)т. О б р а т н ы й х о д проводится точно так же, как в примере 5.9, и дает значения хз = 1, х2 — — 1, х1 = О.
$5.8. Метод Холецкого (метод квадратных корней) 1. Описание метода. Пусть требуется решить систему линейных алгебраических уравнений (5.63) Ах= Ь с симметричной положительно определенной матрицей А. Линейные системы такого типа часто встречаются в приложениях (например, в задачах оптимизации, при решеиии уравнений математической физики и др.). Для их решения весьма часто применяется метод Холецкозо (другое название — метод квадратных корней). В основе метода лежит алгоритм построения специального ЬУ- разложения матрицы А, в результате чего она приводится к виду (5.64) А — ~~т, В разложении (5.64) нижняя треугольная матрица 11 1 0 ...
0 1з1 1гг "О (5.65) 1ш1 1в2 " 1ва 158 Заметим, что матрица перестановки РЬ полностью определяется заданием номера 1ь уравнения, которое переставляется с Й-м уравнением. Поэтому для хранения всей информации о перестановках достаточно целочисленного массива длины я — 1. Юу= Ь, Ст =„. (5.66) Для решения систем (5.66) требуется выполнение примерно 2п12 арифметических операций.
Найдем элементы матрицы Ь. Для этого вычислим элементы матрицы .БЮ и приравняем их соответствующим элементам матрицы Я. В результате получим систему уравнений 111= а11, 2 111111 = а11 1=2, 3, ...,т, 121 + 12 2 а22~ 2 2 111121 + 112122 а ~2~ 1 — 3,4, ...,т, (5.67) $1+ 1~.
+ ... + 1$1,= аь1„ 1111н + 1 2112+ . + 1111и= ч, 1= ~+1, —., я2, 1т1+ 1~юг + "+ 1~ аа~ Решая систему (5.67), последовательно находим 1 =16 1;1 - а;11'111, 1 — 2, 3, ..., т, ~22 Й22 ~1р 1;2 = (а12 — 111121)/122, 1= 3, 4, ..., яг, (5.68) 1~~ = 4а~~-% — %2 —" — 1~,~-1 11lс — (017с- 111111 — 1121122 — ° ° — 11,1с-1 11с,й-1)/11сЬ 1 — ~+ 1 Заметим, что для вычисления диагональных элементов использует- ся операция извлечения квадратного корня. Поэтому метод Холецкого 159 уже не обязательно должна иметь на главной диагонали единицы, как это было в методе Гаусса, а требуется только, чтобы диагональные элементы 1н были положительными.
Если разложение (5.64) получено, то решение системы (5.63) сводится к последовательному решению двух систем с треугольными матрицами: Пример 5.16. Используя метод Холецкого, найдем решение системы уравнений с симметричной положительно определенной матрицей: 6. 25х1 — хг + О. 5хз = 7. 5, — х1 + 5хг + 2.12хз = -8.68 0.5х1 + 2.12хг + З.бхз = -0 24. По формулам (5.68) последовательно находим 1и = ~аи = Д.25 = 2.5, 1г1 = аг1/1и = — 1/2.5 = — 0.4, 6~ = аз~/6~ = 0.5/2Л = О 2, 6г = Аг — ф, = чЬ вЂ” О:16 = 2.2, 1зг = (азг — 1з11г1) = (2,12 — 0.2(-0.4))/2.2 = 1, = 1.6. 1зз = 160 называют еще и методом квадратных корней.
Доказано, что положительность соответствующих подкоренных выражений является следствием положительной определенности матрицы А. 2. Достоинства метода. Метод Холецкого обладает рядом ценных качеств, которые позволяют предпочесть его методу Гаусса, если требуется решить систему линейных алгебраических уравнений с симметричной и положительно определенной матрицей. Как нетрудно подсчитать, число операций, выполняемых в ходе вычисления разложения (5.64) по формулам (5.68), равно примерно тз/3. Учитывая, что для решения систем (5.66) требуется примерно 2тг арифметических операций, убеждаемся, что при больших т метод Холецкого требует вдвое меньше вычислительных затрат по сравнению с методом Гаусса. Учет симметричности матрицы А позволяет экономно использовать память ЭВМ при записи исходных данных задачи и результатов вычислений.
Действительно, для задания матрицы А достаточно ввести в память ЭВМ только элементы а," (1 >~ 7), расположенные на главной диагонали и под ней. В формулах (5.68) каждый такой элемент а,~ используется лишь однажды для получения 1;, и далее в вычислениях не участвует.
Поэтому в процессе вычислений найденные элементы 1,г могут последовательно замещать элементы а,". В результате нижняя треугольная матрица ь может быть расположена в той области памяти, где первоначально хранилась нижняя треугольная часть матрицы А. Применение для решения системы (5.63) метода Гаусса потребовало бы использования примерно вдвое большего объема памяти. Безусловным достоинством метода Холецкого является также его гарантированная устойчнвость. Следовательно, матрица х. такова: Система х.у = Ь имеет вид Решая ее, получаем у1 = 3, уг = -3.4, уз — 1.6, Далее из системы Юх = у которая имеет вид 3 5.9. Метод прогонки Рассмотрим лешод прогонки' — простой и эффективный алгоритм решения систем линейных алгебраических уравнений с трехдиагональными матрицами: 01х1-1 + Ь1х~ + сфх~+~ (5.69) ащ 1х„г+ Ьк 1х~ 1+ с„1хщ =4,ь а~хш 1 + Ьмх~ = д~, Системы такого вида часто возникают при решении различных задач математической физики, а также при решении других вычислитель- ных задач (например, приближения функций сплайнами).
1 Метод прогонки был предложен в начале 50-х годов независимо несколькими авторами, в том числе российскими учеными И.М. Гельфандом, О В. Локуциевским, В.С. Владимировым, А.С. Кронродом. 161 6-28 2.5 0 0 -0.4 2.2 0 0.2 1 1.6 2,5у1 = 7.5, -0.4у1 + 2.2уг = — 8,68, 02у1 + уг + 16уз = -0 24.
2.5х1 — 0.4хг + 0.2хз = 3, 2.2хг + хз = — ЗА, 1.6, находим решение 21 = 0.8, хг = -2, хз = 1. Ь1х1 + с1хг сгх1 + Ьгх2 + с2 хз = Н~, = "г 1. Вывод расчетных формул. Преобразуем первое уравнение системы (5.69) к виду х1 — — а~хг+ А (5.70) где а1 — -с1/Ь1, Д =, И1/Ь1. Подставим полученное для х1 выражение во второе уравнение систе- мы: аг(а1хг + ~У1) + Ьгхг + сгхг = иг. Преобразуем это уравнение к виду хг — агхз + Фг~ (5.71) х; = а;х,+1+ Вь (5.72) где а; = -с;/( Ь; + а;а, 1), А = (4 — аД 1)/(Ь; + а,а, 1).
На т-м шаге подстановка в последнее уравнение выражения х„„1— = ащ1хщ+ Д„1 дает аа(ащ1хщ+ Фщ-1) + Ьщхщ = 4Р. Отсюда можно определить значение х„: хщ =,Ощ = (4„— ащД„1)/(Ьщ + аща„1). Значения остальных неизвестных х, для г = т — 1, т — 2, ..., 1 теперь легко вычисляются по формуле (5.72). 2. Алгоритм прогонки. Сделанные преобразования позволяют организовать вычисления метода прогонки в два этапа'.
Прямой ход метода прогонки (пряжая прогонка) состоит в вычислении прогоночных коэффициентов а; (1 ~ ~1 ( т) и Д (1 ~ 1 ~~ т). При ~ = 1 коэффициенты вычисляют по формулам а1 = -с1/71> А = а1/711 71 = Ь1) (5.73) а при г = 2, 3, ..., т — 1 — по рекуррентным формулам ас = -с~/7ь А = (А а1А-1)/7ь 7в = Ь1+ аФь1. При 1 = т прямая прогонка завершается вычислением (5.74) Д = (И вЂ” а 8щ1)/7щ, 7 = Ьщ+ а а 162 (5.75) где аг = -сг/(Ьг + ага~),,8г = (4 — агД)/(Ьг + ага1). Выражение (5.71) подставляем в третье уравнение системы и т. д. На 1-м шаге этого процесса (1 < 1 ( т) '1-е уравнение системы преобразуется к виду Обратный ход метода прогонки (обратная прогонка) дает значения неизвестных. Сначала полагают з = Д„.
Затем значения остальных неизвестных вычисляют по формуле зг = а>хн1+ А> ~ = т — 1> т — 2,.-.> 1. (5.76) Вычисления ведут в порядке убывания значений з от т — 1 до 1. Пример 5.17. Используя метод прогонки, решим систему 5з1— = 2.0, 2з1 + 4.6з>г — зз = 3.3, 2лг + 3.6зз — 0.8х~ = 2.6, Зтз + 4.4х~ = 7.2, П р я м о й х о д. Согласно формулам (5.73) — (5.75) получаем 6~ = 5, а~ = -с1/7~ = 1/5 = 0.2, Д = Н~/77 = 2.0/5 = 0.4, 6г + ага> = 4.6 + 2.0.2 = 5, аг = -~/уг = 1/5 = 0.2, (>1г — аъА)/уг = (3.3 — 2 0.4)/5 = 0.5, Ъз + азаг = 3.6 + 2 0.2 = 4, аз = -сз/уз = 0.8/4 = 0.2, (4 — азА)/7з = (2.6 — 2'0 5)/4 = 0-4 >>4 + >г4аз 4.4 + 3 0.2 = 5, (>14 — йРз)/74 = (7.2 — 3'0-4)/5 = 1 2.
71 = 7г— Фг = 7з = Фз = О б р а т н ы и х о д. Полагаем з4 — р4 — 1.2. Далее находим зз = аз,т4 + Фз = 0 2'1 2 + 0.4 = 0.64, зг = агзз + рг = О 2'О 64 + 05 = 0 628 з~ — а1зг + о1 = 0.2 0.628 + 0.4 = 0.5256. Итак, получаем решение: з1 = = 0.5256, хг = 0.628, гз = 0.64, з4 = 1.2. 3. Свойства метода прогонки. Непосредственный подсчет показывает, что для реализации вычислений по формулам (5.73) — (5.76) требуется примерно 8т арифметических операций, тогда как в методе Гаусса это число составляет примерно (г/з)тз. Важно и то, что трехдиагональная структура матрицы системы позволяет использовать для ее хранения лишь Зт — 2 машинных слова.
Таким образом, при одной и той же производительности и оперативной памяти ЭВМ метод прогонки позволяет решать системы гораздо большей размерности, чем стандартный метод Гаусса для систем уравнений с заполненной матрицей. Приведем простые достаточные условия на коэффициенты системы (5.69), при выполнении которых вычисления по формулам прямой прогонки могут быть доведены до конца (ни один из знаменателей 7, не обратится в нуль).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
